dCompaction: Speeding up Compaction of the LSM-Tree via Delayed Compaction

详细信息    查看全文

• 作者：Feng-Feng Pan ; Yin-Liang Yue ; Jin Xiong
• 关键词：key ; value store ; Log ; Structured Merge ; tree (LSM ; tree) ; write amplification ; delayed compaction
• 刊名：Journal of Computer Science and Technology
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：32
• 期：1
• 页码：41-54
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general; Software Engineering; Theory of Computation; Data Structures, Cryptology and Information Theory; Artificial Intelligence (incl. Robotics); Information Systems Applications (
• 出版者：Springer US
• ISSN：1860-4749
• 卷排序：32

文摘

Key-value (KV) stores have become a backbone of large-scale applications in today’s data centers. Writeoptimized data structures like the Log-Structured Merge-tree (LSM-tree) and their variants are widely used in KV storage systems like BigTable and RocksDB. Conventional LSM-tree organizes KV items into multiple, successively larger components, and uses compaction to push KV items from one smaller component to another adjacent larger component until the KV items reach the largest component. Unfortunately, current compaction scheme incurs significant write amplification due to repeated KV item reads and writes, and then results in poor throughput. We propose a new compaction scheme, delayed compaction (dCompaction) that decreases write amplification. dCompaction postpones some compactions and gathers them into the following compaction. In this way, it avoids KV item reads and writes during compaction, and consequently improves the throughput of LSM-tree based KV stores. We implement dCompaction on RocksDB, and conduct extensive experiments. Validation using YCSB framework shows that compared with RocksDB, dCompaction has about 40% write performance improvements and also comparable read performance.