Resizable, scalable, concurrent hash tables

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the num-ber of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting read-ers. We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over reader-writer locking, and 56 % over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize. To achieve this performance, this hash table imple-mentation uses a new concurrent programming method-ology known as relativistic programming. In particular, we make use of an existing synchronization primitive which waits for all current readers to finish, with little to no reader overhead; careful use of this primitive allows ordering of updates without read-side synchronization or memory barriers.