多版本垃圾收集的有效方法及实践研究

66Ñďăpqp q理论上和实践上都有效的多版本垃圾收集魏元浩yuanhao1@cs.cmu.edu美国卡内基梅隆大学帕纳焦塔·法图鲁faturu@csd.uoc.gr希腊克里特大学摘要多版本控制广泛应用于数据库、事务内存和并发数据结构。 它可用于支持在存在并发更新操作的情况下显示为原子的只读事务。 任何维护每个对象的多个版本的系统都需要一种有效地回收它们的方法。我们实验比较各种现有的回收技术，将它们应用到多版本树和多版本哈希表。使用这些实验的见解，我们开发了两个新的多版本垃圾收集（MVGC）技术。这些技术使用两种新颖的并发版本列表数据结构。我们的实验评估表明，我们的最快的技术是最快的现有MVGC技术的竞争力，而在某些工作负载上使用显着更少的空间。 我们的新技术提供了强大的理论界限，特别是在空间使用方面。这些界限确保方案具有一致的性能，避免了其他技术的非常高的最坏情况下的空间使用。CCS概念：·计算方法学并行算法。1介绍多版本并发控制广泛用于数据库系统[6，30，37，38，42，53]，事务存储器[16，25，28，39，40]和共享数据结构[4，15，36，50]，主要用于支持只读事务（缩写为rtx），包括出现原子的复杂多点查询，而更新操作同时执行这通常是通过维护每个对象的以前版本的列表来实现的，该列表按指示何时本作品采用知识共享署名国际4.0许可协议进行许可PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577508盖伊·E Blellochguyb@cs.cmu.edu美国卡内基梅隆大学ruppert@eecs.yorku.ca加拿大约克大学对象已更新。 rtx获取一个时间戳���并遍历对象���的版本列表，以读取最新版本。多版本垃圾收集（MVGC）是指删除和收集过时版本的问题 假设版本列表中的两个连续版本具有时间戳1和2。如果有一个正在进行的rtx，其时间戳 满足1，则需要时间戳为1的版本2、过时的，否则。总是需要最新版本有效的MVGC是多版本系统中的一个重要问题[5，7，16，26，30，33，36，37，50]，因为保留过时的版本会导致过多的空间使用。MVGC最简单的方法是使用基于时期的回收（EBR）[16，26，36，37，50]。 EBR通过在没有活动rtx需要时仅从版本列表的末尾删除最早的版本来快速简单地管理版本列表。但是，它不能从版本列表的中间删除过时的版本，因此它可能会维护无限数量的过时版本。在实践中，当存在长寿命的rtx时，这可能导致空间爆破。为了避免这个问题，Lu和Scott设计了一个MVGC系统GVM [33]，它可以通过偶尔遍历所有版本列表并删除过时版本来删除中间版本。HANA系统使用类似的方法[30]。这些方法的问题在于，它们扫描所有列表，即使它们很少或从不更新。Böttcher等人在Steam系统中改进这些技术[7]，将列表扫描与列表更新联系起来。Steam的实验表明，与之前的一些MVGC方法相比，在具有冗长的rtx和频繁更新的工作负载中，删除中间版本可以显着提高空间使用率和吞吐量。然而，这些系统都没有提供强大的最坏情况下的时间界限，并为���进程和���版本列表实现最佳���������空间的界限。Ben-David等人[5]最近给出了一种MVGC技术（以下简称BBF+），该技术具有最知名的时间和空间边界。它删除中间版本而不遍历完整列表。它是无等待的，只维护一个常数因子的版本比需要的，并使用���1个 步骤平均每个分配的版本。为了实现这一点，BBF+定义了一个范围跟踪对象来精确识别过时的版本。然而，BBF+以前没有实施，它是67p qPPoPPBlelloch，Panagiota Fatourou和Eric Ruppert不清楚它在实践中是否能达到时间效率 它使用了一个复杂的双向链表实现，我们称之为TreeDL，因为它上面有一个隐式树。通过在单个系统中实现和比较几种MVGC方案，研究了它们在实践中的效率。基于我们的实验，我们开发了两种新的MVGC方案，它们结合并扩展了Steam和BBF+的技术，以提供与BBF+一样空间高效的协议，同时实现与Steam和EBR相当的时间效率（有时略好，有时略差）。 我们使用MVGC方案从版本列表中取消过时版本的链接，允许垃圾收集器稍后回收它们。 新方案放宽了BBF+的一些最坏情况下的时间保证，以提高常见情况下的时间性能。然而，它们保持了在[5]中证明的强最坏情况空间界我们的实验分析揭示了MVGC的最先进技术的实用价值 它表明，它们的性能显着依赖于工作量，没有一种技术总是占主导地位的时间和空间。然而，我们的新方案显示出最一致的性能，没有任何特别不利的工作负载。从[5，7]中的最新MVGC方案开始我们必须结合、简化和扩展技术以获得两个新的MVGC方案（如第3节所讨论的）。他们的重点是一旦发现过时版本，就加快删除这是MVGC的重要组成部分我们的删除算法大大加快了理论上有效的BBF+计划。其中一个也被用来提出一个无锁版本的蒸汽。对于我们在实验中使用的无锁多版本数据结构，这个版本比锁定整个版本列表的原始版本更有效。我们的算法使用BBF+的范围跟踪（RT）对象来识别过时的版本。一个主要的挑战是删除这些版本可能与版本列表上的其他操作并发。对于第一个新方案，称为DL-RT，我们开发了一个一个更简单的双向链表实现，支持从版本列表的中间删除（参见第4节）。这个实现被称为PDL（实用双向链表），它牺牲了TreeDL���������这种选择是由实验的观点���驱动的，1.01跨各种工作负载。 实验表明，新的，更简单的列表是更快的常数时间列表TreeDL 时，小。我们的第二个算法，SL-RT，进一步提高了许多常见工作负载的实际性能，其中版本列表往往很短，所以线性搜索是相当有效的。在这种情况下，我们使用一个单链表，它需要更少的空间（没有反向指针）和更少的时间来更 新 由 于 较 少 的 指 针 变 化 。 GVM [33] 、 Steam [7] 和HANA [30]也依赖于这一观察[7]。我们在第5开发了一个单链表实现，称为SSL（简单单链表），并使用它来实现SL-RT中的版本列表。与Steam和HANA中的不同，它是无锁的，与无锁的GVM不同，它不需要指针上的任何标记位在不允许直接标记指针的语言中，这样的标记位需要额外的间接级别我们的新列表结构支持排序列表，一端追加，任何地方删除，并可能独立的利益。我们证明两者都是正确的。将我们的新列表与[5]的范围跟踪相结合，与以前的MVGC方案相比，显着提高了许多工作负载中的空间。 范围跟踪对象识别要删除的列表元素（在DL-RT中）或要遍历和收集的列表（在SL-RT中），这比在Steam中每次更新时遍历列表或在HANA和GVM中定期遍历所有列表更准确。在我们的实验（第6节）中，我们实现并研究了几种方案：基于epoch的收集器[50]，BBF+[5]，我们新的MVGC方案以及Steam的优化变体[7]我们使用SSL开发。 MVGC方案包括几个可能对其时间或空间开销有重要影响的机制。我们重点关注了以下机制，我们的实验表明，对性能有很大的影响：（1）存储版本的数据结构和（2）如何选择何时删除过时的版本。我们在多版本并发数据结构的背景下对这些MVGC方案进行了实验这些是利用版本列表来支持原子只读事务的数据结构（例如，范围查询）以及单键插入、删除和查找操作。 它们可以用作数据库索引[31，49]，最近得到了很多关注[27，36，45，45，50]。我们实验比较了MVGC计划在两个完全不同的并发数据结构，一个多版本的平衡二叉搜索树和一个多版本的哈希表。与之前的工作[7]一样，我们看到回收中间版本对于减少内存开销（空间）至关重要，特别是当存在长rtx或超额订阅时（即，当存在比可用逻辑核更多的线程时）。特别是，EBR不收集中间版本，需要比其他版本多10倍的空间。也许令人惊讶的是，我们意想不到的是，蒸汽有时有特别糟糕的空间使用树木，即使它确实收集中间版本。我们发现这是由于版本化指针指向包含其他版本化指针的对象，如第6节所述。这导致需要多达8倍的空间的情况。我们发现SL-RT在空间方面几乎总是表现最好Steam和EBR通常在更新吞吐量方面表现最好，但对于rtx吞吐量，性能好坏参半。对于组合吞吐量，方案之间的差异很小;有时Steam和EBR更好68pqp qPPoPP'23，2023年2月25日至3月1日有时SL-RT和DL-RT更好。BBF+几乎总是最慢的。总之，实验表明，使用范围跟踪的MVGC方案避免了EBR和Steam的高空间异常，吞吐量在混合工作负载上相似，在更新繁重的工作负载上仅略差许多现有的实用MVGC方案是为使用多版本的数据库系统设计的，并且经常与这些多版本系统的其他部分紧密交织在一起。我们相信许多MVGC技术在数据库系统和多版本数据结构中是以前的研究[7]比较了使用不同事务管理协议的各种数据库系统（包括[7，29，30]）中的MVGC方案。对于我们的实验，我们通过将不同的MVGC方案应用于同一对多版本数据结构来控制这些混淆因素。我们知道以前没有全面的，苹果对苹果的MVGC技术比较。我们总结了本文两种新颖的MVGC方案，借鉴和扩展了最先进的空间和时间效率方案的思想。新方案保持了BBF+ [5]提供的强大的最坏情况空间边界，同时在大多数情况下实现了与Steam [7]相当的一个实验分析，公平地比较国家的最先进的MVGC计划，通过将它们应用到相同的多版本数据结构。这揭示了这些计划的实际优点，以及没有一种MVGC方法在空间和时间方面明显获胜的原因几个见解，可以推动新的MVGC方案的设计，因为他们对我们的新方案。一种新的无锁双向链表PDL，在MVGC中使用时是有效的，并且可能在其他地方有用。一个新的简单的单链表实现 SSL， 适用 于 MVGC ， 并具 有更好 的吞吐 量比PDL。2背景和相关工作多版本化。一般来说，使用多版本涉及维护表示当前时间的全局时间戳。根据实现，该全局时间戳可以通过rtx [15，50]、更新操作[36]或系统时钟[27，32]递增。 每次更新都会用时间戳标记任何新对象（或对象的版本），并将新对象添加到相应版本列表的头部。每个rtx读取全局时间戳并使用它来导航版本列表。 更具体地说，带有时间戳 的rtx遍历一个版本列表，直到找到时间戳最多 为的版本，然后从该版本中读取所需的值。 更新操作和rtx如何实现的细节在不同的实现中是不同的，但是这个高级的图片对于我们研究MVGC是足够的。版本化CAS对象[50]是我们在比较不同MVGC方案时在实验中使用的多版本化的特定实现。它是一个CAS对象，支持在给定时间戳的情况下查找以前存储在其中的旧值。 我们的实验使用这些对象将对rtx的支持添加到基于CAS的无锁平衡二叉搜索树[8]和简单的无锁哈希表中。基于时期的复垦（EBR）。EBR [9，18]是一种将执行划分为时期的历史回收技术。每个操作都是通过一个声明数组读取和声明当前epoch当所有活动进程都已宣布当前纪元时，全局纪元计数器递增并且新纪元开始。该历元计数器与用于多版本化的时间戳分开 EBR确保在当前或前一个时期开始的所有活动操作，因此在早期时期删除的任何节点都可以安全地回收。通过观察rtx将永远不会访问在rtx开始之前被覆盖的任何版本，可以将这个想法扩展到多版本因此，在前一个纪元之前被覆盖的所有版本都可以安全地回收，因为它们不再被任何活动的rtx所需要，并且也不在任何所需版本的路径上。由于EBR简单而快速，因此它的变体广泛应用于用于MVGC [16，37，50，53]。然而，基于EBR的MVGC方案仅从版本列表的末尾回收最旧的版本，而不是列表中间的过时版本。因此，EBR不能保证空间边界，并可能导致高空间开销，特别是如果进程执行长rtx，从而阻止epoch提前，或者如果处理器超额预订。基于压实的填海。为了解决EBR的弱点，基于预防的MVGC方案[7，30，33]识别过时的版本并将其从版本列表中删除。一个版本的时间间隔是它是最新版本时的时间戳间隔。在基于警告的方案中，rtx宣布它们打算用于遍历版本列表的时间戳。 通过首先读取所宣布的时间戳，对它们进行排序，然后遍历版本列表以识别并移除其时间间隔不包括任何所宣布的时间戳的版本，来压缩版本列表。由于版本是有序的，因此遍历每个版本所花费的时间是恒定Steam [7]会遍历并压缩一个版本列表，每当有新版本添加到列表中时。 HANA [30]和GVM [33]没有将压缩与添加版本绑定在一起，而是使用后台线程遍历所有列表，或者偶尔压缩主线程。 这些技术的缺点是遍历版本列表，即使它包含很少或没有要收集的过时版本。HANA和GVM甚至在没有对列表进行更改的情况下访问列表 GVM [33]和Steam [7]保证每个版本列表都包含������版本，其中���是进程数，因此���������版本是为���列表维护的。范围追踪BBF+[5]使用范围跟踪对象直接识别过时的版本，避免遍历整个列表。范围跟踪对象跟踪一组非当前版本，每个版本都被分配了‚‚‚‚‚69pqpq``p'q`pqPPoPPBlelloch，Panagiota Fatourou和Eric Ruppert表示其时间间隔的整数范围如果范围跟踪对象中的某个版本的时间间隔与rtx通告的任何时间戳都不相交，则可以回收该版本在RAN ngeTrA cker（[5]的可线性化范围跟踪实现）中，每个线程都将非当前版本追加到本地列表中。如果xmllist的大小���������flush将队列的本地列表附加���然后，它将两个列表从队列中取出，合并它们的内容，并将合并后的列表与当前公告的排序序列进行比较，以确定仍然需要哪些版本所需版本的列表被排入队列，并返回一组过时的版本，以便将它们从列表中删除刷新阶段需要������log���步骤，并且每隔0 ���log���次将元素插入本地列表中执行一次。因此，RA ngeTrA cker确保了它支持的每个操作的摊销常数时间从列表中删除 在发现一个过时的版本后-它必须从它的列表中删除[7]和[30]使用锁来安全地这样做GVM [33]使用Harris的无锁单链表[21]的变体。 这是可行的，因为列表总是从它们的头部开始遍历。然而，BBF+需要安全地从列表中间删除过时的节点，只要有一个指向节点的 指 针 。 为 了 安全有效地做 到 这 一 点 ， BBF+ 使 用TreeDL，一个自定义的无等待的双向链表。TreeDL使用一个隐式二叉树，它的按序transform按顺序给出列表节点作为树的叶子的列表节点在列表中不相邻，因此可以安全地并发删除。 如果只删除叶子，那么存储rtx仍然需要的版本的叶子可能会阻止删除内部节点上的过时版本，从而导致高空间边界。因此，TreeDL提供了复杂的帮助机制，也允许删除树中的内部列表节点。这样做是为了确保列表的一致性和低空间使用。其他填海计划。最近的改进，EBR是基于版本的回收[44]。它通过重新启动长时间运行的操作来限制内存，最近被应用于多版本数据结构[45]。已经提出了其他内存回收方案，但它们不能解决MVGC问题[23，34，41，52]，或者需要硬件[1，13]或操作系统[9，46]的特殊支持。BBF+使用Hazard指针[34]和引用计数[11，12，23]的最新实现[2]来处理-定位已从列表中拼接出来的节点 我们新的MVGC方案依赖于自动Java垃圾收集器来释放不可达节点。其他无锁列表结构。 我们设计了SSL和PDL作为特殊用途的无锁链表，用于表示版本列表。 它们避免了Valois的单链表[48]的额外间接级别，该列表将辅助节点放置在真实节点之间。Harris的单链表[22]和其他建立在它基础上的[17，35]在Java中实现时也增加了一个间接级别，因为它们需要列表指针上的标记位。除了上面讨论的TreeDL之外，其他现有的无锁双向链表实现非常复杂，因为它们支持比我们需要的版本列表更多的操作[43，47]或依赖于多字CAS指令[3，19]，这在硬件中并不广泛可用（尽管它们可以在软件中模拟[20，22]）。3拟议的MVGC计划我们提出了两种新的MVGC方案，DL-RT和SL-RT。 与BBF+一样，我们使用R AN ngeTr A cker来识别列表中间的哪些版本可以删除。我们的新方案可以以与BBF+相同的方式应用;即，rtxs使用RA ngeTrA cker提供的操作来宣布和取消宣布它们的时间戳，并且每当一个版本被新版本覆盖时，它将与其时间间隔一起传递给RA ngeTrA这两个新方案保留了正确性条件（例如，线性化、顺序一致性）。我们的第一个计划，DL-RT是基于一种新的双链表实现，称为PDL，而SL-RT采用了一种新的，简单的实现一个单链表，称为SSL。列表按关键字字段（例如，版本时间戳 ） 。 PDL 支 持 以 下 操 作 ， 在 [5 ， 50]中 引入 ：1 ）tryAppend（x，y）尝试在列表的末尾添加新元素y，假定x当前是最后一个列表元素; 2）remove（x）从列表中删除元素x（并用于垃圾收集）; 3）peekHead返回列表的最后一个元素（即，当前版本）;4）search（key）返回列表中key小于或等于key的最新元素（即， 当密钥是当前时间戳时的当前版本）。与MVGC使用版本列表的方式一致，PDL假设remove只在每个节点上调用一次，而不是在头节点上上面的列表接口支持版本化的CAS对象，如[50]中所述。 在本例中，一个CAS操作想要将值从v更改为v1，它会调用peekHead，并检查存储在最新版本中的值是否为v。如果是这样，则JavaScript调用tryAppend在v之后添加一个包含值v1的版本。如果tryAppend失败，则并发CAS必须成功地将CAS对象的值更改为其他值从v。然后，返回false。为了避免TreeDL的一些复杂性，我们基于一个简单的想法设计了我们的新颖实现PDL：删除一个节点，我们标记它，然后向外遍历到任何方向上的第一个未标记的节点，并使它们相互指向。PDL确保在执行结束时，版本列表中总共有最多的节点，其中包含 追加和 删除的总数。 此界限优于TreeDL [ 5 ]提供的2log界限，其中是单个版本列表上的最大附件数。 在时间方面，PDL确保tryAppend和peekHead保持TreeDL的 p1q界限，但remove的步骤数为 pq，其中70p q````p`p` q´8PPoPP'23，2023年2月25日至3月1日是列表中连续节点的并发删除数在我们的每个实验中的平均值 最多为1.01。因此，从实际的角度来看，将搬迁的时间限制放宽到2000年是一个很好的妥协。SSL是一个单链表实现，因此没有反向指针。 在一个双向链表中，一个版本可以通过只访问节点的直接邻居来删除。 要从一个单链表中删除一个节点，我们必须从链表的头部开始遍历链表，找到它在链表中的前导节点。因此，SSL支持遍历整个列表的紧凑例程，而不是专注于删除单个节点，从而删除过时的节点。实验表明，在许多情况下，版本列表往往很短，因此遍历列表通常是廉价的。事实上，在大多数实验中，采用SSL的SL-RT表现出比DL-RT更好的吞吐量。SSL确保版本列表中包含的节点数量与PDL相同的可������扩展性。PDL和SSL在第4节和第5节中介绍。 由于空间有限，它们的正确性证明和复杂性界限都在完整版本中[51]。 我们使 用 PDL 开 发 DL-RT ， SSL 开 发 SL-RT ， 以 及STEAM+LF，我们在下面描述的Steam的无锁版本。具体来说，DL-RT采用PDL，SL-RT采用SSL，而不是像BBF+那样使用TreeDL来实现版本列表。RA ngeTrA cker [5]由DL-RT（决定何时拼接出单个节点）和SL-RT（决定何时遍历和压缩版本列表）使用文[5]证明了RA ngeTrAcker使用的是n =2的对数周期space，其中，n是在执行过程中的任何时候所需版本的最大数量 我们将PDL中节点的左指针和右指针以及SSL中节点的左指针称为访问指针。一个节点在PDL或SSL中的某个时间点是可达的，如果它可以从列表头开始并跟随访问指针到达。回想一下，PDL和SSL都确保了版本列表中的大多数节点都是可访问的。 这个界限和R A ngeTr Acker的界限意味着以下内容。定理1. 考虑使用DL-RT或SL-RT进行垃圾收集的并发多版本数据结构的实现。在执行的任何时候 ，版本列表中可访问的版本总数为2log ），其中 是之前所有时间内所需版本数的最大值 。如果在执行过程中的某个时刻需要的版本数量很大，这只会影响有限数量的步骤的版本列表更具体地说，如果所需版本的数量保持在执行的后缀中的某个数量以下，则定理1中的可达版本的数量最终将是���p`2logq。4双向链表算法1提供PDL的伪代码。 每个节点存储一个左指针和右指针，以及一个标记位，1类节点{2intkey; Value val;bool mark; //初始化为false3Node* left，right;}4class DoublyLinkedList {5Node* head;6public int findDuplicate（）{returnhead->val;}7public int findDuplicate（intk）{8Node* x = head;9while（x->key > k）{10x = x->left;}11returnx->val; }}12public voidrun（Node* x，Node* y）{13Node* w = x->left;14//如果需要，15如果（w！= null）CAS（（w->right），null，x）;16return x;17publicvoid onDestinyCode（x，y）{18CAS（（x->right），null，y）;19返回true;20returnfalse;21public voidrun（Node*）{22return true;23Node* left = x->left;24Node* right = x->right;25Node* leftRight，rightLeft;26而（true）{27while（left->marked）left = left->left;28while（right->marked）right = right->right;29left = right->left;30leftRight = left->right;31if（left->marked）||right->marked）continue;32如果（！CAS（right->left，rightLeft，left））继续;33如果（！CAS（left->right，leftRight，right））继续;34break;}算法1. 双向链表实现（PDL）。方便删除。它还存储了一个键key和一个值val，它们是在节点创建时设置的，永远不会更改。列表元素被附加到列表的右端，头指针指向最右边的节点。 列表最初包含一个带有key的sentinel节点，该节点始终位于列表的左端。peekHead操作只是读取head并返回节点的val字段。搜索（k）从head开始，跟随左指针，直到到达键最多为k的节点。一个tryAppend（x，y）尝试在一个先前从头指针读取的节点x之后附加一个新的节点y它将y的左指针更新为x（第16行），并使用CAS将头指针从x摆动到y（第17行）。如果摆动头部失败，则操作返回false。否则，tryAppend尝试使用第18行的CAS将x的右指针更新为y。如果摆动头部成功，但在更新x的右指针之前tryAppend暂停71ÑÐÐÐÐPPoPPBlelloch，Panagiota Fatourou和Eric Ruppert头uvWXyz图2. 列表的状态示例。删除（v）已完成。 挂起的remove（w）和remove（y）已成功执行第32行的CAS，但未执行第33行的CAS。搜索可以访问所示的任何节点不一致的状态。因此，在任何后续的tryAppend添加一个节点到y之外之前，它首先通过更新x的右指针（第15行）来帮助完成节点y的追加。使用CAS（第15和18行）初始化x的remove（x）首先标记节点x。（第22行通过一个简单的写操作来实现这一点，因为标记的节点将永远保持标记状态。然后，它会在每一侧寻找最近的未标记节点，并使用CAS指令更新它们以指向彼此。如果任一CAS失败（或者如果第31行验证两个节点仍然未被标记失败），则remove操作再次尝试查找最近的未标记节点，从上一次尝试停止的地方继续向外。一旦两个指针都被更新，移除操作就终止。PDL不能在左指针和右指针之间保持完美的一致性：删除操作可能会更新一个指针，但会在更新另一个指针之前暂停或死亡。此外，为了保持实现的轻量性，remove在应用自己的更改之前不会帮助附近的其他remove操作使列表保持一致;它只是进行更改（这可能会顺便帮助其他remove操作生效）。示例见图2。此外，与移除操作并发的搜索可以遍历移除的节点。因此，需要仔细证明一些相当弱的不变量足以线性化[24]。我们把证据画在第4.1节;详情见完整版[51]。4.1正确性我们表明，任何执行���的双向链表是线性化的。我们假设以下先决条件。当调用tryAppend（x，y）时，y是一个新节点，它以前从未被用作tryAppend的第二个参数，并且它不是sentinel节点。而且，x已经从head读取，y对于每个x，最多只能调用一次remove（x），并且只有在对tryAppend（x，*）的调用返回true之后才能调用它如果x和y是指向节点的指针，我们使用符号x y来表示y->left = x，xy表示x->right = y。我们用x=y来表示从y到x有一条左指针的路径。我们说，当头指针被设置为x时，x被添加到列表中。由于最多有一个以x作为第二个参数的tryAppend调用，因此在Python中最多有一个步骤将head设置为x。我们定义一个总数如果头指针在中被设置为y之前被设置为x，则在：xy期间添加到列表中的节点上的顺序 。下面的不变量捕获了一个节点和它的邻居之间的从本质上讲，它说左指针总是指向旧节点，右指针指向新节点。此外，如果其中一个指针跳过了一个节点，则跳过的节点必须标记为删除。 为了证明这些不变量，我们还需要对挂起移除的左、右局部变量进行类似的声明。不变量2。设 是一个构型，y是一个节点。1. 如果y已经被添加到列表中（并且不是哨兵），那么y->left也是添加到列表中的节点，y->left是y。 对于所有的w，如果y->left w y，则w被标记。2. 如果y->right在之前或之前的配置中为非空���，则���y->right中是添加到列表中的节点，y->right中是y。对于所有的w，如果y = w= y->right，则w是标记。3. 对于任何正在进行的对remove（y）的调用，局部变量left和right是已经添加到列表中的节点，left= y= right。此外，对于所有的w，如果left ≠ w ≠right，则w被标记。4. sentinel节点的左指针为空。头指针被初始化为sentinel节点，并且只能在第17行更新为非空指针。这个事实，不变式2和操作的先决条件意味着空指针永远不会被解引用。由于删除操作同时更新左指针，并且可能一次拼接出多个节点，因此存在一个删除操作可能撤销另一个删除操作的效果的危险。例如，假设我们有四个节点w xy z。如果remove（x）将y->left更新为w，同时remove（y）将z->left更新为x，则x仍然是可达的。下面的引理确保这不会发生。（事实上，它更普遍，因为它甚至适用于四个节点在列表中不连续引理3.假设在执行过程中的某个时刻，w_x_y_z和w_y。 那么就永远不会有x = z的时候。不变量2可以用来表明，每次左指针改变，它指向一个旧节点。引理4. 如果第32行执行CAS（z->left，y，w），则w =y。配置中的抽象列表是通过跟随左指针从头部可到达的节点的序列。接下来的三个引理确保节点x从一旦remove（x）终止，并且仅当remove（x）已被调用时，才返回。引理5意味着对左指针的更新只会从链表中删除元素：更新后的链表是更新前链表的子序列引理5. 如果第32行的CAS将z->left从y更改为w，则在前面的配置中w为y���。引理6. 从中删除节点时，将对其进行标记。72p qp q´8pqPPoPP'23，2023年2月25日至3月1日引理7. 当remove（x）终止时，x不在。这些引理可以用来验证下面的线性化是正确的。当一个成功的tryAppend更新头指针时，我们将其线性化 当第32行的CAS导致x从中移除时，我们将remove（x）线性化。 如果一个CAS删除了几个节点，我们将按降序对它们进行排序。因此，在任何时候，抽象列表同意到目前为止线性化的更新操作。下面的引理，需要技术证明，允许我们线性化搜索操作。引理8. 设 是一个配置，x是在中的未决搜索（k）的局部变量 。在调用搜索和 x在中之间有一段时间，x是中的第一个节点，或者它的前身在中有一个大于k的键。因此，我们可以线性化search（k），当返回的节点x是k中的第一个，key最多为k。一个tryAppend需要101个步骤。搜索是无等待的，而删除是无锁的。一个remove（x）操作需要1000步，其中1000是���在remove结束之前标记的包含x的������在这里，如果在remove（x）期间y<$z或y<$z，则y和z相邻。5 单链表压缩我们现在描述我们设计用于存储版本列表的简单单链表SSL（算法3）。每个列表节点存储一个版本，并且具有相关联的时间戳ts和指向前一版本的指针。 头指针存储最近附加的节点。与PDL类似，SSL提供了一个tryAppend和搜索操作。 节点以非递减顺序被附加到具有时间戳的列表，使得列表总是按时间戳排序。SSL提供了一个紧凑的操作，它遍历整个列表，拼接出过时的节点，而不是拼接出单个节点的删除操作。我们假设列表最初包含一个带有时间戳的哨兵节点，它总是保持在列表紧凑操作被给予由rtxs宣告的时间戳的排序列表A、从全局时间戳计数器读取的阈值时间戳t以及从版本列表的头指针读取的节点h，其指定从何处开始遍历列表以进行紧凑。我们在下面举例说明如何获得这些参数，以便与压缩并发或在压缩之后开始的任何rtx将具有在A中的时间戳（因为rtx的公告在A中）或大于或等于t（因为rtx在从全局计数器读取t之后获取其时间戳）。以下定义描述了压缩应保留的节点。需要一个节点x。到A和t（缩写为������������������A，t），如果（1）x。ts t，或者（2）x是最后一个附加节点，其时间戳最多为t，或者（3）对于某个列表元素Ar= s，x是最后一个附加节点，其时间戳小于或等于Ar s 。1class Node { Node* left;int ts; Value val;}2class AnnScan { Listint> A;int t;}3public void run（）{4AnnScan* newScan = new AnnScan;5重复两次{6AnnScan* old = GlobalAnnScan;7newScan.t = GlobalTimeStamp;8read Announce[1.. P]一个接一个，并排序到newScan. A;9ifCAS（GlobalAnnScan，oldScan，newScan）returnnewScan;}10returnGlobalAnnScan }11voidcompact（Listint> A，intt，Node* h）{//A被排序12A.appendFront（-1）; //padding13inti = A的最后一个元素的索引;14Node* cur = h;15while（cur！sentinel）{16Node* next = cur->left;17//跳过时间戳超过阈值t18if（t）{19return next;20}否则{21while（A[i] >= cur-ts）i--;22if（A[i] >= next->ts）{ //需要next23return next;24}else{ // next不需要25Node* newNext = next->left;26while（A[i] newNext->ts）{27new Next = new Next->left;}28同时（！CAS（（cur->left），next，newNext））{29next = cur->left;30if（next->ts = newNext->ts）break;}31cur = cur->left;}32public voidrun（Node* x，Node* y）{33return x;34return cases（head，x，y）;35public int findDuplicate（intk）{36Node* x = head;37while（x->ts > k）{38x = x->left;}39returnx->val;}算法3. 单链表（SSL）压缩例程。由于版本列表和A都是按时间戳排序compact使用类似于合并两个排序数组的算法来遍历版本列表和A，以确定列表中的哪些节点可以被删除。当找到一个可移动节点时，它将通过其前身的下一个字段上的CAS指令从列表中拼接出来。 如果发现多个连续的节点都是可移除的，则单个CAS会尝试将它们一次全部从列表中拼接出来。更详细地，compact的变量i和cur分别用作指向A和版本列表的指针，从最高保留时间戳和最新版本开始。第18第21行找到73pqPPoPPBlelloch，Panagiota Fatourou和Eric RuppertA的适当元素与cur的时间戳进行比较。第22 - 23行跳过一个节点，如果它是时间戳A[i]所需要的。第25紧凑例程首先在next之后找到第一个需要的节点，并将指向它的指针存储在newNext中（第25 - 27行）。然后，它尝试拼接出一个连续节点块，包括next，方法是在第28行将cur->left从next更改为newNext。 如果CAS失败，它会反复尝试将cur->left更新为newNext，直到成功或发现cur->left指向时间戳小于或等于newNext的节点。 一旦节点块被移除，压缩例程就沿着列表向下进行（第31行）。我们现在讨论如何获得紧致的论证。执行rtx的每个进程将其时间戳写入全局数组Announce。如果一个进程只是简单地将全局时间戳复制到t中，并在调用compact（A，t，h）之前将Announce元素逐个复制到本地副本A中，那么对列表的更新可能会表现得很奇怪。因为副本不是原子地制作的，所以两个并发的紧凑操作可能对所需节点的集合不一致：例如，如果列表中有4个节点x1，x2，x3，x4，时间戳为1， 2， 3， 4，一个紧凑可能认为需要x1，x3，x4，而另一个紧凑可能认为需要x1，x2，x4 这两个操作可能会分别拼接出x2和x3。 如果它们随后执行其CAS步骤以拼接出节点，则节点2将被第一操作的CAS移除，并且然后当第二操作的CAS发生时再次变得可达。我们希望避免这种情况，以保持良好的最坏情况空间边界。如果用作紧凑的起始点的头指针的副本h没有与A和t同时获得，则可能发生类似的问题。这个问题可以通过对全局时间戳、Announce和head进行原子快照来避免，但这太昂贵了。 不同进程用于复制全局时间戳和Announce的时间间隔不重叠就足够了。 这可以通过使用更轻量级的同步机