RMR-Efficient Detectable Objects for Persistent Memory and Their Applications

Over the last decade, the emergence of persistent main memory has reinvigorated research on shared memory algorithms. The ability to retain data across power failures and system crashes opens the door to faster recovery of in-memory data structures than is possible using the traditional approach of rebuilding such structures using state saved in slower secondary storage, and has precipitated a thorough reexamination of established theoretical abstractions. The persistent memory revolution has so far witnessed several reformulations of classic correctness properties and synchronization problems (e.g., [7, 31, 3, 24, 20]) into their recoverable counterparts, as well as the birth of more novel concepts such as Friedman, Herlihy, Marathe and Petrank’s notion of detectability [18, 19] – the capability to forensically determine the outcome of an operation that was interrupted by a failure.

The blossoming landscape of problems and solutions hints at a bright future for algorithmic research on persistent main memory, though the full perspective remains difficult to comprehend given limited connections between emerging concepts. This research takes important steps towards filling this gap by exploring the relationship between detectability, which we formalize using sequential specifications [6, 37, 39], and the recoverable mutual exclusion (RME) problem [24, 25], which is a modern take on the long-standing question of how to implement fault-tolerant mutex locks. In a nutshell, RME generalizes Dijkstra’s mutual exclusion (ME) problem [16] by allowing processes to crash at arbitrary times and recover by starting over. While it makes sense intuitively that objects of arbitrary types can be constructed using RME locks, existing literature focuses on recovering the internal state of the lock and overlooks the fundamental problem of recovering actions performed in the critical section. At best, compositions of RME locks have been considered where such actions are largely idempotent, and can be recovered by repeating the critical section. The use of detectable objects to solve RME is similarly unexplored, and we view this as a missed opportunity since the treatment of such problems from first principles is notoriously challenging (e.g., see [22, 34]). Advances along new research directions that simplify reasoning about failures and concurrency are urgently needed as the theory community takes aim at more complex synchronization problems in the realm of persistent memory.

Implementing detectable objects correctly and using them efficiently is itself technically challenging. Fundamentally, such object implementations face the problem that modern memory hierarchies combine persistent media, such as Intel Optane persistent memory, with volatile CPU registers that are used by primitive memory operations to return responses to the application program. In other words, it is not possible for a program to simply “look up” the outcome of its last memory operation before a failure, or even determine exactly which operation was the last one. Despite this, detectable objects must track the progress of operations across failures so that any process can resolve the status of its most recent operation, even if the corresponding state transition has already been overwritten by an operation applied by another process. Further perils lie ahead when detectable objects are used to solve more complex synchronization problems because such objects achieve only a partial separation of concerns between fault tolerance and concurrency control. To begin with, a recoverable algorithm must decide which of its possibly many detectable base objects need to be resolved, and in which order. Additional recovery state that is kept outside of the base objects (e.g., via checkpoint variables) may also be needed to guide recovery towards a consistent state. On the other hand, once the detectable objects are properly implemented and techniques for their correct use are developed, a new algorithmic style emerges where application-specific imperatives, such as enforcing linearizability [29] or mutual exclusion [16], can be insulated from mundane low-level recovery actions such as determining the outcome of a read-modify-write (RMW) hardware instruction after a failure.

Our main contributions in this paper are two-fold. First (Section 4), we present a universal construction of detectable RMW primitives. Our RME-based construction is the first to implement arbitrary RMW types while using a sublinear number of remote memory references or RMRs – expensive memory operations that traditionally define the time complexity of ME and RME algorithms – while ensuring strict linearizability [1]. We show experimentally that it performs well in comparison to prior lock-free and wait-free techniques. Second (Section 5), we leverage the detectable RMW primitive to devise a novel RMR-optimal RME algorithm, and deduce from the properties of this algorithm a lower bound on the worst-case RMR complexity of any generic construction of detectable RMW primitives. The unique algorithmic style emerging from this reduction opens the door to solving complex problems using a common execution path for both the system-wide and independent failure models, which previously required separate analyses, and relies only on a suitable implementation of the detectable base objects to achieve RMR efficiency in each failure model.

We combine Herlihy and Wing’s classic model of linearizable data structures [27] with features borrowed from recent research on crash recovery for persistent memory [7, 31, 25, 23, 3, 37]. A fixed set of $N$ asynchronous processes, denoted $p_1,p_2,\mathrm{\dots },p_N$, communicate by applying operations on shared base objects. Processes may fail by crashing, either independently or simultaneously, and may recover from crashes by restarting their execution from the beginning under the same process ID. Each base object has a sequential specification that describes its possible states and state transitions. We will assume that base object operations are atomic with the understanding that they can be either supported directly in hardware, or emulated in software via shared object implementations that specify an access procedure for each emulated operation. Base objects are persistent, meaning that their states are unaffected by crash failures. In addition, processes may use private volatile variables whose values are reinitialized during recovery from a failure. The algorithms presented in this paper can be adapted to more complex models that consider a volatile cache through judicious insertion of persistence instructions, for example using the transformations described in [31, 13].

Executions of algorithms are modeled using histories, which are sequences of system states and steps. A system state is the combination of values assigned to all program variables, shared and private, including program counters. There are three types of steps: a base object step represents the execution of one shared memory operation by a process along with bounded local computation (e.g., arithmetic and accessing private volatile variables); an invocation or response step represents the invocation of an operation on an implemented object or its response, respectively; and a crash step represents the crash failure of one or more processes. Crashes can be independent (affecting one process) or system-wide (affecting all processes simultaneously). We consider two types of algorithms in this paper: shared object implementations (Section 4) modeled as a collection of access procedures for different implemented operations, and recoverable mutual exclusion (RME) [24] (Section 5) modeled as a special infinite loop. Histories of RME-like algorithms comprise only base object and crash steps. Histories of implementations additionally contain invocation and response steps.

Histories of an algorithm must satisfy safety and liveness properties specific to that algorithm. For RME, where processes repeatedly execute a non-critical section (NCS), recovery section (RS), entry section (ES), critical section (CS), and exit section (XS), the fundamental safety property is mutual exclusion: at most one process can be in the CS at a given time. A bounded prefix of the ES called the doorway controls the order of entry into the CS in first come first serve (FCFS) RME locks. Liveness means that executions of the RS, ES, and XS eventually terminate, and is predicated on two assumptions: (1) the CS is bounded, and (2) the history is fair, meaning that if a process leaves the NCS, it continues taking steps until it completes the XS and returns to the NCS without crashing. The latter implies that if a process crashes during a passage, which is a sequence of consecutive executions of the RS, ES, CS, and XS, then it eventually begins another passage. A maximal sequence of passages by one process where only the last one ends in a complete execution of the XS is called a super-passage. For shared object implementations, we choose strict linearizability [1] as the main correctness property: implemented operations appear to take effect instantaneously between their invocation and response steps, and any operation interrupted by a crash failure must take effect prior to the failure or not at all. Liveness means that every implemented operation eventually returns a response, and is once again predicated on the history being fair, meaning that if a process invokes an operation then it must continue taking steps until the operation produces a response or the process crashes.

Some shared object implementations are detectable [18, 19], meaning that a process can resolve precisely the outcome of an operation that was interrupted by a crash. We formalize detectability using sequential specifications, following the trend established in [6, 37, 39, 32], whereby detection is accomplished by invoking a special resolution operation (called resolve) on the implemented object. Specifically, we adopt the unified sequential specification (UDSS) introduced by Moridi et al. [39], whereby resolve returns a triple representing the most recent detectable operation $op$ invoked by the calling process $p_i$ that took effect, or else if no such operation exists. Here $res$ is the response of $op$, and $tag$ is an auxiliary argument passed to $op$ to disambiguate successive invocations of $op$ that may return the same response (or no response at all).

We quantify complexity in terms of space, measured by counting the number of persistent base objects, and time, measured by counting remote memory references (RMRs) – expensive shared memory operations that necessitate communication on the interconnect that joins processors with memory. In the cache-coherent (CC) multiprocessor architecture, RMRs are closely tied to cache misses and invalidations. For analyzing upper bounds, we assume that every shared memory operation is an RMR unless a process reads an object that it has previously read, and which has not been overwritten since the most recent such read. In the distributed shared memory (DSM) model, each variable is statically defined as local to exactly one process and remote to all others, and an RMR is defined as any access to a remote variable. In special cases, algorithms or portions thereof may be wait-free [28], meaning that they terminate after a bounded number of steps in all executions.

In this research, we derive both upper and lower bounds on the worst-case RMR complexity per operation of detectable RMW objects (more precisely on objects that simultaneously support FAS and CAS) by connecting this topic formally to RME. In terms of upper bounds, our detectable objects have the same RMR complexity asymptotically as their underlying RME locks, and require only $O(N)$ additional space. As we discuss in Section 4.2, experiments conducted using Intel Optane persistent memory show that our objects scale better than alternatives obtained using lock-free and wait-free techniques [6, 36] for Fetch-And-Store operations. Our lower bound on RMR complexity pertains to the independent failure model, and shows that implementing detectable objects is as hard as solving the RME problem. We obtain this result by constructing a reduction from the latter problem to the former, and applying existing lower bounds on the RMR complexity of RME [9, 10]. The lower bound is tight, which makes our detectable object construction RMR-optimal for independent failures. The same holds for system-wide failures, where we achieve $O(1)$ RMR complexity. As summarized in Tables 1 and 2, we present the first sub-linear (i.e., $o(N)$) RMR bounds for detectable unconditional RMW operations such as Fetch-and-Store.

This section presents a generic RMR-efficient construction of detectable read-modify-write (RMW) primitives using an RME lock as the main building block. This result complements prior work (see Section 6) on detectable constructions of comparison primitives that achieve RMR-efficiency indirectly by guaranteeing wait-freedom. As we show later on in Section 5, detectable FAS and CAS primitives instantiated using our construction can be used to solve the RME problem efficiently and relatively straightforwardly, which establishes equivalence in terms of worst-case RMR complexity (per passage and per operation, respectively) between RME and any generic detectable RMW construction.

This section presents a lower bound on the RMR complexity of detectable objects. We obtain the bound by devising a novel RME algorithm that uses detectable objects for synchronization, and then applying known lower bounds for the RMR complexity of the RME problem [9, 10]. Although the algorithm does not break new ground in terms of RMR and space complexity for the RME problem, its design embodies a novel algorithmic style that may be of independent interest: a common execution path is used for both the system-wide and independent failure models, which previously required separate designs and analyses. The generic algorithm is then instantiated for a particular failure model by substituting a suitable implementation of the detectable base objects, which determines the overall RMR complexity.

Our algorithm, presented in Figure 4 is an adaptation of Mellor-Crummey and Scott’s (MCS) venerated queue lock [38], which represents attempts to enter the CS using a singly linked list of QNode structures. In this section we consider specifically the context-free version of MCS, in which nodes are allocated at line 58 of the entry section. line 61–71 follow the original MCS algorithm faithfully with the exception of the read-modify-write operations at line 62 and line 68, where we introduce detectability. The tail pointer variable $T$ implements a subset⁴⁴4The full UDSS would also preserve non-detectable FAS and CAS operations, which we do not need. of Moridi et al.’s UDSS [39] applied to the combination of FAS and CAS operations: it supports detectable FAS and CAS operations that accept an auxiliary argument called a tag [39], in our case a QNode reference, and the resolution operation described earlier in Section 2. The latter is invoked at line 45 of the recovery section only if a process crashed between line 59 and line 72, where a reference to the current node is saved for recovery, and returns a triple as explained in Section 2. This triple encodes the name of the last operation as $op$, the value of the auxiliary argument as $tag$, and the response of the operation as $res$. The recovery section performs a case analysis on the values of these components, as we explain shortly, to decide the correct way to clean up the last passage.

A crash failure of process $p_i$ occurring with $MyNode[i]=\perp$ (i.e., before line 59 or after line 72) is benign, and in this case the body of Recover is bypassed at line 44. More difficult cases occur if $p_i$ crashes after threading its node behind the tail at line 62, and before it has passed control of the RME lock to the successor (i.e., completed line 71) or unthreaded its node from the queue (i.e., completed a successful swap at line 68). If $p_i$’s most recent operation on the tail pointer $T$ with respect to the current node (read at line 43) was detectable-FAS then $p_i$ must complete its interrupted execution of the entry section. If $p_i$ already linked with the predecessor, then it repeats the busy-wait loop in Enter and then completes Exit via line 50 and line 53. On the other hand, if there was a predecessor but the link was not established then $p_i$ repeats Enter from line 64 and then completes Exit via line 52 and line 53. Finally, if there was no predecessor then $p_i$ simply completes Exit via line 53. Next, there are two cases pertaining to a crash in Exit. If $p_i$ successfully unthreaded its node from the queue then it proceeds to line 72 via line 55 and releases its node. Otherwise $p_i$ has a predecessor $p_j$ and repeats lines 70–72 of Exit via line 57 to link with $p_j$ and pass control of the RME lock. Note that, in all of the above cases, $p_i$ continues to execute the entry, critical and exit sections of the current passage, and no attempt is made to re-execute the CS from the recovery section. To guarantee critical section re-entry (CSR), the algorithm can be modified easily by having $p_i$ bypass Exit at line 53 and then also bypass the body of Enter using an additional private variable to direct the flow of control.

The space complexity of the algorithm can be bounded by recycling the queue nodes allocated at line 58. We defer the details to Appendix C due to lack of space. Our technique reduces space to $O(N)$ while preserving the dynamic joining property: the algorithm allows processes to join an execution “on the fly” and does not assume prior knowledge of $N$.

The correctness properties of the algorithm are stated below in Theorem 3 under the implicit assumption that detectable operations on the tail pointer $T$ are atomic. The doorway of the algorithm, for FCFS, is a bounded prefix of the entry section and comprises lines 58–62. If $T$ is simulated using a software implementation then the detectable-FAS operation must be wait-free, at least until its linearization point, and we address this technicality more formally in Appendix B.

The upper bound on RMR complexity stated in Theorem 3 can be used to deduce a lower bound on the RMR complexity of implementing detectable base objects in the independent crash failure model, as stated in Theorem 4.

The prospect of recovering in-memory data structures directly from persistent main memory after a crash failure opened the door to rethinking some of the fundamental assumptions ingrained in decades of literature on shared memory algorithms. We focus in this section on theoretical aspects of persistent memory, acknowledging that the subject caught the attention of practitioners (e.g., in [46, 11, 41, 30, 42, 12]) before it captivated the theory community.

One of the earliest theoretical issues addressed was the formulation of a suitable correctness condition for concurrent objects in a crash-prone environment. Herlihy and Wing’s celebrated linearizability property [29] has a fundamental drawback in that regard: it assumes that a process finishes one operation before it invokes another. This implies that a crashed process cannot in general restart execution using its old identifier; a new identifier must sometimes be chosen, which goes against the nearly universal modeling assumption that a system comprises a bounded set of $N$ processes with fixed identifiers. Several alternatives have been proposed, the most widely-cited of which is the durable linearizability (DL) property of Izraelevitz, Mendes, and Scott [31]. DL simply disallows immediate reuse of process IDs, which has the side-effect of allowing an operation that is interrupted by a crash to take effect after the crash. Aguilera and Frølund’s strict linearizability (SL) property [1] instead requires interrupted operations to take effect either before the crash or not at all. It allows for, but does not require, the reuse of process IDs across failures. Thus, SL is the strongest and most portable of the relevant correctness properties, though not always attainable, as shown in [1] for certain register constructions. Weaker conditions proposed in [26, 7] are susceptible to undesirable anomalies (non-local behavior, program order inversion). Attiya, Ben-Baruch, and Hendler defined nesting-safe recoverable linearizability (NRL) [3] for recovery of nested compositions of objects. Their framework assumes that the system restarts a crashed process from the most deeply nested interrupted operation to complete it, which circumvents the anomalies present in [26, 7].

Traditional linearizability-like notions of correctness were challenged by Friedman, Herlihy, Marathe and Petrank [18, 19], who introduced the notion of detectability – the ability to resolve the outcome of an interrupted operation during recovery from a failure. NRL satisfies this goal indirectly by ensuring that every interrupted operation eventually takes effect, and variations on this theme have been adopted in several works [5, 2, 45, 36, 40]. Alternatively, detectability can be embedded into an object’s sequential specification by introducing a special resolution operation, and then combined with an existing correctness condition. This approach was first realized by Ben-David, Blelloch, Friedman, and Wei [6], and later generalized by Li and Golab [37] as the detectable sequential specification (DSS), without relying on the strong system assumptions of NRL. Moridi, Wang, Cui, and Golab [39] examined producer-consumer synchronization as a concrete use case for detectable objects, and also proposed to merge the distinct prepare and execute phases of a detectable operation in the DSS by introducing the conceptually simpler unified DSS (UDSS). Jayanti, Jayanti, and Jayanti’s [32] method-based approach to detectability is a blend of [3] and [7].

Recoverable (i.e., crash-tolerant) objects can be constructed by augmenting conventional techniques through the addition of specialized recovery procedures and, in some models, explicit persistence instructions that flush updates from the volatile cache to the persistent memory [7, 6, 17, 2, 32, 3, 45, 36, 40, 37, 24, 19, 8]. Of these, only purely lock-based or wait-free techniques [7, 24, 3, 6, 45, 34] ensure bounded RMR complexity, and only a handful yield RMR-efficient (particularly sub-linear RMR complexity in the number of processes) implementations. The latter generally fall into three categories: solutions based on Golab and Ramaraju’s recoverable mutual exclusion (RME) [24, 25], for which RMR-optimal solutions were later presented in [33, 13, 22, 34], wait-free implementations of comparison primitives such as Compare-And-Swap (CAS) and Load-Linked/Store-Conditional (LL/SC) [3, 6, 32], and universal wait-free constructions [7]. RME does not prescribe a concrete technique for recovering actions performed in the critical section, and hence only partially addresses the implementation problem solved in this paper. On the other hand, detectable wait-free implementations of comparison primitives compete directly with our RME-based generic construction, but they have limited applicability in the context of proving RMR complexity bounds due to their weak symmetry breaking power. For example, the RMR-optimal algorithms in [33, 13, 22, 34] rely on unconditional synchronization primitives, such as Fetch-And-Store (FAS), to maintain queue structures. The wait-free CAS in [6] is strictly linearizable [1], but the constructions in [7, 3, 32] are not.

Tables 1 and 2 summarize the performance guarantees of the existing implementations of detectable object operations for system-wide failures (Table 1) and independent failures (Table 2). For strict linearizability, as mentioned earlier, the implementation provides a resolve procedure to detect if the operation interrupted by a failure has taken effect and perform any needed recovery. For recoverable linearizability, the implementation provides a recover procedure to enable an operation interrupted by a failure to be completed.

Tight bounds on worst-case RMR complexity in the context of persistent shared memory are known for the RME problem in both the CC and DSM models. For independent failures, Golab and Ramaraju’s algorithm [24, 25] solves RME in $O(\log N)$ RMRs per passage using read/write registers only, and this matches Attiya, Hendler, and Woelfel’s lower bound [4], which applies also to comparison primitives [21]. Using unconditional primitives such as FAS, in combination with CAS and read/write registers, the RME problem is solvable in $O(\log N/\log N\log N)$ RMRs per passage using Jayanti, Jayanti, and Joshi’s algorithm [34], which uses the tree structure introduced by Golab and Hendler [22]. This matches the lower bound of Chan and Woelfel [10] for algorithms that use base objects of size $O(\log N)$ bits. Katzan and Morrison [35] showed that more efficient solutions are possible using wider base objects, and the trade-off achieved was proved to be tight by Chan, Giakkoupis, and Woelfel [9]. In the system-wide failure model, RMR bounds for algorithms that use reads, writes, and comparison primitives are the same as in the independent failure model. On the other hand, FAS in combination with CAS and read/write registers can be used to construct efficient queue locks with $O(1)$ RMRs complexity using Jayanti, Jayanti, and Joshi’s algorithm [33] or Dhoked, Golab, and Mittal’s [14]. Our transformation of ME algorithms to RME using detectable base objects proves for the first time that an RMR-optimal generic construction of detectable RMW objects has the same worst-case RMR complexity per operation as the RME problem per passage in the system-wide and independent failure models.

Our detectable object construction is an important step towards a general technique to transform a non-recoverable concurrent program into one that leverages persistent memory for recoverability. Several such transformation already exist. Ben-David, Blelloch, Friedman, and Wei’s technique is based on segmenting the program into capsules that can be recovered using detectable operations [6]. Their technique is presented in the context of lock-free synchronization using Compare-And-Swap, but can be extended to support other detectable RMW operations.⁶⁶6Note that, since our implementation of the detectable-FA$\varphi$ operation is blocking, the concurrent program generated by Ben-David, Blelloch, Friedman, and Wei’s transformation when extended to use our generic detectable-FA$\varphi$ operation will be safe but no longer lock-free. Its main limitation is the assumption of a persistent call stack and page table, which requires a non-standard programming environment and operating system. Attiya, Ben-Baruch, Fatourou, Hendler, and Kosmas describe a general construction of recoverable data structures using persistent memory [2]. Their approach is specific to lock-free algorithms that use only read, write and CAS instructions.

Our work draws the first comprehensive connection between detectability and recoverable mutual exclusion. We showed how to use RME to construct detectable read-modify-write objects, and then used such objects to solve the RME problem using an algorithm that provides a common execution path for both system-wide and independent process failure models. Our constructions establish the first RMR lower bound on detectable object implementations, and pave the way toward future RMR-efficient solutions for complex synchronization problems such as recoverable versions of reader-writer exclusion and group mutual exclusion.