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