Split View: LSM-Tree 완벽 가이드 — RocksDB, LevelDB, Compaction, Bloom Filter, Write Amplification 모든 것 (2025)

LSM-Tree 완벽 가이드 — RocksDB, LevelDB, Compaction, Bloom Filter, Write Amplification 모든 것 (2025)

들어가며 — 왜 또 다른 저장 엔진인가

앞 글에서 PostgreSQL의 내부를 파헤치면서 B-tree의 우아함을 봤다. 수십 년 동안 DB를 지배한 자료구조다. 그런데 2010년대 들어 또 다른 계열이 조용히 세상을 장악하기 시작했다. Cassandra, HBase, LevelDB, RocksDB, ScyllaDB, InfluxDB, TiKV, CockroachDB, FoundationDB, ClickHouse의 MergeTree. 전부 LSM-Tree (Log-Structured Merge Tree) 또는 그 변종 위에서 돌아간다.

왜 LSM인가? B-tree가 완벽했다면 이 질문은 없었을 것이다. B-tree의 약점은 명확하다 — 랜덤 쓰기. 매 업데이트가 페이지 하나를 찾고, 수정하고, WAL을 쓰고, 결국 디스크의 임의 위치에 fsync한다. HDD 시대에는 치명적이었고, SSD 시대에도 write amplification과 wear leveling 문제가 남는다.

LSM의 답: 디스크에는 순차적으로만 쓴다. 기존 데이터는 건드리지 않는다. 업데이트는 새 레코드 추가로 표현한다. 삭제도 tombstone 추가로 표현한다. 시간이 지나면 백그라운드에서 조용히 병합(compaction)한다.

이 간단한 아이디어가 쓰기 처리량을 10–100배 끌어올리고, 현대 NoSQL의 기반이 됐다. 이 글은 LSM의 모든 것을 1,500줄에 걸쳐 다룬다. 1996년 O'Neil의 원래 논문부터 RocksDB의 최신 compaction 전략, Bloom filter, RUM 추측, 실제 시스템(Cassandra, ScyllaDB, TiKV)에서의 응용, 그리고 B-tree와의 공존 전략까지.

이 글은 PostgreSQL 내부 구조 글의 자연스러운 대척점이다. 같은 "키-값 저장"이라는 문제를 두 세계가 얼마나 다르게 푸는지 느껴보자.

1. LSM의 기원 — 1996년의 천재적 통찰

1.1 O'Neil 논문

Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil이 1996년 "The Log-Structured Merge-Tree (LSM-Tree)" 논문에서 제안했다. 당시 문제 의식:

• B-tree는 매 업데이트가 랜덤 I/O.
• HDD의 시크 타임은 10ms 수준 → 초당 100번이 한계.
• TPC-B 같은 벤치마크가 거대해지면서 B-tree로는 따라갈 수 없음.

논문의 핵심 아이디어: 쓰기를 메모리에 모았다가 큰 덩어리로 순차 디스크에 뿌린다. 디스크의 순차 I/O는 랜덤 I/O보다 100–1000배 빠르다. 메모리에 모으는 동안 이미 디스크에 있는 데이터와 병합해야 하는데, 이것도 순차 merge로 풀 수 있다.

당시엔 학술적 호기심이었다. 실제 응용은 2003년 Google의 Bigtable 논문에서 등장. 그 이후 LevelDB (Google의 오픈소스), RocksDB (Facebook의 LevelDB 포크), Cassandra, HBase로 이어졌다.

1.2 근본 공식: Read-Update-Memory 추측 (RUM)

LSM을 이해하려면 먼저 RUM conjecture를 알아야 한다. Athanassoulis et al. (2016) 논문.

모든 저장 엔진은 세 가지를 최적화하려 한다:

• R (Read amplification): 한 논리적 읽기가 실제 몇 번의 디스크 읽기를 유발하는가.
• U (Update amplification = Write amplification): 한 논리적 쓰기가 실제 몇 바이트를 디스크에 쓰는가.
• M (Memory amplification = Space amplification): 논리적 데이터 크기 대비 디스크 사용량.

RUM conjecture: 이 셋을 동시에 최소화할 수 없다. 하나를 줄이면 다른 하나가 늘어난다.

• B-tree: R 우수 (log N), U 나쁨 (랜덤 I/O), M 보통 (fill factor 70%).
• LSM: R 나쁨 (여러 레벨 조회), U 좋음 (순차 쓰기), M 상황에 따라.
• Hash table: R 최고 (O(1)), U 나쁨 (rehashing), M 나쁨.

엔진의 설계는 이 trade-off 중 어디에 앉을지 선택하는 일이다.

2. LSM의 구조 — 3층 구조의 단순함

2.1 기본 구성

+----------+
| Memtable |  <- in-memory, sorted (skiplist)
+----------+
     |
     | flush
     v
+------------+------------+------------+
| SSTable L0 | SSTable L0 | SSTable L0 |  <- 디스크, 여러 파일
+------------+------------+------------+
     |
     | compaction
     v
+----------+----------+----------+
| SST L1   | SST L1   | SST L1   |
+----------+----------+----------+
     |
     v
+-----+-----+-----+
| L2  | L2  | L2  | ...
+-----+-----+-----+

• Memtable: 메모리 내 정렬 자료구조. 보통 skiplist (RocksDB, LevelDB) 또는 B+tree.
• WAL (Write-Ahead Log): 메모리 내 memtable의 유실을 막기 위한 디스크 로그.
• SSTable (Sorted String Table): 불변(immutable) 정렬 파일. 한 번 쓰면 수정되지 않음.
• Compaction: 낮은 레벨의 SSTable을 모아 높은 레벨로 병합.

2.2 쓰기 경로 (Write Path)

PUT(key, value)
  1. WAL에 (key, value) append + fsync (옵션)
  2. Memtable에 insert
  3. Memtable이 임계치 넘으면:
       - 새 Memtable 할당 (쓰기 계속 가능)
       - 기존 Memtable을 immutable로 마킹 (= memtable flush 대상)
       - 백그라운드 thread가 disk로 flush → 새 L0 SSTable 생성
       - WAL 중 이 memtable에 해당하는 부분 폐기

핵심: 쓰기는 메모리에만 간다. 디스크 쓰기는 WAL append (순차) + 나중의 SSTable flush (순차) — 모두 순차 I/O. 그래서 빠르다.

2.3 WAL — 익숙한 이름, 같은 역할

Postgres의 WAL과 개념은 동일하다. 크래시 시 memtable을 재구성하기 위해 쓴다. 차이:

• LSM의 WAL은 보통 memtable flush 후 즉시 폐기됨 (Postgres는 checkpoint까지 유지).
• SSTable 자체가 "과거 상태"를 보존하므로 WAL은 memtable만 보호.

fsync 정책은 tunable:

• sync=true: 매 커밋마다 fsync. Postgres와 같은 durability.
• sync=false: buffered write. 빠르지만 OS 크래시 시 유실 가능.
• group commit: 여러 커밋을 묶어 한 번 fsync.

RocksDB의 WriteOptions.sync가 이 값.

2.4 SSTable — 불변의 미덕

SSTable 파일 하나의 구조 (LevelDB/RocksDB 형식):

+-----------------+
| Data Block 1    |  key-value pairs (sorted)
+-----------------+
| Data Block 2    |
+-----------------+
| ...             |
+-----------------+
| Meta Block      |  Bloom filter, stats
+-----------------+
| Meta Index      |
+-----------------+
| Data Index      |  각 Data Block의 첫 key
+-----------------+
| Footer          |  fixed size, meta index 위치 등
+-----------------+

• Data Block: 4KB 정도. 블록 내에서 key는 prefix compression (restart interval).
• Index: 각 블록의 첫 key만 저장 → 이진 탐색으로 블록 찾기.
• Bloom filter: 블록별 또는 파일 전체. "이 key가 있나?" 를 빠르게 no로 답함.

SSTable이 불변이라는 점이 결정적이다. 읽는 동안 아무도 쓰지 않는다 → lock 없이 안전한 읽기. 백업도 단순 — 파일 복사만 하면 됨. 캐싱도 효율적 — 한번 읽은 블록은 불변.

2.5 Memtable — 왜 Skiplist인가

RocksDB의 기본 memtable은 skiplist. 왜 B+tree나 red-black tree가 아닌가?

1. Lock-free 동시성: skiplist는 CAS로 lock-free 삽입이 쉬움. 고동시성에 유리.
2. 단순한 구현: B-tree의 rebalancing보다 코드가 짧고 버그가 적음.
3. 범위 스캔 친화적: leaf level이 이미 linked list.

단점도 있다. 랜덤 접근 시 캐시 효율이 B+tree보다 낮다. 그래서 RocksDB는 여러 memtable 구현을 제공한다:

• skip_list: 기본.
• hash_skip_list: point lookup이 압도적으로 많으면.
• vector: prefix scan 위주면.

3. 읽기 경로 (Read Path) — LSM의 아킬레스건

3.1 여러 곳을 뒤져야 한다

GET(key)
  1. Active memtable 검사
  2. Immutable memtables 검사 (flush 중인 것들)
  3. L0 SSTables 검사 — 모두! (overlapping key range)
  4. L1, L2, ... 검사 — 각 레벨당 하나의 SSTable만 (non-overlapping)

최악의 경우 L0가 5개, L1부터 L6까지 레벨이 6개면 검사할 곳이 12곳. 각 곳은 메모리 아니면 디스크 접근. B-tree가 O(log N) 페이지만 읽는 것과 비교하면 끔찍하다.

3.2 Bloom Filter — 없는 것을 빠르게 판별

Bloom filter는 확률적 자료구조로 "없음을 확실히, 있음을 확률적으로" 판단한다.

- k개의 해시 함수
- m 비트 배열
- 삽입: k개 해시값 위치에 1
- 질의: k개 위치 모두 1이면 "있음 (확률적)", 아니면 "없음 (확실)"

False positive 확률은 P = (1 - e^(-kn/m))^k. 적절히 설정하면 1–2%. SSTable마다 1KB 정도의 bloom filter로 대부분의 "없음"을 즉시 판별.

RocksDB 설정:

# 보통 10 bits per key → FPR ~1%
bloom_bits = 10

10억 key 테이블에 12.5GB. 메모리 비용이지만 아낄 가치가 있다.

3.3 Block Cache

자주 읽히는 블록은 메모리에 캐시. RocksDB의 block_cache (기본 8MB, 프로덕션에서는 수 GB).

block_cache_size = 16GB
cache_index_and_filter_blocks = true  # 인덱스도 캐시
pin_l0_filter_and_index_blocks_in_cache = true  # L0는 항상 핫

OS 페이지 캐시와 별도로 관리. 블록이 압축되어 있어도 캐시에는 압축 해제 후 저장.

3.4 Index와 Partition Index

인덱스 자체가 커지면 문제다. 100GB DB에 인덱스가 1GB면 메모리에 다 못 올린다.

해결: partitioned index (RocksDB). 인덱스를 다시 인덱싱. 2단 인덱스 구조:

• Top-level index: "어느 index block을 볼지"
• Index block: 실제 key → data block offset

수GB 인덱스를 수MB의 top-level만 메모리에 유지.

3.5 Point Lookup vs Range Scan

Bloom filter는 point lookup에만 쓸모 있다. range scan(WHERE id BETWEEN 100 AND 1000)은 bloom filter가 도움 안 됨 — 범위 내 모든 key를 다 봐야 함.

그래서 LSM은 range-heavy 워크로드에서 B-tree 대비 약하다. TSDB (InfluxDB) 같은 시계열은 "최근 데이터"에 집중된 query 패턴으로 이 약점을 부분 상쇄.

4. Compaction — LSM의 심장이자 악몽

4.1 왜 Compaction이 필요한가

Compaction 없이는:

1. Read amplification 폭발: L0가 무한 성장 → 모든 읽기가 엄청 느려짐.
2. Space amplification: 삭제된 key나 오래된 버전이 영원히 남음.
3. 파일 수 폭발: file descriptor 고갈.

Compaction은 여러 SSTable을 모아 새 SSTable 하나 또는 여러 개로 병합한다. 그 과정에서:

• 중복된 key는 최신 것만 남김.
• tombstone이 시간 경과 후 실제 삭제.
• 같은 레벨 내 overlapping을 해소.

4.2 Size-Tiered Compaction (STCS) — Cassandra의 기본

같은 크기 등급의 SSTable이 N개 (기본 4) 쌓이면 하나로 합침.

처음:  [10MB] [10MB] [10MB] [10MB]
합침:  [40MB]
나중:  [40MB] [40MB] [40MB] [40MB]
합침:  [160MB]
...

장점: Write amplification이 낮다. 각 key가 몇 번만 rewrite됨.

단점: Space amplification이 크다 — 최악의 경우 삭제된 데이터를 포함한 거대한 SSTable이 오래 남음. 일시적으로 디스크 사용량이 2배가 될 수 있다. (compaction 중에는 입력과 출력이 동시 존재.)

4.3 Leveled Compaction (LCS) — LevelDB/RocksDB의 기본

레벨별 크기 제한. 각 레벨은 전체적으로 key range가 겹치지 않음 (L0 제외).

L0: [a-k] [f-p] [l-z]   (overlapping 가능)
L1: 10MB 한도 — [a-c] [c-g] [g-m] ...   (non-overlapping)
L2: 100MB 한도
L3: 1GB 한도
L4: 10GB 한도

L_n이 한도 초과 → 그중 하나를 골라 L_(n+1)의 overlap되는 SSTable들과 병합.

장점: Space amplification이 작다 — 각 레벨의 삭제된 key는 다음 compaction에서 제거. 일반적으로 데이터의 1.1배 디스크 사용.

단점: Write amplification이 크다 — 같은 key가 레벨마다 rewrite. 최악 10–30배.

4.4 Universal Compaction (UCS) — RocksDB 전용

STCS와 비슷하지만 더 정교. 모든 SSTable을 L0에 두고, 크기 조건 만족 시 병합.

Write-heavy + read-light 워크로드(캐싱 레이어, 로그 수집)에 적합. Space amplification이 2–3배 가능.

4.5 FIFO Compaction

Time-series 전용. 오래된 SSTable을 그냥 삭제. compaction 없음.

로그/메트릭 같이 "오래되면 의미 없는" 데이터에 완벽. RocksDB의 TTL 기능과 결합.

4.6 Tombstone과 Compaction의 까다로운 춤

Tombstone: 삭제를 나타내는 특수 마커. 실제 삭제는 compaction 때 일어남.

문제: tombstone은 "자신보다 아래 레벨에 있는 key를 가리는" 역할을 하므로, 모든 하위 레벨의 해당 key가 없어질 때까지 tombstone도 남아야 한다. 그렇지 않으면 delete된 key가 "부활"한다.

Cassandra에서 유명한 zombie rows 문제: tombstone이 gc_grace_seconds 지나서 GC됐는데, 해당 key의 오래된 버전을 가진 노드가 뒤늦게 동기화되면 삭제된 데이터가 되살아남. 해결: gc_grace_seconds를 노드 다운 허용 시간 이상으로 설정 (기본 10일).

4.7 Subcompaction — 병렬 Compaction

큰 compaction을 여러 스레드로 병렬 처리. RocksDB의 max_subcompactions.

입력 SSTable들의 key range를 N등분 → 각 서브레인지를 독립된 스레드로 병합. compaction 완료 시간이 거의 선형으로 줄어든다.

단점: CPU 사용량 증가. 워크로드가 read-heavy면 compaction이 CPU를 뺏어가 쿼리가 느려짐.

4.8 Compaction Scheduling — 예술의 영역

실전에서는 compaction이 시스템 리소스를 가장 많이 쓴다. 잘못된 스케줄링은:

• compaction이 쓰기 속도를 못 따라잡음 → L0가 쌓임 → read가 느려짐 → 앱 스로틀링 → write stall.
• compaction이 너무 공격적 → I/O 경쟁 → 레이턴시 스파이크.

RocksDB의 tunables:

max_background_compactions = 4     # 동시 compaction 수
level0_file_num_compaction_trigger = 4
level0_slowdown_writes_trigger = 20  # 쓰기 슬로우다운
level0_stop_writes_trigger = 36      # 쓰기 완전 스탑
compaction_readahead_size = 2MB
rate_limiter_bytes_per_sec = 100MB  # I/O 한도

rate_limiter가 핵심. 읽기/쓰기 I/O를 compaction이 훔쳐가지 않도록 방지.

5. Write/Space/Read Amplification — 숫자로 보기

5.1 Write Amplification

LSM의 가장 악명 높은 지표. Leveled compaction의 write amp는 대략 WA = 1 + (L-1) * T. 여기서 L은 레벨 수, T는 레벨 간 크기 비율 (기본 10).

레벨 6개, 배율 10 → WA = 51. 즉 1바이트 쓰면 실제 디스크에는 51바이트가 쓰인다. SSD 수명에 치명적.

Size-tiered에서는 WA = L + 1 로 훨씬 작다 — 레벨 6이면 7배. 왜 Cassandra가 STCS를 기본으로 두는지 알 수 있다.

5.2 Space Amplification

Leveled:

• 정상 상태: 1.1배 정도.
• Compaction 중: 일시적으로 최대 2배.

Size-tiered:

• 최악: 2배 (compaction 직전).
• 평균: 1.5배 정도.

5.3 Read Amplification

Leveled:

• Best: bloom filter가 모두 negative → 파일 접근 없이 L_n까지 bloom만 본다.
• Average: 1–2개 파일 접근.
• Worst: 레벨 수만큼 + L0 파일 수만큼.

B-tree:

• O(log N) 페이지 접근. 상수가 더 작다.

5.4 RocksDB의 Tiered + Leveled 하이브리드

최근 추세: 낮은 레벨은 tiered (쓰기 속도), 높은 레벨은 leveled (공간 효율). HyperLevelDB 같은 시스템이 이 방향. RocksDB도 level_compaction_dynamic_level_bytes 옵션으로 비슷한 효과.

6. RocksDB 내부 — LSM의 현대적 정점

6.1 아키텍처

Facebook이 LevelDB를 포크해 만든 embedded KV store. "KV 저장 엔진"만 담당하며, 네트워크/분산은 위 레이어에 맡김. 그래서:

• MyRocks: MySQL storage engine으로 RocksDB.
• TiKV: CockroachDB-like 분산 KV, 각 샤드가 RocksDB.
• CockroachDB: Pebble (RocksDB의 Go 포팅)로 전환했지만 철학은 동일.
• Kafka Streams: state store로 RocksDB.

6.2 Column Family — 논리적 분리

하나의 RocksDB 인스턴스 안에 여러 column family. 각 CF는 독립된 LSM:

rocksdb::ColumnFamilyOptions cf_opts;
rocksdb::ColumnFamilyHandle* cf;
db->CreateColumnFamily(cf_opts, "metadata", &cf);
db->Put(WriteOptions(), cf, "key1", "value1");

서로 다른 CF는 서로 다른 compaction 전략, bloom filter, block size를 가질 수 있다. "테이블"에 대응되는 개념.

6.3 Write Batch — 원자성

WriteBatch batch;
batch.Put("key1", "value1");
batch.Put("key2", "value2");
batch.Delete("key3");
db->Write(WriteOptions(), &batch);

여러 작업이 하나의 WAL 레코드로 쓰여 원자적으로 적용. ACID의 A를 제공.

6.4 Snapshot — 일관된 읽기

const Snapshot* snap = db->GetSnapshot();
ReadOptions ro;
ro.snapshot = snap;
// 이 snapshot은 그 시점의 상태를 본다
db->Get(ro, "key1", &value);
db->ReleaseSnapshot(snap);

LSM은 SSTable이 불변이므로 snapshot 구현이 쉽다. "그 시점의 sequence number보다 작은 것만 보라." Compaction은 살아있는 snapshot이 있으면 해당 sequence 이하 데이터를 지우지 못한다.

6.5 Transaction API (OptimisticTransactionDB / PessimisticTransactionDB)

RocksDB는 기본적으로 KV지만 transaction 계층도 제공:

• OptimisticTransaction: write-time에 충돌 검사. 충돌률 낮을 때 빠름.
• PessimisticTransaction: 2PL. 충돌률 높을 때 유리.

MyRocks, TiKV 같은 시스템은 자체 TX 레이어를 올린다.

6.6 Merge Operator — Increment 최적화

INCR key 같은 연산은 보통 Get → 계산 → Put (3 round). Merge operator로 한 번에:

db->Merge(WriteOptions(), "counter", "1");
// 다음 Get 또는 compaction 시 머지

Redis의 INCR과 유사. Cassandra의 counter column이 내부적으로 이 아이디어를 쓴다.

6.7 TTL (Time-To-Live)

SSTable에 expiration 정보를 메타로 추가. 만료된 key는 read 시 필터, compaction 시 실제 제거.

TSDB, 세션 저장소 등에서 자동 정리.

7. Cassandra — 분산 LSM의 원형

7.1 Dynamo + Bigtable = Cassandra

2008년 Facebook에서 시작. Amazon Dynamo의 partitioning/replication + Google Bigtable의 데이터 모델 (column family, SSTable). 지금은 Apache 재단.

• Partitioning: consistent hashing으로 key를 노드에 분산.
• Replication: 각 key를 N개 노드에 복제 (RF = replication factor).
• Storage: 노드마다 로컬 LSM.

7.2 Write Path

1. 코디네이터 노드가 받음.
2. RF 노드에 병렬 send.
3. 각 노드가 로컬 commit log + memtable에 씀.
4. 노드 N개 중 W개 ack → 코디네이터가 클라이언트에 ack.

W가 consistency level. ONE, QUORUM, ALL. QUORUM은 (RF+1)/2. 대부분 QUORUM + read도 QUORUM으로 strong consistency 달성.

7.3 Read Path (Cassandra-specific)

Cassandra는 read repair를 내장:

1. R개 replica에서 읽기.
2. 다르면 최신 데이터로 전부 업데이트.
3. 클라이언트에는 최신 반환.

덕분에 eventual consistency 시스템이지만 점진적으로 수렴.

7.4 Bloom Filter + Row Cache + Key Cache

레벨별 캐시가 있다:

• Row cache: 실제 row 데이터.
• Key cache: key → SSTable 위치.
• Bloom filter: 노드의 각 SSTable에 존재.

튜닝:

• read-heavy면 row cache 키워야 하지만 메모리 많이 먹음.
• key cache는 기본 활성화, 보통 건드릴 필요 없음.
• bloom filter FP rate는 bloom_filter_fp_chance로 조정. 기본 STCS 0.01, LCS 0.1.

7.5 Compaction 선택

Cassandra는 여러 compaction strategy 지원:

• SizeTieredCompactionStrategy (STCS): 기본. 쓰기 중심.
• LeveledCompactionStrategy (LCS): 읽기 중심. SSD 필수.
• TimeWindowCompactionStrategy (TWCS): 시계열. 윈도우별 compaction.
• DateTieredCompactionStrategy: TWCS의 조상. 지금은 deprecated.

Time-series 데이터면 TWCS가 사실상 필수. 윈도우별 SSTable이라 오래된 윈도우는 통째 삭제 가능.

7.6 Cassandra의 슬픈 점

• JVM: GC pause가 레이턴시에 직결.
• Thread-per-request: 수천 스레드 context switch.
• 복잡한 compaction: 운영자의 지속적 튜닝 필요.
• read-before-write 없음: upsert만 빠름. transaction 없음 (LWT가 있지만 비쌈).

이 슬픔이 ScyllaDB를 낳았다.

8. ScyllaDB — Cassandra를 C++로 다시 쓰기

8.1 Shard-per-core Architecture

ScyllaDB는 Cassandra 프로토콜 호환, C++로 재구현. 가장 큰 차이는 shard-per-core:

• 노드의 각 CPU 코어가 독립된 샤드.
• 샤드 간 통신은 메시지 패싱.
• 스레드 context switch 거의 없음.
• Lock도 거의 없음 (샤드 내부에서만).

이 아키텍처는 Seastar 프레임워크 위에 구축. DPDK, io_uring, NUMA awareness까지 활용한 극한 최적화.

8.2 성능

같은 하드웨어에서 Cassandra 대비 10배 처리량이 흔하다. 특히 tail latency (p99)가 극적으로 낮음 — GC pause가 없으므로.

8.3 LSM의 재구현

Cassandra의 LSM 로직을 그대로 이식하되:

• C++ allocator 최적화.
• 샤드별 독립 LSM.
• 비동기 I/O (io_uring).

SSTable 파일 포맷은 Cassandra와 호환 — 마이그레이션이 쉬움.

9. TiKV와 CockroachDB — LSM 위의 분산 트랜잭션

9.1 TiKV

CNCF 졸업 프로젝트. Rust로 작성. TiDB의 스토리지 레이어.

아키텍처:

• 데이터를 Region (기본 96MB)으로 샤딩.
• 각 Region은 Raft 그룹으로 복제 (3 copies).
• 각 노드의 각 Region 데이터는 RocksDB에 저장.

트랜잭션은 Percolator 알고리즘 (Google 논문) 기반. 2-phase commit + optimistic concurrency.

9.2 CockroachDB

Go로 작성. Spanner 스타일 multi-region DB. 초기에는 RocksDB를 썼으나 2022년 Pebble로 전환.

Pebble은 Go로 작성된 RocksDB 호환 엔진. 같은 LSM 구조지만:

• CGo 호출 오버헤드 없음.
• Go 런타임과의 더 좋은 통합 (scheduler, GC).
• CockroachDB-specific 최적화.

9.3 왜 LSM인가 (분산 DB 관점)

분산 DB는 write-heavy인 경우가 많다. 여러 노드의 Raft 로그를 적용, 메타데이터 업데이트, 컴팩션 등. LSM의 순차 쓰기 특성이 이와 잘 맞는다.

또한 snapshot 생성이 LSM에서 쉽다. Region 이동, replica 추가 시 저렴한 snapshot 복사.

10. B-tree와 LSM의 철학 비교

10.1 한 표로

10.2 각자의 스위트 스팟

• B-tree: 읽기/쓰기 균형, 복잡한 쿼리, ACID 트랜잭션, OLTP.
• LSM: 쓰기 폭주, 시계열, 로그 저장, KV, 분산 shard.

Postgres + RocksDB를 같은 시스템에서 쓰기도 한다. 최근 추세인 hybrid storage: hot 데이터는 B-tree, cold 데이터는 LSM.

10.3 현대의 수렴

재미있게도 두 세계는 서로를 닮아가고 있다:

• B-tree 진영: "copy-on-write B-tree" (LMDB, WiredTiger) — 더 이상 in-place 아님.
• LSM 진영: "hybrid compaction" — 상위 레벨만 tiered, 하위는 leveled.

결국 "순차 I/O 친화적이되 읽기 효율도 챙기기" 가 공통 목표.

11. 운영의 실제

11.1 RocksDB 튜닝 체크리스트

write_buffer_size = 256MB         # memtable 크기
max_write_buffer_number = 4       # memtable 개수
min_write_buffer_number_to_merge = 2
target_file_size_base = 128MB     # L1 SSTable 크기
max_bytes_for_level_base = 1GB    # L1 총 크기
max_bytes_for_level_multiplier = 10
compression_per_level = [none, none, zstd, zstd, zstd, zstd, zstd]
bloom_filter_bits_per_key = 10
cache_index_and_filter_blocks = true
block_cache = 16GB
rate_limiter = 100MB/s

compression_per_level이 재미있다. L0/L1은 압축 안 함 (flush/compaction 속도). L2+는 zstd (저장 효율).

11.2 모니터링 지표

rocksdb.compaction.write.bytes       # compaction write amp
rocksdb.estimate.num.keys
rocksdb.block.cache.hit
rocksdb.block.cache.miss
rocksdb.bloom.filter.useful          # bloom filter가 걸러낸 횟수
rocksdb.write.stall                  # 쓰기 스톨 발생
rocksdb.pending.compaction.bytes     # 밀린 compaction

pending.compaction.bytes가 shared_buffers만큼 쌓이면 경고. 두 배 넘으면 곧 write stall.

11.3 운영 사고 패턴

• Compaction이 따라잡지 못함: 쓰기 폭주 + compaction 느림 → L0 쌓임 → write stall. 해법: max_background_compactions 증가, 쓰기 throttle.
• Bloom filter 없는 range scan 폭주: p99 폭등. 해법: 쿼리 패턴 재검토, prefix bloom 고려.
• Snapshot 유지 → compaction 막힘: long-running iterator가 snapshot 유지하면 compaction이 오래된 데이터를 못 지움. "LSM 버전의 idle in transaction."

11.4 백업 전략

SSTable은 불변 → hard link로 즉시 백업 가능:

# RocksDB backup engine은 이 원리를 자동화
BackupEngine::CreateNewBackup(db)

새 SSTable이 만들어지면 백업 엔진에 link 추가. 오래된 backup이 삭제되면 link 해제. 아주 낮은 오버헤드.

11.5 재해 복구

LSM은 WAL + SSTable만 있으면 재구성 가능.

pg_basebackup 같은 개념:
1. Checkpoint 강제
2. WAL + SSTable 디렉토리 copy
3. 복구 노드에서 로드 + WAL replay

Cassandra는 nodetool snapshot이 이 역할.

12. 고급 주제

12.1 Wisckey — Key-Value 분리

2016년 논문. LSM의 문제: compaction이 value까지 rewrite. 큰 value(1KB+)는 write amp의 주범.

해결: key만 LSM에 두고, value는 별도 append-only log에. LSM의 entry는 (key, value_pointer).

장점:

• Compaction이 작은 key-pointer 쌍만 rewrite → write amp 대폭 감소.
• Read는 추가 I/O 한 번 — pointer follow.

RocksDB의 BlobDB가 이 원리. Pebble도 채택. Badger DB는 처음부터 Wisckey 기반.

12.2 Monkey — Bloom Filter 최적화

2017년 논문. 모든 레벨에 같은 FPR의 bloom filter를 쓰는 건 비효율. 상위 레벨(작고 자주 읽힘)에는 촘촘히, 하위 레벨(크고 덜 읽힘)에는 성기게.

Monkey는 레벨별 최적 FPR 할당을 수학적으로 도출. 같은 메모리로 read 처리량 2배.

12.3 REMIX / Dostoevsky

Compaction 전략을 수학적으로 최적화. Leveled와 tiered의 hybrid. RocksDB의 최근 버전이 이 방향을 채택.

12.4 Learned Index

Kraska et al. 2018. 인덱스를 ML 모델로 대체. key → position을 학습.

현실적 응용은 제한적이지만, **성공적 데이터(정렬된, 예측 가능한 분포)**에서는 B-tree/Bloom filter 대비 메모리 절감 가능.

13. 어느 엔진을 언제 쓸까

13.1 결정 트리

1. ACID가 필요한가? YES → Postgres/MySQL (B-tree).
2. 시계열/로그인가? YES → InfluxDB/ClickHouse/TimescaleDB (LSM-like).
3. 분산 KV 또는 wide-column? YES → Cassandra/ScyllaDB/DynamoDB (LSM).
4. 대규모 분석? YES → ClickHouse (MergeTree는 LSM의 친척).
5. 임베디드 KV? YES → RocksDB/LevelDB (LSM).
6. 기타: Postgres부터 시작해도 대부분 괜찮음.

13.2 신흥 대안들

• FoundationDB: ACID 분산 KV. Apple이 오픈소스화.
• ScyllaDB: Cassandra 대체, 10배 성능.
• TiKV/TiDB: HTAP, MySQL 호환.
• CockroachDB: Spanner-like 분산 Postgres.
• Neon / PlanetScale / Crunchy: Postgres/MySQL의 클라우드 네이티브 재해석.

모두 내부에 LSM 또는 B-tree (또는 변형)를 쓴다. 근본 원리는 30년 전과 같다.

맺음 — 순차 I/O의 예찬

LSM-Tree의 모든 설계 선택은 순차 I/O는 랜덤 I/O보다 압도적으로 빠르다는 한 문장에서 출발한다. 쓰기를 메모리에 모으기, 디스크에 순차적으로 flush하기, 백그라운드에서 merge하기. 이 단순한 아이디어 하나가 NoSQL 혁명의 기반이 됐다.

하지만 LSM은 공짜가 아니다. Read amp, write amp, compaction 오버헤드, 복잡한 튜닝. 그래서 B-tree가 죽지 않았다. Postgres는 여전히 건재하고, MySQL/InnoDB도 건재하다.

정답은 워크로드를 이해하는 것이다. 쓰기 폭주 시스템이라면 LSM을 생각해 보자. 복잡한 쿼리와 트랜잭션이 많다면 B-tree가 여전히 최고다. 둘 다 필요하면 hybrid 아키텍처 — hot은 Postgres, cold는 ClickHouse, state store는 RocksDB 같은 조합.

운영자로서 세 가지 본능을 정리한다:

1. Write amplification을 측정하라. SSD 수명이 걸려있다.
2. Compaction의 속도를 감시하라. 쓰기 속도를 못 따라가면 재앙.
3. Bloom filter를 신뢰하되 검증하라. FPR이 튜닝의 첫 걸음.

다음 글은 ClickHouse의 MergeTree 내부 구조를 다룬다. LSM의 사촌이자 OLAP의 현재 챔피언. 컬럼 저장, sparse index, materialized view가 LSM 원리 위에 어떻게 쌓이는지 본다. 저장 엔진의 세계는 넓다.