Towards an Elastic Lock-Free Hash Trie Design
Miguel Areias and Ricardo Rocha
July 2021
Abstract
A key aspect of any hash map design is the problem of dynamically
resizing it in order to deal with hash collisions. In this context,
elasticity refers to the ability to automatically resize the internal
data structures that support the hash map operations in order to meet
varying workloads, thus optimizing the overall memory consumption of
the hash map. This work extends a previous lock-free hash trie design
to support elastic hashing, i.e., expand saturated hash levels and
compress unused hash levels, such that, at each point in time, the
number of levels in a path matches the current demand as closely as
possible. Experimental results show that elasticity effectively
improves the search operation and, in doing so, our design becomes
very competitive when compared to other state-of-the-art designs
implemented in Java.
Bibtex
@InProceedings{areias-ispdc21,
author = {M. Areias and R. Rocha},
title = {{Towards an Elastic Lock-Free Hash Trie Design}},
booktitle = {Proceedings of the 20th International Symposium on Parallel
and Distributed Computing (ISPDC 2021)},
pages = {9--16},
publisher = {IEEE Computer Society},
editor = {B. Iancu and Ralf-Peter Mundani},
month = {July},
year = {2021},
address = {Cluj-Napoca, Romania (online event)},
}
Download Paper
PDF file
IEEE Computer Society