Paper Info
Title
NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
Abstract
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.
Year
DOI
Venue
2020
10.1145/3385412.3386031
PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation London UK June, 2020
Keywords
DocType
ISBN
Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free
Conference
978-1-4503-7613-6
Citations 
PageRank 
References 
2
0.36
0
Authors
5
Name
Order
Citations
PageRank
Friedman Michal120.36
Ben-David Naama220.36
Yuanhao Wei321.71
Guy E. Blelloch42927207.30
Erez Petrank51601107.96