Practical Detectability for Persistent Lock-Free Data Structures

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

1. primitive detectable operations such as space-efficient compare-and-swap, insertion, and deletion;
2. systematic transformation of lock-free DSs in DRAM into those in PM requiring modest efforts;
3. comparable performance with non-detectable DSs by DRAM scratchpad optimization; and
4. 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] ​ ​