RocksDB & LSM-Tree Deep Dive — Memtable, SST, Compaction, Bloom Filter, Write/Read Amplification 완전 정복 (2025)

TL;DR

• LSM-Tree (Log-Structured Merge Tree)는 랜덤 쓰기를 순차 쓰기로 변환하는 스토리지 구조. SSD에서 B-tree 대비 쓰기 처리량 10-100배.
• RocksDB는 Google LevelDB의 Facebook 포크. 프로덕션급 LSM 엔진, 수백 개의 튜닝 옵션, 임베디드 라이브러리 형태.
• Write Path: WAL → Memtable (메모리) → Flush → L0 SST → Compaction → L1 → L2 → ... Ln.
• Read Path: Memtable → L0 → L1 → ... 순회. 각 레벨에 Bloom Filter와 Block Cache로 불필요한 디스크 접근 회피.
• Compaction 전략:
  • Leveled (RocksDB 기본): 레벨마다 10배씩 증가, 읽기 amplification 최소화.
  • Tiered (Cassandra): 동일 크기 SST를 병합. 쓰기 amplification 최소화.
  • Universal (RocksDB 옵션): 전체 레벨 평준화. 중간 타협.
• 세 가지 Amplification: Write Amp (한 바이트를 몇 번 쓰는가), Read Amp (한 조회가 몇 개 파일을 보는가), Space Amp (실제 데이터보다 디스크를 몇 배 쓰는가). 이 셋은 상호 트레이드오프.
• Bloom Filter: 각 SST의 키 존재 여부를 확률적으로 판단. False negative 없음 → "이 SST에 키 없음"을 99.9% 확신 시 파일 skip.
• 실전 사용: TiKV (CockroachDB의 Rust 친척), MyRocks (MySQL), Kafka Streams state store, Flink state backend, Ceph BlueStore, Solana validator.

1. 왜 B-tree가 아닌 LSM인가

1.1 하드웨어의 진화

1970년대 DB가 만들어졌을 때 저장 매체는 HDD였다. HDD의 특성:

• 랜덤 I/O와 순차 I/O가 대략 비슷한 비용.
• 시킹 시간이 병목.
• Page 단위 접근.

B-tree는 이 환경에 완벽했다. 트리 구조로 랜덤 접근을 O(log n)에 압축하고, in-place 업데이트로 공간 효율이 좋았다.

2000년대에 SSD가 등장했다. 특성이 완전히 달랐다:

• 랜덤 쓰기가 여전히 느림(wear leveling, GC).
• 순차 쓰기는 매우 빠름.
• Random Read도 빠르지만 Write는 Read보다 느림.

B-tree는 SSD에서도 동작하지만 매 업데이트가 랜덤 I/O를 발생시킨다. 특히 높은 쓰기 처리량 환경에서 병목.

1.2 LSM-Tree의 접근

LSM(Log-Structured Merge) 트리는 1996년 Patrick O'Neil의 논문에서 제안됐다. 아이디어:

1. 모든 쓰기를 순차로. In-place 업데이트 없음, 매번 append.
2. 백그라운드에서 정리. 여러 버전이 누적되면 주기적으로 병합(compaction).
3. 메모리 버퍼: 최근 쓰기는 메모리에, 가득 차면 디스크로 플러시.

결과:

• 쓰기: 순차 append → 매우 빠름.
• 읽기: 여러 파일을 봐야 할 수도 → 더 느릴 수 있음.
• 공간: 과거 버전이 쌓이다 compaction으로 정리 → 주기적 spike.

1.3 두 진영

현재 DB 세계는 두 진영으로 나뉜다:

B-tree 진영:

• PostgreSQL, MySQL InnoDB, SQLite, Oracle, SQL Server.
• 읽기/쓰기 균형, OLTP 워크로드.
• 성숙한 기술.

LSM-tree 진영:

• RocksDB 기반: CockroachDB, TiKV, MyRocks, YugabyteDB.
• 자체 LSM: Cassandra, ScyllaDB, HBase, BigTable, LevelDB, DynamoDB.
• 쓰기 위주, 대용량, 분산.

"더 낫다"는 없다. 워크로드에 따라 선택. 2025년 트렌드는 LSM 쪽이 확장하고 있음 — 메시지 큐, 시계열 DB, 분산 KV 저장소가 모두 LSM 우선.

2. LSM-Tree의 기본 구조

2.1 핵심 컴포넌트

┌───────────────────────────────┐
│        Memtable (RAM)          │   ← 현재 쓰기 수용
├───────────────────────────────┤
│   Immutable Memtable (RAM)    │   ← flush 대기
├───────────────────────────────┤
│             L0                 │   ← 최근 flush된 SST 여러 개 (겹침 허용)
├───────────────────────────────┤
│             L1                 │   ← compaction 후, 각 SST는 키 범위 독점
├───────────────────────────────┤
│             L2                 │
├───────────────────────────────┤
│             ...                │
├───────────────────────────────┤
│             Ln                 │   ← 가장 큰, 가장 오래된 데이터
└───────────────────────────────┘

• Memtable: 메모리 자료구조 (보통 skiplist 또는 B+tree).
• WAL (Write-Ahead Log): 메모리 손실 대비.
• SST (Sorted String Table): 디스크 파일. 키-값이 정렬된 상태.
• Levels: L0부터 Ln까지. 아래로 갈수록 크고 오래됨.

2.2 쓰기 경로

client.put("key1", "val1");

1. WAL에 append     (동기, fsync 옵션)
2. Memtable에 insert (sorted 자료구조)
3. 클라이언트에 ack

[백그라운드]
4. Memtable이 꽉 차면 → Immutable Memtable로 전환
5. Immutable Memtable → L0 SST로 flush (순차 쓰기)
6. L0에 파일이 쌓이면 → L1으로 compaction
7. L1이 크기 한계 넘으면 → L2로 compaction
...

각 단계가 순차 쓰기다. SSD 친화적.

2.3 읽기 경로

client.get("key1");

1. Memtable 확인 (가장 최신)
2. Immutable Memtable 확인
3. L0 SST들 확인 (최신부터 — L0는 겹치므로 모두 확인 필요)
4. L1 SST 확인 (Bloom filter로 필터링, 이분 탐색)
5. L2 SST 확인
...
6. 찾을 때까지 또는 Ln까지

읽기가 "여러 파일을 뒤진다"는 점이 LSM의 단점. Bloom filter와 block cache가 이 비용을 줄이는 핵심.

2.4 삭제는 Tombstone

LSM은 in-place 삭제를 못한다 (immutable SST). 대신 tombstone(묘비석)을 쓴다:

put("key1", "val1");   // 원래 값
delete("key1");         // tombstone 추가: key1 → DELETED

Read 시:

• Memtable에서 tombstone 발견 → 반환 값 없음.
• 하위 레벨에서 실제 값 발견하더라도 tombstone이 우선.

Compaction 중에 tombstone과 하위 레벨의 원본을 만나면 둘 다 제거. 하지만 tombstone 자체가 공간을 먹는다. 대량 삭제 후에도 공간이 바로 돌아오지 않는 이유.

3. RocksDB의 역사

3.1 LevelDB에서 RocksDB로

LevelDB: 2011년 Google의 Jeff Dean & Sanjay Ghemawat가 개발. BigTable의 단순화된 오픈소스. 임베디드 KV 저장소.

• 단일 스레드 쓰기.
• 컬럼 패밀리 없음.
• 제한된 튜닝.
• 300KB 소스 코드.

작고 단순했지만 성능 한계가 명확했다.

3.2 Facebook의 포크

2012년 Facebook은 Cassandra를 MySQL로 대체하고 싶었다(운영 부담). 하지만 MySQL의 InnoDB는 쓰기 집약 워크로드에 불충분. LevelDB를 백엔드로 쓰고 싶었지만 기능이 부족.

Facebook이 RocksDB로 포크해 확장:

• 멀티 스레드 쓰기.
• 컬럼 패밀리.
• 수백 개의 튜닝 옵션.
• 강력한 compaction 전략.
• 백업/복제 기능.
• Rate limiter.
• 더 많은 통계.

2013년 오픈소스 공개. 현재 RocksDB는 LSM 스토리지 엔진의 사실상 표준이다.

3.3 사용 사례

RocksDB를 내장하는 시스템:

• MyRocks (MySQL): InnoDB 대체 스토리지 엔진. Facebook이 UDB에 사용.
• TiKV (CockroachDB 친척): 분산 KV, Rust로 RocksDB 바인딩.
• CockroachDB: Pebble(Go로 재구현) 전환 완료. 원래는 RocksDB.
• YugabyteDB: 기본 백엔드.
• Kafka Streams: State store.
• Apache Flink: State backend (checkpoint에 RocksDB).
• Ceph BlueStore: 메타데이터.
• Solana Validator: Ledger 저장.
• ArangoDB: 스토리지 엔진.

"임베디드 LSM이 필요하다 → RocksDB"는 거의 반사적 선택.

4. Memtable 구조

4.1 요구사항

Memtable은:

• 정렬 유지 (키 순서).
• 빠른 insert (쓰기 경로의 병목).
• 빠른 point lookup.
• Iteration 지원 (flush와 scan 용).
• Lock-free 또는 fine-grained locking이 이상적.

4.2 기본: Skiplist

RocksDB의 기본 Memtable은 skiplist다.

Level 3: 1 ───────────────── 9 ──────── 20
Level 2: 1 ────── 5 ──────── 9 ── 14 ── 20
Level 1: 1 ─ 3 ─ 5 ── 7 ──── 9 ── 14 ── 20
Level 0: 1 ─ 3 ─ 5 ── 7 ── 8 9 ── 14 ── 20

장점:

• O(log n) 삽입/검색 (확률적).
• Lock-free 구현 가능 (CAS 기반).
• 삽입이 B+tree보다 간단.
• Iteration이 자연스럽게 정렬 순서.

RocksDB의 Inlineskiplist는 메모리 오버헤드를 줄인 variant.

4.3 대안: HashSkipList, Vector, HashLinkList

RocksDB는 워크로드에 따라 다른 memtable 타입을 허용:

• HashSkipList: 해시 버킷 + skiplist. Point lookup이 많을 때.
• Vector: 정렬 안 된 벡터. 삽입만 할 때(후 정렬). Memtable이 작을 때.
• HashLinkList: 해시 + 작은 링크드 리스트. 매우 작은 memtable.

기본은 skiplist — 일반적 워크로드에 균형 잡힘.

4.4 Memtable 크기와 개수

write_buffer_size = 64MB        # memtable 하나의 최대 크기
max_write_buffer_number = 2     # memtable + immutable 개수

한 memtable이 64MB 되면 immutable로 전환되고 새 memtable 생성. 최대 2개가 동시 존재(기본). 두 개 다 차면 쓰기가 stall.

튜닝:

• 큰 memtable → 쓰기 흡수 버퍼 ↑, flush 빈도 ↓, 메모리 ↑.
• 많은 memtable → burst 흡수 ↑, 메모리 ↑.

5. SST (Sorted String Table)

5.1 파일 구조

SST 파일은 정렬된 키-값 블록의 시퀀스다:

┌─────────────────────────────────────┐
│ Data Block 0                        │   키-값 페어
├─────────────────────────────────────┤
│ Data Block 1                        │
├─────────────────────────────────────┤
│ ...                                 │
├─────────────────────────────────────┤
│ Data Block N                        │
├─────────────────────────────────────┤
│ Meta Block: Filter (Bloom)          │
├─────────────────────────────────────┤
│ Meta Block: Stats                   │
├─────────────────────────────────────┤
│ Meta Block: Properties              │
├─────────────────────────────────────┤
│ Meta Block: Compression Dictionary  │
├─────────────────────────────────────┤
│ Index Block (블록 위치 → 키 범위)     │
├─────────────────────────────────────┤
│ Footer (고정 크기, magic number)      │
└─────────────────────────────────────┘

• Data Block: 기본 4KB. 여러 키-값을 담음.
• Index Block: 각 Data Block의 "last key"와 오프셋. Binary search로 블록 찾기.
• Filter Block: Bloom filter. 키 존재 여부 확률적 판단.
• Footer: 파일 끝에 고정 크기. 다른 블록 위치 가리킴.

5.2 키 저장: Prefix Compression

Data Block 내에서 키는 prefix compression으로 저장된다.

user:1001 → (prefix_len=0, key="user:1001", value=...)
user:1002 → (prefix_len=8, key="2",        value=...)
user:1010 → (prefix_len=6, key="10",       value=...)

"이전 키와 공통 접두사는 생략"하는 방식. 키가 비슷할수록 절약. 특히 이 방식은 prefix scan에 유리 — 같은 prefix의 키들이 같은 블록에 모인다.

단점: 이 키를 보려면 블록 시작부터 순차 읽기 필요. 그래서 restart point를 주기적으로 삽입(예: 16개 키마다 전체 키 저장) 해서 binary search가 가능하게 만든다.

5.3 Block Cache

한 번 읽은 Data Block을 메모리에 캐시한다.

BlockBasedTableOptions {
    block_cache: Cache::new(8GB);
}

• LRU 기반 (또는 Clock).
• 여러 SST가 같은 Cache를 공유.
• 쓰기 시 invalidate 필요 없음(SST immutable).
• hot workload에서 히트율 > 90% 목표.

Block cache는 RocksDB 성능의 핵심. 작으면 디스크 I/O 폭발.

5.4 Compression

각 Data Block은 독립적으로 압축된다. 옵션:

• None: 빠른 쓰기/읽기.
• Snappy: 기본. 빠름, 압축률 중간.
• LZ4: Snappy보다 약간 빠름.
• ZSTD: 압축률 우수, CPU 더 씀.
• BZIP2, XZ: 아카이브용.

RocksDB는 레벨별로 다른 압축 사용 가능:

compression_per_level = [
    None,      # L0: 빠른 flush
    None,      # L1: 빠른 compaction
    Snappy,    # L2
    Snappy,    # L3
    ZSTD,      # L4: 큰 파일, 적은 접근
    ZSTD,      # L5
]

"상위 레벨은 빠르게, 하위 레벨은 압축률 우선" 전략.

6. Compaction 전략

Compaction은 LSM의 심장이다. "언제, 무엇을, 어떻게 병합할지"가 성능을 결정.

6.1 왜 Compaction인가

1. 공간 회수: tombstone과 오래된 버전 제거.
2. 읽기 속도: 파일 수 감소 → 적은 lookup.
3. 중복 제거: 같은 키의 여러 버전 병합.

6.2 Level Style (RocksDB 기본)

각 레벨이 이전 레벨의 N배 크기 (기본 10배).

L0:    최대 4 파일 × 64MB = 256MB
L1:    10 × L0 / 4 = 640MB  (하지만 max_bytes_for_level_base로 설정)
L2:    6.4GB
L3:    64GB
L4:    640GB
L5:    6.4TB

특성:

• L1 이상에서 같은 레벨의 SST들은 키 범위 겹치지 않음.
• Compaction: Ln의 한 파일 + 겹치는 Ln+1의 파일들 병합 → Ln+1 새 파일들.
• Read amplification 낮음: 한 키가 각 레벨에 최대 1개 (L0 제외).
• Write amplification 높음: 하위 레벨로 이동하면서 여러 번 재작성.

Leveled compaction 예시:
L1: [a-m] [n-z]
L2: [a-c] [d-f] [g-i] [j-l] [m-o] [p-r] [s-u] [v-z]

L1의 [a-m] 파일 병합:
- L2의 [a-c], [d-f], [g-i], [j-l] 과 겹침.
- 5개 파일을 읽어 병합 후 새 L2 파일 생성.
- 오래된 파일 삭제.

6.3 Size-Tiered (Cassandra 기본, RocksDB Universal)

"비슷한 크기의 SST들을 한 번에 병합."

L0: [파일 4개, 각 256MB] → 병합 → [1GB 파일 1개]
L0: [파일 4개, 각 1GB] → 병합 → [4GB 파일 1개]
...

특성:

• 쓰기 amplification 낮음 (적은 재작성).
• 읽기 amplification 높음 (여러 파일 모두 확인).
• Space amplification: 병합 중 일시적 2배.
• 간단한 구현.

Cassandra는 STCS(Size Tiered), LCS(Leveled), TWCS(Time Windowed) 세 가지를 지원. Cassandra가 LCS를 쓰는 시점부터 Cassandra = RocksDB 스타일.

6.4 RocksDB Universal Compaction

RocksDB의 universal은 tiered의 변형. 모든 SST가 L0에 존재하지만 파일들이 **"run"**이라는 그룹으로 묶인다.

Run 1: [largest] 4GB
Run 2: 2GB
Run 3: 1GB
Run 4: 512MB (newest)

각 run은 정렬된 SST들의 집합. Compaction은 여러 run을 하나로 병합.

트리거:

1. 파일 수가 너무 많음 (level0_file_num_compaction_trigger).
2. 전체 크기가 특정 배수 (size_ratio).
3. Space amplification 초과.

장점: 쓰기 amplification 최소, 단순. 단점: Universal은 공간 오버헤드가 크고 읽기 성능이 덜하다.

6.5 Compaction 비교표

"쓰기를 많이 하고 TTL로 정리"하는 시계열 데이터는 Time Windowed가 베스트. 일반 KV는 Leveled가 기본.

6.6 FIFO Compaction

가장 단순: 오래된 것 먼저 삭제. 로그 저장 같은 append-only 워크로드.

total_size > max_size → 가장 오래된 SST 삭제

Compaction이 사실상 없다 (삭제만). 매우 빠르지만 중복/update 없음.

7. Write/Read/Space Amplification

LSM 튜닝의 핵심 개념이다.

7.1 Write Amplification (W)

"한 바이트의 논리적 쓰기에 대해 실제 디스크에 쓴 바이트 수."

W = 실제_디스크_쓰기 / 논리_쓰기

LSM에서 W가 큰 이유: compaction이 데이터를 반복적으로 재작성.

• Leveled: W ≈ 10-30 (각 레벨로 이동 시 재작성).
• Tiered: W ≈ 2-5.
• B-tree: W ≈ 1.5-2 (페이지 분할 정도).

W가 크면:

• SSD 수명 단축 (TBW 소비).
• CPU 사용률 증가.
• 디스크 대역폭 소비.

7.2 Read Amplification (R)

"한 키 조회가 몇 번의 디스크 I/O를 발생시키는가."

R = 디스크_I/O_수 / 사용자_쿼리_수

LSM에서 R이 큰 이유: 여러 레벨/파일을 확인.

• Leveled: R ≈ 레벨 수 + 1 (Bloom 도움).
• Tiered: R ≈ 파일 수 (더 많음).
• B-tree: R ≈ 트리 높이 (일반적으로 3-5).

Bloom filter가 R을 크게 줄인다 — "이 파일에 키 없음"을 즉시 판단.

7.3 Space Amplification (S)

"논리적 데이터 크기 대비 디스크 공간."

S = 실제_디스크_공간 / 논리_데이터_크기

LSM에서 S가 큰 이유: 같은 키의 과거 버전, tombstone.

• Leveled: S ≈ 1.11 (최하 레벨이 전체의 90% 차지).
• Tiered: S ≈ 2 이상 (여러 버전 병존).
• B-tree: S ≈ 1.5 (page fill 비효율).

7.4 "RUM Conjecture"

Harvard의 Chatterjee와 Athanassoulis가 제안한 경험칙:

"Read, Update, Memory 세 지표 중 두 개를 최적화하면 나머지 하나는 희생된다."

• 읽기 + 쓰기 최적화 → 메모리 많이 필요 (B-tree with huge cache).
• 쓰기 + 메모리 최적화 → 읽기 비용 (Tiered LSM).
• 읽기 + 메모리 최적화 → 쓰기 비용 (B-tree without cache).

"완벽한 인덱스"는 없다. 워크로드에 따라 선택.

8. Bloom Filter — 읽기 가속의 핵심

8.1 원리

Bloom filter는 확률적 집합이다:

• False positive: "있다"고 했는데 실제로 없음 (가능).
• False negative: "없다"고 했는데 실제로 있음 (불가능!).

이 비대칭성이 LSM에서 완벽하다:

if bloom.may_contain(key):
    check_sst(key)   # 확실하지 않음, 실제 확인
else:
    skip_sst()       # 100% 없음, 건너뛰기

8.2 작동 원리

1. k개의 해시 함수.
2. m 비트 배열.
3. 키 삽입: k개의 해시 결과 위치에 1 표시.
4. 조회: k개의 해시 결과가 모두 1이면 "아마 있음", 하나라도 0이면 "확실히 없음".

m = 비트 배열 크기
n = 키 개수
k = 해시 함수 수
p = false positive 비율

최적 k = (m/n) × ln(2)
p ≈ (1 - e^(-kn/m))^k

실무 예:

• 키당 10비트, 7개 해시 함수 → p ≈ 0.008 (0.8%).
• 키당 16비트, 11개 해시 함수 → p ≈ 0.0004.

RocksDB 기본은 10비트/키.

8.3 RocksDB의 Bloom Filter

BlockBasedTableOptions {
    filter_policy: BloomFilterPolicy::new(10.0, false),
    // 10 = 키당 비트 수
    // false = block-based (true면 full filter)
}

Full filter: 전체 SST에 대한 하나의 bloom. 효율적 메모리. Block-based filter: 각 데이터 블록마다 별도 bloom. 구식.

8.4 Ribbon Filter (RocksDB 6.20+)

Bloom filter의 개선판. 같은 false positive 비율에 30% 적은 공간.

filter_policy: RibbonFilterPolicy::new(10.0, 0);

Ribbon filter는 XOR 기반 해시로 bloom보다 효율적이지만 구축 비용이 약간 크다(컴팩션 시에만).

8.5 Partitioned Bloom

큰 SST는 bloom filter도 크다. Partitioned bloom은 여러 작은 bloom으로 나누고 상위 인덱스로 접근:

• 필요한 부분만 block cache에 로드.
• 메모리 효율 ↑.
• 첫 조회 약간 느림 (인덱스 조회 1회 추가).

9. 구체적 쓰기 경로

db.put("user:1001", "Alice") 호출 시 일어나는 모든 단계:

9.1 Write Batch

WriteBatch batch;
batch.Put("user:1001", "Alice");
batch.Put("user:1002", "Bob");
db.Write(options, &batch);

배치는 원자적으로 적용된다. 단일 Put도 내부적으로 배치로 처리.

9.2 WAL 작성

WAL 레코드:
  [sequence_number] [count=2]
  [type=Put] [key=user:1001] [value=Alice]
  [type=Put] [key=user:1002] [value=Bob]

• log_buffer_size만큼 버퍼링.
• write_options.sync = true면 매 쓰기마다 fsync.
• sync = false면 OS buffer에만 (빠름, 위험).

fsync는 비싸다. 디스크마다 수 ms. 대량 쓰기 시 그룹 커밋으로 여러 쓰기를 한 번 fsync.

9.3 Memtable 삽입

각 키-값을 memtable(skiplist)에 삽입:

memtable->Add(sequence_number, ValueType::Put, key, value);

Sequence number는 RocksDB가 관리하는 전역 카운터. MVCC의 기반. 같은 키의 여러 버전은 sequence number로 구분.

9.4 Trigger: Memtable Full

Memtable이 write_buffer_size 도달 시:

1. 현재 memtable → immutable_memtable_list_에 추가.
2. 새 memtable 생성.
3. WAL 파일도 새로 생성 (옛 WAL은 flush 완료 후 삭제).
4. 백그라운드 flush 스레드 깨우기.

9.5 Flush → L0

Flush 스레드:

1. Immutable memtable을 iterate (정렬 순서).
2. Data block 단위로 SST 파일 생성.
3. Bloom filter, Index block 생성.
4. 파일 close, fsync.
5. Manifest 파일에 "L0에 새 SST 추가" 기록.
6. Immutable memtable 해제, WAL 삭제.

Flush는 순차 I/O만이다. 기존 파일을 건드리지 않음.

9.6 Compaction Trigger

L0에 파일이 쌓이면:

level0_file_num_compaction_trigger = 4  # L0 파일 4개 시 compaction 시작
level0_slowdown_writes_trigger = 20     # 20개 시 쓰기 감속
level0_stop_writes_trigger = 36         # 36개 시 쓰기 정지!

L0 → L1 compaction이 느리면 클라이언트가 throttling 당한다. 이것이 "write stall"의 가장 흔한 원인.

10. 구체적 읽기 경로

db.get("user:1001") 호출 시:

10.1 Snapshot (optional)

ReadOptions read_options;
read_options.snapshot = db.GetSnapshot();  // MVCC

Snapshot은 특정 sequence number를 고정. 이후 조회는 그 시점의 상태.

10.2 Mem Table 체크

if (mem->Get(key, &value)) return value;
if (imm->Get(key, &value)) return value;

Memtable에서 찾으면 즉시 반환 (가장 최근 값).

10.3 SST 버전 순회

for (level = 0; level < num_levels; level++) {
    for (each SST in level, sorted) {
        // Bloom filter 체크 먼저
        if (!bloom_may_contain(key)) continue;

        // Index block으로 블록 찾기
        auto block = index->FindBlock(key);

        // Block cache 확인
        if (block_cache.contains(block_handle)) {
            data_block = block_cache.get(block_handle);
        } else {
            data_block = read_from_disk(block_handle);
            block_cache.put(block_handle, data_block);
        }

        // Data block 내에서 key 검색
        if (data_block.contains(key)) return value;
    }
}

10.4 L0의 특수성

L0의 SST들은 키 범위가 겹친다 (정렬되지 않음). 따라서:

1. 모든 L0 파일을 최신부터 체크.
2. 각각에 Bloom filter로 pre-filter.
3. 히트 시 즉시 반환.

그래서 L0 파일 수가 많을수록 읽기가 느려진다.

10.5 Iterator

db.NewIterator()는 전체 데이터베이스를 정렬 순서로 스캔:

auto it = db.NewIterator(read_options);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
    std::cout << it->key() << ": " << it->value() << std::endl;
}

내부적으로 merging iterator를 씀:

• Memtable 이터레이터
• Immutable memtable 이터레이터
• 각 SST의 이터레이터
• 이들을 priority queue로 병합 → 정렬 순서 유지, 중복 제거.

Range scan은 LSM의 강점: 이미 정렬되어 있고 순차 I/O만 발생.

11. 고급 기능

11.1 Column Family

한 데이터베이스에 여러 "논리적 DB"를 두는 방법.

auto db = DB::Open(options, "/path", 
    {"default", "index", "data"}, &handles, &db);

db->Put(write_opts, handles[1], key, value);  // index CF에
db->Put(write_opts, handles[2], key, value);  // data CF에

각 column family는 독립된 memtable, SST, compaction. 하지만 WAL은 공유 → atomic write across CF.

용도:

• 다른 라이프사이클을 가진 데이터 (hot vs cold).
• 다른 튜닝이 필요한 데이터 (compression, bloom 등).
• 완전히 다른 key space.

11.2 Merge Operator

일반적인 Put은 값을 덮어쓴다. Merge는 "기존 값과 결합".

db->Merge(write_opts, "counter", "1");  // counter += 1

사용자가 MergeOperator를 구현 → RocksDB가 compaction 중 호출.

예: counter, append, set union 등. "read-modify-write"를 single call로 치환.

11.3 Transactions

RocksDB는 두 가지 트랜잭션을 지원:

OptimisticTransactionDB: 낙관적 제어. 커밋 시점에 충돌 확인.

TransactionDB (Pessimistic): 락 기반. 여러 스레드가 같은 키를 수정하려면 기다림.

auto txn = db->BeginTransaction(write_opts);
txn->Put("key", "value");
txn->Get(read_opts, "other", &other);
txn->Commit();

스냅샷 아이솔레이션 지원. RocksDB를 CockroachDB 같은 DB의 백엔드로 만드는 핵심.

11.4 BlobDB (Integrated BlobDB)

큰 값(> 100KB)은 SST에 저장하면 compaction 시 엄청난 write amplification 발생.

BlobDB는 큰 값을 별도 파일에 저장:

SST:
  key → blob_ref (파일 ID + 오프셋)

BlobFile:
  value_0
  value_1
  ...

Compaction은 키와 blob_ref만 재작성 → value 복사 없음. BlobDB가 큰 값에서는 10배 이상 성능 향상.

2021년 RocksDB 6.20에 Integrated BlobDB로 통합.

12. 실무 튜닝

12.1 기본 설정 점검

Options options;
options.create_if_missing = true;
options.IncreaseParallelism(16);                     // compaction 병렬도
options.OptimizeLevelStyleCompaction();

options.write_buffer_size = 64 * 1024 * 1024;        // 64MB memtable
options.max_write_buffer_number = 4;                 // 동시 4개
options.target_file_size_base = 64 * 1024 * 1024;    // L1 파일 크기
options.max_bytes_for_level_base = 256 * 1024 * 1024; // L1 전체 크기

BlockBasedTableOptions table_options;
table_options.block_cache = NewLRUCache(8 * 1024 * 1024 * 1024);  // 8GB
table_options.filter_policy = NewBloomFilterPolicy(10, false);
options.table_factory = NewBlockBasedTableFactory(table_options);

12.2 쓰기 위주 워크로드

options.level_compaction_dynamic_level_bytes = true;  // 하위 레벨 자동 조정
options.max_background_compactions = 8;               // 더 많은 compaction 병렬
options.compaction_style = kCompactionStyleUniversal; // 쓰기 amp ↓

12.3 읽기 위주 워크로드

options.num_levels = 7;                               // 더 많은 레벨 → 각 레벨 작게
options.level0_file_num_compaction_trigger = 2;       // L0 빨리 비우기
table_options.cache_index_and_filter_blocks = true;   // 인덱스/블룸을 cache에
table_options.pin_l0_filter_and_index_blocks_in_cache = true;

12.4 메모리 예산 관리

RocksDB의 메모리 소비:

• Memtable: write_buffer_size × max_write_buffer_number × num_cfs
• Block cache
• Index/filter (cache 안에 또는 밖에)
• WriteBuffer 예약

너무 작으면 I/O 폭주, 너무 크면 OS OOM. 전체 메모리의 50-70% 할당이 일반적.

12.5 대표 통계

std::string stats;
db->GetProperty("rocksdb.stats", &stats);
std::cout << stats << std::endl;

주요 지표:

• Amplifications (Write, Read, Space) per level.
• Compaction time, CPU, stall.
• Hit rate (block cache, memtable, filter).
• Pending compaction bytes.
• Write stall count/time.

12.6 문제 진단 체크리스트

증상 1: 쓰기가 점점 느려진다

• L0 파일 수 확인. 많으면 compaction 뒤처짐.
• CPU가 compaction에 포화됐는가?
• Disk I/O bandwidth가 포화됐는가?
• rate_limiter로 쓰기 감속.

증상 2: 읽기가 느리다

• Bloom filter hit ratio 확인. 낮으면 더 많은 비트 할당.
• Block cache hit ratio. 낮으면 캐시 크기 증가.
• Level 수 확인. 많으면 읽기 amp 증가.

증상 3: 디스크가 계속 차오른다

• Space amplification 높음 → tombstone 미정리?
• Pending compaction bytes 누적?
• CompactRange로 수동 compaction 시도.

13. RocksDB vs 대안

13.1 Pebble (CockroachDB)

Cockroach Labs가 Go로 재구현한 LSM. 2020년 CockroachDB가 RocksDB → Pebble 전환.

이유:

• Go 통합: Cgo 오버헤드 제거.
• 디버그: Go 생태계 도구로 직접 프로파일.
• 단순성: RocksDB의 수백 옵션 대신 핵심만.
• Tuned for CRDB: CockroachDB 워크로드 특화.

Pebble이 10-20% 성능 이득을 냈다. "더 나은 제너럴 LSM"이라기보다 "CRDB용 LSM".

13.2 Sled (Rust)

Rust로 짠 embedded DB. LSM이라기보다 B-epsilon tree 기반이지만 LSM과 성능 비슷. Rust 생태계에서 RocksDB의 대안으로 탐색 중. 아직 프로덕션 준비는 RocksDB보다 부족.

13.3 TerarkDB

TB급 데이터에 특화. Succinct data structure 기반 인덱스로 인덱스 메모리 오버헤드 극소화. 2020년 ByteDance 인수.

13.4 Sirius (Uber)

Uber가 Geo 데이터용으로 만든 LSM. 공간 인덱스(R-tree)와 결합.

13.5 SpeeDB

RocksDB를 상용으로 포크해서 관리형 서비스로 제공. 같은 API + 관리 도구.

14. 학습 리소스

서적:

• "Database Internals" — Alex Petrov. LSM 섹션이 훌륭함.
• "Designing Data-Intensive Applications" — Martin Kleppmann.
• Jim Gray & Andreas Reuter의 "Transaction Processing" — 고전.

논문:

• O'Neil et al., "The Log-Structured Merge Tree" (1996) — 원 논문.
• Chang et al., "Bigtable: A Distributed Storage System" (2006).
• Facebook의 MyRocks 논문들.
• "Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores" — Harvard.

소스 코드:

• RocksDB GitHub: db/, table/, memtable/, util/.
• LevelDB: 더 작고 읽기 쉬움 (학습용).
• Pebble: Go로 작성, 비교하며 학습 가능.

블로그:

• Facebook RocksDB 블로그.
• Mark Callaghan의 블로그 (ex-Facebook DB 엔지니어).
• Small Datum 블로그 (Mark Callaghan).

15. 요약 — 한 장 정리

┌─────────────────────────────────────────────────────┐
│            RocksDB / LSM Cheat Sheet                 │
├─────────────────────────────────────────────────────┤
│ 구조:                                                 │
│   Memtable (RAM) → Immutable → L0 → L1 → L2 → Ln    │
│                                                       │
│ Write Path:                                           │
│   Put → WAL → Memtable                               │
│   Memtable 가득 → flush → L0                         │
│   L0 많음 → compaction → L1                          │
│                                                       │
│ Read Path:                                            │
│   Memtable → Imm → L0(모두) → L1 → ... → Ln          │
│   각 단계 Bloom filter + Block cache로 가속           │
│                                                       │
│ Compaction:                                           │
│   - Leveled: 읽기↑ 쓰기↓  (RocksDB 기본)              │
│   - Tiered: 쓰기↑ 읽기↓  (Cassandra 기본)            │
│   - Universal: 타협                                   │
│   - FIFO: append-only                                 │
│                                                       │
│ Amplification:                                        │
│   - Write (W): 한 바이트 쓰기 / 물리적 쓰기             │
│   - Read (R): 조회당 I/O 횟수                          │
│   - Space (S): 실제 디스크 / 논리 크기                  │
│   - RUM Conjecture: 둘 최적화 → 나머지 희생            │
│                                                       │
│ Bloom Filter:                                         │
│   - False negative 없음 (SST skip 안전)              │
│   - 10 bits/key → 0.8% FP                            │
│   - Ribbon filter: 30% 작음                          │
│                                                       │
│ 주요 옵션:                                             │
│   write_buffer_size (memtable 크기)                   │
│   max_write_buffer_number (memtable 개수)             │
│   block_cache (8GB~ 권장)                             │
│   compression_per_level                                │
│   level_compaction_dynamic_level_bytes                 │
│                                                       │
│ 실전 사용자:                                            │
│   MyRocks, TiKV, YugabyteDB, Kafka Streams,          │
│   Flink, Ceph BlueStore, Solana, ArangoDB           │
│                                                       │
│ 대안:                                                  │
│   - Pebble (Go, CockroachDB)                          │
│   - LevelDB (단순, 학습용)                             │
│   - Cassandra LSM                                     │
└─────────────────────────────────────────────────────┘

16. 퀴즈

이 글이 도움이 됐다면 다음 포스트도 확인해 보세요:

• "Database MVCC와 Isolation Levels" — RocksDB의 MVCC 기반.
• "WAL과 ARIES Recovery" — WAL의 역사적 배경.
• "Database Index 마스터" — B-tree 쪽 상세, LSM과의 비교.
• "Elasticsearch & Lucene 내부" — 검색 엔진의 LSM 유사 구조.