245→TL 4x-磁盘上的缓冲持久事务与内存GalAssaTechnion以色列galassa@campus.technion.ac.ilAndreia Correia瑞士纳沙泰尔大学andreia.unine.chPedro Ramalhete思科系统瑞士pramalhe@gmail.com摘要Valerio Schiavoni瑞士纳沙泰尔大学valerio.unine.ch瑞士纳沙泰尔大学pascal. unine.ch1引言持久存储器设备进入消费者市场，重新唤起了人们对事务持久算法的兴趣。持久性内存（PM）被吹捧为具有两个属性，使其区别于其他存储技术：字节寻址能力和快速事务持久性。在这项工作中，我们调查这些属性如何区分PM从块存储缓冲持久性的上下文中。 我们提出了一种新的算法，TL4x，能够提供缓冲持久的线性化事务，具有高度的可扩展性，不相交的写入和高效的持久性，无论是PM或块存储设备。 TL4x是一个纯软件的用户空间解决方案，它优化了对持久存储的写入，提供了缓冲的持久事务，其成本与类似的非持久事务相比可以忽略不计。TL4x维护一个易失性一致快照，用于缓冲持久性，并与不可撤销的只读事务共享，允许远程查询操作与写事务并行运行。 我们使用TL4x来实现一个事务数据库引擎，它的性能可以超过RocksDB一个数量级。CCS概念：·计算方法学并行算法。关键词：持久内存，事务，缓冲持久性，磁盘持久性允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许用信用进行提取复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。请求权限请发邮件至permissions@acm.org。PPoPP©2023计算机协会ACM ISBN 979-8-4007-0015-6/23/02。- 是的- 是的十五块https://doi.org/10.1145/3572848.3577495持久性主存已经引起学术界和工业界对高效持久事务算法的兴趣。PM，也被称为非易失性主存储器（NVMM），正在销售，因为它比块存储设备具有两个重要的优势：PM具有较低的持久性延迟和字节可寻址。当需要持久事务时，第一个优点很重要。通常，一个事务修改少量数据，但随后会导致至少一个4 kB页面的磁盘写入，并发出至少两个对fsync（）的调用[33，46]。这种方法在磁盘（SSD和HDD）上执行时非常慢，默认情况下没有事务引擎使用它相反，大多数商业和开源数据库管理系统（DBMS），包括RocksDB[39]，Cassandra [2]，WiredTiger（MongoDB的存储引擎）[ 41 ]和CockroachDB [ 32 ]，在持久化到磁盘时默认提供缓冲事务，即。即，在系统崩溃的情况下，一些提交的事务可能丢失这表明缓冲持久事务可以满足广泛的用例第二个优点是字节寻址能力，并且从编程和硬件的角度来看都被认为是有益 虽然这被认为是一个PM独有的功能，我们表明，与缓冲的持久事务，字节寻址能力可以通过使用由磁盘存储支持的DRAM来实现。在这项工作中，我们提出了一种新的持久事务存储器（PTM）框架，TL4x。 TL4x是一种可扩展的通用PTM，当持久化到PM或传统块设备时，与其非持久性能相比，其开销可以忽略不计。TL4x的设计不需要写前日志，这已经被用来实现DBMS中的持久事务至少30年[ 40 ]（e. 例如， 用于MicrosoftHekaton [11]、MySQL InnoDB引擎[42]、PostgreSQL[48]和Oracle DB [35]的redo-log，或用于SAP HANA [14]的redo-log和shadow-copy）。相反，我们的技术始终维护数据的两个易失性副本，其中一个可以在任何给定时间冻结，以包含数据的一致快照。这246×××PPoPP一致副本由后台线程用于将数据复制到持久存储器，而读和写事务继续在另一个副本上不受阻碍地执行。不管底层非易失性存储器和持久化数据所花费的时间如何，通过这种设计，事务执行不受持久化过程的影响：推测性事务在未冻结的易失性副本上操作，并且写入器根据TL4x的状态更新第二易失性副本。一旦不再需要快照，TL4x将解冻其副本并应用错过的更新，而主副本上的执行将不间断地继续。这个快照更新特性是保持事务性能不受持久过程影响的关键。TL4x还使用一致性副本以不可撤销的读取事务形式支持快照读取。这些在执行长距离查询时很有用数据结构或数据库中的全表扫描，以及事务执行具有外部副作用的操作（如I/O请求）时。传统上，事务内存框架仅适应推测性事务，而不是不可撤销的事务，范围查询通常需要通过多版本并发控制（MVCC）大量使用内存，达到数据库中内存使用量的7倍[6]。 根据定义，内存中DBMS利用至少2个数据库的大小，因为将数据库的一个副本存储在DRAM中，另一个副本存储在持久性存储中。在实践中，由于空间放大，这可能会变得更大 TL4x具有恒定的内存开销，为数据大小的4倍，并提供与最佳性能的易失性数据结构相当的长距离查询性能。TL4x的设计与底层持久存储设备无关，在大多数情况下，其性能也是如此使用较慢的设备的唯一影响是，更长的时间来保存数据的副本可能会导致崩溃时丢失的事务数量增加TL4x不依赖于特定持久内存技术的功能，例如最近停产的Intel Optane [26]，并且可以与任何存储设备一起使用，从传统块设备到存储类内存和NVMM。通过TL4x，我们做出了以下贡献：本 文 提 出 了 一 种 高 度 可 扩 展 的 持 久 事 务 存 储 器（PTM），它具有缓冲的持久可线性化事务，可以持久存储到PM或块存储;我们消除了持久化到PM、磁盘或根本不持久化之间的性能差距;• 我们提供只读不可撤销交易的支持;• 我们实现了一个完全事务性的键/值存储，其吞吐量超过现有技术的10倍本文件的结构如下。 我们在§ 2中提供背景，并在§3中介绍底层系统模型。我们在§ 4中描述了TL4x的设计，在§5中通过实验评估了其性能，并在§6中证明了其正确性。我们将在第7节讨论相关工作，并在第8节总结我们的工作。2背景字节可寻址NVMM近年来已经商业化，并且其性能和益处被粗略地分类和评估（例如，例如， Gugnani等人 [21]和Izraelevitz等人。[28]）。它允许程序员在程序运行期间将系统崩溃视为正常事件，通过将持久写入的延迟减少到可以以同步方式执行的程度。此外，块设备的性能已经发展，并且现代存储类存储器设备具有与NVMM相当的访问延迟，例如[30，54]。遗憾的是，持久性既不是微不足道的，也不是没有开销的，它需要仔细的编程来确保持久性数据在崩溃时因此，程序员必须强制执行写入内存的顺序（即。即，存储器）以允许在任何给定时间从崩溃中恢复的方式存在多种用于一致地持久化数据的技术写前日志（WAL）被许多PTM和DBMS广泛使用：在将更改应用于持久化数据之前，将更改持久化到日志中。Redo-logging记录新数据，因此在失败的情况下可以重新应用更改在撤消日志记录中，记录数据的先前状态，并且在恢复时系统回滚到该状态。影子数据是一种不涉及日志记录的技术它维护数据的多个副本，并且在成功更新后，切换一个永久指针指向最新的指针。在崩溃的情况下，并发程序正确性的最流行定义是持久线性化能力和缓冲持久线性化能力，如Izraelevitz等人[27]所述。持久线性化通过要求保留关于崩溃的实时顺序来扩展线性化能力[24]，即。即，如果一个操作在崩溃之前返回，它的效果在崩溃之后是可见的 缓冲持久线性化通过要求崩溃后的恢复状态反映某个可线性化历史来放松持久线性化，该可线性化历史是崩溃前的历史的前缀，但不一定是崩溃前的最近历史。因此，它允许操作从历史中省略，只要因果顺序被保留。事务内存是一种并发控制概念其中可以安全地一起执行多个操作它被认为是程序员友好的，因为事务性的并发控制框架从应用程序员那里抽象出来，并通过允许程序员编写顺序代码来降低编程效率。存在事务存储器的硬件和软件实现，这项工作提出了一个软件事务存储器框架。与跨越一个对象的单个操作不同，事务执行有多个隔离级别（即一致性标准）。 这项工作的重点是线性化，或严格的串行化，这意味着存在一个等效的顺序历史，其中每个事务··TL4xPPoPP247发生在单个时间点（线性化点），并且其效果类似于并发执行中的效果。线性化对已提交的事务施加了总顺序 如[1，5，10]所述，事务系统存在少数隔离级别，主要是允许事务观察的状态不同。更确切地说，我们提出的设计满足比线性化更强的概念，不透明性[20]，即使中止的事务也只观察一致的系统状态。不透明度可以防止在推测执行期间进入非法状态，并防止所有事务（包括中止的事务）观察到可能导致有害场景（如无限循环或除以0）的不一致状态。事务在执行不一致的读取之前中止，而不是进入这种非法状态。TL4x的设计依赖于TL2算法[12]，该算法支持推测性更新和只读事务。简而言之，TL2使用共享的全局时钟，并且每个写事务保持两个集合，读集合和写集合。当一个项目（例如，地址或对象）被读取或更新时，分别在读或写集合序列号与每个项目相关联，以适应读取集验证。它记录上次更新项时全局时钟的值在事务结束时，在写集被锁定之后，读集项被验证以确定可提交性。为了进行验证，每个项目的序列号都与事务开始时观察到的全局时钟的值一致。未能验证的事务将中止。 对于线性化，要求所有读集项在写集锁定后仍然有效。 这样，就可以保证事务可以序列化到单个时间点，即写集中的最后一个项被锁定和第一个项被释放之间的时间点。TL2可以通过写集的急切（等待时间）锁定或提交时间锁定来我们的设计使用了读取-复制-更新（RCU）机制，主义RCU是一种同步原语，它在不使用锁的情况下同步读取器和写入器 读取器使用arrive（）方法表示他们从共享对象读取的意图，并在读取完成时调用depart（）。写入器执行synchronize（）操作，该操作阻塞写入器，直到所有预先存在的读取器离开。3 模式及假设在本节中，我们将介绍TL4x设计的系统和故障模型，以及它提供的保证。我们遵循Izraelevitz等人的模型。 [27]，它假设整个系统崩溃，没有自发崩溃和恢复的个别进程。TL4x采用混合内存架构，具有易失性缓存和主内存，以及NVMM或磁盘形式的附加持久性存储。它能够利用字节和块可寻址的非易失性存储。类似于[49]，我们在事务期间使用跨持久类型的加载和存储操作的语言插入。对于写顺序，我们区分磁盘和NVMM。在NVMM中，我们使用Intel x86架构中支持的缓存行回写（CLWB）作为持久回写，并在[27]中为psync和pfence存储fence（sfence）CLWB将缓存行刷新到持久性内存，sfence对CLWB和其他存储操作进行排序：sfence之后的存储指令只有在sfence之前的存储指令完成之后才开始执行。 对于磁盘，我们使用msync（）将映射地址的写回同步到磁盘。TL4x在同步中使用msync（），即，blocking，方式，所以它对应于[27]中的所有pfence，psync和pfence。TL4x保证缓冲的持久线性化能力[27]，即。即，其事务是可线性化的，并且在崩溃之后，总是可以恢复到表示可线性化历史的非平凡状态 与持久线性化不同，并不是所有提交的事务都需要在崩溃后可见，只需要一个一致的状态。丢失的进度量不受这个正确性标准的限制，也不受我们的设计的限制。4TL4x设计在本节中，我们将介绍TL4x的设计和实现。 我们从算法及其不同状态的高级描述开始，然后描绘不同的构建块。 为了简化算法的介绍，我们在TL4x的子算法中使用连续的行号，并使用tl_前缀标记线程局部变量。4.1高级描述TL4x使用用户数据的四个副本来促进并发和持久化。两个副本是volatile的，Main和Back，两个是persistent的，分 别是100和101。所有四个副本都被映射到具有相同可配置大小的区域我们将块定义为连续内存地址的集合它的大小是可配置的，在我们的实现中，一个块是64字节，在x86上占用一个缓存行。TL4x区分了推测性和不可撤销的只读事务：前者可以中止并重新执行，而后者保证永远不会中止。它将TL2用于推测性事务，这些事务在Main上操作，并将其扩展为支持不可撤销的只读事务，这些事务从Back读取。Back通过我们称为复制线程的专用线程周期性地持久化到其中一个持久化副本。两复制线程和推测写入器参与主到背的同步。TL4x保证当不可撤销的只读事务或复制线程从中读取时，Back总是反映可作为其并发控制的一部分，TL 4x采用四种状态，并按 以 下 顺 序 在 它 们 之 间 循 环 ： DUP-LICATE 、SYNCHRONIZE、SNAPSHOT和DUPLICATE_BLOCK。所有PPoPPGal Assa，Andreia Correia，Pedro Ramalhete，Valerio Schiavoni，andPascal Felber248地 址 地址地址BBBllloocccckk主要➎➏➊➍地址标志和一个计数器来同步不可撤销的读取器与复制线程，以及一个原子整数来存储其状态。 设计依赖于原子比较和交换以及获取和添加。为了同步复制线程和写入事务，TL 4x采用用户空间读取-复制-更新（URCU）机制，➋ ➎➌➏地址地址BBBllloocccckk回来主义URCU保证当复制线程将状态更改为SNAPSHOT时，Back是一致的并被冻结。4.2并发控制顾名思义，TL4x基于事务锁定，图1.TL4x高级描述。状态转换由复制线程驱动推测性更新事务在开始时对状态进行采样，并在结束时使用它来确定它们在Back上的操作图1描述了对每个副本的访问类型。推测读和写在Main上执行（PACK和PACK）。如果TL4x的状态是DUPLICATE，推测写入程序也会将其更新应用到Back（返回）。当需要回读以保持其内容或执行不可撤销的读取时，系统进入SYNCHRONIZE状态。在它触发状态转换之后，复制线程停止，直到观察到DUPLICATE或DUPLICATE_BLOCK状态的每个推测性写事务结束。然后，复制线程将状态更改为SNAPSHOT，以向可重写读取器指示Back现在是可以从中读取的一致快照推测性写入事务如果观察到SYNCHRONIZE或SNAPSHOT状态，则不会更新Back。在SNAPSHOT状态下，不可撤销的只读事务，在Back（Back）上执行读取操作。如果需要持久化，则复制线程执行它（复制）。 这是不可撤销的只读事务执行读取时的唯一状态。在不可撤销的读取器和复制线程完成读回之后，复制线程将状态驱动到DUPLI-CATE_BLOCK并停顿，直到观察到SYNCHRONIZE或SNAPSHOT的所有推测性写入事务结束。然后，复制线程和推测写入器用在状态SYNCHRO-NIZE和SNAPSHOT（SNAPSHOT）期间发生的对Main的修改来更新Back。 当复制线程完成时，它将系统转换为DUPLICATE状态。TL4x使用多个同步原语来支持其并发控制。它使用一个共享的逻辑时钟，以原子计数器的形式，作为它的全局时钟。 如图1的左上角所示，Main包含一个锁和每个块的序列号。 序列号表示更新时的全局时钟值，用于在提交之前验证事务，以及指示是否应在DUPLICATE_BLOCK期间将块复制到Back。Back包含相应的序列号数组。推测写入器在 DUP-LICATE 状 态 （ DUP ） 期 间 更 新 它 ， 并 在DUPLICATE_BLOCK状态（DUP）期间加入这样做的复制线程。TL4x采用共享原子并且特别地采用写入器的急切锁定我们的设计保证了不透明的交易。推测性读和写事务在Main上操作，而不可撤销的读事务在Back上操作。在写事务期间，在第一次尝试写入块中的地址时获取锁，并在提交或中止事务时释放锁。 所有修改后的地址与它们的原始值一起存储在写集中，以便在事务中止时使用。 在推测性（读或写）事务上，读访问是通过乐观并发完成的，而不需要获取锁。此外，在写入事务期间读取的每个存储位置被添加到读取集合，以在提交时验证先前读取的地址没有改变。 在不可撤销的读事务期间，读访问被简单地重定向到Back，而不需要任何原子指令。我们现在描述实现TL4x并发持久事务的算法。 在算法1中，我们提出了endTx（）和endTx（），它们分别标记事务的开始和结束。 用户代码必须放在它们之间。 所有加载和存储必须分别插入算法2中的pload（）和pstore（），以适应我们的TL2实现。虽然不可撤销的事务不容易发生冲突，因为它们在安静的Back上操作，但所有的读访问都必须通过pload（）完成，才能从Main重定向到Back。 当检测到与另一个事务的冲突时，abortTx（）被调用，它触发重新开始事务的开始。为此，我们假设PSTTx是一个宏或内联函数，这使得跳转可以安全执行，因为它的地址在堆栈中可用函数的作用是：根据事务的类型来定义事务 读取和写入集被清除（第7行），全局时钟被采样用于读取集验证（第12行）。写事务到达URCU（第14），向复制线程提供写事务可能正在更新返回的指示。无法忍受的读取器等待，直到Back被冻结并具有一致的快照，即状态为SNAPSHOT（第9行）。 在waitForSnapshot（）上，当COUNTER_ON标志被设置时，读取器增加读取器计数器（第22行）。 这意味着不可撤销的读事务可能会被饿死，因为永远不会观察到第126行上复制线程设置的COUNTER_ON标志。但实际上，投机性的阅读推测性写入简体中文重复块BBBllloocccckkP0/P1TL4xPPoPP249算法1-TL 4x EXTRACTTx（）、endTx（）和abortTx（）1//全局变量2原子uint64_t> gClock;//全局时钟3原子uint64_t> gState {STATE_DUPLICATE};// 快 照 状 态4 原 子uint64_t> gCounter;//挂起读取器的计数器publicvoidrun（）{6RETRY：//abortTx（）跳转到这里7tl_writeSet. num，tl_readSet. num = 0;8if（tl_txType == TX_IS_IRR_READ）{9waitForSnapshot（）;//等待直到'back'是快照10返回;11{\fnSimHei\bord1\shad1\pos（200，288）}12t1_clock = gClock.load（）;13if（tl_txType == TX_IS_UPDATE）{14urcu.arrive（tl_tid）;int n = nums. nums（）;16}17}publicvoidrun（）{19while（true）{20uint64_t counter = gCounter.load（）;21if（（COUNTER_ON）== COUNTER_ON）{22if（gCounter.cas（counter，counter +10））{break;}23}24}25while（gState.load（）！STATE_SNAPSHOT）{}26}publicvoidrun（）{28if（tl_tx_type == TX_IS_UPDATE）{29tl_writeSet.rollbackMain（）;30uint64_t nextClock = gClock.fetch_add（1）+1;31if（tl_state == STATE_DUPLICATE_BLOCK）{32tl_writeSet.duplicateBlocksOnBack_UpdSeq（nextClock）;33}34tl_writeSet.unlock（nextClock）;35urcu.depart（tl_tid）;36}37goto重试;38}39原子uint64_t> gLocks[NUM_LOCKS];//锁数组40uint64_t gSeqMain[NUM_LOCKS];//“main”41uint64_t gSeqBack[NUM_LOCKS];//“back”publicvoid run（）{43if（tl_txType == TX_IS_IRR_READ）{44gCounter.fetch_sub（1）;//信号复制线程45return true;46}47//只读事务立即提交10if（int n = 0）{49if（tl_txType == TX_IS_UPDATE）urcu.depart（tl_tid）;50return true;51}52if（！public int findDuplicate（）;}53uint64_t nextClock = gClock.fetch_add（1）+1;54if（tl_state == STATE_DUPLICATE）{55//在gSeqMain和gSeqBack上设置新序列56tl_writeSet.duplicateOnBack_UpdSeq（nextClock）;57}else if（tl_state == STATE_DUPLICATE_BLOCK）{58//在gSeqMain和gSeqBack上设置新序列59tl_writeSet.duplicateBlocksOnBack_UpdSeq（nextClock）;60}61tl_writeSet.unlock（nextClock）;62urcu.depart（tl_tid）;返回true;64}65//在“back”和更新序列publicint findDuplicateOnBack_UpdSeq（uint64_t）{public intfindDuplicate（）{68intidx = hidx（w.addr）;69gSeqMain[idx] = nextClock;70memcpy（w.addr − BEGIN_MAIN + BEGIN_BACK，w.addr，w.length）;71gSeqBack[idx] = gSeqMain[idx];72}73}当状态为DUPLICATE_BLOCK或DUPLICATE时，有足够的时间让所有挂起的不可撤销读取器增加计数器。一个 不 可 撤 销 的读 取 只 能 在 复 制 线 程 转 换 到 状 态SNAPSHOT（第25行）后开始执行。我们在第6节中展示了当waitForSnapshot（）返回时，可以保证Back是一致的，并且在当前事务完成读取之前不会被修改任何事务类型的读访问都插入了load（）函数以满足不透明性，如算法2所示。Irmable reader只是从Back读取数据，而不需要额外的验证（第77行）。推测性读取检查所需地址是否未锁定，以及是否在时间戳采样后未进行修改，时间戳采样点为STTTx（）（第84行）。在这种情况下，可以将值返回给调用方，并且可以继续执行。否则，事务中止。存储插入在pstore（）中完成，也可以在Algo-rithm2中找到。写入器获取与写入相关的锁，将原始值添加到写入集。新值将写入Main。请注意，在我们的实现中，有些写操作可能跨越多个块，因此需要获取多个锁。在获取锁失败时，事务中止。在用户代码执行完成之后，调用算法1中 在事务结束时执行的步骤由事务的类型定义。Irrevo-cable阅读器保证观察线性快照，并且在返回之前不需要验证 当这些事务完成时，读取器计数器被递减以使复制线程能够进行进一步的状态转换。推测性只读事务也不需要任何提交时验证，因为如果 所 有 读 存 储 器 位 置 观 察 （ 行 83 ） 在 事 务 开 始 时（tl_clock，行12）在序列读取之前的相关联的锁版本，则所有读存储器位置在事务开始时具有相同的值。请注意，更新250PPoPP算法2- 加载和存储插入74templatetypeNT>structpersistent {75uint64_t vrmain;public voidrun（）{77if（tx_type == TX_IS_IRR_READ）{//从'back'读取78Tlval=Vrmain（T）（vrmain−BEGIN_MAIN+BEGIN_BACK）;79返回lval;80}T val = vrmain;82asm volatile（“”：“memory”）;//编译器围栏83uint64_t sl = gLocks[hidx（vrmain）].load（）;（//锁的状态84if（（sl&锁定）||（sl> l_clock））{abortTx（）;}85if（tl_type == WRITE_TX）{tl_readSet.add（this，sizeof（T））;}86returnval;八七}publicintfindDuplicate（T）{89intidx = hidx（vrmain）;90uint64_t sl = gLocks[idx].load（）;//锁的状态91if（sl！（锁定|t1_tid））{92if（！(slLOCKED）（sl=tl_clock）gLocks[idx].CAS（sl，LOCKED&t1_tid））{&&<&&|93tl_writeSet.add（vrmain）;}return{arr（）;}95}96vrmain = newVal;97}98};如果在tlTx（）之后读取存储器位置的锁序列大于或等于tl_clock，则会导致对应的锁序列大于或等于tl_clock。写事务需要验证读集的序列号没有被并发事务修改，直到所有的写集锁被获取。验证成功后，提交时间戳通过递增全局时钟获得，并在释放写集锁时用作新序列。TL4x的设计依赖于背部复制品保持最新。这意味着获得块锁 的 线 程 因此， 在 释 放 写 集 锁 之 前 ， 如 果 状 态 是DUPLICATE，第56行（或DUPLICATE_BLOCK，第59行），则可能需要将在Main（或整个块）上完成的修改复制到Back。由于随后的transac-tions可能会修改多个内存位置在同一块在主同步或快照状态，与更新到回需要整个块。在提交（第49行和第62行）和中止（第35）时，写事务从URCU离开算法1示出了冲突时事务中止过程的代码。在abortTx（）期间，事务释放它在执行期间获得的锁，并将更改回滚到Main。此外，它离开了URCU，因此线程不再被认为能够修改Back。由于被中止的事务可能在执行期间获得了锁，因此如果它们在状态为DUP-LICATE_BLOCK时开始执行，则它们负责将锁定的块复制到Back（第32行）。内存管理。TL4x遵循一个安全的内存recla- mation计划，并使用自己的内存分配器的机密- ory分配和解除分配的事务。 它不会泄漏内存，既不易失也不持久，即使在崩溃时也是如此，因为它的操作被认为是事务的一部分，因此服从相同的全有或全无语义。 粗略地说，它维护一个堆栈集合，这些堆栈代表不同大小的空闲块。 如果所需大小的块在相关堆栈中不可用，则分配器分配满足要求的附加块。 在释放内存时，释放的块被附加到相关堆栈。4.3复制线程复制线程有两个目的：第一，它转换TL4x的状态，第二，它负责将数据从Back复制到持久存储。 它在算法3中描述的无限循环上运行。最初，状态为DUPLICATE，复制线程确定是否需要在Back上冻结快照。如果自上次Back被持久化以来全局时钟前进超过预定义值（MIN_TXN_SYNC），或者当不可撤销的读卡器通过读卡器计数器请求时，则需要快照。我们将这些事件分别称为持久化事件和读快照事件复制线程重置COUNTER_ON以防止其他不可撤销的读取器递增读取器计数器。然后，它触发URCU同步，之后Back是Main的一致快照，在最后一个提交或中止的事务没有观察到SYN-CHRONIZE或SNAPSHOT状态时。如果Back由于持久事件而被冻结，则复制线程通过比较时间戳0和1来确定要更新的持久副本，并选择最新的。我们将选择的复制品表示为 。 在persistTo（）过程中，Back的内容以以下方式复制到。首先，将Back中每个块的时间戳与转换到SYNCHRONIZE时记录的时间戳和的时间戳进行比较 。 如果它在它们之间，则块从Back复制到 。在此复制过程之后，刷新相关的高速缓存行并发出存储器围栏接下来，更新磁盘的时间戳，并为磁盘添加flush、fence或msync（），使其可以安全地用于恢复。最后，它更新的时间戳 。 在这两种情况下（per-sist事件和read snapshot事件），复制线程等待，直到所有正在进 行 的 不 可 撤 销 读 取 器 完 成 ， 然 后 将 系 统 转 换为DUPLICATE_BLOCK状态。在DUPLICATE_BLOCK中，复制线程设置COUNTER_ON以允许不可撤销的读取器递增读取器计数器。复制线程扫描锁和序列数组，查找Main上的序列大于Back上的序列的块，然后锁定并将它们复制到Back，跳过锁定的块。 在复制块之前，复制线程必须触发额外的URCU同步和停顿，以保证新的URCU同步。251TL4xPPoPP'23，2023年2月25日至3月1日，加拿大魁北克省蒙特利尔算法3- 复制线程循环publicvoid println（）{int lastSyncedTn = 0;101while（！public void run（）{returnfalse;103if（gClock.load（）（lastSyncedTxn + MIN_TXN_SYNC））{104if（gCounter.load（）== COUNTER_ON）{continue;}105}else{doPersists =true;}106if（doPersistr）{ lastSyncedTxn = gClock.load（）;}gCounter.fetch_sub（COUNTER_ON）;108gState.store（STATE_SYNCHRONIZE）;109urcu.synchronize（）;110gState.store（STATE_SNAPSHOT）;115uint64_t usedSize = persistTo（p，lastSyncedTxn）;116PFENCE（）;//仅限NVMM117MSYNC（p +sizeof（p−>ts），usedSize）;//仅118p−>ts = lastSyncedTxn;119//时间戳仅在用户数据持久化后才持久化算法4- 恢复publicvoidrun（）{134//根据时间戳从一致持久区域135PMetaP0=（PMetaP0）BEGIN_P0;136PMetap1=（PMeta）BEGIN_P1;137PMet apcons=（p 1−>ts>p0−>ts）？p1：p0;138PMet apincons=（p1−>ts>p 0−>ts）？p0：p1;139memcpy（BEGIN_BACK，pcons，REGION_SIZE）;// restore'back'140memcpy（BEGIN_MAIN，pcons，REGION_SIZE）;// restore'main'141//不要复制timestamp，它是PMeta中的第一个单词142memcpy（（uint8_t）pincons+sizeof（pincons−>ts），（uint8_t）pcons+sizeof（pcons−>ts），REGION_SIZE−sizeof（pcons−>ts））;143flushPWB（pincons，REGION_SIZE）;//刷新NVMM缓存行144PFENCE（）;//仅145MSYNC（pincons +sizeof（pincons−>ts），REGION_SIZE −sizeof（pcons−>ts））;//仅146pincons−>ts = pcons−>ts;147PWB（pincons−>p_ts）;//仅148PSYNC（）;//仅149MSYNC（pincons，sizeof（pincons−>ts））;//仅150gClock.store（pcons−>ts +1）;151}120PWB（p−>p_ts）;//仅121PSYNC（）;//仅122MSYNC（p，sizeof（p−>ts））;//仅123}124while（gCounter.load（）>0）{yield（）};//等待不可撤销的读取125gState.store（STATE_DUPLICATE_BLOCK）;126gCounter.store（COUNTER_ON）;127urcu.synchronize（）;128copyMainToBack（）;//更新快照129gState.store（STATE_DUPLICATE）;returnfalse;131}132}写入器观察到的状态为DUPLICATE_BLOCK。这是为了确保将每个锁定的块复制到Back。否则，观察到不同状态的飞行中写入器可能会解锁块而不更新Back，因此使其处于不 一 致 状 态 。 最 后 ， 复 制 线 程 将 状 态 转 换 回DUPLICATE。当持久化到磁盘时，msync（）可能会失败[53]。虽然在算法3中未示出，但是可以通过重复对persistTo（）的调用（行115）并重试msync（）来处理行117上的msync（）中的错误，而可以通过在重试msync（）之前重复对时间戳的写入（行118）来处理行122的msync（）中的错误。复制线程的进度条件是无阻塞饥饿[23]。只有三个等待循环，分别位于第124、109和127行，其中复制线程最 多 等 待 MAX_THREADS 其 他 线 程 。 复 制 线 程 使 用COUNTER_ON来防止不可撤销的读取器递增读取计数器，因此它将被不超过MAX_THREADS-1可拆卸阅读器（第124）。对于writer-ers ， 有 可 能 在 状 态 更 改 为 SYNCHRO-NIZE 或DUPLICATE_BLOCK（分别位于第109或第127行）之前，在URCU上出现persistTo（）与Back上的不可撤销读取 并 行 执 行 ， 并 且 不 会 被 推 测 性 事 务 阻 塞copyMainToBack（）复制所有其相关锁可由复制线程获取的块，并跳过锁定的块，因此也不阻塞。4.4恢复过程算法4详细介绍了TL4x背后的恢复机制。当存在持久性数据时，在初始化TL4x时进行恢复。它确定要读取的持久性副本是2010年和2011年之间更新的副本，此后表示为-是的我们把第二个复制品记为“辛孔”。的内容cons然后被复制到Main和Back，而不带时间戳。然后，没有时间戳的情况下，将Republiccons反射到Republicincons。更改被刷新，并且只有在之后时间戳才被更新和刷新。最后，全局时钟被设置为时间戳tagcons+1。4.5用户空间RCU我们实现了一个用户空间的RCU，通过写事务同步TL4x的状态的读访问，并通过复制线程更新状态。URCU集成了TL4x写事务在执行前执行arrive（），通过读取全局时钟并通知该时钟值（第14行），并在事务结束时通过清除通知的时钟（第35、49或62行）离开（）。复制线程在将系统状态从允许111public void run（）{112PMeta_P0=（PMet_P0）BEGIN_P0;113PMetaP1=（PMetaP1）BEGIN_P1;114PMeta =（p 1−>ts>p 0−>ts）？p0：p1;//更新旧区域PPoPPGal Assa，Andreia Correia，Pedro Ramalhete，Valerio Schiavoni，a
我的内容管理
展开
