可调删除感知LSM引擎

现代数据系统需要处理由各种应用程序生成的海量数据。为了支持这一要求，现代数据存储通过采用不合适的范例来减少读/写干扰。经典的错位设计是日志结构合并(LSM)树。LSM-Trees将传入的键值条目写入内存缓冲区以确保高写入吞吐量，并使用内存中的辅助数据结构(如布隆过滤器和栅栏指针)来提供具有竞争力的读取性能。虽然LSM通常非常适合写入和读取，但是我们展示了所有最先进的基于LSM的数据存储在工作负载中的存在删除中的性能都是次优的。LSM树中的删除在逻辑上是通过插入特殊类型的键值条目(称为墓碑)来实现的。一旦插入，墓碑就在逻辑上使具有匹配键的树中的所有条目无效，而不必干扰物理目标数据条目。只有在相应的墓碑通过压缩到达树的最后一层之后，才从数据存储中持久地删除目标条目。持久删除目标条目所花费的时间取决于(I)紧凑例程遵循的文件挑选策略，(Ii)向数据库摄取条目的速率，(Iii)LSM树的大小比率，以及(Iv)树中的级别数量。