<p>The efficiency of LSM-tree-based systems is critically dependent on the chosen compaction strategy, broadly categorized into leveled and stack-based strategies. Leveled compaction is beneficial due to its ability to break down larger compactions into more manageable, smaller sub-compactions via partitioning, thereby enhancing parallelism, reducing write stalling, and increasing disk utilization. Particularly for sequential insertions, it enables the transfer of whole files to lower levels without necessitating rewrites, referred to as trivial moves, a capability typically absent in stack-based strategies. These strategies often resort to no or simplistic partitioning techniques, limiting parallelism and the feasibility of trivial moves. This work introduces a hybrid strategy aiming to integrate the best features of both compaction strategies. We introduce two innovative coordinated partitioning algorithms, <i>Local-Range</i> and <i>Global-Range</i>, designed to apply to any stack-based strategy. These algorithms aim to boost parallelism in compactions and facilitate trivial moves, thus reducing the overall compaction costs. By extending RocksDB to incorporate partitioning for stack-based strategies and conducting a comparative analysis with various baselines across different workloads, we demonstrate that the Global-Range partitioning notably improves compaction performance with minimal added overhead.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Enhancing LSM trees merge efficiency via coordinated sorted runs partitioning

  • Qizhong Mao,
  • Vagelis Hristidis

摘要

The efficiency of LSM-tree-based systems is critically dependent on the chosen compaction strategy, broadly categorized into leveled and stack-based strategies. Leveled compaction is beneficial due to its ability to break down larger compactions into more manageable, smaller sub-compactions via partitioning, thereby enhancing parallelism, reducing write stalling, and increasing disk utilization. Particularly for sequential insertions, it enables the transfer of whole files to lower levels without necessitating rewrites, referred to as trivial moves, a capability typically absent in stack-based strategies. These strategies often resort to no or simplistic partitioning techniques, limiting parallelism and the feasibility of trivial moves. This work introduces a hybrid strategy aiming to integrate the best features of both compaction strategies. We introduce two innovative coordinated partitioning algorithms, Local-Range and Global-Range, designed to apply to any stack-based strategy. These algorithms aim to boost parallelism in compactions and facilitate trivial moves, thus reducing the overall compaction costs. By extending RocksDB to incorporate partitioning for stack-based strategies and conducting a comparative analysis with various baselines across different workloads, we demonstrate that the Global-Range partitioning notably improves compaction performance with minimal added overhead.