【RocksDB 内核机制】Leveled Compaction：层级不变式与 CompactionPicker

第 6 篇 的 VersionSet::LogAndApply 把 flush 产出的 SST 挂进 LSM 快照；第 9 篇 说明 L0 文件多时 读放大 如何上升。Leveled Compaction 是 RocksDB 默认策略（CompactionStyle::kCompactionStyleLevel）：后台 CompactionJob 在 LevelCompactionPicker 选定的输入集上归并，把数据逐层下推，同时尽量维持 L1 及以下 key 范围不重叠 的不变式。

本文是系列 第 10 篇，源码锚点：RocksDB 9.x 的 db/version_set.cc（ComputeCompactionScore、CalculateBaseBytes）、db/compaction/compaction_picker_level.cc、db/compaction/compaction_picker.h。写放大（WA）、读放大（RA）、空间放大（SA） 的定义与 Leveled 近似公式见 storage/31 LSM 工程调优——本篇只写 RocksDB 内核如何维护层级结构与触发 compaction，不重复该文推导表格。

版本锚定：RocksDB 9.x（facebook/rocksdb v9.10.0 及相邻 release）。实验：reproduce/run_db_bench.sh exp10（fillrandom,stats）。

一、Leveled 要解决什么问题

MemTable flush 持续向 L0 追加 SST。若不做 compaction：

• L0 文件 key 范围可重叠，点查需扫描多个文件（RA 上升，见 storage/31 第二节）。
• 多版本与 tombstone 无法及时归并（SA 上升）。
• 旧文件长期不被重写，但新数据仍反复 flush + 未来合并（WA 在「从不 compact」与「每层 T 倍合并」之间取平衡）。

Leveled 的核心契约：

L1+ 不重叠使 Version::Get 每层 二分定位至多一个 SST（第 7 篇）；L0 是读路径上 唯一可能多路扫描的层。

二、Size Ratio 与 MaxBytesForLevel

静态配置下（level_compaction_dynamic_level_bytes = false），VersionStorageInfo::CalculateBaseBytes（db/version_set.cc）为每层填充 level_max_bytes_：

• L1 上限 = max_bytes_for_level_base（默认 256 MiB 量级，可调）。
• Li（\(i \ge 2\)）上限 = \(L_{i-1} \times T \times \text{MaxBytesMultiplerAdditional}(i-1)\)，其中 \(T\) = max_bytes_for_level_multiplier（默认 10）。

这与 storage/31 式 \(WA_{\text{leveled}} \approx T \times (h-1)\) 的假设一致：每层向下 compact 时，约需与 整层 L(i+1) 中 key 范围重叠的 ~\(T\) 个文件做归并，用户字节在磁盘上被重写约 \(T\) 次/层。

动态层级字节（level_compaction_dynamic_level_bytes = true）

大 CF 常用 dynamic level bytes：根据 实际数据分布 计算 base_level_（L0 直接 compact 的目标层），使最底层承载绝大部分数据，上层可保持较空。CalculateBaseBytes 会：

1. 找到 第一个非空层 与 最大层 的实际大小；
2. 令 base_level_ 满足「Lbase 目标大小 ≈ max_bytes_for_level_base」；
3. 向上/向下推导各层 level_max_bytes_。

LevelCompactionBuilder::SetupInitialFiles 中，L0 的输出层为 vstorage_->base_level() 而非固定 L1——这是 9.x 与早期 LevelDB「L0 只进 L1」的重要差异。

三、L0 重叠：读代价与 compaction 输入

L0 文件来自 独立 flush，不做 key 范围互斥。因此：

• 读：Version::Get 对 L0 按 从新到旧 遍历候选文件（可能全部查 Bloom + Index）。
• 写（compaction）：L0→Lbase 一次 job 常合并 多个 L0 文件 + Lbase 中 范围重叠 的 Lbase 文件。

LevelCompactionPicker 在 L0 score 过高但 已有 L0→Lbase job 在进行 时，可改选 Intra-L0 compaction（PickIntraL0Compaction / PickSizeBasedIntraL0Compaction）：仅在 L0 内部归并，降低 sorted run 数，缓解 write stall，且与 L0→Lbase 可并行（注释：Intra-L0 compaction is independent...）。

L0 trivial move（TryPickL0TrivialMove）：若单个 L0 文件 key 范围 完全落在 Lbase 某文件间隙中、归并无实质 key 重叠，可直接 改层 而不重写数据——这是 WA 上的重要捷径。

四、Compaction Score 与触发条件

VersionStorageInfo::ComputeCompactionScore（db/version_set.cc）为每层计算 score；score ≥ 1 表示该层需要 compaction（与历史「字节/目标比」语义兼容，9.x 对大 score 还有 10× 缩放 用于优先级，阈值仍为 1.0）。

L0 score

对 Leveled / Universal / FIFO，L0 基础 score 为：

\[ \text{score}_0 = \frac{\text{num\_sorted\_runs}}{\texttt{level0\_file\_num\_compaction\_trigger}} \]

Leveled 额外考虑 L0 总 compensated 大小 与 Lbase 上限关系，避免 L0 单文件过大导致后续 巨型 L0→Lbase（见源码注释：平衡 L0 文件数与字节）。

L1+ score

\[ \text{score}_i = \frac{\sum \text{file\_compensated\_size（未在 compact 中）}}{\texttt{MaxBytesForLevel}(i)} \]

LevelCompactionPicker::NeedsCompaction 扫描各层 score ≥ 1，或存在 TTL / periodic / bottommost 标记文件等，即返回 true。

五、LevelCompactionPicker 选 compaction 流程

LevelCompactionPicker（db/compaction/compaction_picker_level.cc）通过内部 LevelCompactionBuilder 分步构造 Compaction 对象：

flowchart TB
  NEED["NeedsCompaction?"] --> BUILD["LevelCompactionBuilder::PickCompaction"]
  BUILD --> INIT["SetupInitialFiles<br/>scan score >= 1"]
  INIT --> L0{"start_level == 0?"}
  L0 -->|yes| OTHER["SetupOtherL0FilesIfNeeded"]
  L0 -->|no| EXPAND["SetupOtherInputsIfNeeded"]
  OTHER --> EXPAND
  EXPAND --> JOB["CompactionJob::Prepare/Run/Install"]

要点：

1. SetupInitialFiles：从 最高 score 层 选起始文件；L0 输出到 base_level()，Li（\(i>0\)）输出到 i+1。
2. ExpandInputsToCleanCut：扩展输入边界，保证 无遗漏 overlap 文件，且 L1+ 输入在 key 范围上形成 clean cut。
3. 并发约束：L0 同时只允许 有限 L0→Lbase job（level0_compactions_in_progress() 非空时 PickFileToCompact 跳过新的 L0→Lbase）。
4. CompactionReason：L0 文件数触发为 kLevelL0FilesNum；L1+ 字节超限为 kLevelMaxLevelSize（见 SetupInitialFiles 内赋值）。

Compaction 优先级与 round-robin

CompactionOptions 中 compaction_pri（如 kMinOverlappingRatio、kRoundRobin）影响 同层多文件 时先 pick 哪一个。Round-robin 可一次 pick 连续多个 L0 文件 组成大 compaction（SetupOtherFilesWithRoundRobinExpansion），提高单次 job 吞掉 L0 debt 的效率，但单次 job CPU / 磁盘峰值更高——与第 12 篇 max_subcompactions 配合调优。

Picker 接口在 db/compaction/compaction_picker.h；CF 构造时按 compaction_style 实例化（ColumnFamilyData 内 LevelCompactionPicker / UniversalCompactionPicker / FIFOCompactionPicker）。

六、文献中的 Leveled 模型与 Tiering 争论

RocksDB 的 LevelCompactionPicker 实现的是 工业 leveled compaction（源自 LevelDB），不是 1996 年 LSM 论文里的唯一形态。读源码时应与下列 A 级论文 对照——它们定义 size ratio \(T\)、sorted run 数与 \(WA\)/\(RA\) 的定量争论。

6.1 代表 work 对照

Dostoevsky 的核心结论（简述，细节见原文）：在 固定写放大预算 下，纯 leveled 与纯 tiering 都不是全局最优；RocksDB 的 dynamic level bytes 与 Universal 是工程侧对同一 trade-off 的响应，不是论文算法的逐行移植。

6.2 假设—结论链

6.3 开放问题

1. Workload-aware picker：learned / adaptive compaction 在研究与 RocksDB 实验特性中均有线索，无统一 GA 默认。
2. Remote compaction：存储分离后 leveled 的 网络读放大 是否抵消 \(WA\) 收益——须分论文与产品 release 引用。
3. Intra-L0 最优性：何时优于 L0→Lbase 仍靠 trace/stats，缺 closed-form 规则。

七、与三种放大的衔接（不重复 storage/31 全文）

调参 cookbook（200+ 项）见 storage/32 RocksDB 实践；write stall 在 L0 堆积时由 第 11 篇 展开。

八、实验 exp10：观察 Leveled 层级分布

reproduce/run_db_bench.sh exp10 在 Leveled（--compaction_style=0）下跑 fillrandom + stats：

cd post/db/rocksdb/reproduce && ./build_rocksdb.sh
export DB_BENCH=$PWD/rocksdb/_bin/db_bench && ./run_db_bench.sh

本机实测（WSL2，i9-12900K，RocksDB 9.4.0，2026-07-07；以下输出经删减）：

fillrandom   :       2.448 micros/op 408456 ops/sec 0.490 seconds 200000 operations
Uptime(secs): 0.5 total
Cumulative compaction: 0.00 GB write ... Comp(cnt) 0
Write Stall (count): total-delays: 0, total-stops: 0

解读：200k 写、约 0.5s 内后台 可能尚无 compaction（Comp(cnt)=0）——这是 benchmark 过短 的演示限制，不是 leveled 失效。观察层级应拉长 --num/--duration，或 --use_existing_db=1 再跑 stats。

db_bench --benchmarks=fillrandom,stats --num=200000 --value_size=100 \
  --compaction_style=0 --statistics=1 --db=<path>

九、与相邻篇目分工

十、小结

• Leveled 不变式：L0 可重叠；L1+ key 范围不重叠，点查每层至多一个 SST。
• Size ratio \(T\) 与 max_bytes_for_level_base 决定各层容量与近似 WA；dynamic level bytes 动态计算 base_level_，L0 目标层非固定 L1。
• ComputeCompactionScore 驱动 compaction 触发；LevelCompactionPicker 负责 L0→Lbase、Li→Li+1、Intra-L0 与 trivial move 选型。
• L0 文件数是 RA 与 write stall 的共同杠杆；exp10 在短跑条件下可能 看不到 compaction，须延长 workload 再读 stats。
• Dostoevsky / Merge Bush 提供 leveled vs tiering 的 定量争论；RocksDB picker 是工程实现，不是论文复现。

上一篇：Block Cache 与 Bloom

下一篇：Universal、FIFO 与 Write Stall

返回 系列目录

参考资料

1. RocksDB 9.x 源码：db/version_set.cc；db/compaction/compaction_picker_level.cc（A 级）。
2. Dayan & Idreos, The Log-Structured Merge-Bush & the Wacky Continuum, SIGMOD 2017（A 级）。
3. Dayan & Idreos, Dostoevsky, SIGMOD 2018（A 级）。
4. O’Neil et al., LSM-Tree, Acta Informatica 1996（A 级）。
5. storage/31、storage/32。
6. 本机 exp10：reproduce/output/exp10_leveled_stats.txt（RocksDB 9.4.0，2026-07-07）。
7. 第 6–9、11 篇。