[VLDB'21] Constructing and Analyzing the LSM Compaction Design Space 论文阅读
#1. 引言
基于日志布局合并 (LSM) 的键值存储 LSM 树如今被广泛用作现代 NoSQL 键值存储的存储层. LSM 树采用 out-of-place 范式来实现快速数据写入. 传入的键值对被缓冲在主存中, 并定期刷新到持久存储中, 形成 sorted immutable runs. 随着磁盘上 run 数量的增加, 它们会被排序合并, 从而构建更少但更长的 sorted runs. 这个过程被称为 Compaction. 为了便于快速查询, LSM 树使用辅助的内存数据结构 (Bloom Filter 和 Fence Pointer) 辅助减少每次查询执行的平均磁盘 I/O 次数. 由于这些优势, LSM 树被多个生产级键值存储系统采用, 包括 Google 的 LevelDB 和 BigTable、Facebook 的 RocksDB、阿里巴巴的 X-Engine、MongoDB 的 WiredTiger、Cockroach Labs 的 CockroachDB、LinkedIn 的 Voldemort、Amazon 的 DynamoDB、Apache 的 AsterixDB、Cassandra、HBase、Accumulo 以及 Yahoo 的 bLSM 和 cLSM. 基于 LSM 树的学术系统包括 Monkey、SlimDB、Dostoevsky、LSM-Bush、Lethe、Silk、LSbM-tree、SifrDB 和 Leaper.
LSM 树中的 Compaction LSM 树中的 Compaction 操作被定期执行以 通过写放大来减少读放大和空间放大 , 同时确保数据一致性和查询正确性. Compaction 操作会将一个或多个层之间的两个或多个 sorted run 合并, 以确保 LSM 树的层大小呈指数级增长. Compaction 操作通常在某个层达到其容量上限时触发, 此时 Compaction 例程会将数据从已饱和层移动到容量呈指数级增长的下一层. 在 Compaction 过程中, 任何重复条目 (由更新导致) 和失效条目 (由删除导致) 都会被移除, 仅保留逻辑上正确的 (最新的有效) 版本. Compaction 操作决定了磁盘驻留数据的重整方式和时间, 从而影响磁盘上的物理数据布局. 图 1(a) 定性地展示了当前 SOTA 的 LSM 引擎中采用的各种 Compaction 策略的性能影响.
图 1: (a) SOTA 的 LSM-Engine 采用的不同压缩策略导致了性能的差异；(b) 根据设计基本要素对 LSM 压缩进行分类。
挑战: 如何选择合适的 Compaction 策略 尽管 Compaction 对于 LSM 引擎的性能至关重要, 但选择合适的 Compaction 策略需要人为干预. 实际上, 在基于 LSM 的生产数据存储中, “如何 (重新) 组织磁盘上的数据”, 以及"实施或使用哪些 Compaction 策略", 通常取决于工程师或数据库管理员 (DBA) 的专业知识. 这主要是由于两个原因. 首先, LSM 树中的 Compaction 过程通常是黑盒而且不会被暴露为一个可调旋钮. 尽管 LSM Compaction 设计空间巨大, 但由于缺乏正式的 Compaction 模板, 导致严重依赖个人经验, 使得很大一部分设计空间未被探索. 其次, 缺乏关于 Compaction 如何影响 LSM 引擎性能的分析和实验数据, 尤其是在存储引擎底层设计和工作负载特性的背景下.
因此, 即使是专家也很难回答以下设计问题:
我的 LSM 引擎提供的写入性能低于预期: 改变 Compaction 策略是否会有帮助? 如果有帮助, 应该采用哪些策略?
我们过去处理的 Workload 发生了变化: 这如何影响我们系统的读取吞吐量吗? 是否存在可以提高读取吞吐量的 Compaction 策略?
我们计划设计一种新的 LSM 引擎来处理特定工作负载: 为了获得最佳整体性能, 我应该如何 Compaction 数据? 是否存在我必须避免的 Compaction 策略?
依靠人工经验为每个应用程序手动选择合适的 Compaction 策略是不可扩展的, 尤其是在大规模系统部署中. 为此, 本文形式化了基于 LSM 的存储引擎中 Compaction 的设计空间. 此外, 我们通过实验探索了该空间, 并在此基础上提出了 7 个高级要点和 12 个观察结果, 这些内容构成了一套全面的 LSM Compaction 指南, 并为 Compaction 调优和自动化奠定了基础.
#2. 背景
LSM 基础知识 为了支持快速数据摄取, LSM 树会将传入的 inserts、updates 和 deletes 操作 (即一般意义上的数据摄取) 缓冲在主存中. 一旦内存缓冲区满, 其中的条目将按键进行排序, 然后将缓冲区作为一个 sorted run 刷到树的磁盘部分. sorted run 是指一个或多个大小通常相同的 immutable 文件的集合. 对于具有 L 层的 LSM 树, 我们假设其第一层 L(0) 是内存缓冲区, 其余层 (L(1) 到 L(L-1)) 驻留在磁盘上. 在磁盘上, L(i) (i > 1) 层的容量比第 L(i-1) 层大 T 倍, 其中 T 是树的大小比例.
LSM Compaction 为了限制磁盘上 sorted run 的数量 (从而加快查询速度并提高空间利用率), LSM 树会定期将 L(i) 的 run (或 run 的一部分) 与 L(i+1) 中重叠的 run 进行排序合并. 这种数据重整过程, 即在磁盘上创建更少、更长的 sorted run, 被称为 Compaction. 然而, 数据排序合并过程需要在磁盘和主存之间来回移动数据. 这会导致写放大, 在 SOTA 的基于 LSM 的数据存储中, 写放大倍数可能高达 40 倍.
Partial Compaction 为了分摊文件选择成本, 从而避免延迟峰值, SOTA 的 LSM 引擎会将数据组织成更小的文件, 并以文件为单位而非以层为单位执行 Compaction. 如果 L(i) 的数据增长超过阈值, 则会触发 Compaction, 并从 L(i) 中选择一个文件 (或文件子集) 与 L(i+1) 中具有重叠键范围的文件进行 Compaction. 此过程称为 Partial Compaction. 图 2 展示了 LSM 树中完全 Compaction 和 Partial Compaction 例程的对比图.
图 2: (a) 调用时, 经典的 Full Compaction 过程一次压缩整个 Level, 而 (b) Partial Compaction 以文件为粒度执行压缩。
查询 LSM 树 由于 LSM 树以 out-of-place 方式进行更新和删除, 因此树中可能存在多个具有相同键的条目, 但只有最新版本有效.
点查询 点查询从内存缓冲区开始, 从最小层到最大层遍历树, 并在同一层内从最新 run 到最旧 run 遍历. 找到匹配的键后, 查询立即终止. SOTA 的 LSM 引擎使用内存数据结构, 例如 Bloom Filter 和 Fence Pointer 限制查询探测的 run 次数.
范围扫描 范围扫描需要对树所有层中符合范围查询条件的 run 进行排序合并. 这些 run 在内存中进行排序合并, 并返回每个符合条件的条目的最新版本, 同时丢弃所有较旧的、逻辑上无效的版本.
LSM 树中的删除操作 点删除操作通过插入一种特殊的键值对条目 (称为 Tombstone) 来实现, 该条目在逻辑上使目标条目失效, 但并不实际影响它们. 在 Compaction 过程中, Tombstone 会清除所有具有匹配键的旧条目. 当相应的 Tombstone 到达树的最后一个层时, 删除操作最终被视为持久删除, 此时可以安全地删除该 Tombstone. 从基于 LSM 的数据存储中持久删除数据对象所需的时间取决于数据重整过程. 因此, Compaction 在及时持久地删除条目方面也发挥着至关重要的作用, 尤其是在新的数据隐私法规出台的背景下.
#3. Compaction 设计空间
#3.1. Compaction 基本要素
我们将 Compaction 策略定义为设计基本要素的集合. 它代表了关于物理数据布局和数据 (重) 组织策略的基本决策. 每个基本要素都回答了一个基本的设计问题.
- Compaction 触发条件: 何时需要进行数据重整?
- 数据布局: 如何在存储设备上进行数据物理布局?
- Compaction 粒度: 在布局重整期间一次需要移动多少数据?
- 数据迁移策略: 重整过程中需要迁移哪些数据块?
这些设计基本要素共同定义了 LSM 引擎何时以及如何重整持久介质上的数据布局. 所提出的基本要素涵盖了所有 SOTA 的 LSM Compaction 策略, 并且能够合成新的或未探索过的 Compaction 策略.
图 3: 定义 LSM 压缩的基本要素: 触发器、数据布局、粒度和文件选择策略。
#3.1.1 Compaction 触发条件
Compaction 触发条件是指可以启动 Compaction 作业的一系列事件. 最常见的 Compaction 触发条件是基于 LSM 树中某一层的 Saturation. L(i) 的 Saturation 通常以 L(i) 存储的数据字节数与该层理论容量 (以字节为单位) 的比值来衡量. 一旦 Saturation 超过预定义的阈值, L(i) 中的一个或多个 immutable 文件将被标记为待 Compaction. 一些 LSM 引擎使用层中的文件数量来计算 Saturation. 需要注意的是, 基于文件数量的 Saturation 计算方法仅在所有 immutable 文件大小相等, 或者系统文件大小可调的情况下才有效. 基于 “sorted runs” 的触发条件如果一个层中的 sorted runs (或 “tiers”) 的数量超过预定义的阈值, 则触发 Compaction, 而不管层的大小如何.
其他 Compaction 触发因素包括 文件 staleness、基于 Tombstone 的 TTL 以及 空间和读放大. 例如, 为了确保更新和删除操作能够传播到树的更深层, 一些 LSM 引擎会在创建每个文件时为其分配一个 TTL. 每个文件可以在一个层中存活一段有限的时间, 一旦 TTL 到期, 该文件就会被标记为需要 Compaction. 另一个由删除操作驱动的 Compaction 触发条件确保一些 LSM 引擎会在 LSM 树中创建文件时, 通过不同的基于时间戳的方案, 为每个文件分配一个 TTL, 以限制删除操作的持久性延迟. 每个包含至少一个 Tombstone 标记的文件, 在每个层中都会被分配一个特殊的 TTL, 一旦该计时器到期, 文件就会被标记为待 Compaction. 下面, 我们列出最常见的 Compaction 触发条件:
- Level Saturation(LS): 层大小超过标称阈值
- Sorted Runs 数量(SR): 某一层的 sorted runs 次数达到阈值
- File Staleness(FS): 文件在某一层停留时间过长
- 空间放大(SA): 总空间放大超过阈值
- Tombstone-TTL(TTL): 存在 Tombstone TTL 过期
#3.1.2 数据布局
数据布局由 Compaction 急迫程度决定, 并通过控制每个层的 sorted runs 个数来决定磁盘上的数据组织方式. Compaction 操作会在存储和内存之间移动数据, 消耗大量的设备带宽. 因此, 摄入数据 (外部) 和 Compaction (内部) 之间存在着对设备带宽的固有竞争 – 这种权衡取决于 Compaction 优先级.
数据布局通常分为 Leveling 布局和 Tiering 布局.
- Leveling 布局中, 一旦 L(i) 触发 Compaction, 标记为 Compaction 的文件将与 L(i+1)中重叠的文件合并, 并将结果写回 L(i+1). 因此, L(i+1)最终会得到一个更长的、sorted、immutable 的文件序列.
- Tiering 布局中, 每一层可以包含多个具有重叠键域的 sorted run. 一旦 L(i) 触发 Compaction, L(i) 中所有 sorted run 将合并在一起, 并将结果作为一个新的 sorted run 写入 L(i+1), 而不会影响该层中已有的序列.
Dostoevsky 提出了一种混合设计, 其中最后一层采用 Leveling 布局, 其余磁盘层均采用 Tiering 布局. 文献 [24, 37] 对此思想进行了推广, 提出了一种连续体设计方案, 允许每一层单独决定采用 Tiering 布局还是 Leveling 布局. 在生产系统中, RocksDB 的 L1 采用 Tiering 布局, 并允许其持续增长, 以避免在数据摄取密集型工作负载中出现 Write-Stall.
以下列出了数据布局中最常见的几种选项:
- Leveling: 每层一个 sorted run
- Tiering: 每层多个 sorted run
- First-Leveling: 第一层采用 Tiering, 其余层采用 Leveling
- Last-Leveling: 最后一层采用 Leveling, 其余层采用 Tiering
- Hybrid: 一个层既可以是 Tiering, 也可以是 Leveling
#3.1.3 Compaction 粒度
Compaction 粒度是指单次 Compaction 作业期间移动的数据量. 一种 Compaction 数据的方法是对数据进行排序合并, 并将所有数据从一个层移动到下一个层 – 称为 Full Compaction. 这会导致在 Compaction 过程中由于大量文件选择而出现周期性的 I/O Burst, 并且随着树的深度增加, 延迟峰值会加剧, 导致长时间的 Write-Stall.
为了分摊 Compaction 带来的 I/O 开销, 基于 Tiering 的 LSM 的引擎采用了 Partial Compaction, 其中每次 Compaction 只涉及较小粒度的数据, 而不是移动整个层. 数据粒度可以是单文件或多文件, 具体取决于系统设计和工作负载. 需要注意的是, Partial Compaction 并不会从根本上改变 Compaction 导致的文件选择总量, 而是将这些文件选择均匀地分摊到时间上, 从而防止出现不必要的 Latency Spike.
针对 sorted runs 的 Compaction 粒度主要适用于采用惰性合并策略的 LSM. 一旦在 L(i) 触发 Compaction, L(i) 中的所有 sorted runs (或层) 将被 Compaction 在一起, 并将生成的条目写入 L(i+1), 作为一个新的 immutable sorted runs.
下面, 我们列出最常见的 Compaction 粒度:
- Level(L): 两个连续层中的所有数据
- Sorted Runs(SR): 某一层中的所有 sorted runs
- Sorted File(F): 一次处理一个 Sorted file
- 多个 Sorted File(Fs): 一次处理多个 Sorted file.
#3.1.4 文件选择策略
当 Partial Compaction 启动后, 文件选择策略会选择要 Compaction 的文件.
一种简单的选择文件的方式是随机选择或使用 Round-robin 策略, 并不专注于优化任何特定的性能指标, 而是有助于减少空间放大. 为了优化读取吞吐量, 许多生产数据存储会在触发 Compaction 时选择当前层中最冷的文件. 另一个常见的优化目标是最小化写放大. 在这种策略中, 与目标层重叠最少的文件会被标记为 Compaction 文件. 为了减少空间放大, 一些存储引擎会选择 Tombstone 标记和/或更新次数最多的文件. 另一种考虑删除操作的方法引入了一种基于 Tombstone 标记年龄的文件选择策略, 旨在及时持久化逻辑删除.
下面, 我们列出了常见的文件选择策略:
- Round-Robin(RR): 以 RR 方式选择文件
- 重叠最少的父文件(+1): 与父文件重叠最少的文件
- 重叠最少的祖父文件(+2): 与父文件重叠最少的文件, 但与祖父文件重叠最少
- 最冷文件©: 最近最少访问的文件.
- 最旧文件(O): 一层中最旧的文件
- Tombstone 密度(TD): Tombstone 数量超过阈值的文件
- Tombstone TTL(TTL): 存在 Tombstone TTL 过期的文件
#3.2 Compaction 作为基本要素集合
每种 Compaction 策略都接受四个基本要素中的一个或多个值. 触发条件、粒度和文件选择策略是多值基本要素, 而数据布局是单值基本要素.
例如, 一种常见的 LSM 设计采用 Leveled 布局 (数据布局), 一旦某个层达到标称大小 (触发条件) , 就会一次性 Compaction 整个层 (粒度). 这种设计没有实现许多精细的优化, 例如 Partial Compaction, 因此根据定义, 它不需要文件选择策略.
一个更复杂的例子是 Leveled LSM 树 (数据布局) 的 Compaction 策略, 其中 Compaction 以文件为粒度执行. 如果满足以下任一条件, 则会触发 Compaction:
- 某个层达到其容量
- 包含 Tombstone 的文件在某个层中保留的时间超过预设的 TTL
一旦触发, 文件选择策略会选择:
- Tombstone 密度最高的文件
- 否则, 与父层重叠最少的文件
Compaction 设计空间大小 如果两种 Compaction 策略在四个基本要素中的至少一个上存在差异, 则认为它们彼此不同. 即使仅在一个基本要素上存在差异, 在相同的硬件上运行并承受相同的工作负载时, 它们的性能也可能截然不同. 代入一些典型的基本要素基数值, 我们估计 Compaction 策略的基数大于 10 种, 这是一个庞大但尚未被充分探索的设计空间. 表 1 展示了该空间的一个代表性部分, 详细列出了二十多个学术和生产系统中使用的 Compaction 策略.
Compaction 策略分析 为了进行分析和实验, 我们选择了十种在生产和学术界基于 LSM 的系统中普遍存在的具有代表性的 Compaction 策略. 我们在表 2 中对这些候选 Compaction 策略进行了编码和展示.
- Full 表示 Tiering LSM 树的 Compaction 策略, 该策略在调用时 Compaction 整个层.
- +1 和 +2 表示两个 Partial Compaction 例程, 分别选择与父层 (i+1) 和祖父层 (i+2) 中的文件重叠最小的文件进行 Compaction.
- RR 以 Round-robin 方式从每个层中选择文件进行 Compaction.
- Cold 和 Old 是读友好策略, 分别标记层中最冷和最旧的文件进行 Compaction.
- TSD 和 TSA 是删除驱动的 Compaction 策略, 其触发条件和文件选择策略分别由 Tombstone 密度和文件中包含的最旧 Tombstone 的年龄决定.
- Tier 表示 Tiering 数据布局的一种变体, 其中当 (a) 层中 sorted run 数量或 (b) 树中估计的空间放大达到特定阈值时, 将触发 Compaction. 这种 Tiering 解释在 RocksDB 等系统中也被称为 Universal Compaction.
- 1-Lvl 表示一种混合数据布局, 其中第一磁盘层采用 Tiering 布局, 而其他磁盘层采用 Leveling 布局. 这是 RocksDB 的默认数据布局.
表 1: SOTA 系统中的压缩策略 [L 表示采用 Leveling 结构的层级; T 表示采用 Tiering 结构的层级]
| Database | 数据布局 | 触发条件 | 粒度 | 文件选择 |
|---|---|---|---|---|
| RocksDB, Monkey | (1-)Level | LS, FS | F, Fs | +1, C, O, TD |
| Tiering | SR, SA, TTL | SR | NA | |
| LevelDB, Monkey(J.) | Level | LS | F | RR, +1, +2 |
| SlimDB | Tiering | LS | F, Fs | NA |
| Dostoevsky | L-level | LS(L), SR(T) | L(L), SR(T) | +1(L), NA(T) |
| LSM-Bush | Hybrid | LS(L), SR(T) | L(L), SR(T) | +1(L), NA(T) |
| Lethe | Level | LS, TTL | F, Fs | +1, TTL |
| Silk, Silk+ | Level | LS | F, Fs | RR |
| HyperLevelDB | Level | LS | F | RR, +1, +2 |
| PebblesDB | Hybrid | LS | F, Fs | NA |
| Cassandra | Tiering | SR, FS, TTL | SR | NA |
| Level | LS, TTL | F, Fs | +1, TD, TTL | |
| WiredTiger | Level | LS | L | NA |
| X-Engine, Leaper | Hybrid | LS | F, Fs | +1, TD |
| HBase | Tiering | SR | SR | NA |
| AsterixDB | Level | LS | L | NA |
| Tiering | SR | SR | NA | |
| Tarantool | L-level | LS(L), SR(T) | L(L), SR(T) | NA |
| ScyllaDB | Tiering | SR, FS, TTL | SR | NA |
| Level | LS, TTL | F, Fs | +1, TD, TTL | |
| bLSM, cLSM | Level | LS | F | RR |
| Accumulo | Tiering | LS, SR, TTL | SR | NA |
| LsbM-tree | Level | LS | L | NA |
| SifrDB | Tiering | LS | Fs | NA |