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 分离存储优化

← 第 2 章 · 编译安装与语言绑定 | 第 4 章 · 基本操作 →