The application of a causally consistent model for hash table operations is brilliant; treating CPUs and memory as a "traditional" distributed system is brilliant.
I basically think of a single computer as a distributed system now. In other words, it's not a Turing machine / state machine any more; it's a network of such things.
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.
Great; thanks for volunteering to answer questions! I'm still reading your paper; please excuse me if this is covered.
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?
A large part of the overhead of concurrent data structures lies not in the work itself, but in the synchronization used to avoid corruption to the data structure. The technique you're describing could potentially allow a resize to occur incrementally, without blocking other operations for a long time, but that doesn't take away the need to synchronize between resize, write, and read operations.
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.
Are you aware of any way that the work of Overmars et al. fails to meet the criterion "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"?
Nice algorithm. The diagrams in the paper are wonderfully clear and useful.
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?
> Nice algorithm. The diagrams in the paper are wonderfully clear and useful.
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.
How did this compare against Hash Array Mapped Tries? It looks like the amount of nodes that you'd need to change would be smaller, and updates are less dramatic. (They're common in functional programming for persistent data structures, and you get almost as good performance as a hash table with a really wide trie)
The table expansion operation seems complex. Is it really faster than just rebuilding the hash table (by concurrently reading it), switching to the new hash table, then deleting the old table (use RCU to determine when it's safe to delete)?
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.
In addition to the overhead of copying all the elements, you'd break any code that holds references to those elements. In quite a few hash tables in the kernel, other code holds long-running references to hash nodes and expects them to stay alive.
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.
What's wrong with the following much simpler construction: each node contains an array of TWO links, and the hash table itself contains an "int link" field.
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]
Looking at that quickly, I don't see a problem - that should work. Although you're doubling the size of the hash table itself.
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.
That works, and has been tested, but would drastically increase memory usage. And you still need a way to track those readers still looking at the previous version, which you'd probably still want to use RCU for.
I skimmed through the LWN article and it appears to oversimplify the situation implying that bucket lists are singly-linked. They aren't (or at least they weren't in kernel's hlist few years ago), there's also a back pointer and I'm not really sure how this fits in, i.e. one can't simply re-link tail of one bucket to the head of another when merging them... In other words it seems like LWN got the whole thing dumbed down significantly, no?
Readers don't look at the prev pointers, only the next pointers, so the writers can safely change prev pointers concurrently without worrying about readers.
It looks from the article that this results in bounded-time concurrent reads and writes, even in the worst case, as long as resizes can complete often enough to not be overwhelmed by the writers, is that correct?
This looks huge for smoothing the latency spikes out of software networking on Linux.
> It looks from the article that this results in bounded-time concurrent reads and writes, even in the worst case, as long as resizes can complete often enough to not be overwhelmed by the writers, is that correct?
Mostly so, yes. Writers can still contend with each other, but that's less critical on a read-heavy data structure.
(Really awesome to see a production implementation of this.)