Relativistic hash tables

Thank you; you just made my day.

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.

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.

> 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.

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.

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.

> 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.

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.

> Can you comment on how one can safely enumerate "all" keys of the hashtable, while minimizing contention.

for each bucket:

Oof, this may take a much longer blog post, but here is the very high level basic view.

The basic construction on one doc-sharded server looks like: 1) Maximum valid local_docid 2) A map of local_docid => state (valid, deleted) 3) A map of token_id (indexed term) => map of local_docids to positions in doc.

On document update, you increment the next local docid. You then rip through the doc and extract the tokens. For each token, you insert the docid,position into map (3). Then you add the document to map (2) with state "valid", and finally increment (1).

On query, you first copy (1), then do the typical AND/OR retrieval over (3). Any docids seen higher than (1) are ignored, and any docs retrieved are then filtered by (2).

In this model, (1) is a volatile memory access. (2) and (3) are very similar to this "relativistic hash map".

Deletions are complicated, and usually you filter out invalid docids from (3) as a background compaction process.

It looks to me like the major thing here is the grace period right? Otherwise you could get "pointer-changing" happy and mess up readers traversing bucket lists right?

This issue arises even in completely single-threaded programs that have hash tables. Suppose you're iterating over a hash, hitting a callback function for each element which has access to the hash and inserts new elements. During the callback, new elements could be inserted which trigger a growth. If you allow the hash table reorganization, then it has to be reconciled with the in-progress traversal, so that it doesn't miss some elements, or visit some elements more than once.

How does the "grace period" work in practice? Is it really a set amount of wall time?

Cuckoo hashing, and other closed-hashing (non-chaining) approaches, don't allow other portions of the system to maintain references to hash nodes. Nodes within hash tables in the Linux kernel often consist of some other data structure with an embedded hlist_node, allowing the data structure to be dropped into a hash bucket.

Non-chaining hash tables make the most sense when you can fit the entire hash nodes directly into the array of buckets; that way, you never dereference a pointer at all. However, when storing larger structures, you typically need to put a pointer into the bucket rather than the structure itself. Once you've done that, you've already introduced an indirection and an extra memory read (or cacheline fetch). With open chaining, if you've sized the hash table to have on average 1 node per bucket, you have that same single indirection going from the bucket to the node, and then the node has all the data, so you don't need another.

Or 0x00000001 next pointers, if it's using a hlist_nulls. See http://lwn.net/Articles/609904/