Research On Adaptive Nonblocking Hash Tables

Hash table is a practical data structure,with constant time access efficiency.Closed address hash tables use bucket to handle hash conflicts.Operations on different buckets are independent,which suggests an inherent parallelism.The design of concurrent hash table is an important research topic.The traverse of buckets increases the time overhead of hash table.The concurrent resize of hash table also put forward higher requirements for correctness.Adaptive buckets can dynamically adjust the order of the elements in a bucket according to the sequence of requests,thereby improving their access efficiency on non-uniform data.Therefore,the thesis studies adaptive nonblocking hash tables.It improves the implementation of bucket so that hash tables can benefit from the locality of real-life data.The contributions of this paper are summarized as follows.Firstly,based on existing lock-free hash tables,an adaptive lock-free hash table is implemented.The idea is to implement the bucket as a lock-free Move-To-Front linked list.The main challenge is to implement the linked list as a freezeable set,and design split and merge operations to coordinate between the concurrent resize of hash table and operations of linked-list.Secondly,a speedup variation of the adaptive lock-free hash table is implemented.The idea is to avoid some list updates by reading several nodes in advance and tries to find the result from them.Finally,a wait-free version of the lock-free adaptive hash table is implemented.The main challenge is that the waitfreedom of bucket cannot guarantee the wait-freedom of a hash table.The solution is to give priorities for threads and use a help mechanism to ensure that each operation can be completed within a limited number of steps.Experiments show that the new adaptive nonblocking hash tables is comparable to the existing nonblocking hash tables on throughput.It also performs well on scalability with the increase of the number of thread.