1. LevelDB 기본 구조

LevelDB 캐시 메커니즘 분석 — 코드 레벨 딥다이브

GitHub 레포: https://github.com/sss654654/leveldb-cache-analysis 논문: KSC 2022 "LevelDB 캐시 구조 및 성능 분석" (홍수빈, 최민국, 유시환, 최종무) 기간: 2022.07 ~ 2022.12 | 단국대학교 System Software Lab 학부연구생

---

이 문서는 단국대학교 시스템 소프트웨어 연구실(DKU-StarLab)에서 6개월간 수행한 LevelDB 캐시 메커니즘 연구를 기술적으로 상세히 정리한 것이다. Google이 개발한 key-value 스토어 LevelDB의 내부 캐시 구조를 C++ 소스코드(cache.cc, table_cache.cc, db_impl.cc) 레벨에서 분석하고, AWS EC2에서 db_bench와 YCSB 벤치마크로 최적 캐시 파라미터를 도출하여 KSC 2022 학부생 논문으로 게재했다.

---

Part 1. LevelDB 기본 구조

1. 왜 LevelDB 캐시인가? — LSM-tree의 구조와 읽기 성능 문제

LevelDB를 연구 대상으로 선택한 이유부터 정리한다.

LevelDB는 Google이 개발한 key-value 기반 NoSQL 데이터베이스로, LSM-tree(Log-Structured Merge-tree) 구조를 사용한다.

실제 사용처:

• Chrome 브라우저의 IndexedDB
• Android의 LevelDB 백엔드

Facebook이 LevelDB를 fork하여 만든 것이 RocksDB이고, Cassandra, CockroachDB, TiKV 같은 분산 DB들이 내부 스토리지 엔진으로 RocksDB(= LSM-tree 계열)를 채택하고 있다.

→ LevelDB의 내부를 이해하면 현대 분산 DB의 저장 계층 원리를 함께 이해하는 셈이다.

LSM-tree가 무엇이고, 왜 쓰기에 빠르고 읽기에 느린지를 먼저 이해해야 캐시의 필요성이 와닿는다.

---

1-1. LSM-tree Write Path — 쓰기가 빠른 이유

전통적인 B-tree 기반 DB(MySQL InnoDB 등)는 데이터를 업데이트할 때,

디스크에서 해당 페이지를 찾아서 직접 수정(in-place update) → 임의 I/O(Random I/O)가 발생한다. 디스크의 헤드가 이리저리 움직여야 하므로 느리다.

LSM-tree는 반대로 out-place update 방식을 채택한다. → 기존 데이터를 찾아서 수정하지 않고, 항상 새로운 위치에 순차적으로 기록한다(Sequential I/O).

디스크 순차 쓰기 vs 임의 쓰기 속도 차이:

• HDD: 100배 이상
• SSD: 수배~수십 배

이것이 LSM-tree가 쓰기에 최적화된 핵심 원리다.

참고로 "기존 데이터를 수정하지 않는다"는 것은 DELETE도 마찬가지다. LSM-tree에서 삭제는 실제로 데이터를 지우는 것이 아니라 tombstone(묘비)이라는 특수 마커를 새로 쓴다. 나중에 Compaction 과정에서 원본 데이터와 tombstone이 만나면 그때 비로소 실제 삭제가 이루어진다.

LevelDB의 쓰기 흐름은 다음과 같다.

Put(key, value) 호출
  │
  ├─ 1. WAL(Write-Ahead Log)에 기록  ← 디스크 (순차 쓰기, 크래시 복구용)
  │
  └─ 2. Memtable에 삽입              ← 메모리 (SkipList 기반, O(log n))
       │
       ├─ Memtable이 write_buffer_size(기본 4MB)에 도달하면
       │   Memtable → Immutable Memtable로 전환 (읽기 전용)
       │   새로운 빈 Memtable 생성
       │
       └─ Immutable Memtable을 디스크에 flush → SSTable 파일 생성 (L0)
            이것이 Minor Compaction

각 단계를 깊이 살펴본다.

WAL(Write-Ahead Log)

데이터를 Memtable에 쓰기 전에 먼저 로그 파일에 기록한다.

왜 "먼저(Ahead) 로그에" 쓰는가? → Memtable은 메모리에 존재하므로 서버가 크래시되면 데이터가 날아간다. → WAL에 먼저 기록해두면 크래시 후 재시작 시 WAL을 순차적으로 replay하여 Memtable을 복구할 수 있다.

WAL의 핵심 특성은 append-only(추가만 가능)라는 것이다.

• 파일의 끝에 계속 덧붙이기만 하므로 Sequential I/O
• 디스크 헤드가 파일의 끝 위치만 기억하면 되므로 매우 빠르다

이 원리는 다른 시스템에서도 동일하게 사용된다:

• Kafka → commit log
• MySQL InnoDB → redo log
• PostgreSQL → WAL

"먼저 로그를 쓰고, 나중에 실제 데이터 구조에 반영한다"는 패턴은 데이터베이스 전반의 핵심 패턴이다.

WAL 파일 크기는 Memtable 크기와 직결된다.

• write_buffer_size = 4MB → WAL 최대 약 4MB
• Memtable이 flush되면 해당 WAL 파일은 삭제된다
• write_buffer_size를 크게 설정하면 flush 빈도 감소 → 성능 향상, 하지만 크래시 시 WAL replay 시간 증가

Memtable — SkipList 구현

메모리에 존재하는 정렬된 자료구조로, LevelDB는 SkipList를 사용한다.

SkipList는 정렬된 연결 리스트에 여러 레벨의 "고속도로"를 추가한 구조다. 일반 연결 리스트는 검색이 O(n)이지만, SkipList는 확률적으로 상위 레벨 포인터를 추가하여 O(log n) 검색/삽입이 가능하다.

Level 3:  HEAD ──────────────────────────────────→ 50 ───────────────────→ NIL
Level 2:  HEAD ──────────→ 20 ──────────────────→ 50 ──────→ 70 ────────→ NIL
Level 1:  HEAD ──→ 10 ──→ 20 ──→ 30 ──→ 40 ──→ 50 ──→ 60 ──→ 70 ──→ 80 → NIL

key 60을 찾는 과정:
  L3: HEAD → 50 (50 < 60, 이동) → NIL (넘어감, 아래로)
  L2: 50 → 70 (70 > 60, 아래로)
  L1: 50 → 60 (찾음!)

→ 전체 8개 노드 중 4번만에 도달. 레벨이 없으면 6번 필요.
  데이터가 많을수록 Skip 효과가 극적으로 커진다.

LevelDB가 Red-Black Tree 같은 균형 이진 트리 대신 SkipList를 선택한 이유:

1. Lock-free 구현이 쉽다
   • SkipList는 CAS(Compare-And-Swap) 연산만으로 삽입이 가능
   • 멀티스레드 환경에서 Lock 없이 동시 쓰기 가능
   • Red-Black Tree는 삽입 시 rotation이 필요 → 여러 노드를 동시에 수정해야 하므로 Lock-free 구현이 매우 어렵다
2. 순차 순회(Iterator)가 자연스럽다
   • SkipList의 Level 1은 정렬된 연결 리스트 그 자체
   • range scan이나 Iterator 구성이 O(1)로 시작
   • SSTable로 flush할 때 정렬된 순서로 순회해야 하는 LevelDB의 요구사항에 정확히 맞는다

Immutable(읽기 전용) Memtable과 Minor Compaction

Memtable이 write_buffer_size(기본 4MB, YCSB 튜닝에서 47.68MB로 최적화)에 도달하면:

1. 현재 Memtable → Immutable Memtable(읽기 전용)으로 전환
2. 백그라운드 스레드가 Immutable을 디스크의 SSTable 파일로 flush
3. 이 과정이 Minor Compaction

flush = Immutable Memtable의 내용을 디스크에 써서 SSTable 파일을 새로 만드는 것

핵심: flush 동안에도 새로운 Memtable에 쓰기가 계속 진행된다. → 쓰기가 블로킹되지 않는다. → 이것이 "Immutable"로 분리하는 이유다.

구분	역할
Active Memtable	쓰기 담당. 클라이언트의 Put/Delete를 받는다
Immutable Memtable	flush 담당. 백그라운드에서 디스크로 내려간다

다만 Immutable이 flush되기 전에 Active Memtable마저 가득 차면 → 쓰기 잠시 대기(write stall) 발생.

---

1-2. Compaction — Level 간 데이터 이동

Minor Compaction으로 생성된 SSTable은 **L0(Level 0)**에 쌓인다.

L0의 특수한 점: 파일 간 key 범위가 겹칠 수 있다.

왜? Memtable이 가득 찰 때마다 통째로 flush하기 때문이다. → key 기준으로 정리된 게 아니라, 시간 순서대로 쌓인 것일 뿐이다.

구체적 예시: 애플리케이션이 시간 순서대로 데이터를 썼다고 하자.

[1번째 Memtable]  →  flush  →  L0 파일①
  Put("order:100", "{item:book, qty:1}")
  Put("user:042", "{name:kim, age:25}")
  Put("user:099", "{name:park, age:30}")
  → key 범위: order:100 ~ user:099

[2번째 Memtable]  →  flush  →  L0 파일②
  Put("order:200", "{item:phone, qty:2}")
  Put("user:042", "{name:kim, age:26}")   ← user:042를 또 썼다! (나이 업데이트)
  Put("user:150", "{name:lee, age:28}")
  → key 범위: order:200 ~ user:150

L0 파일 ①의 범위 = order:100 ~ user:099 L0 파일 ②의 범위 = order:200 ~ user:150

→ "user:042" 구간이 겹친다! 양쪽 파일에 user:042가 모두 존재한다.

이때 Get("user:042")를 하면? → L0 파일②가 나중에 만들어졌으니까 여기 값(age:26)이 최신 → L0 파일①의 값(age:25)은 옛날 값 → 둘 다 열어봐야 어느 게 최신인지 알 수 있다

L1부터는 compaction으로 정리되어 파일끼리 key 범위가 절대 안 겹긴다. L0만 이런 문제가 있는 이유 = 정리 없이 Memtable을 그대로 내려보내는 구간이라서.

---

L0에 파일이 일정 개수(기본 4개, kL0_CompactionTrigger)에 도달하면 Major Compaction이 시작된다.

핵심 동작: L0 파일들 + L1 파일들을 merge sort로 합쳐서 깔끔한 새 L1 파일을 만든다.

merge sort 전체 과정을 구체적 예시로 보면:

─── 현재 상태 ───

L0 파일① (오래된 것): {order:100:book,   user:042:age25,  user:099:park}
L0 파일② (최신):      {order:200:phone,  user:042:age26,  user:150:lee}

L1 파일A: {config:db:timeout5, log:001:error, order:050:pen}
L1 파일B: {user:010:choi, user:200:jung}

Step 1 — L0에서 겹치는 파일 모두 선택

L0 파일①을 compaction 대상으로 잡았다.

→ L0 파일①의 key 범위 = order:100 ~ user:099 → L0 파일②의 범위(order:200 ~ user:150)와 겹침 발견 → 파일②도 같이 가져간다 (L0끼리 겹치면 반드시 함께 처리)

Step 2 — L1에서 겹치는 파일 찾기

L0 두 파일의 전체 key 범위 = order:100 ~ user:150

→ L1 파일A(config:db ~ order:050) 겹침 → 가져감 → L1 파일B(user:010 ~ user:200) 겹침 → 가져감

─── merge sort 대상: 4개 파일 ───

L0 파일①: {order:100:book,   user:042:age25,  user:099:park}
L0 파일②: {order:200:phone,  user:042:age26,  user:150:lee}
L1 파일A:  {config:db:timeout5, log:001:error, order:050:pen}
L1 파일B:  {user:010:choi,   user:200:jung}

Step 3 — merge sort 실행

4개 파일의 모든 key-value를 꺼내서 key 기준으로 정렬한다:

config:db, log:001, order:050, order:100, order:200,
user:010, user:042:age25(L0①), user:042:age26(L0②), user:099, user:150, user:200
                     ↑          ↑ 같은 key 두 개!

중복 처리:

• "user:042"가 2개 → 최신 값(age26)만 남기고 옛날 값(age25) 버림
• tombstone(삭제 마커)이 있었다면 원본과 함께 둘 다 삭제

─── 정리된 결과 ───

config:db, log:001, order:050, order:100, order:200,
user:010, user:042:age26, user:099, user:150, user:200

Step 4 — 새 L1 파일로 쪼개서 저장

결과를 2MB씩 끊어서 새 L1 SSTable로 만든다:

─── compaction 완료 후 ───

L0: (비어있음)                                          ← L0 파일①② 삭제됨
L1: 새 파일A'{config:db ~ order:200} | 새 파일B'{user:010 ~ user:200}
     key 범위가 겹치지 않는다!                           ← 원래 파일A,B도 삭제됨

→ L0의 뒤죽박죽 겹치는 파일들이 → 깔끔하게 범위가 나뉜 L1 파일들로 재탄생 → 이제 L1에서 검색할 때 파일 하나만 확인하면 된다

Compaction 출력 파일 규칙 (2가지):

1. 출력 파일이 target file size(기본 2MB, max_file_size)에 도달하면 새 파일로 전환 → SSTable 하나의 크기를 결정하는 파라미터
2. 현재 출력 파일의 key 범위가 L+2 레벨의 파일 10개 이상과 겹치면 새 파일로 전환 → 이 규칙이 없으면 나중에 L+1→L+2 compaction 시 "Compaction 폭탄" 발생 → 미래의 compaction 비용을 제한하는 선제적 조치

Key Space Rotation: Compaction은 각 레벨의 key space를 순회한다.

• 각 레벨 L에 대해 마지막 compaction이 끝난 key를 기억
• 다음 compaction 시 그 key 이후부터 시작
• 항상 같은 구간만 정리하는 것을 방지 → 전체 key space가 균등하게 정리

[Memory]                     [Disk]
                             
 Memtable ←── 현재 쓰기      L0: [SST] [SST] [SST] [SST]  ← key 범위 겹침 가능
                                    │ Major Compaction (merge sort)
 Immutable ──→ Minor         L1: [SST] [SST] [SST]        ← key 범위 겹침 없음
               Compaction         │
                             L2: [SST] [SST] [SST] [SST] [SST]
                                  │
                             Lk: [SST] [SST] ... [SST]
                             
 각 레벨의 총 크기 제한: L1: 10MB, L2: 100MB, L3: 1GB, ...
 레벨이 하나 내려갈 때마다 10배씩 커진다 (size_ratio = 10)

L1 이상의 레벨: key 범위가 겹치지 않도록 보장된다. → 검색 시 해당 레벨에서 하나의 SSTable만 확인하면 된다. → L0에서는 모든 파일을 확인해야 하지만, L1 이상에서는 binary search로 1개만.

레벨 크기 제한:

• L1: 10MB → 초과하면 L2와 merge
• L2: 100MB → 초과하면 L3로
• L3: 1GB → ...
• 점진적으로 데이터가 아래 레벨로 내려간다.

Compaction이 캐시와 직접 관련되는 이유:

• Compaction 발생 → 기존 SSTable 삭제 + 새 SSTable 생성
• Table Cache에 캐싱된 기존 SSTable의 Index Block → 무효화되어 제거 필요
• 전체 SSTable 파일 개수 = Table Cache에 필요한 최소 엔트리 수 (파일 100개 → Table Cache 최소 100개 엔트리)

Write Amplification 문제

Compaction의 대가로 Write Amplification이 발생한다.

하나의 key-value가 거치는 경로:

1. L0에 쓰임
2. L0→L1 compaction에서 다시 쓰임
3. L1→L2에서 또 다시 쓰임
4. ...최악의 경우 레벨 수만큼 반복

이것이 LSM-tree의 근본적 트레이드오프다. → 쓰기 자체는 빠르지만(Sequential I/O), 뒤에서 Compaction이라는 비용을 치른다.

RocksDB는 이를 완화하기 위해 Leveled / Universal Compaction 등 다양한 전략을 제공한다. LevelDB는 Leveled Compaction만 사용한다.

Put(key, value)
  → WAL에 기록 (크래시 대비)
  → Memtable에 삽입 (메모리, 빠름)
  → 4MB 차면 → Immutable Memtable로 전환
  → 디스크에 flush → SSTable 생성 (L0)
  → SSTable 쌓이면 → Compaction → 레벨별로 정리

• Minor Compaction = Immutable Memtable → L0 SSTable로 flush하는 것. merge sort 없음. 그냥 내려보내기.
• Major Compaction = L0 파일들 + L1 파일들을 merge sort로 합치는 것. 여기서 중복 제거, tombstone 정리가 일어남.

---

1-3. 읽기가 느린 이유 — 다중 레벨 탐색

쓰기는 Memtable에 한 번 쓰면 끝이지만,

읽기는 찾는 key가 어디에 있는지 모르기 때문에 최신 데이터부터 순서대로 찾아야 한다.

Get(key) 탐색 순서:
  Memtable (메모리)
   → Immutable Memtable (메모리)
    → L0 SSTable × 최대 4개 (모두 확인해야 함, key 범위 겹침)
     → L1 SSTable × 1개 (binary search로 1개만)
      → L2 SSTable × 1개
       → ... → Ln SSTable × 1개

최악의 경우(찾는 key가 가장 깊은 레벨에 있거나 아예 존재하지 않는 경우):

→ 모든 레벨의 SSTable을 열어서 확인해야 한다. → SSTable 하나를 열 때마다 파일 열기 + Index Block 파싱 + Data Block 읽기라는 여러 번의 Disk I/O 발생.

이 문제를 해결하기 위해 LevelDB는 두 가지 캐시를 사용한다.

캐시	역할
Table Cache (인덱스 캐시)	SSTable 파일의 Index Block을 메모리에 캐싱하여 "어느 Data Block에 찾는 key가 있는지"를 Disk I/O 없이 빠르게 탐색
Block Cache (블록 캐시)	SSTable의 Data Block과 Filter Block을 메모리에 캐싱하여 실제 데이터를 Disk I/O 없이 직접 반환

연구 목표:

이 두 캐시의 내부 구조를 C++ 소스코드(cache.cc, table_cache.cc, db_impl.cc) 레벨로 분석하고,

캐시 파라미터(개수/크기)를 조절하면서 읽기 성능 변화를 벤치마크로 측정하는 것이었다.

비유하면 도서관에서 책을 찾는 상황이다.

• Table Cache = "도서 색인 카드"를 메모리에 올려두어 어느 서가에 책이 있는지 바로 아는 것
• Block Cache = "자주 읽는 책 자체"를 책상 위에 두어 서가까지 걸어갈 필요 없이 바로 읽는 것

---

2. SSTable 구조 — 디스크에 저장되는 데이터의 물리적 형태

캐시가 "무엇을" 캐싱하는지 이해하려면 SSTable의 구조를 먼저 알아야 한다.

SSTable(Sorted String Table)은 LevelDB가 디스크에 key-value를 저장하는 파일 형식이다. 하나의 SSTable은 논리적으로 5개 블록으로 구성된다.

(SSTable: "Memtable의 데이터를 정렬된 상태로 디스크에 영구 저장한 읽기 전용 파일")

┌──────────────────┐
│   Data Block 1   │  ← key-value 데이터 저장 (정렬됨)
│   Data Block 2   │                                      ┐
│       ...        │                                      │ 데이터 영역
│   Data Block N   │                                      ┘
├──────────────────┤
│  Filter Block    │  ← Bloom Filter 저장                 ┐
├──────────────────┤                                      │
│ Meta Index Block │  ← Filter Block의 위치 정보           │ 관리 영역
├──────────────────┤                                      │
│  Index Block     │  ← 모든 Data Block의 위치 정보 (핵심!)│
├──────────────────┤                                      │
│    Footer        │  ← Meta Index + Index의 위치 (48B)   ┘
└──────────────────┘

각 블록의 역할을 정리한다.

블록	역할
Data Block	key-value 쌍이 정렬되어 저장됨. 실제 데이터가 담긴 블록. 하나의 SSTable에 여러 Data Block이 존재
Filter Block	각 Data Block에 대한 Bloom Filter 저장. "이 Data Block에 찾는 key가 있을 수 있는가?"를 빠르게 판별
Meta Index Block	Filter Block의 인덱스. key는 meta block의 이름(예: "filter.leveldb.BuiltinBloomFilter2"), value는 해당 block의 BlockHandle(offset + size)
Index Block	모든 Data Block의 인덱스. 각 Data Block당 하나의 엔트리를 저장. key는 "해당 Data Block의 마지막 key 이상이면서 다음 Data Block의 첫 key 미만인 문자열", value는 BlockHandle
Footer	고정 48 bytes. Meta Index Block과 Index Block의 BlockHandle을 저장. 파일 끝에서 고정 크기만큼 읽으면 전체 SSTable의 구조를 파악할 수 있음

각 Data Block은 block_builder.cc의 포맷으로 구성되고 선택적으로 압축(Snappy)된다. Meta Block도 동일한 포맷이다.

각 블록 뒤에는 2가지 메타데이터가 붙는다:

• 압축 여부: 1바이트 type
• CRC32 체크섬: 4바이트

[block data]
[compression type: 1 byte]   ← 0x00=none, 0x01=snappy
[crc32: 4 bytes]              ← block data + compression type의 CRC32

CRC32는 디스크 손상을 감지하기 위한 것이다. → 데이터를 읽을 때 CRC를 재계산하여 저장된 CRC와 비교 → 불일치하면 데이터 손상으로 간주하여 에러 반환 → 프로덕션 DB에서 필수적인 데이터 무결성 검증

Filter Block의 내부 구조

Filter Block은 단순히 하나의 Bloom Filter가 아니라, 여러 filter의 배열이다.

분할 기준:

• SSTable 파일의 offset을 2KB(base) 단위로 나눔
• 각 구간에 속하는 key들로 별도의 filter를 생성

offset 범위 [0KB ~ 2KB)에 시작하는 Data Block의 모든 key → filter 0
offset 범위 [2KB ~ 4KB)에 시작하는 Data Block의 모든 key → filter 1
offset 범위 [4KB ~ 6KB)에 시작하는 Data Block의 모든 key → filter 2
...

Filter Block 레이아웃:
[filter 0] [filter 1] [filter 2] ... [filter N-1]
[offset of filter 0 : 4 bytes]
[offset of filter 1 : 4 bytes]
...
[offset of filter N-1 : 4 bytes]
[offset of beginning of offset array : 4 bytes]
[lg(base) : 1 byte]    ← base=2KB이므로 lg(2048)=11

key를 찾을 때:

1. Data Block의 파일 내 offset으로부터 어느 filter를 확인해야 하는지 계산 (offset / base)
2. 해당 filter에서 key 존재 여부를 판별

이렇게 filter를 분할하면:

• 개별 filter의 크기가 작아져 False Positive 확률을 낮게 유지
• 전체 메모리 사용량을 효율적으로 관리

2-1. Bloom Filter란? — 불필요한 Disk I/O를 줄이는 확률적 자료구조

Filter Block에 저장되는 Bloom Filter를 이해해야 한다.

Bloom Filter란?

• "어떤 원소가 집합에 속하는지"를 빠르게 판별하는 확률적 자료구조
• 1970년 Burton Howard Bloom이 제안
• 공간 효율성이 극도로 높다

핵심 아이디어: → 원소를 저장하는 것이 아니라, 원소의 **"흔적(fingerprint)"**만 저장한다. → m비트의 비트 배열 + k개의 해시 함수 사용.

동작 원리는 다음과 같다.

[삽입]
 key "hello"를 k개의 해시 함수에 통과시킴
 → h1("hello") = 3, h2("hello") = 7, h3("hello") = 12
 → 비트 배열의 3, 7, 12번 위치를 1로 설정

 비트 배열: [0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0]
                   ↑           ↑               ↑

[조회]
 key "world"를 같은 k개 해시 함수에 통과시킴
 → h1("world") = 3, h2("world") = 5, h3("world") = 12
 → 5번 위치가 0 → "world"는 확실히 없음 (True Negative)

 key "hack"를 통과시킴
 → h1("hack") = 3, h2("hack") = 7, h3("hack") = 12
 → 모두 1 → "있을 수도 있음" (False Positive 가능!)

핵심 특성:

특성	설명
False Negative (있는데 없다고 판별)	절대 발생하지 않음. 삽입 시 해당 비트를 반드시 1로 설정하므로, 존재하는 원소의 비트는 반드시 모두 1이다. "없다"고 답하면 확실히 없다
False Positive (없는데 있다고 판별)	발생할 수 있음. 다른 원소들이 설정한 비트가 우연히 겹쳐서 모두 1이 될 수 있다. "있다"고 답해도 실제로는 없을 수 있다

False Positive 확률은 수학적으로 계산할 수 있다. n개 원소, m비트, k개 해시 함수일 때:

FP 확률 ≈ (1 - e^(-kn/m))^k

LevelDB의 filter_bits=10 (key 하나당 10비트):
  m/n = 10, 최적 k ≈ 10 × ln(2) ≈ 6.93 → LevelDB는 k를 자동 계산
  FP 확률 ≈ 0.8% ~ 1%

즉, 100번 조회하면 약 1번은 "있다"고 잘못 판별하여 불필요하게 Data Block을 읽는다. → 하지만 나머지 99번은 Disk I/O를 완전히 건너뛸 수 있으므로 엄청난 성능 이점.

filter_bits 트레이드오프:

filter_bits	FP 확률	Filter 크기
10 bits/key (기본값)	~1%	기준
20 bits/key	~0.0001%	2배

→ 10bits/key가 "공간 대비 FP 감소 효과"가 가장 좋은 균형점 → LevelDB의 기본값으로 채택, YCSB 튜닝에서도 변경하지 않았다.

Bloom Filter의 치명적 제약: 원소를 삭제할 수 없다.

• 비트를 0으로 되돌리면 다른 원소의 비트까지 날아갈 수 있다
• LevelDB에서는 SSTable이 immutable(생성 후 수정 불가)이므로 이 제약이 문제되지 않는다
• SSTable이 Compaction으로 삭제되면 해당 Bloom Filter도 통째로 사라진다

LevelDB에서의 활용:

• SSTable의 Data Block을 읽기 전에 Bloom Filter를 먼저 확인
• "이 Data Block에 찾는 key가 없다" → 해당 Data Block을 아예 읽지 않음
• False Positive(없는데 있다고 판별) 발생 시 → Data Block을 읽었는데 실제로 key가 없는 경우 → 성능 손해일 뿐 정확성에는 영향 없음

2-2. Delta Encoding과 block_restart_interval — Data Block 내부의 압축 기법

Data Block 내부에서 key-value가 어떻게 저장되는지도 이해해야 한다.

LevelDB는 Data Block 내에서 key를 그대로 저장하지 않고 **Delta Encoding(접두사 압축)**을 사용한다. → SSTable의 key는 정렬되어 있으므로 인접한 key들은 공통 접두사를 공유할 가능성이 높다.

원본 key 목록 (정렬됨):
  "user:000100"
  "user:000101"
  "user:000102"
  "user:000200"

Delta Encoding 적용:
  "user:000100"              ← restart point (전체 key 저장)
  [10] + "1"                 ← 앞 10글자 공유, 나머지 "1"만 저장
  [10] + "2"                 ← 앞 10글자 공유, 나머지 "2"만 저장
  [6] + "0200"               ← 앞 6글자 공유, 나머지 "0200" 저장

저장 공간이 크게 절약된다.

하지만 문제가 있다: → 중간에 있는 key를 찾으려면 앞의 key부터 순서대로 복원해야 한다. → 이를 해결하기 위해 block_restart_interval을 둔다.

block_restart_interval(기본값 16) = "몇 개의 key마다 전체 key를 다시 기록(restart)할 것인가"

block_restart_interval = 4 일 때:

  [restart point 0] "user:000100" (전체 key)
  [delta] "1"
  [delta] "2"
  [delta] "3"
  [restart point 1] "user:000200" (전체 key)  ← 4번째마다 restart
  [delta] "1"
  [delta] "2"
  [delta] "3"
  [restart point 2] "user:000300" (전체 key)
  ...

이 설정의 트레이드오프가 중요하다.

설정	효과
block_restart_interval 작음 (예: 4)	restart point가 많아져 binary search로 key를 빠르게 찾을 수 있다. 읽기 성능 향상. 하지만 전체 key 저장이 자주 되므로 저장 공간이 늘어남
block_restart_interval 큼 (예: 32)	저장 공간 절약. 하지만 restart point 간 거리가 멀어져 key 검색 시 더 많은 delta를 순차적으로 풀어야 함. 읽기 성능 저하

YCSB 튜닝 실험에서 기본값 16 → 32로 올린 이유: → 200만 레코드 환경에서 압축 효율이 읽기 성능 손실보다 더 큰 이점을 가졌기 때문 → 이 트레이드오프는 데이터 크기와 접근 패턴에 따라 달라진다.

2-3. SSTable을 열 때의 읽기 순서 — Bottom-Up

SSTable 파일을 처음 열 때 블록을 읽는 순서는 파일의 아래부터 위로다.

SSTable 파일 읽기 순서:
                                    
│   Data Block 1   │                
│       ...        │  ←── 4. 마지막: 실제 데이터 읽기
│   Data Block N   │
├──────────────────┤
│  Filter Block    │  ←── 3. Bloom Filter 확인 (Optional)
├──────────────────┤     (key가 이 Data Block에 있을 수 있는지)
│ Meta Index Block │  ←── 2. Meta Index + Index Block 로드
│  Index Block     │     (어느 Data Block에 key가 있는지 결정)
├──────────────────┤
│    Footer        │  ←── 1. 최초: Footer 읽기 (48 bytes)
└──────────────────┘     (Index Block과 Meta Index Block의 위치 획득)

이 순서의 논리:

1. Footer는 파일의 마지막 48 바이트에 고정 위치 → 바로 읽을 수 있다
2. Footer에서 Index Block의 위치를 얻어 Index Block을 로드
3. 이후 어떤 key든 "어느 Data Block에 있는지"를 바로 알 수 있다

→ 문제는 SSTable을 열 때마다 이 과정을 매번 반복해야 한다는 것이다. → 이 비용을 줄이는 것이 Part 2에서 다룰 캐시의 핵심 역할이다.

---

3. 읽기 흐름 — Memtable부터 SSTable까지의 탐색 경로

LevelDB에서 Get(key) 연산이 호출되면 다음 순서로 탐색한다.

DBImpl::Get(key)
  │
  ├─ 1. Memtable          ← 메모리 (가장 최신 데이터, SkipList)
  │     찾으면 반환, 못 찾으면 ↓
  │
  ├─ 2. Immutable Memtable ← 메모리 (flush 대기 중인 데이터)
  │     찾으면 반환, 못 찾으면 ↓
  │
  └─ 3. 디스크 SSTable     ← L0 → L1 → ... → Ln 순서로 탐색

1~2단계 (메모리): Memtable과 Immutable Memtable은 메모리에 있으므로 빠르다.

3단계 (디스크): 메모리에 없으면 디스크의 SSTable을 뒤져야 한다. 이때 탐색 방식이 레벨마다 다르다:

• L0: 파일 간 key 범위가 겹치므로 → 모든 SSTable을 확인해야 한다
• L1 이상: 파일 간 key 범위가 안 겹기므로 → Binary Search로 해당 key가 포함된 SSTable 1개만 확인

SSTable 하나를 열어서 key를 찾는 과정은 Section 2-3에서 본 것처럼:

1. Footer 읽기 (48 bytes)
2. Index Block 로드 → "어느 Data Block에 key가 있는지" 결정
3. Bloom Filter 확인 → "이 Data Block에 key가 정말 있는지" 빠르게 판별
4. Data Block 읽기 → 실제 key-value 반환

문제: 이 과정이 매번 Disk I/O를 발생시킨다.

최악의 경우를 생각해보면:

• Memtable에 없고, Immutable에도 없고
• L0의 SSTable 4개를 전부 열어봐야 하고
• L1, L2까지 내려가야 key를 찾을 수 있다면
• SSTable을 열 때마다 Footer 읽기 + Index Block 파싱 + Data Block 읽기가 반복된다

→ 한 번의 Get()에 수십 번의 Disk I/O가 발생할 수 있다.

이 문제를 해결하는 것이 캐시다.

• 한번 읽은 Index Block을 메모리에 저장해두면 → 다음에 같은 SSTable을 열 때 Footer부터 다시 읽을 필요 없음
• 한번 읽은 Data Block을 메모리에 저장해두면 → 같은 데이터를 또 요청할 때 디스크에 갈 필요 없음

Part 2에서는 이 캐시가 내부적으로 어떤 구조로 되어 있는지를 C++ 코드 레벨로 분석한다.