PartitionKV: Redesigning LSM-tree KV Stores on NVMs with Adaptive Partitioning for Reducing Write Stalls and Amplification

In write-intensive applications, the log-structured merge (LSM) trees are widely used as the basic index structure of key-value (KV) stores. Existing works integrate NVM into traditional DRAM-SSD architecture to improve write performance. However, these works still suffer from significant write stalls and amplification, mainly due to the inefficient L 0 - L 1 compaction caused by the unordered nature of data in L 0 of LSM-trees. To address these issues, we propose PartitionKV, a novel LSM-tree based KV store designed for the DRAM-NVM-SSD storage architecture, which has three main design characteristics: (1) First, we design an ordered partition layer comprising multiple partitions to replace the Memtable components and L 0 of original LSM-trees. Incoming KVs are directly persisted into NVM Logs of designated partitions based upon keys. This design minimizes unnecessary data rewriting during compaction and can double as a write-ahead log, significantly reducing write amplification. (2) Second, we introduce an adaptive partitioning strategy that dynamically splits or merges partitions based on the number of overlapping SSTables, ensuring that an optimal amount of data is involved in each compaction. (3) Third, we propose a multithreaded compaction strategy where multiple threads leverage two priority lists to efficiently coordinate concurrent data compaction between the partition layer and L 1 . By effectively integrating these two strategies, PartitionKV accelerates NVM space release and reduces write stalls significantly. We implement PartitionKV based on RocksDB and conduct extensive experiments to evaluate its performance. Results show that PartitionKV achieves 3.63× and 4.06× higher random write throughput than FlatLSM and MatrixKV, respectively.