一句话：Memento 是一个面向持久内存并发数据结构的通用高性能框架，用时间戳恢复策略实现可检测可恢复性并给出形式化证明。
持久内存（PM）兼具 DRAM 性能与 SSD 持久性，其上并发数据结构（DS）的可检测可恢复性要求同时满足线程安全与崩溃一致性。现有设计可检测可恢复并发 DS 的方法要么局限于简单算法，要么运行时开销过高。本文提出 Memento：一个通用且高性能的编程框架。为保证通用性，Memento 支持 checkpoint、compare-and-swap 等原语操作及其与控制结构的组合；为保证高性能，它采用基于时间戳的恢复策略，相比已有方法需要更少的 PM 写入与 flush。作者形式化证明了 Memento 在崩溃场景下可保证可检测可恢复性。评估方面，作者用 Memento 实现了无锁栈、链表、队列、哈希表以及 combining queue，在压力测试中可从随机崩溃中可检测地恢复，性能与已有手工调优的持久 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.
@article{paperbot1976,
title = {Memento: A Framework for Detectable Recoverability in Persistent Memory},
author = {Kyeongmin Cho and Seungmin Jeon and Azalea Raad and Jeehoon Kang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {PLDI},
year = {2023},
doi = {10.1145/3591232}
}