스키마 없이 모든 경로를 색인하기 (DocumentDB Indexing, VLDB 2015)

출처

참고 이 페이지는 원문 번역이 아니라 한국어 해설이에요. 정확한 표현과 수치는 원문을 확인하세요.

한눈에

• DocumentDB 는 JSON 문서를 저장하는 멀티 테넌트 데이터베이스 서비스로, 사용자가 스키마나 보조 인덱스를 정의하지 않아도 모든 속성을 자동으로 색인합니다.
• 문서를 트리로 보고, 루트에서 값까지의 경로를 "용어(term)"로, 문서 ID 집합을 비트맵 게시 목록(postings list)으로 표현합니다.
• 색인은 잠금 없는 로그 구조의 Bw-tree 위에 저장되며, 기존 게시 목록을 읽지 않고 변경분만 덧붙이는 "blind incremental update"로 쓰기 증폭을 줄입니다.
• 색인 일관성(consistent, lazy, none)과 포함 및 제외 경로를 정책으로 고를 수 있게 했습니다. 이 개념은 지금 Cosmos DB 의 인덱싱 정책으로 이어집니다.

왜 나왔나

문서 데이터베이스를 쓰는 개발자는 스키마를 미리 정하지 않고 데이터를 넣기를 원합니다. 하지만 스키마가 없으면 어떤 필드에 인덱스를 만들어야 할지 알 수 없고, 인덱스가 없으면 쿼리가 전체 스캔이 됩니다. 반대로 모든 필드를 색인하면 쓰기마다 색인 갱신 비용이 커지고 저장 공간도 늘어납니다. 여기에 클라우드 서비스라는 조건이 더해집니다. 한 장비에 여러 고객의 컬렉션이 함께 살기 때문에, 각 컬렉션의 색인이 쓰는 CPU, 메모리, I/O, 저장 공간에 예측 가능한 상한이 있어야 합니다.

1.4절은 색인 설계 목표를 다섯 가지로 정리합니다. 스키마와 인덱스 관리 없이 자동 색인할 것, 저장과 성능의 균형을 설정할 수 있을 것, 계층적이고 관계형인 풍부한 쿼리를 지원할 것, 쓰기가 계속 몰려도 일관된 쿼리를 줄 것, 멀티 테넌트 환경에서 최악의 색인 저장량을 묶어 둘 것입니다.

핵심 아이디어

시스템 개요

1장은 DocumentDB 의 자원 모델을 설명합니다. 데이터베이스 계정 아래에 데이터베이스, 그 아래에 사용자, 권한, 컬렉션이 있고, 컬렉션에는 문서와 함께 저장 프로시저, 트리거, UDF, 첨부 파일이 들어갑니다. 모든 자원은 안정적인 논리 URI 를 가진 JSON 문서입니다. 컬렉션은 자원 파티션에 배치되고, 각 파티션은 복제본 집합으로 가용성을 얻습니다. 각 복제본 안에는 복제 상태 기계, JavaScript 런타임, 쿼리 처리기, 저장과 색인 하위 시스템을 갖춘 데이터베이스 엔진이 돌아갑니다. 일관성 수준은 strong, bounded-staleness, session, eventual 네 가지를 제공했습니다.

문서를 트리로, 색인도 문서로

2장의 출발점은 JSON 의 문법만 보고 구조는 가정하지 않는 것입니다. 문서는 가상의 루트 아래 속성 이름과 배열 인덱스가 간선이 되고 값이 잎이 되는 트리로 바뀝니다. 그러면 /location/0/country/France 같은 경로 하나가 문서의 사실 하나를 나타냅니다. 색인은 이런 경로들에서 문서 ID 로 가는 역방향 매핑이고, 여러 문서의 트리를 겹쳐 놓은 하나의 큰 트리로 볼 수 있습니다. 노드마다 용어와 게시 목록이 붙습니다. SQL 과 JavaScript 쿼리는 같은 중간 언어로 컴파일되어, 깊이와 상관없는 경로나 /location/*/France 같은 와일드카드 경로도 이 색인으로 풀 수 있습니다(그림 4, 그림 5).

경로를 용어로 인코딩하기

3장은 경로를 그대로 저장하면 너무 길어지므로, 경로의 일부만 잘라 용어로 쓰는 방법을 다룹니다. 그림 7은 네 가지 표현을 비교하고, 최종 설계는 두 가지를 함께 씁니다. 범위 쿼리와 정렬을 위한 "부분 정방향 경로"와, 같음 비교와 와일드카드를 위한 "부분 역방향 경로"(잎을 맨 앞에 두는 방식)입니다. 기본값은 용어당 세 구간이며, 그림 8 기준으로 조부모와 부모에 1바이트씩, 잎에 3바이트를 써서 5바이트가 됩니다. 숫자는 IEEE 754 표현을 쓰고, 0~100 사이에 몰린 값에 맞춘 해시를 따로 둡니다.

게시 목록은 문서 ID 비트맵입니다. ID 공간을 최대 16K 개씩의 게시 항목으로 나누고, 항목 선택자(PES)를 1~7바이트로 가변 인코딩해 작은 컬렉션은 아주 작게, 큰 컬렉션도 감당할 수 있게 했습니다.

색인 정책

3.3절은 사용자가 고를 수 있는 정책을 설명합니다. 문서나 경로를 포함하거나 제외할 수 있고(와일드카드 포함), 경로마다 hash, range, spatial, text 같은 색인 종류와 정밀도를 정할 수 있습니다. 색인 모드는 세 가지입니다.

정책을 바꾸면 별도 저장 공간 없이 온라인으로 그 자리에서 색인을 변환합니다.

물리 구조: Bw-tree 와 blind incremental update

4장은 색인을 담는 자료 구조를 다룹니다. 문서 하나를 넣으면 경로 수십 개의 게시 목록이 바뀌는데, 이 경로들은 키 공간에 흩어져 있어 B+ 트리로는 쓰기와 읽기 증폭이 커집니다. 그래서 Microsoft Research 의 Bw-tree 를 씁니다. Bw-tree 는 페이지를 바꾸는 대신 변경분(delta)을 매핑 테이블의 compare-and-swap 으로 붙이는 잠금 없는 구조이고, 저장소에는 여러 페이지의 변경을 약 4MB 플러시 버퍼에 모아 한 번의 I/O 로 씁니다.

핵심은 "blind incremental update"입니다. 문서를 넣을 때 기존 게시 목록을 읽어 와 고치는 대신, "이 용어에 문서 d 추가" 같은 변경분만 앞에 붙입니다. 나중에 페이지를 합칠 때 병합 콜백이 이 변경분들을 하나로 합치는데, 콜백은 순서가 바뀌거나 중복 적용되어도 결과가 같도록(교환 가능하고 멱등) 설계되었습니다. 문서 갱신은 이전 이미지와 새 이미지에서 뽑은 용어 집합의 차이로 계산합니다. lazy 모드에서는 지워진 문서를 무효화 비트맵으로 걸러 냅니다.

복제, 복구, 자원 거버넌스

색인은 1차 복제본만 문서를 분석해 만들고, 복제본 재구성 때는 Bw-tree 의 물리 데이터를 그대로 스트리밍합니다. 복구는 안정 LSN 까지의 체크포인트를 복원한 뒤 그 이후 문서를 다시 색인하는 두 단계입니다. 자원은 초당 Request Unit(RU/s) 예산으로 관리하고, 디스크 파일은 실제 크기 S 에 66.6% 여유를 두어 약 1.5S 로 잡습니다.

실험과 결과

5장은 운영 중인 서비스에서 얻은 관찰을 보여 줍니다.

• 용어 빈도(그림 12): 모든 클러스터에서 용어 빈도가 지프의 법칙(Zipf)을 따릅니다.
• 스키마 다양성(그림 13): 100MB 에서 10GB 까지 컬렉션 크기별로 색인 트리 노드의 99.105~99.33% 가 잎이고 내부 노드는 1% 미만입니다. 문서 구조는 비슷하고 값이 다양하다는 뜻입니다.
• 용어 크기와 정확도(그림 14): 10GB 컬렉션에서는 용어 5~6바이트가 가장 좋은 정밀도를 보였습니다.
• 색인 오버헤드(그림 15): 테넌트와 데이터 센터별 평균과 99번째 백분위 색인 오버헤드를 보여 줍니다. 본문에 구체 수치는 없습니다.
• blind update 효과(그림 16): 메모리 예산 4MB 에서 색인 크기가 커져도 blind update 는 읽기 I/O 를 거의 만들지 않지만, 기존 방식은 쓰기마다 읽기 한 번이 필요함을 보여 줍니다.

지금 Azure 에서는

DocumentDB 는 2017년 Azure Cosmos DB 로 이름이 바뀌어 그 NoSQL API 가 되었습니다. 공식 문서의 인덱싱 정책은 이 논문의 설계를 그대로 드러냅니다. 기본 정책은 모든 항목의 모든 속성을 색인하고(includedPaths 의 /*), 경로 단위로 포함과 제외를 정하며, 인덱싱 모드로 consistent 와 none 을 고릅니다. 논문의 lazy 모드는 공식 문서에서 쿼리 결과가 불완전할 수 있다는 이유로 새 컨테이너에서는 선택할 수 없게 정리되었습니다. 비용 단위인 Request Unit 도 이 논문의 자원 거버넌스에서 이미 쓰였습니다.

함께 읽기

• Azure Cosmos DB: 이 사이트의 기능 문서
• Socrates: 같은 시기 관계형 데이터베이스 쪽의 클라우드 재설계
• Azure Cosmos DB 인덱싱 정책 공식 문서
• Microsoft Research 논문 페이지