DULL: A Fast Scalable Detectable Unrolled Lock-Based Linked List

A persistent pointer, PMptr, handles two problems: address space layout randomization (ASLR) [32] and efficiently persisting pointers. As a result of ASLR, dereferencing a pointer on PM that stores the address of a persistent object after recovering from a system failure might result in accessing an invalid memory location. The PMptr compensates for ASLR by storing each pointer as an offset from the base address of the persistent memory-mapped file and calculating the pointer value on every access. Persisting the offset upon every read and write is a conservative approach to ensure correctness. However, this might be inefficient since each update needs to be flushed only once to the PM for a subsequent recovery. PMptr persists the offset more efficiently. The idea is borrowed from the work of Wang et al. in [53]. The offset variable is a tuple comprising the offset value intended to be persisted and a “dirty bit” that indicates whether the current offset value has ever been persisted (0) or not (1). A PMptr object can be accessed through two operations: Set and Persist (SaP) and Get and Persist (GaP). See Appendix B for PMptr implementation details.

A persistent key-value pair, PMpair, comprises a single variable and three associated functions. The variable pair is a tuple , where key and value are variables that store a key and its corresponding data, respectively, and flag is a dirty bit set to 1 if key and value are not persisted and 0 otherwise. Accessing pair is governed by three functions: Set, Get and Persist. The function Set stores a key-value pair, given as an argument, into pair and marks the tuple as not persisted. The key and value stored in pair are retrieved by the procedure Get, ignoring the dirty bit state. Neither function flushes the key-value pair object. Persisting pair is delegated to a separate procedure, Persist, for performance purposes. See Appendix C for more implementation details of the PMpair object.

A descriptor object is defined in Algorithm 1. To achieve detectability, each process accessing an instance of DULL has an auxiliary descriptor object. At the beginning of a detectable operation, a process shall store some operation-related information in its descriptor, i.e. prepare the operation, through the function Prep-op. Preparing an operation is designed such that all changes to the descriptor variables appear to be atomic. That is, either all changes take effect or none at all. To achieve atomicity, each descriptor object consists of two instances of its variables, called units, and a Boolean variable, curr, that points to the current unit, where the other instance is called the next unit.

In Prep-op, the next unit variables are initialized with the appropriate parameters (Lines 6-9), then curr is flipped to switch the next and current units (Line 11). Note that, all the descriptor variables in the next unit are persisted to PM at Lines 10 and 12 before the next unit becomes the current one. The preparation process is marked as completed only if curr is updated. If a crash occurs before persisting curr, then re-invoking the function Prep-op upon recovery repeats the whole procedure, making it failure-atomic. The function SetNode is used for check-pointing (more in Section 4.6), and SetResult marks the end of the prepared operation (op) by storing the result in the descriptor. Furthermore, a process can resolve its last operation at any point in time by invoking the idempotent Resolve procedure of its descriptor object.

This section presents the implementation details of DULL. Our detectable implementation is based on the unrolled linked list by Platz et al. [46]. Although our focus is on persistence and detectability, a full description of the proposed DULL algorithm, including overlaps with the algorithm in [46], is provided in this section for completeness. In the search, insertion, and removal operations, the lines of added or modified steps are highlighted in red, and corresponding line numbers are underlined to clearly distinguish our contributions from the original work. The remaining operations are key components of our contribution.

In designing DULL, persistent unrolled nodes are used as building blocks. Node unrolling, initially proposed by Shao et al. [50], involves the storage of multiple elements in an array within each node. Each node comprises the following variables:

• $\mathrm{■}$

  count: the number of key-value pairs stored in the node.

• $\mathrm{■}$

  marked: a Boolean indicating whether the node has been logically removed from the list.

• $\mathrm{■}$

  $m$: a volatile mutex lock used only during insertions and removals in the list.

• $\mathrm{■}$

  anchor: the key that uniquely characterizes a node such that if a key exists in a node, then the key $\ge$ the anchor of that node and the anchor of the successor node. Nodes are thus sorted in ascending order by their anchor keys.

• $\mathrm{■}$

  next: a persistent pointer (PMptr) to the successor node.

• $\mathrm{■}$

  $\text{pairs}[0..K-1]$: an array of up to $K$ unordered variables of type PMpair, where $K$ is the maximum number of pairs in a node.

In addition to persistent nodes, a DULL instance has an array $D[1..N]$ of $N$ descriptor objects, where $N$ is the number of processes. Moreover, a DULL object has at least three persistent nodes at all times: the head and tail sentinel nodes and one non-sentinel node. Sentinel nodes do not store key-value pairs. The head and the non-sentinel node anchor keys are $-\mathrm{\infty }$, and the tail anchor key is $\mathrm{\infty }$, where $-\mathrm{\infty }$ is some key the minimum key in the key space, and $\mathrm{\infty }$ is some key $>$ the maximum key in the key space.

Traversing a DULL is separated into two functions: Scan and Seek. Both procedures are presented in Algorithm 2. The function Scan searches the list for a target key starting from the first non-sentinel node in line 18, while tracking the predecessor (pred) and successor (succ) of each (curr) node. The search ends by reaching a node, curr, where the target key might exist, i.e., the successor’s anchor key is greater than the target key (Line 20). Finally, the function Scan returns the three tracked pointers at Line 24. The while-loop at Line 20 is guaranteed to terminate since the tail’s anchor key is greater than all keys in the key space. The procedure Seek takes a pointer to some node curr and a target key, and it linearly searches for the key in the array pairs of curr (Line 25). If the target key is found, the function returns the index of its key-value pair at Line 29, otherwise, the procedure returns $\perp$ at Line 30, indicating that the key is absent in curr.

A Contains operation, presented in Algorithm 2, searches for the node, curr, that potentially contains the argument target key by invoking the procedure Scan at Line 31. The array pairs of the node curr is searched for the target key by calling the function Seek at Line 32. If the key is found, Seek returns a valid index (Line 33) of the corresponding pair, which is atomically read and then persisted at Lines 34 and 35, respectively. The key of the read pair is checked at Line 36 before returning its value at Line 37. If Seek does not find key and returns $\perp$, or the check at Line 36 fails, the operation returns $\perp$ at Line 38, indicating that the list does not contain the target key. Note that all traversed pointers are flushed at least once through the function GaP at Line 23, and each pair read is persisted through the Persist function at Line 27. Additionally, the function Contains persists the found pair (Line 35) after the atomic read at Line 34. All persistence operations occur before returning from the corresponding procedures to preserve strict linearizability.

Given a pair, key and value, an Insert operation, shown in Algorithm 3, calls Prep-Insert of the executing process’ descriptor to initialize it at Line 39. Subsequently, the operation finds the appropriate node (curr) to store the pair, and its predecessor (pred), by calling the function Scan at Line 40. The predecessor lock is acquired at Line 41 to prevent any simultaneous update to curr, pred and the linking pointer, $\text{pred}.\text{next}$. The validation in [29] is then applied to check that $\text{pred}.\text{next}$ still points to curr and that neither node is marked as removed (Line 42). If the validation fails, then the predecessor’s mutex is released and the insertion operation is restarted. Otherwise, Line 45 calls the function Seek, searching for key in curr’s array. If the returned index ($j$) from Seek is valid, then the function marks the insert operation as completed, unlocks the predecessor’s lock and returns false (Lines 47-49), indicating that the key already exists.¹¹1 Instead, the value in a found pair can be updated and the algorithm remains correct. Otherwise, an empty slot in the array pairs is searched for by the function Seek at Line 51. Consequently, there are two possible scenarios: (1) There is an empty slot in pairs and Seek returns its index, or (2) the array is full and Seek returns $\perp$. If (1), then the empty slot in pairs is set to key and value and is persisted at Lines 53 and 54, respectively, and the counter of curr is incremented at Line 55. If (2), then curr is split into two nodes, ${\text{new}}_1$ and ${\text{new}}_2$, using the helper procedure Split, called at Line 57. The Split function creates two new nodes (${\text{new}}_1$ and ${\text{new}}_2$) to replace curr, where each stores roughly half of the pairs in curr. The implementation details of the Split function are presented in Appendix E.

Subsequently, the given pair is inserted into ${\text{new}}_1$ if the pair’s key is strictly less than the anchor key of ${\text{new}}_2$. Otherwise, the pair is inserted into ${\text{new}}_2$. In both cases, the counter of the node where the pair is inserted is incremented. Note that if the target key is not found at Line 45, it will eventually be inserted regardless of whether case 1 or 2 occurs. To maintain such an effect in the presence of a crash failure, the pointer pred is stored in the descriptor $D[i]$ as a checkpoint marker at Line 50. That is, if a process $p_i$ crashes after persisting $D[i].\text{offset}$ (Line 4), the operation can be resumed during recovery (Section 4.8).

Finally, curr is marked to prevent erroneous subsequent updates to the removed node (Line 66), the locks in curr and pred are released (Lines 67 and 69), and the value true is returned (Line 70) to indicate that the pair is successfully inserted into the list. Before the procedure Insert returns, $p_i$ marks its operation as completed by setting the result field of its descriptor object through calling SetResult at Line 68.

To ensure recoverability, the next pointers of the new replacement nodes are persisted in the Split function. The other variables are persisted using PersistNode (Lines 63 and 64) before the nodes are inserted and accessible by other threads (Line 65), maintaining atomicity in the split process. PersistNode sequentially issues a cache-line write-back for each node variable, followed by a store fence. If the system fails before replacing curr with the new nodes (Line 65), then the incomplete split can be, optionally, re-invoked upon recovery since it has not taken effect. If a failure occurs after Line 65 takes effect, then the recovery protocol (Section 4.8) recovers the new nodes.

Algorithm 4 shows the procedure of removing a key-value pair from a DULL instance.

First, the descriptor of the executing process is initialized at Line 71. Given a target key, invoking Remove finds the node (curr), and its predecessor (pred), that potentially stores the key via the function Scan at Line 72. The lock in pred is acquired at Line 73 to prevent any simultaneous update to the curr and pred nodes. The algorithm validates that the next pointer or pred still points to curr and that both nodes are not marked as removed (Line 74). If the validation fails, then the mutex of pred is unlocked and the removal operation is restarted. If the validation succeeds, the function Seek searches for the target key at Line 77. If the key is not found, then the function marks the operation as completed, unlocks the lock of pred and returns false (Lines 79-80). Otherwise, $p_i$ stores the offset of pred in its descriptor object at Line 81 to detect and optionally resume the operation upon recovery (Section 4.8). Then, the pair containing the target key is removed and persisted at Lines 81 and 82, respectively, and the node’s counter is decremented at Line 82.

Consequently, if the counter is less than a predefined constant ($\text{MinFull}\le K/2$), some actions are taken to reduce the variation in the number of pairs across all nodes. In the general case where curr is not the only non-sentinel node and its successor (succ) is not the tail, there are three possible scenarios: (1) curr is empty, (2) curr is not empty, and the sum of the counters of curr and succ is less than some predefined constant (MaxMerge), or (3) curr is not empty, and the sum of the counters of curr and succ is greater than or equal to MaxMerge. If (1), then curr is logically removed (Line 87) from the list and marked to prevent invalid subsequent changes to the node. If (2), then curr and succ are merged into a new node by invoking the helper function Merge at Line 92. If (3), then the pairs stored in curr and succ are redistributed into two new replacement nodes, by calling the helper procedure Redist at Line 93, such that both nodes contain roughly the same number of pairs. Due to space constraints, the steps for the helper subroutines Merge and Redist are moved to Appendix F. In cases (2) and (3), the new nodes are persisted and logically inserted into the list (Lines 94-96), and curr and succ are marked at Lines 97 and 98, respectively. Finally, at Lines 99-103, all acquired locks are released, the operation is marked as completed, and the Remove procedure returns true, indicating that the pair was successfully deleted.

The recovery protocol, defined in Algorithm 5, is a procedure that is invoked, by a single thread, after a crash failure. First, $D$, head and tail are initialized to the addresses of the descriptors array, head node and tail node (Lines 104-106), respectively (refer to Appendix D for details about the memory mapped file layout). Then, the recovered head and tail are used to traverse the list (Line 108) and recover the variables of each node.

Adding persistent nodes to the list – which may occur when inserting or removing a key – comprises creating new nodes and persisting their anchor, pairs and next variables before the new nodes are logically inserted into the list. Throughout a node life-cycle, anchor does not change after it is first initialized. As for the next pointers, traversing the list (Section 4.5) is designed such that the value of a next pointer is persisted by the GaP function upon reading. In addition, each element in the array pairs is persisted on update. As a result, a node is simply recovered by resetting its mutex (Line 114) and deriving the value of the variable count. A node’s count is inferred by traversing the array pairs and counting all valid key-value pairs (Lines 109-113).

After initializing the list variables from PM, the recovery protocol uses the recovered descriptors to resolve and resume interrupted operations. Locks properties should not be violated during recovery. That is, resuming incomplete operations in arbitrary order violates strict linearizability. For example, consider the following problematic scenario: Suppose there exist two processes, $p_i$ and $p_j$, that are performing an insertion on two consecutive fully-filled nodes such that the curr node of $p_i$ is the pred of $p_j$. Since the curr nodes of $p_i$ and $p_j$ are full of key-value pairs, both processes split their curr nodes (Line 52), or crash. During a failure-free execution, $p_i$ would split its curr node only after $p_j$ finishes splitting its curr node and releases its pred’s lock (Line 69), which is $curr.m$ of $p_i$. Such a sequential order of execution, imposed by the mutex locks, prevents invalid states from occurring. Now, suppose a crash failure occurs after both processes store and persist their pred pointer values into their descriptors (Line 50) but before linking their split nodes at Line 65. Upon recovery, if $p_i$ splits its node first, deleting its curr node (i.e. $p_j$’s pred node), then $p_j$ would create two nodes, ${\text{new}}_1$ and ${\text{new}}_2$, while splitting its curr and erroneously set the next pointer of the removed pred node to ${\text{new}}_1$ (Line 65). Therefore, the sequential execution imposed by the locks must be preserved to avoid inconsistencies. To solve this problem, we observe that locks of consecutive nodes are always acquired in one direction, from head to tail, and always released in the opposite direction. Hence, resuming incomplete operations in the reverse order of the corresponding pred nodes position in the linked list (Lines 117-137), from tail to head, guarantees that all locks are released before being acquired by other processes.

The for-loop at Line 117 iterates through each descriptor object and reads its current unit (Line 118). From each descriptor unit, the last operation of each process is resolved (Line 120) and then checked if it needs to be resumed (Line 121). Incomplete operations (i.e. its $\text{result}=\perp$) of which the corresponding variable offset is initialized with a valid node address shall be resumed. Such operations are logged in an associative array such that each predecessor node address is mapped to the ID of the process by which the operation was being executed when the crash failure occurred. Subsequently, the for-each-loop at Line 125 resolves (Line 130) and resumes the interrupted operations (Lines 132-137) in the reverse order of the associated predecessor nodes in the linked list. For each insertion operation, if the successor’s anchor key is less than the key to be inserted, then the node split, and the key insertion, must have been done before the crash. If the key has been found in curr, then the key has been inserted without splitting the node. In both cases, the recovery protocol just marks the operation as completed (Line 134). Otherwise, the Insert procedure is resumed starting from Line 51 without accessing the locks. As for interrupted key removals, the key is removed at Line 135 if it is found upon recovery (Line 136). Then, Lines 83-103 of the function Remove is executed to merge or redistribute if necessary. Similarly to insertion operations, steps for acquiring and releasing locks are skipped when resuming key removals. Note that executing Lines 83-103 is idempotent. That is, the checks at Lines 83 and 91 ensure that the nodes are redistributed or merged at most once.

The proof is omitted due to space consideration.

When evaluating performance we focus on crash-free executions²²2We also experimentally tested the recoverability of DULL. See Appendix G for more details. as applications are expected to run free of failures most of the time. Flush instructions are used in our failure-free experiments to reflect the lists’ practical performance. Each run involves multiple threads that continuously insert, remove and lookup key-value pairs for a specific period of time. The metric used for evaluating throughput is the total number of operations per second over a varying number of threads. Experiments engage up to 250 threads in three different modes: The first mode uses only physical cores where up to 20 threads are one-to-one mapped to processor cores. The second mode utilizes hyper-threading in addition to physical cores and goes up to 40 threads. The third mode over-subscribes the 40 logical cores with up to 250 threads. The first two modes evaluate the scalability and performance of each list under consideration. The goal of the third mode is to assess system behaviour under high thread preemption. Empirical results are presented, in Figure 1, as graphs in which each point denotes the median of three consecutive runs of five seconds. For each point, there is an error bar that represents ± one standard deviation.

In all-write and balanced workloads, Figures 1(a)-1(c), DULL outperforms all the other lists by several-fold in all of the three modes when considering a key-space of 1000 and 5000. The FliT-based DULL algorithm performed second best in terms of overall performance. FliT, designed as a general-purpose transformation tool, provides persistence by utilizing a custom persistent atomic type in place of the standard atomic library, making it particularly effective for persisting word-sized variables like pointers [55]. However, we found that FliT’s generalized approach is not as efficient when persisting complex objects containing multiple variables, such as our descriptors. Specifically, our custom method, which issues a cache-line write-back instruction for all descriptor variables followed by a single store fence, achieves faster performance. This optimization is valid when the object variables are exclusively read and written by a single thread in the absence of failures, with other processes accessing them only during recovery after a crash. While FliT’s generalization does not take advantage of such specific optimizations, it offers broader applicability, which limits its ability to maximize performance in our case. The two non-recoverable Harris lists are faster than the other algorithms at high concurrency levels. Note that Harris lists are faster than other lists because, unlike other algorithms, they run on DRAM and are not recoverable. Nevertheless, Harris lists are surpassed by our proposed algorithm.

In the first mode, where threads are one-to-one mapped to physical cores, the DFC-ULL algorithm comes in second place when comparing recoverable solutions in most of the workloads, except for the all-write workload when the key space is 1000 as Romulus-LL has higher throughput. In addition, Romulus-LL surpasses OneFile-LL and PMDK-LL in all scenarios. PMDK-LL is dominated by all algorithms except in all-read workloads, Figure 1(d), where it yields higher throughput than OneFile-LL. The reason is, for every node while traversing the list, OneFile-LL performs a more complex load interposition that involves two acquire-locks and may search the write-set [48]. On the other hand, DULL, DFC-ULL, Romulus-LL and PMDK-LL employ simpler loads.

In hyper-threading mode, the throughput of DULL increases in high concurrency levels, unlike the other recoverable algorithms in all-write and balanced workloads. This shows the scalability of our proposed algorithm. The performance of DFC-ULL, Romulus-LL and OneFile-LL degrades when more hyper-threaded cores are used in update workloads. The DFC-ULL and Romulus-LL are flat-combining techniques. Therefore, more concurrent updates raise the global combining overhead, which prolongs blocking other threads. The OneFile-LL behaviour is expected as PTMs tend not to scale in scenarios of high degree of simultaneous updates. On the other hand, our proposed algorithm does not require adding locks, or transactions, beyond the ones required for the correctness of the non-recoverable variant. In DULL, we utilize the fact that the unrolled linked list is already lock-based to achieve detectability. Therefore, in high levels of concurrency (>20 threads), DULL is significantly more scalable than the competition.

In over-subscription mode, the performance of DULL, Romulus-LL and OneFile-LL is shown to be stable and saturated as the number of threads increases in all-write and balanced workloads. The DFC-ULL performance, in contrast, drops significantly when the concurrency level rises. It was interesting at first to see the DFC-ULL algorithm collapses in scalability compared to the Romulus-LL, although both algorithms are based on flat-combining. This observation can be explained as a result of the reduction step in DFC-ULL. In DFC, the combiner first examines the submitted requests by other threads and attempts to reduce the number of operations by elimination. For example, the combiner may resolve the result of each simultaneous pair of opposite operations (an insertion and a removal of the same key) without modifying the data structure. Such a technique is mostly advantageous when used in implementing abstract data types (ADTs) that have a parameterless remove procedure, like stacks, queues and deques, where a removal can be matched and eliminated with any concurrent insertion. In contrast, for a correct set ADT implementation, like a linked list, a key removal can only be eliminated by a simultaneous insertion of the same key.

The results considering all-read workloads are demonstrated in Figure 1(d). The overhead of adding recoverability while traversing DULL is found to be small when compared to the Vanilla-ULL, thanks to the efficient flush-on-read implemented as part of the $PMptr$ and $PMpair$ persistent objects. The same is noticeable for the DFC-ULL as well. In fact, DFC-ULL is slightly faster than DULL since it does not add flush steps to the original traversing algorithm. The Romulus-LL, OneFile-LL and PMDK-LL are slower compared to the DULL and DFC-ULL in all-read workloads as a consequence of using the unrolled list as the underlying list algorithm.

Figure 1(b) illustrates the throughput considering a balanced workload and a key space of 5000 to assess and compare the list algorithms for a larger list size, roughly 2500 key-value pairs. When compared to balanced workloads with key space of 1000, Figure 1(a), a similar pattern with a consistent lower performance is observable in all algorithms, except for DFC-ULL. That is, the DFC-ULL is impacted the least when increasing the key space and list size. The fact that the degradation in performance of the DFC-ULL algorithm is barely noticeable shows that the DFC component is the limiting factor of the list scalability. Specifically, although a larger list slows down traversal, the flat-combining on updates is relatively more complex and, hence, is the performance bottleneck in the DFC-ULL algorithm. The results for all-write and all-read workloads for key space of 5000 are very similar to the results for key space of 1000. Therefore, such outcomes are omitted due to lack of space.

As Vanilla-ULL demonstrates the fastest performance among all the algorithms due to its unrolled nodes and lack of recoverability mechanisms, we used it as a baseline to evaluate the performance of each algorithm over different list sizes. Figure 2 illustrates the relative throughput of each list compared to Vanilla-ULL using 20 threads, a balanced workload consisting of 50% reads and 50% updates, and varying key spaces.

Since key insertions and removals are uniformly distributed across the key space, the list sizes are approximately half the key space. Based on the experimental results presented in Figure 2, we observe that Harris-LL achieves throughput nearly identical to Vanilla-ULL for smaller list sizes, specifically when the key space is 128, corresponding to approximately 64 list elements. DULL follows, achieving about one-third of the throughput of Vanilla-ULL and Harris-LL, primarily due to the additional overhead introduced by the recoverability and detectability mechanisms in DULL.

As the key space – and consequently, the list size – increases, the relative performance of Harris-LL compared to Vanilla-ULL declines sharply, as does DULL’s. This decline is attributable to lock contention: with smaller lists, lock-based algorithms experience higher contention overhead when accessing locks. However, this performance bottleneck diminishes as list sizes grow. Therefore, when the key space exceeds 512, DULL outperforms all other algorithms, demonstrating at least a 2x improvement in throughput compared to Harris-LL and several-fold improvements over the remaining recoverable competitors.