Lethe 如何优化 LSM-Tree delete 难题

Lethe: A Tunable Delete-Aware LSM Engine 这篇论文系统地描述了标记删除给 LSM-Tree 引擎带来的问题，而现有的存储引擎很难解决大范围删除带来的问题。Lethe 通过（1）增加统计信息和 compaction 策略，优化 sort key 大范围删除带来的问题。（2）设计新的 storage layout，优化 secondary key 大范围删除带来的问题。值得一提的是 Lethe 论文中十几次引用阿里云 X-Engine 的表述和结论。

1.LSM-Tree 删除面临哪些问题

众所周知，LSM-Tree 的删除一条记录是通过追加写 tombstone 实现的，这种逻辑删除带来了如下问题：

• Read Cost 增加，范围查询需要扫描更多的记录，点查询 Bloom Filter 的 false positive rate 升高。
• 空间放大，tombstone 自己占有空间，被删除的记录没有被实际删除占有空间。作者认为 delete 带来的空间放大比 update 更严重，因为大部分场景下，key 的大小远远小于 value，占有空间很小的 delete，使多个完整的 record 失效。 即 有用字节/全部字节 更小。
• 写放大，tombstone 需要一直 compaction 到最底层才能被删除。
• 用户隐私，标记删除没有真正删除数据，有侵犯用户隐私的法律风险，欧美国家用户更加在意 privacy，中国用户未来肯定也会更加在意。

当前 LSM-Tree 引擎处理 tombstone 面临的问题：

• tombstone 存在的时长无法控制，因为 compaction 对用户来说是黑盒，决定 tombstone 存在时长的因素包括：workload 的特点和 compaction 策略设计。
• LSM-Tree 应用的场景非常广泛，包括关系数据库、流式系统、KV Store .... 一来，需要处理的 workload 特别丰富，二来，很多删除不是 User-Driven 的，用户不知道的情况下，可能发生大范围的删除，例如：数据迁移、索引删除等。
• 范围删除非 sort key 很难支持/代价很大，例如一颗 LSM-Tree 的 sort key 是 id，delete key 是 timestamp，如有需求删除时间早于 2020.11.11 日的所有 key，那么做法只能是一行行遍历所有数据，删除满足条件的行。或者删除所有的行，将不满足条件的记录重新写入。由于涉及遍历所有数据，代价非常大。

2.Lethe 如何缓解上述问题

Lethe 的两个目标：

• 保证标记删除能在 bounded 的时间内被真正删除（FADE）。
• 支持较为高效的非 Sorted Key 范围删除（KiWi）。

2.1 FADE(Fast Deletion)

2.1.1 FADE 的目标

核心思想是增加额外统计信息，指导 Compaction 策略。

其实与 FADE 类似的，识别大量 delete 并且优先 compaction 的策略，阿里巴巴 X-Engine 也做了，Lethe 做的更先进的一点是 保证 tombstone 存在的时间是 bounded 的， 即如果用户定义一个时长 D，Lethe 首先保证每个 tombstone 最多存活 D，其次尽量减少空间放大/写放大、提升吞吐。

为了保证这一点，每个文件（包含 delete）都记录了 TTL，delete 需要在 D 时长之前触及 LSM-Tree 底部。最简单的方法当然是每层每个文件的 TTL 均为 D / (L-1)，但如此，最底层和最上层的数据被 compact 的概率就相等了。显然最底层 compaction 的代价太大，应该相应增长 TTL ，假如层与层之间数据量的倍数为 T，相应地，每一层的 TTL 应该是上一层的 T 倍，既 di = di-1 * T，d0 + d1 + ... + dL = D。

为了实现上述目标，FADE 需要的元信息包括：

• 文件中最旧的 tombstone 的 timestamp a。
• 因 tombstone 而失效的记录个数估算值 b。诸如 RocksDB 等引擎，已经统计了每个文件的 num_deletes，作者给出的 b 估算的方式是：num_deletes + range delete 可能失效的记录个数（根据统计信息估计）。

可以看到需要的元信息不多，均在 flush/compaction 产生新文件时计算生成，overhead 很小。

2.1.2 FADE 策略

FADE 主要是根据上面描述的元信息，制定了一些针对 delete 的 Compaction policies。主要涉及两方面：

• Compaction 触发规则。
• 文件选择规则。

当前市面上的 LSM-Tree 引擎，大都是某一层数据量（或文件个数）饱和，触发 Compaction，一般会随机选择文件或选择与目标层 overlap 较小的文件。

FADE 的 Compaction 触发规则增加了一条：文件的 TTL 满足后，需要触发调度，即使该层还没有满。

FADE 的文件选择策略有三种模式：

• The saturation-driven trigger and overlap-driven file selection (SO)，即经典 LSM-Tree 文件选择策略，针对写放大优化。
• The saturation-driven trigger and delete-driven file selection (SD)，选择 b 值（失效估算值）最多的文件，针对空间放大优化。
• The delete-driven trigger and delete-driven file selection (DD)，选择 TTL 到期的文件。

如果两个文件在 SD / DD 模式下打成平手（即两个文件 delete 影响 entries 数量接近），则选择有更旧的 tombstone 的文件。

如果两个文件在 SO 模式下打成平手，选择 tombstone 更多的文件。

如果 level 之间打成平手，优先选择更小的 level。

总结：更加激进的 compaction delete 记录，（1）可以较快的清理无用的空间（invalid entries），有利于缓解空间放大，（2）同时可以减少后续 compaction 中 invalid entries 参与的可能，总体上是减少了写放大，（3）最后也有利于读请求（提升 BF 的过滤效率，减少范围查询的需要扫描的个数），（4）并且删除数据存在的时间被严格限定在 D。

2.2 KiWi(Key Weaving Storage Layout)

为了高效的支持非 Sort key 的 range delete，KiWi 更改了现有 SST 文件经典的 layout，引入“delete tile”，牺牲了一定查询代价，提高范围删除的效率。其整体存储架构如下：

LSM-Tree 的分层方式不变，每层文件的排列方式也不变。每个文件的组成，不再是多个 pages，而是加了一层 delete tiles 。同一个文件，delete tile 与 delete tile 之间按照 sort key 排序，delete tile 内部由 h 个 pages 组成，page 与 page 之间按 delete key 排列，page 内按 sort key 排列。

它带来的好处是：delete tile 内的 page 与 page 之间是按照 delete key 排序的，因此 delete key 范围删除可以直接移除满足条件的 page，不用读写，这个效率是非常高的。对于那些 page 里只有部分记录满足删除条件的，可以读取并重新生成 page。后续 compaction时可以回收这部分空间。这个 in-place delete 的效率是当前任何 LSM-Tree 引擎无法达到的。

它带来的代价是读请求定位到 delete tile 后，定位 page 时需要多查询判断几个 page，增加了一些 CPU 的开销，但是由于 Bloom filter 和 fence pointer 的存在，这个代价是较小的。这个设计带来的另一个好处是：在不建二级索引的情况下，可以较为高校的以delete key作为查询条件做查询。

可以通过调整 delete tile 中包含的 page 的个数 h 来调节 read performance 和 secondary range delete 之间的 tradeoff，h=1 时便退化到经典 LSM-Tree 的实现，查询性能最好。

3.实验

以上实验都是删除密集型 workload 的实验结果，这里只列一些关键的结论，更详细的实验结果和分析可以参考论文原文。

注：（1）～（5）对应 FADE，（6）～（7）对应 KiWi

（1）对比 RocksDB 空间放大更小，且 D 设的越小，空间放大越小。（A 图中 16% 指 D 设为 16%workload execution duration）。

（2）Lethe compaction 的次数更加少，因此每次 compaction 处理掉的数据更多，因为 lethe compaction 策略更加激进。

（3）上述原因，本实验里，Lethe 的写放大略高于 RocksDB（C 图）。原因是根据 delete-driven file selection (DD) 挑选文件，和下层 overlap 更大的概率更高。但运行一段时间后，写放大基本与 RocksDB 持平，原因是删除的快，invalid entries 少（F 图）。

（4）Lethe 读性能更好，尽快删除 tombstone 提高了 BF 准确度。

（5）纯写/读写混合性能接近。（G 图）

（6）h（delete tile 里 page 数目） 越大，可以直接 drop 的 page 就越多（H），删除效率更高，但查询效率更低（I）。

（7）该场景下， h = 8 时 lethe 的 IO cost 比 RocksDB 小 76%。