Ctrie

Last updated

A concurrent hash-trie or Ctrie [1] [2] is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. [3] It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots. [2] [4]

Contents

Operation

The Ctrie data structure is a non-blocking concurrent hash array mapped trie based on single-word compare-and-swap instructions in a shared-memory system. It supports concurrent lookup, insert and remove operations. Just like the hash array mapped trie, it uses the entire 32-bit space for hash values thus having low risk of hashcode collisions. Each node may have up to 32 sub-nodes, but to conserve memory, the list of sub-nodes is represented by a 32-bit bitmap where each bit indicates the presence of a branch, followed by a non-sparse array (of pointers to sub-nodes) whose length equals the Hamming weight of the bitmap.

Keys are inserted by doing an atomic compare-and-swap operation on the node which needs to be modified. To ensure that updates are done independently and in a proper order, a special indirection node (an I-node) is inserted between each regular node and its subtries[ check spelling ].

Ctrie insert operation Ctrie-insert.png
Ctrie insert operation

The figure above illustrates the Ctrie insert operation. Trie A is empty - an atomic CAS instruction is used to swap the old node C1 with the new version of C1 which has the new key k1. If the CAS is not successful, the operation is restarted. If the CAS is successful, we obtain the trie B. This procedure is repeated when a new key k2 is added (trie C). If two hashcodes of the keys in the Ctrie collide as is the case with k2 and k3, the Ctrie must be extended with at least one more level - trie D has a new indirection node I2 with a new node C2 which holds both colliding keys. Further CAS instructions are done on the contents of the indirection nodes I1 and I2 - such CAS instructions can be done independently of each other, thus enabling concurrent updates with less contention.

The Ctrie is defined by the pointer to the root indirection node (or a root I-node). The following types of nodes are defined for the Ctrie:

structure INode {     main: CNode }   structure CNode {     bmp: integer     array: Branch[2^W] }   Branch: INode | SNode   structure SNode {     k: KeyType     v: ValueType }

A C-node is a branching node. It typically contains up to 32 branches, so W above is 5. Each branch may either be a key-value pair (represented with an S-node) or another I-node. To avoid wasting 32 entries in the branching array when some branches may be empty, an integer bitmap is used to denote which bits are full and which are empty. The helper method flagpos is used to inspect the relevant hashcode bits for a given level and extract the value of the bit in the bitmap to see if its set or not - denoting whether there is a branch at that position or not. If there is a bit, it also computes its position in the branch array. The formula used to do this is:

bit = bmp & (1 << ((hashcode >> level) & 0x1F)) pos = bitcount((bit - 1) & bmp)

Note that the operations treat only the I-nodes as mutable nodes - all other nodes are never changed after being created and added to the Ctrie.

Below is an illustration of the pseudocode of the insert operation:

definsert(k,v)r=READ(root)ifiinsert(r,k,v,0,null)=RESTARTinsert(k,v)defiinsert(i,k,v,lev,parent)cn=READ(i.main)flag,pos=flagpos(k.hc,lev,cn.bmp)ifcn.bmp&flag=0{ncn=cn.inserted(pos,flag,SNode(k,v))ifCAS(i.main,cn,ncn)returnOKelsereturnRESTART}cn.array(pos)match{casesin:INode=>{returniinsert(sin,k,v,lev+W,i)casesn:SNode=>ifsn.k≠k{nsn=SNode(k,v)nin=INode(CNode(sn,nsn,lev+W))ncn=cn.updated(pos,nin)ifCAS(i.main,cn,ncn)returnOKelsereturnRESTART}else{ncn=cn.updated(pos,SNode(k,v))ifCAS(i.main,cn,ncn)returnOKelsereturnRESTART}}

The inserted and updated methods on nodes return new versions of the C-node with a value inserted or updated at the specified position, respectively. Note that the insert operation above is tail-recursive, so it can be rewritten as a while loop. Other operations are described in more detail in the original paper on Ctries. [1] [5]

The data-structure has been proven to be correct [1] - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties. The lookup operation can be modified to guarantee wait-freedom.

Advantages of Ctries

Ctries have been shown to be comparable in performance with concurrent skip lists, [2] [4] concurrent hash tables and similar data structures in terms of the lookup operation, being slightly slower than hash tables and faster than skip lists due to the lower level of indirections. However, they are far more scalable than most concurrent hash tables where the insertions are concerned. [1] Most concurrent hash tables are bad at conserving memory - when the keys are removed from the hash table, the underlying array is not shrunk. Ctries have the property that the allocated memory is always a function of only the current number of keys in the data-structure. [1]

Ctries have logarithmic complexity bounds of the basic operations, albeit with a low constant factor due to the high branching level (usually 32).

Ctries support a lock-free, linearizable, constant-time snapshot operation, [2] based on the insight obtained from persistent data structures. This is a breakthrough in concurrent data-structure design, since existing concurrent data-structures do not support snapshots. The snapshot operation allows implementing lock-free, linearizable iterator, size and clear operations - existing concurrent data-structures have implementations which either use global locks or are correct only given that there are no concurrent modifications to the data-structure. In particular, Ctries have an O(1) iterator creation operation, O(1) clear operation, O(1) duplicate operation and an amortized O(logn) size retrieval operation.

Problems with Ctries

Most concurrent data structures require dynamic memory allocation, and lock-free concurrent data structures rely on garbage collection on most platforms. The current implementation [4] of the Ctrie is written for the JVM, where garbage collection is provided by the platform itself. While it's possible to keep a concurrent memory pool for the nodes shared by all instances of Ctries in an application or use reference counting to properly deallocate nodes, the only implementation so far to deal with manual memory management of nodes used in Ctries is the common-lisp implementation cl-ctrie, which implements several stop-and-copy and mark-and-sweep garbage collection techniques for persistent, memory-mapped storage. Hazard pointers are another possible solution for a correct manual management of removed nodes. Such a technique may be viable for managed environments as well, since it could lower the pressure on the GC. A Ctrie implementation in Rust makes use of hazard pointers for this purpose. [6]

Implementations

A Ctrie implementation [4] for Scala 2.9.x is available on GitHub. It is a mutable thread-safe implementation which ensures progress and supports lock-free, linearizable, O(1) snapshots.

History

Ctries were first described in 2011 by Aleksandar Prokopec. [1] To quote the author:

Ctrie is a non-blocking concurrent shared-memory hash trie based on single-word compare-and-swap instructions. Insert, lookup and remove operations modifying different parts of the hash trie can be run independent of each other and do not contend. Remove operations ensure that the unneeded memory is freed and that the trie is kept compact.

In 2012, a revised version of the Ctrie data structure was published, [2] simplifying the data structure and introducing an optional constant-time, lock-free, atomic snapshot operation.

In 2018, the closely related Cache-Trie data structure was proposed, [16] which augmented Ctries with an auxiliary, quiescently consistent cache data structure. This "cache" is a hash-table-like entity that makes a best effort to "guess" the appropriate node on a deeper level of the trie, and is maintained in a way such that it's as close as possible to the level where most of the trie's elements are. Cache tries were shown to have amortized expected O(1) complexity of all the basic operations.

Related Research Articles

<span class="mw-page-title-main">Data structure</span> Particular way of storing and organizing data in a computer

In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data.

<span class="mw-page-title-main">Hash table</span> Associative array for storing key-value pairs

In computing, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. A map implemented by a hash table is called a hash map.

In computer science, a priority queue is an abstract data type similar to a regular queue or stack abstract data type. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.

<span class="mw-page-title-main">Trie</span> Search tree data structure

In computer science, a trie, also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store their associated key. Instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key.

In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article.

<span class="mw-page-title-main">Dynamic array</span> List data structure to which elements can be added/removed

In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static arrays, which have a fixed capacity that needs to be specified at allocation.

In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization. STM is a strategy implemented in software, rather than as a hardware component. A transaction in this context occurs when a piece of code executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in a 1986 paper by Tom Knight. The idea was popularized by Maurice Herlihy and J. Eliot B. Moss. In 1995, Nir Shavit and Dan Touitou extended this idea to software-only transactional memory (STM). Since 2005, STM has been the focus of intense research and support for practical implementations is growing.

<span class="mw-page-title-main">Radix tree</span> Data structure

In computer science, a radix tree is a data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at most the radix r of the radix tree, where r = 2x for some integer x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets and for sets of strings that share long prefixes.

In computer science, a ternary search tree is a type of trie where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion.

In computer science, hash trie can refer to:

<span class="mw-page-title-main">Java collections framework</span> Collections in Java

The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures.

A hash array mapped trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie. It is a refined version of the more general notion of a hash tree.

In computer science, an x-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time O(log log M), using O(n log M) space, where n is the number of stored values and M is the maximum value in the domain. The structure was proposed by Dan Willard in 1982, along with the more complicated y-fast trie, as a way to improve the space usage of van Emde Boas trees, while retaining the O(log log M) query time.

In computer science, a hash tree is a persistent data structure that can be used to implement sets and maps, intended to replace hash tables in purely functional programming. In its basic form, a hash tree stores the hashes of its keys, regarded as strings of bits, in a trie, with the actual keys and (optional) values stored at the trie's "final" nodes.

The HAT-trie is a type of radix trie that uses array nodes to collect individual key–value pairs under radix nodes and hash buckets into an associative array. Unlike a simple hash table, HAT-tries store key–value in an ordered collection. The original inventors are Nikolas Askitis and Ranjan Sinha. Askitis & Zobel showed that building and accessing the HAT-trie key/value collection is considerably faster than other sorted access methods and is comparable to the array hash which is an unsorted collection. This is due to the cache-friendly nature of the data structure which attempts to group access to data in time and space into the 64 byte cache line size of the modern CPU.

In computer science, persistent memory is any method or apparatus for efficiently storing data structures such that they can continue to be accessed using memory instructions or memory APIs even after the end of the process that created or last modified them.

A non-blocking linked list is an example of non-blocking data structures designed to implement a linked list in shared memory using synchronization primitives:

The Java programming language's Java Collections Framework version 1.5 and later defines and implements the original regular single-threaded Maps, and also new thread-safe Maps implementing the java.util.concurrent.ConcurrentMap interface among other concurrent interfaces. In Java 1.6, the java.util.NavigableMap interface was added, extending java.util.SortedMap, and the java.util.concurrent.ConcurrentNavigableMap interface was added as a subinterface combination.

<span class="mw-page-title-main">Concurrent hash table</span>

A concurrent hash table or concurrent hash map is an implementation of hash tables allowing concurrent access by multiple threads using a hash function.

References

  1. 1 2 3 4 5 6 Prokopec, Aleksandar; Bagwell, Phil; Odersky, Martin (June 14, 2011). Cache-Aware Lock-Free Concurrent Hash Tries (Technical report). Archived from the original on December 19, 2024.
  2. 1 2 3 4 5 Prokopec, Aleksandar; Bronson, Nathan G.; Bagwell, Phil; Odersky, Martin (2012). Concurrent Tries with Efficient Non-Blocking Snapshots (PDF) (Technical report). Archived (PDF) from the original on July 27, 2024.
  3. ↑ Prokopec, Aleksandar; Bagwell, Phil; Odersky, Martin. Lock-Free Resizeable Concurrent Tries (PDF) (Technical report). Archived (PDF) from the original on April 21, 2024.
  4. 1 2 3 4 Prokopec, Aleksandar. "Ctrie - A Lock-Free Concurrent Hash Array Mapped Trie". GitHub. Archived from the original on December 11, 2023.
  5. ↑ Prokopec, Aleksandar; Bagwell, Phil; Odersky, Martin. "Lock-Free Resizeable Concurrent Tries (Slideshow)". Archived from the original on March 3, 2022.
  6. 1 2 Allard, Brandon; Reem, Johnathan. "Lock-free hash array mapped trie in Rust". GitHub. Archived from the original on March 26, 2023.
  7. ↑ Bronson, Nathan; Pereira, Marcos; Klang, Viktor; Moore, Wesley; Rytz, Lukas; Yoshida, Kenji; et al. "scala-stm: A library-based Software Transactional Memory (STM) for Scala, coupled with transactional sets and maps". GitHub. Archived from the original on October 4, 2024.
  8. ↑ Tisue, Seth. "scala/src/library/scala/collection/concurrent/TrieMap.scala at 2.13.x". GitHub.
  9. ↑ Schröder, Michael (September 29, 2017). "ctrie: Non-blocking concurrent map". Hackage. Archived from the original on October 5, 2024.
  10. ↑ Schröder, Michael; Chen, Chao-Hong. "ctrie: Non-blocking concurrent hashmap for Haskell". GitHub. Archived from the original on March 26, 2023.
  11. ↑ Varga, Robert; Kitt, Stephen; Ha, Thanh; Leggieri, Luciano; Piliar, Peter; et al. "triemap: Java port of a concurrent trie hash map implementation from the Scala collections library". GitHub. Archived from the original on February 8, 2024.
  12. ↑ Varga, Robert; Yoshida, Kenji; Jones, Mark; et al. "java-concurrent-hash-trie-map: Java port of a concurrent trie hash map implementation from the Scala collections library". GitHub. Archived from the original on December 4, 2024.
  13. ↑ Lentz, Dan. "cl-ctrie: lock-free, concurrent, key/value index with efficient memory-mapped persistence and fast transient storage models". GitHub. Archived from the original on November 19, 2024.
  14. ↑ Areias, Miguel; Rocha, Ricardo (2014). A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs (PDF) (Technical report). Archived (PDF) from the original on March 26, 2023.
  15. ↑ "ctrie: Documentation". Go. May 16, 2024. Archived from the original on December 19, 2024.
  16. ↑ Prokopec, Aleksandar (2018). Cache-Tries: Concurrent Lock-Free Hash Tries with Constant-Time Operations (PDF) (Technical report). Archived (PDF) from the original on March 3, 2024.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.