Persistent memory (PM) is an emerging class of storage technology that combines the benefits of DRAM and SSD. This characteristic inspires research on persistent objects in PM with fine-grained concurrency control. Among such objects, persistent lock-free data structures (DSs) are particularly interesting thanks to their efficiency and scalability. One of the most widely used correctness criteria for persistent lock-free DSs is durable linearizability (Izraelevitz et. al., DISC 2016). However, durable linearizability is insufficient to use persistent DSs for fault-tolerant systems requiring exactly-once semantics for storage systems, because we may not be able to detect whether an operation is performed when a crash occurs.
We present a practical programming framework for persistent lock-free DSs with detectability. In contrast to the prior work on such DSs, our framework supports
- primitive detectable operations such as space-efficient compare-and-swap, insertion, and deletion;
- systematic transformation of lock-free DSs in DRAM into those in PM requiring modest efforts;
- comparable performance with non-detectable DSs by DRAM scratchpad optimization; and
- recovery from both full system and thread crashes.
The key idea is memento objects serving as a lightweight, precise, and per-thread checkpoints in PM. As a case study, we implement lockfree and combining queues and hash tables with detectability that outperform (and perform comparably) the state-of-the-art DSs with (and without, respectively) detectability.
For VLDB 2022 Reviewers
Here is an artifact zip file for your reivew: artifact.zip
We perform a performance evaluation of our programming framework for detectable queues and hash tables in PM. We refer to our paper for detailed discussion about results.
Multi-threaded Throughput of enqueue-dequeue pair
Multi-threaded Throughput of enqueue 20%, dequeue 80%
Multi-threaded Throughput of enqueue 50%, dequeue 50%
Multi-threaded Throughput of enqueue 80%, dequeue 20%
Tail Latency of Hash Tables with 32 Threads
Load factor of Hash Tables
Single-threaded Throughput of Hash Tables
Multi-threaded Throughput of Hash Tables for Self Similar Distribution with Factor 0.2
Multi-threaded Throughput of Hash Tables for Uniform Distribution