Reducing Write Amplification in LSM-Trees Through Orchestrated Fine-Grained Compaction and Persistent Memory

This paper investigates how to leverage emerging non-volatile memory (NVM) to enhance the performance of Log-Structure Merge (LSM) tree based key-value (KV) stores. We propose KVFG-DB, which efficiently integrates fine-block granularity and single-NVM-level compaction, to deliver high write and read performance with minimal write amplification and reduced write stalls. KVFG-DB leverages a streamlined SSTable layout called CSSTable to manage data blocks (each containing ordered KV pairs) and their indexes (i.e., the minimal and maximal keys of every block), optimizing both storage costs and compaction performance. It organizes the LSM-tree data as CSSTables into a single level on NVM, with the left area serving as a buffer to receive flushed data with substantially greater capacity, and the right area storing compacted data in a global order among CSSTables. A fine-grained compaction is then performed under various conditions to select the most relevant data blocks with intersecting keys from CSSTables in both areas, facilitating byte-addressable, fast parallel execution across multiple threads. As a result, KVFG-DB adaptively compacts data and quickly moves them from the left area to the right area to enhance performance efficiency, significantly reducing write amplification and further mitigating write stalls. Our extensive experimental studies demonstrate that KVFG-DB achieves 1.2× and 2× lower write amplification, compared with state-of-the-art KV stores MioDB and SLM-DB. Accordingly, KVFG-DB shows a 1.1× and 7.1× improvement in random write performance compared to them, with tail latency reduced by 1.1× and 7×, respectively.