Memory Reclamation Methods for Lock-Free Hash Tries

Pedro Moreno

December 2018

---

Abstract

Data structures are a fundamental programming tool required by almost any program or algorithm. As such, data structures are a key target to ensure that some concurrency properties are inherited by the programs that use them. These properties range from scalability and progress guarantees to memory overheads and bounds.
In this thesis, we focus on studying a particular lock-free data structure, named Lock-Free Hash Tries, and on solving the problem of memory reclamation without loosing the lock-freedom property. To the best of our knowledge, outside garbage collected environments, there is no current implementation of hash maps that is both lock-free and able to reclaim memory. To achieve this goal, we review the current state-of-the-art memory reclamation methods for lock-free data structures and we go over the possibility of making Lock-Free Hash Tries compatible with such memory reclamation methods. We found such a task unfeasible to be done correctly without compromising performance. We thus propose an alternative approach for memory reclamation specific to Lock-Free Hash Tries that explores the characteristics of its structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. This new memory reclamation method makes Lock-Free Hash Tries the first completely lock-free hash map implementation that works in a non garbage collected environment.
Experimental results show that our approach attains better results than the tested state-of- the-art memory reclamation methods and also provides a competitive and scalable thread safe hash map implementation, if compared to lock based implementations.

Bibtex

@MastersThesis{moreno-msc,
  author =  {P. Moreno},
  title =   {{Memory Reclamation Methods for Lock-Free Hash Tries}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {December},
  year =    {2018},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file