LSM Tree란 무엇인가
LSM Tree(Log-Structured Merge Tree)는 데이터를 즉시 디스크에 반영하지 않고, 메모리에 모아두었다가 순차적으로 정리해서 저장하는 자료구조입니다. 이름 그대로 로그를 쌓듯이 데이터를 기록한 뒤, 이를 병합(Merge)하며 정돈된 트리 구조를 유지하는 방식입니다. RocksDB, LevelDB, Cassandra, HBase 등 대규모 쓰기 처리가 필요한 데이터베이스에서 핵심 저장 엔진으로 사용됩니다.
기존의 B-Tree가 ‘쓰기 시점에 정렬된 위치를 찾아 바로 갱신’하는 방식이라면, LSM Tree는 ‘일단 빠르게 기록하고 나중에 정리’하는 전략을 씁니다. 마치 책상 위에 서류를 받는 즉시 서랍 정리함에 순서대로 꽂아 넣는 대신, 일단 쌓아두었다가 나중에 한꺼번에 정리하는 것과 비슷합니다. 매번 정리하는 수고를 줄이는 대신, 나중에 몰아서 정리하는 비용을 감수하는 셈입니다.
동작 원리: MemTable과 SSTable
LSM Tree의 쓰기 과정은 크게 두 단계로 나뉩니다.
- MemTable 쓰기: 새로운 데이터는 먼저 메모리 상의 정렬된 자료구조인 MemTable에 기록됩니다. 메모리 쓰기이므로 매우 빠르며, 디스크 탐색(Seek) 비용이 전혀 들지 않습니다.
- SSTable로 플러시(Flush): MemTable이 일정 크기 이상 쌓이면, 정렬된 상태 그대로 디스크에 파일로 기록합니다. 이 파일을 SSTable(Sorted String Table)이라 부르며, 한 번 생성되면 수정되지 않는 불변(Immutable) 파일입니다.
- 컴팩션(Compaction): 시간이 지나며 SSTable이 여러 개 쌓이면, 백그라운드에서 이를 병합하며 오래되거나 삭제된 데이터를 정리합니다. 이 과정을 컴팩션이라고 합니다.
읽기 요청이 들어오면 MemTable부터 확인하고, 없으면 여러 SSTable을 최신 순서대로 탐색합니다. 여러 파일을 뒤져야 하므로 읽기 성능은 B-Tree보다 불리할 수 있는데, 이를 보완하기 위해 Bloom Filter를 활용해 특정 SSTable에 데이터가 없음을 빠르게 판별하기도 합니다.
실무에서 왜 사용하는가
LSM Tree의 가장 큰 장점은 쓰기 작업이 항상 순차 입출력(Sequential I/O)으로 처리된다는 점입니다. 디스크, 특히 HDD와 SSD 모두 순차 쓰기가 랜덤 쓰기보다 훨씬 빠르기 때문에, 쓰기 처리량이 중요한 시스템에서 큰 이점을 갖습니다.
예를 들어 로그 수집 시스템이나 시계열 데이터베이스처럼 초당 수만 건 이상의 쓰기가 발생하는 환경에서는, 매번 데이터 위치를 찾아 갱신하는 B-Tree 방식보다 LSM Tree가 훨씬 효율적입니다. 대신 컴팩션 과정에서 CPU와 디스크 I/O를 추가로 소모하고, 읽기 시 여러 파일을 조회해야 하는 트레이드오프가 존재합니다. 이런 특성 때문에 LSM Tree는 ‘쓰기가 많고 읽기는 상대적으로 덜 빈번한’ 워크로드에 특히 적합한 구조로 평가받습니다.