Practical Detectability for Persistent Lock-Free Data Structures
Practical programming framework for persistent lock-free DSs with detectability
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
Evaluaton Results
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.
Queue
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%
Hash Table
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
Publications
- (2022)
Practical Detectability for Persistent Lock-Free Data Structures.
Kyeongmin Cho, Seungmin Jeon, Jeehoon Kang.
Submitted.
[paper] [artifact (Development)] [artifact (Evaluation results)] [project page]