Paper

1. 摘要

日志结构合并树 (LSM-trees) 被广泛应用于构建键值存储系统。它们会定期合并重叠的有序运行 (sorted runs) 以减少读取放大 (read amplification)。以往关于压缩 (compaction) 策略的研究主要集中在写入放大 (write amplification, WA) 和读取放大 (read amplification, RA) 之间的权衡。

在本文中，我们提出将 LSM-trees 中的压缩操作视为一种计算和 I/O 带宽投资，旨在提高系统未来的查询吞吐量，从而重新思考压缩策略的设计。典型的 LSM-tree 应用会处理稳定但中等的写入流，并优先为小规模有序运行的顶层刷新 (top-level flushes) 分配资源，以避免因写入停顿造成数据丢失。因此，压缩策略的目标是维护最佳数量的有序运行，以最大限度地提高平均查询吞吐量。

由于压缩和读取操作会争夺相同的 CPU 和 I/O 资源，我们必须进行联合优化，以确定压缩的适当时间和积极程度。我们引入了一个 LSM-tree 的三级模型，并提出了 EcoTune，这是一种基于动态规划的算法，可以根据工作负载特征找到最优的压缩策略。我们对 RocksDB 的评估表明，在具有范围/点查询比率的工作负载下，EcoTune 相较于分层 (leveling) 策略可将平均查询吞吐量提高 1.5 倍至 3 倍，相较于惰性分层 (lazy-leveling) 策略可提高高达 1.8 倍。

2. 简介

以往的工作主要关注写放大和读放大的权衡，并认为写放大会导致低性能。实际上LSM树的写入流平稳且适度（写入速度不是很高）（Meta展示实际负载峰值45MB/s，远小于NVMe SSD提供的2GB/s带宽）。并且为了防止写停顿，会优先处理顶层的数据刷新。实验表明，将剩余的CPU和IO资源分配任意比例分配给压缩和查询都不会影响写入性能。因此，压缩策略的目标是优化查询性能，并且由于压缩操作和读取操作需要争夺相同的剩余 CPU 和 I/O 资源，因此需要联合优化。

以往的研究通常使用压缩操作刚完成后的最坏情况来建模查询性能。实际上读放大会随着有序段（sorted run）的数量变化而改变。因此应该看平均查询吞吐量指标而非瞬态的读放大指标。

实验：经典的 Leveling 策略相比 Lazy Leveling 策略具有更小的读放大（瞬态），但是查询吞吐量低，因为 Leveling 中的压缩操作消耗了超过一半原本可用于查询的 CPU 资源。

图1

本文研究问题：在面对持续不断的写入（以恒定的刷写速度）时，如何在一个压缩轮次内设计压缩策略，以最大化平均查询吞吐量。压缩的本质是通过投入计算资源和 I/O 来减少有序段的数量，从而使未来的查询可以扫描更少的有序运行。然而，这种效果是暂时的，因为新的有序段会不断生成。一次压缩在未来带来的收益，取决于它对当前查询吞吐量的提升程度以及该提升效果持续的时间。

贡献：

1. 提出将 LSM-tree 中的压缩视为一种资源投资，其目标是提升系统的平均查询吞吐量；
2. 在概念上引入了一个三层模型来理解 LSM-tree，并设计了一种动态规划算法 EcoTune，用于为不同的 LSM-tree 实例寻找最优的压缩策略；
3. 将 EcoTune 压缩策略集成到 RocksDB 中。实验结果表明，EcoTune 在不同负载下都显著优于其他方案，有效提升了 RocksDB 的平均查询性能。

3. 背景

3.1. 压缩策略

• Leveling：
  • 一层只有一个排序段，每层的大小限制是上一层的$T$倍
  • 当一层到达大小限制，该层会和下一层合并
  • 合并时会有两层数据量总和的写入，写放大较大
• Tiering：
  • 一层中可以有多个排序段，数量限制为$T-1$
  • 当一层到达数量限制，该层会合并并放到下一层
  • 读取时需要在更多排序段查找，读放大较大

不同压缩策略

3.2. 更多LSM树结构探讨

Dostoevsky(Lazy Leveling)：最下面几层是Leveling，最上面几层是Tiering

LSM‑bush：每层的排序段数量限制可以不同（文中$r_i=T^{X^{L−i−1}}$）

LSM-Bush

MOOSE：每层的大小比例、排序段数量限制等都可以配置；通过数学建模来确定最佳配置

RUSKEY：学习模型

Endure：应对不确定的工作负载，找到一个在运行前就确定的、对各种工作负载都“稳健”的配置

4. Compaction设计

4.1. 对写入性能的影响

• 现代SSD有更高写入带宽，刷新和压缩可以轻松并行化
• 实际工作负载中写入的吞吐量一般不高
• 刷新应该具有最高优先级
  • 应始终为刷新预留足够的带宽和CPU资源，其余资源用于压缩和查询
  • 一旦避免了刷新阻塞，就可以自由设计压缩策略，以提升查询性能，而无需担心写入性能

1L, 2L, 3L表示最后1,2,3层使用Leveling策略。

在两块现代SSD上，写入的平均和尾部延迟都不受压缩策略或CPU数量的影响

Type	Optane SSD			NVMe SSD
Latency	Average / 99th (μs)			Average / 99th (μs)
#Cores	4	8	16	4	8	16
1L	2.8/4.1	2.8/4.2	2.9/4.4	3.3/4.3	3.4/4.3	3.4/4.5
2L	2.8/4.2	2.8/3.9	2.9/4.3	3.4/4.2	3.4/4.5	3.5/4.8
3L	2.9/4.3	2.8/4.3	2.9/4.3	3.4/4.1	3.5/4.4	3.5/4.4

4.2. 对查询性能的影响

• 以往的研究观察最坏情况的读放大复杂度来衡量查询性能
  • 最坏情况指每层都即将填满，下次压缩会导致只剩下一个有序段
  • 该查询性能是瞬时的
  • 压缩有利于瞬时查询性能
• 应该考虑平均查询性能
  • 定义 全局压缩：在这次压缩后，所有有序段被压缩成一个
  • 定义 压缩轮次：两次全局压缩之间的时间
  • 全局压缩之后，未来的查询不受前一轮压缩策略的影响
  • 用一次压缩轮次内的平均查询吞吐量作为衡量平均查询性能的指标
• 压缩的影响
  • 减少有序段，有利于压缩后瞬时查询性能
  • 占用CPU和IO带宽，压缩时查询性能受影响，不一定利于平均查询性能
• 压缩可以看作一种投资
  • 成本：写放大
  • 即时回报：瞬时查询性能
  • 累计回报：平均查询性能

5. EcoTune算法

5.1. 查询性能分析

查询性能分析

• 使用SNARF（一种学习型的范围过滤器），4层LSM
• Bush与其他的性能差异代表合并小有序段的影响
• 1L和2L差异代表合并大有序段的影响
• 由表可知，合并不会显著提高Get/Seek/短范围查询的IO性能
• 因为过多小有序段，访问过滤器导致的CPU开销高，Bush性能较差
• 合并大有序段（1L->2L）对长扫描提升明显，而合并小一些的有序段（2L->3L）对长扫描提升不显著：
  • 长有序段中含大部分目标，压缩能有效减少访问的长有序段的数量
  • 少量短有序段含少部分目标，优于范围过滤器，压缩能减少的需要访问的短有序段的数量很少
  • 短有序段总数$d$，总大小$S$，整个LSM树大小$M$，第$i$短的有序段的大小占整个LSM树的比例为$p_{i}$，长范围扫描为(Seek + $K$Nest)
    • 第$i$个有序段一次也没被访问的概率是$(1-p_{i})^{K}$
    • 第$i$个有序段至少被访问一次的概率是$1-(1-p_{i})^{K}$
    • 短有序段的IO次数期望为$\sum_{i=1}^{d}\left( 1-(1-p_{i})^{K} \right)$
    • 因为$p_{i}$很小，可以近似为$\sum_{i=1}^{d}\left( 1-(1-K p_{i}) \right)=\sum_{i=1}^{d}\left(K p_{i}\right) = K\times \frac{S}{M}$
    • 与d无关

总结：

1. 因为CPU开销，对于小有序段的压缩不能太懒惰
2. 长范围扫描的IO开销高度依赖大有序段的数量
3. 其他类型查询的IO开销受有序段的数量影响小，对其有较强鲁棒性

5.2. 三层设计

• 最优的压缩策略在于最大化累计回报，同时最小化成本
• 压缩的影响会随着时间减弱
• 在一个轮次中越早进行压缩，未来的累计回报越大
• 因此，在轮次开始时应积极地压缩，在靠近轮次结尾时应较为懒惰一些

传统的LSM每层的多个排序段的大小都是相同的，但理想的压缩策略会导致同一层的排序段大小不一致，早期合并的结果比之后的更大一点，因此物理层级变的模糊。

多层LSM vs 3层LSM

5.2.1. 总体结构

• 设计三个逻辑层级：顶层(Top Level)，主层(Main Level)，末层(Last Level)
• 三类后台任务，可以同时进行：
  1. 从内存刷新到顶层的操作(flush)
  2. 从顶层到主层的压缩
  3. 以及主层内部的压缩

5.2.2. 顶层

顶层不做压缩，会有很多排序段。带来问题：

1. 顶层容量设置为多少？$\frac{M}{max(100, K)}$
   1. 压缩前IO次数期望：$\sum_{i=1}^{d}\left( 1-(1-p_{i})^{K} \right) = \sum_{i=1}^{d}\left( 1-(1-\frac{S}{d\times M})^{K} \right)=d(1-e^{-\frac{S\times K}{M\times d}})$
   2. 压缩后IO次数期望$1-(1-\frac{S}{M})^K=1-e^{-\frac{S\times K}{M}}$
   3. $S<\frac{M}{K}$则压缩前后IO期望都小于1，压不压缩没啥作用(?，这边感觉代价啥的算的有点问题)
   4. $S>\frac{M}{K}$则需要压缩
2. 如何处理扫描顶层的巨大CPU开销？在顶层对所有key建立索引

5.2.3. 主层

顶层填满容量后压缩成一个排序段存到主层

主层的容量设置为$\frac{末层大小}{C}$，$C$为定值

主层占总容量$\frac{1}{C+1}$，因此定义访问超过$C+1$个键的查询是长范围查询，因为这样在主层访问至少一个键的期望是大于1的

5.2.4. 末层

只存在一个排序段，主层填满容量后触发全局压缩

5.3. DP算法

每隔$T_w$时间，顶层会压缩一个大小为$S$的排序段（称作单元排序段）到主层，压缩耗时$T_c$，当$R$个单元排序段被压缩到主层后，会触发全局压缩。主层中有$e$个排序段。

假设长查询的比例是$r$，点查的假阳率是$f$。长查询顶层IO次数期望是1，主层和末层IO次数期望近似是排序段个数，查询开销期望是$(e+2)r+(1+f)(1-r)$，查询速度是代价的倒数： $$q(e) = \frac{1}{(e+2)r+(1+f)(1-r)}$$

定义分数为$查询速度\times 时间$ (?应该是查询速度对时间的积分)。

设$f(e, c)$为当前主层中有$e$个后续不进行任何压缩的排序段，且未来会有$c$个新单位排序段加入进来时最高分数，根问题为$f(0,R)$： $$f(e,c) = max_x(f(e,x) + (T_w-xT_c)\times q(e+1)+f(e+1, c-x))$$ 即确定$x$，使前$x$个单元排序段被放入主存后将这些排序段压缩成一个，且后续该排序段不参与压缩的情况能够有最高收益。

overview

上述情况是假设主层间压缩(MLC)时无法进行任何查询。如果允许该压缩的同时能够处理查询，假设压缩期间查询速度$q'(e)=\beta q(e)$，那么压缩期间的$e$依赖于之前的状态。因此加入一维$m$，在$(e,c)$之后，会有一次$(m+c)$个单元排序段大小的压缩，这段压缩的时长是$(m+c)T_c$。$(e,c)$最终会剩下的排序段数可以在$(e,c)$的最右叶子处获取。优于主层大小限制是末层的$\frac{1}{C}$，根问题为$(0,R,R\times C)$，全局压缩会得到大小为$R(C+1)$的排序段。

image-20250724172032721

(拿$m'=m+c$代换一下可能会更容易理解)

例子，蓝色表示下一次压缩得到的结果

如果还要支持$xT_c > T_w$的情况，会更加复杂。

“Due to space limitations, we do not delve deeply into this final version of EcoTune. The idea remains the same as the previous two versions. The algorithm is shown in Algorithm 2.”

EcoTune