BoLt: Barrier-optimized LSM-Tree

Key-value stores such as LevelDB and RocksDB are widely used in various systems due to their high write performance. However, the background compaction operations inherent to the key-value stores are often to blame for write amplification and write stall. In particular, the SSTable size in the existing key-value stores introduces, upon compactions, a tradeoff between the fsync() call frequency and the amount of amplified writes. Small SSTables require a larger number of fsync()/fdatasync() than large SSTables to maintain file consistency. On the contrary, large SSTables result in large overlaps and frequent rewrites of SSTables. In this paper, to reduce file consistency overhead without increasing key ranges of SSTables, we present a variant of LSM-tree, namely, BoLT (Barrier-optimized LSM-Tree), that minimizes the number of calls to fsync()/fdatasync() barriers while taking advantage of fine-grained SSTables. BoLT consists of four key elements: (i) compaction file, (ii) logical SSTables, (iii) group compaction, and (iv) settled compaction. We implement BoLT in LevelDB and HyperLevelDB and compare the performances against LevelDB, HyperLevelDB, RocksDB, and the state-of-the-art PebblesDB. Our experimental study shows that BoLT achieves significantly higher write throughputs than LevelDB and HyperLevelDB.