EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation

Our linked-list implementation, together with the list node class, is presented in Algorithm 1. The simple pointer access methods implementation (e.g., mark() in line 21 and getRef() in line 36) appear in Appendix A. In a similar way to Harris’s list, the API includes the insert(), remove() and contains() operations ³³3The rangeQuery() operation is added in Section 3.2. In addition, lines marked in blue in Algorithm 1 can be ignored at this point. They will also be discussed in Section 3.2. The insert() operation (lines 7-16) receives a key and a value. If there already exists a node with the given key in the list, it returns its value (line 10). Otherwise, is adds a new node with the given key and value to the list, and returns a designated NO_VAL answer (line 16). The remove() operation (lines 17-23) receives a key. If there exists a node with the given key in the list, it removes it and returns its value (line 23). Otherwise, it returns NO_VAL (line 20). The contains() operation (lines 24-27) receives a key. If there exists a node with the given key in the list, it returns its value (line 27). Otherwise, it returns NO_VAL (line 26).

All three API operations use the find() auxiliary method (lines 28-55), which receives a key and returns pointers to two nodes, pred and curr (line 55). As in Harris’s implementation, it is guaranteed that at some point during the method execution, both nodes are consecutive reachable nodes in the list, pred’s key is strictly smaller than the input key, and curr’s key is equal or bigger than the given key. I.e., if curr’s key is strictly bigger than the input key, it is guaranteed that there is no node with the given input key in the list at this point. The method traverses the list, starting from the head sentinel node (line 30), and until it gets to an unmarked and unflagged node with a key which is at least the input key (line 37). Recall that the two output variables are guaranteed to have been reachable, adjacent, unmarked and not flagged at some point during the method execution. Therefore, as long as the current traversed node is either marked or flagged (checked in line 34), the traversal continues, regardless of the current key (lines 34-36). Once the traversal terminates (either in line 35 or 37), if the current two nodes, saved in the pred and curr variables, are adjacent (the condition checked in line 44 does not hold), then the method returns them in line 55. Otherwise, similarly to the original implementation, the method is also in charge of physically removing marked nodes from the list.

As we are going to discuss next, our physical removal procedure, as depicted in Figure 1, is slightly different from the original one [26]. Physical deletions are executed via the trim() auxiliary method (lines 56-71). Although nodes are still marked for deletion in our implementation (line 21), their successful marking does not serve as the removal linearization point. I.e., reachable marked nodes are still considered as list members. The trim() method receives two nodes as its input parameters, pred and victim. victim is the physical removal candidate, and is assumed to already be marked. pred is assumed to be victim’s predecessor in the list, and to be neither marked nor flagged. As depicted in Figure 1, consecutive marked nodes are removed together. Therefore, the method traverses the list, starting from victim, for locating the first node which is not marked (lines 58-59). When such a node is found, the method tries to flag its next pointer, for freezing it until the removal procedure is done. In general, pointers are marked and flagged using their two least significant bits (which are practically redundant when reading node address aligned to a word). Both marked and flagged pointers are immutable, and a pointer cannot be both marked and flagged. Therefore, the flagging trial in line 61 fails if curr’s next pointer is either marked or flagged. If the flagging trial is unsuccessful, and not because some other thread has already flagged curr’s next pointer, the method returns in line 62. Otherwise, a new node is created in order to replace the flagged one (lines 65-67). Note that since this node’s next pointer is flagged (i.e., immutable), it is guaranteed that the new node points to the original one’s current successor. The actual trimming is executed in line 68. If the compare-and-swap (CAS) is successful, then the sequence of marked nodes, together with the single flagged one (at the end of the sequence), are atomically removed from the list, together with the insertion of the new copy of the flagged node (the new copy is neither flagged nor marked).

As the physical removal is necessary for linearizing the removal (as will be further discussed in Section 3.2), a remover must physically remove the deleted node before it returns from a remove() call. The marking of a node in line 21 only determines the remover’s identity and announces its intention to delete the marked node. Therefore, the remover must additionally ensure that the node is indeed unlinked, by calling the find() method in line 22. In Appendix C we formally prove that the list implementation, presented in Algorithm 1, is linearizable and lock-free.

Given Algorithm 1, adding a linearizable range queries mechanism is relatively straight forward. We use a method which is similar to the vCAS technique [65]. As discussed in Section 1, the vCAS scheme introduces an extra level of indirection for the linked-list per node access. Indeed, we show in Section 4 that the vCAS implementation suffers from high overheads. The original vCAS paper provides a technique for avoiding this level of indirection. The suggested optimization relies on the following (very specific) assumption: a certain node can be the third input parameter to a successful CAS operation only once throughout the entire execution. That successful CAS is considered as the recording of this node, and the property is referred to as recorded-once in [65].

Although the recorded-once property yields a linearizable solution, which reduces memory and time overheads, this assumption does not hold in the presence of physical deletions, as they usually set the deleted node’s predecessor to point to the deleted node’s successor [26], or to another, already reachable node [43, 14], and then, this reachable node is recorded more than once. This makes the suggested technique inapplicable to Harris’s linked-list [26] and most other concurrent data-structures (e.g., [43, 12, 29]). The original vCAS paper implemented a recorded-once binary search tree, based on [20], which we compare against in Section 4. We extend the recorded-once condition and make it fit for the linked-list and other data-structures. We claim that associating each node with the data of a single data-structure update (as provided by our list) is enough for avoiding indirection in this setting. Given such an association, there is no need to store update-related data in designated version records, since it can be stored directly inside nodes, in a well-defined manner.

First, in a similar way to [65, 3, 44], we add a shared clock, for associating each node with a timestamp. The shared clock is read and updated using the getTS() and fetchAddTS() methods, respectively (see Appendix A). The shared clock is incremented whenever a range query is executed (e.g., see line 2 in Algorithm 2), and is read before setting a new node’s timestamp (e.g, see lines 15, 43, 54, 60, 64 and 69 in Algorithm 1). Next, we change the nodes layout (see our node class description in Algorithm 1). On top of the standard fields (i.e., key, value and next pointer), we add two extra fields to each node. The first field is the node’s timestamp (denoted as ts), representing its insertion into the list. Nodes’ ts fields are always initialized with a special $\bot$ value (see lines 11 and 65 in Algorithm 1), to be given an actual timestamp after being inserted into the list. The second field, prior, points to the previous successor of this node’s first predecessor in the list (its predecessor when being inserted into the list). Both fields are set once and then remain immutable. E.g., consider the new node, inserted into the list at stage 5 in Figure 1. Its prior field points to the node whose key is 23, as this is the former successor of the node whose key is 9, which is the first predecessor of the newly inserted node. By its specification, once the prior field is set (see line 13 and 67 in Algorithm 1), it is immutable. These two new fields are not used during the list operations from Algorithm 1, but we do specify their proper initialization, in order to support linearizable range queries. Moreover (and in a similar way to [65, 3]), list inserts and deletes are linearized during the execution of the getTS() method, as follows. Let newNode be the node inserted into the list in line 14, during a successful insert() operation. newNode’s timestamp is set at some point, not later than the CAS in line 15 (it may be updated earlier, by a different thread). The getTS() invocation that precedes the successful update of newNode’s timestamp is the operation’s linearization point. In a similar way, consider a successful remove() operation. The removed node is unlinked from the list during a successful trim() execution. Let newCurr be the node successfully inserted into the list in line 68, during this successful trim() execution. newCurr’s timestamp is set at some point, not later than the CAS in line 69 (it may be updated earlier, by a different thread). The getTS() invocation that precedes the successful update of newCurr’s timestamp is the operation’s linearization point.

Our range queries mechanism is presented in Algorithm 2. The rangeQuery() operation receives three input parameters (see line 1): the lowest and highest keys in the range, and an output array for returning the actual keys and associated values in the range. In addition to filling this array, it also returns its accumulated size in the count variable. The operation starts by fetching and incrementing the global timestamp counter (line 2), which serves as the range query’s linearization point. I.e., the former timestamp is the one associated with the range query. This way, the range query is indeed linearized between its invocation and response, along with guaranteeing that the respective view is immutable during the operation (as new updates will be associated with the new timestamp).

After incrementing the global timestamp counter, the operation uses the find() auxiliary method in order to locate the first node in range (lines 4-12). As opposed to the vCAS mechanism [65], and in a similar way to the Bundles mechanism [44], we observe that until the traversal reaches the target range, there is no need to take timestamps into consideration. This observation is crucial for performance, as there is no need to traverse nodes via the prior fields (which produce longer traversals in practice). In addition, it enables using the fast index (described in Section 3.4) for enhancing the search. During each loop iteration, we first find a node with a key which is smaller than the lowest key in the range (saved as the pred variable in line 5). Then, we optimistically try to find a relatively close node, following prior pointers, until we get to a small enough timestamp (lines 7-8). Since this search may result in a node with a bigger key (e.g., see line 13 in Algorithm 1), the next iteration sends a smaller key as input to the find() execution in line 5. Note that in the worst case scenario, the loop in lines 4-12 stops after the find() execution in line 5 outputs the head sentinel node (as its timestamp is necessarily smaller than ts). Therefore, it never runs infinitely. The purpose of updating $ts$ in line 12 will be clarified in Section 3.3, as it is related to the VBR mechanism. Note that in any case, this update does not foil correctness, since it is still guaranteed that the range query is linearized between the operation’s invocation and response.

When pred has a key which is smaller than the range lower bound, the operation moves on to the next step (the loop breaks in line 11). At this point, the traversal continues according to the respective timestamp⁴⁴4In Appendix C we prove that a node’s successor at timestamp $T$ can be found by starting from its current successor and then following prior references until reaching a node with a timestamp which is not greater than $T$., until getting to a node with a key which is at least the range lower bound (lines 13-18). Once a node with a big enough key is found, the traversal continues in lines 20-28. At this stage, the count output variable and the output array are updated according to the data accumulated during the range traversal. Finally, the count output variable, indicating the total number of keys in range, is returned in line 29. Note that throughout the traversals in lines 16-17 and lines 26-27, there is no need to update succ’s timestamp (as done in lines 15 and 25), since it serves as a node’s prior and thus, is guaranteed to already have an updated timestamp (see Appendix C).

Before integrating our list with a manual memory reclamation mechanism, we must first install retire() invocations, for announcing that a node’s memory space is available for re-allocation. Naturally, nodes are retired after unsuccessful insertions, or after they are unlinked from the list. I.e., newNode is retired if the CAS in line 14 is unsuccessful, newCurr is retired if the CAS in line 68 is unsuccessful, and upon a successful trimming in line 68, the unlinked nodes are retired, starting from victim. The last retired node is curr, which is replaced by its new representative in the list, newCurr. Note that we do not handle physical removals of prior links. Handling them is unnecessary, and might cause significant overheads, both to the list operations and to the reclamation procedure. Therefore, retired nodes are still reachable from the list head during retirement: newCurr’s prior field points to victim, making all of the unlinked nodes reachable via this pointer (and their next pointers).

To add a safe memory reclamation mechanism to our list, we use an improved variant of Version Based Reclamation (VBR) [59]. VBR cannot be integrated as is. Similarly to most safe memory reclamation techniques, it assumes that retired objects are not reachable via the data-structure links. This assumption is crucial to the correctness of VBR, as retired objects may be immediately reclaimed. In addition, VBR uses a slow ticking epoch clock, and ensures that the clock ticks at least once between the retirement and future re-allocation of the same node. During execution, the operating threads constantly check that the global epoch clock has not changed. Upon a clock tick, they conservatively treat all data read from shared memory as stale, and move control to an adequate previous point in the code in order to read a fresh value. As long as the clock does not tick, threads may continue executing without worrying about use-after-free issues. The intuition is that if a node is accessed during a certain epoch, then it must have been reachable during this epoch. I.e., even if this node has already been retired, its retirement was during the current epoch, which means that it has not been re-allocated yet (as the clock has not ticked yet).

Our list implementation poses a new challenge in this context. Suppose that the current epoch is $E$, and that a certain node, $n$, is currently in the list (i.e., it has not been unlinked using the trim() method yet). In addition, suppose that $n$’s prior field points to another node, $m$, that has been retired during an earlier epoch. Then $m$ may be reclaimed and re-allocated during $E$. A traversing thread may access $n$’s prior field during $E$, without getting any indication to the fact that the referenced node is a stale value. Another problem, which does not affect correctness, but may cause frequent thread starvations, is that the global epoch clock is likely to tick during a long range query. In the original VBR scheme, a clock tick forces the executing thread to start its traversal from scratch, even if it has not encountered any reclaimed node in practice.

In order to overcome the above problems, we made some small adjustments to the original VBR scheme. First, we kept the global epoch clock of VBR and the timestamp clock of the range queries separated. We separated the two, as VBR works best with a (very) slow ticking clock. Read-intensive workloads (in which range queries dominate the execution) incur high overheads when combining the two clocks. The separation of the two independent clocks helps overcome the potential aborts. The second step was to modify the nodes’ layout (The VBR-integrated node layout appears in Appendix D). Recall that the VBR scheme adds a birth epoch to every node, along with a version per mutable field. Non-pointer mutable fields are associated with the node’s birth epoch, and pointers are associated with a version which is the maximum between the birth epoch of the node and the birth epoch of its successor. Our list nodes have two mutable fields, their timestamp $ts$ (changes only once), and their next pointer. The prior pointers are immutable. Accordingly, we associated the node’s timestamp with its VBR-integrated birth epoch, serving as its version (there was no need to add an extra $ts$ version), and added a designated next pointer version. Writes to the mutable fields are handled exactly as in the original VBR scheme. Accordingly, upon allocation, a node’s timestamp is initialized to $\bot$, along with the current VBR epoch as its associated birth epoch. When the timestamp is updated (see line 15, 43, 54, 60, 64 and 69 in Algorithm 1, or lines 15 and 25 in Algorithm 2), the birth epoch (also serving as the timestamp’s version) does not change, as the two fields are accessed together, via a wide-compare-and-swap (WCAS) instruction. Similarly, next pointers are associated with the maximum between the two respective birth epochs, and are also updated using WCAS.

Reads are handled in a different manner from the original VBR, as the problems we mentioned above must be treated with special care. The original VBR repeatedly reads the global epoch in order to make sure that it has not changed. In our extended VBR variant, it is read once. After reading the global epoch, and as long as the executing thread does not encounter a birth epoch or a version which is bigger then this epoch, it may continue executing its code. The motivation behind this behavior is that even if a certain node in the system has meanwhile been reclaimed, this node does not pose a problem as long as the current thread does not encounter it. Therefore, traversing threads follow three guidelines: (1) a node’s birth epoch is read again after each read of another field, (2) after dereferencing a next pointer, the reader additionally makes sure that the successor’s birth epoch is not greater than the pointer’s version, and (3) after dereferencing a prior pointer (which is not associated with a version), the reader additionally makes sure that the successor’s birth epoch is not greater than the predecessor’s birth epoch. If any of these conditions does not hold, then the reader needs to proceed according to the original VBR’s protocol. In Appendix D we prove that these three guidelines are sufficient for maintaining correctness. Upon an epoch change, the original VBR enforces a rollback to a predefined checkpoint in the code. Accordingly, we install code checkpoints. Whenever a check that our guidelines impose fails, the executing thread rolls-back to the respective checkpoint. Checkpoints are installed in the beginning of each API operation (i.e., insert(), remove(), contains() and rangeQuery()). Another checkpoint is installed after a successful marking in line 21 of Algorithm 1, as the identity of the marking thread affects linearizability (and therefore, a rollback to the beginning of the operation would foil linearizability). Note that a successful insertion in line 14 does not force a checkpoint (although it affects linearizability, by setting the inserter identity), as it is not followed by any reads of potentially reclaimed memory.

Another issue that needs to be dealt with is the guarantee that life-cycles of nodes, allocated from the same memory address, do not overlap. The original VBR scheme does so by associating each node with a retire epoch. A node’s retire epoch is set upon retirement. During re-allocation, if the current global epoch is equal to the node’s retire epoch, then the global epoch is incremented before re-allocation. We chose to optimize over the original VBR, discarding the retire epoch field, as it adds an extra field per allocated node. Instead, each retire list is associated with the epoch, recorded once it is full (right before it is returned to the global pool of nodes). Upon pulling such a list from the global pool, if its associated epoch is equal to the current one, then the global epoch is incremented.

Finally, consider the following scenario. Suppose that a thread $T_{1}$ is running a range query, the current epoch is $E$ and the current global timestamp is $t$. Next, suppose that another thread, $T_{2}$, reclaims a node $n$ that has been retired during $E$, and that is relevant for $T_{1}$’s range query. Starting from this point, whenever $T_{1}$ accesses the newly allocated node, it rolls back and starts its traversal from scratch (as the new node has a birth epoch which is greater then its predecessor through the prior pointer, foiling guideline 3). As long as $T_{1}$’s $ts$ variable does not change, $T_{1}$ will infinitely get to the new allocated node and then roll-back to the beginning. We reduce the probability of such scenarios in practice, by updating the $ts$ variable in line 12 of Algorithm 2. We further ensure that that the current global timestamp is up-to-date by incrementing it upon each re-allocation, if necessary.

Our linked-list implementation encapsulates the key-value pairs and enables the timestamps mechanism. However, when key ranges are large, the linked-list does not perform as good as other concurrent data-structures. It forces a linear traversal per operation, as opposed to skip lists [24, 29] and binary search trees [43, 14]. We observe that the index links in such data-structures (e.g., the links connecting the upper levels in a skip list or the inner levels in a tree) are only required for fast access. The actual data exists only in the lowest level of the skip list (or the leaves of an external tree). Therefore, we allow a simple integration of an external index, enabling fast access instead of long traversals. The index should provide an insert(key, node) operation, receiving a key and a node pointer as its associated value. It additionally should provide a remove(key) operation. Finally, instead of providing a contains(key) operation, it should provide a findPred(key) operation, receiving a key and returning a pointer to the node associated with some key which is smaller than the given one.

The findPred(key) can be naively implemented by calling the data-structure search method (there usually exists such method. E.g., [26, 43, 29]) with a smaller key as input. I.e., it is possible to search for key minus 2 or minus 10. Obviously, this does not guarantee that a suitable node will indeed be returned. However, if the selected smaller key is not small enough, it is possible to start a new trial and search for a smaller key. Our experiments showed that limiting the number of such trials per search to a small constant (e.g., 5 in our experiments) is negligible in terms of performance, and is usually enough for locating a relevant node. In addition, the index is used only for fast access, so correctness is not affected even if all trials fail. Specifically, the findPred(key) operation can be easily implemented for a skip list, using its built-in search auxiliary method [24, 29] (as it returns a predecessor with a smaller key). Examples for using a skip list as a fast index have already been introduced for linearizable data-structures [58] and in the transactional memory setting [63]. The findPred(key) operation can also be implemented for some binary search trees, by traversing the left child, instead of the right child, at some point during the search path. We applied this method when implementing our tree index, based on Natarajan and Mittal’s BST [43].

We update the fast index as follows: New Nodes are inserted into the index after being inserted into the list (i.e., right before the insert() operation returns in line 16 of Algorithm 1). Nodes are removed from the index after being removed from the list, and right before being retired (see Section 3.3). Note that the curr node, replaced by newCurr via the CAS in line 68, should be removed from the index, followed by an insertion of newCurr. In our implemented index, we have implemented an update() operation instead. This operation receives as input a node reference, and uses it to replace a node with the same key in the index⁵⁵5The implemented update() operation also takes the node’s birth epoch into account, and does not replace a node with a reclaimed node or with a node with a smaller birth epoch. In case the external index does not provide an update() operation, this also may be executed via the standard remove() operation, followed by a respective insert() operation. The index is read only during the find() auxiliary method. Instead of starting each list traversal from the head sentinel node (see line 30 in Algorithm 1), the traversing thread tries to shorten the traversal by accessing the fast index. I.e., instead of executing the code in lines 30-31 of Algorithm 1, each thread executes the code from Algorithm 3. It starts by initializing the searched key to the input key (received as input in line 28 of Algorithm 1). Then, after finding the alleged predecessor, using the findPred() operation (line 4), if its birth epoch is bigger than the last recorded one, the executing thread rolls-back to its last recorded checkpoint (see Section 3.3). Otherwise, if pred’s key is not smaller than the given input key, or its timestamp is not initialized yet (this is a possible scenario, as we show in Appendix E), the thread starts another trial, with the same key. Otherwise, if pred is either marked or flagged (line 11), the thread starts another trial, with a smaller key. Otherwise, it is guaranteed that pred and predNext hold a valid node and its (unmarked and unflagged) next pointer, respectively, and the thread may start its list traversal from line 32 of Algorithm 1. Note that the code presented in Algorithm 3 always terminates, as in the worst case scenario, the loop breaks after a predefined number of attempts. A full correctness proof appears in Appendix E.