MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores

on YouTube ↗21m

" summary

MatrixKV implements a matrix container in NVM (Optane DC PMM) inside RocksDB, adds column compaction and cross-row hint search, and flattens levels to cut write amplification. It reduces each L0→L1 compaction to about 33 MB compaction (vs ~3.1 GB in RocksDB and 15 GB in NoveLSM), lowers write amplification by ~3.4×, and delivers 3.6×/2.6× higher random write throughput and 5×/1.9× lower 99th‑percentile latency compared to RocksDB and NoveLSM.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:31Outline
3. 1:56Challenge 1: Write stall
4. 3:29Root cause of write stall: LO-L1 compaction
5. 5:27Root cause of increased write amplification
6. 7:10Motivation
7. 8:02Overall Architecture
8. 9:12Matrix Container
9. 10:21Row Table
10. 11:10Fine grained column compaction
11. 13:19Reducing LSM-tree depth
12. 14:08Cross-Row hint search
13. 16:01Evaluation Setup
14. 16:37Random Write Throughput
15. 17:25Write stalls
16. 17:59Tail Latency
17. 18:25Fine granularity column compaction

" related talks

• 12mSpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid StorageCheng Li, Hao Chen, Chaoyi Ruan, Yinlong Xu, Xiaosong Ma · FAST '21
• 18mSplitKV: Splitting IO Paths for Different Sized Key-Value Items with AdvancedShukai Han, Dejun Jiang, Jin Xiong · 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage '20)
• 18mPreview: KV-Stores and DatabasesAlex Conway · OSDI '21 / USENIX ATC '21
• 15mKVIMR: Key-Value Store Aware Data Management Middleware for Interlaced Magnetic...Tsun-Yu Yang, Yuhong Liang, Ming-Chang Yang · USENIX ATC '21
• 15mMitigating Resource Usage Dependency in Sorting-based KV Stores on Hybrid...Qingyang Zhang, Yongkun Li, Yubiao Pan, Haoting Tang, Yinlong Xu · USENIX ATC '25
• 13mClosing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware...Tong Zhang, Yang Liu, Yifan Qiao, Xubin Chen, Ning Zheng, Jiangpeng Li · FAST '22
• 13mDifferentiated Key-Value Storage Management for Balanced I/O PerformanceYi Wu, Patrick P. C. Lee, Yongkun Li, Yinlong Xu, Qiu Cui, Liu Tang, Zhen Liu, Jiayu Wu, Qi Liu · USENIX ATC '21
• 05mExploring Data Deduplication in LSM Tree-based Key-Value Stores (Work-in-Progress Report)Youngjae Kim, Safdar Jamil, Awais Khan · FAST '22