  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.
