手写 LSM 存储引擎（四）：写路径与 WAL

(手写 LSM 存储引擎, Part 4)

前言

前三篇把 LSM 的数据结构讲完了：Memtable 在内存，SSTable 在磁盘。这一篇把视角拉到"写入"这条路径，看看一次 Put 从 API 调用到最终持久化，中间经过了什么——以及当进程在任一步崩溃时，怎么保证数据不丢。

写路径的设计核心是两件事：快（单次写 1 µs 级）和稳（进程挂了数据不丢）。两者天然矛盾，WAL 就是调和它们的工具。

写路径总览

flowchart TB
    A[Put key,value] --> B[追加到 WAL]
    B --> C[写入 Memtable]
    C --> D{Memtable 满?}
    D -->|否| E[返回成功]
    D -->|是| F[冻结 + 创建新 Memtable]
    F --> E
    F -.后台.-> G[Flush 到 L0 SSTable]
    G -.追加.-> H[Manifest 记录变更]
    G -.后台.-> I[Compaction]

关键路径只有两步——WAL 追加 + Memtable 写入。冻结是极少数情况下才走的分支（memtable 满的时候），flush 和 compaction 发生在后台，完全不阻塞写入。

这个设计支持 1.1 µs 的单次 Put 延迟。其中 WAL 写约 1.5 µs（不 sync），Memtable 写约 1.2 µs——看起来加起来超过 1.1 µs，实际是因为 benchmark 中 WAL 没启用。启用 WAL 后延迟会到 2-3 µs 这一档。

为什么需要 WAL

问题是朴素的：Memtable 在内存里，进程崩了就没了。

Memtable 的设计让写入很快，但内存数据不持久。如果不做任何补救，宕机后所有没来得及 flush 的数据全部丢失。对数据库来说这是绝对不能接受的。

几种可能的解决方案：

方案	问题
每次 Put 直接写盘	随机 I/O，性能崩溃
每次 Put 直接 flush SSTable	产生大量小 SSTable，读放大和 compaction 成本爆炸
Memtable 写完就 flush	等于第二个方案
WAL：顺序追加一条记录，memtable 写内存	顺序写快，崩溃可恢复

WAL（Write-Ahead Log）的思路是——在写 Memtable 之前，先把这次写入追加到一个文件末尾。这条记录是顺序 I/O，比随机 I/O 快几个数量级。一旦 WAL 落盘成功，就算 Memtable 还没写、进程立刻崩溃，重启时也能从 WAL 把数据恢复出来。

这是数据库领域通用的套路——先写日志，再改数据（write-ahead logging）。PostgreSQL、MySQL、etcd、ZooKeeper，都是一模一样的思路。

WAL 的格式

一条 WAL 记录长这样：

┌───────────┬──────────┬──────────┬─────┬───────┬──────┐
│ CRC32(4B) │ k_len(2) │ v_len(2) │ key │ value │  \n  │
└───────────┴──────────┴──────────┴─────┴───────┴──────┘

几个设计选择：

• CRC 放最前面：恢复时先读 CRC，再算 payload 的实际 CRC，对不上就说明这条记录损坏
• 长度用 u16：2 字节，单条记录 key/value 最长 65535 字节。对 LSM 来说够用了
• 末尾的换行符：纯粹是为了方便用 less/hexdump 看日志，不是功能必需
• value 长度为 0：表示删除（tombstone）——和 Memtable 的设计一致

编码过程很直白：

func (r *WalRecord) Encode() []byte {
    // 先组装 payload：[k_len][v_len][key][value]
    headerAndData := make([]byte, 4+len(r.Key)+len(r.Value))
    binary.LittleEndian.PutUint16(headerAndData[0:2], uint16(len(r.Key)))
    binary.LittleEndian.PutUint16(headerAndData[2:4], uint16(len(r.Value)))
    copy(headerAndData[4:], r.Key)
    copy(headerAndData[4+len(r.Key):], r.Value)

    // 前面拼上 CRC，后面追个换行
    crc := crc32.ChecksumIEEE(headerAndData)
    buf := make([]byte, 4+len(headerAndData)+1)
    binary.LittleEndian.PutUint32(buf[0:4], crc)
    copy(buf[4:], headerAndData)
    buf[len(buf)-1] = '\n'
    return buf
}

Sync 的选择

WAL 写入有一个关键决策点——是否每次都 fsync？

os.File.Write 只是把数据推到内核的 page cache，还没真正落盘。如果此时断电，page cache 里的数据就丢了。只有 fsync 能保证数据到磁盘。但 fsync 非常慢——机械盘 5-10 ms，SSD 100 µs 左右。每次 Put 都 fsync 的话，写入吞吐会从百万 ops/s 掉到几千 ops/s。

常见的做法有几种：

策略	持久性	吞吐	适用场景
每次 Put 都 fsync	最强（断电也不丢）	低（<10K ops/s）	金融、账务
按时间批量 fsync（如每 100ms）	弱（最多丢 100ms 数据）	高	通用场景
从不 fsync，靠 OS 刷脏	最弱（宕机可能丢大量数据）	最高	缓存、日志聚合
批量写入时 fsync	折中	高	WriteBatch 场景

我们这个实现默认不 fsync，事务的 WriteBatch.Commit 会主动 sync。生产级引擎一般会开放配置让用户选。

Manifest：元数据的单一事实来源

WAL 记录的是数据——每一条用户写入。但 LSM 引擎的"状态"不只有数据，还有结构——哪些 SSTable 属于 L0、哪些属于 L1、哪些被 compaction 删除了。

假如有这么一个时序：

1. Flush 产生了 SSTable 5，加入 L0
2. Compaction 把 L0 的 1, 2, 3, 5 合并成 L1 的 6
3. 删除 1, 2, 3, 5

进程此刻崩溃。重启的时候，怎么知道现在的"真实状态"是——

• L0: [4]
• L1: [6]
• 物理文件 1.sst、2.sst、3.sst、5.sst 可以删了

靠扫磁盘？不行。磁盘上可能还残留着上次 compaction 的中间产物，或者上次启动建立过但没写进 L0 的孤儿文件。不能靠目录列举。

Manifest 就是这个元数据日志，专门记录状态变更：

type ManifestRecord struct {
    AddedL0SSTs    []uint64         // 新加入 L0 的 SST
    AddedLevelSSTs map[int][]uint64 // 新加入 L1+ 的 SST
    DeletedSSTs    []uint64         // 被删除的 SST（被 compaction 合并掉）
}

每次状态变更追加一条 JSON 记录到 manifest 文件。恢复的时候从头重放所有记录，就能算出当前的 LSM 结构：

for each record:
    state.L0 += record.AddedL0SSTs
    for level, ids in record.AddedLevelSSTs:
        state.Levels[level] += ids
    for id in record.DeletedSSTs:
        state.remove(id)

这样就不再依赖磁盘扫描——manifest 是状态的单一事实来源（single source of truth）。

用 JSON 而不是二进制编码，是为了方便调试——manifest 的量不大（每次 compaction 才追加一条），人类可读带来的可调试性远大于解析开销。生产级引擎如 RocksDB 会用紧凑的二进制格式，我们这个实现图简单。

WAL 和 Manifest 的分工

总结一下两者的角色：

	WAL	Manifest
记录什么	用户每次 Put/Delete	LSM 状态变更（SSTable 增删）
写入频率	每次写操作	Compaction/Flush 时
大小	大（和写入量成正比）	小（只有元数据）
用途	恢复 Memtable	恢复 LSM 结构
什么时候可以截断	Memtable flush 后	从不（或做 snapshot 压缩）

WAL 和 Memtable 一一对应——一个 Memtable 配一个 WAL 文件。Memtable 冻结 flush 到 SSTable 后，对应的 WAL 就可以删了（数据已经到磁盘上了，再崩溃也不会丢）。

崩溃恢复

启动时的恢复流程：

1. 打开 manifest，重放所有记录 → 得到 LSM 结构（哪些 SST 在哪层）
2. 根据结构加载所有 SSTable 到内存（只加载索引和 bloom，不加载 data block）
3. 扫描数据目录里的 WAL 文件
4. 对每个 WAL 文件：
   - 新建一个 Memtable
   - 读取所有有效记录，回放到 Memtable
   - 加入 immutable 列表，等待 flush
5. 创建一个新的空 Memtable 接收后续写入
6. 打开一个新的 WAL 文件

第 3 步的"有效记录"很重要——WAL 的最后一条可能正好写了一半就崩了，这部分数据 CRC 对不上，要丢弃：

for offset < len(data) {
    // 读 4 字节 CRC
    expectedCRC := data[offset:offset+4]
    // 读长度，算 payload 范围
    payload := data[offset+4 : ...]
    actualCRC := crc32.ChecksumIEEE(payload)
    if actualCRC != expectedCRC {
        break  // 损坏，丢弃后续所有数据
    }
    // 解析 key/value，回放
}

这种"遇到 CRC 错误就停"的策略基于一个假设——WAL 是顺序追加的，损坏只可能发生在末尾。中间出错的话就算整个 WAL 都不能用了，这种情况下需要更重的恢复工具（或者直接报损坏）。

Write Batch：批量写入

单次 Put 提供的语义很弱——没有原子性，中途宕机会部分成功。对很多场景（比如"扣库存+下订单"），我们需要多个写操作要么全成功要么全失败。

WriteBatch 提供这个保证：

batch := engine.NewWriteBatch()
batch.Put([]byte("inventory:1"), []byte("99"))
batch.Put([]byte("order:1001"), []byte("{...}"))
err := batch.Commit()  // 原子地完成

实现的关键是——整个 batch 作为一条 WAL 记录写入：

┌───────────┬──────────────┬──────────────┬─────┬──────────────┬─────┐
│ CRC32(4B) │ batch_len(4) │  record 1    │ ... │  record N    │  \n │
└───────────┴──────────────┴──────────────┴─────┴──────────────┴─────┘

这样要么整条记录 CRC 对、全部恢复，要么 CRC 错、一条都不恢复。不可能出现"恢复了一半"的中间状态。

写入 Memtable 的时候虽然是逐条写的，但因为 WAL 已经落盘，这一步失败了也可以从 WAL 重新回放。所以原子性的锚点在 WAL 的一条记录上。

Benchmark 数据：batch=10 时 879 ns/key，batch=200 时 1340 ns/key。小 batch 的分摊收益很明显，大 batch 因为单次 WAL 写的数据量大反而每 key 开销上升。实际使用中 batch=50 左右是最佳平衡点。

小结

写路径是 LSM 性能的门面，几个设计要点：

1. WAL 先于 Memtable——保证 ACID 里的 Durability
2. WAL 是顺序追加——比随机 I/O 快几个数量级
3. CRC32 检测损坏——磁盘坏块、掉电部分写，都能识别
4. Manifest 记录结构变更——LSM 状态的单一事实来源
5. Sync 策略是性能和可靠性的 tradeoff——没有一刀切的答案
6. WriteBatch 用单条 WAL 记录获得原子性——朴素但有效

下一篇换个方向——读路径，以及 MVCC 怎么把"点查"变成"某个时间点的快照读"。