B-Tree와 LSM-Tree의 데이터베이스 스토리지 엔진 내부 논리와 쓰기 증폭 문제

팀 내 세미나를 준비하면서 여러 논문과 레퍼런스를 뒤져봤는데, 한글로 속 시원하게 정리된 곳이 없더군요. 그래서 제 경험을 녹여 직접 작성해 봤습니다. 데이터베이스 시스템의 성능을 결정짓는 가장 핵심적인 요소는 디스크 인터페이스의 I/O 특성을 고려한 자료구조의 선택입니다. 수십 년간 관계형 데이터베이스 관리 시스템(RDBMS)의 사실상 표준 스토리지 엔진을 책임져 온 구조는 B-Tree, 특히 B+Tree의 변형입니다. B-Tree는 트리의 높이를 최소화하여 디스크 탐색 비용을 일정하게 유지함으로써 O(log N)의 안정적인 검색 성능을 보장합니다. 디스크 블록 단위로 노드를 구성하여 순차 접근보다는 임의 접근(Random Access)에 최적화되어 있습니다. 메모리에 루트와 상위 노드들을 캐싱하고 말단 리프 노드에 실제 데이터나 포인터를 정렬된 상태로 보관하므로 특히 범위 검색(Range Query)에 압도적인 강점을 가집니다. 그러나 새로운 데이터가 삽입되거나 삭제될 때 발생하는 노드 분할(Node Split) 현상은 디스크의 파편화를 유발하고 잦은 랜덤 I/O를 강제합니다. 최근 대용량 데이터의 빠른 적재가 요구되는 분산 데이터베이스나 시계열 데이터베이스 환경에서는 삽입 시 랜덤 쓰기의 병목을 극복하기 위해 LSM-Tree(Log-Structured Merge Tree) 구조가 각광받고 있습니다. LSM-Tree는 모든 쓰기 작업을 디스크의 임의 공간에 바로 기록하는 대신, 먼저 인메모리 버퍼인 MemTable에 데이터를 수집하여 정렬합니다. MemTable이 특정 크기에 도달하면 이를 디스크에 순차적(Sequential)으로 플러시(Flush)하여 Immutable SSTable(Sorted String Table) 형태로 저장합니다. 기계식 HDD뿐만 아니라 최신 NVMe SSD에서도 랜덤 쓰기보다는 순차 쓰기의 대역폭이 훨씬 크고 마모 평준화에 유리하기 때문에 이 구조는 폭발적인 쓰기 스루풋을 제공합니다. 하지만 LSM-Tree 구조는 데이터가 여러 층의 SSTable에 분산되어 있으므로 단일 레코드의 조회를 위해 다중 디스크 접근을 해야 할 수 있는 읽기 불이익을 가집니다. 이를 보완하기 위해 블룸 필터(Bloom Filter)를 적용하여 조회할 데이터가 파일 내에 존재하지 않는지 확률적으로 먼저 검증합니다. 또한 시간이 지남에 따라 파편화된 SSTable들을 백그라운드에서 병합하고 불필요한 오래된 버전의 데이터를 삭제하는 컴팩션(Compaction) 과정이 필수적입니다. 이 컴팩션 작업 수행 도중 과도한 디스크 I/O가 소모되는 쓰기 증폭(Write Amplification) 현상이 LSM-Tree의 가장 큰 기술적 숙제로 남아 있으며, LevelDB 모델이나 RocksDB의 향상된 병합 알고리즘들이 이 문제를 최소화하기 위해 고안되었습니다.