A Lock-free Binary Trie

Finding the predecessor of a key in a dynamic set is a fundamental problem with wide-ranging applications in sorting, approximate matching and nearest neighbour algorithms. Data structures supporting Predecessor can be used to design efficient priority queues and mergeable heaps [42], and have applications in IP routing [15] and bioinformatics [3, 31].

A binary trie is a simple sequential data structure that maintains a dynamic set of keys $S$ from the universe $U=\{0,\dots,u-1\}$. Predecessor$(y)$ returns the largest key in $S$ less than key $y$, or $-1$ if there is no key smaller than $y$ in $S$. It supports Search with $O(1)$ worst-case step complexity and Insert, Delete, and Predecessor with $O(\log u)$ worst-case step complexity. It has $\Theta(u)$ space complexity.

The idea of a binary trie is to represent the prefixes of keys in $U$ in a sequence of $b+1$ arrays, $\mathit{D}_{i}$, for $0\leq i\leq b$, where $b=\lceil\log_{2}u\rceil$. Each array $\mathit{D}_{i}$ has length $2^{i}$ and is indexed by the bit strings $\{0,1\}^{i}$. The array entry $\mathit{D}_{i}[x]$ stores the bit 1 if $x$ is the prefix of length $i$ of some key in $S$, and 0 otherwise. The sequence of arrays implicitly forms a perfect binary tree. The array entry $\mathit{D}_{i}[x]$ represents the node at depth $i$ with length $i$ prefix $x$. Its left child is the node represented by $\mathit{D}_{i+1}[x\cdot 0]$ and its right child is the node represented by $\mathit{D}_{i+1}[x\cdot 1]$. Note that $\mathit{D}_{b}$ (which represents the leaves of the binary trie) is a direct access table describing the set $S\subseteq U$. An example of a binary trie is shown in Figure 1.

A Search$(x)$ operation reads $\mathit{D}_{b}[x]$ and returns True if $\mathit{D}_{b}[x]$ has value 1, and False otherwise. An Insert$(x)$ operation sets the bits of the nodes on the path from the leaf $\mathit{D}_{b}[x]$ to the root to 1. A Delete$(x)$ operation begins by setting $\mathit{D}_{b}[x]$ to 0. It then traverses up the trie starting at $\mathit{D}_{b}[x]$, setting the value of the parent of the current node to 0 if both its children have value 0. A Predecessor$(y)$ operation $pOp$ traverses up the trie starting from the leaf $\mathit{D}_{b}[y]$ to the root. If the left child of each node on this path either has value 0 or is also on this path, then $pOp$ returns $-1$. Otherwise, consider the first node on this path whose left child $t$ has value 1 and is not on this path. Then starting from $t$, $pOp$ traverses down the right-most path of nodes with value 1 until it reaches a leaf $\mathit{D}_{b}[w]$, and returns $w$.

More complicated variants of sequential binary tries exist, such as van Emde Boas tries [41], x-fast tries and y-fast tries [44]. Compared to binary tries, they improve the worst-case complexity of predecessor operations. Both x-fast tries and y-fast tries use hashing to improve the space complexity, and hence are not deterministic. Furthermore, none of these variants support constant time search. One motivation for studying lock-free binary tries is as a step towards efficient lock-free implementations of these data structures.

Universal constructions provide a framework to give (often inefficient) implementations of concurrent data structures from sequential specifications. A recent universal construction by Fatourou, Kallimanis, and Kanellou [19] can be used to implement a wait-free binary trie supporting operations with $O(P+\bar{c}(op)\cdot\log u)$ worst-case step complexity, where $P$ is the number of processes in the system, and $\bar{c}(op)$, is the interval contention of $op$. This is the number of Insert, Delete, and Predecessor operations concurrent with the operation $op$. Prior to this work, there have been no lock-free implementations of a binary trie or any of its variants without using universal constructions.

There are many lock-free data structures that directly implement a dynamic set, including variations of linked lists, balanced binary search trees, skip lists [36], and hash tables. There is also a randomized, lock-free implementation of a skip trie[33]. We discuss these data structures in more detail in Section 3.

Our contribution: We give a lock-free implementation of a binary trie using registers, compare-and-swap (CAS) objects, and ($b+1$)-bounded min-registers. A min-write on a ($b+1$)-bit memory location can be easily implemented using a single ($b+1$)-bit AND operation, so all these shared objects are supported in hardware. The amortized step complexity of our lock-free implementation of the binary trie is expressed using two other measures of contention. For an operation $op$, the point contention of $op$, denoted $\dot{c}(op)$, is the maximum number of concurrent Insert, Delete, and Predecessor operations at some point during $op$. The overlapping-interval contention [33] of $op$, denoted, $\tilde{c}(op)$ is the maximum interval contention of all update operations concurrent with $op$. Our implementation supports Search with $O(1)$ worst-case step complexity, and Insert with $O(\dot{c}(op)^{2}+\log u)$ amortized step complexity, and Delete and Predecessor operations with $O(\dot{c}(op)^{2}+\tilde{c}(op)+\log u)$ amortized step complexity. In a configuration $C$ where there are $\dot{c}(C)$ concurrent Insert, Delete, and Predecessor operations, the implementation uses $O(u+\dot{c}(C)^{2})$ space. Our data structure consists of a relaxed binary trie, as well as auxiliary lock-free linked lists. Our goal was to maintain the $O(1)$ worst-case step complexity of Search, while avoiding $O(\bar{c}(op)\cdot\log u)$ terms in the amortized step complexity of the other operations seen in universal constructions of a binary trie. Our algorithms to update the bits of the relaxed binary trie and traverse the relaxed binary trie finish in $O(\log u)$ steps in the worst-case, and hence are wait-free. The other terms in the amortized step complexity are from updating and traversing the auxiliary lock-free linked lists.

Techniques: A linearizable implementation of a concurrent data structure requires that all operations on the data structure appear to happen atomically. In our relaxed binary trie, predecessor operations are not linearizable. We relax the properties maintained by the binary trie, so that the bit stored in each internal binary trie node does not always have to be accurate. At a high-level, we ensure that the bit at a node is accurate when there are no active update operations whose input key is a leaf of the subtrie rooted at the node. This allows us to design an efficient, wait-free algorithm for modifying the bits along a path in the relaxed binary trie.

Other lock-free data structures use the idea of relaxing properties maintained by the data structure. For example, in lock-free balanced binary search trees [11], the balance conditions are often relaxed. This allows the tree to be temporarily unbalanced, provided there are active update operations. A node can be inserted into a tree by updating a single pointer. Following this, tree rotations may be performed, but they are only used to improve the efficiency of search operations. Lock-free skip lists [21] relax the properties about the heights of towers of nodes. A new node is inserted into the bottom level of a skip list using a single pointer update. Modifications that add nodes into the linked lists at higher levels only improve the efficiency of search operations.

Relaxing the properties of the binary trie is more complicated than these two examples because it affects correctness, not just efficiency. For a predecessor operation to traverse a binary trie using the sequential algorithm, the bit of each node must be the logical OR of its children. This is not necessarily the case in our relaxed binary trie. For example, a node in the relaxed binary trie with value 1 may have two children which each have value 0.

The second way our algorithm is different from other data structures is how operations help each other complete. Typical lock-free data structures, including those based on universal constructions, use helping when concurrent update operations require modifying the same part of a data structure: a process may help a different operation complete by making modifications to the data structure on the other operation’s behalf. This technique is efficient when a small, constant number of modifications to the data structure need to be done atomically. For example, many lock-free implementations of linked lists and binary search trees can insert a new node by repeatedly attempting CAS to modify a single pointer. For a binary trie, update operations require updating $O(\log u)$ bits on the path from a leaf to the root. An operation that helps all these updates complete would have $O(\dot{c}(op)\cdot\log u)$ amortized step complexity.

Predecessor operations that cannot traverse a path through the relaxed binary trie do not help concurrent update operations complete. For our linearizable, lock-free binary trie, our approach is to have update operations and predecessor operations announce themselves in an update announcement linked list and a predecessor announcement linked list, respectively. We guarantee that a predecessor operation will either learn about concurrent update operations by traversing the update announcement linked list, or it will be notified by concurrent update operations via the predecessor announcement linked list. A predecessor operation uses this information to determine a correct return value, especially when it cannot complete its traversal of the relaxed binary trie. This is in contrast to other lock-free data structures that typically announce operations so that they can be completed by concurrent operations in case the invoking processes crash.

Section 2 describes the asynchronous shared memory model. In Section 3, we describe related lock-free data structures and compare them to our lock-free binary trie. In Section 4 we give the specification of a relaxed binary trie, give a high-level description of our wait-free implementation, present the pseudocode of the algorithm, and prove it correct. In Section 5, we give a high-level description of our implementation of a lock-free binary trie, present the pseudocode of the algorithm and a more detailed explanation, prove it is linearizable, and analyze its amortized step complexity. We conclude in Section 6. .

Throughout this paper, we use an asynchronous shared memory model. Shared memory consists of a collection of shared objects accessible by all processes in a system. The primitives supported by these objects are performed atomically. A register is an object supporting Write$(w)$, which stores $w$ into the object, and Read$()$, which returns the value stored in the object. CAS$(r,old,new)$ compares the value stored in object $r$ with the value $old$. If the two values are the same, the value stored in $r$ is replaced with the value $new$ and True is returned; otherwise False is returned. A min-register is an object that stores a value, and supports Read$()$, which returns the value of the object, and MinWrite$(w)$, which changes the value of the object to $w$ if $w$ is smaller than its previous value.

A configuration of a system consists of the values of all shared objects and the states of all processes. A step by a process either accesses or modifies a shared object, and can also change the state of the process. An execution is an alternating sequence of configurations and steps, starting with a configuration.

An abstract data type is a collection of objects and types of operations that satisfies certain properties. A concurrent data structure for the abstract data type provides representations of the objects in shared memory and algorithms for the processes to perform operations of these types. An operation on a data structure by a process becomes active when the process performs the first step of its algorithm. The operation becomes inactive after the last step of the algorithm is performed by the process. This last step may include a response to the operation. The execution interval of the operation consists of all steps between its first and last step (which may include steps from processes performing other operations). In the initial configuration, the data structure is empty and there are no active operations.

We consider concurrent data structures that are linearizable [28], which means that its operations appear to occur atomically. One way to show that a concurrent data structure is linearizable is by defining a linearization function, which, for all executions of the data structure, maps all completed operations and a subset of the uncompleted operations in the execution to a step or configuration, called its linearization point. The linearization points of these operations must satisfy two properties. First, each linearized operation is mapped to a step or configuration within its execution interval. Second, the return value of the linearized operations must be the same as in the execution in which all the linearized operations are performed atomically in the order of their linearization points, no matter how operations with the same linearization point are ordered.

A concurrent data structure is strong linearizability if its linearization function satisfies an additional prefix preserving property: For all its executions $\alpha$ and for all prefixes $\alpha^{\prime}$ of $\alpha$, if an operation is assigned a linearization point for $\alpha^{\prime}$, then it is assigned the same linearization point for $\alpha$, and if it is assigned a linearization point for $\alpha$ that occurs during $\alpha^{\prime}$, then it is assigned the same linearization point for $\alpha^{\prime}$. This means that the linearization point of each operation is determined as steps are taken in the execution and cannot depend on steps taken later in the execution. This definition, phrased somewhat differently, was introduced by Golab, Higham and Woelfel [23]. A concurrent data structure is strongly linearizable with respect to a set of operation types $\cal{O}$ if it has a linearization function that is only defined on operations whose types belong to $\cal{O}$.

A lock-free implementation of a concurrent data structure guarantees that whenever there are active operations, one operation will eventually complete in a finite number of steps. However, the execution interval of any particular operation in an execution may be unbounded, provided other operations are completed. A wait-free implementation of a concurrent data structure guarantees that every operation completes within a finite number of steps by the process that invoked the operation.

The worst-case step complexity of an operation is the maximum number of steps taken by a process to perform any instance of this operation in any execution. The amortized step complexity of a data structure is the maximum number of steps in any execution consisting of operations on the data structure, divided by the number operations invoked in the execution. One can determine an upper bound on the amortized step complexity by assigning an amortized cost to each operation, such that for all possible executions $\alpha$ on the data structure, the total number of steps taken in $\alpha$ is at most the sum of the amortized costs of the operations in $\alpha$.

In this section, we discuss related lock-free data structures and the techniques used to implement them. We first describe simple lock-free linked lists, which are a component of our binary trie. We next describe search tree implementations supporting Predecessor, and discuss the general techniques used. Next we describe implementations of a Patricia trie and a skip trie. Finally, we discuss some universal constructions and general techniques for augmenting existing data structures.

There are many existing implementations of lock-free linked lists [24, 38, 40]. The implementation with best amortized step complexity is by Fomitchev and Ruppert [21]. It supports Insert, Delete, Predecessor, and Search operations $op$ with $O(n(op)+\dot{c}(op))$ amortized step complexity, where $n(op)$ is the number of nodes in the linked list at the start of $op$. When $n(op)$ is in $O(\dot{c}(op))$, such as in the case of our binary trie implementation, operations have $O(\dot{c}(op))$ amortized step complexity. This implementation uses flagging: a pointer that is flagged indicates an update operation wishes to modify it. Concurrent update operations that also need to modify this pointer must help the operation that flagged the pointer to complete before attempting to perform their own operation. After an update operation completes helping, it backtracks (using back pointers set in deleted nodes) to a suitable node in the linked list before restarting its own operation.

Ellen, Fatourou, Ruppert, and van Breugel [18] give the first provably correct lock-free implementation of an unbalanced binary search tree using CAS. Update operations are done by flagging a constant number of nodes, followed by a single pointer update. A flagged node contains a pointer to an operation record, which includes enough information about the update operation so that other processes can help it complete. Ellen, Fatourou, Helga, and Ruppert [17] improve the efficiency of this implementation so each operation $op$ has $O(h(op)+\dot{c}(op))$ amortized step complexity, where $h(op)$ is the height of the binary search tree when $op$ is invoked. This is done by allowing an update operation to backtrack along its search paths by keeping track of nodes it visited in a stack. There are many other implementations of lock-free unbalanced binary search trees [9, 14, 29, 32].

There are also many implementations of lock-free balanced binary search trees [5, 6, 8, 16]. Brown, Ellen, and Ruppert designed a lock-free balanced binary search tree [11] by implementing more powerful primitives, called LLX and SCX, from CAS [10]. These primitives are generalizations of LL and SC. SCX allows a single field to be updated by a process provided a specified set of nodes have not been modified since that process last performed LLX on them. Ko [30] shows that a version of their lock-free balanced binary search tree has good amortized step complexity.

Although a binary trie represents a perfect binary tree, the techniques we use to implement a binary trie are quite different than those that have been used to implement lock-free binary search trees. The update operations of a binary trie may require updating the bits of all nodes on the path from a leaf to the root. LLX and SCX do not facilitate this because SCX only updates a single field.

Brown, Prokopec, and Alistarh [12] give an implementation of an interpolation search tree supporting Search with $O(P+\log n(op))$ amortized step complexity, and Insert and Delete with $O(\bar{c}_{avg}(P+\log n(op))$ amortized step complexity, where $\bar{c}_{avg}$ is the average interval contention of the execution. Their data structure is a balanced search tree where nodes can have large degree. A node containing $n$ keys in its subtree is ideally balanced when it has $\sqrt{n}$ children, each of which contains $\sqrt{n}$ nodes in its subtree. Update operations help replace subtrees that become too unbalanced with ideally balanced subtrees. When the input distribution of keys is well-behaved, Search can be performed with $O(P+\log\log n(op))$ expected amortized step complexity and update operations can be performed with $O(\bar{c}_{avg}(P+\log\log n(op))$ expected amortized step complexity. Their implementation relies on the use of double-compare single-swap (DCSS). DCSS is not a primitive typically supported in hardware, although there exist implementations of DCSS from CAS [1, 22, 25].

Shafiei [37] gives an implementation of a Patricia trie. The data structure is similar to a binary trie, except that only internal nodes whose children both have value 1 are stored. In addition to Search, Insert and Delete, it supports Replace, which removes a key and adds another key in a possibly different part of the trie. Her implementation uses a variant of the flagging technique described in [18], except that it can flag two different nodes with the same operation record.

Oshman and Shavit [33] introduce a randomized data structure called a skip trie. It combines an x-fast trie with a truncated skip list whose max height is $\log_{2}\log_{2}u$ (i.e. it is a y-fast trie whose balanced binary search trees are replaced with a truncated skip list). Only keys that are in the top level of the skip list are in the x-fast trie. They give a lock-free implementation of a skip trie supporting Search, Insert, Delete, and Predecessor operations with $O(\tilde{c}(op)+\log\log u)$ expected amortized step complexity from registers, CAS and DCSS. Their x-fast trie uses lock-free hash tables [39]. Their x-fast trie implementation supports update operations with $O(\dot{c}(op)\cdot\log u)$ expected amortized step complexity. Their skip list implementation is similar to Fomitchev and Ruppert’s skip list implementation [21]. In the worst-case (for example, when the height of the skip list is 0), a skip trie performs the same as a linked list, so Search and Predecessor take $\Theta(n)$ steps, even when there are no concurrent updates. Our lock-free binary trie implementation is deterministic, does not rely on hashing, uses primitives supported in hardware, and always performs well when there are no concurrent update operations. Furthermore, Search operations in our binary trie complete in a constant number of reads in the worst-case.

The first universal constructions were by Herhily [26, 27]. To achieve wait-freedom, he introduced an announcement array where operations announce themselves. Processes help perform these announced operations in a round-robin order. Barnes [2] gives a universal construction for obtaining lock-free data structures. He introduces the idea of using operation records to facilitate helping.

Lock-free data structures can be augmented to support iterators, snapshots, and range queries [13, 20, 34, 35]. Wei et al. [43] give a simple technique to take snapshots of concurrent data structures in constant time. This is done by implementing a versioned CAS object that allows old values of the object to be read. The number of steps needed to read the value of a versioned CAS object at the time of a snapshot is equal to the number of times its value changed since the snapshot was taken. Provided update operations only perform a constant amortized number of successful versioned CAS operations, balanced binary search trees can be augmented to support Predecessor with $O(\bar{c}(op)+\log n(op))=O(\dot{c}(op)+\log n(op))$ amortized step complexity.

In this section, we describe our relaxed binary trie, which is used as a component of our lock-free binary trie. We begin by giving the formal specification of the relaxed binary trie in Section 4.1. In Section 4.2, we describe how our implementation is represented in memory. In Section 4.3, we give a high-level description of our algorithms for each operation. In Section 4.4, we give a detailed description of our algorithms for each operation and its pseudocode. Finally, in Section 4.5, we show that our implementation satisfies the specification.