Sigmod 论文《Rethinking The Compaction Policies in LSM-trees》阅读

文章来自清华大学交叉信息学院，论文聚焦于 LSM 树的Compact策略优化，提出了一种名为 EcoTune 的动态规划算法，旨在通过重新思考Compact操作的定位，最大化系统的平均查询吞吐量。LSM 树的核心挑战在于通过将内存中的数据批量Flush到磁盘形成 “sorted string tables”，并定期Compact重叠的待合并SSTable以减少读放大（RA）。

传统Compact策略主要关注写放大（WA）与读放大的权衡，但忽略了现代存储设备的特性。现代 NVMe SSD 具备极高的写入带宽，写入性能不再是瓶颈。Compact与查询会竞争 CPU 和 I/O 资源，因此Compact策略的核心应是优化平均查询吞吐量，而非单纯降低瞬时读放大。

论文链接 Rethinking The Compaction Policies in LSM-trees。

研究思路

将Compact视为对计算和 I/O 资源的投资，其收益是未来查询性能的提升（减少需要探测的归并待合并SSTable数量），成本是Compact过程中占用的资源，优化目标是最大化Compact的 “累积收益”。

对写入性能的影响

传统观点认为，更高的写放大（WA）会降低写入性能，这一结论源于早期HDD的限制：HDD 上的Flush和Compact操作无法并行，Compact会阻塞Flush，可能导致写入停滞和数据丢失，因此需尽可能降低Compact带来的写放大。但现代 NVMe SSD 的高写入带宽改变了这一局面：

• Flush和Compact可并行处理，且实际工作负载的写入速度通常较低；
• 只需为Flush预留足够带宽和 CPU 资源，剩余资源可自由分配给Compact和查询，Compact策略不会影响写入性能。
• 在不同 SSD 和 CPU 核心数下，不同Compact策略的平均写入延迟和尾延迟（P99）几乎无差异，作者认为Compact策略不影响写入性能。

作者认为Compact策略的设计应聚焦于如何利用剩余资源最大化查询性能。

对查询性能的影响

Compact策略的核心目标应是利用剩余资源提升平均查询性能，而非仅优化瞬时读放大（RA）。作者给出平均查询性能的定义：以 “Compact周期”（两次全局Compact的间隔）内的平均查询吞吐量为衡量标准。全局Compact会将所有待合并SSTable合并为一个，确保不同周期的策略互不影响，但是Compact对查询的双刃剑：

• 积极Compact可减少待合并SSTable数量，提升瞬时查询速度；但Compact会占用 CPU 和 I/O 资源，导致查询暂时变慢，甚至阻塞。
• 保守Compact可能增加单次查询的 I/O 成本，但能为查询保留更多资源，反而可能提升整个周期的平均吞吐量。

作者认为Compact是对资源的 “投资”，成本是Compact的写放大和资源占用，收益是未来查询性能的提升。优化目标是最大化Compact的性能提升与持续时间的乘积。

EcoTune 算法

出发点: 作者通过实验分析不同查询类型（Get、Seek、短扫描、长扫描）对Compact策略的敏感度：：
合并小SSTable对 Get、Seek 和短扫描的 I/O 性能提升有限（RangeFilter已减少不必要 I/O），但过多小SSTable会增加 CPU 开销（需更多Filter来下探SSTable内容）。
合并大SSTable显著提升长范围扫描的吞吐量（因长扫描的目标键多位于大SSTable中，Compact可降低读放大）。

作者认为Compact策略的核心应是优化大SSTable的合并，以提升长范围扫描性能，同时避免小SSTable过多导致的 CPU 开销。

核心设计

Compact过程拆分为三个逻辑层级，根据对查询性能的影响制定不同策略：

• 顶层（Top Level）：作为 SSD 上的写缓冲区，存储新刷入的小SSTable，不进行Compact（作者认为对查询 I/O 影响小）。通过全局索引记录键与运行 ID 的映射，平衡 CPU 开销与内存占用。其容量设为(S = M/K)（M为 LSM 树总大小，K为长扫描的平均键数量），确保长扫描的 I/O 效率。
• 主层（Main Level）：存储中等大小的SSTable，其Compact策略直接影响长扫描性能。通过动态规划算法优化Compact时机和粒度，每个运行配备范围过滤器加速查询。
• 最后层（Last Level）：仅保留一个SSTable，限制空间放大。当主层达到容量上限（由主层与最后层的大小比c控制）时，触发全局Compact，合并所有运行至最后层。

其中，Flush和顶层到主层的Compact使用固定线程，主层内部的Compact与查询共享剩余线程，空闲时主层线程可处理查询，提升资源利用率。通过动态规划确定主层的最优Compact策略，动态规划的核心是权衡Compact的 “成本”（资源占用时间）和 “收益”（查询性能提升的持续时间）。

动态规划算法：
问题定义：现有$e$个sstable，待处理$c$个新sstable，需确定最优Compact策略以最大化查询吞吐量累积。

状态定义：
$f(e,c)$ 表示吞吐量累计的最大值。

递推关系：
$$
f(e,c)=max_x[f(e,c) + (T_w - x \cdot T_c) \cdot q(e + 1) + f(e + 1, c - x)]
$$
其中：

• $x$: 首次合并的单位SSTable数量；
• $T_w$：生成 1 个单位SSTable的时间；
• $T_c$：合并 1 个单位SSTable的时间；
• $q(e)$：当前有e个SSTable时的查询速度；

时间复杂度：(O(R^3))（R为Compact周期内的单位SSTable总数）

个人分析

适合的场景

长范围扫描占比高的工作负载
EcoTune 的核心优化目标之一是提升长范围扫描的性能，其三级模型通过合并主层的大SSTable显著降低长扫描的 I/O 放大。

高带宽 SSD 环境
该方法的设计前提是现代 SSD 具备远超实际工作负载的写入带宽可支持Compact与查询并行执行。在这类硬件上，EcoTune 能更灵活地分配剩余资源（CPU 和 I/O），平衡Compact与查询的资源竞争。

中等写入速度的稳定工作负载
当写入速度远低于 SSD 带宽，EcoTune 保证写入不阻塞的前提下，通过动态规划优化Compact时机，最大化平均查询吞吐量。

对平均吞吐量和延迟稳定性要求高的场景
EcoTune 通过平衡Compact与查询的资源占用，减少了因Compact导致的查询排队延迟，尤其在高并发或查询请求突发的场景中，其延迟稳定性优于 Leveling 和 Lazy Leveling。作者在 30K/s 的查询到达速度下，EcoTune 的尾延迟比传统策略低 3-4 个数量级。

不适合的场景

写入速度接近或饱和 SSD 带宽的极端场景
当写入速度接近 SSD 带宽上限，Flush与Compact的并行性被打破，该方法的优化逻辑可能失效。此时使用传统策略（比如 Lazy Leveling）可能更稳定。

以点查询或短扫描为主的工作负载
EcoTune 的优化重心是主层大SSTable的合并，以提升长范围扫描性能，但对以点查询、短扫描为主的场景提升有限。实验显示，合并小SSTable对这类查询的 I/O 性能影响极小，反而可能因动态规划的资源分配逻辑增加额外开销。

硬件资源极度受限的环境
若硬件资源限制（比如 CPU 核心少、SSD 带宽低）无法支持Compact与查询并行，EcoTune 的动态规划算法难以平衡资源分配。在作者的实验中仅 4-6 个 CPU 核心的场景中，CPU 竞争和上下文切换开销会削弱其优化效果，导致性能接近甚至低于传统策略。

对瞬时性能而非平均性能要求高的场景
EcoTune 通过牺牲部分瞬时性能（如允许短期内更多SSTable存在）来优化Compact周期内的平均吞吐量。若应用场景对 “瞬时最高延迟” 或 “某一时刻的峰值性能” 要求严格（如高频交易、实时查询），其策略可能不符合需求。