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. 顶层