Closing the Performance Gap Between Volatile and Persistent Key-Value Stores Using Cross-Referencing Logs


Yihe Huang, Harvard University; Matej Pavlovic, EPFL; Virendra Marathe, Margo Seltzer, Tim Harris, and Steve Byan, Oracle Labs


Key-Value (K-V) stores are an integral building block in modern datacenter applications. With byteaddressable persistent memory (PM) technologies, such as Intel/Micron’s 3D XPoint, on the horizon, there has been an influx of new high performance K-V stores that leverage PM for performance. However, there remains a significant performance gap between PM optimized K-V stores and DRAM resident ones, largely reflecting the gap between projected PM latency relative to that of DRAM. We address that performance gap with Bullet, a K-V store that leverages both the byte-addressability of PM and the lower latency of DRAM, using a technique called cross-referencing logs (CRLs) to keep PM updates off the critical path. Bullet delivers performance approaching that of DRAM resident K-V stores by maintaining two hash tables, one in the slower (backend) PM and the other in the faster (frontend) DRAM. CRLs are a scalable persistent logging mechanism that keeps the two copies mutually consistent. Bullet also incorporates several critical optimizations, such as dynamic load balancing between frontend and backend threads, support for nonblocking Gets, and opportunistic omission of stale updates in the backend. This combination of implementation techniques delivers performance within 5% of that of DRAM-only key-value stores for realistic (read-heavy) workloads. Our general approach, based on CRLs, is “universal” in that it can be used to turn any volatile K-V store into a persistent one (or vice-versa, provide a fast cache for a persistent K-V store).

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {216029,
author = {Yihe Huang and Matej Pavlovic and Virendra Marathe and Margo Seltzer and Tim Harris and Steve Byan},
title = {Closing the Performance Gap Between Volatile and Persistent {Key-Value} Stores Using {Cross-Referencing} Logs},
booktitle = {2018 USENIX Annual Technical Conference (USENIX ATC 18)},
year = {2018},
isbn = {978-1-939133-01-4},
address = {Boston, MA},
pages = {967--979},
url = {},
publisher = {USENIX Association},
month = jul

Presentation Audio