LSM-Tree (Log-Structured Merge-Tree)

개요

LSM-Tree(Log-Structured Merge-Tree)는 디스크 기반 저장 장치에서 쓰기(write) 성능을 극대화하기 위해 설계된 트리 기반 자료구조입니다. RocksDB, LevelDB, Cassandra 등 다양한 NoSQL·NewSQL 시스템에서 채택되고 있으며, 로그 형태의 쓰기 버퍼와 다단계 정렬·병합(Merge) 구조를 활용하여 쓰기 집약형 워크로드에 특화된 성능을 제공합니다.

---

1. 개념 및 정의

항목	설명
정의	LSM-Tree는 메모리 상에 로그처럼 데이터를 기록한 후, 주기적으로 디스크에 정렬된 트리 형태로 병합하는 계층형 트리 아키텍처입니다.
목적	랜덤 쓰기를 순차 쓰기로 변환하여 디스크 I/O 병목을 해소함
필요성	기존 B-Tree 계열은 쓰기 성능 한계 및 디스크 IOPS 문제 발생

LSM-Tree는 **“쓰기 우선 구조 + 배치 병합 전략”**을 통해 디스크 효율을 극대화합니다.

---

2. 구조 및 구성 요소

구성 요소	설명	역할
MemTable	메모리 상의 쓰기 버퍼 (보통 Red-Black Tree 또는 Skip List)	최신 데이터 저장 및 읽기 우선 탐색
WAL(Write-Ahead Log)	MemTable과 병행하여 기록되는 영속성 로그	장애 복구 및 데이터 durability 확보
SSTable (Sorted String Table)	디스크에 저장된 정렬된 불변 파일	계층별 병합(Merge), Bloom Filter 포함
Compaction	여러 SSTable을 병합하여 상위 레벨로 승격	중복 제거, 공간 회수, 정렬 유지
Level 구조	L0~Lk까지 단계별 저장소 계층	LSM-tree의 핵심 계층 구조 설계

데이터 흐름은 MemTable → WAL → SSTable → Compaction 순으로 진행됩니다.

---

3. 주요 동작 원리

1. 쓰기 요청이 들어오면 MemTable에 삽입되고 동시에 WAL에 로그 기록
2. MemTable이 가득 차면 디스크에 flush되어 SSTable로 저장
3. 여러 SSTable이 특정 수 이상이 되면 compaction이 발생하여 상위 레벨로 병합
4. 읽기 요청은 MemTable → L0~Ln 레벨 순서로 탐색되며, Bloom Filter, Index로 가속화됨

LSM-Tree는 쓰기 성능을 위해 읽기 성능을 일부 희생하지만, 캐시·Filter로 보완합니다.

---

4. 성능 특성 비교

항목	LSM-Tree	B+-Tree
쓰기 속도	빠름 (순차 쓰기, batch 처리)	느림 (랜덤 I/O, 노드 스플릿 비용)
읽기 속도	느릴 수 있음 (다중 레벨 탐색)	빠름 (단일 인덱스 트리 탐색)
공간 효율성	좋음 (중복 제거, 압축)	중간
압축/정렬	필요 (Compaction)	불필요 (동시 정렬 유지)
장애 복구	WAL 기반 빠른 복구	WAL 기반 + Checkpoint 방식

LSM-Tree는 쓰기-많은 워크로드에 강한 대안입니다.

---

5. 활용 사례

시스템	설명	특징
RocksDB	Facebook 개발, LSM 기반 고성능 KV 저장소	커스텀 Compaction, TTL 지원
LevelDB	Google 개발, 경량 LSM-Tree	Write-heavy 앱에 적합
Apache Cassandra	분산형 LSM 기반 NoSQL	Time-series 데이터 처리 최적화
ClickHouse MergeTree	대용량 분석 컬럼 저장 엔진	병렬 Compaction 및 Merge 지원
Apache HBase	Hadoop 기반 LSM 구조	HDFS 연계 및 실시간 조회 가능

대부분의 NoSQL/분산 데이터베이스에서 LSM-Tree는 표준 저장 구조로 자리잡고 있습니다.

---

6. 장점과 한계

장점	설명
고속 쓰기 처리	배치 삽입, 비동기 flush 구조로 성능 우수
디스크 효율성	순차 쓰기 및 압축 구조로 저장 효율 향상
안정성	WAL 및 Snapshot으로 장애 복구 신속
유연한 튜닝	Compaction 전략, Cache 크기 조정 가능

한계	설명
읽기 성능	다단계 조회, Compaction 간 레이턴시 증가 가능
Compaction 비용	주기적 병합 작업의 I/O 부하 큼
Hot Key 문제	특정 키 집중 시 레벨 간 불균형 발생 가능

---

7. 결론

LSM-Tree는 쓰기 중심 워크로드가 많은 현대의 데이터 환경에서 필수적인 스토리지 엔진 아키텍처입니다. 효율적인 디스크 쓰기, 유연한 병합 전략, 다양한 최적화 기능을 제공하며, RocksDB, Cassandra, ClickHouse 등 주요 시스템에서 중심 기술로 채택되고 있습니다. 단, 읽기 응답 지연과 compaction 비용 등은 시스템 설계 시 충분히 고려되어야 하며, 이를 위한 튜닝과 캐시 전략이 병행되어야 합니다.