Transactional Composition of Nonblocking Data Structures
Transactional Composition of Nonblocking Data Structures
复制标题
DOI：
10.1145/3558481.3591079
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Wentao Cai;Haosen Wen;M. Scott
中科院分区：
文献类型：
--
作者：
Wentao Cai;Haosen Wen;M. Scott
本文介绍了非阻塞事务组合（NBTC），这是一种对并发数据结构进行非阻塞操作原子组合的新方法。与以前的软件事务内存 (STM) 方法不同，NBTC 利用现有非阻塞结构的线性化能力，将必须以原子方式一起执行的内存访问数量减少到大多数情况下每个操作仅一次（这些通常是组成操作的线性化指令）。我们对 NBTC（我们称之为 Medley）的无阻碍实施使得可以轻松地将大多数非阻塞数据结构转换为事务性数据结构，同时保持其活跃性和高并发性。在我们的实验中，Medley 的性能比之前最快的竞争方法无锁事务转换 (LFTT) 高出 40--170%。相对于连续执行的单独操作，Medley 的事务组合的边际开销约为 2.2 倍。对于持久性数据结构，我们观察到，通过基于纪元的周期性持久性，可以“几乎免费”实现事务的失败原子性。为此，我们将 Medley 与 nbMontage（用于周期性持久性数据结构的通用系统）集成。生成的 txMontage 提供 ACID 事务，并实现比 OneFile 持久性 STM 系统高两个数量级的吞吐量。
This paper introduces nonblocking transaction composition (NBTC), a new methodology for atomic composition of nonblocking operations on concurrent data structures. Unlike previous software transactional memory (STM) approaches, NBTC leverages the linearizability of existing nonblocking structures, reducing the number of memory accesses that must be executed together, atomically, to only one per operation in most cases (these are typically the linearizing instructions of the constituent operations). Our obstruction-free implementation of NBTC, which we call Medley, makes it easy to transform most nonblocking data structures into transactional counterparts while preserving their liveness and high concurrency. In our experiments, Medley outperforms Lock-Free Transactional Transform (LFTT), the fastest prior competing methodology, by 40--170%. The marginal overhead of Medley's transactional composition, relative to separate operations performed in succession, is roughly 2.2x. For persistent data structures, we observe that failure atomicity for transactions can be achieved "almost for free'' with epoch-based periodic persistence. Toward that end, we integrate Medley with nbMontage, a general system for periodically persistent data structures. The resulting txMontage provides ACID transactions and achieves throughput up to two orders of magnitude higher than that of the OneFile persistent STM system.