不要忘记删除范围! 通过更兼容的查找和删除增强基于 LSM 的密钥价值商店
LSM-trees的特点是异地更新,其中密钥删除通过插入墓碑来标记其陈腐性而不是将其移除到位来处理。 这将实际移除推迟到压实,并大大减少了开销。 然而,这种经典策略与另一个基本操作符范围删除作斗争,该删除在指定范围内删除所有密钥,要求系统插入许多墓碑并造成严重的性能问题。 为了解决这个问题,现代LSM系统引入了记录开始和结束键的范围墓碑,以避免每个关键墓碑。 虽然这实现了令人印象深刻的范围删除效率,但这样的解决方案与查找不兼容。 特别是,我们的实验表明,点查找延迟可以增加30%,即使工作负载中仅删除1%的范围。 令我们惊讶的是,这个问题以前没有提出过,尽管范围墓碑解决方案已经使用了五年多。 为了解决这一关键性能问题,我们提出了GLORAN,这是一种高效的范围删除方法,可以集成到现代基于LSM的系统中,并在不影响点查找效率的情况下提供理想的范围删除性能。 它引入了一个全局索引,允许点查找快速定位相关范围,而无需检索许多不相关的元素,将I/O复杂度从O(N/λ)降低到O(log^2 N/(λF)或O(φlogN/F),其中1/λ是范围删除的比例,并且φ是LSM-trees中Bloom过滤器的FPR。 此外,我们设计了一个入口有效性估算器,以进一步提高O(εlog^2 N/(λF))的预期I/O成本,用于查找现有密钥。 广泛的评估表明,与SOTA方法相比,GLORAN始终优于基线,同时实现高达10.6倍的点查找和2.7倍的整体吞吐量。
数据库