LSM-tree Compaction 策略：leveling、tiering、lazy leveling 与 RocksDB 的实现
内容提要
本文澄清了LSM-tree compaction的三个常见误解：tiering写放大约为层数L而非T·L；Monkey是给小层更多Bloom filter位；RocksDB universal默认参数下写放大可达30.15，高于leveled的14.40。文章用四原语框架分析leveling、tiering、lazy leveling的代价差异，结合RocksDB 9.7.4源码讲解触发、粒度与文件选择，并实测各策略的写、读、空间放大，结论是没有普适最优策略。
延伸解读
写放大公式的常见误解
文章指出，tiering 的写放大常被误认为 T·L，但实际每层只写一次，写放大约为 L。Monkey 的 Bloom filter 分配也常被说反：它给较小的层更多位、更低误判率，而非最大层。RocksDB universal 在默认参数下，若按大小比找不到可合并的相邻 run，run 数超过触发阈值就强制合并最新几个 run，在本文负载中写放大达 30.15，高于 leveled 的 14.40。这些澄清有助于避免基于错误前提进行调优。
四原语框架与策略差异
文章采用 Sarkar 等人的四原语框架（触发条件、数据布局、粒度、数据移动策略）分析 compaction 策略。leveling 每层一个 run，写放大 O(T·L/B)，空间放大 O(1/T)；tiering 每层多个 run，写放大 O(L/B)，空间放大 O(T)；lazy leveling 只在最大层 leveling，写放大 O((T+L)/B)，空间放大与 leveling 同阶。Dostoevsky 证明没有一种策略在所有负载下占优，最优取决于更新与查询的比例。
RocksDB 实现细节与调参影响
RocksDB 9.7.4 的 leveled compaction 默认使用 kMinOverlappingRatio 挑文件，动态层大小默认开启。实测中，最小重叠比将 T=10 的写放大从 14.40 降至 13.61；动态层大小在 base 8 MiB 时写放大从 14.22 降至 14.01，但收益取决于数据量落在 T 的哪两个幂之间。universal 的 run 个数规则在 memtable 远小于数据量时会频繁介入，提高触发阈值或设 max_read_amp=0 可显著降低写放大。
实测数据与选型启示
在同一负载上，leveled T=10 写放大 14.40、平均空间放大 1.116；tiered T=10 写放大 3.32、空间放大 1.678；lazy T=8 写放大 7.99、空间放大 1.083；universal 触发 4 写放大 30.15。没有配置同时最优。选型需权衡：通用场景可选 leveled，写入密集可考虑 universal 但需注意峰值空间，时间序列等只查最近数据可用 FIFO。调参时注意 leveled 与 tiered 对 T 的响应方向相反。
Q&A
tiering compaction 的写放大真的是 T·L 吗？
不是。tiering 每层只写一次，写放大约为 L，而不是 T·L。
Monkey 优化 Bloom filter 分配时，是给大层还是小层更多位？
Monkey 给小层更多 Bloom filter 位，使小层的误判率更低，而不是给最大层更多位。
RocksDB universal compaction 的写放大一定比 leveled 低吗？
不一定。在默认参数下，universal 的写放大可能比 leveled 更高，例如在本文负载中达到 30.15，而 leveled 为 14.40。
leveling、tiering 和 lazy leveling 在代价模型上主要差在哪里？
leveling 每层一个 run，更新代价 O(T·L/B)，空间放大 O(1/T)；tiering 每层多个 run，更新代价 O(L/B)，空间放大 O(T)；lazy leveling 只在最大层 leveling，更新代价 O((T+L)/B)，空间放大 O(1/T)，短范围查询变差。
RocksDB 的 leveled compaction 如何挑选要合并的文件？
默认使用 kMinOverlappingRatio，优先选择下一层重叠字节数与自身大小之比最小的文件，以减少写放大。
RocksDB 的 FIFO compaction 适合什么场景？
适合时间序列、日志、缓存等只关心最近数据的场景，写放大恒为 1，但旧数据会随文件删除而丢失，不能当持久键值存储。
在相同负载下，leveled、tiered、lazy 和 universal 的写放大和读放大表现如何？
leveled 写放大最高（12-15），读放大最低（run 数 4.5-6.5）；tiered 写放大最低（3.3-5.2），读放大最高（run 数 8-15）；lazy 介于两者之间；universal 默认触发阈值下写放大可达 30.15，调整后降至 3.4-5.6。
RocksDB 的写停顿（write stall）在什么条件下触发？
按顺序判断：未 flush 的 memtable 数 ≥ max_write_buffer_number 或 L0 文件数 ≥ level0_stop_writes_trigger 或待合并字节 ≥ hard_pending_compaction_bytes_limit 时停止写入；L0 文件数 ≥ level0_slowdown_writes_trigger 或待合并字节 ≥ soft_pending_compaction_bytes_limit 时延迟写入。
有没有一种 compaction 策略在所有负载下都是最优的？
没有。Dostoevsky 和 Sarkar 等人的研究都表明不存在对所有负载都最优的 compaction 策略，最优选择取决于负载中更新、点查、范围查询的比例。
