LSM-Tree는 어떻게 동작하고, B-Tree와 무엇을 맞바꾸는가

seonwoo_jung·2026년 5월 30일

1. 도입

InnoDB가 B+Tree를 쓴다는 걸 정리하다 보니, 자연스럽게 "그럼 쓰기가 많은 DB는 왜 다른 구조를 쓴다는 걸까?"라는 의문이 따라왔다. Cassandra, RocksDB, LevelDB, HBase 같은 이름들이 공통적으로 LSM-Tree(Log-Structured Merge-Tree)를 기반으로 한다고 말하는데, 정작 그 구조가 B+Tree와 무엇이 다른지, 왜 쓰기에 강하다고 하는지는 막연했다.

이 글에서는 LSM-Tree가 데이터를 어떻게 저장하고 읽는지를 단계별로 따라가 보고, B-Tree 계열과 비교했을 때 무엇을 얻고 무엇을 내주는지를 정리했다. 주된 출처는 Martin Kleppmann의 Designing Data-Intensive Applications(이하 DDIA) Ch.3 "Storage and Retrieval"이며, 일부 구현 세부는 LevelDB/RocksDB 문서에서 알려진 내용을 곁들였다.

결론을 한 줄로 먼저 적으면: LSM-Tree는 모든 쓰기를 메모리에 모았다가 디스크에 "순차적으로" 통째로 내려쓰고, 나중에 백그라운드에서 정리(compaction)한다. 그래서 쓰기에 강한 대신 읽기에서 손해를 본다.

2. 핵심 개념: 왜 "로그"이고 왜 "머지"인가

LSM-Tree를 이해하는 출발점은 "디스크에 무작위로 흩뿌리는 쓰기(random write)는 느리고, 순차적으로 이어 쓰는 쓰기(sequential write)는 빠르다"는 사실이다. DDIA Ch.3에서도 가장 단순한 데이터베이스를 "파일 끝에 계속 append하는 로그"로 출발시킨다. append만 한다면 디스크 헤드가 한 방향으로만 움직이거나, SSD라도 순차 쓰기 패턴이 유리하다.

문제는 로그에 계속 덧붙이기만 하면 읽기가 O(n)이 된다는 점이다. 특정 키를 찾으려면 파일을 전부 훑어야 한다. 그래서 LSM-Tree는 두 가지 장치를 더한다.

정렬(Sorted): 디스크에 내려쓸 때 키 순서로 정렬해서 저장한다. 이렇게 정렬된 파일을 SSTable(Sorted String Table)이라 부른다.
머지(Merge): 시간이 지나면 SSTable이 여러 개 쌓이는데, 이들을 백그라운드에서 병합·정리한다(compaction).

즉 이름 그대로 "로그처럼 쓰고(Log-Structured), 머지로 정리하는(Merge) 트리"다.

3. 내부 동작: 쓰기·읽기 경로를 따라가기

쓰기 경로

DDIA에 정리된 흐름을 단계로 옮기면 다음과 같다.

쓰기가 들어오면 먼저 memtable이라는 메모리 안의 정렬된 자료구조에 넣는다. 보통 레드-블랙 트리나 스킵 리스트처럼 정렬을 유지하면서 삽입이 빠른 구조를 쓴다고 알려져 있다.
memtable이 일정 크기(예: 수 MB)를 넘으면, 그 시점의 내용을 키 순서로 정렬된 SSTable 파일로 디스크에 통째로 내려쓴다(flush). 이때 디스크 쓰기는 순차 쓰기다.
flush가 끝나면 새 memtable을 시작한다.

여기서 한 가지 헷갈렸던 지점이 있다. memtable은 메모리에 있으니, flush 전에 서버가 죽으면 데이터가 날아가는 것 아닌가? 그래서 LSM 구현들은 보통 memtable과 별개로 디스크의 write-ahead log(WAL)에 먼저 append해 둔다. 크래시가 나면 WAL을 재생(replay)해서 memtable을 복구한다. 이 WAL은 정렬되지 않은 순수 append 로그이므로, 해당 memtable이 SSTable로 안전하게 flush되면 버려도 된다.

   쓰기 요청
      │
      ├──► WAL(디스크, append-only)   ← 크래시 복구용
      │
      └──► memtable(메모리, 정렬 유지)
                │  (임계 크기 초과)
                ▼
           SSTable flush (디스크, 정렬된 파일)
                │  (시간이 지나 여러 개 누적)
                ▼
           compaction(백그라운드 병합·정리)

읽기 경로

읽기는 쓰기만큼 단순하지 않다. 하나의 키가 memtable에도, 여러 SSTable에도 (서로 다른 버전으로) 존재할 수 있기 때문이다. 그래서 최신 데이터부터 순서대로 찾는다.

먼저 memtable을 본다. 있으면 반환.
없으면 가장 최근에 만들어진 SSTable부터, 오래된 SSTable 쪽으로 차례대로 본다.

문제는 키가 아예 존재하지 않을 때다. 이 경우 모든 SSTable을 다 뒤지고 나서야 "없음"을 확정하게 되어 디스크 I/O가 크게 늘 수 있다. DDIA는 이를 완화하는 장치로 Bloom filter를 소개한다. Bloom filter는 "이 SSTable에 이 키가 확실히 없다"는 것을 적은 메모리로 빠르게 판정해 주는 확률적 자료구조다(없다고 하면 진짜 없고, 있다고 하면 있을 수도/없을 수도 — false positive는 가능하지만 false negative는 없다고 알려져 있다). 이걸로 존재하지 않는 키에 대한 헛디스크 읽기를 상당히 줄인다.

또한 각 SSTable에는 sparse index(드문드문 찍힌 키→파일 오프셋 인덱스)를 메모리에 둬서, 정렬된 파일 안에서 대략적인 위치로 점프한 뒤 그 구간만 스캔하도록 한다. 전체를 다 읽지 않아도 되는 것이다.

삭제는 어떻게 하나 — Tombstone

LSM은 기존 값을 제자리에서 덮어쓰지 않는다(append 기반이므로). 그래서 삭제도 "삭제됨"이라는 특수 마커, 즉 tombstone을 새로 기록하는 방식으로 처리한다. 읽을 때 가장 최신 레코드가 tombstone이면 "없는 키"로 취급한다. 실제 공간 회수는 compaction 때 이뤄진다.

Compaction — 두 가지 전략

SSTable이 계속 쌓이면 읽을 때 뒤져야 할 파일이 늘고, 같은 키의 오래된 버전·tombstone이 공간을 차지한다. 이를 정리하는 게 compaction이다. 여러 SSTable을 읽어 머지 정렬(merge sort)하면서, 같은 키는 최신 것만 남기고 tombstone으로 지워진 키는 제거한 새 SSTable을 만든다. 입력이 이미 정렬돼 있으므로 머지 정렬이 효율적이라는 점이 핵심이다.

compaction을 언제 어떻게 묶느냐에 따라 전략이 갈린다. 대표적으로 두 가지가 알려져 있다.

항목	Size-tiered	Leveled
묶는 기준	비슷한 크기의 SSTable들을 모아 병합	레벨별로 크기 한도를 두고 작은 SSTable을 아래 레벨로 병합
쓰기 증폭	상대적으로 낮은 편	상대적으로 높은 편
공간 증폭	상대적으로 높을 수 있음	상대적으로 낮은 편
채택 예	Cassandra, HBase의 기본 계열	LevelDB, RocksDB

(전략별 특성은 워크로드·구현에 따라 달라지므로 위 표는 일반적으로 알려진 경향에 대한 정리로 보는 게 안전하다.)

4. read/write 트레이드오프

LSM-Tree와 B-Tree(B+Tree)를 비교할 때 자주 등장하는 세 가지 "증폭(amplification)" 개념으로 정리하면 트레이드오프가 선명해진다.

Write amplification(쓰기 증폭): 애플리케이션이 1번 쓴 데이터가 디스크에는 몇 번 쓰이는가. LSM은 compaction이 같은 데이터를 여러 번 다시 쓰기 때문에 쓰기 증폭이 생긴다. 하지만 B-Tree도 페이지를 덮어쓰면서 (그리고 WAL까지 합쳐) 쓰기 증폭이 있다. DDIA는 LSM이 흔히 더 높은 쓰기 처리량을 낼 수 있다고 정리하는데, 이유로 (1) 경우에 따라 쓰기 증폭이 더 낮고, (2) 트리 페이지 여러 개를 무작위로 덮어쓰는 대신 정렬된 SSTable을 순차적으로 쓰기 때문이라고 설명한다.
Read amplification(읽기 증폭): 한 번의 조회가 실제로 몇 번의 디스크 접근을 유발하는가. LSM은 memtable + 여러 SSTable을 단계적으로 뒤져야 하므로 읽기 증폭 측면에서 불리하다. Bloom filter와 인덱스로 완화하지만, B+Tree가 보통 정해진 트리 높이만큼만 내려가면 되는 것과 대비된다.
Space amplification(공간 증폭): 같은 키의 옛 버전·tombstone이 compaction 전까지 디스크를 더 차지한다. 반대로 B-Tree는 키마다 한 군데에만 저장되는 경향이 있다.

여기에 더해, DDIA가 지적하는 LSM의 실무적 약점이 하나 더 있다. compaction이 백그라운드에서 디스크 대역폭을 잡아먹기 때문에, 쓰기가 몰리는 상황에서 compaction과 들어오는 쓰기가 같은 자원을 두고 경쟁할 수 있다는 점이다. 이때 일부 요청의 응답 지연(특히 상위 백분위 latency)이 튈 수 있다고 알려져 있다.

요약하면 대략 이런 그림이다.

관점	LSM-Tree	B+Tree
쓰기	순차 쓰기 위주, 처리량 높은 편	페이지 제자리 갱신, 무작위 쓰기 발생
읽기	여러 SSTable 탐색, 상대적으로 불리	정해진 높이만큼만 탐색, 예측 가능
디스크 패턴	순차 쓰기 + 백그라운드 compaction	random write 위주
지연 안정성	compaction 영향으로 튈 수 있음	상대적으로 균일한 편

5. 작은 예시: 같은 키를 여러 번 쓰면

키 user:42를 시간 순서대로 세 번 갱신했다고 하자. LSM에서 디스크에는 대략 이런 식으로 흔적이 남는다(개념을 보이기 위한 의사 표현이다).

# 오래된 SSTable
user:42 → {"name":"A"}          (seq=1)

# 그 다음 SSTable
user:42 → {"name":"B"}          (seq=2)

# 최신 SSTable (또는 아직 memtable)
user:42 → {"name":"C"}          (seq=3)  ← 읽기는 이걸 반환

읽기는 최신부터 보므로 {"name":"C"}를 돌려준다. 옛 버전 두 개는 여전히 디스크에 남아 공간을 차지하다가(공간 증폭), compaction이 돌면서 최신 것만 남기고 정리된다. 만약 중간에 삭제가 있었다면 그 자리에는 tombstone이 기록되고, 역시 compaction에서 실제로 제거된다.

이 한 장면 안에 LSM의 성격이 다 들어 있다. 쓰기는 그냥 "새로 덧붙이기"라 빠르고, 대신 읽기·공간 정리의 부담을 나중으로 미뤄 둔 구조라는 것.

6. 정리

LSM-Tree는 쓰기를 메모리(memtable)에 모았다가 정렬된 SSTable로 순차적으로 내려쓰고, 누적된 파일을 compaction으로 정리한다. 그 대가로 읽기는 여러 단계를 뒤져야 하고, compaction이 자원을 쓴다.

쓰기 경로: WAL + memtable → SSTable flush → compaction.
읽기 경로: memtable → 최신 SSTable → … 순으로 탐색, Bloom filter·sparse index로 완화.
트레이드오프는 write/read/space amplification 세 축으로 보면 정리된다. 쓰기 많은 워크로드에 LSM이, 읽기·범위 조회 중심에 B+Tree가 흔히 어울린다고 정리했다.

다음에 더 파고들 만한 주제:

RocksDB의 leveled compaction 세부와 튜닝 포인트(level 크기 배수, write stall)
Bloom filter의 false positive 비율과 메모리·비트 수의 관계

참고 자료

Martin Kleppmann, Designing Data-Intensive Applications, Ch.3 "Storage and Retrieval" — SSTable, memtable, LSM-Tree, compaction, Bloom filter, B-Tree와의 비교 및 write/read amplification 서술
LevelDB / RocksDB 공식 문서 — memtable·SSTable·leveled compaction 등 구현 측면에서 알려진 동작 (세부는 버전·구현에 따라 다를 수 있음)