Recursive Compaction Method of LSM-tree based Key-value Store

Jongbin Kim, Seohui Son, Hyunsoo Cho, Hyungsoo Jung

http://doi.org/10.5626/JOK.2019.46.9.946

LSM-tree-based key-value stores exhibit an optimized structure for data writing operations and typically maintain the form of LSM tree by executing a compaction operation. The compaction operation which reads data from the storage device into memory for sorting it and writes back the result data in to the storage device several times causes some problems. In this paper, we analyzed the performance degradation and the write amplification caused by the compaction, and proposed a new compaction method known as recursive compaction. Recursive compaction alleviates the problems involving the compaction operation by utilizing multiple threads to perform multiple compactions at a time, handling read operation and garbage collection properly. We implemented this technique for Google LevelDB and analyzed the results.