Persistent memory and the rise of universal constructions

Non-Volatile Main Memory (NVMM) has brought forth the need for data structures that are not only concurrent but also resilient to non-corrupting failures. Until now, persistent transactional memory libraries (PTMs) have focused on providing correct recovery from non-corrupting failures without memory leaks. Most PTMs that provide concurrent access do so with blocking progress.

The main focus of this paper is to design practical PTMs with wait-free progress based on universal constructions. We first present CX-PUC, the first bounded wait-free persistent universal construction requiring no annotation of the underlying sequential data structure. CX-PUC is an adaptation to persistence of CX, a recently proposed universal construction. We next introduce CX-PTM, a PTM that achieves better throughput and supports transactions over multiple data structure instances, at the price of requiring annotation of the loads and stores in the data structure-as is commonplace in software transactional memory. Finally, we propose a new generic construction based on a finite number of replicas and Herlihy's wait-free consensus, which uses physical instead of logical logging. This PTM, which we named Redo-PTM, records all the store instructions executed on each operation and considerably improves throughput for update transactions. These generic constructions enable the creation of wait-free, failure resilient and durable linearizable data structures for NVMM, with integrated wait-free memory allocation and deallocation. By exploiting its capability of providing wait-free ACID transactions, we have used Redo-PTM to implement the world's first persistent key-value store with bounded wait-free progress.