Lock-Free Memory Reclamation for Concurrent Hash Tries

Paulo Rosa

December 2020

---

Abstract

Data structures are a fundamental programming tool needed to implement programs. They are a key target to ensure concurrency properties and guarantee good performance. Our work is focused on the study of lock-free data structures, in particular the CTries (Concurrent Hash Tries) data structure, and how memory reclamation can be applied without losing the lock-free property. To the best of our knowledge, there are no implementations of CTries outside garbage collector environments. Extending the Ctries design to support lock-free memory reclamation requires adapting the data structure to achieve efficient memory reclamation with well-defined memory bounds. To achieve this goal, we study the state-of-the-art of memory reclamation methods, their advantages and known problems, and how CTries can be adapted to support memory reclamation methods.
Due to the similarities between the CTries and the LFHT data structure, we focused our work on the memory reclamation method used by LFHT, named HHL (Hazard Hash Level). After extending CTries to implement the HHL method, we realized that the HHL method does not guarantee bounded memory usage in this context. To fit our goals, we then adapted HHL in order to achieve a well-defined memory bounded solution. Experimental results show that our solution introduces some overheads, mainly in the insert operation, but it is still very competitive with the current state-of-the-art methods, achieving better results than some of them.

Bibtex

@MastersThesis{rosa-msc,
  author =  {P. Rosa},
  title =   {{Lock-Free Memory Reclamation for Concurrent Hash Tries}},
  school =  {University of Porto},
  address = {Portugal},
  month =   {December},
  year =    {2020},
  type =    {{MSc Thesis}},
}

Download Thesis

PDF file