
arXiv: 2203.07621
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.
FOS: Computer and information sciences, D.1.3, Computer Science - Programming Languages, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, D.3.3, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), E.1, D.3.3; E.1; D.1.3, Programming Languages (cs.PL)
FOS: Computer and information sciences, D.1.3, Computer Science - Programming Languages, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Data Structures and Algorithms, D.3.3, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), E.1, D.3.3; E.1; D.1.3, Programming Languages (cs.PL)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
