LSM-Tree (Log-Structured Merge Tree)

LSM-Tree (Log-Structured Merge Tree)

쓰기 최적화된 자료구조로, 모든 쓰기를 순차적으로 메모리(MemTable)에 기록한 후 디스크의 정렬된 파일(SSTable)로 병합하여 높은 쓰기 처리량 제공

목적: 쓰기 성능 최적화, 순차 I/O 활용, 대용량 데이터 처리

특징: Write-Optimized: 쓰기 최적화, 순차 쓰기, 레벨 기반 병합, Compaction: SSTable 병합·정리, SSTable(Sorted String Table): 정렬된 불변 디스크 파일

구조

• •MemTable: 메모리 내 정렬된 구조(Red-Black Tree, Skip List)
• •WAL(Write-Ahead Log): 내구성 보장을 위한 로그
• •SSTable(Sorted String Table): 디스크의 불변 정렬 파일
• •레벨(L0, L1, ...): 계층적 SSTable 구조

동작

• •Write: WAL 기록 → MemTable 삽입 → 가득 차면 SSTable로 플러시
• •Read: MemTable → L0 → L1 → ... 순차 검색, Bloom Filter로 최적화
• •Compaction: SSTable 병합하여 중복 제거, 삭제 적용, 레벨 이동

Compaction 전략

• •Leveled: 각 레벨 크기 제한, 균일한 읽기 성능, RocksDB 기본
• •Size-Tiered: 비슷한 크기 SSTable 병합, 공간 효율, Cassandra

Bloom Filter: 각 SSTable에 적용, 불필요한 디스크 읽기 방지

장점: 높은 쓰기 처리량, 순차 I/O, SSD 친화적, 압축 효율

단점: 읽기 증폭(Read Amplification), 쓰기 증폭, 공간 증폭, Compaction 오버헤드

적용사례: LevelDB, RocksDB, Cassandra, HBase, MongoDB(WiredTiger)

비교: LSM-Tree(쓰기최적화) vs B+Tree(읽기최적화) vs 해시(점조회)

연관: RocksDB, Compaction, SSTable, Bloom Filter, NoSQL