Towards an Elastic Lock-Free Hash Trie Design

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 =    {Rodica Potolea, Bogdan Iancu and Radu Razvan Slavescu},
  month =     {July},
  year =      {2021},
  address =   {Cluj-Napoca, Romania (online event)},
  doi =       {10.1109/ISPDC52870.2021.9521630},
}

Download Paper

PDF file
IEEE Computer Society