KahaDB가 인덱스를 위해 B-Tree를 사용하는 이유는?

KahaDB가 인덱스를 위해 B-Tree를 사용하는 이유는?

ActiveMQ Classic의 기본 스토리지 엔진인 KahaDB는 압도적인 디스크 I/O 성능을 자랑합니다. 그 비결은 앞서 다루었듯, 데이터를 무식하고 빠르게 이어 붙이는 '저널 파일(db-*.log)'과 그 데이터의 위치를 찰나의 순간에 찾아내는 '인덱스 파일(db.data)'의 완벽한 분업 아키텍처에 있습니다.

여기서 인덱스 파일의 심장 역할을 하는 핵심 자료구조가 바로 B-Tree (Balanced Tree)입니다. 컴퓨터 공학에는 해시 테이블(Hash Table)이나 일반 이진 트리(Binary Tree) 등 수많은 자료구조가 존재하지만, KahaDB는 왜 메인 인덱스 엔진으로 반드시 B-Tree를 고집했을까요? 메시지 브로커의 태생적 한계와 디스크 물리적 특성을 교차하여 그 이유를 상세히 분석합니다.

---

1. 큐(Queue)의 생명인 '순차 탐색(Sequential Access)' 지원

메시지 큐의 기본 원칙은 선입선출(FIFO)입니다. 먼저 들어온 메시지가 먼저 나가야 하며, 때로는 큐 브라우저(Queue Browser)를 통해 큐에 쌓인 수만 개의 메시지를 순서대로 스캔해야 할 때도 있습니다.

• 해시 테이블(Hash Table)의 한계: 만약 인덱스를 해시 기반으로 만들었다면, 단일 메시지를 고유 ID로 찾아내는 속도는 극단적으로 빠를 것입니다. 하지만 해시 테이블은 데이터의 '순서'를 전혀 보장하지 않습니다. 1번부터 100번까지의 메시지를 순서대로 가져오려면 해시 테이블에서는 엄청난 정렬 오버헤드가 발생합니다.
• B-Tree의 강점: B-Tree는 내부의 모든 데이터 키(Key) 값을 항상 오름차순 또는 내림차순으로 정렬된 상태(Sorted)로 유지합니다. 루트 노드에서 시작하여 가장 왼쪽의 리프(Leaf) 노드에 도달한 뒤, 우측으로 순차적인 스캔을 진행하기만 하면 큐에 들어온 메시지를 시간순으로 완벽하게 읽어낼 수 있습니다.

2. 디스크 I/O 블록에 최적화된 노드(Node) 구조

db.data 인덱스 파일은 브로커의 힙 메모리에도 일부 캐싱되지만, 본질적으로는 영속성을 위해 디스크(HDD/SSD)에 저장되는 물리적 파일입니다. 디스크에서 데이터를 읽어오는 작업은 메모리 접근보다 수만 배 느리기 때문에, 디스크 헤더가 움직이는 횟수(I/O 횟수)를 최소화하는 것이 인덱스 성능의 핵심입니다.

• 일반 이진 트리(Binary Tree)의 한계: 이진 트리는 하나의 노드가 단 하나의 데이터만 가지고, 가지(Branch)가 2개로만 뻗어 나갑니다. 100만 개의 데이터가 있다면 트리의 깊이(Depth)가 기하급수적으로 깊어집니다. 깊이가 깊다는 것은 목적지에 도달하기 위해 디스크의 이곳저곳을 수십 번씩 흩어져서 읽어야 함을 의미합니다.
• B-Tree의 강점: B-Tree의 'B'는 통상적으로 Broad(넓은) 또는 Block(블록)을 의미한다고도 해석됩니다. B-Tree는 하나의 커다란 노드 안에 수십에서 수백 개의 키와 포인터를 배열 형태로 꽉꽉 채워 넣습니다. 이 하나의 노드 크기를 운영체제의 디스크 기본 읽기 단위(Page Size, 보통 4KB 또는 8KB)와 정확히 일치시키면, 단 한 번의 디스크 읽기 요청(I/O)만으로 수백 개의 인덱스 키를 통째로 메모리에 올려서 탐색할 수 있습니다. 결과적으로 트리의 깊이가 매우 얕게(Shallow) 유지되어 극단적으로 적은 디스크 I/O만으로 원하는 데이터 위치를 찾아냅니다.

3. 데이터 편향(Skew) 방지와 일정한 탐색 속도 보장

메시지 브로커에는 초당 수천 건의 메시지가 예측 불가능한 순서와 시간대에 인입됩니다.

• 불균형 트리(Unbalanced Tree)의 위험성: 일반적인 트리 구조에 데이터가 한쪽 방향으로만 편향되게 계속 입력되면, 트리가 한쪽으로 길게 늘어지는 '선형 리스트(Linked List)'처럼 변질됩니다. 이렇게 되면 트리의 탐색 성능은 완전히 붕괴되어 전체 큐를 처음부터 끝까지 뒤져야 하는 치명적인 병목이 발생합니다.
• B-Tree의 균형 유지 (Balancing): B-Tree의 가장 위대한 특성은 데이터가 어떤 순서로, 얼마나 많이 들어오든 간에 트리의 모든 리프(Leaf) 노드가 항상 같은 깊이를 유지하도록 스스로 구조를 재배치(Balancing)한다는 점입니다. 노드가 가득 차면 반으로 분할(Split)하고, 비어 있으면 인접한 노드와 병합(Merge)합니다. 이 덕분에 KahaDB에 메시지가 1만 개 있든 1,000만 개 있든 브로커는 항상 일정하고 예측 가능한 매우 빠른 속도로 메시지를 찾아낼 수 있습니다.

4. 빈번한 삽입과 삭제(Enqueue & Dequeue)에 대한 강력한 내성

데이터베이스(RDBMS)의 데이터는 한 번 저장되면 꽤 오랜 시간 유지되는 경향이 있습니다. 반면, 메시지 브로커의 데이터(메시지)는 '들어오는 즉시 소비되어 삭제되는(High Churn Rate)' 매우 극단적인 라이프사이클을 가집니다. 초당 1만 번의 Insert와 1만 번의 Delete가 동시에 일어나는 가혹한 환경입니다.

B-Tree는 이러한 잦은 노드의 갱신과 삭제 작업에서도 트리 전체를 잠그지(Lock) 않고, 필요한 국소적인 노드 범위 내에서만 분할과 병합을 처리하도록 최적화된 알고리즘을 갖추고 있습니다. 따라서 수백 명의 생산자와 소비자가 동시에 KahaDB 인덱스 파일에 접근하여 쓰고 지우는 작업을 수행하더라도, 브로커 내부의 경합(Contention)을 최소화하면서 무결성을 지켜냅니다.

---

결론: 순차 쓰기 저널과 B-Tree의 완벽한 앙상블

결론적으로 KahaDB가 B-Tree를 선택한 것은 타협이 아닌 필연이었습니다.
무거운 메시지 본문은 디스크 I/O의 최고 속도를 낼 수 있는 '순차 쓰기(Append-Only)' 방식의 저널 파일에 맡겨두고, 그 데이터를 빠르고 순차적으로 찾아내는 검색 로직은 디스크 블록 읽기에 가장 최적화된 'B-Tree' 인덱스 파일에 전담시켰습니다.

이 두 가지 아키텍처의 결합이 바로 ActiveMQ Classic이 오랜 세월 동안 엔터프라이즈 메시징 시장의 표준으로서 엄청난 대용량 트래픽을 견뎌낼 수 있었던 시스템적 기반입니다.