Towards a Lock-Free, Fixed Size and Persistent Hash Map Design
Miguel Areias and Ricardo Rocha
October 2017
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
concurrent hash map design 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. Experimental results show
that our proposal is quite competitive when compared against other
state-of-the-art proposals implemented in Java. Its design is modular
enough to allow different types of configurations aimed for different
performances in memory usage and execution time.
Bibtex
@InProceedings{areias-sbacpad17,
author = {M. Areias and R. Rocha},
title = {{Towards a Lock-Free, Fixed Size and Persistent Hash Map Design}},
booktitle = {Proceedings of the International Symposium on Computer Architecture and
High Performance Computing (SBAC-PAD 2017)},
pages = {145--152},
publisher = {IEEE Computer Society},
editor = {M. Valero and A. Melo},
month = {October},
year = {2017},
address = {Campinas, Brazil},
}
Download Paper
PDF file
IEEE Computer Society