KDB: A Scalable Persistent Key-Value Store with Atomic Batches and Snapshots

Abstract

In this paper, we introduce KDB, a novel persistent key-value data store (a concurrent index) with rich linearizable semantics. In contrast to state-of-the-art systems which offer only lookup and put/remove operations, KDB supports both snapshots (which are used by range scans) and atomic batch updates—put and remove operations that are executed atomically. Despite its rich semantics, our system offers highly scalable performance across varied workloads thanks to its unique multiversioned architecture. It features a hybrid lock-CAS synchronization mechanism that allows lookup operations and scans to proceed in a wait-free fashion. Under the hood, KDB maintains all key-value entries in persistent memory (PM) for failure atomicity, but it heavily relies on an efficient DRAM-backed multiversion index based on skip lists to hide the costs of accessing PM. For better PM utilization, entries are arranged in PM in preallocated arrays that occasionally undergo compaction.