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

  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

queue-legend1 queue-legend2

Multi-threaded Throughput of enqueue-dequeue pair

queue-throughput-pair

Multi-threaded Throughput of enqueue 20%, dequeue 80%

queue-throughput-prob20

Multi-threaded Throughput of enqueue 50%, dequeue 50%

queue-throughput-prob50

Multi-threaded Throughput of enqueue 80%, dequeue 20%

queue-throughput-prob80

Hash Table

hash-legend1 hash-legend2

Tail Latency of Hash Tables with 32 Threads

hash-latency

Load factor of Hash Tables

hash-loadfactor

Single-threaded Throughput of Hash Tables

hash-single

Multi-threaded Throughput of Hash Tables for Self Similar Distribution with Factor 0.2

hash-self1 hash-self2

Multi-threaded Throughput of Hash Tables for Uniform Distribution

hash-uniform1 hash-uniform2

Publications