2022/03/15 by Kyeongmin Cho, Cho, Kyeongmin, Seun Jeon +3
Computer Science · #Advanced Data Storage Technologies #D.1.3 #D.3.3 #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #E.1 #FOS: Computer and information sciences #Parallel #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2203.07621
openalex publication_date 2022/03/15 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
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 lock-free and combining queues and hash tables with detectability that outperform (and perform comparably) the state-of-the-art DSs with (and without, respectively) detectability.