TriangleKV: Reducing Write Stalls and Write Amplification in LSM-Tree Based KV Stores With Triangle Container in NVM

Abstract

Popular LSM-tree based key-value stores suffer from suboptimal and unpredictable performance due to write amplification and write stalls that cause application performance to periodically drop to nearly zero. Our preliminary experimental studies reveal that (1) write stalls mainly stem from the significantly large amount of data involved in each compaction between <inline-formula><tex-math notation="LaTeX">$L_{0}$</tex-math></inline-formula> - <inline-formula><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> (i.e., the first two levels of LSM-tree), and (2) write amplification increases with the depth of LSM-trees. Existing work mainly focus on reducing write amplification, while only a couple of them target mitigating write stalls. In this paper, we exploit unique features of non-volatile memory (NVM) to address these two limitations and propose TriangleKV, a new LSM-tree based persistent KV store with multi-tier DRAM-NVM-SSD storage. TriangleKV's design principles include performing smaller and cheaper <inline-formula><tex-math notation="LaTeX">$L_{0}$</tex-math></inline-formula> - <inline-formula><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> compaction to reduce write stalls while reducing the depth of LSM-trees to mitigate write amplification. To this end, four novel techniques are proposed. First, we relocate and manage the <inline-formula><tex-math notation="LaTeX">$L_{0}$</tex-math></inline-formula> level in NVM with our proposed <i>triangle container</i> . Second, the new <i>right-angle side compaction</i> is devised to compact <inline-formula><tex-math notation="LaTeX">$L_{0}$</tex-math></inline-formula> to <inline-formula><tex-math notation="LaTeX">$L_{1}$</tex-math></inline-formula> at fine-grained key ranges, thus substantially reducing the amount of compaction data. Third, TriangleKV increases the width of each level to decrease the depth of LSM-trees thus mitigating write amplification. Finally, the <i>cross-row hint search</i> is introduced for the triangle container to keep adequate read performance. We implement TriangleKV based on MatrixKV and evaluate it on a hybrid DRAM/NVM/SSD system using Intel's latest 3D Xpoint NVM device Optane DC PMM. Evaluation results show that, with the same amount of NVM, TriangleKV outperforms RocksDB, NoveLSM and MatrixKV in 99th-percentile latencies by <inline-formula><tex-math notation="LaTeX">$5.5\times$</tex-math></inline-formula> , <inline-formula><tex-math notation="LaTeX">$2.1\times$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$1.1\times$</tex-math></inline-formula> , and random write throughput by <inline-formula><tex-math notation="LaTeX">$4.9\times$</tex-math></inline-formula> , <inline-formula><tex-math notation="LaTeX">$3.5\times$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$1.4\times$</tex-math></inline-formula> respectively.