memtable · SSTable · compaction · Bloom filter

LSM-tree：不改页，只追加

B+ tree 的每一次写都是一次页的原地修改。改哪一页由 key 决定，所以随机 key 的写入就是随机写：读进这一页、改几个字节、写回去。SSD 上这还牵出 read-modify-write 与 erase block 的问题，机械盘上则是彻底的寻道。

LSM-tree 换掉的就是「原地」这两个字。写入只往文件尾追加，永不回头改已经落盘的东西。代价是同一个 key 的多个版本散落在不同文件里，读的时候要把它们找齐。

1 · 写路径

一次写依次经过三个地方。

首先是 WAL（write-ahead log）：一条日志追加到磁盘上一个只增不改的文件，用于崩溃后重放。这是唯一一次同步落盘，也是写入延迟的下界。

然后进 memtable，内存里的一个有序结构（跳表或平衡树）。此时写入已经算完成，返回调用方。

memtable 涨到阈值就整块冻结，排序后一次性写成一个 SSTable：磁盘上一个不可变的、按 key 升序排列的文件，附带稀疏索引与 Bloom filter。写这个文件是一次纯顺序 I/O。原来的 memtable 换一个新的空表继续接收写入，冻结的那一块在刷完盘后连同对应的 WAL 段一起释放。

删除同样是写。LSM-tree 不能原地抹掉一个 key，因为它可能存在于任意一个更旧的 SSTable 里；删除写的是一条 tombstone：一条 value 为空的记录，读的时候它遮盖住所有更旧的版本。

注 · 三个地方各写了一遍同一条数据：WAL 一份、SSTable 一份、后续 compaction 里还要再写若干份。写放大的下界因此是 2，与 compaction 策略无关。本系列引擎的实测里，WAL 与 flush 两项恒为 1.00 与 1.00，剩下的全部差异都来自 compaction 那一项。

2 · compaction 的两种策略

SSTable 只增不减的话，文件会无限累积，读要摸的文件数随时间线性增长。compaction 是后台把多个文件归并成更少文件的过程：同 key 只留最新版本，到达最深层的 tombstone 可以彻底丢掉。

图 2-1 · 写入、flush 与 compaction 的分层视图，L0 是刚刷下来的重叠文件，L1 及以下按策略组织。可切换 leveled 与 tiered 并单步执行 compaction，观察文件如何往下沉。

leveled 让 L1 及以下每一层都是一条不重叠的有序 run，切成若干个文件。第 $i$ 层的容量是 $M \cdot T^i$ （ $M$ 是 memtable 大小， $T$ 是层间倍率）。某层超容量时，挑一个文件下推到下一层，与下层区间重叠的那些文件一起重写。一次点查在每层至多摸一个文件。

tiered 让每层攒着 $T$ 个各自有序但彼此重叠的 run，攒够了整层合并成一个下推。写的次数少得多，但一次点查在每层要把所有 run 都看一遍。

区别落在同一份负载上（20 万次写、10 万个 key、 $T = 10$ 、memtable 64 条）：

	leveled	tiered
层数	5	4
compaction 次数	1290	686
写放大	56.61	4.77
磁盘上的 entry 数	103259	166728
空间放大	1.19	1.93
点查读放大（无 Bloom）	2.61	11.91
未命中读放大（无 Bloom）	2.85	14.92

写放大差 11.9 倍，未命中读放大差 5.2 倍，方向相反。

3 · Bloom filter 挡住不必要的读

每个 SSTable 附一份 Bloom filter，记录它含有哪些 key。查之前先问 filter：答「一定没有」就整个文件跳过，答「可能有」才真去读。假阴性不存在，所以跳过永远是安全的。

filter 的每 key 位数 $b$ 决定假阳率约 $(1 - e^{-k/b})^k$ ，最优的哈希个数 $k = b \ln 2$ 。同一份 leveled 负载下改 $b$ ：

每 key 位数	哈希个数	理论假阳率	实测未命中读放大	filter 内存
4	3	14.69%	0.434	42 KB
8	6	2.16%	0.065	84 KB
10	7	0.82%	0.030	105 KB
16	11	0.05%	0.002	169 KB

10 位 / key 是 LevelDB 与 RocksDB 的默认值，86423 个 key 只要 105 KB 内存，把未命中的读放大从 2.85 压到 0.030，将近百倍。

Bloom filter 对命中的查询帮助有限：要找的 key 确实在某个文件里，那次读省不掉，filter 只能挡住它上面几层的无效探测。leveled 从 2.61 降到 1.01，tiered 从 11.91 降到 1.09——两者被拉到同一水平，因为剩下的那一次读正是真正含有该 key 的那个文件。

建议 · Bloom filter 只减代价不改结果，这一条值得写成断言。本系列的测试里有一组专门验它：同一串 put / del 序列分别喂给开 filter 与关 filter 的两个实例，逐 key 比对 get 的返回值必须完全相同，同时断言开 filter 那一侧的 probed 严格更小、skipped 严格大于零。任何把 filter 写进正确性路径的实现都会在第一条上挂掉。

4 · 三个放大的取舍三角

写放大、读放大、空间放大三者构成一个取舍三角，任何 compaction 策略只能占其中两个角。这是 RUM conjecture 在 LSM 上的具体形态：Read、Update、Memory 三项开销不可能同时最优。

图 4-1 · 三个放大随 compaction 策略、层间倍率与 Bloom filter 开关的变化。可切换策略与倍率，观察写放大与读放大的方向始终相反。

层间倍率 $T$ 是最主要的旋钮。理论上 leveled 的写放大约为 $T \cdot \log_T (N/M)$ ，读放大约为层数 $\log_T (N/M)$ ，两者一升一降。实测（leveled，关 Bloom）：

$T$	层数	写放大	点查读放大	空间放大
2	12	19.56	4.40	1.53
4	7	26.95	2.49	1.20
10	5	56.61	2.61	1.19
20	4	36.38	2.67	1.08
50	3	25.25	1.99	1.01

警示 · 写放大这一列并不单调， $T = 10$ 处冒出一个 56.61 的峰，两侧都更低。这与 $T \cdot \log_T(N/M)$ 的单调预期不符，跑之前没料到。查下来原因是层数取整： $N/M \approx 1562$ ， $\log_{10} 1562 \approx 3.19$ ，向上取整成 4 个层间转移，但最深那一层只装了不到两成的数据，下推时被重写的下层数据却按满层的比例算； $T = 20$ 时 $\log_{20} 1562 \approx 2.46$ ，层数少一个，那一项就整体消失。 $T \cdot \log_T(N/M)$ 是把层数当连续量的近似，在只有三五层的规模上取整误差足以压过趋势本身。这条不写进正文的话，读者对着表会以为引擎算错了。真实系统的层数通常在 6 到 7 层，取整的影响相对小，但同样存在。

工程上的取法：写多读少（日志、时序、指标）用 tiered 或大 $T$ ；读多写少用 leveled 加小 $T$ ；两者都要则靠 Bloom filter 把读放大按住，再把 $T$ 往写优化那一侧推。RocksDB 的默认是 leveled 加 $T = 10$ ，Cassandra 默认 tiered。

5 · 参考文献

O'Neil, P., Cheng, E., Gawlick, D., & O'Neil, E. (1996). The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4), 351–385.
Chang, F., Dean, J., Ghemawat, S., et al. (2006). Bigtable: A distributed storage system for structured data. Proceedings of OSDI '06, 205–218.
Dayan, N., Athanassoulis, M., & Idreos, S. (2017). Monkey: Optimal navigable key-value store. Proceedings of SIGMOD '17, 79–94.
Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing access methods: The RUM conjecture. Proceedings of EDBT '16, 461–466.
Luo, C., & Carey, M. J. (2020). LSM-based storage techniques: A survey. The VLDB Journal, 29(1), 393–418.