TL4x：磁盘上的缓冲式持久事务处理与内存中的一样快

2450TL4x — 使用磁盘上的缓冲持久事务与内存一样快0以色列理工学院加尔∙阿萨galassa@campus.technion.ac.il0瑞士纳沙泰尔大学安德烈亚∙科雷亚andreia.veiga@unine.ch0思科系统瑞士公司Pedro Ramalhetepramalhe@gmail.com0瑞士纳沙泰尔大学瓦莱里奥∙斯基亚沃尼valerio.schiavoni@unine.ch0瑞士纳沙泰尔大学帕斯卡尔∙费尔贝尔pascal.felber@unine.ch0摘要0持久性内存设备的出现使事务性持久算法重新引起了人们的兴趣。持久性内存（PM）被宣传为具有字节寻址和快速事务持久性的两个属性，与其他存储技术有所区别。在这项工作中，我们研究了这些属性在缓冲持久性的上下文中如何将PM与块存储区别开来。我们提出了一种新颖的算法TL4x，能够提供缓冲持久性的线性化事务，并在PM或块存储设备上实现高扩展性的不相交写入和高效持久性。TL4x是一种仅基于软件的用户空间解决方案，它优化对持久性存储的写入，提供的缓冲持久性事务的成本与类似的非持久性事务相比可以忽略不计。TL4x始终保持一个易失性一致的快照，该快照用于缓冲持久性并与不可撤销的只读事务共享，允许长距离查询操作与写入事务并行运行。我们使用TL4x实现了一个事务性数据库引擎，其性能超过RocksDB一个数量级。0CCS概念: •  计算方法学 → 并发算法。0关键词：持久性内存、事务、缓冲持久性、磁盘持久性0未经ACM许可，您可以将本作品的所有或部分内容以个人或课堂使用为目的进行数字或印刷复制，但不得以盈利或商业利益为目的进行复制或分发，并且复制件必须带有本声明和第一页的完整引用。必须尊重ACM拥有的本作品组件的版权。允许带有来源标注的摘要。复制或重新发布，发布在服务器上或重新分发到列表上，需要事先获得具体的许可和/或支付费用。请向permissions@acm.org申请权限。PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，版权所有©2023年计算机协会。ACM ISBN 979-8-4007-0015-6/23/02...$15.00https://doi.org/10.1145/3572848.357749501 引言0持久性主存储器引起了学术界和工业界对高效持久性事务算法的兴趣。PM，也称为非易失性主存储器（NVMM），被宣传为比块存储设备具有两个重要优势的技术:PM具有较低的持久性延迟并且是字节寻址。第一个优势在需要持久性事务时非常重要。通常，一个事务修改少量数据，但随后会将至少一个4kB页写入磁盘并发出至少两个fsync()调用[33,46]。当在磁盘（SSD和HDD）上执行此过程时，速度非常慢，因此没有事务引擎默认使用它。相反，包括RocksDB[39]、Cassandra[2]、WiredTiger（MongoDB的存储引擎）[41]和CockroachDB[32]在内的大多数商业和开源数据库管理系统（DBMS）在将数据持久化到磁盘时默认提供缓冲事务，即某些已提交的事务在系统崩溃时可能会丢失。这表明缓冲的持久性事务可以满足广泛范围的用例。第二个优势，字节寻址，允许以更细粒度进行访问，并从编程和硬件角度都被认为是有益的。虽然这被认为是PM的独有功能，但我们表明通过使用由磁盘存储支持的DRAM，可以实现字节寻址。在这项工作中，我们提出了一种新颖的持久性事务内存（PTM）框架TL4x。TL4x是一个可扩展的通用PTM，当持久化到PM或传统块设备时，与非持久性性能相比，它的开销可以忽略不计。TL4x的设计不需要预写日志，预写日志已被用于至少30年的DBMS中实现持久性事务[40]（例如，MicrosoftHekaton的重做日志[11]、MySQLInnoDB引擎[42]、PostgreSQL [48]和Oracle DB[35]，或SAPHANA的重做日志和影子副本[14]）。相反，我们的技术始终保持两个易失性数据副本，其中一个副本可能在任何给定时间被冻结以包含一致的数据快照。这个快照更新功能是保持事务的持久性的关键。2460PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加尔∙阿萨，安德烈亚∙科雷亚，佩德罗∙拉马尔特，瓦莱里奥∙斯基亚沃尼和帕斯卡尔∙费尔贝尔0背景线程使用一致性副本将数据复制到持久性存储中，而读取和写入事务在另一个副本上继续执行。无论底层的非易失性存储以及持久化数据所需的时间如何，使用这种设计，事务性执行都不会受到持久化过程的影响:推测性事务在未冻结的易失性副本上操作，而写入者根据TL4x的状态更新第二个易失性副本。一旦不再需要快照，TL4x解冻其副本并应用丢失的更新，而主副本上的执行继续不间断进行。这种快照更新功能是保持事务性性能不受持久化过程影响的关键。TL4x还进一步利用一致性副本来支持以不可撤销的读事务形式进行的快照读取。当在数据结构上执行长距离查询或在数据库中进行全表扫描时，这些功能非常有用，而且当事务执行具有外部副作用（如I/O请求）的操作时也很有用。传统上，事务性内存框架仅支持推测性事务而不支持不可撤销的事务，而范围查询通常需要通过多版本并发控制（MVCC）广泛使用内存，数据库中的内存使用量可达到原始数据库大小的7倍[6]。按照定义，内存型数据库管理系统利用的至少是数据库大小的2倍，因为它们在DRAM中存储数据库的一个副本，并在持久性存储中存储另一个副本。实际上，由于空间扩增，这个大小可能会增加得更大。TL4x的常量内存开销为数据大小的4倍，并且提供与最佳性能的易失性数据结构相当的长距离查询性能。TL4x的设计不受底层持久性存储设备的影响，大部分情况下性能也不受其影响。使用较慢的设备的唯一影响是长时间持久化数据副本的时间可能导致崩溃时丢失的事务数量增加。TL4x不依赖于特定的持久性内存技术的特性，例如最近停产的英特尔Optane[26]，可以与任何存储设备一起使用，从传统的块设备到存储级内存和非易失性内存。我们通过TL4x做出以下贡献:0•我们引入了一种高度可扩展的持久性事务内存（PTM），具有缓冲持久性的线性化事务，可以持久化到PM或块存储；0• 我们消除了将数据持久化到PM、磁盘或根本不持久化之间的性能差距;0• 我们支持只读的不可撤销事务； •我们实现了一个全事务的键值存储，其吞吐量超过现有技术10倍。0本文的组织结构如下。我们在第2节中提供背景信息，并在第3节中介绍底层系统模型。我们在第4节中描述了TL4x的设计，在第5节中对其性能进行了实验评估，并在第6节中证明了其正确性。我们在第7节中讨论相关工作，并在第8节中总结我们的工作。02 背景0近年来，可寻址字节的NVMM已经商业化，并且其性能和优势已经得到了彻底的分类和评估（例如，Gugnani等[21]和Izraelevitz等[28]）。它使程序员可以将系统崩溃视为程序运行过程中的正常事件，通过减少持久写入的延迟，可以以同步方式执行。此外，块设备的性能已经发展，现代存储类内存设备的访问延迟与NVMM相当，例如[30,54]。然而，持久性既不是微不足道的，也不是无额外开销的，需要仔细编程以确保持久数据在崩溃时的一致性。因此，程序员必须以允许在任何给定时间点从崩溃中恢复的方式对内存（即存储）的写入进行排序。存在多种保持数据一致性的技术。预写式日志（WAL）被许多PTM和DBMS广泛使用：更改在应用于持久数据之前持久化到日志中。重做日志记录新数据，因此在发生故障时可以重新应用更改。在撤销日志中，记录数据的前一个状态，并在恢复时将系统回滚到该状态。阴影数据是一种不涉及日志记录的技术。它维护数据的多个副本，并在成功更新后将持久指针切换到最新的副本。在存在崩溃的情况下，存在多个正确性定义来规范并发程序的正确性，包括持久性线性化和缓冲持久性线性化，由Izraelevitz等[27]正式化。持久性线性化通过要求与崩溃相关的实时顺序被保留来扩展线性化[24]，即如果操作在崩溃之前返回，则在崩溃后其效果是可见的。缓冲持久性线性化通过要求崩溃后的恢复状态反映出在崩溃前的历史的一些可线性化历史来放松持久性线性化，但不一定是最近的历史。因此，它允许从历史中省略操作，只要保持因果顺序即可。事务内存是一种并发控制概念，可以安全地执行多个操作。它被认为对程序员友好，因为事务内存框架将并发控制从应用程序员中抽象出来，并通过允许程序员编写顺序代码来减少编程工作量。事务内存有硬件和软件实现，本文介绍了一种软件事务内存框架。与跨越一个对象的单个操作不同，事务执行有多个隔离级别（即一致性准则）。本文侧重于线性化或严格串行化，这意味着存在一种等效的顺序历史，其中每个事务2470TL4x PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0事务的线性化发生在某个时间点（线性化点），其效果与并发执行中的效果相似。线性化对已提交的事务强制实施了全序。存在许多事务系统的隔离级别，如[1, 5,10]所述，这些级别在事务被允许观察的状态上有所不同。更确切地说，我们提出的设计满足比线性化更强的概念，即不透明性[20]，其中即使中止的事务也只观察到一致的系统状态。不透明性可以防止在推测执行期间进入非法状态，并防止所有事务（包括中止的事务）观察到导致有害情况（如无限循环或除以0）的不一致状态[55]。事务内存的设计依赖于TL2算法[12]，它支持推测更新和只读事务。简而言之，TL2使用共享全局时钟，每个写入事务维护两个集合，读集和写集。当读取或更新项目（例如地址或对象）时，将其记录在读集或写集中。为了适应读集验证，每个项目都与一个序列号相关联。它记录了项目最后一次更新时观察到的全局时钟的值。在事务结束时，在锁定写集之后，将验证读集项目以确定可提交性。对于验证，将每个项目的序列号与事务开始时观察到的全局时钟的值进行比较。未能通过验证的事务将中止。对于线性化，要求在锁定写集之后所有读集项目仍然有效。这样，可以确保事务可以序列化到某个时间点，在锁定写集中最后一个项目和第一个项目释放之间的时间。TL2可以通过急切（遇到时间）锁定或写入集的提交时间锁定来实现。我们的设计使用了读-复制-更新（RCU）机制。RCU是一种无锁同步原语，用于同步读者和写者。读者使用arrive()方法表达他们打算从共享对象中读取，并在读取完成后调用depart()。写者执行synchronize()操作，该操作阻塞写者直到所有现有读者离开为止。03 模型和假设在本节中，我们描述了TL4x的系统和故障模型以及它提供的保证。我们遵循Izraelevitz等人[27]的模型，该模型假设完全系统崩溃，没有个别进程的自发崩溃和恢复。TL4x假设具有易失性缓存和主存的混合内存体系结构，并具有NVMM或磁盘形式的额外持久性存储。它能够利用0既支持字节寻址的非易失性存储，也支持块寻址的非易失性存储。与[49]类似，我们在事务期间使用语言插入来进行跨持久类型的加载和存储操作。对于写入排序，我们区分磁盘和NVMM。在NVMM中，我们使用缓存行写回（CLWB），在Intelx86架构中作为持久写回支持，并使用存储栅栏（sfence）进行psync和pfence[27]。CLWB将缓存行刷新到持久内存中，sfence将CLWB和其他存储操作与自身进行排序：sfence之后的存储指令仅在sfence之前的存储指令完成后才开始执行。对于磁盘，我们使用msync()将映射地址的回写同步到磁盘。TL4x以同步的方式使用msync()，即阻塞方式，因此它对应于[27]中的pwb、psync和pfence。TL4x保证了缓冲持久性线性化[27]，即其事务是可线性化的，并且在崩溃后始终可以恢复到表示线性化历史的非平凡状态。与持久性线性化不同，不要求在崩溃后所有已提交的事务都可见，只需一个一致的状态。所丢失的进度量不受此正确性标准或我们的设计的限制。04 TL4x设计0在本节中，我们描述了TL4x的设计和实现。我们从算法及其不同状态的高级描述开始，然后划分出不同的构建块。为了算法的简洁性，我们在TL4x的子算法中使用连续的行号，并使用tl_前缀标记线程本地变量。04.1高级描述TL4x使用四个用户数据副本来实现并发和持久性。两个副本是易失性的，Main和Back，两个是持久性的，�0和�1。所有四个副本都被内存映射到相同大小的区域。我们将块定义为一系列连续的内存地址。其大小是可配置的，在我们的实现中，块大小为64字节，占用x86上的一个缓存行。TL4x区分推测的和不可撤销的只读事务：前者可以中止和重新执行，而后者保证永远不会中止。它使用TL2进行推测事务，它们操作Main，并将其扩展为支持不可撤销的只读事务，这些事务从Back读取。Back定期持久化到其中一个持久副本，由一个专用线程完成，我们将其称为复制线程。复制线程和推测写入者都参与将Main同步到Back。TL4x保证当不可撤销的只读事务或复制线程从其中读取时，Back始终反映出一个可线性化的历史。作为并发控制的一部分，TL4x采用四个状态，并按照以下顺序在它们之间循环：复制，同步，快照和复制块。所有2480PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克省Gal Assa，Andreia Correia，Pedro Ramalhete，Valerio Schiavoni和Pascal Felber0Main0� �0Back0�0� 地址0地址0地址0地址0地址0��0� � �0P0/P10� �0�  推测读取  �  推测写入0�  不可撤销的读取  �持久化0�  复制 �  复制块0块 块 块 块 块 块 块 块0图1.  TL4x高级描述。0状态转换由复制线程驱动。推测的更新事务在开始时采样状态，并根据结束时的状态确定对Back的操作。每个副本的访问类型在图1中描述。推测读取和写入在Main上执行（�和�）。如果TL4x的状态为复制，则推测写入者也将其更新应用于Back（�）。当需要读取Back以持久化其内容或执行不可撤销的读取时，系统进入同步状态。在触发状态转换之后，复制线程暂停，直到观察到DUPLICATE或DUPLICATE_BLOCK状态的每个推测写入事务结束为止。然后，复制线程将状态更改为SNAPSHOT，以向不可撤销的读取者指示Back现在是一个一致的快照，可以从中读取。如果推测写入事务观察到同步或快照状态，则不会更新Back。在快照状态下，不可撤销的只读事务在Back上执行其读操作（�）。如果需要持久化，复制线程执行该操作（�）。这是唯一的状态，当不可撤销的只读事务执行读取操作时。在不可撤销的读取者和复制线程完成从Back读取后，复制线程将状态驱动到DUPLICATE_BLOCK并暂停，直到观察到SYNCHRONIZE或SNAPSHOT的所有推测写入事务结束为止。然后，复制线程和推测写入者使用在SYNCHRONIZE和SNAPSHOT状态期间发生在Main上的修改更新Back（�）。完成复制线程后，它将系统转换到复制状态。TL4x使用多个同步原语来支持其并发控制。它使用一个共享的逻辑时钟，以原子计数器的形式作为全局时钟。如图1左上角所示，Main包含每个块的锁和序列号。序列号表示更新时的全局时钟的值，并用于在提交之前验证事务以及指示是否应在DUPLICATE_BLOCK期间将块复制到Back。Back包含相应的序列号数组。推测写入者在DUPLICATE状态期间更新它（�），并在DUPLICATE_BLOCK状态期间与复制线程一起这样做（�）。TL4x采用了基于事务锁定的并发控制，其设计保证了不透明事务。推测读取和写入事务在Main上操作，而不可撤销的读取事务在Back上操作。在写事务期间，首次尝试写入块中的地址时会获取锁，并在提交或中止事务时释放锁。所有修改的地址都存储在写集中，连同其原始值，以备事务中止时使用。在推测（读取或写入）事务中，读访问是乐观并发进行的，无需获取锁。此外，在写事务期间读取的每个内存位置都会添加到读集中，以在提交时验证先前读取的地址是否发生了变化。在不可撤销的读取事务中，读访问只需将其重定向到Back，无需任何原子指令。我们现在描述实现TL4x并发耐用事务的算法。在算法1中，我们呈现了beginTx（）和endTx（），它们分别标记事务的开始和结束。用户代码必须放置在它们之间。所有加载和存储必须分别与在算法2中呈现的pload（）和pstore（）交织，以适应我们的TL2实现。虽然不可撤销的事务不容易发生冲突，因为它们在宁静的Back上操作，但是所有读取访问必须通过pload（）进行，以从Main重定向到Back。当检测到与另一个事务的冲突时，调用abortTx（）并触发重新开始事务。为此，我们假设beginTx是一个宏或内联函数，使得执行跳转是安全的，因为它的地址在堆栈中可用。beginTx（）函数根据其类型初始化事务。读和写集合被清除（行7），并对读集合进行验证时对全局时钟进行采样（行12）。写事务在URCU上到达（行14），提供指示给复制线程可以更新Back的写事务。不可撤销的读取者等待直到Back使用一致的快照冻结，即状态为SNAPSHOT（行9）。在waitForSnapshot（）中，当设置了COUNTER_ON标志时，读取者增加读取计数器（行22）。这意味着不可撤销的读取事务可能会被饥饿，永远不会观察到由复制线程在行126上设置的COUNTER_ON标志。但是，在实践中，应该0标志和计数器，用于将不可撤销的读取者与副本线程同步，以及用于存储其状态的原子整数。设计依赖于原子比较和交换以及加法和读取。为了将副本线程与写事务同步，TL4x采用了用户空间读-复制-更新（URCU）机制。URCU保证了在副本线程将状态更改为快照时，Back是一致且冻结的。011}16}17 }23}26 }33}38 }46}60}64 }72}73 }2490TL4x PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克省0算法1 - TL4x的beginTx（），endTx（）和abortTx（）01  // 全局变量02  atomic gClock; // 全局时钟03  atomic gState {STATE_DUPLICATE}; // 快照状态04 atomic gCounter; // 待处理读者的计数器05 void beginTx() {06 RETRY: // abortTx()跳转到这里0Entries = 0;08 if (tl_txType == TX_IS_IRR_READ) {010 return ;013 if (tl_txType == TX_IS_UPDATE) {014 urcu.arrive(tl_tid);015 tl_state = gState.load();018 void waitForSnapshot() {019 while (true) {021 if ((counter & COUNTER_ON) == COUNTER_ON) {022 if (gCounter.cas(counter, counter + 1ULL)) { break; }025 while (gState.load() != STATE_SNAPSHOT) { }027 void abortTx() {028 if (tl_tx_type == TX_IS_UPDATE) {029 tl_writeSet.rollbackMain();031 if (tl_state == STATE_DUPLICATE_BLOCK) {032 tl_writeSet.duplicateBlocksOnBack_UpdSeq(nextClock);034 tl_writeSet.unlock(nextClock);035 urcu.depart(tl_tid);037 goto RETRY;039 atomic gLocks[NUM_LOCKS]; // 锁的数组040 uint64_t gSeqMain[NUM_LOCKS]; // 'main'的序列数组041 uint64_t gSeqBack[NUM_LOCKS]; // 'back'的序列数组042 bool endTx() {043 if (tl_txType == TX_IS_IRR_READ) {0(1); // 信号复制线程045 return true;048 if (tl_writeSet.numEntries == 0) {0TX_IS_UPDATE) urcu.depart(tl_tid);050 return true;052 if (!tl_readSet.validate(tl_clock)) { abortTx(); }01) + 1;054 if (tl_state == STATE_DUPLICATE) {055 // 在gSeqMain和gSeqBack上设置新的序列057 } else if (tl_state == STATE_DUPLICATE_BLOCK) {058 // 在gSeqMain和gSeqBack上设置新的序列059 tl_writeSet.duplicateBlocksOnBack_UpdSeq(nextClock);061 tl_writeSet.unlock(nextClock);0_tid);063 return true;066 void duplicateOnBack_UpdSeq(uint64_t nextClock) {067 for (w : tl_writeSet){068 int idx = hidx(w.addr);069 gSeqMain[idx] = nextClock;070 memcpy(w.addr − BEGIN_MAIN + BEGIN_BACK, w.addr,071 gSeqBack[idx] = gSeqMain[idx];0对于DUPLICATE_BLOCK或DUPLICATE状态，等待快照的时间足够长，以便所有待处理的不可撤销读者在开始执行之后递增计数器。只有当复制线程转换到STATE_SNAPSHOT状态(Line25)之后，不可撤销读才能开始执行。我们在第6节中证明了，当waitForSnapshot()返回时，可以保证Back是一致的，并且在当前事务完成读取之前不会被修改。为了满足不透明度，任何事务类型的读访问都通过pload()函数进行插入，如Algorithm2所示。不可撤销读者只需从Back读取数据，无需进行额外验证(Line77)。推测性读取检查所需地址是否被锁定，并且在beginTx()处采样的时间戳之后是否被修改(Line84)。在这种情况下，可以将值返回给调用者，并且执行可以继续。否则，事务中止。存储插入也在Algorithm2中的pstore()中进行。写者获取与写入相关的锁，并且0将原始值添加到写集。新值以就地写入Main。请注意，在我们的实现中，某些写操作可能跨越多个块，因此需要获取多个锁。如果无法获取锁，则事务中止。在用户代码执行完成后，调用Algorithm1中的endTx()函数。事务结束时执行的步骤由事务的类型定义。不可撤销读保证可以观察到一个线性化的快照，并且在返回之前不需要验证。这些事务完成后，读取计数器递减，以使复制线程能够进行进一步的状态转换。推测性只读事务在提交时间不需要任何验证，因为如果所有读取的内存位置(Line83)观察到的关联锁版本在事务开始时读取的序列之前(即tl_clock，Line12)，则所有读取的内存位置在事务开始时具有相同的值。请注意，更新操作80}87}95}97}98 };2500PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔Gal Assa，Andreia Correia，Pedro Ramalhete，Valerio Schiavoni和Pascal Felber0Algorithm 2 —— 加载和存储插入074 template  struct persist {075 uint64_t vrmain;076 T pload() const {077 if (tx_type == TX_IS_IRR_READ) { // 从'back'读取0rmain − BEGIN_MAIN + BEGIN_BACK);079 return lval;082 asm volatile ("" : : : "memory"); // 编译器屏障083 uint64_t sl = gLocks[hidx(&vrmain)].load(); // 锁的状态084 if ((sl & LOCKED) || (sl > tl_clock)) { abortTx(); }085 if (tl_type == WRITE_TX) { tl_readSet.add(this, sizeof(T)); }086 return val;088 void pstore(T newVal) {089 int idx = hidx(&vrmain);090 uint64_t sl = gLocks[idx].load(); // 锁的状态091 if (sl != (LOCKED | tl_tid)) {092 if (!(sl & LOCKED) && (sl <= tl_clock) &&gLocks[idx].CAS(sl, LOCKED | tl_tid)) {0);094 } else { abortTx(); }096 vrmain = newVal;0在beginTx()之后读取内存位置的数据将导致相应的锁序列大于或等于tl_clock。写事务需要验证读集的序列号在获取所有写集锁之前没有被并发事务修改。验证成功后，通过增加全局时钟来获得提交时间戳，并在释放写集锁时使用该时间戳作为新的序列号。TL4x的设计依赖于Back副本的更新。这意味着获取块锁的线程负责将其内容复制到Back。因此，在释放写集锁之前，如果状态为DUPLICATE(Line56)或DUPLICATE_BLOCK(Line59)，可能需要将在Main上进行的修改(或整个块)复制到Back。需要复制整个块，因为后续的事务可能在Main上的同一个块中修改多个内存位置，而不会更新到Back。在提交(Lines49和62)和中止(Line 35)时，写事务与URCU不同。0算法1显示了冲突发生时事务中止过程的代码。在abortTx()期间，事务释放其在执行期间获得的锁，并回滚对Main的更改。此外，它退出URCU，因此不再被认为能够修改Back。由于已中止的事务可能在执行期间获得锁定块，因此如果它们在状态为DUPLICATE_BLOCK时开始执行，则需要负责将锁定的块复制到Back。0内存管理。TL4x采用安全的内存回收方案，并使用自己的内存分配器在事务中进行内存分配和释放。它不会泄漏内存，无论是易失性还是持久性，即使在崩溃的情况下，因为其操作被认为是事务的一部分，因此受到相同的全有或全无语义的约束。大致而言，它维护了一组表示不同大小的空闲块的堆栈。如果在相关堆栈中没有所需大小的块，则分配器会分配一个满足要求的附加块。在释放内存时，释放的块被追加到相关堆栈中。04.3复制线程复制线程有两个目的：首先，它转换TL4x的状态；其次，它负责将数据从Back复制到持久存储中。它在一个无限循环中运行，如算法3所示。最初，状态为DUPLICATE，并且复制线程确定是否需要在Back上冻结快照。如果全局时钟自上次Back持久化以来提前了一个预定义的值（MIN_TXN_SYNC），或者在不可撤销的读者通过读者计数器请求时，需要一个快照。我们将这些事件称为持久化事件和读取快照事件。复制线程重置COUNTER_ON以防止其他不可撤销的读者增加读者计数器。然后，它触发URCU同步，之后Back是Main的一致快照，即最后一次提交或中止的事务在观察到状态为SYNCHRONIZE或SNAPSHOT时的时间点。如果由于持久化事件而冻结了Back，则复制线程通过比较A0和A1的时间戳并选择最早的时间戳来确定要更新的持久副本。我们将选择的副本称为A。在persistTo()期间，将Back的内容按以下方式复制到A。首先，将Back中每个块的时间戳与转换为SYNCHRONIZE时记录的时间戳和A的时间戳进行比较。如果在它们之间，将块从Back复制到A。在此复制过程之后，刷新相关的缓存行并发出内存屏障。接下来，更新A的时间戳，并伴随着flush、fence或msync()进行磁盘操作，使其在恢复时可以安全使用。最后，更新A的时间戳。在这两种情况下（持久化事件和读取快照事件），复制线程等待所有正在进行中的不可撤销的读者完成，然后将系统转换为DUPLICATE_BLOCK状态。在DUPLICATE_BLOCK中，复制线程设置COUNTER_ON以允许不可撤销的读者增加读者计数器。复制线程扫描锁定和序列数组，查找在Main上的序列大于在Back上的序列的块，然后锁定并复制它们到Back，跳过已锁定的块。在复制块之前，复制线程必须触发附加的URCU同步和静默，以确保新的131}132 }151 }2510TL4x PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔0算法3 - 复制线程循环099  void copyThreadLoop() {0101 while (!destructorCalled) {0102 bool doPersist = false;0103 if (gClock.load() < (lastSyncedTxn + MIN_TXN_SYNC)) {0104 if (gCounter.load() == COUNTER_ON) { continue; }0105 } else { doPersist = true; }0106 if (doPersist) { lastSyncedTxn = gClock.load(); }0107 gCounter.fetch_sub(COUNTER_ON);0108 gState.store(STATE_SYNCHRONIZE);0109 urcu.synchronize();0110 gState.store(STATE_SNAPSHOT);0111 if (doPersist) {0112 PMeta* p0 = (PMeta*)BEGIN_P0;0113 PMeta* p1 = (PMeta*)BEGIN_P1;0114 PMeta* p = (p1->ts > p0->ts) ? p0 : p1; // 更新较旧的区域0115 uint64_t usedSize = persistTo(p,lastSyncedTxn);0116 PFENCE(); // 仅针对NVMM0117 MSYNC(p + sizeof(p->ts), usedSize); // 仅针对磁盘0118 p->ts = lastSyncedTxn;0119 // 仅在用户数据持久化后才持久化时间戳0120 PWB(&p->p_ts); // 仅针对NVMM0121 PSYNC(); // 仅针对NVMM0122 MSYNC(p, sizeof(p->ts)); // 仅针对磁盘0124 while (gCounter.load()>0) { yield() };0// 等待不可撤销的读取0125 gState.store(STATE_DUPLICATE_BLOCK);0126 gCounter.store(COUNTER_ON);0127 urcu.synchronize();0128 copyMainToBack(); // 更新快照0DUPLICATE);0130 doPersist = false;0writers观察状态为DUPLICATE_BLOCK。这样做是为了确保每个锁定的块都被复制到Back中。否则，观察到不同状态的正在进行中的写操作可能会在不更新Back的情况下解锁块，从而使其处于不一致状态。最后，复制线程将状态转换回DUPLICATE。当持久化到磁盘时，msync()可能会失败[53]。虽然在算法3中没有显示，但是在117行的msync()中出现错误可以通过重复调用persistTo()（第115行）和重试msync()来处理，而122行的msync()的错误可以通过在重试msync()之前重复写入时间戳（第118行）来处理。复制线程的进展条件是阻塞无饥饿[23]。只有三个等待循环，分别在124、109和127行，其中复制线程等待多达MAX_THREADS-1个其他线程。复制线程使用COUNTER_ON来防止不可撤销的读者增加读计数器，因此它最多会被阻塞不超过0算法4 - 恢复0133  void recover() {0134 // 根据时间戳从一致的持久区域复制0135 PMeta* p0 = (PMeta*)BEGIN_P0;0136 PMeta* p1 = (PMeta*)BEGIN_P1;0137 PMeta* pcons = (p1->ts > p0->ts) ? p1 : p0;0138 PMeta* pincons = (p1->ts > p0->ts) ? p0 : p1;0139 memcpy(BEGIN_BACK, pcons, REGION_SIZE); // 恢复'back'0140 memcpy(BEGIN_MAIN, pcons, REGION_SIZE); // 恢复'main'0142 memcpy((uint8_t*)pincons + sizeof(pincons->ts),(uint8_t*)pcons + sizeof(pcons->ts), REGION_SIZE -0143 flushPWB(pincons, REGION_SIZE); // 刷新NVMM缓存行0144 PFENCE(); // 仅针对NVMM0145 将pincons+sizeof(pincons->ts)到REGION_SIZE-sizeof(pcons->ts)的数据区域MSYNC到磁盘中0146 pincons->ts = pcons->ts;0147 PWB(&pincons->p_ts); // 仅针对NVMM0148 PSYNC(); // 仅针对NVMM0149 将pincons的大小(即pincons->ts)MSYNC到磁盘中0150 gClock.store(pcons−>ts + 1);0MAX_THREADS -1 irrevocable-readers on  Line 124 .对于写线程，相同数量的线程在状态变为 SYNCHRO- NIZE或 DUPLICATE_BLOCK 之前可以到达URCU，分别在 Line109 或 127 处。 persistTo() 与 Back上的不可撤销读操作并行执行，不能被推测性事务阻塞。copyMainToBack()复制所有关联锁可获取的块，并跳过已锁定的块，因此也不会被阻塞。04.4 恢复过程0算法4详细描述了 TL4x背后的恢复机制。在存在持久化数据时，恢复过程发生在初始化 TL4x 时。它确定要读取的持久化副本是 � 0 和 � 1中较新的副本，因此记为 � cons。我们将第二个副本记为 �incons。然后将 � cons 的内容无时间戳地复制到 Main 和Back。然后，无时间戳地将 � cons 反映到 �incons。更改被刷新，仅在刷新后更新时间戳。最后，全局时钟设置为 � cons +1 的时间戳。04.5 用户空间RCU我们实现了一个用户空间RCU来通过写事务将