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.2$\times$. 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.
翻译:本文介绍了非阻塞交易构成(NBTC),这是在并行数据结构上非阻塞操作的原子构成的新方法。与以往的软件交易存储(STM)方法不同,NBTC利用了现有非阻塞结构的线性可扩展性,将大多数情况下必须一起执行的存储存取数量从原子上减少到每个操作仅一个(通常是各组成部分业务的线性指令)。我们称之为Medley的无阻碍实施NBTC,使我们很容易将大多数非阻塞数据结构转化为交易对应机构,同时保持其活力和高通货率。在我们实验中,Medley超越了以前最快的竞争方法-无锁交易变形(LFTT),增加了40-170 % 。Medley的交易构成的边际间接,相对于在连续运行中进行的不同操作,约为2.2美元/美元。关于持续的数据结构,我们发现交易的失败原子性可以“最免费”实现,同时保持其活力和高调。为此,我们把Medley与NbMetile和NbMontage(LT)系统整合了一个不固定的高级系统。