CollapseDB: Exploring Multi-Level Compaction in LSM-Trees to Enhance Write Performance

Log Structured Merge Tree (LSM-Tree) is the core data structure that powers many modern key-value storage engines for its high write throughput property. To enable high speed writes, LSM-Tree ingests updates in an out-of-place manner and organizes key-value items into multiple levels of exponentially increasing capacities. To service fast data access, LSM-Tree frequently performs compaction operation, where data between two consecutive levels is sort-merged and written down to the lower level in granularity of SSTable. This compaction operation is known to cause high write amplification, which is the main threat to the LSM-tree's design objective of achieving high write performance.