Abstract
Key-value storage systems based on LSM-trees achieve fast write performance through out-of-place updates and a hierarchical structure. However, their range query process involves filtering and sorting SSTables at each level, resulting in significant performance overhead. To enhance range query performance, we traverse all KV pairs during the SSTable creation phase when compaction, and construct an efficient global index named BIVX with LSM-tree’s bottom level’s information. BIVX allows rapid location and reading of target files during range queries, significantly improving range query performance. Based on BIVX, we developed BIVXDB and demonstrated the effectiveness of our improvements through experimental results.
This work has been partially supported by the National Science Foundation of China No. 62372450.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970). https://doi.org/10.1145/362686.362692
Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., Sears, R.: Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing - SoCC 2010, p. 143. ACM Press, Indianapolis (2010)
Dayan, N., Athanassoulis, M., Idreos, S.: Optimal bloom filters and adaptive merging for LSM-trees. ACM Trans. Database Syst. 43(4) (2018). https://doi.org/10.1145/3276980
Dharmapurikar, S., Krishnamurthy, P., Taylor, D.: Longest prefix matching using bloom filters. IEEE/ACM Trans. Network. 14(2), 397–409 (2006). https://doi.org/10.1109/TNET.2006.872576
Facebook: Rocksdb documentation. https://rocksdb.org.cn/ doc .html
Facebook: Rocksdb tuning guide. https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide
Google: Leveldb documentation. https://github.com/google/leveldb/ blob/master/doc/index.md
Huang, C., Hu, H., Wei, X., Qian, W., Zhou, A.: Partition pruning for range query on distributed log-structured merge-tree. Front. Comput. Sci. 14(3) (2020). https://doi.org/10.1007/s11704-019-8234-x
Im, J., Bae, J., Chung, C., Arvind, Lee, S.: Design of LSM-tree-based Key-value SSDs with bounded tails. ACM Trans. Storage 17(2) (2021). https://doi.org/10.1145/3452846
Kaiyrakhmet, O., Lee, S., Nam, B., Noh, S.H., Choi, Y.R.: SLM-DB: single-level key-value store with persistent memory. In: 17th USENIX Conference on File and Storage Technologies (FAST 2019), pp. 191–205. USENIX Association, Boston (2019). https://www.usenix.org/conference/fast19/presentation/kaiyrakhmet
Li, C., Chen, H., Ruan, C., Ma, X., Xu, Y.: Leveraging NVME SSDS for building a fast, cost-effective, LSM-tree-based KV store. ACM Trans. Storage 17(4) (2021). https://doi.org/10.1145/3480963
Li, Y., Tian, C., Guo, F., Li, C., Xu, Y.: ElasticBF: elastic bloom filter with hotness awareness for boosting read performance in large key-value stores. In: USENIX Association, pp. 739–752 (2019)
Lu, K., Zhao, N., Wan, J., Fei, C., Zhao, W., Deng, T.: TridentKV: a read-optimized LSM-tree based KV store via adaptive indexing and space-efficient partitioning. IEEE Trans. Parallel Distrib. Syst. 33(8), 1953–1966 (2022). https://doi.org/10.1109/TPDS.2021.3118599
Luo, S., Chatterjee, S., Ketsetsidis, R., Dayan, N., Qin, W., Idreos, S., Rosetta: a robust space-time optimized range filter for key-value stores. In: Association Computing Machinery, pp. 2071–2086 (2020). https://doi.org/10.1145/3318464.3389731
O’Neil, P., Cheng, E., Gawlick, D., O’Neil, E.: The log-structured merge-tree (LSM-TREE). Acta Informatica 33(4), 351–385 (1996)
Sun, X., Yu, J., Zhou, Z., Xue, C.J.: FPGA-based compaction engine for accelerating LSM-tree key-value stores. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 1261–1272 (2020). https://doi.org/10.1109/ICDE48307.2020.00113
Wang, Y., Jin, P., Wan, S.: HotKey-LSM: a hotness-aware LSM-tree for big data storage, pp. 5849–5851 (2020). https://doi.org/10.1109/BigData50022.1010.9377736
Wu, F., Yang, M., Zhang, B., Du, D.: AC-key: adaptive caching for LSM-based key-value stores. In: USENIX Association, pp. 603–615 (2020)
Yao, T., et al.: Matrixkv: reducing write stalls and write amplification in LSM-tree based KV stores with matrix container in nvm. In: the 2020 USENIX Annual Technical Conference, pp. 17–31 (2020)
Zhang, B., Du, D.H.C.: NVLSM: a persistent memory key-value store using log-structured merge tree with accumulative compaction. ACM Trans. Storage 17(3) (2021). https://doi.org/10.1145/3453300
Zhang, H., et al.: Succinct range filters. ACM Trans. Database Syst. 45(2) (2020). https://doi.org/10.1145/3375660
Zhong, W., Chen, C., Wu, X., Jiang, S.: REMIX: efficient range query for LSM-trees. In: USENIX Association, pp. 51–64 (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yao, Z., Zhou, J., Fan, Z., Shan, L., Yue, Y., Song, Y. (2024). BIVXDB: A Bottom Information Invert Index to Speed up the Query Performance of LSM-Tree. In: Zhang, W., Tung, A., Zheng, Z., Yang, Z., Wang, X., Guo, H. (eds) Web and Big Data. APWeb-WAIM 2024. Lecture Notes in Computer Science, vol 14964. Springer, Singapore. https://doi.org/10.1007/978-981-97-7241-4_2
Download citation
DOI: https://doi.org/10.1007/978-981-97-7241-4_2
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-7240-7
Online ISBN: 978-981-97-7241-4
eBook Packages: Computer ScienceComputer Science (R0)