TreeLine: An Update-In-Place Key-Value Store for Modern Storage

Many modern key-value stores, such as RocksDB, rely on logstructured merge trees (LSMs). Originally designed for spinning disks, LSMs optimize for write performance by only making sequential writes. But this optimization comes at the cost of reads: LSMs must rely on expensive compaction jobs and Bloom ltersall to maintain reasonable read performance. For NVMe SSDs, we argue that trading o read performance for write performance is no longer always needed. With enough parallelism, NVMe SSDs have comparable random and sequential access performance. This change makes update-in-place designs, which traditionally provide excellent read performance, a viable alternative to LSMs. In this paper, we close the gap between log-structured and update-in-place designs on modern SSDs with the help of new components that take advantage of data and workload patterns. Specically, we explore three key ideas: (A) record caching for efcient point operations, (B) page grouping for high-performance range scans, and (C) insert forecasting to reduce the reorganization costs of accommodating new records. We evaluate these ideas by implementing them in a prototype update-in-place key-value store called TreeLine. On YCSB, we nd that TreeLine outperforms RocksDB and LeanStore by 2.20⇥ and 2.07⇥ respectively on average across the point workloads, and by up to 10.95⇥ and 7.52⇥ overall.