ElasticBF: Fine-grained and Elastic Bloom Filter Towards Efficient Read for LSM-tree-based KV Stores


Yueming Zhang, Yongkun Li, Fan Guo, Cheng Li, and Yinlong Xu, University of Science and Technology of China


LSM-tree based KV stores suffer from severe read amplification, especially for large KV stores. Even worse, many applications may issue a large amount of lookup operations to search for nonexistent keys, which wastes a lot of extra I/Os. Even though Bloom filters can be used to speedup the read performance, existing designs usually adopt a uniform setting for all Bloom filters and fail to support dynamic adjustment, thus results in a high false positive rate or large memory consumption. To address this issue, we propose ElasticBF, which constructs more small filters for each SSTable and dynamically load into memory as needed based on access frequency, so it realizes a fine-grained and elastic adjustment in running time with the same memory usage. Experiment shows that ElasticBF can achieve 1.94×-2.24× read throughput compared to LevelDB under different workloads, and preserves the same write performance. More importantly, ElasticBF is orthogonal to existing works optimizing the structure of KV stores, so it can be used as an accelerator to further speedup their read performance.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {216888,
author = {Yueming Zhang and Yongkun Li and Fan Guo and Cheng Li and Yinlong Xu},
title = {{ElasticBF}: Fine-grained and Elastic Bloom Filter Towards Efficient Read for {LSM-tree-based} {KV} Stores},
booktitle = {10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18)},
year = {2018},
address = {Boston, MA},
url = {https://www.usenix.org/conference/hotstorage18/presentation/zhang},
publisher = {USENIX Association},
month = jul