Concurrent hash table

When creating concurrent hash tables, the functions accessing the table with the chosen hashing algorithm need to be adapted for concurrency by adding a conflict resolution strategy. Such a strategy requires managing accesses in a way such that conflicts caused by them do not result in corrupt data, while ideally increasing their efficiency when used in parallel. Herlihy and Shavit[5] describe how the accesses to a hash table without such a strategy - in its example based on a basic implementation of the Cuckoo hashing algorithm - can be adapted for concurrent use. Fan et al.[6] further describe a table access scheme based on cuckoo hashing that is not only concurrent, but also keeps the space efficiency of its hashing function while also improving cache locality as well as the throughput of insertions.

When hash tables are not bound in size and are thus allowed to grow/shrink when necessary, the hashing algorithm needs to be adapted to allow this operation. This entails modifying the used hash function to reflect the new key-space of the resized table. A concurrent growing algorithm is described by Maier et al.[1]

Mega-KV[7] is a high performance key-value store system, where the cuckoo hashing is used and the KV indexing is massively parallelized in batch mode by GPU. With further optimizations of GPU acceleration by Nvidia and Oak Ridge National Lab, Mega-KV was pushed to another high record of the throughput in 2018 (up to 888 millions of key-value operations per second).[8]

Concurrent accesses causing contention (marked in red).

As with any concurrent data structure, concurrent hash tables suffer from a variety of problems known in the field of concurrent computing as a result of contention.[3] Examples for such are the ABA problem, race conditions, and deadlocks. The extent in which these problems manifest or even occur at all depends on the implementation of the concurrent hash table; specifically which operations the table allows to be run concurrently, as well as its strategies for mitigating problems associated with contention. When handling contention, the main goal is the same as with any other concurrent data structure, namely ensuring correctness for every operation on the table. At the same time, it should naturally be done in such a way as to be more efficient than a sequential solution when used concurrently. This is also known as concurrency control.

Phase concurrency

Concurrent accesses grouped into distinct phases.

A phase concurrent hash table groups accesses by creating phases in which only one type of operation is allowed (i.e. a pure write-phase), followed by a synchronization of the table state across all threads. A formally proven algorithm for this is given by Shun and Blelloch.[2]

Naturally, concurrent hash tables find application wherever sequential hash tables are useful. The advantage that concurrency delivers herein lies within the potential speedup of these use-cases, as well as the increased scalability.[1] Considering hardware such as multi-core processors that become increasingly more capable of concurrent computation, the importance of concurrent data structures within these applications grow steadily.[3]

Maier et al.[1] perform a thorough analysis on a variety of concurrent hash table implementations, giving insight into the effectiveness of each in different situations that are likely to occur in real use-cases. The most important findings can be summed up as the following:

As expected low contention leads to positive behavior across every operation, whereas high contention becomes problematic when it comes to writing. The latter however is a problem of high contention in general, wherein the benefit of concurrent computation is negated due to the natural requirement for concurrency control restricting contending accesses. The resulting overhead causes worse performance than that of the ideal sequential version. In spite of this, concurrent hash tables still prove invaluable even in such high contention scenarios when observing that a well-designed implementation can still achieve very high speedups by leveraging the benefits of concurrency to read data concurrently.

However, real use-cases of concurrent hash tables are often not simply sequences of the same operation, but rather a mixture of multiple types. As such, when a mixture of insert and find operations is used the speedup and resulting usefulness of concurrent hash tables become more obvious, especially when observing find heavy workloads.

Ultimately the resulting performance of a concurrent hash table depends on a variety of factors based upon its desired application. When choosing the implementation, it is important to determine the necessary amount of generality, contention handling strategies and some thoughts on whether the size of the desired table can be determined in advance or a growing approach must be used instead.

• Since Java 1.5, concurrent hash maps are provided based upon concurrent map interface.[9]
• libcuckoo provides concurrent hash tables for C/C++ allowing concurrent reads and writes. The library is available on GitHub.[10]
• Threading Building Blocks provide concurrent unordered maps for C++ which allow concurrent insertion and traversal and are kept in a similar style to the C++11 std::unordered_map interface. Included within are the concurrent unordered multimaps, which allow multiple values to exist for the same key in a concurrent unordered map.[11] Additionally, concurrent hash maps are provided which build upon the concurrent unordered map and further allow concurrent erasure and contain built-in locking.[12]
• growt provides concurrent growing hash tables for C++ on the basis of the so-called folklore implementation. Based on this non-growing implementation, a variety of different growing hash tables is given. These implementations allow for concurrent reads, inserts, updates (notably updating values based on the current value at the key) and removals (based upon updating using tombstones). Beyond that, variants on the basis of Intel TSX are provided. The library is available on GitHub.[1][13]
• folly provides concurrent hash tables[14] for C++14 and later ensuring wait-free readers and lock-based, sharded writers. As stated on its GitHub page, this library provides useful functionality for Facebook.[15]
• Junction provides several implementations of concurrent hash tables for C++ on the basis of atomic operations to ensure thread-safety for any given member function of the table. The library is available on GitHub.[16]

• Parallel computing
• Liveness
• Ctrie

• Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 299–328. ISBN 978-0-12-370591-4.