DHash: Dynamic Hash Tables With Non-Blocking Regular Operations

Junchang Wang, Dunwei Liu, Xiong Fu, Fu Xiao, Chen Tian

Abstract

Once started, existing hash tables cannot change their pre-defined hash functions, even if the incoming data cannot be evenly distributed to the hash table buckets. In this paper, we present <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> , a type of hash table for shared memory systems, that can change its hash function and rebuild the hash table on the fly, without noticeably degrading its service. The major technical novelty of <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> stems from an efficient distributing mechanism that can atomically distribute every node when rebuilding, without locking the corresponding hash table buckets. This not only enables non-blocking lookup, insert, and delete operations, but more importantly, makes <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> independent of the implementation of hash table buckets, such that <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> allows programmers to select the set algorithms that meet their requirements best from a variety of existing lock-free and wait-free set algorithms. Evaluations show that <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> can efficiently change its hash function on the fly. Moreover, when rebuilding, <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DHash</small> consistently outperforms the state-of-the-art hash tables in terms of throughput and response time of concurrent operations, at different concurrency levels, and with different operation mixes and average load factors.
BibTeX
@article{wang2022dhash,
  author = {Junchang Wang and Dunwei Liu and Xiong Fu and Fu Xiao and Chen Tian},
  title = {{DHash: Dynamic Hash Tables With Non-Blocking Regular Operations}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2022},
  url = {https://openreview.net/forum?id=ol6qhuNW61L},
}

Loading related content...

Figure