[Daily morning study] LSM Tree (Log-Structured Merge-Tree) 작동 원리
#daily morning study
LSM Tree란
LSM Tree(Log-Structured Merge-Tree)는 1996년 Patrick O’Neil 등이 발표한 자료구조로, 쓰기 성능을 극대화하기 위해 설계됐다. RocksDB, LevelDB, Cassandra, HBase, InfluxDB 등 대용량 쓰기가 중요한 시스템에서 광범위하게 사용된다.
전통적인 B+Tree 기반 스토리지 엔진은 랜덤 I/O가 많이 발생해서 디스크 쓰기 성능이 좋지 않다. LSM Tree는 모든 쓰기를 순차 I/O로 바꿔서 이 문제를 해결한다.
핵심 구조
LSM Tree는 크게 두 계층으로 나뉜다.
메모리 계층: MemTable
- 쓰기 요청이 오면 디스크에 직접 쓰지 않고 메모리의 MemTable에 먼저 기록한다
- MemTable은 보통 레드-블랙 트리나 스킵 리스트로 구현되어 메모리 내 정렬 상태를 유지한다
- 동시에 WAL(Write-Ahead Log)에 순차적으로 기록해서 장애 복구를 보장한다
- MemTable이 일정 크기에 도달하면 Immutable MemTable로 전환되고, 새 MemTable이 쓰기를 받는다
디스크 계층: SSTable (Sorted String Table)
- Immutable MemTable은 디스크에 SSTable 파일로 플러시(flush)된다
- SSTable은 키-값 쌍이 정렬된 불변(immutable) 파일이다
- 한 번 쓰면 수정하지 않고, Compaction을 통해 병합/정리한다
Write → MemTable (메모리, 정렬)
↓ (flush)
Level 0 SSTable (디스크)
↓ (compaction)
Level 1 SSTable
↓ (compaction)
Level 2 SSTable
...
쓰기 과정
- 클라이언트가 key-value 쓰기 요청
- WAL에 순차 기록 (내구성 보장)
- MemTable에 삽입 (메모리, O(log N))
- MemTable이 임계치 도달 → Immutable MemTable으로 전환
- 백그라운드 스레드가 디스크에 SSTable로 플러시
- Level 0 SSTable이 쌓이면 Compaction 실행
모든 쓰기가 순차적(sequential write)이라 HDD, SSD 모두에서 랜덤 쓰기보다 훨씬 빠르다.
읽기 과정
읽기는 쓰기보다 복잡하다.
- MemTable 먼저 탐색 (가장 최신 데이터)
- Immutable MemTable 탐색
- Level 0 SSTable 탐색 (여러 파일 모두 확인해야 할 수 있음)
- Level 1, 2, … 순서로 탐색
최악의 경우 모든 레벨을 탐색해야 하므로 읽기 성능이 B+Tree보다 떨어질 수 있다. 이를 보완하기 위해 Bloom Filter를 사용한다.
Bloom Filter 활용
각 SSTable에 Bloom Filter를 붙여서, 특정 키가 해당 SSTable에 존재하지 않는다면 디스크 I/O 없이 빠르게 건너뛸 수 있다. 존재하지 않는 키 조회 성능이 크게 향상된다.
Compaction
SSTable이 쌓이면 읽기 성능이 나빠지고 디스크 공간도 낭비된다. Compaction은 여러 SSTable을 병합해서 정리하는 작업이다.
Size-Tiered Compaction
- 비슷한 크기의 SSTable 여러 개를 하나로 병합
- 쓰기 증폭(Write Amplification)이 적다
- 하지만 임시로 2배 공간이 필요하고, 읽기 성능이 나쁠 수 있다
- Cassandra 기본 전략
Leveled Compaction
- 각 레벨의 총 크기를 고정 비율로 제한 (예: Level 1=10MB, Level 2=100MB, Level 3=1GB)
- Level N의 SSTable이 가득 차면 Level N+1로 Compaction
- 한 레벨 내에서 키 범위가 겹치지 않도록 유지
- 읽기 성능이 좋고 공간 효율이 높다
- 하지만 쓰기 증폭이 크다
- RocksDB, LevelDB 기본 전략
Leveled Compaction 구조:
Level 0: [SST-A] [SST-B] [SST-C] ← 키 범위 겹침 가능
Level 1: [0-100] [101-200] [201-300] ← 키 범위 겹침 없음
Level 2: [0-10] [11-20] ... [291-300] ← 더 세밀하게 분리
삭제 처리: Tombstone
LSM Tree에서 삭제는 즉시 데이터를 지우지 않는다. 대신 Tombstone(삭제 마커)를 삽입한다.
- 읽기 시 Tombstone을 발견하면 해당 키는 삭제된 것으로 처리
- Compaction 중에 Tombstone과 실제 데이터가 함께 처리되면서 최종 삭제
이 방식 때문에 삭제된 데이터가 Compaction 전까지 디스크에 잔류할 수 있다.
LSM Tree vs B+Tree 비교
| 항목 | LSM Tree | B+Tree |
|---|---|---|
| 쓰기 성능 | 매우 빠름 (순차 I/O) | 상대적으로 느림 (랜덤 I/O) |
| 읽기 성능 | 상대적으로 느림 (여러 파일 탐색) | 빠름 (트리 탐색) |
| 공간 효율 | Compaction 전까지 낮음 | 높음 |
| 쓰기 증폭 | Compaction에 따라 다름 | 낮음 |
| 적합한 워크로드 | 쓰기 집약적 | 읽기/쓰기 균형 |
Write Amplification
쓰기 증폭(Write Amplification)은 실제 사용자 데이터 크기 대비 디스크에 실제 기록되는 양의 비율이다.
LSM Tree에서 Compaction이 반복되면 같은 데이터가 여러 번 다시 쓰여진다. Leveled Compaction에서는 쓰기 증폭이 10~30배에 달할 수 있다. 이는 SSD 수명에 영향을 주므로 프로덕션 환경에서 중요한 고려사항이다.
사용자가 1MB 쓰기 → 실제 디스크 기록 10~30MB (Compaction 포함)
실제 사용 사례
RocksDB (Facebook이 LevelDB를 포크해서 만듦)
- MySQL(MyRocks), TiKV, CockroachDB 등에서 스토리지 엔진으로 사용
- Leveled Compaction 기본 사용
Apache Cassandra
- 분산 NoSQL DB
- Size-Tiered Compaction을 기본으로 사용
- 쓰기 집약적 워크로드에 최적화
InfluxDB, Apache HBase
- 시계열 데이터, 로그 데이터처럼 쓰기가 폭발적으로 많은 환경
정리
LSM Tree의 핵심 아이디어는 랜덤 쓰기를 순차 쓰기로 변환하는 것이다. MemTable에서 받은 쓰기를 SSTable로 순차 플러시하고, Compaction으로 주기적으로 정리한다. 쓰기 성능이 중요하고 읽기보다 쓰기가 훨씬 많은 워크로드에서 B+Tree 대비 압도적으로 유리하다. 다만 읽기 증폭과 쓰기 증폭을 Compaction 전략과 Bloom Filter로 완화하는 것이 실제 운용의 핵심이다.