非阻塞事务组合的并发数据结构

441××非阻塞数据结构的事务处理组合蔡文涛wcai6@cs.rochester.edu美国罗切斯特大学计算机科学系摘要WenHaosenhwen5@cs.rochester.com罗彻斯特大学计算机科学系美国1背景Michael L.Scottscott@cs.rochester.com罗切斯特大学计算机科学系美国纽约州罗切斯特我们介绍了非阻塞事务组合（NBTC），一种新的方法，原子组合的非阻塞操作并发数据结构。与以前的软件事务存储器（STM）方法不同，NBTC利用现有非阻塞结构的线性化能力，将必须一起执行的存储器访问的数量减少到原子地，在大多数情况下每个操作只有一个（这些通常是组成操作的线性化指令）。我们的NBTC的无障碍实现，我们称之为Medley，可以很容易地将大多数非阻塞数据结构转换为事务对应物，同时保持其非阻塞活性和高并发性。在我们的实验中，Medley优于Lock-Free TransmittanceTransform（LFTT），这是最快的先前竞争方法，达到40- 170%。相对于连续执行的单独操作，Medley的transsac- tional组成的边际开销约 为2 . 2 。对于持久内存，我们观察到，故障原子性的事务可以实现 为此，我们将混合泳与nbMontage，一个通用的系统，定期持久的数据结构。由此产生的txMontage提供了ACID事务，并实现了比OneFile持久STM系统高两个数量级的吞吐量。CCS概念：·计算方法学→并行算法;·计算理论→并行计算模型;·硬件→非易失性存储器。关键词：非阻塞数据结构，事务，持久内存允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。本作品的第三方组件的版权必须得到尊重。对于所有其他用途，请联系所有者/作者。PPoPP许多多线程系统需要将操作组成以全有或全无的方式发生的事务（即，原子地）。一个潜在的解决方案可以在软件事务存储器（STM）系统中找到，该系统检测和跟踪每个存储器访问，并将几乎任意的顺序代码转换为推测性事务。 几个STM系统提供非阻塞进程[4，7，9，10，16]。STM编程模型是有吸引力的，但它的扩展通常会对事务操作造成3-9.2.3]。Spiegelman等人基于锁的事务数据结构库（TDSL）[15]通过将STM定制为特定数据来减少开销-例如， 将读取集大小减小到仅其更新可能指示语义冲突的关键节点上的那些读取集大小。在与TDSL同时进行的工作中，Zhang et al.[18]提出了无锁transmittance Transform（LFTT），一种静态组成非阻塞操作的非阻塞方法，基于只有关键节点在冲突管理中起 作 用 的 观 察 。 随 后 ， LaBorde et al.s 动 态 事 务 转 换（DTT）[8]将LFTT推广到动态事务（指定为lambda表达式）。LFTT和DTT利用了现有的非阻塞数据结构的并发性.不幸的是，识别关键节点的需要往往将它们限制在表示集合和映射的数据结构中。 DTT的发布和帮助机制还要求操作之间的“粘合”代码完全可重入（通过帮助线程允许并发执行[ 8 ]），并且在冲突出现时可能导致冗余工作。更糟糕的是，对于读取繁重的工作负载，LFTT和DTT要求读取器对写入器可见，从而引入元数据更新，这会显著增加缓存一致性协议中的争用。2我们的贡献我们介绍了非阻塞事务组合（NBTC），一种新的方法，可以创建各种各样的非阻塞数据结构的事务版本，同时保持非阻塞的进展，并产生显着低于传统STM的开销。具体来说，NBTC©2023版权归所有者/作者所有。ACM ISBN 979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577503这项工作得到了NSF资助CCF-1717712、CNS-1900803和CNS-1955498的部分支持。完整版本可在arXiv上找到 [2]。442×PPoPP斯科特可以组成任何非阻塞数据结构，其中每个操作具有可立即识别的线性化点，即：1. 静态地，我们可以识别可能用作操作的线性化点的每个指令这样的指令必须是用于只读操作的加载或用于更新操作的比较和交换（CAS）;2. 动态地，在执行潜在的线性化输入之后，我们可以确定它是否真的是106105104线程01020304050607080(a) get：insert：remove 0：1：101020304050607080(b) 获取：插入：删除18：1：1线性化点一个线性化负载必须确定，米明操作返回之前，一个线性化CAS必须确定，而不执行任何额外的共享内存访问。人们普遍认为，大多数非阻塞操作包括一个执行计划阶段并不保证操作成功;如果需要，任何线程都可以执行清理NBTC背后的直觉是，在已经非阻塞的结构中，只有关键的内存访问-在大多数情况下，线性加载和比较交换（CAS）指令-需要原子地发生，而计划可以在事务遇到它安全地执行，清理可以推迟到事务提交之后我们对现有数据结构和组合模式的调查揭示了这种直觉的两个主要复杂性第一个复杂性涉及到一个并行点的概念，在这个点上，一个操作可能对其他线程可见，但还没有线性化。 因为发布可能会改变其他线程的行为，所以在整个事务提交之前，它必须保持推测性。 在Natarajan和Mittal的二叉搜索树中可以看到一个例子[11]。第二个复杂情况是，一个事务执行了两个或多个操作，其中一个后续操作（称之为事务2）观察到一个先前操作（称之为事务1）的推测CAS 在这里，线程执行 必须像1已经完成一样继续。如果BTC1需要清理（NBTC通常会延迟到事务提交之后���% 2可能需要推测性地帮助���% 1，然后% ���2才能继续。同时，其他交易不应该知道���1的存在。这两种复杂的情况都可以通过引入推测间隔的概念来处理，在推测间隔中，CAS指令必须一起完成，操作才能作为事务的一部分这类似于规范化非阻塞数据结构中的CAS执行器阶段[ 17 ]，但不相同，主要是由于第二个复杂性。通过将关键指令定义为推测间隔中的CAS，加上只读操作的线性化负载，NBTC方法如下：为了在NBTC可组合数据结构上原子地执行一组操作，我们变换每个操作，使得（1）推测间隔之前的非关键图1.事务性跳过列表的输出（日志 轴）。当事务遇到推测间隔中的指令时，在运行中执行它们;（2）以推测方式执行关键指令，因此它们将仅在事务提交时原子地生效;以及（3）推测间隔之后的指令被推迟直到提交之后。为了说明NBTC，我们编写了一个系统Medley，(1) 仪器的关键指令，执行他们speculatively，并提交他们原子使用M-compare-N-swap，我们的变体的多字CAS的哈里斯等人。[6];(2) 识别并积极解决交易冲突;以及(3) 将非关键清除延迟到事务提交。图1报告了在一个总共有80个超线程的服务器上执行的我们测量的瞬态系统（实线）包括我们的Medley，OneFile 瞬 态 STM [13] ， TDSL [15] 和 LFTT [18] 。Medley的性能优于OneFile和TDSL的一个数量级，LFTT的40- 170%。考虑到我们的不可见读取器，当工作负载具有较高的写入百分比时，Medley和LFTT之间的差距会更大。对于持久内存，我们观察到事务的失败原子性与基于epoch的周期性持久性无关[12]：如果同一事务的操作总是发生在同一epoch中，那么它们将在崩溃后在此观察的基础上，我们将Medley与nbMontage[1]（我们基于纪元的非阻塞周期性持久性系统）合并，以创建tx- Montage。给定事务中的所有操作都标记有相同的epoch编号，然后在提交时与其余的读取集一起进行验证，以确保事务在此epoch中提交。图1中的持久系统（虚线）代表我们的txMontage和OneFile 持 久 STM （ POne-File ） [13] 。 虽 然 英 特 尔Optane非易 失性 存 储 器 上的TxMontage的性 能接近DRAM上的Medley，但永久OneFile比其瞬态版本慢大约10-比TxMontage慢两个数量级我们已经使用Medley和txMontage转换了各种数据结构，并在Medley，txMontage和其他兼容的竞争对手上运行TPC-C [ 3 ]事务处理基准进行了实验。 结果（在arXiv [2]的完整版本中报告）再次证实了我们系统的卓越性能。Medley OneFile TDSLTxMontage POneFile LFTTMedley OneFile TDSLTxMontage POneFile LFTT吞吐量（txn/s）443海报：非阻塞数据结构的transmittance composition PPoPP引用[1] 蔡文涛，温浩森，弗拉基米尔·马克西莫夫斯基，杜明哲，拉斐尔·桑纳，什赖夫·阿卜杜拉和迈克尔·L。Scott. 2021年并发数据结构的快速非阻塞持久化。 在35th Intl. Symp. 分布式计算（DISC）德国弗莱堡，14：1[2] 蔡文涛，温浩森，迈克尔L。Scott. 2023年非阻塞数据结构的transmittance组合。arXiv预印本arXiv：2301.00996。[3] 交易处理委员会。2010年。 TPC-C基准测试（修订版5.11.0）。http://www.tpc.org/tpcc/。[4] 凯尔·弗雷泽2003年。实用锁自由。博士D. 论文。大学国王剑桥大学作 为 大 学 出 版 剑 桥 计 算 机 实 验 室 技 术 报 告 #579 ， 2004 年 2 月www.cl.cam. ac.uk/techreports/UCAM-CL-TR-579.pdf。[5] 作者：Michael Friedman，Naama Ben-David，Yuanhao Wei，Guy E.Blelloch和Erez Petrank2020年。NVTraverse：在NVRAM数据结构中，目的地比旅程更重要。第41届ACM编程语言设计与实现 大 会 （ 41st ACM Conf. on Programming Language Design andImplementation，PLDI）虚拟会议，377-392.[6] 蒂莫西湖Harris，Keir Fraser，and Ian A.普拉特2002年。一种实用的多字比较交换操作。在16th Intl. Symp.分布式计算（DISC）图卢兹，法国，265[7] Maurice Herlihy ， Victor Luchangco ， Mark Moir ， and WilliamN.Scherer三. 2003.用于动态大小数据结构的软件事务存储器。 第22届ACMSymp. 分布式计算原理（PODC）Boston，MA，92[8] Pierre LaBorde，Lance Dechoff，Christina Peterson，Deli Zhang和Damian Dechev。2019年。链接数据结构的无等待动态事务。 在第10国际机场。多核和众核编程模型和应用研讨会（PMAM）。 华盛顿特区，41-50。[9] 维伦德拉·贾扬特·马奎斯和马克·莫伊尔。2008年迈向高性能无阻塞软件事务存储器。第13届ACMSIGPLAN Symp. 并行程序设计原理与实践（PPoPP）。盐湖城，UT，227[10] 维兰德拉·J迈克尔·马歇尔放大图片创作者：MichaelM. Scherer III和Michael L.Scott. 2006. 降 低 软 件 传 输 内 存 的 开 销 第 一 届 ACMSIGPLAN跨平台计算研讨会（transmitting Computing，TRANSACT）加拿大渥太华，11页。[11] Aravind Natarajan和Neeraj Mittal 2014.快速并行无锁二叉查找树。第19届ACM SIGPLAN Symp. 并行程序设计原理与实践（PPoPP）奥兰多，佛罗里达州，317[12] 放 大 图 片 创 作 者 ： Joseph Izraelevitz ， Terence Kelly ， Charles B.Morrey III，Dhruva R.Chakrabarti和Michael L.Scott. 2017年。Dalí：A Periodically Persistent Hash Map. 在31st Intl. Symp. 分布式计算（DISC）奥地利维也纳37：1[13] 佩德罗·拉马赫特，安德烈·科雷亚，帕斯卡尔·费尔伯，纳赫松·科亨.2019年。OneFile：一个无等待的持久性transmittance存储器。第49届IEEE/IFIP Intl. Conf. 依赖系统和网络（DSN）。Portland，OR，151-163.[14] Michael L.Scott. 2013年。共享内存同步。Morgan ClaypoolPublishers，San Rafael，CA.[15] Alexander Spiegelman，Guy Golan-Gueta，and Idit Keidar.2016年。跨 平 台 数 据 结 构 库 。 第 37 届 ACM 会 议 编 程 语 言 设 计 与 实 现（PLDI）加利福尼亚州圣巴巴拉，682- 696。[16] 放 大 图 片 作 者 ： James R. 作 者 ： Andrew W. 海 伊 和 王 聪 2009.NZTM：非阻塞零间接事务存储器。在第21届ACM Symp. 算法和架构中的并行性（SPAA）卡尔加里，AB，加拿大，204[17] 沙哈尔·蒂姆纳特和埃雷兹·佩特兰克2014年。一种实用的无锁数据结构的无等待模拟 第19届ACM SIGPLAN Symp. 对并行程序设计原理与实践（PPoPP）奥兰多，佛罗里达州，357-368。[18] 张德利和达米安·德切夫。2016年。无锁事务，不回滚链接数据结构。在 第 28 届 ACM Symp. 算 法 和 架 构 中 的 并 行 性 （ SPAA ） PacificGrove，CA，325