Optimization of LSM-tree storage systems based on non-volatile memory

doi:10.3969/j.issn.1000-5641.2021.05.004

Abstract

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

CLC Number:

TP392

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.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Table 1

References 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]	Mengchen YANG, Xudong CHEN, Peng CAI, Lyu NI. Survey of early time series classification methods [J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 115-133.
[2]	XIAO YAO, BI Jun-fang, HAN YI, DONG Qi-wen. Study of click through rate prediction in online advertisement [J]. Journal of East China Normal University(Natural Sc, 2017, 2017(5): 80-86,100.