TLSM: Tiered Log-Structured Merge-Tree Utilizing Non-Volatile Memory

Jihwan Lee, Won Gi Choi, Doyoung Kim, Hanseung Sung, Sanghyun ParkIEEE Access 2020 · OpenReview

Abstract

Log-Structured Merge-tree (LSM-tree) organizes write-friendly and hierarchical structure, which leads to inevitable disk I/O from data compaction occuring between layers. Previous research tried to reduce write bottlenecks of LSM-tree by using non-volatile memory (NVM) to LSM-tree, but write amplification on compaction does not resolved. In this paper, we present tiered LSM (TLSM), a persistent LSM-based key-value database tiering NVM, which is regarded as fast storage device. Our design aims to exploit multi-layered LSM system utilizing NVM and reduce redundant cost on compaction. We address 4 key points: (1) analysis of disk I/O overhead on current LSM-tree, (2) novel design of TLSM preserving the concept of LSM-tree and utilizing NVM, (3) persistent and byte-addressable data compaction minimizing disk write, and (4) tiering policy for increasing usability to TLSM. To implement TLSM-tree, we extended LevelDB, which is a simple LSM-based key-value store. On micro-benchmark DB Bench, the write and read latencies of TLSM are improved up to 34% and 57%, respectively, compared to those of LevelDB-NVM. In evaluation of YCSB, TLSM also reduces the write and read latencies of existing LevelDB up to 25%, 33%, respectively. Furthermore, frequency of write stall and total amount of data write are reduced significantly in TLSM.
BibTeX
@inproceedings{lee2020tlsm,
  author = {Jihwan Lee and Won Gi Choi and Doyoung Kim and Hanseung Sung and Sanghyun Park},
  title = {{TLSM: Tiered Log-Structured Merge-Tree Utilizing Non-Volatile Memory}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=wvwVUovHSd},
}

Loading related content...

Figure