# Transactions on Red-black and AVL trees in NVRAM

Thorsten Schütt  Florian Schintke  Jan Skrzypczak

(Zuse Institute Berlin
)

###### Abstract

Byte-addressable non-volatile memory (NVRAM) supports persistent storage with
low latency and high bandwidth. Complex data structures in it ought to be
updated transactionally, so that they remain recoverable at all times.
Traditional database technologies such as keeping a separate log, a journal,
or shadow data work on a coarse-grained level, where the whole transaction is
made visible using a final atomic update operation. These methods typically
need significant additional space overhead and induce non-trivial overhead for
log pruning, state maintenance, and resource (de-)allocation. Thus, they are
not necessarily the best choice for NVRAM, which supports fine-grained, byte-
addressable access.

We present a generic transaction mechanism to update dynamic complex data
structures ‘in-place’ with a constant memory overhead. It is independent of
the size of the data structure. We demonstrate and evaluate our approach on
Red-Black Trees and AVL Trees with a redo log of constant size (4 resp. 2
cache lines). The redo log guarantees that each accepted (started) transaction
is executed eventually despite arbitrary many system crashes and recoveries in
the meantime. We update complex data structures in local and remote NVRAM
providing exactly once semantics and durable linearizability for multi-reader
single-writer access. To persist data, we use the available processor
instructions for NVRAM in the local case and remote direct memory access
(RDMA) combined with a software agent in the remote case.

##  1 Introduction

The introduction of NVRAM enables a new range of applications, but it also
causes new challenges for their effective use. NVRAM is the first non-volatile
storage providing byte-granular access with low-latency and high bandwidth. In
addition, it will replace SSDs as fastest persistent storage in the storage
hierarchy. While SSDs only provide block-oriented APIs, NVRAM comes as a
standard DIMM. Plain loads and stores suffice to get direct access (DAX) while
bypassing the operating system. For recoverability and consistency of data
structures, it becomes relevant when, in which order, and which part of them
will be written to NVRAM from the processor’s caches—either explicitly by
instructions or implicitly by cache evictions. This is influenced by aspects
such as data alignment, weak memory models, and cache properties such as
associativity, size, and its replacement and eviction policy. To conquer all
these aspects, complex data structures stored in NVRAM must be recoverable at
all times, which requires new and sound transactional update mechanisms.

The literature on NVRAM has been mostly focusing on B+trees [16] with a high
radix [12, 27] to minimize costs for insert and remove. By using a high radix,
expansive operations like balancing happen seldom. Insert and remove are
operations on leaves. Thus, they do not have to be transactional and only
require a few persist calls. If the sequence of calls is interrupted by a
crash, the tree remains valid. They are tuned for absolute performance.

In contrast, balancing is the common case for Red-Black Trees and AVL Trees
[58]. Insert and remove always need an unpredictable and variable sequence of
operations, i.e., balancing, recoloring, and updating the balance factors.
This depends on the size and the shape of the tree as they work across several
levels of it. For NVRAM, the steps of the sequence have to happen atomically
despite an arbitrary number of crashes and restarts. Otherwise, the tree might
become invalid, unrecoverable, and may lose sub-trees. Thus, transactions are
needed [50].

The literature so far focused on a copy-on-write style for updating data-
structures. It comes with additional costs for allocating, de-allocating, and
garbage collection. For B+ trees, a constant amount of memory is needed, i.e.,
the size of a node, which simplifies the process. As Wang et al. [63] noted,
for Red-Black Trees copy-on-write operations touch almost the complete tree.
One needs to allocate and de-allocate a variable amount of memory for
operations. We split updates into a sequence of micro-transactions. Thus a
constant size redo log suffices for all operations. We neither allocate nor
de-allocate memory for operations as all updates are in-place [54]. It shows
its strengths for complex data structures where updates are global operations
and touch large parts of the data structure. There is no doubt that
performance-wise B+-trees beat binary trees. It is by design. However, binary
trees represent a wider class of dynamic data structures using pointers. For
binary trees, we needed to invent new methodologies for storing data
structures in NVRAM that widely differ from B+-trees. They could also be
applied to data structures such as (doubly) linked lists, priority queues, or
graphs. Trees are often used as proxies for index data structures [49, 48].

As NVRAM behaves like memory rather than a spinning hard-disk, we can use
remote direct memory access (RDMA) of modern interconnects to directly access
NVRAM on remote nodes. Local and remote access can rely on a common set of
operations. For NVRAM, access can be expressed in terms of read, write, atomic
compare&swap (CAS), and persist operations. For remote access, get, put,
remote atomic CAS, and remote persist of the _passive target communication_
model defined in the MPI standard [38] can be used. For passive target
communication, the origin process can access the target’s memory without
involvement of the target process. It is similar to a shared memory model and
allows the design of a single transaction system based on common primitives
for both local and remote NVRAM.

We support exactly once operations [21] on dynamic complex data structures in
local and remote NVRAM and make the following main contributions:

  * •

We designed a new transaction system for NVRAM, which splits large multi-step
transactions into a sequence of micro-transactions. A state machine describes
the transaction and the sequence of micro-transactions. Each micro-transaction
resp. state transition is idempotent allowing atomicity and recovery in the
failure case for multi-step transactions. All updates happen directly on the
data structure ‘in-place’ without shadow copying. It incrementally transforms
the old data structure into the new one. All accepted operations will
eventually succeed (Sect. 4).

  * •

A _redo log_ of constant size (four resp. two cache lines for Red-Black Trees
and AVL Trees) is used to guarantee recoverability and atomicity at all times.
Note that the size of the redo log is independent of the size of the data
structure (Sect. 4.1).

  * •

Our approach supports exactly once semantics and guarantees durable
linearizability for all operations, both local and remote. Failed clients
cannot corrupt any data (Sect. 4.4).

  * •

We implemented balanced Red-Black Trees and AVL Trees in NVRAM using our
approach—local and with passive target communication for remote access (Sect.
6).

  * •

Intel guarantees 8 byte fail-safe atomicity for NVRAM. For our approach 7
bytes suffice as we do not rely on atomic pointer updates (Sect. 4).

  * •

We designed a multi-reader single-writer lock with $f$-fairness to coordinate
concurrent RDMA writes. Failed lock-holders can be safely expelled by other
processes, because their process ids are stored in the lock, which allows
other clients to use failure detectors (Sect. 10).

  * •

We simulated more than 2,000,000 power failures by killing processes to
validate the robustness of our approach (Sect. 11).

  * •

Our evaluation shows more than 2,300/s key-value pair inserts into Red-Black
Trees using passive target communication with NVRAM. For AVL Trees, we reached
more than 1,800/s inserts (Sect. 12.4). For local access, we reached almost
400,000 inserts per second (Sect. 12.1).

##  2 System Model

We assume a full-system failure model [30]. On a crash, all transient state
(of all processes) is lost. Only operations on fundamental, naturally aligned
data types up to 8 bytes are atomic fail-safe in NVRAM, but 7 bytes are enough
for our approach.

While RDMA operations can fail non-atomically, we assume 64 bit RDMA CAS
operations to be atomic. To detect failed nodes, we use the weak failure
detector $\Diamond\mathcal{W}$ [11]. We consider a system with a single server
storing data without replication for simplicity. An arbitrary number of
read/write clients may try to access the data concurrently. We do not consider
Byzantine failures.

##  3 Preliminaries

As discussed above, hardware only supports atomic updates of 8 bytes. In the
following, we describe the basic concepts needed for larger updates and
describe in detail the methods for persisting data with NVRAM.

###  3.1 Logging and shadow copying

As long as updates are atomic, i.e., 8 bytes for NVRAM or a block for SSDs,
they can be done in-place. For non-atomic updates, transaction systems [39,
63, 6] use a combination of different techniques to preserve consistency in
the face of crashes. Logging uses undo and redo logs to store enough data to
roll-back an interrupted transaction (undo) or retry the transaction again
(redo). Undo logging tends to be more costly. It has to log every store before
executing it. Thus, redo logging is the preferred technique. Some databases
[6] use a combination of both. Shadow copying, also known as copy-on-write,
creates a copy of the data to be updated, updates the copy, and atomically
replaces the old data with the new data. For example, to atomically update a
tree node, a copy of the node is created, updated, and then the parent’s
pointer to the node is atomically updated. Often, it is sufficient to replace
one 8-byte pointer for the last step, which can be done atomically.

###  3.2 How to persist data with NVRAM?

Persisting data in NVRAM works similar to block-oriented storage, i.e., writes
followed by a flush, but the details differ. Persisting data to NVRAM relies
on cache line (cl) flushing, which persists data as a side effect. According
to Intel Corp. [28], there are four different methods: clflush, movnti+sfence,
clflushopt+sfence, and clwb+sfence. The clflushopt and clwb operations were
recently introduced with the Skylake micro architecture. Stores before an
sfence, a store fence, are separated from following stores. clflush and
clflushopt persist the cache line’s data by invalidating it and writing the
content back to memory. movnti is a non-temporal store, which bypasses caches
and writes directly to memory. Hot data has to be loaded again from memory. To
mitigate the costs of cache misses, prefetching can be used [65]. A clwb ought
to perform a write-back of the data without invalidating the cache line. It is
recommended to use clwb [28].

While any pair of clflush instructions are ordered, pairs of clflushopt are
only ordered with each other when accessing the same cache line. Pairs of clwb
always remain unordered with each other. These recently introduced operations
of the Skylake micro architecture shown above allow more parallelism than the
older ones.

Former versions of Intel Corp. [29] recommended clflush+mfence, where mfence
is a memory fence that separates load _and_ stores before and after the fence.
CDDS [61] and NV-Tree [65] even used mfence+clflush+mfence. Memory fences have
much higher latency than store fences.

Today, there is no hardware support for remote persisting. The standard work-
around is proposed by SNIA [56]. After an RDMA write, the client has to
request cache flushing by sending a message to a software agent. The software
agent then must respond with an _ack_ message. This workflow is implemented by
the PMDK.111http://pmem.io/pmdk/

##  4 Exactly once operations with Micro-Transactions ($\upmu$-Tx) and State
Machines

Performing updates on complex data structures often requires a sequence of
smaller operations (recoloring, balancing, node splitting, etc.). NVRAM makes
it challenging to perform them correctly in the face of power losses as only
aligned stores up to 8 bytes are fail-safe atomic with current hardware. All
larger operations require transactions. Otherwise, it is unknown which updates
are persistent in the failure case, i.e., reached the persistence domain. This
can fatally corrupt the data. Traditional techniques to address this problem
are shadowing, copy-on-write, and logging (see Sect. 3.1).

Aims. Inserting or removing elements from trees, for example, often requires a
sequence of operations, such as tree rotations (see Sect. 5.1). We want to
support such complex data structure updates atomically ‘in-place’. We directly
update the data structure without shadow copying but with a redo log of
_constant size_ independent of the size of the overall data structure. The
structure and actual size of such a constant-size redo log depends on the
particular data structure and operations to be supported. In Sect. 6, we show
some examples for Red-Black Trees and AVL Trees.

Approach. In general, we split an operation to be performed on a complex data
structure into a sequence of smaller operations, which we execute in micro-
transactions ($\upmu$-Tx) until the whole operation is finished. We want to be
able to identify the ongoing operation (insert or remove), detect the progress
in that operation, perform updates atomically, minimize the size of the redo
log, and guarantee that all accepted operations will eventually complete. We
need the following components (see Figure 6): (1) the primary data structure D
of potentially dynamic size that we want to update, (2) a redo log L of
constant size, and (3) a state machine $M$ with $\mathcal{S}$ states
describing the sequence of updates on D and L. D and L can be seen as disjoint
sets of byte ranges. D, L, and the current state of $M$ are stored in NVRAM.

For non-trivial updates, the idea is to establish a two-step mode of operation
repeatedly: First, persist all information that are required to perform the
operation on D in the redo log L. Afterwards, perform the operation and
persist it. Each step is idempotent until the next micro-transaction begins.
To separate them from each other, a state variable is updated atomically
between steps to indicate which step finished last.

The current state of the state machine indicates whether the data structure is
clean for performing the next read or write or if it is currently performing
an ongoing concurrent operation. In this case, any upcoming read, insert, or
remove request has to wait. We reject concurrent operations with locks (see
Sect. 10) as our transaction approach cannot handle concurrent accesses by
itself. Otherwise, they may corrupt the data structure [20].

[width=mode=tex]Figures/state-machine2

Figure 1: $\upmu$-Tx in a state machine with clean and dirty states working on
a constant size redo log L, a complex data structure D of arbitrary size, and
the state variable s.

Each state transition of the state machine (see Figure 1) performs a sequence
of writes followed by a mechanism to make the writes persistent—an epoch [17].
A state transition either updates D or L and then updates the current state
atomically. Thus, it consists of two epochs. We require all state transitions
to be idempotent. If a transition updates D, there must be enough information
in L to be able to redo the operation. If it updates L, there must be enough
information in D and L to redo the operation, i.e., D can be the redo log for
L. Switching the roles of the two components during an ongoing transaction is
uncommon for traditional databases, but it is one of the fundamental concepts
of our approach. Idempotence of state transitions facilitates applying non
fail-safe atomic updates consistently.

State transitions. A transition from the current state $s_{i}$ to a direct
successor state $s_{j}$ is split into two steps: (a) an epoch updating D or L
and (b) atomically making $s_{j}$ the current state. We discuss in Sect. 4.2
our approach for identifying and atomically changing the current state. If a
client succeeds in updating D or L, it tries to make $s_{j}$ the current
state. When the client fails to complete the first step, $s_{i}$ remains the
current state. If the client finishes the epoch and fails to make $s_{j}$ the
current state, $s_{i}$ also remains the current state. So, any attempt to
perform a state transition may fail. As all update operations resp. epochs are
required to be idempotent, a state transition can be blindly retried
arbitrarily often. Given enough progress, it will eventually succeed. It will
never abort.

To be able to precisely track progress and detect failures, we divide the
states $\mathcal{S}$ into disjoint sets of clean states $\mathcal{C}$ and
dirty states $\mathcal{D}$, such that $\mathcal{S}=\mathcal{C}\cup\mathcal{D}$
and $\mathcal{C}\cap\mathcal{D}=\varnothing{}$. If the state machine is in a
clean state, clients can read D or start a new transaction. If it is in a
dirty state, a transaction is ongoing and it has to be finished first.

Recovery. Recovery is agnostic to the ongoing operation. In case of a power
failure, we can always identify the current state at all times. If we recover
in the clean state, there was either no accepted operation or an operation
completed that did not return to the client before the power loss. If we
recover in a dirty state, we continue the current operation until we reach the
clean state as all state transitions are idempotent.

For databases, recovery is separated from production, see Sect. 13. For
recovery, databases have to analyze the logs and cleanup the damage caused by
the crash. In our approach, we simply continue the ongoing operation. Recovery
barely differs from production.

In contrast to shadowing and logging, the state machine approach is less
affected by failures. When it reached the first dirty state, it can guarantee
the client that the operation will eventually succeed. The first state
transition accepts the operation and the following ones perform the operation.
Shadowing can only guarantee success after completion. We can identify the
kind of operation uniquely by the current state. Different operations will use
disjoint sets of dirty states. If the machine is in a clean state, there is no
ongoing operation.

The recovery cost is negligible. We might lose one epoch, which we have to
repeat. The next process can continue where the last process crashed. For
comparison, NV-Trees [65] only store the leaves in NVRAM. On recovery, they
have to recompute the inner nodes.

###  4.1 Overhead

There is a trade-off between the number of states and the size of the redo
log. Larger state machines tend to have smaller logs. Less information is
needed to make state transitions idempotent. However, they require more state
transitions and flushes. Smaller state machines will need larger logs and
require fewer state transitions and flushes.

The smallest state machine with one clean and one dirty state akin to
traditional transactions in databases has no constant size redo log. Remove
for AVL Trees has in the worst case $\mathcal{O}(\log{}n)$ balancing
operations, which cannot be executed in-place. All balancing operations
require logging, see Sect. 5.4. Thus, the minimal state machine with two
states has no constant size redo log. For remove with AVL Trees, the log’s
size is a function of the depth of the tree. In our approach, it suffices to
provide enough space in the redo log to make state transitions idempotent. The
complexity of state transitions is independent of the size of the data
structure.

There are operations that imperative code implements in-place, such as tree
rotations, updating pointers, and updating loop counters. These operations are
not idempotent and have to be split into two state transitions. The smallest
state machine with a constant size redo log depends on the complexity of the
algorithm. Note that both state machines for AVL Trees are larger than the two
for Red-Black Trees. AVL Trees are stricter balanced . Furthermore, the remove
state machine for AVL Trees is larger than the one for insert (35 vs. 24
states).

Despite all state transitions being idempotent, there are two strategies for
re-executing an interrupted state transition: (a) blindly re-executing it and
(b) analyzing the progress made before the crash and only executing missing
parts. In our implementation, we used the former strategy. The number of
stores per state transition is small. A single rotation needs two state
transitions with three stores each. The gain of the latter strategy would be
negligible. For store intensive state transitions, like, e.g., writing a GiB
of data, the latter would be more efficient than the former.

###  4.2 Maintaining the Current State

State change operations have to be either fail-safe atomic or use a state
machine, otherwise we can reach unintended resp. unreachable states.

We use a global state variable of 7 bytes that stores the current state and is
updated atomically with CAS operations. This means that the number of states
is limited to $2^{56}$. When $2^{56}$ states are insufficient, we create a
state machine where _D_ is a variable with more than 56 bits. However, the
number of executable state transitions is not bounded by the 7 byte limit.
Unfortunately, this approach does not allow reliably detecting whether the
state machine made progress. Even if the state variable did not change between
two reads, the state machine may have transitioned through several states in
the meantime ending in the original state again. Supporting detection of
progress would require an approach based on arbitrary precision counters,
which is unfortunately challenging with NVRAM.

###  4.3 Detectable Execution

The _detectable execution_ property was introduced by Friedman et al. [21]. A
data structure with this property can, upon recovery after a crash, detect for
each operation executed during the crash whether it completed or aborted. This
property is necessary to execute operations exactly once.

To fulfill this property, additional state provided by the client is required.
The operation has to go through three steps: (1) announced, (2) accepted, and
(3) done. The client has to durably store its intent to execute an operation
(step 1). Then it can move the state machine from the clean state into the
first dirty state (the operation is accepted) and durably store that the
operation is accepted (step 2). Finally, the client traverses the state
machine until it reaches the clean state again and durably marks the operation
as done (step 3).

If a crash happens before step 1, the operation was never intended to be
executed. If the crash happens between step 1 and step 2, the state machine is
either in the clean state or the first dirty state. Thus, the operation did
not happen yet. If the crash happens between step 2 and step 3, the state
machine is either in a dirty state or the clean state. When it is in a dirty
state, the operation did not finish . If it is in the clean state, the
operation finished, but the client did not update the state. If the state
machine is after step 3, the operation finished. Thus, we can support exactly
once semantic. We did not implement this approach and the evaluation in Sect.
12 does not consider it.

For systems based on shadow copying, it is challenging to support this
property. Updates become only visible with the last atomic pointer update.
Intermediate steps cannot be detected. Even if the client durably stored its
intent to perform an operation, there are no visible events that allow
distinguishing between success and failure after the crash. For a no-op
operation, we cannot detect whether it succeeded or not. The updated value
does not change and we cannot use the value change to distinguish between
success or failure.

###  4.4 Durable Linearizability

According to _durable linearizability_ introduced by Izraelevitz et al. [30],
operations have to become durable before they return. In case of a crash, all
previously completed operations remain completed. Operations started before
the crash may be visible, because they progressed enough but did not return.
The concept preserves important properties from linearizability,
composability, and non-blocking progress [25, 2, 53].

In contrast, _buffered durable linearizability_ [30] only requires operations
to be persistently ordered before they return. After a crash, the data would
still be persistent but not necessarily up to date.

In our approach, all operations start at the state transition the last
operation finished. They start from the clean state, traverse the state
machine, and return to the clean state before they return. The current state
of D represents the execution resp. history of all previously completed
$\upmu$-Tx. If the state machine is in a dirty state after the crash, an
operation started but did not return. Given enough progress, the state machine
might be in the clean state after the crash, but it did not return before the
crash. Thus, our approach supports durable linearizability.

##  5 Self-balancing Binary Search Trees

Binary search trees are a widely studied topic. They serve as a research
vehicle for theoretical computer science and have many applications in
practical systems.

###  5.1 Red-Black Trees

Red-Black Trees [24, 18] are half-balanced binary trees. They have the
following properties: (a) each node is colored either red or black, (b) all
children of red nodes are black, and (c) every path from a given node to its
leaves has the same number of black nodes. Violating property (b) or (c) is
called a _red violation_ or _black violation_ , respectively. The shortest
possible path from a given node to its leave has all black nodes. The longest
possible path from a given node to its leave alternates between black and red
nodes with twice the length of the shortest possible path. Thus, Red-Black
Trees are called half-balanced [42]. Our root is always colored black to
prevent red violations (property (b)) between the root and its children.
Insert, remove, and lookup are all in $\mathcal{O}(\log{n})$.

We focus on insert and remove as lookups are not of particular interest
regarding failures. We use top-down algorithms, which start at the root and
walk down the tree. They will always insert (add) or remove a leaf object. On
the way down, they anticipate and repair red and black violations. This relies
on node recoloring and tree rotations. In case of a failure, recoloring is
trivial to repair—we verify the Red-Black Tree properties and recolor the
nodes as necessary. Failures during tree rotations are more challenging,
because they might fatally damage the tree and risk losing sub-trees. Thus,
tree rotations have to be performed atomically (see Sect. 5.4).

###  5.2 AVL Trees

AVL Trees [1] are balanced binary trees. In contrast to Red-Black Trees, they
are height balanced. For each node, the heights of the subtrees of its two
children differ at most by one. Red-Black Trees store a color in each node to
support the balancing scheme. AVL Trees store two bits in each node—the
balance. It is either -1, 0, or 1 depending on the comparison of the height of
the subtrees. AVL Trees also rely on tree rotations for balancing. Insert,
remove, and lookup are all in $\mathcal{O}(\log{n})$.

Knuth [31] describes a top-down algorithm for insert with $\mathcal{O}(1)$
single or double rotations on average [36]. It walks down the tree and inserts
the new node at the bottom. On the way down, it records the positions, which
have to potentially be rebalanced. Additionally, it adapts the respective
balance factors.

Remove deviates from the algorithms described so far. It also requires
$\mathcal{O}(1)$ balance operations on average, but it can need up to
$\mathcal{O}(\log{n})$ balance operations [59]. It must walk back up to
balance the tree. B and B+ trees [8, 16, 9] use a similar concept. If a node
is full, they split the node and walk up the tree.

The imperative C code from Julienne Walker
222http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx.
uses a stack of size $\mathcal{O}(\log{n})$ for remove. This violates our aim
that the redo log is constant size. On the way down, we store pointers to
parents in the nodes, which can be used to walk back up the tree as needed. In
general, it shows a limit of our approach. Algorithms that need auxiliary
space larger than $\mathcal{O}(1)$ in the log cannot be directly supported
when the log must remain of constant size. Here, we used the common technique
of storing pointers to parents in the nodes. We discuss this problem in more
in detail in Sect. 15.

###  5.3 Weight-balanced trees

Red-Black Trees and AVL Trees use the height of sub-trees as a balancing
criterium. Weight-balanced trees [41, 26] store the number of nodes in its
sub-trees in each node. A node $n$ is $\alpha$-weight-balanced if
$\text{weight}(\text{n.left})\geq\alpha*\text{weight}(n)\land\text{weight}(\text{n.right})\geq\alpha*\text{weight}(n)$.
A larger $\alpha$ makes a tree more balanced. Weight-balanced trees also rely
on tree rotations for balancing.

[width=mode=tex]Figures/tree-rotation2

Figure 2: Right rotation with red (white) and black (gray) nodes. Nodes/Roles
(A, B, C, pivot P, Q, and GP) and keys (1, 2, 3, …, 6). P is promoted and Q is
demoted. Nodes drop (D) and take (T) children.

###  5.4 Tree Rotations

A common balancing technique in binary trees are tree rotations [55]. Tree
rotations preserve the order of nodes, but change the shape of the tree for
rebalancing. Figure 2 shows an example for a right rotation with Q as the root
of the rotation, P as pivot (the left child of Q), and GP as grandparent of P.
The rotation increases the height of the tree under the pivot by one and
decrease the height of the tree under the root by one. Additionally, it solves
a red violation between the pivot ( 2) and B ( 3). A left rotation works vice
versa. The order of keys (1, 2, 3, $\ldots$, 6) and thus the order of nodes
remains unchanged.

For the right rotation, Q replaces its left child (the pivot) with B. The
pivot replaces its right child (B) with Q. The GP replaces its left child (Q)
with the pivot. The three nodes pass the ownership, the parent relation,
around. This leads to the tree rotating around the GP.

#### Atomic Tree Rotations for NVRAM

For NVRAM, the ownership changes are implemented with stores (S1-S3). S1 for
updating Q’s left child, S2 for updating the pivot’s right child, and S3 for
updating GP’s left child. If the ownership changes are performed partially,
i.e, the pivot drops the link to B and Q does not take ownership of B, we lose
sub-trees and can create cycles, as the following analysis shows:

_S1_ and _S3_ | fail | $\rightarrow$ | No link to pivot P. |
---|---|---|---|---
_S1_ and _S2_ | fail | $\rightarrow$ | No link to B. | Cycle: Q and pivot P.
_S2_ and _S2_ | fail | $\rightarrow$ | No link to Q. |
_S1_ | fails | $\rightarrow$ | No link to pivot P. |
_S3_ | fails | $\rightarrow$ | No link to Q. |
_S2_ | fails | $\rightarrow$ | No link to B. | Cycle: Q and pivot P.

GP, Q, and the pivot have to be updated atomically. Otherwise, the tree will
lose sub-trees and becomes invalid. Logging the insert resp. delete request
would not be sufficient. Shadowing would copy Q and the pivot node, update
them, and atomically update the pointer of the grandparent pointing to the new
pivot. In our approach, we copy pointers to Q, the pivot, and B to the redo
log in a first step and then update Q, the grandparent, and the pivot in a
second transaction.

##  6 Implementing binary trees with $\upmu$-Tx

In the following, we describe how to implement Red-Black Trees (RBTs) in
NVRAM. The major challenge is to convert the RBT insert and remove algorithms
into state machines with idempotent state transitions. For AVL Trees, we use
the same concepts. For didactic and brevity reasons, we focus on RBTs in the
following.

###  6.1 Creating the state machine

In the following, we outline how to create the state machine. For this paper,
we build them manually following the techniques described below. Building a
tool that automatically converts an algorithm into a state machine with
idempotent state transitions is beyond the scope of this paper.

As a first approximation, the imperative algorithm is converted into a
control-flow graph [4] with basic blocks. The nodes represent basic blocks
resp. state transitions and edges represent states. If a basic block is not
idempotent, it has overlapping read and write sets and has to be split into
two. The first block writes data into the redo log and the second block
updates data in-place. This process has to be iterated until all state
transitions are idempotent.

For example, a tree rotation updates pointers in-place. Its read and write
sets overlap. The overwritten values, which can be determined by alias
analysis [3], have to be stored in the redo log first before the actual
rotation is performed.

While creating the state machine and its redo log, we tried to find a balance
between convenience and the log’s size. Minimizing the log’s size is
equivalent to the register allocation problem [45]. An example for the
flexibility in design are double rotations. They could be expressed as two
single rotations (4 state transitions, space for 3 pointers in the log) or as
one double rotation (2 state transitions, space for 6 pointers in the log).
Trivial control-flow can often be hidden in state transitions, like, e.g.,

Direction dir = (it->key < key) ? Right : Left;

###  6.2 Insert

⬇

1void insert(root, key, value) {

2 if (root == nullptr) { // the first node

3 root = new Node(key, value); // A1

4 } else { // initialize pointers and iterators

5 Node head; // A2

6 Node *it, *parent, *grand, *grandgrand = nullptr;

7 parent = &head;

8 it = parent->right = root;

9 Direction dir, last; dir = Left;

10 while(true) {

11 if (it == nullptr) { // insert the new node here

12 parent->dir = it = new Node(key, value); // A3,A4

13 } else if (isRed(it->left) and isRed(it->right)) {

14 // recolor

15 it->color = Red; // A5

16 it->left->color = it->right->color = Black;

17 }

18 if (isRed(it) and isRed(parent) // need rotation?

19 rebalance(grandgrand, grand, last); // A6,A7,A8,A9,A10,A11

20 if (it->key == key) break; // key exists already

21 // traverse one level down the tree

22 last = dir; dir = (it->key < key) ? Right : Left; // A12

23 grandgrand = grand;

24 grand = parent; parent = it;

25 it = it->dir;

26 }

27 // update root

28 root = head.right; // A13

29 }

30 // ensure the root is black

31 root->color = Black; // A14

32}

Figure 3: Top down insert based on Guibas and Sedgewick [24] and J. Walker.2
The labels show the state of the state machine in Figure 6.

Guibas and Sedgewick [24] introduced top-down approaches for inserting and
removing key-value pairs for dichromatic trees, see Figure 3. As they are top-
down algorithms, they do not require keeping a stack, but only keep a few
pointers up the tree—the iterators. They are mainly used for playing the
roles/anchors in tree rotations. They also use a fake head node to simplify
corner-cases. We derived insert and remove (Figure 3 and 4) from Julienne
Walker,2 who uses the same concepts. To avoid black violations, we insert the
new node as a red node at the bottom. However, inserting a red node can yield
red violations, which can be resolved by promotions [58], i.e., color flip,
single, and double rotation.

Inserting a node into an empty tree from the clean state _C_ is trivial (_C_
$\rightarrow$ _A1_ $\rightarrow$ _C_). Otherwise, we initialize helpers with
the init transition (lines 6–9; outgoing edges from _A2_). If a leaf node is
reached, we insert the new node (line 12; _A3_ $\to$ _A4_). Otherwise, we
might need to flip colors (lines 15–16), which can be done in one state
transition, because setting a new color is idempotent (outgoing edges of
_A5_).

The rebalance function (line 19 in Figure 3) performs single or double
rotations between the grand and grand grandparent. Single rotations are
converted into two state transitions: one for logging and one for executing
the rotation (Figure 6, _A10_ $\rightarrow$ _A11_ $\rightarrow$ either _A12_
(to continue) or _A13_ (key was found)). Double rotations need four state
transitions accordingly (_A6_ $\rightarrow$ _A7_ $\rightarrow$ _A8_
$\rightarrow$ _A9_).

Lines 23–25 descend the iterators one level down the tree (outgoing edges of
_A8_) to close the loop. In Sect. 8, we show how to update the iterators with
fewer state transitions and persist operations in some cases. Finally, the
root is set and colored black (lines 28–31; _A13_ $\to$ _A14_ $\to$ _C_).

The log’s size (4 cache lines of 64 bytes each) is independent of the size of
the tree (see Figure 6). Its main components are the key, the value, the
iterator, the parent, and the grandparent. In addition, it keeps some space
for redo logging, e.g., _Dir_ , _TmpNode_ , and _Sp_. The direction on the way
down the tree (_Dir_). A temporary node for tree rotations (_TmpNode_). An
anchor node on the way down the tree for remove in RBT (_Sp_). The majority of
the space would also be needed for non-persistent insert operation. Note that
the log does not keep a stack of size $\mathcal{O}(\log{n})$. Instead, it
suffices to keep a few pointers up the tree.

###  6.3 Remove

⬇

1void remove(root, key) {

2 if (root == nullptr) return; // empty tree

3 // initialize pointers and iterators

4 Node head; // C0

5 Node *it, *parent, *grand, *found = nullptr;

6 Direction dir = Right;

7 it = &head;

8 it->right = root;

9 while (it->dir != nullptr) {

10 // traverse one level down the tree

11 Direction last = dir; // R1

12 grand = parent;

13 parent = it;

14 it = it->dir;

15 dir = (it->key < key) ? Right:Left; // direction?

16 found = (it->key == key) ? it:found; // found?

17 if (not isRed(it) and not isRed(it->dir)) {

18 if (isRed(it->(!dir))) { // single rotation

19 parent = parent->last = single(it, dir); // R2,R3

20 } else if (not isRed(it->(!dir))) {

21 Node *s = parent->(!last); // R4

22 if (s != nullptr) {

23 Direction dir2 =

24 (grand->right == parent)? Right : Left;

25 if (not isRed(s->left) and not isRed(s->right)){

26 // recolor

27 parent->color = Black; // R5

28 s->color = Red;

29 it->color = Red;

30 } else if ((grand != nullptr) and

31 not((grand==&head) and (dir2==Left))){

32 // rotate?

33 rebalance(grand, parent, s, last); // R6,R7,R8,R9,R10,R11

34 // recolor

35 it->color = g->dir2->color = Red; // R12

36 grand->dir2->left->color = Black;

37 grand->dir2->right->color = Black;

38 } } } } }

39 if (found != nullptr) { // unlink and delete

40 found->key = it->key; // R13,R14

41 Direction dirL = (parent->right == it) ? Left:Right;

42 Direction dirR = (it->left == nullptr) ? Right:Left;

43 parent->dirL = it->dirR;

44 delete it;

45 }

46 // update root

47 root = head.right; // R15

48 root->color = Black; // ensure the root is black

49}

Figure 4: Top down remove based on Guibas and Sedgewick [24] and J. Walker.2
The labels show the state of the state machine in Figure 7.

While the algorithm for remove (Figure 4) looks more complex than for insert
(Figure 3), its state machine in Figure 6 is simpler than the one for
inserting. The control flow graph for remove is simpler and consists of a
single nested if statement. In each iteration, the state machine can jump into
exactly one place. In contrast, the inner part of the insert algorithm
contains two nested if statements. It allows jumping into two cases resulting
in a more complex state machine.

After the basic initialization, lines 11–14 move the iterators one level
further down the tree. It uses the even-odd optimization described in Sect. 8,
so that all outgoing edges of _R1_ update the iterators. The single rotation
in line 19 uses _R2_ $\to$ _R3_. The color flip in lines 27–29 is idempotent.
Thus, a single state transition from _R5_ suffices. The same applies to the
color correction in lines 35–37 represented by _R12_.

[mode=tex]Figures/tree

Figure 5: Tree-nodes occupy 31 bytes aligned to 32 bytes, tree-pointers need 4
bytes, keys and values require 8 bytes each, and directions (_Dir_), the
balance (_Bal_), and colors (_Col_) take one byte each. The Next Node fills 7
bytes aligned to 8 bytes.

The balance operation in line 33 either executes a single rotation (_R6_ $\to$
_R7_) or a double rotation (_R8_ $\to$ _R9_ $\to$ _R10_ $\to$ _R11_).

###  6.4 Common state for Trees on NVRAM

The tree (Figure 5) is represented as a fixed-length array of tree nodes.
Pointers to nodes are thus indices into the array, so that the pointers remain
valid when the array is mapped to a different base address after a crash. The
first element is reserved for the special head node in the insert and remove
algorithms. The node data-structure is shared by Red-Black Trees and AVL
Trees. The Col (the color) field is used for RBTs. Up (up pointer ), Dir
(direction from parent), and Bal (the balance) are exclusively used for AVL
Trees. Up and Dir are needed to walk the tree back up again, see Sect. 5.2.

The programming model for NVRAM requires the tree to be a fixed-length array
[57]. The size of mmapped files for NVRAM cannot change. Increasing the tree’s
size further would require adding additional fixed-length arrays. The index
type would need to be updated accordingly (from IdxType to (ArrayIdxType,
IdxType)).

To support allocating new tree nodes after a crash, we use the _Next Node_
structure—a uint56_t. It stores the index of the next free array element. Note
though, we did not implement garbage collection. Despite a client releasing a
node, it cannot be used anymore. We only allocate from the head and do not
maintain free lists.

NVRAM-aware garbage collection and dynamic node allocation is provided with
Makalu [10], nvm_malloc [51], and PAllocator [43]. They could be used for our
tree data structure. The state and next node variable have to be updated with
atomic CAS operations. All other updates can use non-atomic stores, because we
can do redo logging.

###  6.5 State for Red-Black Trees on NVRAM

The main data structures to manage an RBT are stored in NVRAM: the tree, the
log, the state variable, and the next node (Figure 5 and Figure 6). For
concurrency control, we additionally maintain a multi-reader single-writer
lock in volatile memory (see Sect. 10).

[width=mode=tex]Figures/fsms2

Figure 6: NVRAM data structures and state machines for insert and remove for
Red-Black Trees with 15 (insert) and 16 (remove) states (rot=rotation,
init=initialize variables, add=insert new node, remove=remove a node,
descend=one step down the tree, root=update root, color=recolor nodes,
black=color the root black). Dashed edges flush to the log. The State fills 7
bytes aligned to 8 bytes.

The log is structured into four parts, each fitting into a single cache line:
data for the root node and the request to perform, data to redo the current
state transition, and even and odd data structures (see Sect. 8 for more
details on this) for traversing the tree.

###  6.6 State for AVL Trees on NVRAM

[width=mode=tex]Figures/avl-state

Figure 7: NVRAM data structures and state machines for insert and remove for
AVL Trees with 24 and 35 states. Dashed edges flush to the log. The State
fills 7 bytes aligned to 8 bytes.

The state for AVL Trees is similar to Red-Black Trees. While the log for Red-
Black Trees occupies four cache lines, the log for AVL Trees fits into two
cache lines. The overhead can mostly be accounted for the optimizations, see
Sect. 8, and the cache lines are only partially filled while the two cache
lines for AVL Trees are completely filled. Spreading the data over more cache
lines might improve performance further by reducing correlated cache misses,
but such optimizations are beyond the scope of this paper.

##  7 Remote Persisting with a Software Agent

Clients efficiently access our Red-Black Trees and AVL Trees with passive
target communication using RDMA. All buffers used for such communication have
to be registered with the network card, which creates _remote keys_. Clients
have to use remote keys to access the registered address range with RDMA
operations. Revoking the key would deny the client to access the address
space. To gain access to remote keys for address ranges with InfiniBand,
clients have to establish a connection and query a software agent that we run
on the server node. For each connection request by a client, the software
agent creates two client-specific memory registrations: (a) $\mathit{mr}_{d}$
and (b) $\mathit{mr}_{\mathit{nv}}$ with read and write privileges.

Memory registrations allow revoking the access privileges of individual users.
If a client starts a failure detector on $c$ and the failure detector claims
$c$ to be failed, the client asks the software agent to revoke access
privileges of $c$, i.e., it invalidates its remote key. This is a way to
ensure client $c$ cannot access the data any longer. The client can then
safely release locks held by $c$. After a power loss, the DRAM region will be
initialized with zeros. The locks lose their value as the remote keys became
invalid and can safely be reset to not taken. Poke and Hoefler [46] also use
memory registration and InfiniBand’s QP mechanism to handle access rights, but
fail to realize that locks, see Sect. 10, or atomic operations are required to
prevent data-races.

As there is no hardware support for remote data persisting yet, the software
agent also provides cache flushing as a service.

##  8 Optimizations

Figure 8 shows the epochs by category for inserting resp. removing $10^{7}$
keys into Red-Black Trees. There are $\mathcal{O}(1)$ single and double
rotations per operation on average and one color flip as can be expected [58].
Some categories reflect necessary steps for starting resp. completing
operations, e.g., removing the found node, updating the root, initializing the
variables for the search, and flushing the current command. While the cost for
all operations is in $\mathcal{O}(\log{n})$, the number of state transitions
are dominated by shuffling the iterators for tree traversal.

As we cannot update the iterators in place, we need to use the redo log. The
canonical approach requires for each loop iteration two state transitions (4
epochs). In the first, it flushes the old iterators to the log. In the second,
it updates the new iterators to go one level deeper into the tree. Instead, we
implemented an even-odd scheme. All iterators are stored twice to have
disjoint read and write sets. In even rounds through the loop, the first set
is written. In odd rounds, the second set is written. Thus, we need only one
state transition and the previous iterators form the redo log to go one level
down the tree. A set of iterators fits into a single cache line, which
supports the even-odd scheme and reduces flush costs. We use one bit of the
state variable to store whether we are in an even or odd round:

⬇

struct SV {bool:1 Even{1},uint56_t:55 State{0}} EvenState;

Figure 8: Average number of epochs for inserting resp. removing $10^{7}$ keys
in random order in Red-Black Trees. Figure 9: Average number of epochs for
inserting resp. removing $10^{7}$ keys in random order in AVL Trees.

If the next loop iteration does not perform any rotations or recoloring, it
can be skipped. It does not change the tree. For inserts, we added _unlimited
look-ahead_ (LA): instead of going exactly one level down into the tree in
each iteration, we progress the iterators directly to the next level that
needs balancing or recoloring.

Figure 8 shows the average number of epochs, i.e., flushes for inserting resp.
removing $10^{7}$ keys in random order [35] into RBTs. Insert and remove are
dominated by the tree traversal, but unlimited look-ahead (LA) almost
eliminates the costs. Figure 9 shows the transitions for AVL Trees. Add is
dominated by the loop walking down the tree. Look-ahead does not iterate
through the loop. Remove is dominated by push stack, which stores in nodes the
pointers to their parents. Again AVL Trees are more expansive than RBTs. In
both experiments, keys are inserted on average in depth 21. The final Red-
Black Tree has a depth of 29 and the AVL Tree has a depth of 28. It is
balanced more strictly.

The AVL Tree insert algorithm [31] is split into two phases. First, it walks
down the tree and searches the parent of the new node. On the way down, it
saves two balancing points. In the second phase, it inserts the new node and
uses the balancing points to rebalance the tree. The first loop can be
replaced by two state transitions, because it is almost side-effect
free—except for storing the balancing points. The approach is similar to the
look-ahead for RBTs.

The AVL Tree remove algorithm is more challenging, because the loops walking
down the tree store parent pointers in the nodes. Skipping loop iterations is
challenging. The last loop walks up the tree and balances it. There are fewer
opportunities for skipping iterations.

##  9 Implementation Details

The programming model for NVRAM [57] maps files into memory using mmap, which
provides direct access (DAX) to the NVDIMM. Mapping a file again after a power
failure may yield a different base address. So, all memory accesses have to be
explicitly adjusted to the corresponding address range. This is necessary to
consistently access the same data after a power loss. Makalu [10] is a
persistent heap manager, which hides this problem from users.

For simplicity, we placed the log structure and the tree, an array of nodes,
into different files. There are pointers between nodes and between the log and
the nodes, which have to be adjusted to the base addresses. The following
assignment is completely handled by the compiler.

⬇

log->root->left->color = log->save->right->color;

There are no means to either control or adapt the intermediate memory
accesses. For NVRAM, we need to control all memory accesses. We have to map
and adjust them to their respective locations in mmapped address ranges. For
remote access, we need to know all addresses and intermediate steps to invoke
put and get calls accordingly.

expression | mmapped file
---|---
log->root | log file
log->root->left | tree file
log->root->left->color | tree file
log->save | log file
log->save->right | tree file
log->save->right->color | tree file

The only feasible solution is to manage memory accesses by the user instead of
the compiler. Thus, for memory accesses and persist operations, we wrote our
own embedded domain specific language (DSL) based on expression templates
[60].

The DSL provides a declarative language for describing memory addresses
including all intermediate steps—the path. Instead of using expressions such
as log->root->left->color, we assign types to each memory address, e.g.,
ColorInNode<LeftInNode<RootInLog>> address = {log};. Each memory access can be
seen as a path of intermediate memory accesses. The DSL allows programmers to
describe memory accesses and persist operations declaratively while ignoring
the peculiarities of the underlying programming model. For each memory access,
the runtime maps the request to the corresponding object (log, nodes, next
node, and state variable) and its associated mapped file. The access is
applied to the address space with the offset adjusted accordingly. This allows
development on machines with and without NVRAM and facilitates remote access.
For local development, we simply use malloc to simulate mmapped files. For
machines with NVRAM, we rely on the PMDK for mmapping. For remote access, we
use PMDK to mmap files and UCX 333http://www.openucx.org for communication
with RDMA. Additionally, our DSL allows us to transparently experiment with
different cache flushing and caching strategies. The runtime can map persist
operations to the different persist operations described in Sect. 3.2. For
remote access, we can cache the results of gets.

The following updates the key and value in the log:

⬇

WriteOp<typename LogAddress::Key, KeyValue> W1 =

{LogAddress::Key(log), KeyValue(key)};

WriteOp<typename LogAddress::Value, ValueValue> W2 =

{LogAddress::Value(log), ValueValue(value)};

flushOp(W1, W2);

WriteOp and flushOp are the customization points. Each WriteOp has a source
and a destination memory location. It performs a read and a write. flushOp
executes all write operations. As memory locations for read and write are
described by paths, they have to be evaluated first. They may require a
sequence of plain loads for local access or gets for remote access. Each
WriteOp could execute the assignment followed by a clwb and the flushOp
invokes an sfence to finish the epoch. For our tree code, the largest epoch
(in AVLT remove) invokes WriteOp nine times.

##  10 Multi-Reader Single-Writer Locks
with $f$-fairness over RDMA

Data structures with concurrent writers can show greatly reduced performance
[47]. Thus, we use multi-reader single-writer (mrsw) locks [19] to limit the
number of concurrent writers. It is sufficient to store the mrsw-lock in DRAM,
because after power losses remote keys become invalid (cmp. Sect. 7).

Two distributed lock servers based on RDMA were developed by Narravula et al.
[40] and Chung and Zamanian [13] with similar designs. They both use atomic
CAS and fetch&add to update the lock data structure (see top of Figure 10). In
exclusive mode, the _excl_ field holds the client’s process id (pid) [5]
holding the lock. In shared mode, the _shrd_ field holds the number of clients
sharing the lock. The holders of the shared lock are anonymous, which hinders
to identify failed lock holders and to get the lock back into exclusive mode.
Thus, these designs are not well prepared for client failures. They also
cannot guarantee fairness, because readers can always starve any writer trying
to acquire the write-lock. Gerstenberger et al. [22] designed a similar lock
for one-sided communication in MPI, but here even the holder of the write lock
is anonymous. However, one could argue that as of today the behavior of failed
nodes in MPI is deliberately unspecified. The same concepts are used for
shared-memory as well. Bit-vectors (32-bit or 64-bit) are split into reader
and writer parts and atomic operations are used to update the value [37].

[mode=tex]Figures/lock-types

Figure 10: State for reader-writer locks with RDMA.

To tolerate client failures, all lock holders have to store their pid. A
stored pid is the proof that the lock is taken. Our data structure’s design is
shown in the bottom part of Figure 10. For a $k$-reader single-writer lock
with $f$-fairness, we use an array of $k$ 64 bit slots to hold the readers
$r_{0}$–$r_{k-1}$, one slot for the writer $w$, $f$ slots for the waiting
queue $\mathit{sl}_{0}$–$\mathit{sl}_{f-1}$, and one slot for the outer lock
($\mathit{lock\ owner}$), which has to be acquired to modify the lock data
structure itself. Each entry is either 0 or the pid of the respective client.
Using the lock-holder’s pid to indicate whether a lock is taken allows clients
to use failure detectors on lock-holders. If a client wants to acquire a taken
lock, it can either be taken because of contention or because the holder
failed. The client starts a failure detector on the lock-holder and retries to
acquire the lock to cover both cases.

Fairness (equal share and no starvation) would require a waiting queue with
sufficient capacity to hold all waiting clients, which is a theoretical but
not a practical solution. A compromise is $f$-fairness with a waiting queue of
length $f$. Clients in the queue are subject to fairness. They cannot overtake
each other. The first node is always the next to acquire its desired lock.
However, we cannot guarantee fairness for clients waiting to enter the queue.

When the desired lock becomes available, the process in the first slot of the
queue takes the outer lock, takes the desired lock, copies the other members
of the queue one step forward, sets the last element to zero, and releases the
outer lock. All operations require atomic CAS operations, as a crash of the
writing process during a non-atomic RDMA write may result in a slot with a
valid pid of a process not intending to hold a lock.

Due to the 64 bit size limitation of remote atomics, it is not possible to
shift the complete queue in a single CAS operation. Therefore, the outer lock
is needed to prevent other processes from interfering. During the shift, each
process in the queue is always stored at least once in it—either in the old
and/or new slot. If the shifting process fails, the fairness in the queue is
preserved. On success, the last slot becomes zero and is available for the
next client. Entering the queue does not require holding the outer lock. It is
a CAS with a zero entry, which may fail. A process holding a read or write
lock can release it at any time by zeroing its slot. It does not have to
acquire the outer lock beforehand.

##  11 Simulating Power-Failures

To validate our implementation, we simulate power failures by killing
processes with SIGKILL following the approach used by NV-Heaps [14]. We start
a process doing insert resp. remove operations. At a later time, we kill the
process. Similar to a power failure, we lose all transient data. As the
process and thus the mmapped address range does not exist anymore, dirty cache
lines cannot be written back. The process could have been killed at any
instruction of any state transition. Afterwards, we start a new process that
recovers the current state and progresses to the clean state. The two
processes actually use the same code. While the former assumes that it is in
the clean state, the latter actually reads the current state from the file.

The testing revealed an issue with idempotence. We killed a process during a
tree rotation. The recovery process obviously executed the tree rotation
again, but tree rotations were not idempotent at that time. As discussed in
Sect. 5.1, failures during tree rotations can lose sub-trees. The challenge
with tree rotations is that they read and write the same memory locations. In
the example, we could lose access to Q, the pivot, or B. To make them
idempotent, we have to store all read values in the redo log. Thus, we have to
keep pointers to all three of them in the redo log to separate the read and
write sets. Since then, we have run more than 2,000,000 tests without
revealing any further issues.

##  12 Evaluation

For all experiments with NVDIMM-N and Infiniband, we used one server with two
Intel Xeon Gold 6138 and one server with two Intel Xeon Silver 4116 CPUs. Each
server has 192 GiB main memory and two 16 GiB NVDIMM-N. They are connected
with an InfiniBand FDR network (ConnectX-3). We used CentOS 7.5, Clang 6.0.0,
PMDK 1.5.1, and UCX 1.5.

For each measurement, we report the median among 1,000 samples. The 99 percent
confidence interval (CI) is always within the 1.5 percent of the reported
medians. Extremely short runs show slightly larger percentages.

Red-Black Trees and AVL Trees are self-balancing binary search trees. Each
node has at most two children. There are no high radix variants. They do not
amend themselves to the optimizations commonly used for B and B+-trees. Red-
Black Trees and AVL Trees are simply not competitive. Our contributions are
not in the area of optimizations for speed, but we designed a new transaction
system with $\mathcal{O}(1)$ log-space, in-place updates, and RDMA. Thus, we
did not compare the performance of our implementation with highly optimized
B+-trees. We want to analyze our optimizations and the scalability of our
approach itself. We used the data structures as shown in Figure 6 and Figure
7. The constant-size redo logs were used for trees from 0 to $10^{7}$ nodes.

###  12.1 Local Performance for Red-Black Trees and AVL Trees with NVDIMM-N

For all local experiments, we used the Xeon Gold. As Figure 6 shows, sequences
through the state machine often alternate between flushing to the log and
reading the log back to update the tree. This concept is needed to facilitate
idempotent updates of the tree. This style of micro-transactions performs well
with persistence mechanisms based on write-backs without invalidation and can
take full advantage of cache hierarchies. According to Intel Corp. [28], clwb
should show such behavior, but our evaluation shows no significant differences
between clwb and clflushopt—neither in micro-benchmarks nor in the shown Red-
Black Tree and AVL Tree benchmarks. clflush is consistently slower than clwb
and clflushopt.

For all local benchmarks, we varied the number of keys inserted into empty
trees. The range covers 10 to $10^{6}$. Keys were inserted in random order.
For remove, we re-used the filled tree and removed all items in a different
random order.

Figure 11: Insert throughput for Red-Black Trees and AVL Trees both with look
ahead with NVDIMM-N.

For small trees, the performance is worse than for larger trees, cmp. Figure
11. For trees larger than 100 keys, the performance stabilizes. It could be
due to the fact that for small trees insert operations touch a larger share of
the tree, i.e., they flush out a large part of the tree. For larger trees,
large parts of the tree remain untouched and can be accessed without cache
misses in the next operation. If you insert a key on the left side, it will
evict parts of the tree on the path down from the caches. If the next insert
is on the right side, there will be only a low number of cache misses. If the
tree is small, the two paths will overlap and cause more cache misses.

Figure 12: Remove throughput for Red-Black Trees and AVL Trees both without
look ahead with NVDIMM-N.

According to Tarjan [58], Red-Black Trees and AVL Trees only need
$\mathcal{O}(1)$ balance operations per insert on average. With the
optimizations described in Sect. 8, we almost eliminate the logarithmic part
of the insert operation. As expected, the insert costs are independent of the
size of the tree. It also shows again that Red-Black Trees are faster than AVL
Trees. Red-Black Trees might reduce the costs for insert by leaving the trees
less balanced than AVL Trees, see Sect. 5. Despite Cormen et al. [18],
Adel’son-Vel’skii and Landis [1] suggesting that the throughput should
decrease with the depth of the tree, we can keep it constant.

The costs for remove are much higher than for insert, cmp. Figure 12. Note
that we only tried to optimize insert operations. The expected costs per
remove are $\mathcal{O}(\log N)$. Red-Black Trees and AVL Trees perform
$\mathcal{O}(1)$ balance operations per remove on average. As expected AVL
Trees are slower than Red-Black Trees. The gap is much smaller.

Figure 13: Insert throughput for Red-Black Trees and AVL Trees both with look
ahead with Intel Optane. Figure 14: Remove throughput for Red-Black Trees and
AVL Trees both without look ahead with Intel Optane.

For the evaluation of their RBT code Wang et al. [63] simulated NVDIMM, STT-
RAM, and PCM. For insert with $10^{6}$ resp. $2^{10}$ keys, they achieved:
666,666, 166,666, and 52,600 inserts per second. It shows that the workload is
latency sensitive. For simulating NVDIMMs, they used plain DRAM. Our hardware
setup differs from theirs, but our NVDIMM-Ns run at a lower clock than DRAM.
With close to 400,000 inserts per seconds for RBTs, we are close despite a
completely different approach. Our AVL Trees are slightly slower because they
keep the tree more balanced and thus require more epochs.

###  12.2 Local Performance for Red-Black Trees and AVL Trees with Intel
Optane

For the experiments with Intel Optane, we used one server with two Intel Xeon
Platinum 8260L CPUs. It has 3 TB Apache Pass. We used CentOS 7, GCC 9.1, and
pmdk 1.7.1.

According to [29, 64] Optane has a three times higher latency than DRAM in
idle mode. Under load, the latency and bandwidth depends on the access
pattern. While the shape of the graphs for NVDIMM-Ns and Intel Optane are
similar, Intel Optane is slower by a factor of 3-5x.

The optimizations for insert keep the performance constant despite the trees
growing. For remove the performance drops with the size as expected. In all
experiments with Intel Optane the performance of clwb and clflushopt is
indistinguishable, see Figure 13 and Figure 14.

###  12.3 Gain of Optimizations

To analyze the improvements of our optimizations, see Sect. 8, we compared the
performance with and without look-ahead, see Figure 15. For both kinds of
trees, the gain is over a factor of 2.5x in throughput.

Figure 15: Insert throughput for Red-Black Trees and AVL Trees with and
without look-ahead (LA) using clwb.

###  12.4 Remote Performance via RDMA

For all experiments with InfiniBand, the Xeon Silver served as client, while
the Xeon Gold served as server. For all measurements, we inserted 1,000 keys
in random order into an empty tree. With flushing, every flush epoch ends with
a ping pong message from the client to the software agent on the server to
persist the data. The workload needs $\approx$ 40,000 flush requests. With
caching enabled, we cache all read requests to the redo log. The client keeps
a local copy. All write requests are applied accordingly. Accesses to the tree
are never cached.

Table 1: Remote inserts via RDMA and software agent based flushing (RBTs).

AVLT | No Cache | Cache
---|---|---
No Flush | 2,145/s | 2,150/s
Flush | 1,867/s | 1,866/s

RBT | No Cache | Cache
---|---|---
No Flush | 2,091/s | 2,542/s
Flush | 1,922/s | 2,312/s

With caching and flushing enabled (Table 1), we reach more than 2,300 inserts
per second for RBTs and 1,800 inserts per second for AVL Trees. Remote
transaction processing is latency bound because of gets and there is no
efficient way for remote persisting with a passive target yet. The
unsatisfactory performance of the cache is due to the fact that accesses to
the tree are not cached. Furthermore, it does not affect communication with
the software agent.

##  13 Related Work

Trees on NVRAM. A number of systems were already proposed to manage tree data
structures with persistent memory. A popular tree variant in this area are
B+trees [16], which store all values in the leaves. CDDS B-Tree [61], for
example, relies on 8-byte writes and a version system for inserts as long as
free slots are available in leaf nodes. Otherwise, it uses shadow copying to
split the node and to update the inner nodes. On recovery, it uses its version
system to discard all interrupted operations. Similarly, NV-Tree [65] stores
all values in leaf nodes. While the leaf nodes are stored in NVRAM, here, the
inner nodes are stored in DRAM and can be restored after a power failure. To
further minimize the cost of flushing, entries in leaf nodes are appended to
the corresponding leaf node and remain unsorted. Full leaf nodes are split
using shadow copying. Rebalancing is not done on-the-fly but as a separate
operation that recreates the inner nodes and makes them the current ones
atomically. The wB+Tree [12] also mitigates the costs of flushing by keeping
node entries unsorted to avoid entry movements on insert. This allows inserts
with only a few 8-byte writes and shadowing. Two B+tree algorithms exploiting
weak memory models and allowing temporal inconsistencies are FAST and FAIR
[27]. The Bztree [7] is a multi-threaded B+Tree. It relies on Persistent
Multi-Word CAS (PMwCAS) and an epoch-based garbage collection scheme.

For radix trees, WORT [32] maintains a tree shape independent of the insertion
order. It neither needs nor supports balancing. Inserting items on leaves or
leaf paths and pointer updates can be done with atomic 8-byte writes. For more
sophisticated adaptive radix trees, shadow copying is used.

Most research focuses on variants of B-trees with often more than two children
and optimizations for external memory. In most cases, new keys can be added in
leaf nodes with a few flushes without any re-balancing.

Red-Black Trees in NVRAM were discussed in Wang et al. [63] for the first
time. While they implemented a more complex tree kind than before, they still
relied on shadow copying and a versioning system to distinguish between the
copy and the real tree. They maintain something close to a shadow tree with
some efforts to minimize overhead. Operations are performed on the shadow
tree. An atomic pointer update switches between the shadow and the current
tree. Wang et al. [63] also show that update operations on RBTs are not local
operations. It does not suffice to do shadow copying on individual nodes. It
requires shadow copying of larger fractions of the tree.

All these systems handle requests in a blocking way and operations often
become visible with the last 8-byte atomic pointer update. After a crash, it
is challenging for them to identify aborted resp. the last successful
operation. Highly desirable properties such as exactly once semantics, see
Sect. 4.3, are hard to achieve. In contrast, with our state machine approach,
we can guarantee eventual success after accepting the command to the redo log
and support exactly once semantics.

Transactions on NVRAM. Systems supporting generic transaction processing on
NVRAM based on redo logging are, for example, SoftWrAP [23] and DudeTx [33].
They use a mix of shadow-memory and redo logging where all memory accesses
during a transaction are aliased into a volatile memory region and writes are
stored in a persistent redo log immediately or when all work of the
transaction is done. For DudeTx, the redo log is then applied to the actual
data stored in persistent memory in a final step. With language extensions,
Mnemosyne [62] provides primitives for working with persistent memory.
Variables can be marked as persistent. Code regions marked as atomic will be
executed with durable transactions. It hooks into a lightweight software
transaction system to implement write-ahead redo logging.

Other systems base their transaction system on write-ahead and undo logging
[52]. First, all store operations are written to the undo log before the real
transaction is executed. In case of a power failure, uncompleted transactions
are rolled back. The NV-Heaps system [14] provides its own heap manager,
specialized pointers, and atomic sections for persistent memory. For
transactions, it keeps a volatile read log and a non-volatile write log. In
case of an abort or power failure, it rolls back all changes.

Here, the literature seems to be undecided between undo and redo logging.
However, undo logging suffers from more flush operations compared to redo
logging. Shadow memory is a neat way to exploit the fact that there are two
types of memories available—volatile and non-volatile—with different
performance characteristics. It provides isolation and can leverage the
benefits of caches. Our approach of in-place updates is seldomly found in the
literature.

Logging in Databases. The quasi-standard algorithm for write-ahead logging
(WAL) with no-force and steal policies, ARIES [39], has influenced the design
of many commercial databases. It is optimized for spinning disks and maintains
an append-only log. The log contains undo and redo records. For recovery, it
goes through 3 phases: (a) analyze the log for uncommitted and aborted
transactions, (b) redo finishable transactions, and (c) undo the remaining
transactions. In our approach, we only us a fixed-size redo log. While Aries
uses write-only WAL, we read the log during epochs to facilitate idempotence.
Our analysis phase simply identifies the current state and continues from
there.

While ARIES optimizes for sequential writes, MARS [15] exploits the fact, that
SSDs support high random access performance. It introduces the concept of
editable atomic writes (EAW), which are essentially redo logs. The full
transaction is executed in a redo record and on commit the system applies the
transaction atomically. On failure, it can simply reapply the redo log. In
contrast, we write the data directly into the data structure. The transaction
becomes re-doable because of the redo log created in the previous epoch. We
always split large transactions into a sequence of micro-transactions. For
NVRAM, redo logs provide lower costs. They reduce the number of flushes in
contrast to undo logs. We can also avoid complex log pruning mechanisms,
because the log has a fixed size and every operation re-uses the log of the
previous operation.

##  14 Discussion of Correctness

_General approach._ It is a standard technique in compiler construction to
convert code into control flow graphs with basic blocks. For the execution of
this representation we can use state machines. It tracks which basic black is
currently executed and which are the legal successor blocks. State transitions
correspond to the execution of basic blocks. Large basic blocks can be split
into a sequence of smaller ones without changing the algorithm. Additionally,
splitting a basic block into two: (a) reading from the data structure and
writing to the log and (b) reading the log and updating the data structure,
ought to make both basic blocks idempotent. This is a common task for
databases with appropriate logging. The size of the basic block resp. the
number of stores influences the size of the log.

_Red-Black Trees and AVL Trees._ In Sect. 11, we discussed our testing
approach. After a crash, we verified that we can recover and return to the
clean state. Furthermore, after the recovery we checked whether the tree is
correct, i.e., correctly balanced and colored. For all experiments in Sect.
12, we inserted $k$ keys into an empty tree and removed the same $k$ keys in a
different order from the tree. This indicates that the state machines are
correct. Otherwise this would yield corrupt trees. During the development of
the state machine, we extensively tested the state machine. After each insert
or remove operation, we verified that the tree is correct and the number of
nodes was as expected.

##  15 Discussion of Limitations

For remote access, message passing might in some cases provide higher
performance than RDMA, but it is a completely orthogonal approach to shared
memory for local access. It would require two completely different transaction
systems, but our goal was to design one transaction system for local and
remote usage. As shown in Sect. 9, we abstract from local and remote access
and use one common implementation for both.

For B and B+ trees, insert, remove, and balancing are operations of limited
scope. They do not need transactions. The algorithms for these trees are of
low complexity and the corresponding state machines would be tiny. They are
tuned for absolute performance. The literature went for high radix trees for
performance reasons with low balance costs. However, for Red-Black Trees and
AVL Trees balancing is the common case [58]. Red-Black Trees and AVL Trees are
simply not competitive and serve other demands.

As discussed before, data structures that need an auxiliary space, which is
not in $\mathcal{O}(1)$, cannot be supported with a constant size log.
Allocating additional memory would violate our assumptions. The only option
left is store the auxiliary data in the data structure. AVL remove needs a
stack of $\mathcal{O}(\log{n})$. We use the common technique of maintaining
pointers to parents. In theory, that would induce space overhead in each tree
node. The initial data layout for the Red-Black Trees was 32 bytes. It had
sufficient unused space to add up-pointers (Up and Dir) without needing to
change its size, see Figure 5. Insert and remove in trees can often be
implemented with top-down algorithms, which only need constant-sized auxiliary
space. Linked lists and hash-tables also need constant-sized auxiliary space.

Atomic CAS for NVRAM [34, 44] brings its own challenges. Atomic operations are
commonly used, because (a) they do no tear and (b) provide protection against
concurrent access. In our approach, we are only interested in the former
property, because we use locks for thread safety. In this paper, we consider
CAS more like a read, modify, and atomic update resp. store operation of 8
bytes (cmp. Sect. 2) as there is no contention.

##  16 Conclusion

We presented a new transaction system for complex data structures in NVRAM
that provides exactly once semantics and linearizable durability with a redo
log of constant size. It splits large transactions into smaller micro-
transactions and uses a state machine approach to perform larger transactions
step-wise. Every accepted transaction will eventually succeed and will never
be aborted. For local and remote access, we use the same primitives: load,
store, atomic update, and persist. This allowed us to design one transaction
system that runs locally and with InfiniBand for remote access. As our
approach is not prepared for concurrent access, we use locks to control
concurrency. For remote access, we designed a fault-tolerant lock with
$f$-fairness.

Wang et al. [63] showed the first Red-Black Tree implementation for NVRAM, but
their approach is based on shadowing the whole tree. We presented, to the best
of our knowledge, the first AVL Tree implementation for NVRAM and the first
Red-Black Tree implementation for NVRAM without shadowing and with updates
‘in-place’. These trees are algorithmic far more challenging than the trees
covered in the literature so far. Insert and remove are global operations
instead of a sequence of operations with limited scope. Thus, they need
transactions.

Shadowing can claim that data structures are consistent all the time. This
approach atomically replaces parts of a data structure with new data.
Intermediates steps are not visible. Wang et al. [63] atomically replace the
old tree with the new one. There is also no need for recovery, but it fails at
exactly once semantics. In our approach, the data structure might be
inconsistent after a crash, but it is recoverable all the time. We see
recovery as finishing the interrupted operation, i.e., moving forward to the
clean state. Likewise, we support exactly once semantics. By using a constant-
sized log, we avoid any overhead for dynamic log allocation, log pruning, and
keeping a shadow copy of the whole tree.

##  17 Availability

Our code is on GitHub 444https://github.com/tschuett/transactions-on-nvram
under the Apache License 2.0.

## Acknowledgments

The authors thank ZIB’s Supercomputing department and ZIB’s core facilities
unit for providing the machines and infrastructure for the evaluation. This
work received funding from the German Research Foundation (DFG) under grant RE
1389 as part of the DFG priority program SPP 2037 (Scalable data management
for future hardware). This work is partially supported by Intel Corporation
within the “Research Center for Many-core High-Performance Computing” (Intel
PCC) at ZIB.

## References

  * Adel’son-Vel’skii and Landis [1962] Georgy Adel’son-Vel’skii and Evegnii Landis.  An algorithm for the organization of information.  _Dokl. Akad. Nauk SSSR_ , 146:263–266, 1962.
  * Aguilera and Terry [2016] Marcos K. Aguilera and Douglas B. Terry.  The many faces of consistency.  _IEEE Data Eng. Bull._ , 39(1):3–13, 2016.  URL http://sites.computer.org/debull/A16mar/p3.pdf.
  * Aho et al. [1986] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman.  Compilers, principles, techniques.  _Addison Wesley_ , 7(8):9, 1986.
  * Allen [1970] Frances E. Allen.  Control flow analysis.  _SIGPLAN Not._ , 5(7):1–19, July 1970.  ISSN 0362-1340.  doi: 10.1145/390013.808479.  URL http://doi.acm.org/10.1145/390013.808479.
  * Armstrong [2013] Joe Armstrong.  _Programming Erlang: Software for a Concurrent World_.  Pragmatic Bookshelf, 2013.  ISBN 193778553X, 9781937785536.
  * Arulraj et al. [2015] Joy Arulraj, Andrew Pavlo, and Subramanya R. Dulloor.  Let’s talk about storage & recovery methods for non-volatile memory database systems.  In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_ , pages 707–722, New York, NY, USA, 2015. ACM.
  * Arulraj et al. [2018] Joy Arulraj, Justin Levandoski, Umar Farooq Minhas, and Per-Ake Larson.  Bztree: A high-performance latch-free range index for non-volatile memory.  _Proc. VLDB Endow._ , 11(5):553–565, January 2018\.  ISSN 2150-8097.  doi: 10.1145/3187009.3164147.  URL https://doi.org/10.1145/3187009.3164147.
  * Bayer [1972] Rudolf Bayer.  Symmetric binary b-trees: Data structure and maintenance algorithms.  _Acta informatica_ , 1(4):290–306, 1972.
  * Bayer and McCreight [1972] Rudolf. Bayer and Edward McCreight.  Organization and maintenance of large ordered indexes.  _Acta Informatica_ , 1(3):173–189, Sep 1972.  ISSN 1432-0525.  doi: 10.1007/BF00288683.  URL https://doi.org/10.1007/BF00288683.
  * Bhandari et al. [2016] Kumud Bhandari, Dhruva R. Chakrabarti, and Hans-J. Boehm.  Makalu: Fast recoverable allocation of non-volatile memory.  In _Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ , OOPSLA 2016, pages 677–694, New York, NY, USA, 2016. ACM.  ISBN 978-1-4503-4444-9.
  * Chandra et al. [1996] Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg.  The weakest failure detector for solving consensus.  _Journal of the ACM (JACM)_ , 43(4):685–722, 1996\.
  * Chen and Jin [2015] Shimin Chen and Qin Jin.  Persistent b+-trees in non-volatile main memory.  _Proc. VLDB Endow._ , 8(7):786–797, February 2015\.  ISSN 2150-8097.  doi: 10.14778/2752939.2752947.  URL http://dx.doi.org/10.14778/2752939.2752947.
  * Chung and Zamanian [2015] Yeounoh Chung and Erfan Zamanian.  Using RDMA for lock management.  _CoRR_ , abs/1507.03274, 2015.  URL http://arxiv.org/abs/1507.03274.
  * Coburn et al. [2011] Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson.  NV-Heaps: Making persistent objects fast and safe with next-generation, non-volatile memories.  _SIGPLAN Not._ , 46(3):105–118, March 2011.  ISSN 0362-1340.
  * Coburn et al. [2013] Joel Coburn, Trevor Bunker, Meir Schwarz, Rajesh Gupta, and Steven Swanson.  From ARIES to MARS: Transaction support for next-generation, solid-state drives.  In _Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles_ , SOSP ’13, pages 197–212, New York, NY, USA, 2013. ACM.  ISBN 978-1-4503-2388-8.
  * Comer [1979] Douglas Comer.  The ubiquitous B-tree.  _ACM Comput. Surv._ , 11(2):121–137, 1979.  doi: 10.1145/356770.356776.  URL http://doi.acm.org/10.1145/356770.356776.
  * Condit et al. [2009] Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin Lee, Doug Burger, and Derrick Coetzee.  Better I/O through byte-addressable, persistent memory.  In _Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles_ , SOSP ’09, pages 133–146, New York, NY, USA, 2009. ACM.  ISBN 978-1-60558-752-3.
  * Cormen et al. [2009] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  _Introduction to Algorithms, Third Edition_.  The MIT Press, 3rd edition, 2009.  ISBN 0262033844, 9780262033848.
  * Courtois et al. [1971] Pierre-Jacques Courtois, Frans Heymans, and David Lorge Parnas.  Concurrent control with readers and writers.  _Commun. ACM_ , 14(10):667–668, October 1971\.  ISSN 0001-0782.
  * Dechev et al. [2010] Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup.  Understanding and effectively preventing the aba problem in descriptor-based lock-free designs.  In _2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing_ , pages 185–192. IEEE, 2010.
  * Friedman et al. [2018] Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank.  A persistent lock-free queue for non-volatile memory.  In _Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria, February 24-28, 2018_ , pages 28–40, New York, NY, USA, 2018. ACM.
  * Gerstenberger et al. [2013] Robert Gerstenberger, Maciej Besta, and Torsten Hoefler.  Enabling Highly-Scalable Remote Memory Access Programming with MPI-3 One Sided.  In _Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_ , pages 53:1–53:12, New York, NY, USA, Nov. 2013. ACM.  ISBN 978-1-4503-2378-9.
  * Giles et al. [2015] Ellis R. Giles, Kshitij Doshi, and Peter Varman.  SoftWrAP: A lightweight framework for transactional support of storage class memory.  In _Mass Storage Systems and Technologies (MSST), 2015 31st Symposium on_ , pages 1–14, New York, NY, USA, 2015. IEEE Computer Society.
  * Guibas and Sedgewick [1978] Leo J. Guibas and Robert Sedgewick.  A dichromatic framework for balanced trees.  In _Foundations of Computer Science, 1978., 19th Annual Symposium on_ , pages 8–21, New York, NY, USA, 1978. IEEE Computer Society.
  * Herlihy and Wing [1990] Maurice P. Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  _ACM Trans. Program. Lang. Syst._ , 12(3):463–492, July 1990.  ISSN 0164-0925.  doi: 10.1145/78969.78972.  URL http://doi.acm.org/10.1145/78969.78972.
  * Hirai and Yamamoto [2011] Yoichi Hirai and Kazuhiko Yamamoto.  Balancing weight-balanced trees.  _Journal of Functional Programming_ , 21(3):287––307, 2011.  doi: 10.1017/S0956796811000104.
  * Hwang et al. [2018] Deukyeon Hwang, Wook-Hee Kim, Youjip Won, and Beomseok Nam.  Endurable transient inconsistency in byte-addressable persistent B+-tree.  In _16th USENIX Conference on File and Storage Technologies (FAST 18)_ , pages 187–200, Oakland, CA, 2018. USENIX Association.  ISBN 978-1-931971-42-3.  URL https://www.usenix.org/conference/fast18/presentation/hwang.
  * Intel Corp. [May 2019] Intel Corp.  Intel 64 and IA-32 architectures software developer’s manual, May 2019\.
  * Intel Corp. [September 2019] Intel Corp.  Intel 64 and IA-32 architectures optimization reference manual, September 2019.
  * Izraelevitz et al. [2016] Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott.  Linearizability of persistent memory objects under a full-system-crash failure model.  In Cyril Gavoille and David Ilcinkas, editors, _Distributed Computing_ , pages 313–327, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.  ISBN 978-3-662-53426-7.
  * Knuth [1998] Donald E. Knuth.  _The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching_.  Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998\.  ISBN 0-201-89685-0.
  * Lee et al. [2017] Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh.  WORT: Write optimal radix tree for persistent memory storage systems.  In _15th USENIX Conference on File and Storage Technologies (FAST 17)_ , pages 257–270, Santa Clara, CA, 2017. USENIX Association.  ISBN 978-1-931971-36-2.
  * Liu et al. [2018] Mengxing Liu, Mingxing Zhang, Kang Chen, Xuehai Qian, Yongwei Wu, Weimin Zheng, and Jinglei Ren.  DudeTx: Durable transactions made decoupled.  _ACM Trans. Storage_ , 14(1):7:1–7:28, April 2018\.  ISSN 1553-3077.
  * Marathe et al. [2017] Virendra J. Marathe, Margo Seltzer, Steve Byan, and Tim Harris.  Persistent memcached: Bringing legacy code to byte-addressable persistent memory.  In _9th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 17)_ , Santa Clara, CA, 2017. USENIX Association.  URL https://www.usenix.org/conference/hotstorage17/program/presentation/marathe.
  * Matsumoto and Nishimura [1998] Makoto Matsumoto and Takuji Nishimura.  Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator.  _ACM Trans. Model. Comput. Simul._ , 8(1):3–30, January 1998.  ISSN 1049-3301.  doi: 10.1145/272991.272995.  URL http://doi.acm.org/10.1145/272991.272995.
  * Mehlhorn and Tsakalidis [1986] Kurt Mehlhorn and Athanasios Tsakalidis.  An amortized analysis of insertions into avl-trees.  _SIAM Journal on Computing_ , 15(1):22–33, 1986\.
  * Mellor-Crummey and Scott [1991] John M. Mellor-Crummey and Michael L. Scott.  Scalable reader-writer synchronization for shared-memory multiprocessors.  In _ACM SIGPLAN Notices_ , volume 26, pages 106–113, New York, NY, USA, 1991. ACM.
  * Message Passing Interface Forum [2015] Message Passing Interface Forum.  _MPI: A Message-Passing Interface Standard Version 3.1_.  MPI Forum, 2015.
  * Mohan et al. [1992] Chandrasekaran Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz.  Aries: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging.  _ACM Trans. Database Syst._ , 17(1):94–162, March 1992.  ISSN 0362-5915.
  * Narravula et al. [2007] Sundeep Narravula, A. Marnidala, Abhinav Vishnu, Karthikeyan Vaidyanathan, and Dhabaleswar K. Panda.  High performance distributed lock management services using network-based remote atomic operations.  In _Cluster Computing and the Grid, 2007. CCGRID 2007. Seventh IEEE International Symposium on_ , pages 583–590, New York, NY, USA, 2007. IEEE Computer Society.
  * Nievergelt and Reingold [1973] Jürg Nievergelt and Edward Reingold.  Binary search trees of bounded balance.  _SIAM Journal on Computing_ , 2(1):33–43, 1973\.  doi: 10.1137/0202005.
  * Olivié [1982] Henk J. Olivié.  A new class of balanced search trees: half-balanced binary search tress.  _RAIRO. Informatique théorique_ , 16(1):51–71, 1982.
  * Oukid et al. [2017] Ismail Oukid, Daniel Booss, Adrien Lespinasse, Wolfgang Lehner, Thomas Willhalm, and Grégoire Gomes.  Memory management techniques for large-scale persistent-main-memory systems.  _PVLDB_ , 10(11):1166–1177, 8 2017.  doi: 10.14778/3137628.3137629.  URL http://www.vldb.org/pvldb/vol10/p1166-oukid.pdf.
  * Pavlovic et al. [2018] Matej Pavlovic, Alex Kogan, Virendra J. Marathe, and Tim Harris.  Brief announcement: Persistent multi-word compare-and-swap.  In _Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing_ , PODC ’18, pages 37–39, New York, NY, USA, 2018. ACM.  ISBN 978-1-4503-5795-1.  doi: 10.1145/3212734.3212783.  URL http://doi.acm.org/10.1145/3212734.3212783.
  * Pereira and Palsberg [2006] Fernando Magno Quintao Pereira and Jens Palsberg.  Register allocation after classical ssa elimination is np-complete.  In _International Conference on Foundations of Software Science and Computation Structures_ , pages 79–93. Springer, 2006.
  * Poke and Hoefler [2015] Marius Poke and Torsten Hoefler.  Dare: High-performance state machine replication on rdma networks.  In _Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing_ , pages 107–118. ACM, 2015\.
  * Scherer III and Scott [2005] William N. Scherer III and Michael L. Scott.  Advanced contention management for dynamic software transactional memory.  In _Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing_ , pages 240–248, New York, NY, USA, 2005\. ACM.
  * Schütt et al. [2007] Thorsten Schütt, Florian Schintke, and Alexander Reinefeld.  A structured overlay for multi-dimensional range queries.  In _European Conference on Parallel Processing_ , pages 503–513. Springer, 2007.
  * Schütt et al. [2008a] Thorsten Schütt, Florian Schintke, and Alexander Reinefeld.  Range queries on structured overlay networks.  _Computer Communications_ , 31(2):280–291, 2008a.
  * Schütt et al. [2008b] Thorsten Schütt, Florian Schintke, and Alexander Reinefeld.  Scalaris: reliable transactional p2p key/value store.  In _Proceedings of the 7th ACM SIGPLAN workshop on ERLANG_ , pages 41–48, 2008b.
  * Schwalb et al. [2015] David Schwalb, Tim Berning, Martin Faust, Markus Dreseler, and Hasso Plattner.  nvm malloc: Memory allocation for nvram.  In Rajesh Bordawekar, Tirthankar Lahiri, Bugra Gedik, and Christian A. Lang, editors, _ADMS@VLDB_ , pages 61–72, 2015.  URL http://dblp.uni-trier.de/db/conf/vldb/adms2015.html#SchwalbBFDP15.
  * Shin et al. [2017] Seunghee Shin, James Tuck, and Yan Solihin.  Hiding the long latency of persist barriers using speculative execution.  In _Proceedings of the 44th Annual International Symposium on Computer Architecture_ , ISCA ’17, pages 175–186, New York, NY, USA, 2017. ACM.  ISBN 978-1-4503-4892-8.  doi: 10.1145/3079856.3080240.
  * Skrzypczak et al. [2019] Jan Skrzypczak, Florian Schintke, and Thorsten Schütt.  Linearizable state machine replication of state-based CRDTs without logs.  In _Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing_ , pages 455–457, 2019.
  * Skrzypczak et al. [2020] Jan Skrzypczak, Florian Schintke, and Thorsten Schütt.  RMWPaxos: Fault-tolerant in-place consensus sequences.  _IEEE Transactions on Parallel and Distributed Systems_ , 31(10):2392–2405, 2020.
  * Sleator et al. [1986] Daniel Sleator, Robert Tarjan, and William Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  In _Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing_ , STOC ’86, pages 122–135, New York, NY, USA, 1986. ACM.  ISBN 0-89791-193-8.  doi: 10.1145/12130.12143.  URL http://doi.acm.org/10.1145/12130.12143.
  * Storage Networking Industry Association [February 2016] Storage Networking Industry Association.  NVM PM Remote Access for High Availability, February 2016.
  * Storage Networking Industry Association [June 2017] Storage Networking Industry Association.  NVM Programming Model v1.2, June 2017.
  * Tarjan [1983] Robert Endre Tarjan.  Updating a balanced search tree in O(1) rotations.  _Information Processing Letters_ , 16(5):253–257, 1983.  ISSN 0020-0190.
  * Tsakalidis [1985] Athanasios K. Tsakalidis.  Rebalancing operations for deletions in avl-trees.  _RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications_ , 19(4):323–329, 1985.
  * Vandevoorde and Josuttis [2002] David Vandevoorde and Nicolai M. Josuttis.  _C++ Templates: The Complete Guide_.  Addison-Wesley Professional, 1 edition, November 2002.  ISBN 9780201734843.
  * Venkataraman et al. [2011] Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell.  Consistent and durable data structures for non-volatile byte-addressable memory.  In _Proceedings of the 9th USENIX Conference on File and Stroage Technologies_ , FAST’11, pages 5–5, Berkeley, CA, USA, 2011. USENIX Association.  ISBN 978-1-931971-82-9.
  * Volos et al. [2011] Haris Volos, Andres Jaan Tack, and Michael M. Swift.  Mnemosyne: lightweight persistent memory.  In Rajiv Gupta and Todd C. Mowry, editors, _Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011_ , pages 91–104. ACM, 2011.  ISBN 978-1-4503-0266-1.  doi: 10.1145/1950365.1950379.  URL https://doi.org/10.1145/1950365.1950379.
  * Wang et al. [2018] Chundong Wang, Qingsong Wei, Lingkun Wu, Sibo Wang, Cheng Chen, Xiaokui Xiao, Jun Yang, Mingdi Xue, and Yechao Yang.  Persisting rb-tree into nvm in a consistency perspective.  _ACM Trans. Storage_ , 14(1):6:1–6:27, February 2018.  ISSN 1553-3077.  doi: 10.1145/3177915.  URL http://doi.acm.org/10.1145/3177915.
  * Yang et al. [2020] Jian Yang, Juno Kim, Morteza Hoseinzadeh, Joseph Izraelevitz, and Steve Swanson.  An empirical guide to the behavior and use of scalable persistent memory.  In _18th $\\{$USENIX$\\}$ Conference on File and Storage Technologies ($\\{$FAST$\\}$ 20)_, pages 169–182, 2020.
  * Yang et al. [2015] Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, and Bingsheng He.  NV-Tree: Reducing consistency cost for NVM-based single level systems.  In _13th USENIX Conference on File and Storage Technologies (FAST 15)_ , pages 167–181, Santa Clara, CA, 2015. USENIX Association.  ISBN 978-1-931971-201.