Name
Abstract | ||
|---|---|---|
This paper presents a novel concurrent hash table implementation which supports wait-free, near-linearly scalable lookup, even in the presence of concurrent modifications. In particular, this hash table implementation supports concurrent moves of hash table elements between buckets, for purposes such as renames. Implementation of this algorithm in the Linux kernel demonstrates its performance and scalability. Benchmarks on a 64-way POWER system showed a 6x scalability improvement versus fine-grained locking, and a 1.5x improvement versus the current state of the art in Linux. To achieve these scalability improvements, the hash table implementation uses a new concurrent programming technique known as relativistic programming. This approach uses a copy-based update strategy to allow readers and writers to run concurrently without conflicts, avoiding many of the non-scalable costs of synchronization, inter-processor communication, and cache coherence. New techniques such as the proposed hash-table move algorithm allow readers to tolerate the resulting weak memory-ordering behavior that arises from allowing one version of a structure to be read concurrently with updates to a different version of the same structure. Relativistic programming techniques provide performance and scalability advantages over traditional synchronization, as demonstrated through several benchmarks. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1842733.1842750 | Operating Systems Review |
Keywords | Field | DocType |
scalability advantage,novel concurrent hash table,new concurrent programming technique,concurrent move,scalability improvement,relativistic programming,concurrent modification,scalable concurrent hash table,relativistic programming technique,hash table element,hash table implementation,hash table,cache coherence,power system | SHA-2,Hopscotch hashing,Double hashing,Computer science,Parallel computing,HAT-trie,Real-time computing,Relativistic programming,Hash function,Dynamic perfect hashing,Hash table | Journal |
Volume | Issue | Citations |
44 | 3 | 21 |
PageRank | References | Authors |
1.02 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josh Triplett | 1 | 64 | 3.05 |
| Paul E. McKenney | 2 | 279 | 30.11 |
| Jonathan Walpole | 3 | 1122 | 137.35 |