%0 Conference Paper %1 Triplett:2011:RSC:2002181.2002192 %A Triplett, Josh %A McKenney, Paul E. %A Walpole, Jonathan %B Proceedings of the 2011 USENIX conference on USENIX annual technical conference %C Berkeley, CA, USA %D 2011 %I USENIX Association %K hash non-deterministic relativistic table %P 11 %T Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming %U http://dl.acm.org/citation.cfm?id=2002181.2002192 %X 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.</p> <p>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.</p> <p>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.

@inproceedings{Triplett:2011:RSC:2002181.2002192, 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.</p> <p>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.</p> <p>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.}, acmid = {2002192}, added-at = {2012-01-23T15:32:09.000+0100}, address = {Berkeley, CA, USA}, author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}, biburl = {https://www.bibsonomy.org/bibtex/22901f41af59c26c028beab65c179d593/gron}, booktitle = {Proceedings of the 2011 USENIX conference on USENIX annual technical conference}, description = {Resizable, scalable, concurrent hash tables via relativistic programming}, interhash = {e3865bed6dcb48bdc77e154a1efb39f6}, intrahash = {2901f41af59c26c028beab65c179d593}, keywords = {hash non-deterministic relativistic table}, location = {Portland, OR}, numpages = {1}, pages = 11, publisher = {USENIX Association}, series = {USENIXATC'11}, timestamp = {2012-01-30T17:55:32.000+0100}, title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}, url = {http://dl.acm.org/citation.cfm?id=2002181.2002192}, year = 2011 }