Fast Nonblocking Persistence for Concurrent Data Structures
Fast Nonblocking Persistence for Concurrent Data Structures
复制标题
DOI：
10.4230/lipics.disc.2021.14
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Wentao Cai;Haosen Wen;Vladimir Maksimovski;Mingzhe Du;Rafaello Sanna;Shreif Abdallah;M. Scott
中科院分区：
文献类型：
--
作者：
Wentao Cai;Haosen Wen;Vladimir Maksimovski;Mingzhe Du;Rafaello Sanna;Shreif Abdallah;M. Scott
我们为持久化数据结构提出了最新的蒙太奇系统的一个完全无锁的变体。我们的变体nbMonage为几乎任何非阻塞并发结构添加了持久性，而不会引入显著的开销或任何类型的阻塞。像它的前身一样，nbMonage是可持久线性化的缓冲：它保证在崩溃后恢复的状态将表示崩溃前执行的一致前缀。与它的前身不同，nbMonage确保持久性边界的无等待进程，从而限制在崩溃时可能丢失的最新更新的数量，并允许线程强制更新边界(即执行同步操作)，而不会有阻塞的风险。作为一个额外的好处，我们的免等待同步所采用的帮助机制显著减少了它的延迟。非阻塞队列、跳过列表、树和哈希表的性能结果可与文献中的定制数据结构相媲美--大大快于以前的通用系统，并且通常在放置在DRAM中的等效非持久结构的50%以内。
We present a fully lock-free variant of the recent Montage system for persistent data structures. Our variant, nbMontage, adds persistence to almost any nonblocking concurrent structure without introducing significant overhead or blocking of any kind. Like its predecessor, nbMontage is buffered durably linearizable: it guarantees that the state recovered in the wake of a crash will represent a consistent prefix of pre-crash execution. Unlike its predecessor, nbMontage ensures wait-free progress of the persistence frontier, thereby bounding the number of recent updates that may be lost on a crash, and allowing a thread to force an update of the frontier (i.e., to perform a sync operation) without the risk of blocking. As an extra benefit, the helping mechanism employed by our wait-free sync significantly reduces its latency. Performance results for nonblocking queues, skip lists, trees, and hash tables rival custom data structures in the literature -- dramatically faster than achieved with prior general-purpose systems, and generally within 50% of equivalent non-persistent structures placed in DRAM.