Memento: A Framework for Detectable Recoverability in Persistent Memory
Memento: A Framework for Detectable Recoverability in Persistent Memory
复制标题
DOI：
10.1145/3591232
复制
发表时间：
2023-06
影响因子：
--
通讯作者：
K. Cho;Seungmin Jeon;Azalea Raad;Jeehoon Kang
中科院分区：
文献类型：
--
作者：
K. Cho;Seungmin Jeon;Azalea Raad;Jeehoon Kang
持久内存 (PM) 是一种新兴的存储技术，它将 DRAM 的性能与 SSD 的耐用性结合在一起，提供了两全其美的优点。这导致了对 PM 中持久对象的研究激增。在此类持久对象中，并发数据结构 (DS) 由于其性能和可扩展性而特别令人感兴趣。持久并发 DS 最广泛使用的正确性标准之一是可检测的可恢复性，确保线程安全性（非崩溃并发执行中的正确性）和崩溃一致性（崩溃执行中的正确性）。然而，现有的设计可检测可恢复并发 DS 的方法要么局限于简单的算法，要么遭受高运行时开销。我们提出了 Memento：一个通用的高性能编程框架，用于 PM 中可检测可恢复的并发 DS。为了确保对各种 DS 的普遍适用性，Memento 支持原始操作，例如检查点、比较和交换及其与控制结构的组合。为了确保高性能，Memento 采用基于时间戳的恢复策略，与现有方法相比，该策略需要更少的 PM 写入和刷新。我们正式证明 Memento 可确保在发生崩溃时可检测到的可恢复性。为了展示 Memento，我们实现了一个无锁堆栈、列表、队列和哈希表，以及一个组合队列，该队列可以从压力测试中的随机崩溃中可检测地恢复，并且在具有或不具有可检测的可恢复性的情况下，其性能与现有的手动调整的持久 DS 相当。
Persistent memory (PM) is an emerging class of storage technology that combines the performance of DRAM with the durability of SSD, offering the best of both worlds. This had led to a surge of research on persistent objects in PM. Among such persistent objects, concurrent data structures (DSs) are particularly interesting thanks to their performance and scalability. One of the most widely used correctness criteria for persistent concurrent DSs is detectable recoverability, ensuring both thread safety (for correctness in non-crashing concurrent executions) and crash consistency (for correctness in crashing executions). However, the existing approaches to designing detectably recoverable concurrent DSs are either limited to simple algorithms or suffer from high runtime overheads. We present Memento: a general and high-performance programming framework for detectably recoverable concurrent DSs in PM. To ensure general applicability to various DSs, Memento supports primitive operations such as checkpoint and compare-and-swap and their composition with control constructs. To ensure high performance, Memento employs a timestamp-based recovery strategy that requires fewer writes and flushes to PM than the existing approaches. We formally prove that Memento ensures detectable recoverability in the presence of crashes. To showcase Memento, we implement a lock-free stack, list, queue, and hash table, and a combining queue that detectably recovers from random crashes in stress tests and performs comparably to existing hand-tuned persistent DSs with and without detectable recoverability.