DHash: Dynamic Hash Tables With Non-Blocking Regular Operations

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 DHash , a type of hash table for shared memory systems, that can change its hash function and rebuild the has...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2022-12, Vol.33 (12), p.3274-3290
Main Authors: Wang, Junchang, Liu, Dunwei, Fu, Xiong, Xiao, Fu, Tian, Chen
Format: Article
Language:English
Subjects:
Algorithms
Buckets
Concurrency
Concurrent programming
dynamic hash tables
Hash based algorithms
Hash functions
Heuristic algorithms
Kernel
Linux
Locking
parallelism and concurrency
Rebuilding
Response time
Robustness
Synchronization
Time factors
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 DHash , 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 DHash 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 DHash independent of the implementation of hash table buckets, such that DHash 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 DHash can efficiently change its hash function on the fly. Moreover, when rebuilding, DHash 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.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2022.3151499