NVTraverse: In NVRAM Data Structures, the Destination Is More Important Than the Journey
The recent availability of fast, dense, byte-addressable non-volatile memory has led to increasing interest in the problem of designing durable data structures that can recover from system crashes. However, designing durable concurrent data structures that are correct and efficient has proven to be very difficult, leading to many inefficient or incorrect algorithms. In this paper, we present a general transformation that takes a lock-free data structure from a general class called traversal data structure (that we formally define) and automatically transforms it into an implementation of the data structure for the NVRAM setting that is provably durably linearizable and highly efficient. The transformation hinges on the observation that many data structure operations begin with a traversal phase that does not need to be persisted, and thus we only begin persisting when the traversal reaches its destination. We demonstrate the transformation's efficiency through extensive measurements on a system with Intel's recently released Optane DC persistent memory, showing that it can outperform competitors on many workloads.
Thu 18 Jun Times are displayed in time zone: (GMT-07:00) Pacific Time (US & Canada) change
|05:00 - 05:20|
Conrad WattUniversity of Cambridge, UK, Christopher PulteUniversity of Cambridge, UK, Anton PodkopaevMPI-SWS, NRU HSE, JetBrains Research, Guillaume BarbierENS Rennes, France, Stephen DolanUniversity of Cambridge, UK, Shaked FlurGoogle, Jean Pichon-PharabodUniversity of Cambridge, UK, Shu-yu GuoBloomberg, USAPre-print
|05:20 - 05:40|
Sung-Hwan LeeSeoul National University, South Korea, Minki ChoSeoul National University, South Korea, Anton PodkopaevMPI-SWS, NRU HSE, JetBrains Research, Soham ChakrabortyIIT Delhi, India, Chung-Kil HurSeoul National University, South Korea, Ori LahavTel Aviv University, Israel, Viktor VafeiadisMPI-SWS, Germany
|05:40 - 06:00|