Montage: A General System for Buffered Durably Linearizable Data Structures

Montage: A General System for Buffered Durably Linearizable Data Structures

Mar 01, 2021
|
41 views
|
Details
Abstract: The recent emergence of fast, dense, nonvolatile main memory suggests that certain long-lived data might remain in its natural pointer-rich format across program runs and hardware reboots. Operations on such data must be instrumented with explicit write-back and fence instructions to ensure consistency in the wake of a crash. Techniques to minimize the cost of this instrumentation are an active topic of research. We present what we believe to be the first general-purpose approach to building buffered durably linearizable persistent data structures, and a system, Montage, to support that approach. Montage is built on top of the Ralloc nonblocking persistent allocator. It employs a slow-ticking epoch clock, and ensures that no operation appears to span an epoch boundary. It also arranges to persist only that data minimally required to reconstruct the structure after a crash. If a crash occurs in epoch e, all work performed in epochs e and e−1 is lost, but work from prior epochs is preserved. We describe the implementation of Montage, argue its correctness, and report unprecedented throughput for persistent queues, sets/mappings, and general graphs. Authors: Haosen Wen, Wentao Cai, Mingzhe Du, Louis Jenkins, Benjamin Valpey, Michael L. Scott (University of Rochester)

Comments
loading...