Lethe: A Tunable Delete-Aware LSM Engine
Lethe: A Tunable Delete-Aware LSM Engine
复制标题
DOI：
10.1145/3318464.3389757
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Subhadeep Sarkar;Tarikul Islam Papon;Dimitris Staratzis;Manos Athanassoulis
中科院分区：
文献类型：
--
作者：
Subhadeep Sarkar;Tarikul Islam Papon;Dimitris Staratzis;Manos Athanassoulis
数据密集型应用程序推动了基于日志结构化合并（LSM）的键值引擎的发展，这些引擎采用了不适当的范例来支持高摄取率和低读/写干扰。然而，这些好处的代价是将删除视为二等公民。删除操作会插入一个逻辑删除，使已删除键的较旧实例无效。最先进的LSM引擎不保证墓碑将以多快的速度传播以持久化删除。此外，LSM引擎只支持删除排序键。删除另一个属性（例如，时间戳），整个树被读取和重写。我们强调，在不影响读取性能的情况下快速持久删除是支持以下内容的关键：（i）在数据窗口上运行的流式传输系统，（ii）对被遗忘权的隐私延迟保证，以及（iii）使存储成为宝贵资源的数据系统的云部署。为了解决这些挑战，在本文中，我们建立了一个新的键值存储引擎，Lethe，它使用了非常少量的额外的元数据，一组新的删除感知压缩策略，以及一个新的物理数据布局，编织排序和删除键顺序。我们表明，Lethe支持任何用户定义的删除持久性延迟阈值，提供更高的读取吞吐量（1.17- 1.4倍）和更低的空间放大（2.1- 9.8倍），写入放大适度增加（4%至25%）。此外，Lethe通过丢弃整个数据页而不牺牲读取性能，也不使用昂贵的全树合并，支持在辅助删除键上进行有效的范围删除。
Data-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource. To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17-1.4x) and lower space amplification (2.1-9.8x), with a modest increase in write amplification (between 4% and 25%). In addition, Lethe supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance nor employing a costly full tree merge.