Building an Efficient Put-Intensive Key-Value Store with Skip-Tree

Multi-component based Log-Structured Merge-tree (LSM-tree) has been becoming one of the mainstream indexes. LSM-tree adopts component-by-component KV item flowing down mechanism to push each KV item from one smaller component to the adjacent larger component during compaction procedures until the KV items reach the largest component. This process incurs significant write amplification and limits the write throughput. In this paper, we propose one multi-component Skip-tree to aggressively push the KV items to the non-adjacent larger components via skipping some components and then make the KV items' top-down move more efficient. We develop adaptive and reliable KV item movements among components. By reducing the number of steps during the flowing process from memory-resident component to the disk-resident largest component, Skip-tree can effectively reduce the write amplification and thus improve the system throughput. We design and implement one high performance key-value store, named SkipStore, based on Skip-tree. The experiments demonstrate that SkipStore outperforms the state-of-the-art open-sourced system RocksDB in Facebook by 66.5 percent under HDD and 61 percent under SSD.