海报：非阻塞数据结构的事务合成

4410海报：非阻塞数据结构的事务组合0Wentao Cai0wcai6@cs.rochester.edu罗切斯特大学 计算机科学系罗切斯特，纽约，美国0Haosen Wen0hwen5@cs.rochester.com罗切斯特大学 计算机科学系罗切斯特，纽约，美国0Michael L. Scott0scott@cs.rochester.com罗切斯特大学 计算机科学系罗切斯特，纽约，美国0摘要0我们引入了非阻塞事务组合（NBTC），一种用于并发数据结构上的非阻塞操作的原子组合的新方法。与以前的软件事务内存（STM）方法不同，NBTC利用现有非阻塞结构的线性化能力，在大多数情况下，将必须以原子方式执行的内存访问数量减少到每个操作中的一个（这通常是组成操作的线性化指令）。我们对NBTC的无阻塞实现称为Medley，它可以轻松地将大多数非阻塞数据结构转换为事务对应物，同时保持其非阻塞活力和高并发性。在我们的实验中，Medley的性能超过了最快的竞争性先前方法LFTT，提高了40-170％。与按顺序执行的单独操作相比，Medley的事务组合的边际开销约为2.2倍。对于持久内存，我们观察到通过基于时代的定期持久性可以“几乎免费”实现事务的故障原子性。为此，我们将Medley与nbMontage集成在一起，nbMontage是一个用于周期性持久性数据结构的通用系统。结果的txMontage提供了ACID事务，并实现的吞吐量比OneFile持久性STM系统高出两个数量级。0CCS概念：•计算方法→并发算法；•计算理论→并行计算模型；•硬件→非易失性内存。0关键词：非阻塞数据结构，事务，持久内存0获得本作品的部分或全部数字或印刷副本，用于个人或课堂使用，授予免费，但不得为了盈利或商业优势制作或分发副本，并且副本必须在第一页上带有此通知和完整引用。必须尊重本作品的第三方组件的版权。对于其他所有用途，请联系所有者/作者。PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克，版权所有©2023年，所有者/作者保留版权。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.357750301 背景许多多线程系统需要将操作组合成以全有或全无方式（即原子方式）发生的事务。其中一个潜在的解决方案可以在软件事务内存（STM）系统中找到，该系统会对每个内存访问进行仪器化和跟踪，并将几乎任意的顺序代码转换为推测性事务。几个STM系统提供非阻塞进展[4，7，9，10，16]。STM编程模型很有吸引力，但是它的仪器化通常会对事务操作施加3-10倍的开销[14，第9.2.3节]。Spiegelman等人的基于锁的事务数据结构库（TDSL）[15]通过将STM量身定制到特定数据上（例如，将只读集大小减小到可能指示语义冲突的关键节点上）来减少开销。在与TDSL并发进行的工作中，Zhang等人[18]提出了锁定非阻塞事务变换（LFTT），一种基于观察到冲突管理中只有关键节点重要的非阻塞方法。随后，LaBorde等人的动态事务变换（DTT）[8]将LFTT推广到动态事务（指定为lambda表达式）。LFTT和DTT利用了现有非阻塞数据结构的并发性。不幸的是，需要识别关键节点的需求往往限制它们只能用于表示集合和映射的数据结构。DTT的发布和帮助机制还要求操作之间的“粘合”代码完全可重入（以便由帮助线程并发执行[8]），并且在冲突发生时可能会导致冗余工作。更糟糕的是，对于读取密集的工作负载，LFTT和DTT要求读者对编写者可见，引入了在缓存一致性协议中显著增加争用的元数据更新。02 我们的贡献0我们引入了非阻塞事务组合（NBTC），一种新的方法，可以创建各种非阻塞数据结构的事务版本，同时保持非阻塞进展，并且比传统STM的开销明显降低。具体来说，NBTC0本工作得到NSF基金CCF-1717712，CNS-1900803和CNS-1955498的部分支持。arXiv上提供了完整版本[2]。10410510610604420PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克，Wentao Cai，Haosen Wen和Michael L. Scott0可以组合任何非阻塞数据结构，其中每个操作都有一个可以立即识别的线性化点，即：01.静态地，我们可以确定每个指令可能作为操作的线性化点。这样的指令必须是只读操作的加载或更新操作的比较交换（C02.动态地，在执行潜在的线性化指令之后，我们可以确定它是否确实是线性化点。线性化加载必须在操作返回之前确定；线性化CAS必须在执行任何其他共享内存访问之前确定。0广泛认为，大多数非阻塞操作由“规划”阶段和“清理”阶段组成[5,17]，由一个线性化指令分隔开来。执行规划阶段不会导致操作成功；如果需要，任何线程都可以执行清理。NBTC的直觉是，在已经非阻塞的结构中，只有关键的内存访问——大部分是线性化的加载和比较交换（CAS）指令——需要以原子方式发生，而规划可以安全地在事务遇到时执行，清理可以延迟到事务提交后。我们对现有数据结构和组合模式进行的调查揭示了这种直觉的两个主要复杂性。第一个复杂性涉及到“发布点”的概念，即一个操作可能对其他线程可见但尚未线性化的点。由于发布可以改变其他线程的行为，因此必须保持推测状态，直到整个事务提交。一个例子可以在Natarajan和Mittal的二叉搜索树中看到[11]。第二个复杂性出现在一个事务�执行了两个以上的操作，其中一个后续操作（称之为�2）观察到了一个先前操作（称之为�1）的推测性CAS。在这种情况下，执行�的线程必须像�1已经完成一样继续进行。如果�1需要清理（这是NBTC通常会延迟到事务提交后的操作），�2在继续之前可能需要推测性地帮助�1。与此同时，其他事务不应该知道�1的存在。引入一个推测间隔的概念可以处理这两种复杂情况，在推测间隔中，CAS指令必须同时完成才能作为事务的一部分生效。这类似于规范化的非阻塞数据结构中的CAS执行器阶段[17]，但并不相同，主要是由于第二个复杂性。将关键指令定义为推测间隔中的CAS，以及只读操作的线性化加载，NBTC方法如下：要在可组合的非阻塞数据结构上原子地执行一组操作，我们将每个操作转换为以下形式（1）推测间隔之前的指令和非关键的00 10 20（a）获取：插入：删除0：1：10（b）获取：插入：删除18：1：10图1. 事务性跳表的吞吐量（以log�为轴）。0在推测区间内的指令在事务遇到它们时即时执行；（2）关键指令以推测的方式执行，因此它们只有在事务提交时才会以原子方式生效；（3）推测区间之后的指令将被推迟到提交之后执行。为了说明NBTC，我们编写了一个系统Medley，该系统（1）对关键指令进行仪器化，以推测方式执行并使用M-compare-N-swap，我们改进的Harris等人的多字CAS的原子提交；（2）识别和积极解决事务冲突；（3）将非关键清理延迟到事务提交之后。图1报告了在总共80个超线程的服务器上执行跳表微基准测试的吞吐量。我们测量的瞬态系统（实线）包括我们的Medley，OneFile瞬态STM [13]，TDSL[15]和LFTT[18]。Medley的性能优于OneFile和TDSL一个数量级，并且比LFTT快40-170％。对于持久内存，我们观察到事务的故障原子性可以通过基于时期的定期持久性[12]来免费实现：如果同一事务的操作总是发生在同一时期，则它们将在崩溃后一起恢复（或丢失）。基于这个观察，我们将Medley与nbMontage[1]（我们的基于时期的非阻塞定期持久性系统）合并在一起，创建tx-Montage。给定的事务中的所有操作都带有相同的时期号码，然后在提交时与其他读取集一起验证，以确保事务在该时期提交。图1中的持久化系统（虚线）表示我们的txMontage和OneFile持久STM（POneFile）[13]。尽管在IntelOptane非易失性内存上，txMontage的性能接近DRAM上的Medley，但持久的OneFile比其瞬态版本慢大约10倍，反过来比txMontage慢两个数量级。我们使用Medley和txMontage转换了各种数据结构，并在Medley，txMontage和其他兼容的竞争对手上运行TPC-C[3]事务处理基准测试。结果（在arXiv的完整版本中报告[2]）再次证实了我们系统的卓越性能。4430海报：非阻塞数据结构的事务组合PPoPP '23，2023年2月25日-3月1日，加拿大蒙特利尔0参考文献0[1] Cai Wentao，Wen Haosen，Vladimir Maksimovski，MingzheDu，Rafaello Sanna，Shreif Abdallah和Michael L. Scott. 2021.并发数据结构的快速非阻塞持久性.在第35届分布式计算国际研讨会（DISC）上. 德国弗赖堡，14:1-14:20页。0[2] Cai Wentao，Wen Haosen和Michael L. Scott. 2023.非阻塞数据结构的事务组合. arXiv预印本arXiv:2301.00996.0[3] 事务处理委员会. 2010. TPC-C基准测试（修订版5.11.0）。http://www.tpc.org/tpcc/ .0[4] Keir Fraser. 2003. 实用的无锁性. 博士论文.伦敦国王学院，剑桥大学计算机实验室技术报告＃579，2004年2月.www.cl.cam. ac.uk/techreports/UCAM-CL-TR-579.pdf .0[5] Michal Friedman，Naama Ben-David，Yuanhao Wei，Guy E.Blelloch和Erez Petrank. 2020.NVTraverse：在NVRAM数据结构中，目标比旅程更重要.在第41届ACM程序设计语言设计和实现会议（PLDI）上.虚拟会议，377-392页。0[6] Timothy L. Harris，Keir Fraser和Ian A. Pratt. 2002.一种实用的多字比较并交换操作.在第16届分布式计算国际研讨会（DISC）上. 法国图卢兹，265-279页。0[7] Maurice Herlihy，Victor Luchangco，Mark Moir和William N.Scherer III. 2003. 用于动态大小数据结构的软件事务内存.在第22届ACM分布式计算原理研讨会（PODC）上.马萨诸塞州波士顿，92-101页。0[8] Pierre LaBorde，Lance Lebanoff，Christina Peterson，DeliZhang和Damian Dechev. 2019. 用于链式数据结构的无等待动态事务.在第10届多核和众核编程模型和应用国际研讨会（PMAM）上.华盛顿特区，41-50页。0[9] Virendra Jayant Marathe和Mark Moir. 2008.迈向高性能无阻塞软件事务内存. 在第13届ACMSIGPLAN并行编程原理与实践研讨会上0（PPoPP）。犹他州盐湖城，227-236页。0[10] Virendra J. Marathe，Michael F. Spear，Christopher Heriot，AthulAcharya，David Eisenstat，William N. Scherer III和Michael L. Scott.2006. 降低软件事务内存的开销. 在第1届ACM SIGPLAN事务计算研讨会上.加拿大渥太华，11页。0[11] Aravind Natarajan和Neeraj Mittal. 2014. 快速并发无锁二叉搜索树.在第19届ACM SIGPLAN并行编程原理与实践研讨会（PPoPP）上.佛罗里达州奥兰多，317-328页。0[12] Faisal Nawab，Joseph Izraelevitz，Terence Kelly，Charles B.Morrey III，Dhruva R. Chakrabarti和Michael L. Scott. 2017.Dalí：一种定期持久哈希映射. 在第31届国际分布式计算研讨会（DISC）上.奥地利维也纳，37:1-37:16页。0[13] Pedro Ramalhete，Andreia Correia，Pascal Felber和NachshonCohen. 2019. OneFile：一种无等待持久事务内存.在第49届IEEE/IFIP国际可靠系统和网络会议（DSN）上.俄勒冈州波特兰，151-163页。0[14] Michael L. Scott. 2013. 共享内存同步. Morgan＆ClaypoolPublishers，圣拉斐尔，加利福尼亚州。0[15] Alexander Spiegelman，Guy Golan-Gueta和Idit Keidar. 2016.事务数据结构库. 在第37届ACM程序设计语言设计和实现会议（PLDI）上.加利福尼亚州圣巴巴拉，682-696页。0[16] Fuad Tabba，Mark Moir，James R. Goodman，Andrew W.Hay和Cong Wang. 2009. NZTM：非阻塞零间接事务内存.在第21届并行算法和体系结构研讨会（SPAA）上.加拿大阿尔伯塔省卡尔加里，204-213页。0[17] Shahar Timnat和Erez Petrank. 2014. 无锁数据结构的实用无等待仿真.在第19届ACM SIGPLAN并行编程原理与实践研讨会（PPoPP）上.佛罗里达州奥兰多，357-368页。0[18] Deli Zhang和Damian Dechev. 2016. 无回滚的链式数据结构无锁事务.在第28届并行算法和体系结构研讨会（SPAA）上.加利福尼亚州太平洋格罗夫，325-336页。