Name
Abstract | ||
|---|---|---|
We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow Read-Copy Update (RCU) hash tables to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers. We call the resulting data structure a relativistic hash table. Benchmarks of relativistic hash tables in the Linux kernel show that lookup scalability during resize improves 125x over reader-writer locking, and 56% over Linux's current state of the art. Relativistic hash lookups experience no performance degradation during a resize. Applying this algorithm to memcached removes a scalability limit for get requests, allowing memcached to scale linearly and service up to 46% more requests per second. Relativistic hash tables demonstrate the promise of a new concurrent programming methodology known as relativistic programming. Relativistic programming makes novel use of existing RCU synchronization primitives, namely the wait-for-readers operation that waits for unfinished readers to complete. This operation, conventionally used to handle reclamation, here allows ordering of updates without read-side synchronization or memory barriers. |
Year | Venue | Keywords |
|---|---|---|
2011 | USENIX Annual Technical Conference | constant-time performance,rcu synchronization primitive,entries decrease,resize algorithm,hash table,linux kernel show,relativistic hash lookups,relativistic hash table,relativistic programming,concurrent hash table,new concurrent programming methodology,high performance computing |
Field | DocType | Citations |
Data structure,Hash tree,Double hashing,Computer science,Parallel computing,Relativistic programming,Hash function,Hash list,Linux kernel,Hash table | Conference | 32 |
PageRank | References | Authors |
1.46 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josh Triplett | 1 | 64 | 3.05 |
| Paul E. McKenney | 2 | 279 | 30.11 |
| Jonathan Walpole | 3 | 1122 | 137.35 |