I wrote the paper and dissertation this work was based on, and I'm happy to answer any questions people might have.
(Really awesome to see a production implementation of this.)
(Really awesome to see a production implementation of this.)
I know I said it twice already, but: brilliant.
Reading your dissertation now.
Once you have multiple CPUs, you can't avoid concurrency, and message passing and immutability become common themes. The strategy for many years was to naively add locks to traditional stateful algorithms and mutable data structures, but this often leads to bad performance (and unpredictable performance)
There is an elaborate backward compatible illusion presented by the architecture, C, and most languages built on top of C. Internal busses and caches are not exposed to you as a programmer, but they are there and affect performance. But if you think of your app from the OS perspective rather than the language perspective, the distributed model becomes more clear and natural.
There is a technique for eliminating the long pauses from rebuilding called "incremental global rebuilding". The big idea is that the new structure is built piece-by-piece, taking a few building steps for each update to the existing structure. The new construction is finished before the existing structure fills up (or empties out, for deletes). Depending on the variant, updates may be applied as the new structure is being built, batched to be applied later, or applied in a secondary "ghost" structure.
It has been used in dozens of data structures, and was, I think, made famous by a series of papers by Overmars and co-authors in the early 80s. He wrote a book about related techniques called "The Design of Dynamic Data Structures".
Does this technique not apply to resizing hash tables in a concurrent kernel?
RCU-based algorithms allow readers to proceed with absolutely no locking, compare-and-swap, atomic operations, or other expensive steps. In order to support that, any modification to the data structure (such as a write or resize) must make sure the structure remains in a completely valid state after every individual modification. The hash resize algorithm I wrote provides that feature, ensuring that the resize does not disrupt concurrent readers.
My instinct on reading it is that allowing readers to continue during a resize is a solid improvement, but that any approach based on buckets using linked pointers (open chaining) should be considered "low performance" by definition.
Do you think this approach is enough to make them competitive? Is there a parallel approach that would work for faster hashes that don't chase pointers? Would here be a way to "compact" the hash on resize so that at least the pointers are tightly arranged?
Thanks! LaTeX and TikZ are awesome; I would not have wanted to draw those diagrams in any kind of WYSIWYG diagramming tool.
> My instinct on reading it is that allowing readers to continue during a resize is a solid improvement, but that any approach based on buckets using linked pointers (open chaining) should be considered "low performance" by definition.
See my comment at https://news.ycombinator.com/item?id=8365436 ; for many of the hashes in the Linux kernel, the hash nodes are too large to store directly in the buckets, and other parts of the system need to maintain references to them, so a resize cannot copy them and free the originals. And if you're storing a pointer to a node rather than a node, then you'll have one indirection (with associated memory/cacheline fetch) in each bucket anyway, whether you use a closed (non-chaining) table or an open (chaining) table.
Perhaps copying is slow if the nodes are large. Perhaps one way around this is to have two bucket pointers within each node and swap between them whenever the table is rewritten.
When I first started working on hash table algorithms, years ago, I started out by developing an algorithm to move a single node between buckets because the key changed. My first attempt involved making a copy of the node. That works fine in a standalone hash table, but it won't work in many real kernel data structures (for instance, dcache), because it breaks other pointers to the (reference-counted) node.
That's why the algorithm shown here does not copy any nodes.
As for having two bucket pointers within each node: we've looked at that approach, as have others, but it uses far more memory. If you have a hash table with millions of entries, you don't want to add 8 bytes to every one of them.
Readers traverse the chain using the pointer indexed by the link field.
Resizing rebuilds the chains by storing the new links into the 1-link field. When resizing is done, just set link=1-link. The "only" thing you have to guard against are extremely slow readers, i.e., that the table does not get resized twice while a single reader is traversing some chain.
According to the LWN article, concurrent updates with resizing is generally serialized.
What am I missing...? [ya, filling in the details and formal proof of correctness]
You can even do (atomic) refcounting to make sure that everyone is done using the old chain before resizing, although this may slow things down. (So the hash table contains a field of two integers, which indicate the number of readers currently traversing index 0 and 1. Once the value of the "old" index reaches 0, you know it is safe to resize again.)
And you should be able to extend this to k versions easily, which would mean that (k-2) slow readers won't inhibit resizing.
Although, all of that being said, I don't really see the advantage of this over a coocoo hash table.
Can you comment on how one can safely enumerate "all" keys of the hashtable, while minimizing contention.
It would be great to know whether, in principle, rhashtable can offer such a capability.
for each bucket:
This looks huge for smoothing the latency spikes out of software networking on Linux.
Mostly so, yes. Writers can still contend with each other, but that's less critical on a read-heavy data structure.
would the same principles that apply for chaining, apply for linear probing and cuckoo hashing as well ? thanks !