海报：路径复制树中的意外扩展

4380海报：路径复制树中的意外扩展0Vitaly AksenovITMO大学 俄罗斯0Trevor Brown滑铁卢大学 加拿大0Alexander FedorovIST奥地利奥地利0Ilya KokorinITMO大学俄罗斯0CCS概念：•计算方法→并发算法。0关键词：并发，持久树，路径复制01引言虽然已经提出了各种各样的手工并发数据结构，但人们对于构建并发数据结构的通用方法（即通用构造或UC）非常感兴趣。UC（半）自动地将顺序数据结构转换为并发数据结构。最简单的方法使用锁[3,6]来保护顺序数据结构，并且一次只允许一个进程访问它。然而，由此产生的数据结构是阻塞的。大多数UC的工作都集中在获得非阻塞进展保证，如无障碍性，无锁定性或无等待性。出现了许多非阻塞性UC。其中一些关键的例子包括Herlihy的里程碑无等待UC[2]，Yi等人的NUMA感知UC[10]以及Fatourou等人的用于大型对象的高效UC[1]。在这项工作中，我们考虑实现持久数据结构的简单问题，即在修改数据结构时保留旧版本[7]。通常，这涉及复制数据结构的一部分，例如树中从根到修改节点的路径[4]，这样就无需直接更改任何现有节点。我们借鉴持久性数据结构和多版本并发控制（MVCC）[9]的思想，特别是路径复制，并使用它们来实现顺序持久数据结构的并发版本。以这种方式实现的数据结构在搜索方面非常高效，但我们预计它们在写入密集型工作负载中无法扩展。令人惊讶的是，我们发现以这种方式实现的并发treap在写入密集型工作负载中与顺序treap[8]相比获得了高达2.4倍的加速。我们在实验中展示了这个效果，并在具有私有每处理器缓存的模型中进行了分析：简而言之，随着进程数量的增加，我们的大小为�的treap的加速比趋向于Ω(log�)。0未经许可，个人或课堂使用者可以免费复制或复制本作品的部分或全部内容，但不得以盈利或商业优势为目的分发副本，并且复制品必须带有本通知和第一页的完整引用。必须尊重本作品第三方组件的版权。对于其他所有用途，请联系所有者/作者。PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 ©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.357751202持久数据结构的直接同步在下面的讨论中，我们重点讨论根据根节点进行操作的数据结构，但可以通过在具有多个入口点的数据结构中添加一个间接级别来概括这些思想（例如，可以添加一个包含所有入口点的虚拟根节点）。我们在名为Root_Ptr的Read/CAS寄存器中存储指向持久数据结构的当前版本的指针（例如，指向持久树的当前版本的根节点）。只读操作（查询）读取当前版本，然后在获取的版本上顺序执行。请注意，没有其他进程可以修改该版本，因此顺序操作在原子上是平凡的。修改操作的实现方式如下：1）读取当前版本；2）通过应用顺序修改使用路径复制（即复制根节点，并复制每个访问的节点）来获得新版本；3）尝试使用CAS原子性地将当前版本替换为新版本；如果CAS成功，则返回：修改操作已成功应用；否则，数据结构已被某个并发进程修改：从步骤（1）重新执行执行。这种方法平凡地结果为无锁线性化数据结构。我们预计只读操作将极好地扩展。实际上，两个进程可以同时读取持久数据结构的当前版本，并并行执行只读持久操作。然而，修改操作似乎无法扩展。当多个修改争用时，只有一个可以成功完成，其他必须重试。例如，考虑对集合的并发修改操作：1）进程P调用insert(2)并获取当前指针RP；2）进程Q调用remove(5)并获取当前指针RP；3）P构造一个带有键2的新版本RPP；4）Q构造一个不包含键5的新版本RPQ；5）P成功执行CAS(&Set.Root_Pointer, RP, RPP)；6）Q从RP到RPQ执行CAS，但失败；因此，Q必须重试。成功的修改操作是顺序应用的，一个接一个地。直观地说，在所有操作都必须执行成功修改的工作负载中，这种方式根本不会扩展。正如我们将在第4节中看到的那样，这种直觉是错误的。3分析关键洞察力是尝试执行更新加载数据到处理器缓存中，这些数据在将来的尝试中可能有用。为了更好地理解，考虑图1所示的二叉搜索树修改。假设我们想4390PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 Vitaly Aksenov，Trevor Brown，Alexander Fedorov和Ilya Kokorin0插入两个键：5和75。我们比较这些插入操作是如何按顺序和并发执行的。首先，我们考虑顺序执行。我们将键5插入树中。它应该作为10的左子节点插入。因此，我们从根节点遍历树到叶子节点10。在此过程中，我们将节点{40, 30, 20,10}加载到处理器缓存中。请注意，此操作执行了四个未缓存加载。现在，我们插入75。它应该作为70的右子节点插入。我们的遍历加载了四个节点：{40, 50, 60,70}。节点40已经被缓存，而其他三个节点必须从内存中加载。因此，我们执行了三个未缓存加载，总共七个未缓存加载。现在，我们考虑使用两个进程的并发执行，其中P插入5，Q插入75。最初，两个进程读取Root_Ptr以加载当前版本。然后，1）P从根节点遍历到10，加载节点{40, 30, 20,10}，2）Q从根节点遍历到70，加载节点{40, 50, 60,70}。每个进程构建数据结构的新版本，并尝试使用CAS替换根指针。假设P成功，Q失败。Q重试操作，但在新版本上进行（图1）。请注意，新版本与旧版本共享大多数节点。Q将75插入新版本。同样，该键应该作为70的右子节点插入。Q从新版本的树中加载了四个节点{40, 50, 60,70}。关键是，节点{50, 60,70}已经被Q缓存。这次重试只产生了一个缓存未命中！因此，并发执行中只有五个序列化加载，而顺序执行中有七个。高级分析我们使用一个简单的模型来分析这个效果（完整证明见[5]）。在这个模型中，进程是同步的，即它们每个时钟周期执行一个原始操作，每个进程都有自己的大小为�的缓存。我们证明对于大量的进程�，加速比为Ω(log�)，其中�是树的大小。现在，我们给出该证明的直观理解。为了简化问题，我们假设树是外部的和平衡的，即每个操作经过log�个节点。我们还假设0工作负载由均匀随机选择的键上的成功修改操作组成。我们首先计算一个进程的操作成本：(log�−log�)∙�+log�，其中 � 是缓存大小（�<�），�是未缓存加载的成本。此表达式捕捉了在最近最少使用缓存下的预期行为。进程应该缓存树的前log�级，因此缓存中的路径上有log�个节点，而log�−log�个节点不在缓存中。为了计算具有 � 个进程的系统的吞吐量，我们假设 �相当大（≈Ω(���(�,log�))）。因此，每个操作执行多次不成功的尝试，最后以一次成功的尝试结束，并且所有成功的尝试（对所有操作而言）是串行化的。由于系统是同步的，每个操作尝试�次加载先前成功尝试�′的数据结构的版本。自 � 开始以来被逐出的节点是由 �′创建的节点。可以证明，在期望中，路径上只有两个节点是未缓存的。最后，操作的成功尝试产生的成本是2∙�+(log�−2)。由于成功尝试是串行化的，所以预期的总加速比是(log�−log�)∙�+log�02∙� +(log�−2)给出Ω(log�) ，其中 � = Ω(log�) 和 � =�(�1−�)。4个实验0我们实现了一个无锁Treap，并在具有18个核心的Intel Xeon5220系统上用Java运行了实验，将其与顺序Treap进行了比较。每个数据点是15次试验的平均值。我们重点介绍以下两个工作负载。（更多结果见[5]。）4.1批量插入和批量删除0假设系统中有 �个并发进程。初始时，集合由10^6个随机整数键组成。进程在互不相交的键集上操作。每个进程重复进行以下操作：逐个插入其所有键，然后逐个删除其所有键。由于键集是不相交的，每个操作都成功地修改了Treap。下面报告了我们的Treap相对于顺序Treap的加速比。4.2随机插入和删除在这个工作负载中，我们首先在[−10^6，10^6]中插入10^6个随机整数，然后每个进程重复生成一个随机键，并以相等的概率尝试插入/删除。某些操作不会修改数据结构（例如插入一个已经存在的键）。0工作负载 Seq Treap UC 1p UC 4p UC 10p UC 17p0批处理451 940 0.89x 1.23x 1.47x 1.47x0随机 419 736 1.48x 2.38x 3.07x 3.19x0致谢0本研究得到以下支持：加拿大自然科学和工程研究理事会（NSERC）探索计划资助：RGPIN-2019-04227，以及加拿大创新基金会约翰∙R∙埃文斯领导者基金（CFI-JELF），同样得到安大略省研究基金CFI领导者机会基金的支持：38512。4400海报：路径复制树中的意外扩展PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔0参考文献0[1] Panagiota Fatourou，Nikolaos D Kallimanis和EleniKanellou。2020年。大对象的高效通用构造。arXiv（2020年）。0[2] MauriceHerlihy。1991年。无等待同步。ACM程序设计语言和系统事务（TOPLAS）13, 1（1991年），124-149。0[3] Maurice Herlihy，Nir Shavit，Victor Luchangco和MichaelSpear。2020年。多处理器编程的艺术。Newnes。0[4] Haim Kaplan。2018年。持久化数据结构。在数据结构和应用手册。Chapman andHall/CRC，511-527。0[5] Ilya Kokorin，Alexander Fedorov，Trevor Brown和VitalyAksenov。2022年。海报：路径复制树中的意外扩展。arXiv0预印本arXiv:2212.00521（2022年）。0[6] Leslie Lamport。1987年。快速互斥算法。ACM事务计算机系统（TOCS）5,1（1987年），1-11。0[7] Chris Okasaki。1999年。纯函数数据结构。剑桥大学出版社。0[8] Raimund Seidel和Cecilia R Aragon。1996年。随机搜索树。Algorithmica16, 4（1996年），464-497。0[9] Y Sun，G Blelloch，W Lim和APavlo。2019年。支持多版本索引的混合工作负载的高效快照隔离。VLDB13, 2（2019年）。0[10] Z Yi，Y Yao和KChen。2021年。用于NUMA多核并发数据结构的通用构造。在第50届ICPP中。1-11。