Paper Info
Title
Pipelined Compaction for the LSM-Tree
Abstract
Write-optimized data structures like Log-Structured Merge-tree (LSM-tree) and its variants are widely used in key-value storage systems like Big Table and Cassandra. Due to deferral and batching, the LSM-tree based storage systems need background compactions to merge key-value entries and keep them sorted for future queries and scans. Background compactions play a key role on the performance of the LSM-tree based storage systems. Existing studies about the background compaction focus on decreasing the compaction frequency, reducing I/Os or confining compactions on hot data key-ranges. They do not pay much attention to the computation time in background compactions. However, the computation time is no longer negligible, and even the computation takes more than 60% of the total compaction time in storage systems using flash based SSDs. Therefore, an alternative method to speedup the compaction is to make good use of the parallelism of underlying hardware including CPUs and I/O devices. In this paper, we analyze the compaction procedure, recognize the performance bottleneck, and propose the Pipelined Compaction Procedure (PCP) to better utilize the parallelism of CPUs and I/O devices. Theoretical analysis proves that PCP can improve the compaction bandwidth. Furthermore, we implement PCP in real system and conduct extensive experiments. The experimental results show that the pipelined compaction procedure can increase the compaction bandwidth and storage system throughput by 77% and 62% respectively.
Year
DOI
Venue
2014
10.1109/IPDPS.2014.85
IPDPS
Keywords
Field
DocType
pcp,compaction,parallel processing,compaction bandwidth improvement,storage system, lsm-tree, compaction, pipeline,pipelined compaction procedure,tree data structures,storage management,log-structured merge-tree,lsm-tree,lsm-tree based storage systems,background compactions,merging,pipeline,compaction frequency reduction,computation time,storage system throughput,i/o devices,write-optimized data structures,cpu,key-value entries,performance evaluation,storage system,key-value storage systems,performance bottleneck,pipeline processing,log structured merge tree,hardware,lsm tree,indexes,bandwidth,pipelines,data structures
Bottleneck,Data structure,Computer science,Computer data storage,Parallel computing,Bandwidth (signal processing),Throughput,Data compaction,Compaction,Speedup
Conference
ISSN
Citations 
PageRank 
1530-2075
7
0.49
References 
Authors
11
7
Name
Order
Citations
PageRank
Zigang Zhang170.49
Yinliang Yue25110.90
Bingsheng He32810179.09
Jin Xiong415715.95
Ming-yu Chen590279.29
Lixin Zhang657145.96
SUN Ning-Hui7126897.37