본문으로 건너뛰기
MongoDB WiredTiger의 B+Tree에 없는 형제 연결
목차

MongoDB WiredTiger의 B+Tree에 없는 형제 연결 (2025-02)

원문 정보

  • 원문: MongoDB WiredTiger의 B+Tree
  • 매체 · 게시일: 카카오 기술블로그 · 2025-02-20
  • 저자: andy.hj (카카오 분산데이터베이스 조직, MongoDB 운영)
  • 원문 내용을 바탕으로 재구성한 요약입니다.

InnoDB와 닮았으리라 생각했던 B+Tree

MongoDB를 처음 운영하던 필자는 WiredTiger의 B+Tree도 InnoDB와 비슷하리라 예상했습니다. 그 예상으로는 이해하기 어려운 동작이 있었고, 두 엔진의 내부 구현을 비교하면서 의문을 풀었습니다. 같은 B+Tree라도 페이지를 연결하고 레코드를 관리하는 방법은 달랐습니다.

앞 글 “MongoDB WiredTiger의 파일 구조”가 구성 요소와 아키텍처를 다뤘다면, 시리즈의 두 번째 글인 이번에는 메모리 안의 페이지와 변경 이력을 추적합니다. 확인에 쓴 환경은 MongoDB Community Edition v6.0.15이며, 분석 도구는 gdb입니다. 타임스탬프, 잠금, 이빅션은 이번 범위에 포함하지 않았고, 필자는 기회가 되면 다룰 후속 주제로 남겨 두었습니다.

배열을 그대로 둔 채 이어지는 WT_UPDATE

WiredTiger는 디스크의 페이지를 메모리로 읽을 때 키/값 쌍마다 WT_ROW를 만들고, 리프 페이지 안에서 배열로 관리합니다. __wt_row_search는 이 배열을 이진 탐색해 원하는 로우를 찾습니다. 문제는 중간 삽입과 삭제입니다. 배열에 직접 반영하면 다른 로우까지 조정해야 하므로, WiredTiger는 메모리의 WT_ROW 배열을 직접 고치지 않고 별도 자료구조에 변경사항을 보관합니다.

기존 키의 변경과 삭제를 담당하는 구조체는 WT_UPDATE입니다. WT_UPDATE 배열은 WT_ROW 배열과 크기가 같고, 각 키에 해당하는 항목에서 업데이트 체인이 이어집니다. 같은 키를 여러 번 고치면 그 버전들이 연결 리스트에 남고, 가장 최근 변경이 체인의 헤드에 붙습니다.

gdb에서 확인한 예제는 num: 7인 도큐먼트의 cnt를 $set으로 1, 2, 3으로 바꾼 작업입니다. __wt_update_serial에 브레이크포인트를 걸어 살펴보니, next를 따라 txnid 2416, 2414, 2412 순으로 연결되어 있었습니다. 최신 변경부터 이전 버전으로 이어지는 모습입니다. 이 예제는 컬렉션 파일의 트리이며, 키는 num이 아닌 recordId입니다.

같은 데이터의 여러 버전을 유지하는 MVCC 덕분에 읽기와 쓰기가 서로 방해하지 않으면서 스냅샷 격리를 지원할 수 있습니다. 각 WT_UPDATE에는 txnid 같은 정보도 들어 있습니다. WiredTiger는 스냅샷 격리 외에 REPEATABLE_READ, READ_COMMITTED도 지원하지만, MongoDB에서는 스냅샷 격리만 사용합니다.

새 키가 쌓이는 구간별 스킵 리스트

기존 키를 고치는 작업과 새 키를 넣는 작업은 다릅니다. 페이지에 키 1과 10000만 있다면 그 사이에 수많은 키가 들어올 수 있고, 이를 단순 연결 리스트에 보관하면 새로 넣은 키를 찾는 비용이 커집니다. 그래서 신규 키를 담당하는 WT_INSERT에는 스킵 리스트를 사용합니다.

스킵 리스트는 기존 키 사이의 구간마다 존재합니다. 첫 키 앞과 마지막 키 뒤도 포함해야 하므로, 구간을 관리하는 WT_INSERT_HEAD는 WT_ROW 배열의 항목 수보다 하나 더 필요합니다. 새 키도 나중에 수정될 수 있습니다. 이를 위해 WT_INSERT에도 WT_UPDATE 체인을 둡니다.

새 컬렉션에 num 1부터 5까지 넣으며 __wt_insert_serial을 관찰한 결과, 삽입한 키들은 키 순서대로 정렬된 스킵 리스트에 쌓였습니다. 최대 깊이는 10입니다. WT_ROW 배열을 재조정하지 않고 삽입하면서도, 새 키가 많아졌을 때 단순 연결 리스트보다 빠르게 조회할 수 있는 방식입니다.

이 자료구조를 사용하는 모습은 인덱스 파일과 컬렉션 파일에서 달라집니다. MongoDB 인덱스는 도큐먼트 대신 도큐먼트를 찾기 위한 recordId를 value로 저장합니다. 인덱스 값이 바뀔 때는 삭제와 삽입으로 처리하므로 업데이트 체인이 길게 이어지지 않고 새 WT_INSERT가 생깁니다.

컬렉션 파일에서는 순차 증가하는 recordId가 key입니다. value의 변경을 허용하므로 같은 키의 업데이트 체인이 길어질 수 있습니다. 삽입 위치에는 제약이 있습니다. 사용자가 중간 recordId를 임의로 넣을 수 없기 때문에, 새 데이터는 WT_ROW 배열 마지막 슬롯에 해당하는 스킵 리스트에만 들어갑니다.

WiredTiger의 기능 중 일부만 사용하는 모습입니다. WiredTiger는 MongoDB가 2014년에 인수한 오픈소스 스토리지 엔진으로, 애초에 MongoDB만을 위해 개발된 엔진은 아닙니다. MongoDB는 제공되는 기능을 자신의 데이터 관리 방식에 맞게 활용합니다.

한 번의 삽입이 하나의 트리에서 끝나는 것도 아닙니다. 이 테스트의 도큐먼트 삽입은 컬렉션 데이터, _id 인덱스, num 인덱스, oplog 등에 여러 삽입을 일으킵니다. 일련의 작업은 WiredTiger 트랜잭션으로 수행되므로 쓰기의 일부만 반영되는 일은 없습니다.

약 7%의 정렬 차이를 보인 테스트

MongoDB는 인덱스에 지정한 방향의 역순으로도 정렬할 수 있습니다. 예를 들어 { a: 1, b: 1 } 인덱스는 { a: -1, b: -1 } 정렬도 지원합니다. 지원 여부와 내부 탐색 비용은 별개입니다. WT_ROW 배열에서는 인덱스를 늘리거나 줄이면 되지만, 새로 삽입한 데이터를 담는 스킵 리스트는 단방향으로 연결되어 있습니다.

오름차순 인덱스를 만든 뒤 10,000건을 넣고, num의 오름차순과 내림차순 조회에 각각 limit(100)을 적용했습니다. 모든 데이터가 메모리의 스킵 리스트에 있던 이 조건에서는 정렬 방향에 따라 약 7%의 성능 차이가 났습니다.

서버를 재시작한 뒤에는 결과가 달라졌습니다. 스킵 리스트가 비고 모든 데이터가 WT_ROW 배열로 구성된 상태에서는 방향에 따른 차이가 거의 없었습니다.

WiredTiger는 PREV_ITEM, PREV_INS 매크로로 스킵 리스트의 역순 조회를 최적화합니다. 그래도 첫 시나리오의 내림차순 조회에서는 __cursor_skip_prev가 조회 건수만큼 추가로 호출됐습니다. 필자는 이 호출 때문에 오름차순보다 약간의 성능 저하가 있었던 것으로 봅니다. 재시작 후에는 이 함수 없이 방향에 따라 __cursor_row_next 또는 __cursor_row_prev만으로 조회했습니다.

이 차이는 일반적인 서비스 환경에서 체감하기 어려운 경우가 많을 것이라는 판단입니다. 필자는 양방향 정렬이 필요하다면 크게 걱정하지 않고 사용해도 된다고 봅니다. 한 방향의 정렬만 쓴다면 인덱스와 조회의 정렬 방향을 맞추는 편이 더 최적화된 선택이라는 설명입니다.

다음 리프를 찾아 올라가는 부모 페이지

한 리프의 끝까지 읽은 커서는 다음 리프를 찾아야 합니다. 보통의 B+Tree는 범위 쿼리나 순차 접근을 위해 같은 레벨의 페이지를 연결하지만, WiredTiger에는 이 연결이 없습니다. 다음 페이지로 이동할 때 부모를 거칩니다.

루트와 인터널 페이지는 레코드 대신 자식 페이지를 참조하는 WT_REF 배열인 __index를 유지합니다. 각 페이지의 parent_ref는 자신을 참조하는 WT_REF를 가리키고, WT_REF의 home은 상위 부모 페이지를 가리킵니다. 옆 페이지로 직접 향하는 포인터는 없습니다.

페이지 이동을 확인한 별도 예제에서는 1부터 10,000까지 순서대로 데이터를 넣은 뒤 { num: 1 } 인덱스를 생성했습니다. 트리는 루트와 리프의 두 계층으로 구성됐고, 루트의 WT_REF 배열에는 유효한 항목이 14개 있었습니다. 각 리프의 로우 수인 1981, 651, …, 400을 합하면 삽입한 10,000건과 일치했습니다.

num >= 1981 범위 쿼리는 첫 리프의 마지막 값에서 시작합니다. 그다음 값을 읽으려면 페이지를 옮겨야 합니다. 이때 호출된 __tree_walk_internal은 부모의 WT_REF 배열에서 현재 페이지의 슬롯을 찾아 다음 슬롯으로 이동했습니다. 이어서 확인한 커서는 651개 항목이 있는 다음 리프를 가리켰습니다.

이렇게 부모를 거치는 이유는 페이지 분할 비용과 연결됩니다. 형제 페이지가 연결되어 있다면 분할할 때 부모의 __index뿐 아니라 인접 페이지의 포인터도 고쳐야 합니다. 데이터 무결성을 보장하려면 잠금이 필요하고, 수정할 곳이 늘수록 잠금 경합과 성능 저하로 이어질 수 있습니다.

WiredTiger는 분할 과정에서 부모의 __index를 CAS로 원자적으로 갱신합니다. CAS는 메모리의 값을 비교하고 조건이 맞으면 교체하는 연산입니다. 변경 페이지를 항상 파일의 새 위치에 쓰는 no-overwrite 방식에서 여러 포인터를 함께 갱신하려면 처리가 복잡해지고 CAS 활용도 제한될 것이라는 게 필자의 해석입니다.

형제 연결을 두지 않으면 연결 관리가 단순해지고 원자적 연산을 쓰기 쉬워집니다. 그 대신 여러 페이지를 훑는 범위 쿼리는 부모를 거치는 추가 작업 때문에 상대적으로 비효율적일 수 있습니다. 필자는 단일 페이지를 대상으로 하는 쿼리가 주로 쓰이는 환경이라면 이 선택이 더 효과적일 수 있다고 봅니다.

잠금부터 획득하는 InnoDB의 동시성 제어

InnoDB는 같은 레벨의 페이지를 양방향 연결 리스트로 잇습니다. 범위 쿼리가 부모 페이지를 거치지 않고 다음 페이지로 이동할 수 있는 이유입니다. 페이지 분할 때는 인접 페이지의 연결도 조정해야 하므로, 연결을 관리하는 비용과 복잡성이 따릅니다.

리프 페이지 안에서도 출발점이 다릅니다. InnoDB는 레코드를 단방향 연결 리스트로 관리해 삽입과 삭제를 빠르게 처리합니다. 하지만 한 페이지에 수천 개의 레코드가 있다면 마지막 레코드를 찾기까지 긴 탐색이 필요할 수 있습니다.

이를 보완하는 배열이 페이지 디렉터리입니다. 정렬된 레코드의 포인터를 4~8개 간격으로 관리하고, 먼저 디렉터리를 이진 탐색해 원하는 값 근처로 이동합니다. 남은 구간은 연결 리스트를 따라 찾습니다. WiredTiger가 배열의 변경 비용을 리스트로 보완했다면, InnoDB는 리스트의 탐색 비용을 배열로 보완하는 접근입니다.

이 차이를 동시성 제어와 연결해서도 볼 수 있습니다. WiredTiger는 잠금을 최소화하는 방향으로 설계되어 있으며, WT_UPDATE 체인의 변경에도 CAS를 활용합니다. 충돌이 없으리라 가정하고 연산하다가 충돌하면 재시도하는 낙관적 동시성 제어입니다. 충돌이 드문 환경에서는 최선의 선택이 될 수 있지만, 충돌이 잦으면 성공할 때까지 재시도하면서 쿼리 성능을 예측하기 어려워질 수 있습니다.

InnoDB는 연산 전에 잠금을 획득하는 비관적 동시성 제어를 사용합니다. 필자는 레코드와 페이지가 연결 리스트로 구성된 방식이 갭 락 같은 잠금 기법을 적용하기에 유리할 것으로 봅니다. 잠금을 얻은 뒤 연산하므로 비교적 균일한 성능을 보일 수 있다는 해석도 덧붙입니다. 어느 방식이 적합한지는 서비스 특성에 달려 있으며, 이 설명은 복합적인 설계 이유 가운데 동시성 제어에 초점을 둔 관점입니다.

WiredTiger와 InnoDB의 구현 비교와 관찰 수치
항목WiredTigerInnoDB
동일 레벨 페이지 간 연결없음있음
리프 페이지의 레코드 저장ArrayLinked List
성능 보완을 위한 추가 구조Linked List, Skip ListArray
동시성 제어 방식OptimisticPessimistic
항목값
테스트 데이터10,000건, 루트와 리프 2계층, 루트 WT_REF 14개
스킵 리스트 최대 깊이10
정렬 방향 차이, 스킵 리스트 조회약 7%
정렬 방향 차이, WT_ROW 배열 조회거의 없음
마지막 수정 일자