00 · 设计推演：从零造一个存储引擎
“这一节没有一个’正确’的最终代码。有的是八次失败，和每一次失败逼出来的设计决策。“
开场：我要你忘记所有已知的方案
老陈：给你一个需求，最朴素的那种。
需求：做一个 KV 存储。支持
Put(key, value)和Get(key)。数据要持久化——进程重启后数据还在。现在，不许用 MySQL、不许用 BoltDB、不许用任何现成的东西。你来设计。
小林：……那先想最简单的。内存里放个 map？
老陈：好。写下来。 然后我问你：这个设计有什么问题？
小林：进程退出数据就没了。
老陈：对。这就是第一次失败。我们开始，一步一步改。
v0：内存 map
type DB struct {
data map[string]string
}
func (db *DB) Put(k, v string) { db.data[k] = v }
func (db *DB) Get(k string) (string, bool) {
v, ok := db.data[k]
return v, ok
}这一版能工作。 快、简单、五十行以内。
失败原因：进程退出，数据全丢。
老陈：注意，这是最重要的一步——先写一个”能工作但很差”的版本。
很多人跳过这一步，直接想”最终方案”，结果是想出来的东西过度设计。 先有 v0，你才知道 v1 要改什么。
v1：内存 map + 定时全量落盘
思路：内存里维护 map，每隔一段时间把整个 map 序列化写到磁盘。
func (db *DB) Put(k, v string) {
db.data[k] = v
}
// 每隔 60 秒，或者每 1000 次写入
func (db *DB) snapshot() error {
// 全量序列化
buf, _ := json.Marshal(db.data)
return os.WriteFile("dump.db", buf, 0644)
}改进了：数据能存下来了。
但遇到四个问题：
| # | 问题 | 后果 |
|---|---|---|
| 1 | 上次快照之后的写入会丢 | 60 秒的快照间隔 = 最多丢 60 秒数据 |
| 2 | 快照期间怎么办？ | 一边写文件一边改 map → 数据不一致；加锁 → 服务停顿 |
| 3 | 数据量 > 内存就完蛋 | 100GB 数据需要 100GB 内存 |
| 4 | 每次全量写入 | 改 1 个字节要重写整个文件（写放大 N 倍） |
小林：那我缩短快照间隔？每秒一次？
老陈：问题 4 会更严重。 每秒重写全量文件，磁盘扛不住。
小林：那……只写变化的部分？
老陈：对。这是我们下一个版本的唯一改动。但你要想清楚：“只写变化的部分”意味着什么文件格式？
v2：追加日志（Append-Only Log）
核心改动：不重写全量，只把”这次做了什么”追加到文件末尾。
type DB struct {
data map[string][]byte // 内存索引：key → 文件偏移
file *os.File
offset int64
}
func (db *DB) Put(k, v string) error {
// 1. 序列化这条记录
rec := encode(k, v)
// 2. ★ 追加到文件末尾（顺序写！）
if _, err := db.file.Write(rec); err != nil {
return err
}
// 3. 更新内存索引
db.data[k] = db.offset
db.offset += int64(len(rec))
return nil
}
func (db *DB) Get(k string) (string, bool) {
offset, ok := db.data[k]
if !ok {
return "", false
}
// 从偏移处读一条记录
rec := readAt(db.file, offset)
return decode(rec)
}这是一个巨大的进步：
写入: 从"随机写全量"变成"顺序追加"
HDD 上快 100 倍，SSD 上快 10 倍
这是 Bitcask（Riak 的存储引擎）的核心思想
但遇到四个新问题：
| # | 问题 | 后果 |
|---|---|---|
| 1 | 文件无限增长 | 反复 Put 同一个 key，文件里全是旧版本 |
| 2 | 空间浪费 | 一个 key 更新 1000 次，磁盘上就有 1000 条记录 |
| 3 | 启动慢 | 重启要扫描整个文件重建索引（100GB 文件要几分钟） |
| 4 | 删除怎么做？ | 直接从 map 删？重启后又回来了 |
问题 4 的解法：墓碑（Tombstone）——删除也是追加一条记录，只是标记为”已删除”。
func (db *DB) Delete(k string) error {
rec := encodeTombstone(k)
db.file.Write(rec)
delete(db.data, k) // 内存里删掉
return nil
}老陈：注意”墓碑”这个思路——它不是”把东西拿走”，而是”记下一笔’拿走了’”。
这是日志结构（log-structured）的核心思维：所有操作都是追加，包括删除。
这个思路后面会反复出现：LSM 的删除、MVCC 的旧版本、Raft 的日志压缩、数据库的 MVCC vacuum。
v3：分段 + 合并（Compaction）
问题 1、2 的解法：把日志切成段，段满了就冻结，后台合并。
data.log (当前写入的段)
data.001 (已冻结)
data.002
data.003
...
后台任务: 把多个冻结段合并成一个，每个 key 只保留最新的值
func (db *DB) compact(segments []string) error {
// 1. 顺序读所有段，后面的段优先级更高
merged := make(map[string][]byte)
for _, seg := range segments { // 从旧到新
for rec := range readSegment(seg) {
if rec.IsTombstone {
delete(merged, rec.Key)
} else {
merged[rec.Key] = rec.Value
}
}
}
// 2. 写一个新的段
// 3. 删掉旧段
return nil
}效果：空间被回收了。
但还有两个问题：
| # | 问题 | 后果 |
|---|---|---|
| 1 | 启动还是要重建索引 | 要扫描所有段 |
| 2 | 查询要查多个段 | 段越多越慢，从新到旧逐个找 |
小林：查询要逐段找，那如果 key 不存在，就要把所有段都翻一遍？
老陈：对。这是最坏情况。 你想想怎么优化。
小林：……给每个段建个索引？
老陈：好主意。但先想：索引建在什么粒度上？每个 key 都建？
v4：段内有序 + 稀疏索引（SSTable 雏形）
关键改动：写入段的时候，让段内的 key 有序。
怎么做？内存里先排序，再一次性写入。
func (db *DB) flushMemTable() error {
// 1. 把内存里的 map 按 key 排序
keys := sortedKeys(db.memtable)
// 2. 顺序写入新段
f, _ := os.Create(nextSegmentName())
for _, k := range keys {
write(f, encode(k, db.memtable[k]))
}
// 3. ★ 同时写稀疏索引
// 每 N 条记录记一个 (key, offset)
return nil
}这个改动带来三个好处，都是”免费”的：
好处 1 · 合并可以用归并排序
两个有序段合并 = O(n+m)，不需要在内存里建完整 map
→ 可以合并远大于内存的段
好处 2 · 可以建稀疏索引
段内有序 → 查找 "user:9527" 时：
1. 查稀疏索引（在内存里，二分查找）
找到最后一个 <= "user:9527" 的索引项
比如 "user:9000" → offset 4096
2. 从 offset 4096 开始顺序扫描
★ 最多扫 N 条（N = 稀疏索引的间隔）
★ 不需要把每个 key 都放进索引
1000 个 key 的段，可能只要 10 个索引项
好处 3 · 范围查询变快
查询 "user:1000" 到 "user:2000"：
1. 定位起点（二分）
2. ★ 顺序扫描到终点
不需要查每个 key
这就是 SSTable（Sorted String Table）。 Google Bigtable 论文里的核心数据结构。
还差什么？
| # | 问题 | 现状 |
|---|---|---|
| 1 | 不存在的 key 查询慢 | 要二分 + 扫描，每个段都要试 |
| 2 | 段多了查询还是慢 | 10 个段 = 10 次查找 |
小林：段多了慢，那就少点段？
老陈：但段少了，合并就频繁，写放大就大。 你又遇到一对矛盾。
小林：……那先解决问题 1？不存在的 key 能不能快速排除？
老陈：对。想想：你只需要一个”可能存在 / 一定不存在”的判断。
v5：布隆过滤器 + 分层（LSM-Tree 成型）
问题 1 的解法：每个段配一个布隆过滤器。
func (db *DB) Get(k string) (string, bool) {
for i := len(db.segments) - 1; i >= 0; i-- { // 从新到旧
seg := db.segments[i]
// ★ 布隆过滤器快速排除：0 次磁盘 IO
if !seg.bloom.MayContain([]byte(k)) {
continue
}
// 可能存在，真正去查
if v, ok := seg.get(k); ok {
return v, true
}
}
return "", false
}效果：不存在的 key，几乎零 IO 就能返回。
问题 2 的解法：分层（Leveled）
L0: 刚从内存刷下来的段，key 范围可能重叠
L1: 合并后的段，key 范围不重叠
L2: 更大
...
★ 好处：L1 及以下，一个 key 只可能在某一个段里
→ 查询从 O(段数) 降到 O(层数)
到这里，你已经重新发明了 LSM-Tree。
日志追加 → 分段 → 排序 → 稀疏索引 → 布隆过滤器 → 分层合并
v2 v3 v4 v4 v5 v5
这就是 LevelDB / RocksDB / Cassandra / InfluxDB 的核心
★ 也是 Elasticsearch 的 Lucene 段机制的本质
但 LSM 有两个绕不开的问题：
① 写放大（Write Amplification）
一条记录可能被 compaction 重写 10-30 次
→ SSD 寿命损耗，磁盘带宽浪费
② 读放大（Read Amplification）
一次查询可能要查多个层、多个段
老陈：现在，我要你换个思路。
LSM 的所有问题，根子在哪？
小林：……段不可变？
老陈：对。段不可变 → 更新必须追加新版本 → 必须合并 → 写放大。
那如果允许”原地更新”呢？
v6：换个思路——原地更新（B+Tree）
思路转变：不追加了，直接在原地修改。
但怎么组织？ 如果所有记录乱序堆在文件里，查询要全表扫描。
第一次尝试：排序数组 + 二分
文件: [key1][key2][key3]...[keyN] (有序)
查询: 二分，O(log N) 次磁盘 IO
插入: ★ 要移动后面所有记录！O(N)
失败：插入太慢。
第二次尝试：分页
把文件切成固定大小的页（4KB）
每页存若干有序记录
维护一个"页目录"：每页的最小 key → 页号
查询: 二分页目录 → 定位页 → 页内二分
插入: ★ 只在页内移动，O(页大小)
好多了。但还有问题：
如果页满了怎么办？
→ 分裂成两个页
→ 页目录要更新
→ 页目录也会满
→ 页目录也要分裂
→ ★ 递归下去
这个结构就是 B+Tree
第三次尝试：B+Tree
┌──────────────┐
│ 内部节点 │ 只存 key 和子页号
│ [100 | 500] │
└───┬────┬──┬──┘
┌────┘ │ └────┐
▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐
│叶子页 │ │叶子页 │ │叶子页 │ 存真正的数据
│<100 │ │100-500│ │>500 │ ★ 叶子之间用链表相连
└──────┘ └──────┘ └──────┘
└────────┴────────┘
范围查询走链表
为什么数据库用 B+Tree 而不是 B-Tree 或红黑树？ 这是三个约束逼出来的：
约束 1: 数据在磁盘上，IO 单位是页（4KB/16KB）
→ 节点大小 = 页大小（一次 IO 读一个完整节点）
约束 2: 要尽量减少 IO 次数
→ 节点要能存尽可能多的 key → 树要矮
→ ★ 内部节点只存 key，不存数据（B+Tree 的关键！）
约束 3: 要支持范围查询
→ 叶子节点用链表相连（B+Tree 独有）
算一下:
页 16KB，key 8 字节 + 指针 6 字节 = 14 字节
→ 每节点 1170 个 key
→ 树高 3 能存 1170³ ≈ 16 亿条记录
→ ★ 16 亿数据，最多 3-4 次磁盘 IO
B+Tree 解决了 LSM 的写放大问题（原地更新，不需要 compaction）。
但引入了新问题：
| # | 问题 | 说明 |
|---|---|---|
| 1 | 随机写 | 更新一个 16KB 页里的 100 字节 → 要重写整个 16KB 页 |
| 2 | 页分裂代价高 | 要移动数据、更新父节点，可能级联 |
| 3 | ★ 崩溃时页可能写了一半 | 这是致命的 |
小林：问题 3……写了一半会怎样？
老陈：比你想的严重。不只是”这条数据丢了”。
小林：……还会怎样？
老陈：想想插入导致页分裂要几步。
小林：分配新页、移动一半数据、更新父节点、更新叶子链表……四步。
老陈：如果执行到第二步断电呢？
小林：……数据复制了一半？
老陈：不止这四个后果： ① 数据丢失（新页内容只在 page cache 里） ② 结构损坏（原页改了一半，新页没写完） ③ 空间泄漏（新页已分配但无内容，永久浪费） ④ 链表断裂（next 指针只更新了一半）
小林：那怎么办？
老陈：这就是 WAL 的由来——你下一节会学到。但先想：为什么追加日志的方案（v2-v5）不会有这个问题？
小林：……因为它是追加，不会破坏已有数据？
老陈：对！这就是 LSM 相对 B+Tree 的一个根本优势——不可变性带来的崩溃安全。
记住这个对比：
- 不可变结构（LSM）：崩溃安全，但有写放大
- 可变结构（B+Tree）：无写放大，但需要额外的崩溃恢复机制
这是一个贯穿整个存储领域的根本权衡。
v7：B+Tree + WAL（MySQL InnoDB 的做法）
崩溃问题的解法：在修改数据页之前，先把”要做什么”写进日志。
func (db *DB) Put(k, v string) error {
// 1. ★ 先写 WAL（顺序追加，很快）
db.wal.Append(&LogRecord{
Type: LogUpdate,
Key: k,
OldValue: oldValue, // 用于回滚（undo）
NewValue: v, // 用于重做（redo）
})
db.wal.Sync() // fsync
// 2. 再修改内存里的页（此时还没落盘）
page := db.findPage(k)
page.Put(k, v)
page.MarkDirty()
// 3. 返回成功（页会在后台刷盘）
return nil
}崩溃恢复：重启时读 WAL，把没落盘的修改重做一遍（redo），把没提交的事务回滚（undo）。
这就是 ARIES 算法，现代数据库的恢复基石。
而且 WAL 不只是为了恢复——它让写入变快了：
不用 WAL: 每次写入 → 随机读写数据页 (100μs) + fsync (500μs)
用 WAL: 每次写入 → 顺序追加日志 (10μs) + 批量 fsync
★ 快几十倍，因为把"随机"变成了"顺序"
老陈：看到这里，你有没有发现一个有趣的事情？
B+Tree 为了解决崩溃问题，又引入了日志——也就是说，它又变回了”日志 + 索引”的结构。
LSM 是”日志就是数据”，B+Tree 是”数据 + 辅助日志”。
两者殊途同归。
v8：你现在能做选择了
两条路的完整对比
| LSM-Tree | B+Tree | |
|---|---|---|
| 写入 | 顺序追加，极快 | 随机写，慢 10-100 倍（HDD） |
| 写入放大 | 10-30 倍（compaction） | 页级（16KB/次） |
| 点查询 | 要查多层多段 | 3-4 次 IO |
| 范围查询 | 要合并多层 | ★ 叶子链表，极快 |
| 崩溃安全 | ★ 天然安全（段不可变） | 需要 WAL |
| 空间放大 | 1.1-2 倍 | 页内碎片 |
| 延迟稳定性 | ★ compaction 有尖刺 | 稳定 |
| 事务支持 | 复杂 | ★ 天然（原地更新 + 锁） |
| 代表 | RocksDB、Cassandra、HBase、Lucene | MySQL、PostgreSQL、SQLite |
怎么选
选 LSM 的信号:
· 写多读少（写:读 > 1:1）
· 数据量巨大（TB 级）
· 能接受压缩（SSTable 压缩率高）
· 不需要强事务
选 B+Tree 的信号:
· 读多写少
· 需要事务
· 延迟要求稳定（不能有 compaction 尖刺）
· 范围查询多
★ 这一节真正的收获
不是”LSM 长这样”或”B+Tree 长那样”。而是这条推导链：
需求: 持久化 KV
│
├─ v0 内存 map
│ 失败: 数据丢失
↓
├─ v1 全量落盘
│ 失败: 写放大、数据量受限
↓
├─ v2 追加日志
│ 失败: 文件无限增长、启动慢
↓
├─ v3 分段合并
│ 失败: 查询要查多段、启动慢
↓
├─ v4 段内有序 + 稀疏索引 ← 关键洞察：有序带来三个免费好处
│ 失败: 段多仍慢、不存在 key 慢
↓
├─ v5 布隆过滤器 + 分层 ← LSM-Tree 成型
│ 失败: 写放大、读放大
↓
├─ v6 转向原地更新 → B+Tree ← 关键洞察：段不可变是写放大的根
│ 失败: 随机写、崩溃损坏
↓
└─ v7 B+Tree + WAL ← 又回到日志
剩下: 写放大 vs 读放大的权衡
每一个箭头上，都写着”上一个方案遇到了什么具体问题”。
这就是设计的过程。不是”我知道该用 B+Tree”，而是”我试过了别的，它们在这些地方不行，所以我需要这样一个结构”。
三个可以迁移的思维模式
① 先做能工作的最差版本
v0 很烂，但没有 v0，你不知道 v1 该改什么。跳过 v0 直接设计 v7，你一定会过度设计。
② 每个失败都要精确归因
❌ "v1 性能不好"
✅ "v1 有四个问题：
① 快照间隔内的数据会丢
② 快照期间一致性/可用性二选一
③ 数据量超内存就崩
④ 每次全量写入导致 N 倍写放大"
★ 不精确归因，就找不到下一步的方向
③ 注意”免费的”好处
v4 把段内改成有序，一次性得到三个好处（归并合并、稀疏索引、范围查询）。
这种”一个改动带来多个收益”的点，是设计中的杠杆。 发现它，你就找到了关键决策。
现在，轮到你了
练习：用同样的推导方式，设计一个分布式的 KV 存储。
起点（v0）：一台机器上跑我们刚做的存储引擎。
v0: 单机存储引擎
失败: 机器挂了服务不可用；容量受限
v1: ???
失败: ???
v2: ???
...
提示（不要用，先自己想）：
- 数据怎么分到多台机器？（想想第 5 章的一致性哈希）
- 副本怎么保持一致？（想想 Raft）
- 一台机器挂了怎么办？
- 网络分区了怎么办？
老陈：第 5 章的 Raft，就是这条推导链的下一环。但这次，我希望你是”自己推出来”，而不是”记住它”。
下一节
这一节我们走完了”为什么”，下一节开始走”怎么做”——把 v7 的方案真正实现出来。
带着这个问题去读：v2-v7 的每一个失败，在最终实现里分别由哪个机制解决？