手写 LSM 存储引擎（一）：从 B-Tree 到 LSM
(手写 LSM 存储引擎, Part 1)
从 B-Tree 说起
B-Tree 是个非常成功的设计。它的优势很直接：
- 读很快：树高 O(log n)，哪怕百亿行的表，几次磁盘 I/O 就能定位到数据
- 原地更新：改一行数据，只改一个页
- 天然有序：范围扫描、排序、游标都很自然
但 B-Tree 有一个根本性的问题——随机写。
考虑往一张表里不断 insert，新来的 key 可能落在树的任何叶子节点上。每次插入要：
- 从根节点往下走，找到目标叶子页
- 把新记录插进去
- 如果叶子页放不下了，分裂成两个页，分裂可能向上递归
- 把修改过的页写回磁盘
问题出在第 4 步。磁盘 I/O 的单位是"页"（典型 4KB 或 16KB），你只是改了几十字节，但要把整个页重新写一遍。而且连续几次写请求很可能落在完全不同的页上——这就是随机写。
机械盘上随机写是噩梦，寻道开销巨大。SSD 好一点，但也好得有限——SSD 的擦除单位是"块"（好几 MB），修改一个页实际会触发"读出整块-擦除-重写"的放大。此外，B-Tree 本身为了维持平衡，周期性地做节点分裂和合并，又加了一层写放大。
对于读多写少、写入相对集中的场景（比如 OLTP），B-Tree 跑得非常好。但如果应用长这样——
- 日志系统：每秒百万条事件往里塞
- IoT 时序数据：海量传感器持续上报
- 消息队列元数据：高频写入，读主要是按时间窗口扫描
- 区块链状态存储：每个区块都是大量写入
——B-Tree 就撑不住了。写入吞吐成了瓶颈。
LSM 的核心思想
LSM 的出发点是一个简单的观察：顺序写比随机写快几个数量级。机械盘上省掉了寻道，SSD 上也让控制器的垃圾回收负担小很多。
所以 LSM 做了一个看似极端的决定——所有写入都顺序追加，永不修改已有数据。
这带来了几个直接的后果：
- 写入快：每个写操作都是 append，本质上是顺序 I/O
- 没有原地更新：改一个 key，就再写一条新记录；删除也是写一条"墓碑"记录
- 数据分散：同一个 key 可能以多个版本存在于不同地方，读取要合并
- 需要后台整理：不然旧数据永远不会被清理，空间和读取效率都会崩溃
为了管理这堆不断追加的数据，LSM 把它们组织成分层的结构。新数据先进内存，然后一层一层往下沉：
内存
┌──────────────────┐
│ Memtable │ ← 写入这里，支持并发读写
└──────────────────┘
│ 满了就冻结
▼
┌──────────────────┐
│ Immutable Memtable│ ← 只读，等待 flush
└──────────────────┘
│ flush 到磁盘
磁盘 ▼
┌──────────────────┐
│ L0 SSTables │ ← 和 memtable 一一对应，key 可能重叠
├──────────────────┤
│ L1 SSTables │ ← 每层容量递增
├──────────────────┤
│ L2 SSTables │
├──────────────────┤
│ ... │
└──────────────────┘
SSTable（Sorted String Table）是磁盘上不可变的文件，内部按 key 有序排列。每一层的容量按某个倍数（典型 10x）递增，越往下数据越老、越多。
后台有一个持续运行的过程叫 compaction——把某一层的 SSTable 读出来，和下一层合并，重新写成新的 SSTable。这个过程做几件事：
- 把多个版本的 key 合并成最新版本
- 丢弃已经过期的墓碑
- 让数据在每层内重新保持有序
写路径全貌
一次 Put(key, value) 发生了什么：
flowchart TB
A[客户端 Put] --> B[WAL 追加写]
B --> C[Memtable 写入]
C --> D{Memtable 满?}
D -->|否| E[返回成功]
D -->|是| F[冻结为 Immutable Memtable]
F --> G[创建新 Memtable]
G --> E
F -.后台异步.-> H[Flush 到 L0 SSTable]
H -.后台异步.-> I[Compaction]
WAL（Write-Ahead Log）是为了应对崩溃恢复——Memtable 在内存里，进程挂了就没了，但 WAL 已经落盘，重启时重放 WAL 就能恢复 Memtable。
关键点是：写路径的关键路径只有两步——WAL 追加 + Memtable 写入。两步都非常快，前者是顺序 I/O，后者是内存操作。Flush 和 compaction 都发生在后台，不阻塞写入。
读路径全貌
读取要复杂一些，因为一个 key 可能散落在多个地方：
读 Get(key)
1. 查 Memtable
↓ 没找到
2. 查 Immutable Memtables（从新到旧）
↓ 没找到
3. 查 L0 SSTables（从新到旧，因为 L0 内部 key 可能重叠）
↓ 没找到
4. 查 L1, L2, ... SSTables（每层内部 key 不重叠，二分即可）
↓
返回结果或 KeyNotFound
按时间从新到旧查找，遇到墓碑就当作"不存在"返回。这就是为什么 LSM 删除不需要真的删掉旧数据——只要有一条更新的墓碑在，旧数据就永远读不到。
读路径看起来 I/O 很多，实际有几个优化让它不至于太慢：
- Bloom filter：每个 SSTable 带一个 Bloom filter，可以快速判断"这个 key 一定不在这里"，跳过大部分 SSTable
- 有序性：除了 L0，每一层的 SSTable key 不重叠，用二分查找可以快速定位到唯一可能包含 key 的那个 SSTable
- 缓存：热数据留在 Memtable 和块缓存里
代价：放大三角
天下没有免费的午餐。LSM 换来了高写入吞吐，代价是三种"放大"：
| 放大类型 | 含义 | LSM 的情况 |
|---|---|---|
| 写放大（Write Amplification） | 用户写 1 字节，磁盘实际写入多少字节 | 高。Compaction 要不断重写数据，典型 10-30 倍 |
| 读放大（Read Amplification） | 一次逻辑读，实际触发多少次磁盘 I/O | 中等。要查多层，但 Bloom filter 能缓解 |
| 空间放大（Space Amplification） | 逻辑数据 1GB，磁盘实际占用多少 | 中等。同一 key 的多版本共存，等 compaction 清理 |
三者是跷跷板——选不同的 compaction 策略就是在三者之间做权衡：
- Size-Tiered：同一层攒够数量再合并到下一层。写放大小，但空间和读放大大
- Leveled：每层严格按容量控制，超出就立刻合并。写放大大，但空间紧凑、读放大小
RocksDB 默认用 leveled，Cassandra 默认用 size-tiered，场景不同选择不同。这个系列后面会把两种策略都实现一遍。
B-Tree vs LSM
把两者放在一起对比一下：
| 维度 | B-Tree | LSM |
|---|---|---|
| 写入吞吐 | 中等，受随机 I/O 限制 | 高，纯顺序 I/O |
| 点读延迟 | 低且稳定 | 中等，需要查多层 |
| 范围扫描 | 很好，树天然有序 | 较好，需要多路归并 |
| 空间效率 | 好，原地更新 | 差，需要 compaction |
| 实现复杂度 | 中等 | 高，compaction 是大坑 |
| 崩溃恢复 | 依赖 WAL + checkpoint | 依赖 WAL + manifest |
| 典型代表 | InnoDB, PostgreSQL, BoltDB | LevelDB, RocksDB, Pebble |
所以选型大致是——写入密集选 LSM，读延迟敏感且写入温和选 B-Tree。
本系列的规划
后面 7 篇大概这样安排：
- （二）Memtable 与跳表：内存层怎么设计，为什么是跳表，墓碑与冻结
- （三）SSTable：磁盘上的数据长什么样：block 编码、索引、Bloom filter、压缩
- （四）写路径与 WAL：崩溃恢复、manifest、checksum
- （五）读路径：多层合并与一致性视图：迭代器栈、MVCC 时间戳、snapshot
- （六）Compaction：LSM 最难的一块：size-tiered、leveled、GC
- （七）写测试，修 Bug：几个印象深刻的踩坑
- （八）性能分析：pprof、调参、对比 RocksDB
小结
LSM 不是比 B-Tree"更好"，只是换了一个取舍维度：
- 写入全部转成顺序追加，换来极高的写入吞吐
- 数据分层管理，后台 compaction 持续整理
- 读路径变复杂，靠 Bloom filter、有序性和缓存缓解
- 代价是写放大、读放大、空间放大——三角取舍
现代数据库基础设施之所以几乎清一色用 LSM，是因为如今的负载真的越来越偏写入密集——日志、监控、IoT、区块链，都在往这个方向卷。写入能不能顶得住，常常比读延迟多 1ms 更要命。
下一篇从 Memtable 开始，看看内存层怎么设计。