基于更新热点感知的LSM-Tree查询优化

doi:10.11959/j.issn.2096-0271.2022049

摘要/Abstract

摘要：

基于LSM-Tree的键值存储已经得到广泛使用。LSM-Tree通过将更新的数据缓存在内存中、随后批量写入磁盘的I/O优化措施来取得极高的写性能。然而，在基于LSM-Tree的键值存储中，被更新键值对的旧数据不会立即从存储系统中清除，导致整个存储系统中会积累大量的无效数据，最终会显著降低键值存储的读性能。针对以上问题，提出一种更积极的Compaction方法，通过记录键值对更新的历史信息，识别出更新热点，在整个LSM-Tree存储系统中寻找无效数据大量聚集的SSTable，及早地实施Compaction，清除其中的无效数据，缓解写放大效应，从而提升读性能。实验表明，该方法能够降低LevelDB 65.2%的读平均延迟，69.4%的读尾延迟以及71.4%的写放大。

关键词:

"> 键值存储；日志结构合并树；读性能优化；写放大

Abstract:

Key-value stores based on LSM-Tree has been widely used. LSM-Tree gains excellent write performance by collecting updated data in memory and then flush data into storage in batches. However, in LSM-Tree based key-value stores, old data generated by update operations will not be eliminated immediately from the storage system, resulting in a large amount of invalid data accumulated in the entire srotage system, which will eventually significantly reduce the read performance of key-value stores. For the above problems, an active compaction method was proposed. By recording the history information of updated key-value pairs, recognizing hot-updated keys, finding SSTables that contain large amount of invalid data in the storage system, and triggering compaction as soon as possible to clear much more invalid data, the proposed method can reduce write amplification and improve read performance of LSM-Tree based key-value stores. Experiments show that this method can reduce average read latency of LevelDB by 65.2%, 99 percent read tail latency by 69.4%, and write amplification by 71.4%.

林清音, 陈志广. 基于更新热点感知的LSM-Tree查询优化[J]. 大数据, doi: 10.11959/j.issn.2096-0271.2022049.

Qingyin LIN, Zhiguang CHEN.

A Hot-update-aware Optimization to the Query of LSM-Tree [J]. Big Data Research, doi: 10.11959/j.issn.2096-0271.2022049.

参考文献

[1] O’Neil P, Cheng E, Gawlick D, et al. The log-structured merge-tree (LSM-tree)[J]. Acta Informatica, 1996, 33(4): 351-385.

[2] Sanjay Ghemawat and Jeff Dean. Leveldb, 2016. https://github.com/google/leveldb.

[3] Facebook. Rocksdb, a persistent key-value store for fast storage enviroments, 2019. http://rocksdb.org/.

[4] Lakshman A, Malik P. Cassandra: a decentralized structured storage system[J]. ACM SIGOPS Operating Systems Review, 2010, 44(2): 35-40.

[5] Yao T, Zhang Y, Wan J, et al. MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM [C]//2020 USENIX Annual Technical Conference. USA: USENIX Association, 2020: 17-31.

[6] Lu L, Pillai T S, Gopalakrishnan H, et al. Wisckey: Separating keys from values in ssd-conscious storage[J]. ACM Transactions on Storage (TOS), 2017, 13(1): 1-28.

[7] Raju P, Kadekodi R, Chidambaram V, et al. Pebblesdb: Building key-value stores using fragmented log-structured merge trees[C]//Proceedings of the 26th Symposium on Operating Systems Principles. Shanghai, China. New York: Association for Computing Machinery, 2017: 497-514.

[8] Yao T, Wan J, Huang P, et al. A light-weight compaction tree to reduce I/O amplification toward efficient key-value stores[C]//Proc. 33rd Int. Conf. Massive Storage Syst. Technol.(MSST). 2017: 1-13.

[9] Li Y, Tian C, Guo F, et al. Elasticbf: elastic bloom filter with hotness awareness for boosting read performance in large key-value stores[C]//2019 USENIX Annual Technical Conference. USA: USENIX Association, 2019: 739-752.

[10] Wu F, Yang M H, Zhang B, et al. AC-key: Adaptive caching for LSM-based key-value stores[C]//2020 USENIX Annual Technical Conference. USA: USENIX Association, 2020: 603-615.

[11] Wu X, Xu Y, Shao Z, et al. LSM-trie: An LSM-tree-based ultra-large key-value store for small data items[C]//2015 USENIX Annual Technical Conference, Santa Clara, USA. USA: USENIX Association, 2015: 71-82.

[12] Shin J, Wang J, Aref W G. The LSM RUM-Tree: A Log Structured Merge R-Tree for Update-intensive Spatial Workloads[C]//2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2021: 2285-2290.

[13] Xiong X, Aref W G. R-trees with update memos[C]//22nd International Conference on Data Engineering (ICDE'06). IEEE, 2006: 22-22.

[14] Chandramouli B, Prasaad G, Kossmann D, et al. Faster: A concurrent key-value store with in-place updates[C]//Proceedings of the 2018 International Conference on Management of Data, Housto, USA. New York: Association for Computing Machinery. 2018: 275-290.

[15] Alsubaiee S, Behm A, Borkar V, et al. Storage management in AsterixDB[J]. Proceedings of the VLDB Endowment, 2014, 7(10): 841-852.

[16] Cooper B F, Silberstein A, Tam E, et al. Benchmarking cloud serving systems with YCSB[C]//Proceedings of the 1st ACM symposium on Cloud computing, Indianapolis, USA. New York: Association for Computing Machinery. 2010: 143-154.