טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZuriel Yoav
SubjectEfficient Lock-Free Durable Sets
DepartmentDepartment of Computer Science
Supervisors Professor Erez Petrank
Dr. Nachson Cohen
Full Thesis textFull thesis text - English Version


Abstract

Recently Intel released a new hardware component, Non-volatile memory, promising comparable access latencies to the traditional DRAM while making the data written on it persistent, resilient to power outages. As a result, non-volatile memory is expected to co-exist or even replace DRAM in upcoming architectures. Durable concurrent data structures for non-volatile memories are essential building blocks for constructing adequate software for use with these architectures.


In this paper, we propose a new approach for durable concurrent sets. Using this approach we design two novel techniques to create durable linearizable data structures.

We use these techniques to build three different kinds of sets from existing lock-free sets: linked list, hash map, and skip list. Our techniques yield the most efficient durable hash tables available today.


We ran three different tests on a 64-core AMD platform to obtain a better understanding of the different sets: scalability test, key range test, and workload test. The evaluation shows a performance improvement factor of 3.3x over the existing state-of-the-art hash map with 32 concurrent threads. To go with the new durable data structures, we extend an existing memory manager to work with persistent memory.

The correctness of concurrent data structures is not trivial and thus a full correctness proof is provided for both lists proving durable linearizability and lock-freedom.