Rethinking LSM-tree based Key-Value Stores: A Survey
Authors:
- Yina LvYLYina Lv
- Qiao LiQLQiao Li
- Quanqing XuQXQuanqing Xu
- Congming GaoCGCongming Gao
- Chuanhui YangCYChuanhui Yang
- Xiaoli WangXWXiaoli Wang
- Chun Jason XueCXChun Jason Xue
Preprint
Abstract
LSM-tree is a widely adopted data structure in modern key-value store systems that optimizes write performance in write-heavy applications by using append writes to achieve sequential writes. However, the unpredictability of LSM-tree compaction introduces significant challenges, including performance variability during peak workloads and in resource-constrained environments, write amplification caused by data rewriting during compactions, read amplification from multi-level queries, trade-off between read and write performance, as well as efficient space utilization to mitigate space amplification. Prior studies on LSM-tree optimizations have addressed the above challenges; however, in recent years, research on LSM-tree optimization has continued to propose. The goal of this survey is to review LSM-tree optimization, focusing on representative works in the past five years. This survey first studies existing solutions on how to mitigate the performance impact of LSM-tree flush and compaction and how to improve basic key-value operations. In addition, distributed key-value stores serve multi-tenants, ranging from tens of thousands to millions of users with diverse requirements. We then analyze the new challenges and opportunities in these modern architectures and across various application scenarios. Unlike the existing survey papers, this survey provides a detailed discussion of the state-of-the-art work on LSM-tree optimizations and gives future research directions.Keywords
All Related Versions
This publication has 90 references indexed in Scilit:
- Coordinating Compaction Between LSM-Tree Based Key-Value Stores for Edge Federation2024
- LightPool: A NVMe-oF-based High-performance and Lightweight Storage Pool Architecture for Cloud-Native Distributed Database2024
- Towards flexibility and robustness of LSM treesThe VLDB Journal, 2024
- Supporting Elastic Compaction of LSM-tree with a FaaS Cluster2021
- SineKV: Decoupled Secondary Indexing for LSM-based Key-Value Stores2020
- Kill Two Birds with One Stone: Auto-tuning RocksDB for High Bandwidth and Low Latency2020
- LSM-based storage techniques: a surveyThe VLDB Journal, 2019
- LSbM-tree: Re-Enabling Buffer Caching in Data Management for Mixed Reads and Writes2017
- dCompaction: Speeding up Compaction of the LSM-Tree via Delayed CompactionJournal of Computer Science and Technology, 2017
- The log-structured merge-tree (LSM-tree)Acta Informatica, 1996