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

作　　者：Feng-Feng Pan Yin-Liang Yue Jin Xiong 

机构地区：[1]State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing 100190, China [2]University of Chinese Academy of Sciences, Beijing 100049, China [3]Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

出　　处：《Journal of Computer Science & Technology》2017年第1期41-54,共14页计算机科学技术学报（英文版）

基　　金：This work is supported by the National Key Research and Development Program of China under Grant No. 2016YFB1000202 and the National Natural Science Foundation of China under Grant Nos. 61303056 and 61379042.

摘　　要：Key-value （KV） stores have become a backbone of large-scale applications in today＇s data centers. Write- optimized 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.Key-value （KV） stores have become a backbone of large-scale applications in today＇s data centers. Write- optimized 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.

关 键 词：key-value store Log-Structured Merge-tree （LSM-tree） write amplification delayed compaction 

分 类 号：TP309[自动化与计算机技术—计算机系统结构] U415.55[自动化与计算机技术—计算机科学与技术]