LevelDB 完全指南 / 第 3 章 · 架构总览
第 3 章 · 架构总览
3.1 整体架构
LevelDB 的架构可以用一张全景图概括：
┌─────────────────────────────┐
│ 用户写入 │
└──────────┬──────────────────┘
│
▼
┌──────────────────────────────┐
│ Write-Ahead Log (WAL) │ ← 持久化保障
└──────────────────────────────┘
│
▼
┌──────────────────────────────┐
│ MemTable (内存) │ ← 跳表实现
│ ┌──────────────────────┐ │
│ │ Active MemTable │ │ ← 可写
│ ├──────────────────────┤ │
│ │ Immutable MemTable │ │ ← 只读，等待刷盘
│ └──────────────────────┘ │
└──────────────┬───────────────┘
│ Flush
▼
┌──────────────────────────────────────────────────┐
│ SSTable 文件 (磁盘) │
│ ┌────────────────────────────────────────────┐ │
│ │ Level 0 (直接从 MemTable 刷出) │ │
│ │ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ │
│ │ │SST-1 │ │SST-2 │ │SST-3 │ │SST-4 │ │ │
│ │ └──────┘ └──────┘ └──────┘ └──────┘ │ │
│ ├────────────────────────────────────────────┤ │
│ │ Level 1 (Compaction 后的有序数据) │ │
│ │ ┌────────────────┐ ┌────────────────┐ │ │
│ │ │ SST-5 │ │ SST-6 │ │ │
│ │ └────────────────┘ └────────────────┘ │ │
│ ├────────────────────────────────────────────┤ │
│ │ Level 2 (更大的有序数据集) │ │
│ │ ┌──────────────────────────────────┐ │ │
│ │ │ SST-7 │ │ │
│ │ └──────────────────────────────────┘ │ │
│ ├────────────────────────────────────────────┤ │
│ │ ... │ │
│ │ Level 6 (最大层) │ │
│ └────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────┘
核心组件一览
| 组件 | 位置 | 作用 | 数据结构 |
|---|---|---|---|
| WAL | 磁盘 | 崩溃恢复 | 顺序日志文件 |
| MemTable | 内存 | 缓冲写入 | 跳表（SkipList） |
| Immutable MemTable | 内存 | 等待刷盘 | 跳表（SkipList） |
| Table Cache | 内存 | 缓存打开的 SSTable 文件句柄 | LRU Cache |
| Block Cache | 内存 | 缓存热数据块 | LRU Cache |
| VersionSet | 内存 | 管理所有 SSTable 文件的元信息 | Version 链表 |
| Manifest | 磁盘 | 记录 SSTable 文件的增删操作 | VersionEdit 日志 |
| SSTable | 磁盘 | 存储实际数据 | 排序的键值对文件 |
| Current | 磁盘 | 指向当前活跃的 Manifest 文件 | 单行文本文件 |
3.2 MemTable
MemTable 是 LevelDB 的内存写缓冲区，所有写操作首先在这里完成。
数据结构：跳表（SkipList）
Level 3: HEAD ────────────────────────────────────→ 90 ──→ NIL
Level 2: HEAD ──────────────→ 30 ─────────────────→ 90 ──→ NIL
Level 1: HEAD ──→ 10 ───────→ 30 ──→ 50 ──────────→ 90 ──→ NIL
Level 0: HEAD ──→ 10 ──→ 20 ──→ 30 ──→ 40 ──→ 50 ──→ 60 ──→ 70 ──→ 80 ──→ 90 ──→ NIL
为什么选择跳表而不是红黑树？
| 对比项 | 跳表 | 红黑树 |
|---|---|---|
| 查找复杂度 | O(log n) | O(log n) |
| 实现复杂度 | 简单 | 复杂 |
| 范围扫描 | 天然支持（链表遍历） | 需要额外逻辑 |
| 并发友好 | 更容易实现无锁 | CAS 旋转复杂 |
| 缓存友好 | 较好 | 较差（指针多） |
| 内存开销 | 平均 1.33x | 2x（颜色位+指针） |
MemTable 内部格式
每个键值对在 MemTable 中的存储格式：
┌──────────────┬────────────┬─────────────┬──────────────┬────────────┐
│ key_size │ key │ value_size │ value │ 标记 │
│ (varint32) │ (InternalKey)│ (varint32)│ (值) │ (Put/Del) │
└──────────────┴────────────┴─────────────┴──────────────┴────────────┘
InternalKey 的格式：
┌──────────────────────┬──────────────────┬──────────┐
│ user_key │ sequence number │ type │
│ (用户提供的 Key) │ (7 字节) │ (1 字节) │
└──────────────────────┴──────────────────┴──────────┘
关键参数
| 参数 | 默认值 | 说明 |
|---|---|---|
write_buffer_size |
4 MB | 单个 MemTable 的最大大小 |
max_write_buffer_number |
2 | 最大 MemTable 数量（含 Immutable） |
min_write_buffer_number_to_merge |
1 | 刷盘前最少合并的 MemTable 数 |
💡 提示：增大
write_buffer_size可以减少 Minor Compaction 频率，但会增加内存占用和崩溃恢复时间。
3.3 Write-Ahead Log (WAL)
WAL 是 LevelDB 崩溃恢复的核心保障。任何写入在到达 MemTable 之前，必须先持久化到 WAL。
WAL 文件格式
┌─────────────────────────────────────────────────────────┐
│ Record #1 │
│ ┌────────┬────────┬────────┬───────────┬────────────┐ │
│ │ CRC32 │ Length │ Type │ Data │ Padding │ │
│ │ (4B) │ (2B) │ (1B) │ (变长) │ (对齐到) │ │
│ └────────┴────────┴────────┴───────────┴────────────┘ │
├─────────────────────────────────────────────────────────┤
│ Record #2 │
│ ┌────────┬────────┬────────┬───────────┬────────────┐ │
│ │ CRC32 │ Length │ Type │ Data │ Padding │ │
│ └────────┴────────┴────────┴───────────┴────────────┘ │
├─────────────────────────────────────────────────────────┤
│ ... │
│ Block size = 32KB │
└─────────────────────────────────────────────────────────┘
Record Type
| 类型 | 值 | 说明 |
|---|---|---|
| kZeroType | 0 | 预留 |
| kFullType | 1 | 完整记录（数据在一个 Record 中） |
| kFirstType | 2 | 分片记录的第一片 |
| kMiddleType | 3 | 分片记录的中间片 |
| kLastType | 4 | 分片记录的最后一片 |
WAL 工作流程
写入流程：
1. 用户调用 db->Put("key", "value")
2. 构造 InternalKey = "key" + seq(7) + type(Put)
3. 序列化为 WAL Record
4. 追加写入当前 WAL 文件（顺序 I/O）
5. 如果 sync=true，调用 fsync()
6. 插入 MemTable
崩溃恢复流程：
1. 打开数据库，读取 MANIFEST 文件确定最新 Version
2. 找到未归档的 WAL 文件
3. 逐条回放 WAL Record
4. 重建 MemTable
5. 触发 Flush 将 MemTable 刷到 SSTable
WAL 关键参数
| 参数 | 默认值 | 说明 |
|---|---|---|
WriteOptions::sync |
false | 每次写入后是否 fsync |
⚠️ 注意：
sync=false时，写入只保证到达 OS 缓冲区，不保证持久化到磁盘。如果机器突然断电，可能丢失最近几秒的数据。生产环境建议根据数据重要性权衡。
3.4 SSTable（Sorted String Table）
SSTable 是 LevelDB 在磁盘上的数据存储格式，文件后缀为 .ldb（或旧版本的 .sst）。
SSTable 文件结构
┌───────────────────────────────────────────────┐
│ Data Block #1 │
│ ┌──────────────────────────────────────────┐ │
│ │ Entry₁ │ Entry₂ │ ... │ Entryₙ │ │
│ └──────────────────────────────────────────┘ │
│ [重启点偏移量数组] │
├───────────────────────────────────────────────┤
│ Data Block #2 │
│ ... │
├───────────────────────────────────────────────┤
│ ... │
├───────────────────────────────────────────────┤
│ Meta Block (Bloom Filter) │
│ ┌──────────────────────────────────────────┐ │
│ │ Bloom Filter 位数组 │ │
│ └──────────────────────────────────────────┘ │
├───────────────────────────────────────────────┤
│ Meta Index Block │
│ ┌──────────────────────────────────────────┐ │
│ │ "filter" → Meta Block 位置 │ │
│ └──────────────────────────────────────────┘ │
├───────────────────────────────────────────────┤
│ Index Block │
│ ┌──────────────────────────────────────────┐ │
│ │ 最大Key₁ → Data Block #1 位置 │ │
│ │ 最大Key₂ → Data Block #2 位置 │ │
│ │ ... │ │
│ └──────────────────────────────────────────┘ │
├───────────────────────────────────────────────┤
│ Footer (固定 48 字节) │
│ ┌──────────────────────────────────────────┐ │
│ │ Meta Index Block 偏移+大小 │ │
│ │ Index Block 偏移+大小 │ │
│ │ Magic Number (0xdb4775248b80fb57) │ │
│ └──────────────────────────────────────────┘ │
└───────────────────────────────────────────────┘
Data Block 内部格式
┌─────────────┬─────────────┬───────────┬──────────┬───────────┐
│ Shared Len │ Non-Shared │ Value Len │ Key Suffix│ Value │
│ (varint) │ Len (varint)│ (varint) │ (字节) │ (字节) │
└─────────────┴─────────────┴───────────┴──────────┴───────────┘
前缀压缩示例：
Key₁ = "user:1001:name" → 存储完整 key
Key₂ = "user:1001:email" → shared=10, non_shared=5, suffix="email"
Key₃ = "user:1002:name" → shared=5, non_shared=9, suffix="1002:name"
SSTable 关键参数
| 参数 | 默认值 | 说明 |
|---|---|---|
block_size |
4096 (4KB) | Data Block 大小 |
block_restart_interval |
16 | 每隔多少个 Entry 做一次前缀压缩重启 |
compression |
kSnappyCompression | 压缩算法 |
文件命名规则
Level 0: /data/000001.ldb, 000002.ldb, ...
Level 1: /data/000005.ldb, 000008.ldb, ...
Level 2: /data/000012.ldb, ...
...
Level 6: /data/000045.ldb
WAL: /data/000003.log
Manifest: /data/MANIFEST-000002
Current: /data/CURRENT
3.5 Level 层级结构
SSTable 文件按 Level 组织，从 Level 0 到 Level 6：
| Level | 最大总大小 | SSTable 数量 | Key 范围关系 |
|---|---|---|---|
| 0 | ~10 MB | ≤ 4 个文件 | 可重叠 |
| 1 | ~10 MB | 不限 | 不重叠 |
| 2 | ~100 MB | 不限 | 不重叠 |
| 3 | ~1 GB | 不限 | 不重叠 |
| 4 | ~10 GB | 不限 | 不重叠 |
| 5 | ~100 GB | 不限 | 不重叠 |
| 6 | ~1 TB | 不限 | 不重叠 |
关键特点：
- Level 0 的 SSTable 之间 Key 范围可能重叠（因为直接从 MemTable 刷出）
- Level 1+ 的 SSTable 之间 Key 范围严格不重叠（Compaction 保证）
- 相邻 Level 之间大小比约为 10 倍（
max_bytes_for_level_multiplier）
Level 0: [a──────f] [c──────i] [b──────g] ← Key 范围重叠
Level 1: [a───c] [d───f] [g───i] ← Key 范围不重叠
Level 2: [a─b] [c─d] [e─f] [g─h] [i─j] ← Key 范围不重叠
查找流程
查找 Key="user:1001:name":
1. 查找 MemTable → 未命中
2. 查找 Immutable MemTable → 未命中
3. 查找 Level 0 SSTable（可能需要查多个文件，按新→旧顺序）
→ 在 SST-2 中找到？返回
4. 查找 Level 1（二分定位 SSTable）
→ SST-5 包含 [d───f]，Key 在范围内 → 读取并查找
5. 未找到则继续 Level 2, 3, ..., 6
3.6 Version 与 MANIFEST
Version
每个 Version 代表某一时刻数据库中所有 SSTable 文件的快照。LevelDB 使用 Version 链表管理历史版本：
VersionSet
└── current_ → Version-5
├── Level 0: {000001.ldb, 000002.ldb}
├── Level 1: {000005.ldb}
└── Level 2: {000008.ldb, 000012.ldb}
Version-4
├── ...
Version-3
└── ...
MANIFEST 文件
MANIFEST 文件记录了 Version 的变更历史（VersionEdit 序列化日志）：
MANIFEST-000002:
┌───────────────────────────────────┐
│ Edit #1: │
│ log_number = 3 │
│ add: Level 0, file 000001.ldb │
│ delete: (none) │
├───────────────────────────────────┤
│ Edit #2: │
│ log_number = 5 │
│ add: Level 1, file 000005.ldb │
│ delete: Level 0, file 000001 │
└───────────────────────────────────┘
CURRENT 文件
$ cat /data/CURRENT
MANIFEST-000002
单行文本文件，指向当前活跃的 MANIFEST 文件。
3.7 读写路径全景
写入路径
用户调用 db->Put(key, value)
│
▼
┌──────────────────────┐
│ 1. 加写锁 │ ← 保证单写者
│ 2. 分配 Sequence No. │
│ 3. 构造 InternalKey │
└──────────┬───────────┘
│
▼
┌──────────────────────┐
│ 4. 写入 WAL │ ← 崩溃恢复保障
│ (可选: fsync) │
└──────────┬───────────┘
│
▼
┌──────────────────────┐
│ 5. 插入 MemTable │ ← 内存操作
└──────────┬───────────┘
│
▼
┌──────────────────────────────────────┐
│ 6. 检查 MemTable 是否超过阈值 │
│ 是 → 将当前 MemTable 设为 Immutable │
│ 创建新 MemTable + 新 WAL │
│ 后台线程将 Immutable Flush │
└──────────────────────────────────────┘
读取路径
用户调用 db->Get(key, &value)
│
▼
┌──────────────────────────────────┐
│ 1. 加读锁（允许并发读） │
│ 2. 获取当前 Version │
│ 3. 构造 LookupKey │
└──────────┬───────────────────────┘
│
▼
┌──────────────────────────────────┐
│ 4. 查找 MemTable │ ← 找到则返回
│ 5. 查找 Immutable MemTable │ ← 找到则返回
└──────────┬───────────────────────┘
│
▼
┌──────────────────────────────────┐
│ 6. 使用 Table Cache 查找 SSTable │
│ Level 0: 遍历所有文件(新→旧) │
│ Level 1-6: 二分查找定位文件 │
│ │
│ 对每个 SSTable: │
│ a. 检查 Bloom Filter → 跳过? │
│ b. 查找 Index Block → 定位 │
│ Data Block │
│ c. 读取 Data Block → 查找 │
│ d. 找到 → 检查类型 │
│ Put → 返回 value │
│ Delete → 返回 NotFound │
└──────────┬───────────────────────┘
│
▼
┌──────────────────────────────────┐
│ 7. 所有层未找到 → 返回 NotFound │
└──────────────────────────────────┘
3.8 并发模型
LevelDB 的并发模型非常简单：
┌───────────────────────────────────────────────┐
│ LevelDB │
│ │
│ ┌────────────┐ ┌──────────────────────┐ │
│ │ Writer │ │ Reader 1 │ │
│ │ (单线程) │ │ Reader 2 │ │
│ │ │ │ Reader 3 │ │
│ │ 互斥锁 │ │ ... │ │
│ │ 保证串行 │ │ 共享读锁（无锁） │ │
│ └────────────┘ └──────────────────────┘ │
│ │
│ ┌──────────────────────────────────────────┐ │
│ │ Background Thread │ │
│ │ (Compaction / Flush) │ │
│ └──────────────────────────────────────────┘ │
└───────────────────────────────────────────────┘
| 操作 | 线程模型 | 说明 |
|---|---|---|
| 写入 | 单线程串行 | 所有写入排队，一个接一个执行 |
| 读取 | 多线程并发 | 使用引用计数，无需加锁 |
| Compaction | 后台单线程 | 异步执行，不阻塞读写 |
| Flush | 后台单线程 | 异步将 Immutable MemTable 刷盘 |
⚠️ 注意：LevelDB 不支持并发写入。如果写入成为瓶颈，考虑使用 RocksDB（支持多线程写）。
3.9 关键文件汇总
| 文件 | 作用 | 生命周期 |
|---|---|---|
*.log |
WAL 日志文件 | 写满后归档，Compaction 后删除 |
*.ldb |
SSTable 数据文件 | Compaction 生成新文件后旧文件删除 |
MANIFEST-* |
VersionEdit 日志 | 新建 MANIFEST 后旧的归档 |
CURRENT |
指向当前 MANIFEST | 持久存在 |
LOCK |
文件锁，防止多进程打开 | 持久存在 |
LOG / LOG.old |
诊断日志 | 轮转 |
3.10 本章小结
| 组件 | 核心要点 |
|---|---|
| MemTable | 跳表实现，4MB 默认大小，所有写入先到这里 |
| WAL | 顺序写日志，保证崩溃一致性 |
| SSTable | 多层结构，前缀压缩，支持 Bloom Filter |
| Level | L0 Key 可重叠，L1+ 严格有序，相邻层 10 倍递增 |
| Version/MANIFEST | 记录 SSTable 文件变更历史 |
扩展阅读
- LevelDB 源码：
db/db_impl.cc，核心实现 - SSTable 格式：
table/format.cc，SSTable 文件结构 - 跳表实现：
db/skiplist.h，无锁跳表 - Bigtable 论文：Google, 2006 — SSTable 的源头
- WiscKey 论文：USENIX FAST 2016 — Value 分离存储优化