# Fast Nonblocking Persistence for Concurrent Data Structures111This work was
supported in part by NSF grants CCF-1717712, CNS-1900803, CNS-1955498, and by
a Google Faculty Research award.

Wentao Cai,222The first two authors contributed equally to this work. Haosen
Wen,††footnotemark:  Vladimir Maksimovski, Mingzhe Du,
Rafaello Sanna, Shreif Abdallah, and Michael L. Scott
Department of Computer Science, University of Rochester
{wcai6@cs,hwen5@cs,vmaksimo@u,mdu5@cs,rsanna@u,selsaid<EMAIL_ADDRESS>
(May 2021)

## Abstract

We present a fully lock-free variant of the recent Montage system for
persistent data structures. Our variant, nbMontage, adds persistence to almost
any nonblocking concurrent structure without introducing significant overhead
or blocking of any kind. Like its predecessor, nbMontage is _buffered durably
linearizable_ : it guarantees that the state recovered in the wake of a crash
will represent a consistent prefix of pre-crash execution. Unlike its
predecessor, nbMontage ensures wait-free progress of the persistence frontier,
thereby bounding the number of recent updates that may be lost on a crash, and
allowing a thread to force an update of the frontier (i.e., to perform a sync
operation) without the risk of blocking. As an extra benefit, the helping
mechanism employed by our wait-free sync significantly reduces its latency.

Performance results for nonblocking queues, skip lists, trees, and hash tables
rival custom data structures in the literature—dramatically faster than
achieved with prior general-purpose systems, and generally within 50% of
equivalent non-persistent structures placed in DRAM.

##  1 Introduction

With the advent of dense, inexpensive nonvolatile memory (NVM), it is now
feasible to retain pointer-based, in-memory data structures across program
runs and even hardware reboots. So long as caches remain transient, however,
programs must be instrumented with write-back and fence instructions to ensure
that such structures remain consistent in the wake of a crash. Minimizing the
cost of this instrumentation remains a significant challenge.

Section 2 of this paper surveys both bespoke persistent data structures and
general-purpose systems. Most of these structures and systems ensure that
execution is _durably linearizable_ [29]: not only will every operation
linearize (appear to occur atomically) sometime between its call and return;
each will also _persist_ (reach a state in which it will survive a crash)
before returning, and the persistence order will match the linearization
order. To ensure this agreement between linearization and persistence, most
existing work relies on locks to update the data structure and an undo or redo
log together, atomically.

Unfortunately, strict durable linearizability forces expensive write-back and
fence instructions onto the critical path (and into the latency) of every
operation. A few data structures—notably, the Dalí hash table of Nawab et al.
[44] and the InCLL MassTree of Cohen et al. [10]—reduce the cost of
instrumentation by supporting only a relaxed, _buffered_ variant [29] of
durable linearizability. Nawab et al. dub the implementation technique
_periodic persistence_. In the wake of post-crash recovery, a buffered durably
linearizable structure is guaranteed to reflect some prefix of the pre-crash
linearization order—but with the possibility that recent updates may be lost.

Independently, some data structures—notably, the B-tree variants of Yang et
al. [55], Oukid et al. [45], and Chen et al. [7], and the hash set of Zuriel
et al. [56]—reduce the overhead of persistence by writing back and fencing
only the data required to rebuild a semantically equivalent structure during
post-crash recovery. A mapping, for example, need only persist a pile of key-
value pairs. Index structures, which serve only to increase performance, can
be kept in faster, volatile memory.

Inspired by Dalí and the InCLL MassTree, Wen et al. [54] introduced the first
and, to our knowledge, only _general purpose_ system for buffered durably
linearizable data structures. Like the transient-index sets of the previous
paragraph, their _Montage_ system also facilitates persisting only
semantically essential _payloads_. Specifically, Montage employs a global
_epoch clock_. It tracks the semantically essential updates performed in each
operation and ensures that (1) no operation appears to span an epoch boundary,
and (2) no essential update fails to persist for two consecutive epochs. If a
crash occurs in epoch $e$, Montage recovers the abstract state of the
structure from the end of epoch $e-2$.

In return for allowing a bit of work to be lost on a crash, and for being
willing to rebuild, during recovery, any portion of a structure needed only
for good performance, users of Montage can expect to achieve performance
limited primarily by the read and write latency of the underlying memory—not
by instrumentation overhead. When a strict persistence guarantee is required
(e.g., before printing a completion notice on the screen or responding to a
client over the network), Montage allows an application thread to invoke an
explicit sync operation—just as it would for data in any conventional file or
database system.

Unfortunately, like most other general-purpose persistence systems, Montage
relies on locks at critical points in the code. All of the reported
performance results are for lock-based data structures. More significantly,
while the authors indicate that their system can support nonblocking
structures, progress of the persistence frontier is fundamentally blocking.
Specifically, before advancing the epoch from $e$ to $e+1$, the system waits
for all operations active in epoch $e-1$ to complete. If one of those
operations is stalled (e.g., due to preemption), epoch advance can be
indefinitely delayed. This fact implies that the sync operation cannot be
nonblocking. It also implies that the size of the history suffix that may be
lost on a crash cannot be bounded _a priori_.

While blocking is acceptable in many circumstances, nonblocking structures
have compelling advantages. They are immune to deadlocks caused by lock
misordering or priority inversion, and to performance anomalies and high tail
latency due to inopportune preemption. Lock-free and wait-free nonblocking
structures [24, Sec. 3.7] are also immune to livelock. By assigning a coherent
abstract state to every reachable concrete state, nonblocking data structures
simplify recovery [2] and eliminate the need to perform logging for the sake
of failure atomicity [13]. As long envisioned in the theory community, they
may even facilitate data sharing among processes that fail independently [23].

In their original paper on durable linearizability, Izraelevitz et al. [29]
presented a mechanical transform that will turn any linearizable nonblocking
concurrent data structure into an equivalent persistent structure.
Unfortunately, this transform is quite expensive, especially for highly
concurrent programs: it litters the code with write-back and fence
instructions. More efficient strategies for several specific data structures,
including queues [18] and hash tables [8, 56], have also been developed by
hand.

Friedman et al. [17] observed that many nonblocking operations begin with a
read-only “traversal” phase in which instrumentation can, with care, be safely
elided; applying this observation to the transform of Izraelevitz et al. leads
to substantially better performance in many cases, but the coding process is
no longer entirely mechanical. Ramalhete et al. [47] and Beadle et al. [1]
present nonblocking persistent software transactional memory (STM) systems,
but both have fundamental serial bottlenecks that limit scalability.

In this paper, we extend Montage to produce the first _general-purpose, high-
performance system for nonblocking persistence_. Our _nbMontage_ allows
programmers, in a straightforward way, to convert most wait-free or lock-free
linearizable concurrent data structures into fast, equivalent structures that
are lock-free and buffered durably linearizable. (Obstruction-free structures
can also be converted; they remain obstruction free.) Like its predecessor,
nbMontage requires every nonblocking update operation to linearize at a
compare-and-swap (CAS) instruction that is guaranteed, prior to its execution,
to constitute the linearization point if it succeeds. (Read-only operations
may linearize at a load.) Most nonblocking structures in the literature meet
these requirements.

Unlike its predecessor, nbMontage provides a wait-free sync. Where the
original system required all operations in epoch $e-1$ to complete before the
epoch could advance to $e+1$, nbMontage allows the fate of pending operations
to remain in limbo: in the wake of a crash or of continued crash-free
execution, an operation still pending at the end of $e-1$ may or may not be
seen, sometime later, to have linearized in that epoch. In addition, where the
original Montage required operations to accommodate “spurious” CAS failures
caused by epoch advance, nbMontage retries such CASes internally, without
compromising lock freedom. These changes were highly nontrivial. Among other
things, they required new mechanisms to stage (announce) pending updates;
distinguish, in recovery, between staged and linearized updates; indefinitely
delay (and reason about) the point at which an update is known to have
linearized; and avoid work at sync time for threads that have nothing to
persist.

We have applied nbMontage to Michael & Scott’s queue [42], Natarajan &
Mittal’s binary search tree [43], the rotating skip list of Dick et al. [14],
Michael’s hash table [40], and Shalev & Shavit’s extensible hash table [49].
All conversions were straightforward—typically less than 30 lines of code. By
persisting only essential data and avoiding writes-back and fences on the
critical path, nbMontage structures often approach or outperform not only
their equivalents in the original (blocking) Montage but also their transient
equivalents when data is placed (without any algorithmic changes) in slower,
nonvolatile memory.

Summarizing contributions:

  1. 1.

We introduce nbMontage, the first general system for nonblocking periodic
persistence.

  2. 2.

We tailor nbMontage’s API to the needs of nonblocking data structures. With
this new API, conversion of existing nonblocking structures for persistence is
entirely straightforward.

  3. 3.

We argue that nbMontage provides buffered durable linearizability and wait-
free sync for compatible data structures, while still preserving safety and
liveness.

  4. 4.

We compare the performance of nbMontage structures both to their original,
transient versions and to hand-crafted alternatives from the literature,
running on a recent Intel server with Optane NVM. Our results confirm
exceptional throughput, responsive sync, negligible overhead relative to the
original Montage, and reasonable recovery latency.

##  2 Related Work

The past decade has seen extensive work on persistent data structures, much of
it focused on B-tree indices for file systems and databases [51, 6, 55, 45,
30, 27, 32, 7, 3]. Other work has targeted queues [18], RB trees [53], radix
trees [31], and hash tables [56, 48, 44, 8].

In recent years, _durable linearizability_ has emerged as the standard
correctness criterion for such structures [29, 18, 56, 38]. This criterion
builds on the familiar notion of linearizability [25] for concurrent (non-
persistent) structures. A structure is said to be linearizable if, whenever
threads perform operations concurrently, the effect is as if each operation
took place, atomically, at some point between its call and return, yielding a
history consistent with the sequential semantics of the abstraction
represented by the structure. A persistent structure is said to be _durably
linearizable_ if (1) it is linearizable during crash-free execution, (2) each
operation persists (reaches a state that will survive a crash) at some point
between its call and return, and (3) the order of persists matches the
linearization order.

In addition to custom data structures, several groups have developed general-
purpose systems to ensure the failure atomicity of lock-based critical
sections [26, 4, 28, 34] or speculative transactions [52, 9, 5, 20, 12, 11,
39, 47, 21, 1, 46, 50, 33, 19]. Like the bespoke structures mentioned above,
all of these systems are durably linearizable—they ensure that an operation
has persisted before returning to the calling thread.

As noted in Section 1, nonblocking persistent structures can achieve failure
atomicity without the need for logging, since every reachable concrete state
corresponds to a well-defined abstract state. At the same time, while a lock-
based operation can easily arrange to linearize and persist in the same order
(simply by holding onto the locks needed by any successor operation), a
nonblocking operation becomes visible to other threads the moment it
linearizes. As a result, those other threads must generally take care to
ensure that anything they read has persisted before they act upon it. Writing
back and fencing read locations is a major source of overhead in the
mechanical transform of Izraelevitz et al. [29]. Friedman et al. [17] avoid
this overhead during the initial “traversal” phase of certain nonblocking
algorithms. David et al. [13] avoid redundant writes-back and fences in linked
data structures by _marking_ each updated pointer in one of its low-order
bits. A thread that persists the pointer can use a CAS to clear the bit,
informing other threads that they no longer need to do so.

In both blocking and nonblocking structures, the overhead of persistence can
be reduced by observing that not all data are semantically meaningful. In any
implementation of a set or mapping, for example, the items or key-value pairs
must be persistent, but the index structure can (with some effort) be
_rebuilt_ during recovery. Several groups have designed persistent B-trees,
lists, or hash tables based on this observation [55, 45, 7, 36].

Ultimately, however, any data structure or general-purpose system meeting the
strict definition of durable linearizability will inevitably incur the
overhead of at least one persistence fence in every operation. For highly
concurrent persistent structures, this overhead can easily double the latency
of every operation—potentially significantly increasing a program’s critical
path. Similar observations, of course, have applied to I/O operations since
the dawn of electronic computing, and are routinely addressed by completing
I/O in the background. For data structures held in NVM, _periodic persistence_
provides an analogous “backgrounding” strategy, allowing a structure to meet
the more relaxed requirements of _buffered_ durable
linearizability—specifically, the state recovered after a crash is guaranteed
to represent a prefix of the linearization order of pre-crash execution.

Nawab et al. [44] present a lock-based hash table, Dalí, that performs updates
only by pre-pending to per-bucket lists, thereby creating a revision history
(deletions are effected by inserting “anti-nodes”). A clever “pointer-
rotation” strategy records, for each bucket, the head nodes of the list for
each of the past few values of a global _epoch clock_. At the end of each
coarse-grain epoch, the entire cache is flushed. In the wake of a crash,
threads ignore nodes prepended to hash bucket lists during the two most recent
epochs. No other writes-back or fences are required. Cohen et al. [10] also
flush the cache at global epoch boundaries, but employ a clever system of _in-
cache-line-logging_ (InCLL) to retain the epoch number and beginning-of-epoch
value for every modified leaf-level pointer in a variant of the Masstree
structure [37]. In the wake of a crash, threads use the beginning-of-epoch
value for any pointer that was modified in the epoch of the crash.

Both Dalí and InCLL employ techniques that might be applicable in principle to
other data structures. To the best of our knowledge, however, the Montage
system of Wen et al. [54] is the only existing general-purpose system for
buffered durable linearizable structures. It also has the advantage of
persisting only semantically essential data. As presented, unfortunately, it
provides only limited support for nonblocking data structures, and its
attempts to advance the epoch clock can be arbitrarily delayed by stalled
worker threads. Our nbMontage resolves these limitations, allowing us to
provide a wait-free sync operation and to bound the amount of work that may be
lost on a crash. It also provides a substantially simpler API.

##  3 System Design

###  3.1 The Original Montage

As described in Section 1, semantically essential data in Montage resides in
_payload_ blocks in NVM. Other data may reside in transient memory. The
original system API [54] is designed primarily for lock-based data structures,
but also includes support for nonblocking operations (with blocking advance of
the persistence frontier). The typical operation is bracketed by calls to
begin_op and end_op. In between, reads and writes of payloads use special
_accessor_ (get and set) methods.

Internally, Montage maintains a slow-ticking _epoch clock_. In the wake of a
crash in epoch $e$, the Montage recovery procedure identifies all and only the
payloads in existence at the end of epoch $e-2$. It provides these, through a
parallel iterator, to the restarted application, which can then rebuild any
needed transient structures. Accessor methods allow payloads that were created
in the current epoch to be modified in place, but they introduce significant
complexity to the programming model.

Payloads are created and deleted with pnew and pdelete. These routines are
built on a modified version of the Ralloc [2] persistent allocator. In the
original Ralloc, a tracing garbage collector was used in the wake of a crash
to identify and reclaim free blocks. In the Montage version, epoch tags in
payloads are used to identify all and only those blocks created and not
subsequently deleted at least two epochs in the past. To allow a payload to
survive if a crash happens less than two epochs after a deletion, deletions
are implemented by creating _anti-nodes_. These are automatically reclaimed,
along with their corresponding payloads, after two epochs have passed.

To support nonblocking operations, the original Montage provides a CAS_verify
routine that succeeds only if it can do so in the same epoch as the preceding
begin_op. If CAS_verify fails, the operation will typically start over; before
doing so, it should call abort_op instead of end_op, allowing the system to
clean up without persisting the operation’s updates.

Regardless of persistence, nodes removed from a nonblocking structure
typically require some sort of _safe memory reclamation_ (SMR)—e.g., epoch-
based reclamation [16] or hazard pointers [41]—to delay the reuse of memory
until one can be sure that no thread still holds a transient reference. In
support of SMR, the original Montage provides a pretire routine that arranges
for the following end_op to create an anti-node. In the absence of crashes,
Montage will automatically reclaim the payload and its anti-node 2–3 epochs
after SMR calls pdelete. In the event of a crash, however, if two epochs have
elapsed since pretire, the existence of the anti-node allows the Montage
recovery procedure to avoid a memory leak by reclaiming the retired payload
even in the absence of pdelete. Significantly, since a still-active operation
will (in the original Montage) prevent the epoch from advancing far enough to
persist anything in its epoch, pretire can safely be called after the
operation has linearized, so long as it has not yet called end_op.

When a program needs to ensure that operation(s) have persisted (e.g., before
printing a confirmation on the screen or responding to a client over the
network), Montage allows it to invoke an explicit sync. The implementation
simply advances the epoch from $e$ to $e+2$ (waiting for operations in epochs
$e-1$ and $e$ to complete). The reason for the two-epoch convention, as
explained by the authors of Dalí [44], is to avoid the need for quiescence: a
thread can advance the epoch from $e$ to $e+1$ while other threads are still
completing operations that will linearize in $e$.

The key to buffered durable linearizability is to ensure that every operation
that updates payloads linearizes in the epoch with which those payloads are
tagged. Each epoch boundary then captures a prefix of the data structure’s
linearization order. Maintaining this consistency is straightforward for lock-
based operations. In the nonblocking case, CAS_verify uses a variant of the
double-compare-single-swap (DCSS) construction of Harris al. [22] (App. B) to
confirm the expected epoch and perform a conditional update, atomically.
Unfortunately, the fact that an epoch advance from $e$ to $e+1$ must wait for
operations in $e-1$ means that even if a data structure remains nonblocking
during crash-free execution, the progress of persistence itself is
fundamentally blocking. This in turn implies that calls to sync are blocking,
and that it is not possible, _a priori_ , to bound the amount of work that may
be lost on a crash.

class PBlk; // Base class of all Payload classes class Recoverable // Base
class of all persistent objects template ¡class payload_type¿ payload_type*
pnew(…); // Create a payload block void pdelete(PBlk*); // Delete a payload;
should be called only when safe void pdetach(PBlk*); // Mark payload for
retirement if operation succeeds void sync(); // Persist all operations that
happened before this call vector¡PBlk*¿* recover(); // Recover and return all
recovered payloads void abort_op(); // Optional routine to abandon current
operation ; template ¡class T¿ class CASObj // Atomic CAS object that provides
load and CAS /* Epoch-verifying linearization method: */ bool lin_CAS(T
expected, T desired) begin_op(); // write back or delete old payloads as
necessary; tag new ones while (1) // iterations can be limited for liveness …
// main body of DCSS switch (DCSS_status) case COMMITTED: end_op(); // clean
up metadata return true; case FAILED: abort_op(); // untag payloads and clear
retirements; clean up metadata return false; case EPOCH_ADVANCED: reset_op();
// update and reuse payloads and retirements /* Non-verifying atomic methods:
*/ T load(); void store(T desired); bool CAS(T expected, T desired); ;

Figure 1: C++ API of nbMontage, largely inherited from the original Montage.

The key observation of our own work on nbMontage is that since CAS_verify will
succeed only in the expected epoch, any nonblocking operation that lags behind
an epoch advance is doomed to fail and retry in a subsequent epoch. There is
no need to wait for it to resume, explicitly fail, and unregister from the old
epoch in abort_op. Unfortunately, the waiting mechanism is deeply embedded in
the original Montage implementation—e.g., in the implementation of pretire, as
noted above. Overall, there are four nontrivial issues that must be addressed
to build nbMontage:

(Sec. 3.3)

Every operation must stage its pending updates (both new and to-be-deleted
payloads) before reaching its linearization point, so that an epoch advance
can help it to persist even if it stalls immediately after the linearization
point.

(Sec. 3.4)

The recovery procedure must be able to distinguish an epoch’s “real” payloads
and anti-nodes from those that may have been staged for an operation that
failed due to a CAS conflict or epoch advance.

(Sec. 3.5)

The implementation must accommodate an arbitrary number of epochs in which
operations have not yet noticed that they are doomed to fail and retry in a
new epoch.

(Sec. 3.6)

An epoch advance must be able to find and persist any blocks (payloads or
anti-nodes) that were created in the previous epoch but have not yet been
written back and fenced. If sync is to be fast, this search must avoid
iterating over all active threads.

###  3.2 nbMontage API

As shown in Figure 3.1, the nbMontage API reflects three major changes. First,
because the epoch can now advance from $e$ to $e+1$ even when an operation is
still active in $e-1$, we must consider the possibility that a thread may
remove a payload from the structure, linearize, and then stall. If a crash
occurs two epochs later, we must ensure that the removed payload is deleted
during post-crash recovery, to avoid a memory leak: post-linearization pretire
no longer suffices. Our nbMontage therefore replaces pretire with a pdetach
routine that must be used to register to-be-deleted payloads _prior_ to
linearization. As in the original Montage, deletion during crash-free
execution is the responsibility of the application’s SMR.

Second, again because of nonblocking epoch advance, nbMontage requires that
payloads visible to more than one thread be treated as immutable. Updates
always entail the creation of new payloads; get and set accessors are
eliminated.

Third, in a dramatic simplification of the API, nbMontage replaces the
original begin_op, end_op, and CAS_verify with a new lin_CAS (linearizing CAS)
routine. (The abort_op routine is also rolled into lin_CAS, but remains in the
API so operations can call it explicitly if they choose, for logical reasons,
to start over.) When lin_CAS is called, all payloads created by the calling
thread since its last completed operation (and not subsequently deleted) will
be tagged with the current epoch, $e$. All anti-nodes stemming from pdetach
calls made since the last completed operation (and not corresponding to
payloads created in that interval) will likewise be tagged with $e$. The
lin_CAS will then attempt a DCSS and, if the current epoch is still $e$ and
the specified location contains the expected value, the operation will
linearize, perform the internal cleanup previously associated with end_op, and
return true. If the DCSS fails because of a conflicting update, lin_CAS will
perform the internal cleanup associated with abort_op and return false. If the
DCSS fails due to epoch advance, lin_CAS will update the operation’s payloads
and anti-nodes to the new epoch and retry. By ensuring, internally, that the
epoch never advances unless some thread has completed an operation (App. C),
nbMontage can ensure that the retry loop is bounded.

Programmers using nbMontage are expected to obey the following constraints:

  1. 1.

Each nbMontage data structure $R$ must be designed to be nonblocking and
linearizable during crash-free execution when nbMontage is disabled.
Specifically, $R$ must be linearizable when (a) pnew and pdelete are ordinary
new and delete; (b) pdetach and sync are no-ops; and (c) CASObj is std::atomic
and lin_CAS is ordinary CAS.

  2. 2.

Every update operation of $R$ linearizes in a pre-identified lin_CAS—one that
is guaranteed, before the call, to contain the operation’s linearization point
if the lin_CAS succeeds. Any operation that conflicts with or depends upon
this update must access the lin_CAS’s target location. Read-only operations
may linearize at a load.

  3. 3.

Once attached to a structure (made visible to other threads), a payload is
immutable. Changes to a structure are made only by adding and removing
payloads.

  4. 4.

The semantics of each operation are fully determined by the set of payloads
returned by pnew and/or passed to pdetach prior to lin_CAS.

Pseudocode for nbMontage’s core classes and methods appears in Figure 2; these
are discussed in more detail in the following subsections. Appendix A presents
the changes required to port Maged Michael’s lock-free hash table [40] to
nbMontage.

###  3.3 Updates to Payloads

To allow the epoch clock to advance without blocking, nbMontage abandons in-
place update of payloads. It interprets pdetach as requesting the creation of
an _anti-node_. An anti-node shares an otherwise unique ID with the payload
being detached. Newly created payloads and anti-nodes are buffered until the
next lin_CAS in their thread. If the lin_CAS succeeds, the buffered nodes will
be visible to epoch advance operations, and can be persisted even if the
creating thread has stalled.

In the pseudocode of Figure 2, calls to pnew and pdetach are held in the
allocs and detaches containers. Anti-nodes are created, and both payloads and
anti-nodes are tagged, in begin_op (lines 2–2, called from within lin_CAS). If
the lin_CAS fails due to conflict, abort_op resets pnew-ed payloads so they
can be reused in the operation’s next attempt (lines 2–2); it also withdraws
pdetach requests, allowing the application to detach something different the
next time around (lines 2–2). If attempts occur in a loop (as is common), the
programmer may call pnew outside the loop and pdetach inside, as shown in
Figure Fast Nonblocking Persistence for Concurrent Data Structures111This work
was supported in part by NSF grants CCF-1717712, CNS-1900803, CNS-1955498, and
by a Google Faculty Research award. (App. A). If an operation no longer needs
its pnew-ed payloads (e.g., after a failed insertion), it may call pdelete to
delete them; this automatically erases them from allocs (line 2). The internal
reset_op routine serves to update and reuse both payloads and anti-nodes in
anticipation of retrying a DCSS that fails due to epoch advance (lines 2–2).

###  3.4 CAS and Recovery

The implementation of lin_CAS employs an array of persistent _descriptors_ ,
one per thread. These form the basis of the DCSS construction [22] (App. B).
Each descriptor records CAS parameters (the old value, new value, and CAS
object); the epoch in which to linearize; and the status of the CAS itself (in
progress, committed, or failed—lines 2–2). After a crash, the recovery
procedure must be able to tell when a block in NVM (a payload or anti-node)
appears to be old enough to persist, but corresponds to an operation that did
not commit. Toward that end, each block contains a 64-bit field that encodes
the thread ID and a monotonic serial number; together, these constitute a
unique _operation ID_ (lines 2 and 2). At the beginning of each operation
attempt, begin_op updates the descriptor, incrementing its serial number (line
2). Previous uses of the descriptor with smaller serial numbers are regarded
as having committed; blocks corresponding to those versions remain valid
unless they are deleted or reinitialized (lines 2, 2, and 2). Deleting or
reinitializing a persistent block resets its epoch to zero and registers it to
be written back in the current epoch (lines 2–2). This ensures that those
resets persist, in begin_op, _before the next update to the descriptor_ (lines
2–2). During an epoch advance from $e$ to $e+1$, the descriptors of operations
in $e-1$ are written back (at line 2) to ensure that their statuses reach NVM
before the update of the global epoch clock.

Informally, an nbMontage payload is said to be _in use_ if it has been created
and not yet detached by linearized operations. Identifying such payloads
precisely is made difficult by the existence of _pending_ operations—those
that have started but not yet completed, and whose effects may not yet have
been seen by other threads. In the wake of a crash in epoch $e$, nbMontage
runs through the Ralloc heap, assembling a set of potentially allocated blocks
and finding all CAS descriptors (identified by their type fields—lines 2 and
2). By matching the serial numbers and thread IDs of blocks and descriptors,
the nbMontage-internal recovery procedure identifies all and only the payloads
that are known, as of the crash, to have been in use at the end of epoch
$e-2$. Specifically, if block $B$ has thread ID $t$, serial number $s$, and
epoch tag $f\\!$, nbMontage will recover $B$ if and only if

  1. 1.

$0<f\leq e-2$;

  2. 2.

$(s<\mathtt{descs}[t].\mathtt{sn})\lor(s=\mathtt{descs}[t].\mathtt{sn}\land\mathtt{descs}[t].\mathtt{status}=\mathtt{COMMITTED})$;
and

  3. 3.

if $B$ is a payload, it has not been canceled by an in-use anti-node.

Once the in-use blocks have been identified, nbMontage returns them to a data-
structure-specific recovery routine that rebuilds any needed transient state,
after which the state of the structure is guaranteed to reflect some valid
linearization of pre-crash execution through the end of epoch $e-2$.

1

Struct  _CircBuffer_

2 uint64 cap

3 atomic¡uint64¿ pushed,popped

4 PBlk* blks[cap]

5 Function  _push(PBlk* item)_

6 cpush=pushed.load()

7 cpop=popped.load()

8 if cpush$\leq$cpop+cap then

9 clwb(blks[cpop%cap])

10 popped.CAS(cpop,cpop+1)

11

12 blks[cpush%cap]=item

pushed.store(cpush+1)

// single producer

13

14 Function  _pop_all()_

15 cpop=popped.load()

16 cpush=pushed.load()

17 if cpop==cpush then

18 return

19

20 foreach i from cpop to cpush do

21 break if i%cap reaches cpop%cap twice

22 clwb(blks[i%cap])

23

24 popped.CAS(cpop,cpush)

25

26

27 atomic¡uint64¿ global_epoch

28 Mindicator mindi

29 thread_local uint64 e_curr,e_last

30 thread_local vector¡PBlk*¿ allocs,detaches

31 thread_local int tid

int thd_cnt

// number of threads

32 CircBuffer TBP[thd_cnt][4]

33 Struct  _Desc_

34 uint64 old,new,epoch=0

35 uint64 type=DESC

36 uint64 tid_sn=0

// 64 bits for ref to CASObj

// 64 for cnt, with last 2 for status

37 atomic¡uint128¿ r_c_s

38 Function  _reinit(uint64 e)_

39 tid_sn++

40 r_c_s.store(0)

41 epoch=e

42

43

44 Struct  _PBlk_

45 (void* vtable)

46 PBlk* anti=NULL

47 uint64 epoch=0

48 uint64 type={PAYLOAD,ANTI}

49 uint64 tid_sn=0,blk_uid=0

50 Function  _setup(uint64 t,Desc* desc,uint64 e)_

51 type=t

52 epoch=desc?0:desc.epoch

53 tid_sn=desc?0:desc.tid_sn

54 TBP[tid][e%4].push(this)

55

56 Function  _destructor()_

57 epoch=0

58 clwb(this)

59

60Desc descs[thd_cnt]

61 vector¡PBlk*¿ TBF[thd_cnt][4]

62 Function  _pdelete(PBlk* pblk)_

63 e=global_epoch.load()

allocs.erase(pblk)

// no-op if pblk not in allocs

64 TBF[tid][e+1].insert(pblk$\rightarrow$anti)

65 TBF[tid][e].insert(pblk)

66

67 Function  _begin_op(bool reset=false)_

68 e_curr=global_epoch.load()

69 if e_last<e_curr then

70 TBP[tid][e_last%4].pop_all()

71 clwb(descs[t])

72 update t’s val to e_curr in mindi

73

74 descs[tid].reinit(e_curr)

75 for i from e_last-1 to min(e_last+1,e_curr-2) do

76 delete all items in TBF[tid][i%4]

77 sfence

78

79 foreach r in detaches do

80 if !reset then // default branch

81 allocate an anti-node anti for r

82 r$\rightarrow$anti=anti

83 r$\rightarrow$anti$\rightarrow$blk_uid=r$\rightarrow$blk_uid

84

85 r$\rightarrow$anti$\rightarrow$setup(ANTI,descs[tid],e_curr)

86

87 foreach p in allocs do

88 p$\rightarrow$setup(PAYLOAD,descs[tid],e_curr)

89

90

91Function  _end_op()_

92 detaches.clear()

93 allocs.clear()

94 e_last=e_curr

95 e_curr=0

96

97Function  _abort_op(bool reset=false)_

98 if reset then // to reuse anti-nodes

99 foreach r in detaches do

100 r$\rightarrow$anti$\rightarrow$setup(ANTI,NULL,e_curr)

101

102

103 else // default branch:delete anti-nodes

104 foreach r in detaches do

105 delete(r$\rightarrow$anti)

106 r$\rightarrow$anti=NULL

107

108 detaches.clear()

109

110 foreach p in allocs do

111 p$\rightarrow$setup(PAYLOAD,NULL,e_curr)

112

113 e_last=e_curr

114 e_curr=0

115

116Function  _reset_op()_

117 abort_op(true)

118 begin_op(true)

119

120 Function  _advance()_

121 e=global_epoch.load()

122 foreach t in mindi whose val==e-1 do

123 TBP[t][(e-1)%4].pop_all()

124 clwb(descs[t])

125 update t’s val to e in mindi

126

127 sfence

128 if some op linearized in e-1 or e then

129 global_epoch.CAS(e,e+1)

130

131

Figure 2: nbMontage pseudocode.

###  3.5 Buffering

Persistent blocks created or deleted in a given epoch will be recorded in
thread- and epoch-specific to-be-persisted (TBP) and to-be-freed (TBF)
containers. Every thread maintains four statically allocated instances of each
(Fig. 2, lines 2 and 2).

TBPs are fixed-size circular buffers. When a buffer is full, its thread
removes and writes back a block before inserting a new one. In the original
version of Montage, epoch advance always occurs in a dedicated background
thread (the sync operation handshakes with this thread). As part of the
advance from epoch $e$ to $e+1$, the background thread iterates over all
worker threads $t$, waits for $t$ to finish any active operation in $e-1$,
extracts all blocks from TBP$[t][(e-1)\\!\\!\\!\mod 4]$, and writes those
blocks back to memory.

Insertions and removals from a TBP buffer never occur concurrently in the
original version of Montage. In nbMontage, however, an operation that is
lagging behind may not yet realize that it is doomed to retry, and may still
be inserting items into the buffer when another thread (or several other
threads!) decide to advance the epoch. The lagging thread, moreover, may even
be active in epoch $e-1-4k$, for some $k>0$ (lines 2 and 2). This concurrency
implies that TBPs need to support single-producer-multiple-consumers (SPMC)
concurrency. Our implementation of the SPMC buffer (lines 2–2) maintains two
monotonic counters, pushed and popped. To insert an item, a thread uses store
to increment pushed. To remove some item(s), a thread uses CAS to increase
popped. For simplicity, the code exploits the fact that duplicate writes-back
are semantically harmless: concurrent removing threads may iterate over
overlapping ranges (lines 2–2).

TBFs are dynamic-size, thread-unsafe containers implemented as vectors (line
2), as in the original Montage. Although deletion must respect epoch ordering,
it can be performed lazily during crash-free execution, with each thread
responsible for the blocks in its own TBFs. In begin_op, _after it has updated
its descriptor_ , thread $t$ deletes blocks in TBF$[t][i\\!\\!\mod 4]$, for
$i\in[e_{\mathit{last}}-1,\min(e_{\mathit{last}}+1,e_{\mathit{curr}}-2)]$,
where $e_{\mathit{last}}$ is the epoch of $t$’s last operation and
$e_{\mathit{curr}}$ is the epoch of its current operation (lines 2–2).

###  3.6 Epoch Advance

To make sync nonblocking, we first decentralize the original epoch advance in
Montage so that instead of making a request of some dedicated thread, every
thread is now able to advance the epoch on its own. In the worst case, such an
epoch advance may require iterating over the TBP buffers of all threads in the
system. In typical cases, however, many of those buffers may be empty. To
reduce overhead in the average case, we deploy a variant of Liu et al.’s
_mindicator_ [35] to track the oldest epoch in which any thread may still have
an active operation. Implemented as a wait-free, fixed-size balanced tree, our
variant represents each thread and its current epoch as a leaf. An ancestor in
the tree indicates the minimum epoch of all nodes in its subtree. When thread
$t$ wishes to advance the epoch from $e$ to $e+1$, it first checks to see
whether the root of the mindicator is less than $e$. If so, it scans up the
tree from its own leaf until it finds an ancestor with epoch $<e$. It then
reverses course, traces down the tree to find a lagging thread, persists its
descriptor and any blocks in the requisite TBP container, and repeats until
the root is at least $e$. When multiple threads call sync concurrently, this
nearest-common-ancestor strategy allows the work of persistence to be
effectively parallelized. Experiments described in Section 5.3 confirm that
our use of the mindicator, together with the lazy handling of TBF buffers
(Section 3.5), leads to average sync times on the order of a few microseconds.

##  4 Correctness

We argue that nbMontage preserves the linearizability and lock freedom of a
structure implemented on top of it, and adds buffered durable linearizability.
We also argue that advances of the persistence frontier in nbMontage are wait
free.

###  4.1 Linearizability

######  Theorem 1.

Suppose that $R$ is a data structure obeying the constrains of Section 3.4,
running on nbMontage, and that $K$ is realizable concrete history of $R$. $K$
is linearizable.

###### Proof (sketch).

The pnew, pdelete, and lin_CAS routines of nbMontage have the same semantics
as new, delete, and CAS calls in the original data structure. The pdetach
routine has no semantic impact on crash-free execution: it simply ensures that
a block whose removal has linearized will be reclaimed in post-crash recovery.
The sync routine, similarly, has no semantic impact—with no parameters and no
return values, it can linearize anywhere. If the instructions comprising each
call to pnew, pdelete, pdetach, sync, and lin_CAS in a concrete nbMontage
history are replaced with those of new, delete, no-op, no-op, and CAS,
respectively, the result will be a realizable concrete history of the original
data structure. Since that history is linearizable, so is the one on
nbMontage. ∎

###  4.2 Buffered Durable Linearizability

As is conventional, we assume that each concurrent data structure implements
some abstract data type. The semantics of such a type are defined in terms of
legal _abstract sequential histories_ —sequences of operations (request-
response pairs), with their arguments and return values. We can define the
_abstract state_ of a data type, after some finite sequential history $S$, as
the set of possible extensions to $S$ permitted by the type’s semantics. In a
_concurrent_ abstract history $H$, invocations and responses may be separated,
and some responses may be missing, in which case the invocation is said to be
_pending_ at end of $H.$ $H$ is said to be _linearizable_ if (1) there exists
a history $H^{\prime}$ obtained by dropping some subset of the pending
invocations in $H$ and adding matching responses for the others, and (2) there
exists a sequential history $S$ that is equivalent to $H^{\prime}$ (same
invocations and responses) and that respects both the _real-time_ order of
$H^{\prime}$ and the semantics of the abstract type. $S$ is said to be a
_linearization of_ $H.$

Suppose now that $R$ is a linearizable nonblocking implementation of type $T,$
and that $r$ is a concrete state of $R$—the bits in memory at the end of some
concrete (instruction-by-instruction) history $K$. For $R$ to be correct there
must exist a mapping $\mathcal{M}$ such that for any such $K$ and $k,$
$\mathcal{M}(k)$ is the abstract state that results from performing, in order,
the abstract operations corresponding to concrete operations that have
linearized in $K$.

A structure $R$ is _buffered durably linearizable_ if post-crash recovery
always results in some concrete state $s$ that is justified by some prefix $P$
of pre-crash concrete execution—that is, there exists a linearization $S$ of
the abstract history corresponding to $P$ such that $\mathcal{M}(s)$ is the
abstract state produced by $S$.

Consider again the 4 constraints listed at the end of Section 3.2 for data
structures running on nbMontage. Elaborating on constraints 3 and 4, we use
$r|_{p}$ to denote the set of payloads that were created and not yet detached
by the operations that generated $r$. This allows us to recast constraint 4
and to add an additional constraint:

  1. 4′.

There exists a mapping $\mathcal{Q}$ from sets of payloads to states of $T$
such that for any concrete state $r$ of $R$,
$\mathcal{M}(r)=\mathcal{Q}(r|_{p})$.

  2. 5.

The recovery procedure of $R$, given a set of in-use payloads $p$, constructs
a concrete state $s$ such that $\mathcal{M}(s)=\mathcal{Q}(p)$.

######  Theorem 2.

If a crash happens in epoch $e$, $R$ will recover to a concrete state $s$ such
that $\mathcal{M}(s)$ is the abstract state produced by some linearization $S$
of the abstract history $H$ comprising pre-crash execution through the end of
epoch $e-2$. In other words, $R$ is buffered durably linearizable.

###### Proof (sketch).

For purposes of this proof, it is convenient to say that an update operation
that successfully commits the descriptor of its lin_CAS linearizes on the
_preceding load_ of the global epoch clock—the one that double-checks the
clock before commit. Under this interpretation, if $r$ is the concrete state
of memory at the end of epoch $e-2$, we can say that $\mathcal{M}(r)$ reflects
a sequential history containing all and only those operations that have
committed their descriptors (line 8 in Fig. 8 of App. B) by the end of the
epoch. But this is not the only possible linearization of execution to that
point! In particular, any operation that has loaded global_epoch (line 2 in
Fig. 2), initialized its descriptor (line 2 of Fig. 2), and installed that
descriptor in a CASObj (line 8 of Fig. 8) but has not yet committed the
descriptor may “linearize in the past” (i.e., in epoch $e-2$) if it _or
another, helping thread_ commits the descriptor in the future. When a crash
occurs in epoch $e$, any such retroactively linearized operations will see
their payloads and anti-nodes included in the state $s$ recovered from the
crash. $\mathcal{M}(s)$ will therefore correspond, by constraint 5, to the
linearization of execution through the end of epoch $e-2$ that includes all
and only those pending operations that have linearized by the time of the
crash. Crucially, if operation $b$ depends on operation $a$, in the sense that
$a$ has completed in any extension of $H$ in which $b$ has completed, then, by
constraint 2 of Section 3.2, the helping mechanism embodied by lin_CAS ensures
that if $b$’s payloads and anti-nodes are included in $s$, $a$’s are included
also. ∎

###  4.3 Wait-free Persistence

######  Theorem 3.

The epoch advance in nbMontage is wait free.

###### Proof (sketch).

As shown in Fig. 2, an epoch advance from $e$ to $e+1$ repeatedly finds a
thread $t$ that may still be active in $e-1$ (line 2), persists the contents
of its TBP container and its descriptor (lines 2–2), and updates its
mindicator entry. In the worst case, identifying all threads with blocks to be
persisted requires time $O(T)$, where $T$ is the number of threads, since the
total size of the mindicator is roughly $2T$ nodes. Since each TBP container
has bounded size, all the data of a thread can be persisted in $O(1)$ time.
Mindicator updates, worst case, take $O(T\log T)$.

Since sync advances the epoch at most twice, it, too, is wait free. ∎

###  4.4 Lock freedom

######  Theorem 4.

nbMontage preserves lock freedom during crash free execution.

###### Proof (sketch).

Given Theorem 3, the only additional loop introduced by nbMontage is the
automatic retry that occurs inside lin_CAS when the epoch has advanced. While
this loop precludes wait freedom, we can (with a bit of effort—see App. C)
arrange to advance the epoch from $e$ to $e+1$ only if some update operation
has linearized in epoch $e-1$ or $e$ (line 2 of Fig. 2). This suffices to
preserve lock freedom. As a corollary, a data structure that is obstruction
free remains so when persisted with nbMontage. ∎

##  5 Experimental Results

To confirm the performance benefits of buffering, we constructed nbMontage
variants of Michael & Scott’s queue [42], Natarajan & Mittal’s binary search
tree [43], the rotating skip list of Dick et al. [14], Michael’s chained hash
table [40], and the resizable hash table of Shalev & Shavit [49]. Mappings
keep their key-value pairs in payloads and their index structures in transient
memory. The queue uses payloads to hold values and their order. Specifically,
between its two loads of the queue tail pointer, the euqueue operation calls
fetch_add on a global counter to obtain a serial number for the to-be-inserted
value. We benchmarked those data structures and various competitors on several
different workloads. Below are the structures and systems we tested:

Montage and nbMontage –

as described in previous sections.

Friedman –

the persistent lock-free queue of Friedman et al. [18].

Izraelevitz and NVTraverse –

the N&M tree, the rotating skip list, and Michael’s hash table persisted using
Izraelevitz’s transform [29] and NVTraverse transform [17], respectively.

SOFT and NVMSOFT–

the lock-free hash table of Zuriel et al. [56], which persists only semantic
data. The original SOFT keeps a full copy in DRAM, while NVMSOFT is modified
to keep and access values only in NVM. Neither supports update on existing
keys.

CLevel –

The persistent lock-free hash table of Chen et al. [8].

Dalí –

the lock-based buffered durably linearizable hash table of Nawab et al. [44].

DRAM (T) and NVM (T) –

as a baseline for comparison, these are unmodified transient versions of our
various data structures, with data located in DRAM and NVM, respectively.

###  5.1 Configurations

We configured Montage and nbMontage with 64-entry TBP buffers and an epoch
length of 10 ms. In practice, throughput is broadly insensitive to TBP size,
and remains steady with epochs as short as 100 µs. All experiments were
conducted on an Intel Xeon Gold 6230 processor with 20 physical cores and 40
hyperthreads, six 128 GB Optane Series 100 DIMMs, and six 32 GB DRAMs, running
Fedora 30 Kernel 5.3.7 Linux Server. Threads are placed first on separate
physical cores and then on hyperthreads. NVM is configured through the dax-
ext4 file system in “App Direct” mode.

All experiments use JEMalloc [15] for transient allocation and Ralloc [2] for
persistent allocation, with the exception of CLevel, which requires the
allocator from Intel’s PMDK. All chained hash tables have 1 million buckets.
The warm-up phase for mappings inserts 0.5 M key-value pairs drawn from a key
space of 1 M keys. Queues are initialized with 2000 items. Unless otherwise
specified, keys and values are strings of 32 and 1024 bytes, respectively. We
report the average of three trials, each of which runs for 30 seconds. All
source code for nbMontage and the experiments will be made available before
the date of the conference.

###  5.2 Throughput

Results for queues, binary search trees, skip lists, and hash tables appear in
Figures 3–4. The nbMontage versions of the M&S queue, N&M tree, rotating skip
list, and Michael hash table outperform most persistent alternatives by a
significant margin—up to 2$\times$ faster than Friedman et al.’s queue,
1.3–4$\times$ faster than NVTraverse and Izraelevitz et al.’s transform, and
3–14$\times$ faster than CLevel and Dalí. Significantly, nbMontage achieves
almost the same throughput as Montage. SOFT and NVMSOFT are the only
exceptions: the former benefits from keeping a copy of its data in DRAM; both
benefit from clever internal optimizations. The DRAM copy has the drawback of
forgoing the extra capacity of NVM; the optimization has the drawback of
precluding atomic update of existing keys. While the transient S&S hash table
(DRAM (T)-SS in Fig. 4) is significantly slower than the transient version of
Michael’s hash table (DRAM (T)), the throughput of the Montage version
(nbMontage-SS) is within 65% of the transient version and still faster than
all other pre-existing persistent options other than SOFT and NVMSOFT.

(a) Queues—1:1 push:pop (b) Binary search trees—2:1:1 get:insert:remove

(c) Skip lists—2:1:1 get:insert:remove

Figure 3: Throughput of concurrent queues, binary search trees, and skip
lists.

(a) 2:1:1 get:insert:remove (b) 18:1:1 get:insert:remove

Figure 4: Hash table throughput. Options in the left column of the key are all
variants of Michael’s nonblocking algorithm.

In another experiment (not shown in the figures), we compared Michael’s hash
table on nbMontage with chained hash tables built with the OneFile [47] and
QSTM [1] persistent STM systems. Since these systems are word-based and do not
work well with large blocks, in this experiment we used 64-bit integers as
keys and values. While the STM systems do not scale to even modest thread
counts, nbMontage scales extremely well, running up to 30$\times$ faster than
OneFile and 60$\times$ faster than QSTM at 40 threads.

###  5.3 Overhead of Sync

To assess the efficacy of nonblocking epoch advance and of our mindicator
variant, we measured the latency of sync and the throughput of code that calls
sync frequently. Specifically, using nbMontage version of Michael’s hash
table, on the (2:1:1 get:insert:remove) workload, we disabled the periodic
epoch advance performed by a background thread and had each worker call sync
explicitly.

Average sync latency is shown in Figure 6 for various thread counts and
frequencies of calls, on both nbMontage and its blocking predecessor. In all
cases, nbMontage completes the typical sync in 1–40 µs. In the original
Montage, however, sync latency never drops below 5 µs, and can be as high as
1.3 ms with high thread count and low frequency.

Hash table throughput as a function of sync frequency is shown in Figure 6 for
40 threads running on Montage and nbMontage. For comparison, horizontal lines
are shown for various persistent alternatives (none of which calls sync).
Interestingly, nbMontage is more than 2$\times$ faster than CLevel even when
sync is called in every operation, and starts to outperform NVTraverse once
there are more than about 10 operations per sync.

Figure 5: Average latency of sync on hash tables.

Figure 6: Throughput of hash tables with a sync every $x$ operations on
average (log-scale $x$-axis).

###  5.4 Recovery

To assess recovery time, we initialized the nbMontage version of Michael’s
hash table with 1–32 M 1-KB elements, leading to a total payload footprint of
1–32 GB. With one recovery thread, nbMontage recovered the 1 GB data set in
1.4 s and the 32 GB data set in 103.8 s (22.2 s to retrieve all in-use blocks;
81.6 s to insert them into a fresh hash table). Eight recovery threads
accomplished the same tasks in 0.3 s and 17.9 s. These times are all within
0.5 s of recovery times on the original Montage.

##  6 Conclusions

To the best of our knowledge, nbMontage is the first general-purpose system to
combine buffered durable linearizability with a simple API for nonblocking
data structures and nonblocking progress of the persistence frontier.
Nonblocking persistence allows nbMontage to provide a very fast wait-free sync
routine and to strictly bound the work that may be lost on a crash. Lock-free
and wait-free structures, when implemented on nbMontage, remain lock free;
obstruction-free structures remain obstruction free.

Experience with a variety of nonblocking data structures confirms that they
are easy to port to nbMontage, and perform extremely well—better in most cases
than even hand-built structures that are strictly durably linearizable. Given
that programmers have long been accustomed to sync-ing their updates to file
systems and databases, a system with the performance and formal guarantees of
nbMontage appears to be of significant practical utility. In ongoing work, we
are exploring the design of a hybrid system that supports both lock-based and
nonblocking structures, with nonblocking persistence in the absence of lock-
based operations. We also hope to develop a buffered durably linearizable
system for object-based software transactional memory, allowing persistent
operations on multiple data structures to be combined into failure-atomic
transactions.

## References

  * [1] H. A. Beadle, W. Cai, H. Wen, and M. L. Scott.  Nonblocking persistent software transactional memory.  In 27th Intl. Conf. on High Performance Computing, Data, and Analytics (HiPC), pages 283–293, Dec. 2020.
  * [2] W. Cai, H. Wen, H. A. Beadle, C. Kjellqvist, M. Hedayati, and M. L. Scott.  Understanding and optimizing persistent memory allocation.  In 19th Intl. Symp. on Memory Management (ISMM), June 2020.
  * [3] H. Cha, M. Nam, K. Jin, J. Seo, and B. Nam.  B3-tree: Byte-addressable binary B-tree for persistent memory.  ACM Trans. on Storage, 16(3):17:1–17:27, July 2020.
  * [4] D. R. Chakrabarti, H.-J. Boehm, and K. Bhandari.  Atlas: Leveraging locks for non-volatile memory consistency.  In ACM Conf. on Object Oriented Programming Systems Languages & Applications (OOPSLA), pages 433–452, Portland, OR, Oct. 2014.
  * [5] A. Chatzistergiou, M. Cintra, and S. D. Viglas.  REWIND: Recovery write-ahead system for in-memory non-volatile data-structures.  Proc. of the VLDB Endowment, 8(5):497–508, Jan. 2015.
  * [6] S. Chen and Q. Jin.  Persistent B+-trees in non-volatile main memory.  Proc. of the VLDB Endowment, 8(7):786–797, Feb. 2015.
  * [7] Y. Chen, Y. Lu, K. Fang, Q. Wang, and J. Shu.  uTree: A persistent B+-tree with low tail latency.  Proc. of the VLDB Endowment, 13(11):2634–2648, Aug. 2020.
  * [8] Z. Chen, Y. Huang, B. Ding, and P. Zuo.  Lock-free concurrent level hashing for persistent memory.  In Usenix Annual Technical Conf. (ATC), pages 799–812, July 2020\.
  * [9] J. Coburn, A. M. Caulfield, A. Akel, L. M. Grupp, R. K. Gupta, R. Jhala, and S. Swanson.  NV-Heaps: Making persistent objects fast and safe with next-generation, non-volatile memories.  In 16th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 105–118, Newport Beach, CA, 2011\.
  * [10] N. Cohen, D. T. Aksun, H. Avni, and J. R. Larus.  Fine-grain checkpointing with in-cache-line logging.  In 24th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 441–454, Providence, RI, USA, 2019.
  * [11] N. Cohen, D. T. Aksun, and J. R. Larus.  Object-oriented recovery for non-volatile memory.  Proc. of the ACM on Programming Languages, 2(OOPSLA):153:1–153:22, Oct. 2018.
  * [12] A. Correia, P. Felber, and P. Ramalhete.  Romulus: Efficient algorithms for persistent transactional memory.  In 30th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 271–282, Vienna, Austria, July 2018.
  * [13] T. David, A. Dragojević, R. Guerraoui, and I. Zablotchi.  Log-free concurrent data structures.  In Usenix Annual Technical Conf. (ATC), pages 373–386, Boston, MA, July 2018.
  * [14] I. Dick, A. Fekete, and V. Gramoli.  A skip list for multicore.  Concurrency and Computation: Practice and Experience, 29(4), May 2016.
  * [15] J. Evans.  A scalable concurrent malloc (3) implementation for FreeBSD.  In BSDCan Conf., Ottawa, ON, Canada, May 2006.
  * [16] K. Fraser.  Practical Lock-Freedom.  PhD thesis, King’s College, Univ. of Cambridge, Sept. 2003.  Published as Univ. of Cambridge Computer Laboratory technical report #579, February 2004. www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf.
  * [17] M. Friedman, N. Ben-David, Y. Wei, G. E. Blelloch, and E. Petrank.  NVTraverse: In NVRAM data structures, the destination is more important than the journey.  In 41st ACM Conf. on Programming Language Design and Implementation (PLDI), pages 377–392, London, UK, 2020.
  * [18] M. Friedman, M. Herlihy, V. Marathe, and E. Petrank.  A persistent lock-free queue for non-volatile memory.  In 23rd ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 28–40, Vienna, Austria, 2018.
  * [19] K. Genç, M. D. Bond, and G. H. Xu.  Crafty: Efficient, HTM-compatible persistent transactions.  In 41st ACM Conf. on Programming Language Design and Implementation (PLDI), pages 59–74, June 2020.
  * [20] E. R. Giles, K. Doshi, and P. Varman.  SoftWrAP: A lightweight framework for transactional support of storage class memory.  In 31st Symp. on Mass Storage Systems and Technologies (MSST), pages 1–14, Santa Clara, CA, May–June 2015.
  * [21] J. Gu, Q. Yu, X. Wang, Z. Wang, B. Zang, H. Guan, and H. Chen.  Pisces: A scalable and efficient persistent transactional memory.  In Usenix Annual Technical Conf. (ATC), pages 913–928, Renton, WA, July 2019.
  * [22] T. L. Harris, K. Fraser, and I. A. Pratt.  A practical multi-word compare-and-swap operation.  In 16th Intl. Symp. on Distributed Computing (DISC), pages 265–279, Toulouse, France, Oct. 2002.
  * [23] M. Hedayati, S. Gravani, E. Johnson, J. Criswell, M. L. Scott, K. Shen, and M. Marty.  Hodor: Intra-process isolation for high-throughput data plane libraries.  In Usenix Annual Technical Conf. (ATC), pages 489–504, Renton, WA, July 2019.
  * [24] M. Herlihy and N. Shavit.  The Art of Multiprocessor Programming.  Morgan Kaufmann, San Francisco, CA, 2008.
  * [25] M. P. Herlihy and J. M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Transactions on Programming Languages and Systems, 12(3):463–492, July 1990.
  * [26] T. C.-H. Hsu, H. Brügner, I. Roy, K. Keeton, and P. Eugster.  NVthreads: Practical persistence for multi-threaded applications.  In 12th European Conf. on Computer Systems (EuroSys), pages 468–482, Belgrade, Serbia, 2017.
  * [27] D. Hwang, W.-H. Kim, Y. Won, and B. Nam.  Endurable transient inconsistency in byte-addressable persistent B+-tree.  In 16th Usenix Conf. on File and Storage Technologies (FAST), pages 187–200, Oakland, CA, Feb. 2018.
  * [28] J. Izraelevitz, T. Kelly, and A. Kolli.  Failure-atomic persistent memory updates via JUSTDO logging.  In 21st Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 427–442, Atlanta, GA, Apr. 2016\.
  * [29] J. Izraelevitz, H. Mendes, and M. L. Scott.  Linearizability of persistent memory objects under a full-system-crash failure model.  In Intl. Symp. on Distributed Computing (DISC), pages 313–327, Paris, France, Sep. 2016.
  * [30] W.-H. Kim, J. Seo, J. Kim, and B. Nam.  clfB-tree: Cacheline friendly persistent B-tree for NVRAM.  ACM Trans. on Storage, 14(1):5:1–5:17, Feb. 2018.
  * [31] S. K. Lee, K. H. Lim, H. Song, B. Nam, and S. H. Noh.  WORT: Write optimal radix tree for persistent memory storage systems.  In 15th Usenix Conf. on File and Storage Technologies (FAST), pages 257–270, Santa clara, CA, Feb. 2017.
  * [32] M. Liu, J. Xing, K. Chen, and Y. Wu.  Building scalable NVM-based B+tree with HTM.  In Intl. Conf. on Parallel Processing (ICPP), pages 101:1–101:10, Kyoto, Japan, Aug. 2019.
  * [33] M. Liu, M. Zhang, K. Chen, X. Qian, Y. Wu, W. Zheng, and J. Ren.  DudeTM: Building durable transactions with decoupling for persistent memory.  In 22nd Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 329–343, Xi’an, China, Apr. 2017\.
  * [34] Q. Liu, J. Izraelevitz, S. K. Lee, M. L. Scott, S. H. Noh, and C. Jung.  iDO: Compiler-directed failure atomicity for nonvolatile memory.  In 2018 51st Intl. Symp. on Microarchitecture (MICRO), pages 258–270, Fukuoka, Japan, 2018.
  * [35] Y. Liu, V. Luchangco, and M. Spear.  Mindicators: A scalable approach to quiescence.  In IEEE 33rd Intl. Conf. on Distributed Computing Systems (ICDCS), pages 206–215, Philadelphia, PA, 2013.
  * [36] P. Mahapatra, M. D. Hill, and M. M. Swift.  Don’t persist all: Efficient persistent data structures, 2019.  arXiv preprint arXiv:1905.13011.
  * [37] Y. Mao, E. Kohler, and R. T. Morris.  Cache craftiness for fast multicore key-value storage.  In 7th European Conf. on Computer Systems (EuroSys), pages 183–196, Bern, Switzerland, Apr. 2012.
  * [38] A. Memaripour, J. Izraelevitz, and S. Swanson.  Pronto: Easy and fast persistence for volatile data structures.  In 25th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 789–806, Mar. 2020.
  * [39] A. Memaripour and S. Swanson.  Breeze: User-level access to non-volatile main memories for legacy software.  In 36th Intl. Conf. on Computer Design (ICCD), pages 413–422, Hartford, CT, Oct. 2018.
  * [40] M. M. Michael.  High performance dynamic lock-free hash tables and list-based sets.  In 14th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 73–82, Winnipeg, MB, Canada, 2002.
  * [41] M. M. Michael.  Hazard pointers: Safe memory reclamation for lock-free objects.  IEEE Transactions on Parallel and Distributed Systems, 15(6):491–504, June 2004.
  * [42] M. M. Michael and M. L. Scott.  Simple, fast, and practical non-blocking and blocking concurrent queue algorithms.  In 15th ACM Symp. on Principles of Distributed Computing (PODC), pages 267–275, Philadelphia, PA, 1996.
  * [43] A. Natarajan and N. Mittal.  Fast concurrent lock-free binary search trees.  In 19th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 317–328, Orlando, FL, USA, Feb. 2014.
  * [44] F. Nawab, J. Izraelevitz, T. Kelly, C. B. M. III, D. R. Chakrabarti, and M. L. Scott.  Dalí: A periodically persistent hash map.  In Intl. Symp. on Distributed Computing (DISC), pages 37:1–37:16, Vienna, Austria, Oct. 2017.
  * [45] I. Oukid, J. Lasperas, A. Nica, T. Willhalm, and W. Lehner.  FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory.  In Intl Conf on Management of Data (SIGMOD), pages 371–386, San Francisco, CA, 2016.
  * [46] M. Pavlovic, A. Kogan, V. J. Marathe, and T. Harris.  Brief announcement: Persistent multi-word compare-and-swap.  In ACM Symp. on Principles of Distributed Computing (PODC), pages 37–39, Egham, United Kingdom, 2018.
  * [47] P. Ramalhete, A. Correia, P. Felber, and N. Cohen.  OneFile: A wait-free persistent transactional memory.  In 49th IEEE/IFIP Intl. Conf. on Dependable Systems and Networks (DSN), pages 151–163, Portland, OR, June 2019.
  * [48] D. Schwalb, M. Dreseler, M. Uflacker, and H. Plattner.  NVC-hashmap: A persistent and concurrent hashmap for non-volatile memories.  In 3rd VLDB Workshop on In-Memory Data Management and Analytics (IMDM), pages 4:1–4:8, Kohala, HI, Aug. 2015.
  * [49] O. Shalev and N. Shavit.  Split-ordered lists: Lock-free extensible hash tables.  Journal of the ACM, pages 379–405, May 2006.
  * [50] U. Upadhyayula and A. M. Rudoff.  Introduction to Programming with Persistent Memory from Intel.  https://software.intel.com/en-us/articles/introduction-to-programming-with-persistent-memory-from-intel, Aug. 2017.
  * [51] S. Venkataraman, N. Tolia, P. Ranganathan, and R. H. Campbell.  Consistent and durable data structures for non-volatile byte-addressable memory.  In 9th Usenix Conf. on File and Storage Technologies (FAST), pages 61–75, San Jose, CA, Feb. 2011.
  * [52] H. Volos, A. J. Tack, and M. M. Swift.  Mnemosyne: Lightweight persistent memory.  In 16th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 91–104, Newport Beach, CA, Mar. 2011.
  * [53] C. Wang, Q. Wei, L. Wu, S. Wang, C. Chen, X. Xiao, J. Yang, M. Xue, and Y. Yang.  Persisting RB-Tree into NVM in a consistency perspective.  ACM Trans. on Storage, 14(1):6:1–6:27, Feb. 2018.
  * [54] H. Wen, W. Cai, M. Du, L. Jenkins, B. Valpey, and M. L. Scott.  Montage: A general system for buffered durably linearizable data structures, Sept. 2020.  arXiv preprint arXiv:2009.13701. Brief announcement presented at DISC 2020\.
  * [55] J. Yang, Q. Wei, C. Chen, C. Wang, K. L. Yong, and B. He.  NV-Tree: Reducing consistency cost for NVM-based single level systems.  In 13th Usenix Conf. on File and Storage Technologies (FAST), pages 167–181, Santa Clara, CA, Feb. 2015.
  * [56] Y. Zuriel, M. Friedman, G. Sheffi, N. Cohen, and E. Petrank.  Efficient lock-free durable sets.  Proc. of the ACM on Programming Languages, 3(OOPSLA):128:1–128:26, Oct. 2019.

class MHashTable : public Recoverable class Payload : public PBlk K key; V
val; ; // Transient index class: struct Node Payload* payload = nullptr; //
Transient-to-persistent pointer CASObj¡Node*¿ next = nullptr; // Transient-to-
transient pointer Node(K& key, V val) payload = pnew¡Payload¿(key, val);
Node() if(payload!=nullptr) pdelete(payload); ; EBRTracker tracker; // Epoch-
based memory reclamation // Starting from p, find node ¿= k and assign to c:
bool find(CASObj¡Node*¿* &p,Node* c,Node* n,K k); // Insert, or update if the
key exists: void put(K key, V val) Node* new_node = new Node(key, val);
CASObj¡Node*¿* prev = nullptr; Node* curr, next; tracker.start_op();
while(true) if (find(prev,curr,next,key)) // update
new_node-¿next.store(curr); pdetach(curr-¿payload); if(prev-¿lin_CAS(curr,
new_node)) while(!curr-¿next.CAS(next,mark(next)));
if(new_node-¿next.CAS(curr,next)) tracker.retire(curr); else
find(prev,curr,next,key); break; else // key does not exist; insert
new_node-¿next.store(curr); if(prev-¿lin_CAS(curr,new_node)) break;
tracker.end_op(); ;

Figure 7: Michael’s lock-free hash table example (nbMontage-related parts
highlighted).

##  Appendix A Example nbMontage Data Structure

As an example of the use of the nbMontage API, Figure Fast Nonblocking
Persistence for Concurrent Data Structures111This work was supported in part
by NSF grants CCF-1717712, CNS-1900803, CNS-1955498, and by a Google Faculty
Research award. presents a fragment of Michael’s lock-free hash table [40],
modified for persistence. Highlighted lines were changed from the original.

##  Appendix B DCSS

Figure 8 provides pseudocode for DCSS-style lin_CAS. It supercedes the
sketched implementation in Figure 3.1. CAS-able data is of type CASObj. It
contains a 64-bit field that may be either a value or a pointer to a
descriptor, a counter used to avoid ABA problems, and a status field that
differentiates between the value and pointer cases: INIT indicates the former;
IN_PROG the latter.

1

uint2 INIT=0,IN_PROG=1

2 uint2 COMMITTED=2,FAILED=3

Obj<T> T val

// 64-bit

3 uint62 cnt

4 uint2 stat

5 CASObj<T> atomic¡Obj¡T¿¿ var

6 Desc uint64 old,new,epoch=0

7 uint64 type=DESC

8 uint64 tid_sn=0

9 atomic¡Obj¡T¿¿ r_c_s

10 commit(Obj cur) expected=Obj(cur.val,cur.cnt,IN_PROG)

11 desired=Obj(cur.val,cur.cnt,COMMITTED)

12 r_c_s.CAS(expected,desired)

13 abort(Obj cur) expected=Obj(cur.val,cur.cnt,IN_PROG)

14 desired=Obj(cur.val,cur.cnt,FAILED)

15 r_c_s.CAS(expected,desired)

16 cleanup(Obj cur) tmp=r_c_s.load()

17 if tmp.cnt!=cur.cnt or tmp.val!=cur.val  then

18 return

19expected=Obj(this,tmp.cnt,IN_PROG)

20 new_val=tmp.stat==COMMITTED?new:old

21 desired=Obj(new_val,tmp.cnt+1,INIT)

22 CASObj* casobj=tmp.val

23 casobj$\rightarrow$var.CAS(expected,desired)

24 try_complete(uint64 addr) cur=r_c_s.load()

25 if addr!=cur.val then

26 return

27if epoch==global_epoch.load() then

28 commit(cur)

29

30else

31 abort(cur)

32

33cleanup(cur)

34 Obj<T> CASObj<T>::_load() r.stat==IN_PROG r=var.load()

35 if r.stat==IN_PROG then

36 ((Desc*)r.val)$\rightarrow$try_complete(this)

37

38 return r T CASObj<T>::load() return _load().val CASObj<T>::store(T val)
!var.CAS(r,newr) r=var.load()

39 if r.stat==IN_PROG then

40 ((Desc*)r.val)$\rightarrow$try_complete(this)

41 r.cnt++

42 r.stat=INIT

43

44newr=Obj(val,r.cnt+1,INIT)

bool CASObj<T>::CAS(T exp,T val)

// regular CAS without epoch verification

45 r=_load()

46 oldr=Obj(exp,r.cnt,INIT)

47 newr=Obj(val,r.cnt+1,INIT)

48 return var.CAS(oldr,newr)

bool CASObj<T>::lin_CAS(T exp,T des) begin_op()

// descs[tid].epoch is set here

49 r=_load()

50 if r.val==exp then

51 descs[tid].r_c_s=Obj(this,r.cnt,IN_PROG)

52 descs[tid].old=exp

53 descs[tid].new=des

54 newr=Obj(&descs[tid],r.cnt,IN_PROG)

55 if var.CAS(r,newr) then

56 descs[tid].try_complete(this)

57 if COMMITTED==descs[tid].r_c_s.stat then

58 end_op()

59 return true

60

61

// assume that failed CAS loads new var to r

62 if r.val==exp then

// failed desc or changed cnt

// epoch must have advanced; retry

63 reset_op()

64 goto 8

65

66

67abort_op()

68 return false

Figure 8: DCSS pseudocode, adapted from Harris et al. [22].

Each descriptor includes a similar $\langle$value, counter, status$\rangle$
field, together with an indication of the old and new values intended for the
corresponding CASObj and the epoch in which the change is intended to occur.
In a descriptor, the status field indicates whether an epoch-respecting CAS is
in progress, committed, or failed due to conflict or epoch advance. A
successful lin_CAS sets up a descriptor, CAS-es a pointer to it into the to-
be-changed CASObj, double-checks the epoch, CAS-es the descriptor from IN_PROG
to COMMITTED, and then CAS-es the new value back into the CASObj. A
conflicting lin_CAS in another thread will try to complete the descriptor and
help update the CASObj based on the status of the descriptor. A successful
lin_CAS calls end_op. A lin_CAS that fails due to conflict calls abort_op. A
lin_CAS that experiences an epoch transition calls reset_op and retries.

Once a thread, $t$, has initialized its lin_CAS descriptor and installed it in
the named CASObj $j$, arbitrary time may elapse before $t$ (or another thread)
executes the CAS at line 8. If that CAS succeeds, the operation $o$ that
called lin_CAS can be considered to have linearized at the earlier load of
global_epoch at line 8. If that load returned $e$ and the CAS succeeds and
persists $t$’s descriptor in epoch $e^{\prime}$, $o$ will persist when the
epoch advances to $e^{\prime}+2$, but _it still will have linearized in
$e$_—the epoch with which its payloads were tagged.

It is possible, of course, that a crash will occur before $o$’s lin_CAS has
committed. Say the crash occurs in epoch $f\geq e+2$. If $o$ has not persisted
at the crash, then we know it did not return before the end of epoch $f-2$,
implying that it was pending at the end of epoch $e$. Moreover we know that no
other thread will have accessed $j$ ($o$’s CASObj) before the end of epoch
$f-2$, because it would have completed the CAS at line 8 and $t$’s descriptor
should be persisted by the end of $f-2$. We are thus permitted to declare, in
recovery, that $o$ did not linearize at all. This is true even if $f>\\!>e$.

1

EStat uint63 e

2 bool status

3 EStat w[4]

4 end_op() detaches.clear()

5 allocs.clear()

/* new code begins */

6 if e_last!=e_curr then

// first successful op in e_curr

7 w[e_curr%4].CAS($\langle$e_curr,0$\rangle$,$\langle$e_curr,1$\rangle$)

8

/* new code ends */

9 e_last=e_curr

10 e_curr=0

11 advance() e=global_epoch.load()

12 foreach t in mindi whose val==e-1 do

13 TBP[t][(e-1)%4].pop_all()

14 clwb(descs[t])

15 update t’s val to e in mindi

16

17sfence

/* new code below */

18 if w[e%4]==$\langle$e,0$\rangle$ and w[(e-1)%4]==$\langle$e-1,0$\rangle$
then

// no op succeeds in recent 2 epochs

19 return

20if w[(e+1)%4]==$\langle$e-3,0$\rangle$ then

21 if w[(e+1)%4].CAS($\langle$e-3,0$\rangle$,$\langle$e+1,0$\rangle$) then

22 goto 9

23

24

25if w[(e+1)%4]==$\langle$e-3,1$\rangle$ then

26 w[(e+1)%4].CAS($\langle$e-3,1$\rangle$,$\langle$e+1,0$\rangle$)

27

28global_epoch.CAS(e,e+1)

Figure 9: Pseudocode for advance and end_op with logic to skip the epoch
change in the absence of a successful update operation.

##  Appendix C Ensuring Progress

At line 2 in Figure 2, to avoid compromising lock freedom, we assume that an
epoch advance happens only when at least one successful operation has occurred
in the two most recent epochs. In practice, this will usually be true, given
multi-millisecond epochs and the intended use of sync. To enforce such
progress, however, the epoch advancer needs to know whether anything has
happened in the two most recent epochs. To capture this information, we employ
a set of global status words w, indexed (like TBP and TBF containers) using
the low-order bits of the global epoch. Each word contains a recent epoch
number and a boolean to indicate progress; each successful operation tries to
CAS w[e%4] from $\langle$e,0$\rangle$ to $\langle$e,1$\rangle$. Concurrently,
an epoch advance can reuse the status word of an old epoch by CAS-ing w[e%4]
from $\langle$e,_$\rangle$ to $\langle$e+4,0$\rangle$. Pseudocode appears in
Figure 9.