EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

An LSM Tree Augmented with B + Tree on Nonvolatile Memory

Donguk Kim, Jongsung Lee, Keun Soo Lim, Jun Heo, Tae Jun Ham, Jae W. Lee

ACM Transactions on Storage · 29.02.2024 · 20 (1) · 1-24

DOI: 10.1145/3633475 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Storage, online erschienen am 30.01.2024. Verfasst von Donguk Kim und 5 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 58 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Institute of Information & Communications Technology Planning & Evaluation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Modern log-structured merge (LSM) tree-based key-value stores are widely used to process update-heavy workloads effectively as the LSM tree sequentializes write requests to a storage device to maximize storage performance. However, this append-only approach leaves many outdated copies of frequently updated key-value pairs, which need to be routinely cleaned up through the operation called compaction . When the system load is modest, compaction happens in background. However, at a high system load, it can quickly become the major performance bottleneck. To address this compaction bottleneck and further improve the write throughput of LSM tree-based key-value stores, we propose LAB-DB, which augments the existing LSM tree with a pair of B + trees on byte-addressable nonvolatile memory (NVM). The auxiliary B + trees on NVM reduce both compaction frequency and compaction time, hence leading to lower compaction overhead for writes and fewer storage accesses for reads. According to our evaluation of LAB-DB on RocksDB with YCSB benchmarks, LAB-DB achieves 94% and 67% speedups on two write-intensive workloads (Workload A and F), and also a 43% geomean speedup on read-intensive YCSB Workload B, C, D, and E. This performance gain comes with a low cost of NVM whose size is just 0.6% of the entire dataset to demonstrate the scalability of LAB-DB with an ever increasing volume of future datasets.

Förderung

  • Institute of Information & Communications Technology Planning & Evaluation

Zitieren

APA

Kim, D., Lee, J., Lim, K. S., Heo, J., Ham, T. J., & Lee, J. W. (2024). An LSM Tree Augmented with B + Tree on Nonvolatile Memory. ACM Transactions on Storage, 20(1), 1-24. https://doi.org/10.1145/3633475

Vancouver

Kim D, Lee J, Lim KS, Heo J, Ham TJ, Lee JW. An LSM Tree Augmented with B + Tree on Nonvolatile Memory. ACM Transactions on Storage. 2024;20(1):1-24. doi:10.1145/3633475

BibTeX
@article{Kim2024,
  author = {Kim, Donguk and Lee, Jongsung and Lim, Keun Soo and Heo, Jun and Ham, Tae Jun and Lee, Jae W.},
  title = {An LSM Tree Augmented with B + Tree on Nonvolatile Memory},
  journal = {ACM Transactions on Storage},
  year = {2024},
  volume = {20},
  number = {1},
  pages = {1--24},
  doi = {10.1145/3633475}
}
Kostenlos starten →