Concurrent hash table

This is just a brainstorming issue for concurrent hash tables.

@Amanieu, do you think we could make hashbrown concurrent by having a lock per bucket? When resizing the table we'd probably have to lock all buckets. That sounds like a rather straightforward approach for building a totally generic concurrent hash table without much fuss.

I'm sure we could devise a faster hash table for more specialized use cases. Apart from a fully generic HashMap<K, V>, we'd probably want to build a special HashMap<K: Copy, V> too that can avoid locks in some places.

Thoughts? What do you think would be the best way forward here? Ideally something not overly ambitious that at least gets us started. :)

cc servo/servo#22334
cc @SimonSapin

[Amanieu]

Here's a design which keeps all values in the table itself rather than through a pointer.

EDIT: There is actually a flaw with this design, which could allow the same key to be inserted twice in the map.

This is a very efficient layout since it doesn't suffer from pointer indirection. In effect, it would look just like hashbrown does today. However (K, V): Clone is required at minimum to support growing the hash table.

Once an element has been added to the table, it can be marked as erased, however the value itself will only be dropped when the table is destroyed (or the table grows and the old table is GCed).

The table will use 8-bit control bytes, just like hashbrown, but with the following bit allocation:

• 1 bit to mark the table being resized. Lookups will ignore this bit, insertions and deletions will abort the current operation and block until the table resize is complete. (This was partly inspire by the Junction hashmap)
• 1 bit to differentiate between empty and full entries.
• 6 bits of the hash code to speed up lookups. For empty entries these bits are used for extra info (deleted, reserved, etc).

Lookup is wait-free: just ignore the top bit when scanning the table.

Insertion will first try to decrement the table capacity counter, and resize the table if the capacity is full. Then search for an empty control byte, CAS it to "reserve" it, write the value to the data slot, then CAS the control byte again to "publish" the element. If at any point the resize bit is set, the operation is aborted.

Deletion is evil simpler, just perform a CAS to mark the control byte as empty. If the resize bit is set, the operation is aborted.

Aborted operations will basically block until the resize has finished, and the retry.

Resizing basically goes through the entire table and sets the resize bit on every element, while cloning them to a new table. After the resize is complete, wake up any threads waiting for the resize.

[SimonSapin]

Interesting! What about insertion when the same key already has a value in the map?

[SimonSapin]

(Aside: While reading this I was wondering if we could get away with moves instead of (K, V): Clone. In other words, can the semantic transfer of ownership (when the new and old table are swapped) be decorrelated from the implementation of the move (shallow byte copy)? I think the answer is no, not while preserving Sync-correctness in the possible presence of interior mutability. If V contains a Mutex<T> for example, we could be trying to "move" it while another threads is in the middle of writing to it. Clone::clone however receives &self so it’s the impl’s responsibility to acquire that mutex to correctly clone the value while preserving Sync.)

[Amanieu]

An easy way to get rid of the Clone requirement is to just put the values in an Arc. I have some ideas about a different table design based on pointers, but haven't fully figured out all the details yet.

As for insertion when a key already exists, I forgot to mention that part. Essentially, after a successful insertion, you need to perform another scan and delete all equal elements that are "before" the newly inserted one.

[Amanieu]

If we are careful with the memory orderings then we should be able to ensure that a thread performing lookups will never see a "gap" where the item it is looking for is not found.

@Amanieu Interesting, that sounds like a pretty good design.

I wonder, would it makes sense to make resizing lock-free like in Cliff Click's hash table (but maybe not in the first release of the hash table)?

Another concern I have is what if we have a HashMap<String, String>? Then resizing would create clones of all strings, which might be a little expensive. But I suppose then we should use HashMap<Arc<str>, Arc<str>> instead?

Do you have an opinion on adaptive radix trees? The good thing about this tree is that it doesn't need resizing so we could just have Art<String, String> without ever cloning strings.

[Amanieu]

Hmm actually after thinking about it for a bit, my design is broken because it allows 2 concurrent inserts of the same key to create 2 separate entries in the table. So please disregard it.

I think the only way to keep the using the fast SIMD lookups from SwissTable is to use a sharded lock for inserts & deletes, where the shard is selected based on the hash. This also avoids the need for a resize bit in the control bytes.

[SimonSapin]

HashMap<String, String> v.s. HashMap<Arc<str>, Arc<str>> is docs concern, isn’t it?

[Amanieu]

Yes, the tradeoffs would have to be explained in the documentation, since clone is called on table growth.

Suppose we go with cloning keys & values when resizing the table. What do you think the HashMap::get() method should return?

• An Option<EntryGuard<'a, K, V>>?
• Or, a cloned value Option<V>?

[Amanieu]

I was thinking of returning something along the lines of a Option<&'guard (K, V)>. There is no need to copy values out unless absolutely required.

Useful comment with links: crossbeam-rs/crossbeam#41 (comment)

It might be worth looking into https://github.com/efficient/libcuckoo because it's a concurrent hash table with high performance but uses locking here and there and locks the table during resizes. Apart from the "cuckoo" part, it seems very similar to what we're aiming for here.

[schets]

In general, I'm biased towards trie structures for this case since they provide very good performance overall and tend to fare better in many-writer scenarios, whereas hashmaps can have very poor scaling with many writers. The ART paper is especially compelling in this regard given the implementation simplicity.

[maximecaron]

Relativistic hash tables from the linux kernel 1 should be easy to port to Rust but require RCU.
Do you think Crossbeam already have all the RCU support that would be needed ?

This hashtable is great because it does not block reader during table resize, so it give stable low latency access.