The Taub Faculty of Computer Science Events and Talks

Recent non-volatile main memory technology (such as Intel’s Optane) gave rise to an abundance of research on building persistent data structures, whose content can be recovered after a system crash. While there has been significant progress in making durable data structures efficient, shortening the length of the recovery phase after a crash (in which data cannot be accessed) has not received much attention. In fact, programmers need to choose exclusively between durable data structures that provide high performance during normal (failure-free) execution and durable data structures that provide fast recovery from crashes. In this paper we present the RELAX general transformation. RELAX generates durable data structures that provide the best of both worlds. They provide high performance with almost zero recovery time, with an overhead that quickly descends following a crash event, until the program soon regains maximal performance. We implemented RELAX on a hash table, a skip list, a binary tree, a linked list, and an array. The evaluation shows that the generated data structures are fast, and that following a crash, even large data sets with hundreds of millions of nodes become responsive within a few milliseconds, whereas other efficient constructions require more than 10 seconds of unresponsive recovery time.