Lethe

【SIGMOD’20】论文浏览笔记

Lethe: A Tunable Delete-Aware LSM Engine

https://dl.acm.org/doi/10.1145/3318464.3389757

简介

应用十分小的额定元数据、新的 delete-aware 压缩策略、新的存储布局

后果：反对任何用户自定义的持久性删除提早阈值，更高的写吞吐量（1.17-1.41x），更低的空间放大（2.1-9.8x），（代价是写放大进步 4%-25%）。反对 secondary delete key 上高效删除，且不需就义写性能、不需全树合并。

背景

• LSM-tree 逻辑删除的问题：（逻辑删除：插入 tombstone，使指标键的旧条目生效）

  • 空间放大：保留了物理条目，而减少了 tombstone
  • 读代价：可能读到大量生效的
  • 写放大：生效的条目被反复压缩
  • 隐衷问题：存在 unbounded delete persistence latency。
• 持久性删除提早。逻辑删除不保障持久性删除。持久性删除提早取决于零碎的设计、负载特色，这在执行期间是难以管制的，提早可能是有限的。（持久性删除提早：从插入 tombstone 到实现最底层压缩的工夫）
• 非排序键上的大范畴删除很辣手，如 sort key 是 id，删除键是工夫戳，须要全树压缩，代价微小。

Lethe

• FADE（fast deletion）：保障在无限工夫内实现持久性删除。依据蕴含的有效条目标数量、最古老 tombstone 的年龄、与其余文件重叠的范畴，对文件进行压缩排序，来决定何时对何文件进行压缩、在阈值内革除有效条目。
• KiWi（key weaving storage layout）：实现高效的 secondary range delete。引入 delete tiles 的概念。一个 delete tile 有多个页，一个文件有多个 tile。在删除键上排序 delete tile，数据页外部放弃在排序键上的有序。在页面级应用布隆过滤器，在 sort key 和删除键上设置栅栏指针，KiWi 通过从 delete tile 删除整个页面，来实现 secondary range delete，假阳性的减少是一个常量。
• Lethe 交融 FADE 和 KiWi，实现持久性删除和零碎其余性能之间，可调的均衡。

LSM

操作

• 关系数据的主键看作 key，其余视作 value。
• L 层的 LSM-tree，内存的为 Level 0，其余的常驻磁盘。Level i 的大小是 Level i-1 的 T 倍，T 称为_size ratio_。
• 缓冲插入和更新。缓冲达到最大容量后，条目排好序，造成_immutable sorted run_，写回 level 1。磁盘层缓冲达到最大容量后，归并排序到下一磁盘层。
• 合并策略。leveling：层 i- 1 的每个 run，与层 i 的 run 进行归并排序。tiering：每层积攒到 T 个 run 才归并排序。归并时，整合键匹配的条目，只保留最近的无效条目。近来的混合合并策略交融这两者，以实现读写吞吐的均衡。
• 局部合并。有的引擎把 run 组织成小文件，在小文件粒度上而非 level 上合并。
• 查问 LSM-tree。从内存到小的磁盘层到大的磁盘层。对 tiering 的，从最近的开始。
• 优化查问。应用布隆过滤器和栅栏指针优化查问。栅栏指针在内存中存储每个磁盘页最小的关键字。

删除

LSM 利用宽泛。LSM 删除不肯定是由用户触发的，也有可能是数据迁徙、running window 的流操作等。

secondary range delete：range deletion in a delete key other than the sort key