Crafty：高效、HTM兼容的持久事务操作技术

59Crafty：高效、HTM兼容的持久事务卡安·根尼俄亥俄州立大学（美国）osu.eduMichael D. 俄亥俄州立大学（美国）mikebond@cse.ohio-state.edu徐国庆UCLA（美国）harryxu@cs.ucla.edu摘要字节可寻址持久存储器，如Intel/Micron 3D XPoint，是一种新兴的技术，它弥补了易失性存储器和持久存储器之间的持久内存中的数据在崩溃和重启后仍然存在;然而，确保这些数据在故障后保持一致是一个挑战。现有的方法会产生显著的性能成本，以确保崩溃的一致性。本文介绍了Crafty，一种新的方法，用于确保一致性和原子性的持久性内存操作使用商品硬件与现有的硬件transsac- tional内存（HTM）的能力，同时产生低开销。Crafty采用了一种称为非破坏性撤销日志记录的新技术，该技术利用商品HTM来控制每个站点的顺序。我们的评估表明，Crafty在低竞争下优于最先进的先前工作，并且在高竞争下具有竞争力。CCS概念：·信息系统→存储类内存;·软件及其工程→并发编程结构。关键词：持久事务，事务内存ACM参考格式：作者：Michael D.邦德和徐国庆。2020年。Crafty：高效、HTM兼容的持久事务。在2020年6月15日至20日举行的第41届ACM SIGPLAN编程语言设计与实现国际会议（PLDI英国伦敦ACM，纽约，纽约，美国，16页。https://doi.org/10.1145/3385412.33859911介绍非易失性存 储器（NVM）技术，诸 如相变存储器（ PCM ） [ 38 ， 56 ， 61]、 电 阻 式 随 机 存 取 存 储 器（RAM）[38，56，61 ]、非易失性存储器（NVM）技术、非易失性存储器（RAM）[ 38，56，61 ]、非易失性存储器（RAM）[38，56，61]、非易失性存储器（RAM）[38，56，61]。允许使数字或硬拷贝的全部或部分本工作的个人或课堂使用是免费的，只要副本不得为牟利或商业利益而制作或分发，且副本的第一页须载有本通知及全文引用。版权的组成部分，本工作所拥有的其他人比作者（S）必须感到荣幸允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先 获 得 特 定 许 可 和 / 或 付 费 。 请 求 权 限 请 发 邮 件 至permissions@acm.org。PLDI'20，2020年6月15日至20日，英国伦敦© 2020版权归所有者/作者所有。授权给ACM的出版权。ACM ISBN 978-1-4503-7613-6/20/06。. . 15美元https://doi.org/10.1145/3385412.3385991存储 器（RRAM ）[55]、自 旋转 移矩存 储器 （STT-MRAM）[35]和3D XPoint [26]被设计为将DRAM的字节寻址能力和存储的耐久性结合在一起因此，NVM有可能从根本上改变DRAM和持久存储之间的二分法在许多重要领域，如存储系统[24，36，58，59，63]，数据库[1，2，25，64]，和大规模存储系统[24，36，58，59，63 ]数据分析[53]。与任何存储系统一样，有效使用NVM的第一个挑战是提供崩溃一致性[44，52]，这允许程序在故障时正确地从持久性数据恢复。崩溃一致性通常是通过在高级编程模型中利用事务支持来实现的开发人员指定持久事务，其中对持久存储器的更新在程序崩溃时看起来是一个原子单位，这些更新中的全部或全部都不被提交，从而确保重要的数据结构始终保持一致的状态。然而，先前的工作首先，所有机制--撤销日志记录[9，32]、重做日志记录[52]和写时复制[7，15，39，43，57]--都会导致性能成本，例如每次写入时的持久延迟、程序读取时的查找、影子内存的维护以及较差的多线程可扩展性。第二，虽然商品硬件事务存储器（HTM），如英特尔的事务同步扩展（TSX）[21，22，60]是一个有吸引力的机制，用于提供持久性事务，以实现完整的ACID事务，持久性事务机制是不兼容的商品HTM，因为以下困境：为了确保正确的恢复，日志条目必须在事务提交之前持久化，但事务的性质决定了执行事务不能执行持久化操作。尽管最近的一些工作展示了如何使硬件事务持久化[3，4，7，15，16，39，54]，但它有主要的缺点，例如需要在读取时进行日志查找，使用影子内存，引发可扩展性瓶颈，或依赖于重要的硬件更改（第2节）。捐款. 本文通过利用商品HTM来控制按需排序，解决了先前工作的两个我们介绍了一种新的持久性事务机制，非破坏性撤销日志，利用商品HTM填充和持久撤销日志之前，PLDI作者：Michael D.邦德和徐国庆60使持久写入可见。在硬件事务中运行持久事务的代码并在撤销日志记录中记录持久写入的非破坏性撤销日志记录的关键在于，硬件事务在提交之前回滚其持久写入，从而有效地创建其撤销日志条目而不执行实际的持久写入。 此行为通过将撤消日志更新与持久写入分离，打破了上面提到的HTM的持久提交依赖循环。在提交其计算撤销日志条目的硬件事务之后，持久事务可以执行其持久写入，尽管是以与持久撤销日志条目和其他线程的持久事务一致的方式我们采用无损撤销日志引入狡猾，一种新颖的和通用的方法，正确和有效的持久性事务使用未经修改的商品HTM。对于每个持久事务，Crafty首先使用非破坏性撤销日志记录来计算和持久化撤销日志条目。然后，它通过以下方式执行事务Crafty可以在仅提供故障原子性的线程不安全模式下操作（依赖于一些其他机制，例如线程原子性的锁），或者它可以在提供故障和线程原子性的线程安全模式下操作（即，ACID交易）。我 们 通 过 扩 展 NV-HTM 的 公 开 可 用 实 现 来 实 现Crafty[7]，NV-HTM也实现了DudeTM[39];这两种方法都支持使用基于影子内存的写时复制机制与HTM进行我们的评估使用了几个程序不同程度的线程争用：持久事务微基准和事务基准。我们的研究结果表明，Crafty优于两个国家的最先进的基于HTML的持久事务实现NV-HTM和DudeTM，特别是在低线程争用。此外，Crafty通常在非持久事务上增加较低的运行时开销，并且其开销主要是线程本地的，因此可以很好地随额外的线程扩展。这些结果表明，非破坏性撤销日志和Crafty是提供高效，HTM兼容的持久事务的有前途的方法。2背景和动机本节介绍了持久内存编程模型的背景，并激发了对持久事务更好机制的需求2.1持久内存编程模型支持持久性内存的关键挑战是确保在发生故障时，恢复观察器可以将持久性内存恢复到重新启动后可用的状态程序.这种属性通常通过故障原子性提供：在崩溃或电源故障的情况下，持久内存状态可以恢复，以便每个持久事务看起来已经完全执行或根本没有执行[5，7-19，18，23，27，39，41]。此外，多线程程序通常需要线程原子性-持久事务相对于其他线程原子地执行-恢复观察器重构的状态应该与持久事务的提交顺序一致。具有持久事务的程序可以通过使用锁[8，18，23]或通过使用事务内存[7，9，15，39，52]来提供线程原子性，在这种情况下，事务具有完整的ACID属性。要求. 持久事务的实现必须确保，崩溃后，恢复观察者可以恢复程序例如，如果事务恢复发生在事务恢复之前，则恢复的状态必须对应于以下三种执行场景之一：（1）在事务恢复之后执行恢复，（2）仅执行恢复，或者(3)根本没有交易执行此外，恢复状态应该对应于距离崩溃时间不太远的时间点。否则，需要重新执行的工作量可能太大而不实用。2.2持久事务机制在崩溃或电源故障时，恢复观察器必须重建一个状态，在该状态下，事务似乎已经完全执行或根本没有存储不会按照其发布顺序到达持久性内存，这一事实加剧了这一挑战这是因为处理器缓存有效地缓冲写入，直到驱逐或显式写回脏行到持久性内存。为了确保存储按顺序到达持久内存，可以使用持久操作。持久化操作由一个或多个刷新操作组成，缓存行到持久存储器，然后是一个漏操作，等待直到刷新操作完成的操作。在x86上，刷新可以用CLWB （ 缓 存 行 回 写 ） 指 令 实 现 ， 而 排 空 可 以 用SFENCE（存储围栏）指令实现[49]。持久化操作的开销很大，因为它会引发往返写操作NVM的延迟，预计为几百纳秒[38，50]。即使NVM控制器缓冲持久存储并且包括缓冲器作为持久域的一部分[49]，持久延迟（即，用于与NVM控制器的往返通信的时间如果能够开发出一种商品化的方法，在许多持久性写入中有效地分摊持久性延迟，那么就可以从持久性域中删除缓冲区，从而简化未来的硬件设计。Crafty：高效、HTM兼容的持久事务PLDI61失败_原子{int sum = 1;...= dq;in tsum=2;}(a) 持久事务undoLog.app end （ p ，p ） ;flush （ last logentry）;drain;int sum = 1;...= dq;undoLog.app end （ r ，r）;flush（最后一个日志条目）;drain;in tn=2;undoLog.append（）;(b) 撤销应用于（a）的return（p，1）;... = redoLog.lookup（q）;redoLog.put（r，2）;redoLog.append（COMMITTED）; foreachentryin redoLogreturn（）;排水;foreachptr，val> in redoLogreturnval;(c) 重做日志记录应用于（a）int n = 1;// 阴影线return（p，1）;...//返回上一页 读取阴影r=2;//writesshadowreturn（）;排水;foreachptr，val> in redoLog//写入 永久地址StringgetPersistAddr（ptr）= val;(d) 写入时复制适用于（a）图1. 为了在（a）中为持久事务提供故障原子性，系统使用以下崩溃一致性机制之一：（b）撤销日志记录，（c）重做日志记录，或（d）写时复制。所有位置的初始值均为0。持久性事务通常使用以下三种机制之一来提供崩溃一致性：撤销日志记录[9，32]，重做日志记录[52]和写入时复制[7，39，43，57]。Marriott等人定量地比较了这些机制，发现没有一种机制在所有情况下都是明显的赢家（例如，跨线程计数或事务大小）[41]。在这里，我们描述每种机制及其缺点。我们使用图1（a）作为一个简单的持久事务示例。撤消日志记录。 在撤消日志记录中，持久事务在存储器存储更新持久位置之前将该位置的旧值记录在持久撤消日志中。撤销日志记录支持快速读取访问：由于每个存储执行就地内存更新，因此任何内存加载都可以直接从持久内存中读取最新值，而无需重新映射到不同的地址。然而，为了确保崩溃后正确的回滚，实现必须持久化（即，在写入到对应的持久性存储器位置之前，对撤销日志的每次更新进行刷新和排出（flush and drain），导致每次NVM写入的高写入等待时间。图1（b）显示了图1（a）中的持久事务的撤销日志记录是如何为了发出持续事务日志条目结束的多线程实现可以包括具有COMMITTED条目的时间戳（图中未示出），以使恢复观测器能够重建与某个全局一致的时间点相对应的状态。重做日志记录。相比之下，重做日志记录不是对持久性内存执行就地更新，而是缓冲所有持久性写入并在事务结束时一起执行它们。通过缓冲写入，重做日志记录仅在每个事务结束时支付一次持久化排序的成本但是，它为每次持久读取增加了开销，因为读取需要在一组缓冲写入。由于读操作的数量通常远远超过写操作，重做日志记录也会带来很大的开销。图1（c）说明了重做日志是如何对持久性存储器的写入和读取分别被替换为对基于映射的日志的更新和查找，使得对持久性存储器的读取正确地从任何先前的写入读取。写时复制最近的工作提出了写时复制机制，该机制为每个要修改的持久性页面维护一个volatileshadow [7，39，43，57]。我们专注于使用影子分页的写时复制机制，因为它允许有效的就地写入。其他写时复制机制使用间接方式在事务中的第一次写入时复制对象，产生类似于重做日志记录的成本[15，41]。持久事务正常地执行读取和写入，因为虚拟地址被映射到物理易失性影子存储器地址。在事务结束时，对每个影子页的更改都持久化到其对应的非易失性页。图1（d）显示了这一机制的工作原理。虽然写时复制技术享有撤销和重做日志记录的性能优势，并且可以与商品HTM兼容，如简短描述的那样，但是遮蔽整个NVM是昂贵且不切实际的。最重要的是，写时复制机制必须确保对易失性页和非易失性页的更新之间的一致性，解决可扩展性瓶颈，如下所述。2.3事务存储器实现提供完整ACID属性的持久事务的一种自然方法是利用事务特性[21，22]。大部分关于持久事务的现有工作扩展了软件事务存储器（STM）[20]，这在检测和解决并发事务之间的冲突时引起了很高的开销。硬件事务存储器（HTM）在硬件级别检测和解决冲突，是实现高效持久事务的一种有吸引力的技术。PLDI作者：Michael D.邦德和徐国庆62然而，商品HTM实现，包括英特尔由于日志更新必须在内存更新之前发生，因此存在一个明显的困境：一方面，撤销或重做日志条目必须在硬件事务提交实际内存更新之前持久化（以确保崩溃一致性），而另一方面，事务的性质规定这些日志条目不能在事务提交之前持久化，否则它们不能在中止时被撤销。日志条目的更新和实际的内存更新相互依赖，形成了一个依赖循环，似乎阻碍了持久事务使用HTM。最近的方法使用商品HTM的持久化事务，从HTM的并发控制解耦持久化。DudeTM[39]和NV-HTM[7]展示了写时复制机制如何支持基于HTM的持久事务。硬件事务对影子内存执行就地读写。在事务提交之后，重做日志条目可以在将事务的写入复制到持久性存储器之前被持久化。此外，通过异步地将重做日志条目和程序写入持久存储器，可以组合对相同持久位置的写入。然而，缺点是DudeTM和NV-HTM在维护影子状态和保持对持久性存储器的更新与写入易失性影子状态的事务的顺序一致方面具有显著的缺点。首先，如上所述，这些方法通过维护程序状态的两个副本来增加空间开销。其次，它们必须确保在事务内部写入DRAM的顺序与在事务结束时写入NVM的顺序之间的一致性。 DudeTM通过递增商品HTM中的全局变量来计算时间戳，使其与商品HTM有效地不兼容[39]。另一方面，NV-HTM与未修改的commodity HTM一起工作，但它有两个主要的可扩展性瓶颈，限制了更高线程数的性能[7]。首先，每个持久事务只有在其他所有正在进行的事务完成后才能完成具体地，每个事务不能将COMMIT条目写入其重做日志，直到它确保没有正在进行的事务仍然可以写入用于较早事务的COMMIT条目，因为重做日志被恢复观察器用于在崩溃之后前滚持久状态等待确保如果恢复观察器看到某个事务的COMMIT条目，它也会看到所有早期事务的COMMIT当然，这会带来开销。第二，将日志和程序写入持久化内存的线程必须以序列化的方式进行在NV-HTM中，异步后台线程将事务的写入（基于其重做日志条目）按时间戳顺序应用这一系列的写入持久存储器是事务记录时间戳（为了效率）的事实所固有的，从该时间戳中只能推断出全局事务顺序。DudeTM论文推测，将持久性与HTM解耦可能是避免撤销和重做日志记录的缺点并减少性能损失的最佳（也可能是唯一）方法[39]。我们的工作旨在反驳这一假设，并克服现有持久事务机制的性能缺点3Crafty概述正如2.3节所解释的，在实现持久化事务时，阻碍商品HTM有效使用的主要障碍是依赖循环，这是由日志条目更新和程序内存更新的紧密耦合引起的：如果硬件事务包含这两种类型的更新的混合，它既不能在持久化之前提交，也不能在提交之前持久化。为了解决这个问题，我们引入了一种新的持久化事务设计，称为Crafty，它利用了一种新的日志记录机制，称为非破坏性撤消日志记录。Crafty成功的关键是通过在单独的硬件事务中执行日志条目更新和程序内存更新来打破持久性提交依赖循环，有效地解耦这两种类型的更新。在非破坏性撤销日志记录中，硬件事务执行日志阶段，该阶段以仅更新撤销日志条目而不更新程序的持久数据的方式执行持久事务。这些日志条目在硬件事务提交后持久化。接下来，Crafty使用另一个硬件事务执行程序写入这些写入的执行方式与日志条目的更新以及其他线程执行的事务一致挑战和见解。 实现正确和高效的设计提出了三个主要挑战。第一个挑战是如何使日志阶段只更新撤消或重做日志条目，而不修改程序内存位置。为了克服这个挑战，Crafty在执行日志阶段时使用了撤销日志：在每次写入持久内存位置之前，该位置的旧值被记录在线程本地撤销日志中。在事务结束时，Crafty通过以相反的顺序应用撤消日志的条目来回滚所有这些写入，有效地将修改后的值设置回事务执行前的原始值此外，在此回滚过程中，当旧值和新值都可见时，硬件事务为这些位置构建重做在日志阶段提交之后，所有撤销日志条目都被持久化到持久内存中。图2显示了Log阶段如何使用非破坏性撤消日志记录为图1中的持久事务构造撤消日志。第二个挑战是如何以与要记录的更新相同的顺序执行程序Crafty：高效、HTM兼容的持久事务PLDI63HTM_BEGIN;int findDuplicate（）;int sum = 1;...= dq;int n= nums（r，n）;in tsum=2;foreachentry< ptr，oldVal> in undoLog inreverseredoLog g. intn =nums（nums，nums）;//unload/unload/unloadHTM_END;undoLog中的foreach条目return（）;drain;//持久化撤消日志条目/你...事务/return（）;图2. Crafty的崩溃一致性机制（非破坏性撤销日志记录）如何条目为此，Crafty启动第二阶段，更新程序内存位置。从理论上讲，我们所需要的只是一个重做阶段，日志阶段的结束。如果持久化事务由悲观技术（如锁定）保护，则这种天真的方法将有效，因为不同线程执行的事务将相互冲突。然而，如果持久事务可能发生冲突，则在两个单独的硬件事务中执行的线程这可能会导致日志条目与其相应内存位置中的内容之间的不一致。为了解决这个问题，Crafty让Redo阶段基于时间戳检查保守的冲突约束此检查失败是事务冲突的必要但不充分的条件。为了保证安全，Crafty会中止执行此重做阶段的HTM事务。第三个挑战是当重做中止时该怎么办由于我们的冲突约束的保守性质，重做中止不一定表示真正的冲突。因此，当且仅当Redo中止时，Crafty在阶段处执行V a l i d，其重新执行持久事务以检查在日志阶段中持久化的撤销日志条目的有效性。如果所有撤消日志项仍然有效，则事务成功，允许内存写入提交并对其他线程可见。日志条目中的值与其对应的日志位置之间的任何不匹配都会使ValI date中止，这表示在当前线程的日志阶段完成之后，另一个线程已提交了新的冲突写入被中止的线程通过重新执行日志阶段并构造新的撤消和重做日志来启动覆盖，从而处理这种情况。纲要第4节描述了Crafty如何执行持久事务以在运行时提供原子性并支持崩溃时的第5节描述了恢复如何在崩溃后恢复持久状态4Crafty如何执行交易本节介绍Crafty如何利用非破坏性撤消日志记录来执行持久事务。执行模式。 Crafty可以在两种模式中的任何一种下运行。在其线程安全模式（本文的重点）中 所有ACID属性）。Crafty在这种模式下，程序员可以显式地或以Crafty形式指定事务边界，以将所有临界区[5，8，23，27，40]或无同步区域[18]视为持久事务。图3和图4分别显示了Crafty如何在线程安全和线程不安全模式下运行（第3节）。第4.1节和第4.3节详细描述了Crafty线程安全模式下的日志、重做和验证日期在线程安全模式下，重复的中止会导致Crafty在持有单个全局锁（SGL）的同时转换到线程不安全模式，如图3所示和4.4节所述。本节的其余部分使用图5作为示例来展示Crafty是如何工作的。4.1对数相Crafty这里的关键处理是日志阶段不提交任何程序写入持久内存。日志阶段通过允许持久事务在其执行期间正常执行写入，但在硬件事务提交之前回滚写入来实现此结果算法1显示了日志阶段的详细信息，该阶段在硬件事务中执行持久事务主体。在每次持久写入之前，日志阶段在执行线程的持久撤消日志中记录写入地址的旧值。例如，在图5中，每个持久事务在事务结束时，日志阶段使用撤消日志条目回滚事务当回滚写时，Crafty同时为事务构建一个易失性重做日志，该日志可由后续重做阶段用于执行程序写。例如，在图5中，从"开始回滚：恢复“注释开始，持久事务在提交PLDI作者：Michael D.邦德和徐国庆64成功验证失败回退只读失败成功验证阶段成功结束持久事务重做阶段线程不安全模式下基于SGL的执行低G相最多可写入低G阶段，启动持久事务Thread 1 Thread 2回退atomic_and_durable{n = n;in t sum=1;}atomic_and_durable{int n = 2;return 3;}(a) 两个持久性交易。Thread 1 Thread 2日志阶段：HTM_BEGINundoLogT1。add（0）p =undoLogT1。add（r，0）1.1.1.1.1.1.1.1.1.1.1.1.1.1// 开始 回滚：redoLogT1。add（r，1）/ / fr=0//fromundologredoLogT1。add（0）//从撤消日志中删除lastTST1 = ts（）图3. 线程安全模式下的Crafty启动持久事务;MAX_WRITES持久写入（如果n=1）持久性写入undoLogT1。add（LOGGED，lastTST1）HTM_END重做阶段：HTM_BEGIN日志阶段：HTM_BEGINundoLogT2。add（q，0）q = 2undoLogT2。add（s）S = 3// 开始 回滚：redoLogT2。add（s，3）Undo = 0//来自撤消日志redoLogT2。add（q，2）Undog = 0//来自undo log...成功（如果n>1）故障失败成功在持久写入事务结束结束持久事务检查gLastRedoTS lastTST1Rewrite = 0//来自重做日志r=1//fromredologgLastRedoTS = ts（）undoLogT1。add（提交，gLastRedoTS）HTM_ENDlastTST2 = ts（）undoLogT2。add（LOGGED，lastTST2）HTM_END重做阶段：HTM_BEGIN// redocheck gLastRedoTSlastTST2ABORT//检查失败图4. Crafty对于硬件事务，日志阶段添加一个具有Lamport时间戳1的LOGGED条目，表示当前逻辑时间（相当于开始时的逻辑时间因为HTM确保原子性）。恢复将使用这些时间戳对不同线程的撤消日志条目进行排序在图5中，每个Log阶段都在提交硬件事务之前将一个LOGGED条目插入到撤消日志中提交事务后，日志阶段将事务的撤消日志条目刷新到持久性内存中。该算法刷新事务1如果两个事件按happens-before排序，则它们的逻辑时间相应地排序[37]。第二阶段：HTM_开始check blog == 0// from undo logq = 2check until == 0//从撤消日志S = 3check # writes == # log entriesgLastRedoTS = ts（）undoLogT2。add（提交，gLastRedoTS）HTM_END(b) 在（a）中的持久事务的可能执行使用在它的线程安全模式下是狡猾的，它提供了所有的ACID属性。图5. Crafty的线程安全模式执行持久事务的示例*p、*q、*r和*s的初始值为0。该示例省略了冲洗和排水说明。2start;开始←开始返回上一页对数相位执行直到持久写入或事务结束重做阶段记录阶段Crafty：高效、HTM兼容的持久事务PLDI65算法1日志阶段1：HTM_BEGIN持久事务的开始. . .程序写入持久变量：2：将URL addr，oldValue URL添加到T. undoLogT是当前线程3：*addr=newValue原始程序写入. . .持久事务4：使用T.undoLog回滚事务5：将LOGGED，getTimestamp（）添加到T.undoLog6：HTM_END7：flush（此交易的T.undoLog而不是等待它们被写回到持久存储器（即，刷新但不排出），因为程序写入将由硬件事务内的Redo或ValI日期阶段提交，其具有排出语义（例如，RTM事务具有SFENCE语义）。日志阶段完成后，事务已经被持久化，但是从其他线程和存储器的角度来看，该事务实际上没有被执行，因为没有执行任何存储器更新在图5中，Log阶段完成后，*p，*r，*q和*s仍然具有它们的初始值（0）。把这些编出来-对其他线程和持久内存可见的日期，使用“重做”或（如果需要）“验证日期”阶段。只读事务不需要向撤消日志添加LOGGED条目或执行任何持久化操作，并且它可以跳过Redo和ValI date阶段，如图3所示。4.2重做阶段重做阶段应用来自重做日志的写入（以它们在日志阶段中被记录的相反顺序），如算法2所示。如果程序是单线程的，或者没有其他线程访问持久内存，那么无条件地执行重做阶段是安全的。但是，如果多个线程正在执行持久事务，则可能违反原子性例如，线程B因此，确保A的Redo阶段仅在与其先前的Log阶段一起原子地执行时才完成是很重要的为此，Crafty使用了一个全局变量gLastRedoTS，该变量表示任何螺纹. 图5演示了如何更新和使用gLastRedoTSCrafty在线程1的重做阶段开始时检查gLastRedoTS检查成功，因为没有线程自线程1的日志阶段以来已提交写入然后，重做线程1通过更新gLastRedoTS来完成重做阶段，将带时间戳的已提交条目添加到日志。这算法2重做阶段线程安全重做阶段：1：HTM_BEGIN2：如果gLastRedoTS<日志阶段的日志时间戳然后3：gLastRedoTS←getTimestamp（）4：执行线程不安全的重做阶段5：else6：中止事务并失败重做阶段7：如果结束8：HTM_END9：同花顺位（写入地址）线程不安全重做阶段：10：从重做日志11：如果不在硬件事务中，则12：刷新（写入地址）13：如果结束14：将提交，getTimestamp（）添加到T.undoLogtimestamp表示事务的写入相对于其他线程的事务发生的时间失败的检查指示潜在的原子性冲突。在图5中，线程2对gLastRedoTS的检查失败，因为线程1更新了gLastRedoTS，以反映它在线程2的日志阶段之后提交了写入（在其重做阶段）。线程2（或者，在不同的定时下，线程2线程1将使重做失败阶段并尝试ValI date阶段，重新执行transaction并将*q，2的更新值写入*p。）如果成功，则恢复阶段结束时刷新事务冲洗但不排水）。下一个如果它的写入没有完全持久化（第5节）。所有事务的重做阶段都有效地串行化。这并不一定会导致性能瓶颈，因为Redo阶段通常很短，并且可以与Log和ValI date阶段并发执行。4.3第一阶段ValI日期阶段的目标是执行与持久化的撤消日志条目一致的持久化事务。ValI日期阶段通过将撤销日志中记录的旧值与相同位置的当前值进行比较来检查一致性，如算法3所示。ValI日期阶段检查对于每个程序写入，其在撤销日志中的对应条目是否匹配写入如果是这样，PLDI作者：Michael D.邦德和徐国庆66算法3确认日期阶段1：将T.undoLog重置为事务的开头2：HTM_BEGIN永久事务. . .程序写入持久变量：3：让t.expectedAddr，expectedValue作为T.undoLog中的下一个条目4：如果addr_expectedAddr_*addr_expectedValue，则5：中止交易并验证失败6：如果结束7：*addr←newValue原程序编写. . .永久事务8：检查T.undoLog中的下一个条目是否为LOGGED条目（如果不是，则中止事务并使验证失败）9：gLastRedoTS ←getTimestamp（）10：在T.undoLog中的记录的项11：HTM_END12：刷新（写入地址）暗示撤消日志条目的有效性例如，在图5中，线程2的Val i日期阶段检查对q和s的写入是否与撤消日志中的原始地址和旧值匹配，并且是否没有新的年底在持久事务中，硬件事务被提交，并且写入被持久化并且对其他线程可见。请注意，重要的是通过验证撤消日志条目而不是仅执行写操作来重新执行事务，以确保（隐式地）事务读取的值仍然与撤消日志条目一致与重做阶段一样，在执行写入操作之后，Crafty向日志中添加一个已提交的getTimestamp（）条目，该条目表示事务的写操作与其他线程相关请注意，只有当Redo阶段失败时，才会执行ValI日期阶段。每个持久性事务都只提交一次写入，无论是Redo还是ValI日期阶段。4.4单一全局锁定回退硬件事务可能会由于各种原因而中止，包括与其他线程的冲突，缓存容量溢出或不受支持的事件，如中断[60]。由于商品HTM通常不提供进度保证，因此必须特别注意确保执行取得进展。如图3所示，CraftySGL有两个目的。首先，它消除了不同线程之间的冲突。其次，它允许Crafty在线程不安全模式下执行，其中Crafty可以执行更短的硬件事务（更少的指令）或不执行硬件事务以确保进度。SGL是一个全局变量，线程通过将其原子地从0更新到1来获取它，并通过将其设置为0（使用适当的内存屏蔽）来释放它。为了确保与在线程安全模式下执行硬件事务的其他线程的一致性这种处理确保了与正在进行的SGL部分或在事务执行时启动的SGL部分的一致性（因为事务的读取集包含SGL）。这种回退方法在文献中被称为推测性锁省略，并且已经被广泛研究[28，46，60]。在获得SGL之后，线程可以在Crafty在这种模式下，SGL确保原子性，因此HTM仅用于实现非破坏性撤销日志记录（即，以防止更新的高速缓存行过早地写回到持久存储器），而不是为了线程原子性。因此，线程不安全模式仅在日志阶段使用硬件事务，该阶段可以等到持续事务的第一次持久写入才开始线程不安全模式不使用HTM因 为 没 有 其 他 线 程 可 以 更 新 全 局 时 间 戳gLastRedoTS，因此该阶段总是成功。根本不需要验证确保取得进展。即使没有来自其他线程的争用，硬件事务仍可能由于高速缓存容量或其他原因而中止。线程不安全模式下的日志阶段可以通过将持久性事务分解为较小的硬件事务来确保进度，每个事务最多执行一次持久性写入。在执行了持久性写操作之后（如果持久性事务在达到持久性写操作之前结束，则执行更少的持久性写操作），日志阶段将正常完成，回滚写操作并持久化撤消日志条目（包括LOGGED入境然后，Redo阶段将按以下时间点（或更少时间点）持续写，除了它不添加一个提交条目，它只应该用于指示（基于SGL的）事务的结束。 Log和Redo阶段继续执行持久性事务，以块的形式进行 写入。如果log=1，则日志阶段在执行写入内存之前写入并持久化撤消日志条目，而不使用任何硬件事务。当进入线程不安全模式进行持久性事务时，Crafty以一个（相对较大的）值“0”开始（例如，64)其目标是跨多个写入分摊持久延迟。在线程不安全模式下，每次事务性中止后，Crafty在下一次硬件事务性中呈几何级数下降当token的值降为1时，保证线程不安全模式可以继续进行。图4说明了线程不安全模式的逻辑，该模式在写入块直到完成。Crafty：高效、HTM兼容的持久事务PLDI67在释放SGL之前，Crafty会将一个COMMITTED条目添加到持久性撤消日志中。SGL部分的所有硬件事务的LOGGED因此，Crafty自适应地调整事务大小，以在持久化延迟和中止风险之间进行权衡在其他背景下，以前的工作将交易拆分为每笔交易成本和中止成本之间的平衡[42，51]。5如何巧妙地恢复崩溃本节介绍Crafty的恢复逻辑。我们首先描述在无限对数初始为零的假设下如何进行恢复（即，没有回绕或重用），并且日志条目被原子地持久化。然后，我们将展示如何在没有这些简化假设的情况下处理日志。5.1基本恢复逻辑在上述假设下，恢复对象服务器可以检测持久化条目，其是具有非零地址字段（其是地址或日志）或COMMITTED标签）。一个完全持久化的序列是一个连续的，持久化的日志addr，oldValue条目的有效序列，其前面是（持久化的）LOGGED或COMMITTED条目，后面是持久化的LOGGED条目。恢复观察器需要完全回滚最后一个因为一些相应的写入可能已经被持久化，但不是所有的写入都肯定地被持久化。设“已登录”为序列然后我们定义一个序列是ts。为了获得全局一致的快照，恢复观察器还必须回滚时间戳晚于或等于被回滚的任何序列的时间戳的每个序列在完全持久化序列之外的任何持久化条目都不能回滚，因为它们对应的写入肯定没有持久化。若要回滚序列，恢复观察器将以相反顺序删除addr，oldValue条目，执行*addr=每个条目的oldValue。恢复观察器以相反的时间戳顺序回滚5.2处理高性能电缆接下来，我们将讨论Crafty如何在没有简化日志假设的情况下提供正确的恢复。下面的设计处理重用条目的循环日志，并且它不需要原子地持久化日志条目。该设计还解决了迄今为止Crafty设计的限制该设计假设系统提供字（或更粗）粒度的持久性。该设计依赖于每个线程区分重用的条目。为了处理撤消日志条目的重用（例如，通过循环日志），恢复观察器需要能够分辨条目“addr，oldValue”是来自最新的事务还是来自日志的最后一次回绕。受先前机制的启发[10]，Crafty事务处理维护每个线程的回绕位，该回绕位被编码在每个字中，并且在每次日志回绕时翻转。此回绕位允许恢复区分在最新日志回绕之前和之后写入的字由于记录的事务比回绕发生的频率更高，因此恢复只能观察下一个最新回绕之后的日志条目，因此单个回绕位就足够了。我们进一步假设所有地址都是字（4或8字节）对齐的。这使我们能够在每个Addr，Value日志条目中窃取两个或三个位的Addr字其中之一是用作环绕位。记录和提交-每个TED标签都表示为保留的对齐地址。因为NVM仅保证在字粒度上提供持久性，所以在一个“地址，值”日志条目中的值字也将需要一个环绕位。然而，value需要它的所有位用于程序值。因此，我们在每个地址字中窃取另一位来存储位（例如，最低位），从而允许值字的相同位被环绕位替换。丢弃条目和限制回滚严重性。为了使Crafty通过循环日志），我们必须能够丢弃恢复观察器不再需要的一些条目。由于Crafty不能丢弃需要回滚的日志事务的条目，因此我们需要确保最早可能的回滚时间戳ts大于Crafty准备丢弃的日志事务的时间戳。我们在这里解决的一个相关问题是限制恢复观察器必须回滚到多远的时间。如果线程有一段时间没有执行持久事务，则该距离可能相当远。日 志 记 录 算 法 维 护 一 个 全 局 时 间 戳 tsLow-erBound，它是恢复可能需要回滚到的最早可能时间戳的下限这是一个较低的绑定，因为出于性能原因，它是惰性地保持最新的。当向其撤消日志添加LOGGED条目时，线程检查currentTS（）ts下限+MAX_LAG其中MAX_LAG表示恢复可能需要回滚的可自定义最大持续时间，currentTS（）是表示当前时间的时间戳。PLDI作者：Michael D.邦德和徐国庆68类似地，每当线