Ph.D Thesis

Ph.D StudentKorenberg)Friedman( Michal-Evgenia
SubjectConcurrent Data-Structures for Non-Volatile Memory
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank
Full Thesis textFull thesis text - English Version


Memory and storage are considered major performance bottleneck of almost all computer systems. The role of computer storage, particularly secondary memory such as SSDs or HDDs, has become even more critical with the advance in technology and system design. Fortunately, the emergence of non-volatile main memory (NVMM), which provides persistence, byte-addressability, near-DRAM performance and large capacity, revolutionizes the way we use secondary memory. By using NVMM, data can be read/written directly from memory, without the need of marshaling it into a block-based format, and is crash-resilient at a minimal performance cost. Several challenges still remain, however, since caches and registers remain volatile. Consequently, the most updated application's data may be located in the cache, and is lost upon a crash. Accordingly, data structures must be designed in a way that a recovery procedure will be able to retrieve a consistent memory state following a crash. Concurrent data structures increase the difficulty of the design, as achieving correctness, efficiency, and scalability simultaneously becomes more challenging, and the involvement of experts in concurrency and durability is required.

This dissertation aims at designing efficient, durable and concurrent data structures and algorithms for NVMM. It first presents novel implementations of a concurrent lock-free queue. These implementations illustrate algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. Additionally, we present a new notion of \emph{detectable execution}. A data structure provides detectable execution if it is possible to tell at the end of a recovery phase whether a specific operation was executed. Interestingly, there was no such requirement prior to this work.

Next, we introduce two general techniques for building lock-free data structures, \emph{NVTraverse} and \emph{Mirror}. Presented as NVM libraries, they reduce the programming effort required to add persistence to volatile data structures. Our evaluation shows that these constructions outperform other techniques for designing durable data structures by a large margin. NVTraverse is a general transformation that takes a lock-free data structure from a general class called a \emph{traversal data structure} and automatically transforms it into an implementation of the data structure for the NVMM setting that is provably correct and highly efficient. Mirror is a simple, general automatic transformation that adds durability to any lock-free data structure, with a low performance overhead. Moreover, Mirror exploits the hybrid system to substantially improve performance.

The next contribution in this dissertation is \emph{FliT}, a C library that facilitates writing efficient persistent code. Using the library’s default mode makes any linearizable data structure durable with minimal changes to the code. FliT avoids many redundant flush instructions by using a novel algorithm to track dirty cache lines.

Finally, our last contribution is the development of a general construction that takes any concurrent program and makes it persistent. The converted algorithm has a constant computational delay (preserves instruction counts on each process within a constant factor), as well as a constant recovery delay (a process can recover from a fault in a constant number of instructions).