LSM-Tree 全景：为什么要”先写日志再排序”

假设你在做一个写入远多于读取的存储系统——时序数据库、消息持久化层、日志归档，都是这类场景。问题很快会变得具体：每次写入都要落到 B-Tree 的某个叶子页上，这意味着随机磁盘写。即使在 SSD 上，随机写的吞吐也只有顺序写的几分之一。写入量一大，随机 I/O 会先把系统打垮。

有没有办法，把随机写变成顺序写？

1996 年 O’Neil 等人在论文 The Log-Structured Merge-Tree 中给出了一个思路：数据先写到内存里的有序结构，攒够一批再顺序刷盘，后台再慢慢归并整理。 代价是”写放大”——同一份数据会被反复写入磁盘多次——但换来了前台写路径上零随机 I/O。这就是 LSM-Tree。

本文是”从零写一个 LSM-Tree 存储引擎”系列的第 1 篇。目标很明确：搞清楚 LSM-Tree 每个组件为什么存在，数据怎么在它们之间流动，不同设计取舍的代价如何量化。后续 4 篇用 C 逐一实现，最后用 Rust 重写做对比。

B-Tree vs LSM-Tree：两种截然不同的哲学

先看写路径，两棵树的差异一目了然：

B-Tree：原地更新

B-Tree 的写操作本质是原地更新（in-place update）：

find_leaf(key)          // 磁盘随机读：从根到叶
page_write(leaf, k, v)  // 磁盘随机写：覆盖已有页
wal_commit()            // 磁盘顺序写：WAL 保证崩溃一致性

至少两次磁盘 I/O，其中一次是随机写。如果页满了还要分裂（split）——一次写变成两三次。这是 B-Tree 在写密集场景下的根本瓶颈。

LSM-Tree：追加写

LSM-Tree 反过来：绝不原地修改磁盘数据。

wal_append(key, value)       // 磁盘顺序追加
memtable_insert(key, value)  // 纯内存操作（跳表）
return OK                    // ← 前台到此结束

// 后台异步：
flush_to_sstable()           // 磁盘顺序写
compact()                    // 磁盘顺序读写

LSM-Tree 的关键不是”少写”，而是把前台写路径上的随机 I/O 全部赶到后台去。前台只剩一次顺序追加（WAL）加一次内存插入。代价也很直接：读路径变长，后台归并变重。

正面对比

维度	B-Tree	LSM-Tree
写 I/O 模式	随机	顺序
单次读性能	O(log n) 一次磁盘	可能查多层（Bloom Filter 缓解）
写放大	≥ 2×	10–70×（取决于层数和策略）
空间利用	页内碎片	过期数据 + tombstone 占空间
适用场景	读多写少、事务	写多读少、日志/时序

不存在绝对优劣。MySQL/PostgreSQL 选 B-Tree 是因为 OLTP 场景读写均衡、需要高效的范围扫描和事务。LevelDB/RocksDB 选 LSM-Tree 是因为目标场景写入量远大于读取。

LSM-Tree 架构全景

下面这张图展示了 LSM-Tree 的完整数据流——写入从左上角进入，读取从左侧逐层向下查找，后台 Compaction 在右侧默默归并：

接下来逐个拆解每个组件。

WAL（Write-Ahead Log）

WAL 解决的问题很简单：MemTable 在内存里，进程一崩就没了。所以数据必须先顺序追加到磁盘上的 WAL 文件，再写入 MemTable。崩溃后重启时逐条重放 WAL，就能恢复出崩溃前的 MemTable 状态。

WAL 的格式决定了恢复速度。LevelDB 的设计是：每条记录带 CRC32 校验 + 类型标记，按 32KB Block 对齐，支持一条记录跨 Block 分片。

→ 第 2 篇详细实现 WAL，包括分片策略和崩溃恢复的正确性证明。

MemTable

作用：内存中的有序写缓冲区。

为什么选跳表（Skip List）而不是红黑树？

并发友好：跳表的插入只需修改局部指针，容易做细粒度锁甚至无锁；红黑树的旋转操作牵涉多个节点。
实现简单：跳表 200 行 C 就能写完，红黑树的删除修复逻辑是出了名的复杂。
缓存局部性：如果节点使用 arena 分配器连续分配，遍历时缓存命中率会更高（LevelDB 正是这样做的）。

当 MemTable 占用内存达到阈值（LevelDB 默认 4MB），它被转为只读的 Immutable MemTable，同时创建一个新的空 MemTable 接收后续写入。Immutable MemTable 等待后台线程将其 flush 为磁盘上的 SSTable 文件。

→ 第 2 篇从零实现跳表和 MemTable。

SSTable（Sorted String Table）

作用：磁盘上的不可变有序文件。

每个 SSTable 是一个静态文件，内容按 key 排序，写入后永不修改。内部结构：

Data Block：存储实际的 KV 对，使用前缀压缩节省空间。每隔若干条记录设一个 restart point 用于二分查找。
Index Block：记录每个 Data Block 的最大 key、偏移量和大小——相当于 SSTable 的目录。
Meta Block：存放 Bloom Filter 数据。
Footer：固定大小，指向 Index Block 和 Meta Block 的位置——打开文件时第一个读取的东西。

读取一个 key 的流程：读 Footer → 定位 Index Block → 二分查找定位 Data Block → 读 Data Block → 在 Block 内二分查找。

为了减少这些磁盘读取，LevelDB 实现了两级缓存。Table Cache 缓存已打开的 SSTable 文件句柄和 Index Block，避免重复打开文件。Block Cache 缓存热点 Data Block，减少磁盘读取。Block Cache 的实现正是我们在《leveldb 的缓存结构》中分析过的 ShardedLRUCache。

→ 第 3 篇详细实现 SSTable 的 Block 格式、Builder 和 Reader。

Bloom Filter

作用：避免对不存在的 key 做无效磁盘读取。

Bloom Filter 是一个概率数据结构：它可以确定地告诉你”这个 key 一定不在这个 SSTable 里”，或者”这个 key 可能在”。代价是偶尔的误判——明明不在却说可能在，白读一次磁盘。

误判率取决于参数选择：

\[ p_{\text{fp}} = \left(1 - e^{-kn/m}\right)^k \]

其中 \(n\) 是 key 的数量，\(m\) 是 bit 数组大小，\(k\) 是哈希函数的个数。LevelDB 默认 10 bits/key，此时误判率约 1%。

假设有 7 层 SSTable，查一个不存在的 key 需要查每一层。没有 Bloom Filter 要读 7 次磁盘。有了 Bloom Filter，期望额外磁盘读次数 ≈ \((7-1) \times 0.01 = 0.06\) 次——几乎为零。

→ 第 3 篇从零实现 Bloom Filter，包括双重哈希技巧。

Compaction

作用：后台归并整理。Compaction 存在的根本原因是：不做归并的 LSM-Tree 会迅速退化成一堆无序的文件。

没有 Compaction 的 LSM-Tree 会迅速退化：

SSTable 文件越来越多，读取要查越来越多的文件。
已删除的 key（tombstone）永远占据磁盘空间。
同一个 key 的旧版本散落在不同 SSTable 里，浪费空间。

分层结构：SSTable 按层级组织，L0 → L1 → L2 → … → L6：

L0 比较特殊：直接从 MemTable flush 而来，各 SSTable 的 key 范围可能重叠。
L1 及以上：同一层内的 SSTable key 范围不重叠，且每层总容量是上一层的 10 倍。L1 = 10MB, L2 = 100MB, …, L6 = 1TB。

Minor Compaction（Flush）：Immutable MemTable → L0 SSTable。简单的顺序写。

Major Compaction（Merge）：选取 Ln 的一个 SSTable，找到 Ln+1 中所有 key 范围重叠的 SSTable，做多路归并排序，输出新的 Ln+1 SSTable。归并时：相同 key 只保留最新版本，tombstone 推到底层后才能真正删除。

→ 第 4 篇详细实现 Compaction，包括多路归并迭代器和 Version 管理。

三种放大：写放大、读放大、空间放大

LSM-Tree 的核心设计权衡可以用三个指标量化：

写放大（Write Amplification）

定义：实际磁盘写入量 ÷ 用户写入量。

在 Leveled Compaction 下（这里做数量级估算，忽略 L0 特殊处理和部分归并优化），每层容量是上层的 \(T\) 倍（LevelDB 默认 \(T = 10\)）。当 Ln 的一个 SSTable 被 compact 到 Ln+1 时，最坏情况下要和 Ln+1 中 \(T\) 个 SSTable 归并。一个 key 从 L0 到 L6 共经历 \(L\) 次这样的归并，所以：

\[ WA \approx T \times L \]

LevelDB 默认 \(T = 10\), \(L \approx 7\)，所以 \(WA \approx 70\)。用户写 1MB 数据，磁盘实际写了 70MB。

这个代价看起来很吓人，但请注意：这 70 次全是顺序写。在 HDD 上，一次顺序写的吞吐是随机写的 100 倍以上。即使写放大 70 倍，总吞吐量仍然远高于 B-Tree 的随机写。

读放大（Read Amplification）

定义：读取一个 key 需要的磁盘读次数。

最坏情况：key 不存在，从 MemTable 一路查到 L6，每层都要读磁盘。

Bloom Filter 真正解决的是”不存在的 key”的查询代价：每层的误判率为 \(p\)，只有误判时才会白读一次磁盘。期望的额外磁盘读次数：

\[ RA_{\text{extra}} \approx (L - 1) \times p \]

\(p = 0.01\) 时，\(RA_{\text{extra}} \approx 0.06\)。对于存在的 key，通常在前几层就能找到（热数据倾向停留在上层），但最坏情况仍然需要查到底层——如果你的读负载 key 分布均匀，读尾延迟会比 B-Tree 差。

空间放大（Space Amplification）

定义：磁盘实际占用 ÷ 用户数据的逻辑大小。

来源：同一个 key 的多个版本分布在不同层，已删除的 key 在 tombstone 被推到底层之前仍占空间。

Leveled Compaction 的空间放大：

\[ SA \leq 1 + \frac{1}{T} \approx 1.1 \]

因为最底层包含绝大部分数据，而倒数第二层最大只有底层的 \(1/T\)。这是 Leveled 策略的核心优势。

权衡的本质

三种放大不可能同时最优——降低一个必然抬高另一个。这是 LSM-Tree 设计中最核心的工程决策：

策略	写放大	读放大	空间放大	典型用户
Leveled	高 (~70)	低	低 (~1.1)	LevelDB, RocksDB
Size-Tiered	低 (~10)	高	高 (~2.0)	Cassandra, ScyllaDB
FIFO	极低 (~1)	极高	极高	时序数据（TTL 过期）
Universal	可调	可调	可调	RocksDB（按需配置）

你的选择取决于工作负载：写密集且不在乎空间？Size-Tiered。读写均衡且空间敏感？Leveled。只有插入和 TTL 删除？FIFO。

一次完整的读写操作走查

把所有组件串起来，看数据如何流过一个 LSM-Tree 存储引擎：

写路径走查

db.Put("user:1001", "{name: Alice, age: 30}")

CRC32 校验：计算 key + value 的校验码，插入 WAL record。
WAL 追加：将 [CRC32 | length | type | key | value] 顺序追加到 WAL 文件末尾。如果开启了 sync 模式，调用 fsync() 确保落盘。
MemTable 插入：以 InternalKey = user:1001 | seq=42 | type=Put 为 key，插入跳表。
返回成功。整个前台延迟 < 1ms（SSD 上）。

如果此时 MemTable 占用达到 4MB：

当前 MemTable 标记为 Immutable，新建空 MemTable 继续接收写入。
后台线程将 Immutable MemTable 的数据顺序遍历，写入一个新的 L0 SSTable 文件。

读路径走查

db.Get("user:1001")

查 MemTable：在跳表中查找。命中 → 直接返回。
查 Immutable MemTable（如果存在）：同上。
查 L0 SSTable：L0 的多个 SSTable key 范围可能重叠，需要全部检查。对每个 SSTable：先查 Bloom Filter（“一定不在” → 跳过），再在 Index Block 二分查找定位 Data Block，最后读 Data Block。
查 L1 → L6：每层 key 不重叠，先二分确定哪个 SSTable，然后同样 Bloom → Index → Data。
所有层都没找到 → 返回 NotFound。

每一次”读 Data Block”都可能命中 Block Cache 而跳过磁盘 I/O。

删除走查

db.Delete("user:1001") 实际上是写入一条 tombstone 记录：

InternalKey = user:1001 | seq=43 | type=Delete

物理删除直到 Compaction 时才发生：当 tombstone 被归并到最底层且没有更旧的同 key 记录时，才真正丢弃。

现实世界的 LSM-Tree

LSM-Tree 不是学术玩具。以下系统的核心存储引擎都基于 LSM-Tree：

LevelDB（Google, 2011）—— 开山鼻祖，代码简洁（约 2 万行 C++），也是本系列的蓝本。Leveled Compaction，单线程 Compaction。教学价值极高，但工程能力有限：不支持并发写入、没有列族、Compaction 会阻塞写入。不推荐直接用于生产。

RocksDB（Facebook, 2012）—— 从 LevelDB fork 而来，是目前工业界的事实标准嵌入式 LSM 引擎。核心增强：列族（Column Family）、并行 Compaction、多种压缩算法（Snappy/LZ4/ZSTD）、Universal Compaction 策略、事务支持。代价是复杂度显著上升——配置项数百个，调优需要深入理解内部机制。

Cassandra（Apache）—— 分布式数据库，默认使用 Size-Tiered Compaction。写入吞吐是它的核心卖点，但读取延迟和空间放大的代价不小，适合写入远多于读取的场景（日志、事件流）。也支持 Leveled Compaction，但社区经验是：切换策略后 Compaction 资源消耗可能飙升。

其他：HBase、ScyllaDB、CockroachDB（基于 Pebble，Go 实现的 LSM 引擎）、TiKV（基于 RocksDB）、BadgerDB（Go 实现，分离 key-value，适合大 value 场景）。

它们在 Compaction 策略、并发模型、压缩算法上的选择各不相同，但核心架构——WAL → MemTable → SSTable → Compaction——完全一致。

系列路线图

本系列共 5 篇，从概念到可运行的 KV 引擎：

篇目	标题	核心产出
第 1 篇	LSM-Tree 全景（本文）	架构心智模型 + 三种放大的数学推导
第 2 篇	WAL + MemTable	`skiplist.c/h` `wal.c/h` `memtable.c/h`
第 3 篇	SSTable + Bloom Filter	`block.c/h` `bloom.c/h` `sstable.c/h`
第 4 篇	Compaction	多路归并迭代器 + Version/MANIFEST + 策略对比
第 5 篇	完整引擎 + Rust 重写对比	DB API + 并发 + Snapshot + Iterator + Rust 重写 + benchmark

代码将放在 examples/lsm-tree/，以 LevelDB 为蓝本但大幅简化——重点是教育性而非生产级。每个模块独立可测：make test_skiplist、make test_wal、make test_bloom……

参考

Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996.
Google LevelDB 源码: google/leveldb, tag 1.23.
Facebook RocksDB Wiki: Compaction.
本站相关文章：leveldb 的缓存结构 ——Block Cache 和 Table Cache 的 LRU 实现细节。
本站相关文章：LevelDB 日常使用 ——API、性能调优、Bloom Filter 参数选择。

目录