Enhancing LSM trees merge efficiency via coordinated sorted runs partitioning

Abstract 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.