LSM 树：Compaction 与写放大

一句话定义

LSM 树（Log-Structured Merge-Tree）把写入变成「内存表顺序追加 + 后台归并排序（Compaction）」：用顺序 IO 承接随机写，代价是读需要跨多层查找、后台 Compaction 产生读写放大。

为什么重要

它是 RocksDB、LevelDB、Cassandra、HBase 的存储内核，也是 NoSQL/宽列家族能扛住高写入吞吐的根本原因。
与 B+ 树（kp-009）构成「读优化 vs 写优化」的两极，是存储引擎选型与压测调优的第一分叉。
写放大（WAF）、空间放大（SAF）、读放大（RAF）三角权衡是引擎面试与容量规划的高频题。

前置知识

kp-019（页与顺序/随机 IO 的代价差）。

核心概念

MemTable：内存有序结构（跳表/红黑树），写入先落这里（同时记 WAL，见 kp-020）。
SSTable（Sorted String Table）：MemTable 满后冻结刷盘的不可变有序文件。
层级（Level）：L0 各文件可能键区间重叠；L1+ 层内键不重叠、每层容量约 10 倍于上层。
Compaction：把相邻层的重叠文件归并为新文件，清理被覆盖的旧值与墓碑。
墓碑（Tombstone）：删除标记，Compaction 到最底层时才真正消失。
Bloom Filter：每层文件的概率结构，快速回答「键肯定不在此文件」，抑制读放大。

原理与机制

写入路径全部是顺序 IO：追加 WAL → 更新 MemTable → 满则整体刷成 SSTable → 后台线程按「大小分层（Tiered）或逐层（Leveled）」策略归并。读路径：先查 MemTable，再按层级查 SSTable，Bloom Filter 排除无关文件，最后命中最新版本（同键多版本按时间戳取新）。Leveled Compaction 把每层与下一层重叠部分归并，读放大小、空间放大小，但单次 Compaction 大；Tiered 归并多个满层文件，写放大小、读放大与空间放大较大。量化三角：Leveled 写放大 ≈ 每层数 × 层数（典型 10 层 × 10 = 10~30 倍），即一条 1KB 数据最终要写 10~30KB；RocksDB 因此提供 Compaction 风格调优与列族隔离热点。读放大来自跨层查找，Bloom Filter（假阳率 ~1%）把它压回常数级。

实例或案例

监控指标入库（每秒百万点、按时间序追加）：选 RocksDB 系（TiKV/InfluxDB IOx 等）看中的正是顺序写吞吐；查询「某指标近 1 小时序列」时按时间前缀在底层文件顺序扫，表现优异。反过来，若负载是「随机更新同一批用户行的余额」，LSM 的 Compaction 会反复重写包含这些键的文件，写放大击穿磁盘预算，B+ 树引擎（原地更新 + Undo）更合适。压测时观测三个指标：write_amplification = 实际写入字节 / 业务写入字节、P99 读延迟随 Compaction 积压的抖动、磁盘空间占用与逻辑数据的比值。

常见误区

认为 LSM「写入无代价」：代价被推迟而非消除，Compaction 积压时会反噬写入（stall）与读延迟。
删除即释放空间：删除只是写墓碑，物理空间在 Compaction 抵达底层才回收，大量删除后磁盘可能短暂「越删越满」。
用 B+ 树直觉调 LSM：LSM 没有「索引页缓存热度」逻辑，调优对象是层大小比例、Bloom 精度、Compaction 并发。

自测题

为什么 LSM 需要 Bloom Filter？答：读可能命中任意层任意 SSTable，逐文件二分代价高；Bloom 以极小空间给出「肯定不在」的判断，直接排除绝大多数文件，控制读放大。
Leveled 与 Tiered Compaction 的核心取舍？答：Leveled 层内不重叠，读与空间表现好但写放大约等于层数量级；Tiered 归并更粗，写放大小但读放大与空间放大更大。

公式或模型

写放大（Leveled，放大因子 r、层 n）：WAF ≈ r × n（r=10、n=4~5 时 10~30 倍）。空间放大上界：Leveled ≈ 1 + 1/r；Tiered ≈ r。读放大（含 Bloom）：RAF ≈ n × P_false + log(每文件)。

图示

LSM：内存表 → 冻结为 L0 SSTable → 逐层 Compaction 归并，旧文件被新产物取代

直观类比

B+ 树是「随到随上架」的图书馆：每本书立即插入正确格位（随机写），取书一步到位；LSM 是「先堆周转箱、夜里统一归架」的仓库：进货（写）极快，取货要翻几个周转箱，管理员（Compaction）深夜把箱子归并上架，代价是搬运翻倍（写放大）。

与其他知识点的关系

kp-009 是对照的读优化结构；kp-020 的 WAL 同样是它的写入保险；kp-027 的宽列与 KV 家族几乎全部建构在 LSM 之上；kp-012 的执行计划在 LSM 引擎中读数含义不同（SSTable 扫描）。

前置知识点

相关知识点