Key Technologies for System

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

  • Yang YU ,
  • Huiqi HU ,
  • Xuan ZHOU
Expand
  • School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received date: 2021-07-27

  Online published: 2021-09-28

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 L0layer, 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.

Cite this article

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 . DOI: 10.3969/j.issn.1000-5641.2021.05.004

References

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.
5 STRUKOV D B, SNIDER G S, STEWART D R, et al. The missing memristor found. Nature, 2008, 453 (7191): 80- 83.
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.
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/.
Outlines

/