Redesigning Persistent Key-Value Stores for Future Workloads, Hardware, and Performance Requirements

Abstract

Cloud storage stacks are being challenged by new workloads, new hardware, and new performance requirements. First, workloads evolved from following a read-heavy pattern (e.g., a static web-page) to a write-heavy profile where the read:write ratio is closer to 1:1 (e.g., as in the Internet of Things). Second, the hardware is undergoing rapid changes. The divide between fine-grained volatile memory and slow block-level storage is rapidly being bridged by the emerging byte-addressable non-volatile memory devices and the fast block-addressable NVMe SSDs (e.g., Intel Optane NVMe SSDs). Third, performance requirements in storage systems now emphasize low tail latency, in addition to high throughput. This dissertation argues that existing storage systems, in particular persistent key-value stores (KVs), have fundamental limitations that do not allow them to fully meet these challenges. This dissertation proposes four new KVs designed for future hardware, workloads, and performance requirements. FloDB shows how to scale the throughput of KVs on servers with ample memory sizes of up to hundreds of GBs. TRIAD introduces novel techniques to reduce write amplification and to increase throughput in log-structured merge based KVs running on SSDs. SILK presents an I/O bandwidth scheduler to decrease tail latency in log-structured merge based KVs. Finally, KVell demonstrates that NVMe SSDs shift the performance bottleneck from I/O to CPU, invalidating an assumption that has underpinned all past storage system design. In line with this observation KVell then presents a new design for KVs that departs from the conventional wisdom of optimizing disk usage and instead optimizes CPU usage.