Exploring Data Deduplication in LSM Tree-based Key-Value Stores (Work-in-Progress Report)

on YouTube ↗05m

" summary

Explores adding value-based deduplication to LSM trees, showing inline duplication (fingerprinting on writes with a chunk information table) causes severe write-performance drop and metadata inconsistency from in-place updates; builds DeltaKV, an offline dedupe applied at flush that delays fingerprinting to background threads, splits metadata into a value information table and a B+ tree for reads, and writes only unique values to level-0 SSTables; preliminary evaluation reports DeltaKV matches RocksTV performance and outperforms mamdado.

AI-written summary · about

" related talks

• 18mPreview: KV-Stores and DatabasesAlex Conway · OSDI '21 / USENIX ATC '21
• 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
• 17mLight-Dedup: A Light-weight Inline Deduplication Framework for Non-Volatile...Yu Hua, Jiansheng Qiu, Wen Xia, Yanqi Pan, Xiaojia Huang, Wenjun Wu, Xiangyu Zou, Shiyi Li, Shiyi Li · USENIX ATC '23
• 21mMatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV StoresChangSheng Xie, Yiwen Zhang, Xubin He, Ting Yao, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang · USENIX ATC '20
• 15mXLL: Cross-Layer Logging for Data Deduplication in Consensus-Based StorageAndrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, John Shawger, Arnav Jhingran · NSDI '26
• 01h 16mDeep Dive into On-Disk Data StructuresLeif Walsh · HighLoad++ 2014
• 12mThe Dilemma between Deduplication and Locality: Can Both be Achieved?Wen Xia, Xiangyu Zou, Philip Shilane, Haijun Zhang, Xuan Wang, Jingsong Yuan · FAST '21
• 18mDon't Maintain Twice, It's Alright: Merged Metadata Management in Deduplication File...Erci Xu, Hao Huang, Wen Xia, Yanqi Pan, Xiangyu Zou, Shiyi Li · FAST '25