Increase Merge Efficiency in LSM Trees Through Coordinated Partitioning of Sorted Runs
Increase Merge Efficiency in LSM Trees Through Coordinated Partitioning of Sorted Runs
复制标题
DOI：
10.1109/bigdata59044.2023.10386222
复制
发表时间：
2023-12
期刊：
影响因子：
--
通讯作者：
Qizhong Mao;Vagelis Hristidis
中科院分区：
文献类型：
--
作者：
Qizhong Mao;Vagelis Hristidis
基于LSM树的系统的性能在很大程度上依赖于所采用的压缩策略。存在两种主要的压缩策略类别：分层和基于堆栈。水平压实具有几个优点。首先，它的增量合并风格可以通过分区将大的压缩分解为更小的子压缩。这种分区增强了压缩执行过程中的并行性，减少了写入延迟，并提高了磁盘利用率。此外，对于特定的工作负载，如顺序插入，它允许将整个文件移动到较低的级别，而无需重写它们，从而节省磁盘I/O。这些移动被称为琐碎移动。另一方面，基于堆栈的策略通常缺乏对这些所需属性的支持。他们的大型压缩要么不执行分区或依赖于天真的分区方法，导致有限的机会，并行和平凡的moves.The本文的目标是促进压缩的优势，分层策略在基于堆栈的系统，从而创建一个混合策略，结合了这两个世界的优势。为了实现这一点，我们提出了两个新的协调分区算法，即局部范围和全局范围。这些算法可以应用于任何基于堆栈的压缩策略，以增强压缩过程中的并行性，并为琐碎的移动创造更多的机会，从而提高整体压缩成本。我们扩展RocksDB以支持基于堆栈的策略的分区，并使用各种工作负载对几个基线进行比较分析。实验结果表明，全局范围划分方法显着提高压缩性能，以最小的开销。
The performance of an LSM-tree-based system heavily relies on the compaction strategy employed. Two main categories of compaction strategies exist: leveled and stack-based. Leveled compaction offers several advantages. Firstly, its incremental merge style enables breaking down large compactions into smaller sub-compactions through partitioning. This partitioning enhances parallelism during compaction execution, reduces write stalling, and improves disk utilization. Additionally, for specific workloads like sequential insertions, it allows moving entire files to lower levels without the need for rewriting them, thus saving disk I/O. These moves are known as trivial-moves. On the other hand, stack-based policies typically lack support for these desired properties. Their large compactions either perform no partitioning or rely on naive partitioning methods, resulting in limited opportunities for parallelism and trivial-moves.The goal of this paper is to facilitate the compaction advantages of leveled strategies in stack-based systems, hence creating a hybrid strategy that combines the advantages of both worlds. To achieve this, we propose two novel coordinated partitioning algorithms, namely Local-Range and Global-Range. These algorithms can be applied to any stack-based compaction strategy to enhance parallelism during compactions and create more opportunities for trivial-moves, resulting in improved overall compaction cost. We extend RocksDB to support partitioning on stack-based strategies and conduct a comparative analysis against several baselines using various workloads. The experimental results demonstrate that the Global-Range partitioning method significantly enhances compaction performance with minimal overhead.