Implementing a hash table with true concurrency

Question

This was recently a question I was asked in a screening and it got me thinking. I never totally settled on how the conversation ended, and I did some digging. None of the answers I saw seemed satisfactory to me.

The question is essentially "how would you implement a thread safe hash map?" Obviously protect with a mutex, but then you have to deal with contention of multiple threads waiting on a single mutex which means access isn't truly concurrent, and so on. We eventually got to a simple design of n buckets in the hash table, with one mutex corresponding to one bucket. Easy enough, and this is where I see a lot of answers to this question on other sites stop. It does not handle what happens when the hash table is resized or for whatever reason the table is rehashed.

It was supposed that one thread would manage rehashing, so our simple design becomes n + 1 mutexes, and the managing thread has to lock all n + 1 mutexes to rehash. However, any thread that is waiting on any of the n buckets could gain ownership to a mutex which is now matched matched to a different bucket (after a rehash). Only answer I could come up w/ basically went back to a non-concurrent hash map.

I believe java has some type of concurrent hash map out of the box, but I live in a C++ world. I passed the screen but I'm still very curious about this as I never had that "a-ha" moment and it sounds like a practical application.

I do think read-write locks may be a somewhat suitable answer but again, I think there is still the caveat when rehashing.

Answer 1

I have wrestled with this. I did a few iterations on my design...

First solution: Just have a hash table with a global lock.

Second solution: Wait free fixed size hash table. We need to figure out that it is possible to implement a wait free thread safe hash set with fixed size. To do this, we are going to use an array, where the index is the hash, we will use linear probing, and all operations are going to be interlocked.

So, yes, we will have locking. However a thread will never be spin waiting or waiting on a wait handle. It takes some work to figure out how to guarantee they are all atomic.

Third solution: Lock on growth. The naive approach is to lock the structure, create a new array, copy all the data, then unlock. That works, it is thread safe. We can get away with locking only on growth because as long as the size does not change we can work as in the prior solution.

Except I do not like the down time. There are threads waiting for the copy to complete. We can do better...

Fourth solution: Cooperative growth. First implement a thread safe state machine so that the structure can change from normal use to growth and back. Next, every thread that wants to do an operation, instead of waiting, will cooperate in copying data to the new array. How? We can have an index that we increment, again with an interlocked operation... each thread increments the index, takes the element, computes where to place it in the new array, writes it there and then loops until the operation is completed.

There is a problem: it does not shrink.

Fifth solution: Sparse array. Instead of using an array, we can use a tree of arrays, and use it like a sparse array. Its size will be enough to allocate every value that our hash function can output. Now, threads can nodes as needed. We will keep track of usage of each node, that is how many children are occupied and how many threads are currently using it. When usage reaches zero, we can remove it... wait... locking? turns out we can do an optimistic solution: we keep to references to the node data, every thread will write one after operation. The thread that found 0 will erase, then read (another thread could have written it), and then copy to the second reference. All interlocked operations.

By the way, those atomic operations? Yeah, it turns out they are some common patterns we can abstract out. At the end, I only have DoMayIncrement for operation that may or may not add items, DoMayDecrement for those that may or may not remove, and Do for everything else. They will take callbacks with references to the values, which the callback code does not need to know exactly where they are stored, and we build on top of that more specific operations and add probing to handle collisions along the way.

Oh, I forgot, to minimize allocations I pool the arrays that make up the nodes of the tree.

Sixth solution: Phil Bagwell's Ideal Hash Trees. It is similar to my fifth solution. Main difference is that the tree does not behave like a sparse array where all values are inserted at the same depth. Instead, the depth of tree branches is dynamic. When a collision happens, the old node is replaced with a branch where the old node is reinserted in addition to the new node. This should make Bagwell’s solution more memory efficient on the average case. Bagwell also pools arrays. Bagwell does not elaborate on shrinking.

---

The fifth solution is what I currently use to backport/polyfill ConcurrentDictionary<TKey, TValue> to .NET 2.0. More precisely, my backport of ConcurrentDictionary<TKey, TValue> wraps around a custom type ThreadSafeDictionary<TKey, TValue> which uses a Bucket<KeyValuePair<TKey, TValue>> which implement atomic operations over a BucketCore which is my thread-safe sparse array thingy, which has the logic for shrink and grow.

Answer 2

A "hashtable with true concurrency" has problems anyway. If thread A looks up a key, while thread B deletes or adds the exact same key, then the best possible outcome is that you don't know whether A will find the key or not.

You will need more than just the usual operations to be atomic. For example, you need an operation that looks up a key, removes it, and returns it to the caller, all atomically, or your algorithms will run into trouble. If you add a key to the dictionary and immediately look it up, there is no guarantee that it is still there. Fun all over.

So the very first step is to design what operations you will support in a threadsafe way. The next thing is to make them threadsafe. The easiest thing is using one mutex. Just because a hashtable has to be threadsafe, that doesn't mean it is used a lot. I think Java has some tricks up its sleeve to make uncontested locks quite fast. Then I'd have a look if you can use a spin lock, which should be efficient because hashtable lookups should be fast. You probably should try to do the comparison of the keys outside the lock.

Answer 3

Imagine we want to add two new (key, value) pairs into your hashmap:

• calculating the hash of each key is without race condition.
• race condition happens as soon as you are accessing the buckets and look for potential collisions, since another thread may be modifying it.
• race conditions also happen when inside a bucket, since other may modify it while you're looking where to insert in the chain of coliding values.

Now as a first remark, it easy to create a lock free liked list. This would solve the last issue

You can exploit this feature and make each bucket of the hashmap a (lock-free) (empty) linked-list, at construction, before the hashmap is used concurently. This solves the first issue: accessing a bucket goes always through a lock-free linked-list.

With such a structure, you would have a nice concurrent lock-free hashmap, as long as you do not have to rearange the buckets (e.g. if you want to dynamically grow or shrink the number of buckets or change hashing function).

Edit

If you'd lock the whole table, all the advantages of our lock-free structures would be gone, since we would have to acquire the global lock.

It's very tricky to keep it lock-free, so the following idea has to be cross-checked. The idea could be to work with a shadow table that you would create once you start the resize and that will contain the new buckets:

• the readers always look in the shadow table first. If not found, it will look in the current table.
• the writers would insert in the shadow table, and mark the value from the old table as deleted if it exists.
• a mover (to be defined who) will read in the old table, insert in the shadow table (but if the CAS fails will do nothing because a newer value replaced already the old one), mark as deleted in the old table.
• once all elements in the old table are marked as deleted, switch completely to the new one, then get rid of old one.

I have not done the detailed analysis, but I think the worst that could happen is that a writer is writing a new value in the shadow while a reader just missed it and still read the old one, which defacto would be as if it would happen before the update. Another bad case would be a thread starting to look in the current table, is put on hold, and resume once the old table is deleted. It is not totally clear how to avoid this. Perhaps a use count of threads that jumped on the old table ?

Answer 4

TLDR: There are a lot of different ways of dealing with this sort of thing, and you can't even begin to choose between them until you precisely define what behaviours you need and what behaviours you are flexible about so you can at least narrow down your list of applicable concurrency models.

You would be best served by first working out a more precise definition of what you need.

1. You ask for a hash table, but must your data structure really be a hash table and nothing else? (And if so, why?) Or can it be any data structure that gives you fast key-value lookups and is mutable in some way?

2. Your "Obviously protect w/ a mutex" comment could be read as implying a serialized concurrency model such once a thread starts making a change, other threads must never see data from before the change. But is this also truly necessary? Or would you be fine (or perhaps even better off) with a "multiversion" concurrency model where a thread gets a specific version of the data structure and all lookups come from that version until it requests a later version. (If a thread wants to do multiple lookups that must be consistent, the serialized model implies that it must lock before the first read and maintain the lock util it's finished all reads for that transaction.)

If, for example, you are fine with any data structure that gives you a key-value dictionary and you can live with (or even require) multi-version concurrency, you could instead use a hash tree with a reference to it stored in a global variable.

Reads simply read the global variable to get the root of the tree and then use that copy for as long as necessary to look up values from that version of the tree, giving you consistency.

For writes you have at least two choices, depending on what sort of performance tradeoffs you want to make. You could lock the the global variable before you make changes to the dictionary and hold the lock until your changes are done. This won't block readers, but will block other writers. Alternatively, you could make your changes to an existing versio of the tree but then store the new tree only if the current version is still the same as the version you started modifying, aborting otherwise. This saves the cost of the lock, but imposes higher costs for recovery from conflict between writing threads (and possibly also more complexity in recovery if you can't easily "replay" the changes you wanted to make against the new version of the tree).

Answer 5

Thread-safe (aka "concurrent") data structures (such as hash maps) are never fully "concurrent" in the sense that two or more threads have totally concurrent access to any part of them at any time. "Concurrent" as applied to data structures simply means that they are thread-safe i.e. two or more threads can attempt concurrent access at any time, and the structure will maintain consistency for all reader/writers. In practice, this means that threads will be blocked under some circumstances; well-written concurrent structures will employ appropriate strategies to minimize the occurrence of blocking and the delay due to blocking when it does occur.