MDCF: Multiple Dynamic Cuckoo Filters for LSM-Tree

As a write-optimized data structure, the Log-Structured Merge-tree (LSM-tree) based storage engine, which maintains data in a leveled structure on disk, is widely used in Key-Value (KV) storage systems. Meanwhile, the leveled design also makes it suffer from heavy read amplification since one query may incur multiple file search operations across several levels. To reduce I/O overhead, Bloom filters are adopted to accelerate the query process. Nevertheless, caching Bloom filters in memory incurs substantial memory overhead, and they need to be rebuilt during compaction. In this paper, we analyze the factors causing read amplification in LSM-trees and the challenges for the designing of Bloom filters. Based on our observation and analysis, we propose MDCF, an innovative solution that replaces Bloom filters with Multiple Dynamic Cuckoo Filters (MDCF) and implements it on LevelDB. The basic idea of MDCF is to construct a DCF for each level of the LSM-tree, except for the lowest level. KV pairs in level \(L_0\) are mapped to a combination of a fingerprint and an SSTable identifier in \(DCF_0\) , while KV pairs in other levels are mapped to a fingerprint in the corresponding DCF. We demonstrate that this design not only significantly reduces read amplification by directly locating the target SSTable for each read request, but also consumes much less memory space. Experimental results based on YCSB demonstrate that MDCF outperforms LevelDB by 20–89% in read throughput without sacrificing write latency.