On the Correctness and Efficiency of a Novel Lock-Free Hash Trie Map Design
Miguel Areias and Ricardo Rocha
2021
Abstract
Hash tries are a trie-based data structure with nearly ideal
characteristics for the implementation of hash maps. In this paper, we
present a novel, simple and scalable hash trie map design that fully
supports the concurrent search, insert and remove operations on hash
maps. To the best of our knowledge, our proposal is the first that
puts together the following characteristics: (i) be lock-free; (ii)
use fixed size data structures; and (iii) maintain the access to all
internal data structures as persistent memory references. Our design
is modular enough to allow different types of configurations aimed for
different performances in memory usage and execution time and can be
easily implemented in any type of language, library or within other
complex data structures. We discuss in detail the key algorithms
required to easily reproduce our implementation by others and we
present a proof of correctness showing that our proposal is
linearizable and lock-free for the search, insert and remove
operations. Experimental results show that our proposal is quite
competitive when compared against other state-of-the-art proposals
implemented in Java.
Bibtex
@Article{areias-jpdc21,
author = {M. Areias and R. Rocha},
title = {{On the Correctness and Efficiency of a Novel Lock-Free Hash Trie Map Design}},
journal = {Journal of Parallel and Distributed Computing},
pages = {184--195},
volume = {150},
month = {April},
year = {2021},
}
Download Paper
PDF file
Elsevier