基于非易失性内存的LSM-tree存储系统优化

doi:10.3969/j.issn.1000-5641.2021.05.004

摘要/Abstract

摘要：

随着大数据时代的到来, 金融行业产生的数据越来越多, 对数据库的压力也越来越大. LevelDB是谷歌开发的一款基于LSM-tree架构的键值对数据库, 有写入快和占用空间小的优点, 被金融行业广泛应用. 针对LSM-tree架构的写停顿、写放大、对读不友好等缺点, 提出了一种基于非易失性内存和机器学习的L₀层的设计方法, 能够减缓甚至解决上述问题. 实验结果表明, 该设计能够实现较好的读写性能.

关键词: 非易失性内存, 机器学习, LSM-tree架构

Abstract:

With the advent of the big data era, the financial industry has been generating increasing volumn of data, exerting pressure on database systems. LevelDB is a key-value database, developed by Google, based on the LSM-tree architecture. It offers fast writing and a small footprint, and is widely used in the financial industry. In this paper, we propose a design method for the L₀layer, based on non-volatile memory and machine learning, with the aim of addressing the shortcomings of the LSM-tree architecture, including write pause, write amplification, and unfriendly reading. The proposed solution can slow down or even solve the aforementioned problems; the experimental results demonstrate that the design can achieve better read and write performance.

Key words: NVM, machine learning, LSM-tree architecture

中图分类号:

TP392

余阳, 胡卉芪, 周煊. 基于非易失性内存的LSM-tree存储系统优化[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 37-47.

Yang YU, Huiqi HU, Xuan ZHOU. Optimization of LSM-tree storage systems based on non-volatile memory[J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 37-47.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

参考文献 27

1	EL-SHIMI A, KALACH R, KUMAR A, et al. Primary data deduplication—large scale study and system design [C]//2012 USENIX Annual Technical Conference. USENIX Association, 2012: 285-296.
2	SHILANE P, HUANG M, WALLACE G, et al. WAN-optimized replication of backup datasets using stream-informed delta compression. ACM Transactions on Storage, 2012, 8 (4): 1- 26.
3	GOOGLE INC. LevelDB [EB/OL]. [2019-06-20]. https://github.com/google/leveldb.
4	BHASKARAN M S, XU J, SWANSON S. Bankshot: Caching slow storage in fast non-volatile memory. ACM SIGOPS Operating Systems Review, 2014, 48 (1): 73- 81. doi: 10.1145/2626401.2626417
5	STRUKOV D B, SNIDER G S, STEWART D R, et al. The missing memristor found. Nature, 2008, 453 (7191): 80- 83. doi: 10.1038/nature06932
6	IZRAELEVITZ J, YANG J, ZHANG L, et al. Basic performance measurements of the intel optane DC persistent memory module [EB/OL]. (2019-03-13) [2021-06-12]. https://arxiv.org/pdf/190305714v1.pdf.
7	DRISKILL-SMITH A. Latest advances and future prospects of STT-RAM [C]//Non-Volatile Memories Workshop. 2010: 11-13.
8	CAULFIELD A M, DE A, COBURN J, et al. Moneta: A high-performance storage array architecture for next-generation, non-volatile memories [C]//2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture. IEEE, 2010: 385-395.
9	LI J, PAVLO A, DONG S. NVMRocks: RocksDB on non-volatile memory systems [EB/OL]. [2021-06-20]. http://istc-bigdata.org/ index.php/nvmrocks-rocksdb-on-non-volatie-memory-systems/.
10	KANNAN S, BHAT N, GAVRILOVSKA A, et al. Redesigning LSMs for nonvolatile memory with NoveLSM [C]//2018 USENIX Annual Technical Conference. USENIX Association, 2018: 993-1005.
11	WU M, ZWAENEPOEL W. eNVy: A non-volatile, main memory storage system. ACM SIGOPS Operating Systems Review, 1994, 28 (5): 86- 97. doi: 10.1145/381792.195506
12	JAGADISH H V, NARAYAN P P S, SESHADRI S, et al. Incremental organization for data recording and warehousing [C]//Proceedings of the 23rd VLDB Conference. 1997: 16-25.
13	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. 2017: 497-514.
14	YAO T, WAN J, HUANG P, et al. A light-weight compaction tree to reduce I/O amplification toward efficient key-value stores [C]//Proceedings of the 33rd International Conference on Massive Storage System Technology (MSST). 2017: 1-13.
15	LU L, PILLAI T S, GOPALAKRISHNAN H, et al. Wisckey: Separating keys from values in SSD-conscious storage. ACM Transactions on Storage, 2017, 13 (1): 1- 28.
16	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. USENIX Association, 2015: 71-82.
17	SHETTY P J, SPILLANE R P, MALPANI R R, et al. Building workload-independent storage with VT-trees [C]//11th USENIX Conference on File and Storage Technologies. USENIX Association, 2013: 17-30.
18	BALMAU O, DIDONA D, GUERRAOUI R, et al. TRIAD: Creating synergies between memory, disk and log in log structured key-value stores [C]//2017 USENIX Annual Technical Conference. 2017: 363-375.
19	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. USENIX Association, 2020: 17-31.
20	BALMAU O, DINU F, ZWAENEPOEL W, et al. SILK: Preventing latency spikes in log-structured merge key-value stores [C]//2019 USENIX Annual Technical Conference. USENIX Association, 2019: 753-766.
21	SEARS R, RAMAKRISHNAN R. bLSM: A general purpose log structured merge tree [C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. 2012: 217-228.
22	LEPERS B, BALMAU O, GUPTA K, et al. KVell: The design and implementation of a fast persistent key-value store [C]//Proceedings of the 27th ACM Symposium on Operating Systems Principles. New York: Association for Computing Machery, 2019: 447-461.
23	KAIYRAKHMET O, LEE S, NAM B, et al. SLM-DB: Single-level key-value store with persistent memory [C]//17th USENIX Conference on File and Storage Technologies. USENIX Association, 2019: 191-205.
24	EISENMAN A, GARDNER D, ABDELRAHMAN I, et al. Reducing DRAM footprint with NVM in Facebook [C]//Proceedings of the Thirteenth EuroSys Conference. 2018: 1-13.
25	FERRAGINA P, VINCIGUERRA G. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 2020, 13 (10): 1162- 1175.
26	EIGEN. [EB/OL]. [2019-06-20]. https://eigen.tuxfamily.org/.
27	GMP. [EB/OL]. [2019-06-20]. https://gmplib.org/.

key数量	有索引时延/μs	无索引时延/μs
1000	7.0	6.8
10000	7.2	8.7
100000	16.3	10.5

[1]	杨梦晨, 陈旭栋, 蔡鹏, 倪葎. 早期时间序列分类方法研究综述[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 115-133.
[2]	肖垚, 毕军芳, 韩易, 董启文. 在线广告中点击率预测研究[J]. 华东师范大学学报(自然科学版), 2017, 2017(5): 80-86,100.