Dynamic read & write optimization with TurtleKV

High read and write performance is important for generic keyvalue stores, which are foundational to modern applications and databases. Yet, achieving high performance for mixed and dynamic workloads is challenging due to fundamental trade-os between memory use and I/O for retrieval and updates. Past work emphasizes the trade-o between read-and write-optimization as expressed through primary data structure, in combination with read-memory trade-o mechanisms like caching and ltering. This raises re-tuning costs as optimal trade-o targets change, due to restructuring of stored data. We show that write-memory trade-o mechanisms are under-developed in current designs, and propose a new approach to dynamic key-value store optimization using a novel read-/write-balanced on-disk structure, the TurtleTree, and exible read-/write-memory tuning knobs. We describe how to avoid in-memory bottlenecks to achieve high performance across a wide tuning range. When evaluated using YCSB, our prototype TurtleKV matches state-of-the-art SplinterDB for inserts, and is 5⇥/12⇥ faster than RockDB/WiredTiger. In mixed workloads, TurtleKV is 16-25% faster than SplinterDB, >4⇥ RocksDB, and 3-6⇥ WiredTiger. TurtleKV is 2-9⇥ faster than the others for point-query workloads, and has the best scan rate of the write-optimized systems tested.