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

Jihwan Lee, Won Gi Choi, Doyoung Kim, Hanseung Sung, Sanghyun Park

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Article number9056561
Pages (from-to)100948-100962
Number of pages15
JournalIEEE Access
Publication statusPublished - 2020

Bibliographical note

Publisher Copyright:
© 2013 IEEE.

All Science Journal Classification (ASJC) codes

  • General Engineering
  • General Computer Science
  • General Materials Science


Dive into the research topics of 'TLSM: Tiered Log-Structured Merge-Tree Utilizing Non-Volatile Memory'. Together they form a unique fingerprint.

Cite this