2PLSF：高度可扩展的无饥饿保证的两阶段锁定

3902PLSF：具有无饥饿保证的两阶段锁定0Pedro RamalheteCisco Systemspramalhe@gmail.com0Andreia CorreiaNeuchâtel大学andreia.veiga@unine.ch0Pascal FelberNeuchâtel大学pascal.felber@unine.ch0摘要0两阶段锁定（2PL）是在40多年前发明的，它能够在多个记录上提供不透明的事务。然而，经典的2PL在应用于具有大量非不相交读访问的工作负载时可能会遇到活锁问题，并且其可扩展性较低。在本文中，我们提出了一种新的2PL算法（2PLSF），通过利用一种新颖的读写锁，提供具有无饥饿保证的高度可扩展的事务。我们的2PLSF并发控制可以应用于记录、元数据和数据库管理系统（DBMS）中使用的索引数据结构。在我们的实验中，我们展示了2PLSF通常优于经典的2PL，并且可以超越具有乐观读取的并发控制，同时为不相交和非不相交的工作负载提供高吞吐量和低延迟。0CCS概念•计算理论�并发算法。01 引言0在数据库管理系统（DBMS）的背景下，两阶段锁定（2PL）在1976年被发明，是提供可串行化事务的通用并发控制的第一种[1,10]。在2PL中，在访问记录（无论是读取还是写入）之前，必须获取保护记录的锁。事务结束时释放锁。名称“两阶段”来自两个不同的阶段：锁获取在第一（扩展）阶段完成，锁释放在第二（收缩）阶段完成。为了保证可串行性，一旦释放第一个锁，就不能再获取其他锁。更具体地说，2PL确保了不透明性[14]，这是一种比可串行性更强的条件。不透明性保证没有正在进行的事务可以看到尚未0未经费用许可，允许个人或课堂使用本作品的全部或部分数字或硬拷贝，前提是不得为盈利或商业优势而制作或分发拷贝，并且拷贝必须带有本通知和第一页的完整引用。必须尊重比作者（们）拥有的本作品组成部分的版权。允许带有信用的摘要。要进行其他复制、再版、发布到服务器或重新分发到列表，需要事先获得特定的许可和/或费用。请向permissions@acm.org请求权限。PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔©2023版权归所有者/作者所有。出版权由ACM许可。ACM ISBN 979-8-4007-0015-6/23/02...$15.00https://doi.org/10.1145/3572848.35774330已提交。实际上，这意味着所有事务都是可串行化的，无论是已提交的事务还是已中止的事务。这种行为通过确保事务执行期间应用程序不变量保持不变来简化编程[23]。2PL实现通常使用互斥锁来进行读访问[29]，原因是常见的读写锁在短暂的读锁获取上具有较差的可扩展性。这是因为在计数活动读者数量的变量上存在争用，因此被称为读指示器。读指示器[9,17]是一个并发对象，提供三个函数：arrive()，depart()和isEmpty()。虽然文献中存在可扩展的读写锁，通过将读指示器分割成多个缓存行，以减少争用[2,17]，但我们不知道有哪些2PL实现使用了这些读写锁。因此，现有的2PL实现在大多数或所有事务读取相同对象的读多工作负载下扩展性较差。当将2PL用作基于树的索引数据结构的并发控制时，这一点尤为明显，其中所有线程必须读取树的根节点以访问其预期的键。换句话说，对树的所有操作都需要获取保护根节点的读锁，从而导致扩展性瓶颈。因此，DBMS更喜欢使用并发控制具有乐观读取的索引数据结构的使用。乐观并发控制技术在执行读访问时不获取读锁，而是使用序列锁或类似的版本机制来检查在读访问期间数据是否被修改。在处理冲突的方式方面，2PL有三种主要变体，分别称为无等待、等待或死亡和死锁检测[1,28,29]。2PL无等待变体使用退避策略，在检测到锁冲突时立即中止事务。2PL等待或死亡变体对所有事务强加一个顺序，通常使用事务开始时的时间戳，并在发生锁冲突时通过比较事务的时间戳和锁所有者的时间戳来决定等待锁还是中止。2PL死锁检测变体保持一个内部线程列表，该列表等待锁并检测循环（死锁）。存在一种名为wound-wait的等待或死亡变体，其中导致冲突的事务被中止[4]，而不是等待或死亡变体中的事务中止自身。等待或死亡和死锁检测方法可以实现无活锁。根据我们的最佳7 // central clock for conflicts8 atomic conflictClock = 1;9 // unique thread id for a thread10 thread_local uint16_t tl_tid;11 T stmRead(T∗ addr) {12if (!tryOrWaitReadLock(addr2lockIdx(addr))) restartTxn();13readlockSet.log(addr);// save address to later unlock14return ∗addr;// read data15 }16 void stmWrite(T∗ addr, T newValue) {17if (!tryOrWaitWriteLock(addr2lockIdx(addr))) restartTxn();18writeSet.log(addr, ∗addr);// save address and original value19∗addr = newValue;// write to data20 }21 void beginTxn() {// always inlined or preprocessor macro22setjmp();23readSet.reset();24writeSet.reset();25// will do nothing on the first attempt26while (announceTS[tl_otid] == tl_oTS) pause();27 }28 void commitTxn() {29writeSet.unlock();30readSet.unlock();31tl_myTS = NO_TIMESTAMP;32announceTS[tid].store(NO_TIMESTAMP);33 }34 void restartTxn() {35writeSet.rollbackModifications();36writeSet.unlock();// calls writeUnlock() for every entry37readSet.unlock();// calls readUnlock() for every entry38longjmp();// continues at setjmp() in beginTxn()39 }40 // returns the index of the lock which protects a given address41 uint32_t addr2lockIdx(void∗ addr) {// example of lock hashing42return (((uint64_t)(addr) >> 5) & (NUM_RWL−1));43 }400PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 Pedro Ramalhete，Andreia Correia和Pascal Felber0据我所知，除了PLOR[4]之外，没有其他基于这些变体的算法提出了饥饿自由，这是保证每个事务及时执行的重要进展条件。在本文中，我们提出了2PLSF，一种具有类似于2PLwait-or-die的冲突策略的两阶段锁并发控制，然而，2PLSF能够提供可扩展的无饥饿事务。我们的目标是展示2PLSF可以为DBMS提供可扩展性，包括索引数据结构，并且可以同时部署在这些数据结构和数据库记录上，从而简化DBMS的实现和维护。2PLSF通过两个独特的特性实现了这一目标。第一个特性是使用高度可扩展的读写锁，将读指示器分割到多个缓存行中，每个读指示器每个线程一个位，将64个读写锁（对于一个线程）的读指示器聚合到一个64位字中。这种方法减少了内存使用量，并允许使用原子存储释放进行读锁释放，这种操作的同步成本低于顺序一致的存储或原子递减。第二个特性是使用集中式原子计数器仅在冲突发生时对事务进行排序。与2PLwait-or-die每个事务都增加一个中央时钟不同，2PLSF的读写锁每个事务最多增加一次中央时钟，即第一次检测到冲突时，导致中央时钟变量上的争用较少，从而提高了可扩展性。此外，我们的读写锁允许2PLSF跟踪导致冲突的线程/事务，这意味着中止的事务只需等待冲突的事务，而在2PLwait-or-die中，中止的事务必须等待所有时间戳较低的事务，即使它们是非冲突的。这为2PLSF提供了高效的冲突解决，特别是在具有成对冲突的工作负载中，它能够提供可扩展性。总结起来，本文的主要贡献有：0•一种新的读写锁，提供无饥饿和由于其独特的内存布局，在读访问上具有高可扩展性；0•利用上述的读写锁，提供了一种新颖的两阶段锁算法（2PLSF），它提供了无饥饿和不透明的事务，保证最多重新启动 � �������  −0•在2PLSF中，只有冲突的事务被排序，并且每个冲突的事务只需等待导致冲突的特定事务。0本文的其余部分组织如下。我们首先在第2节中介绍了我们的并发控制2PLSF。我们在第3节中对2PLSF进行评估。然后我们在第4节中讨论相关工作。最后我们在第5节中总结。02 无饥饿的两阶段锁0像2PL这样的并发控制可以管理对数据的单个读写访问。当在软件事务内存（STM）中部署时，这些被实现为读取和写入的插入函数，即stmRead()和stmWrite()，如算法1所示。0算法1 —— STM函数01  // 读写锁的总数02 uint64_t NUM_RWL = 4 * 1024 * 1024ULL; // 400万个锁03  // 时间戳数组，所有条目都初始化为NO_TIMESTAMP04 atomic announceTS[MAX_THR];06 uint64_t NO_TIMESTAMP = 0;0与2PL类似[1]，在进行读取或写入操作之前必须先获取锁。如果锁获取失败（在第12或17行），事务将重新启动，这将撤销事务中到目前为止的任何写入，并释放锁（第34行），然后跳回事务的开始处。2PLSF: Two-Phase Locking with Starvation-FreedomPPoPP ’23, February 25-March 1, 2023, Montreal, QC, Canada44 atomic wlocks[NUM_RWL];// initialized to zero46 thread_local uint16_t tl_otid = NO_TID;48 thread_local uint64_t tl_oTS = NO_TIMESTAMP;50 thread_local uint64_t tl_myTS = NO_TIMESTAMP;51 bool tryOrWaitReadLock(uint32_t widx) {52riArrive(widx);53uint16_t wstate = wlocks[widx].load();54if (wstate == UNLOCKED || wstate == tl_tid) return true;55if (tl_myTS == NO_TIMESTAMP) {56tl_myTS = conflictClock.fetch_add(1);57announceTS[tl_tid].store(tl_myTS);58}59while (true) {60if (wlocks[widx].load() == UNLOCKED) return true;61tl_oTS = getTSOfWLock(widx);62if (tl_oTS < tl_myTS) {63// write−lock taken by other thread with lower timestamp64riDepart(widx);65return false;66}68}69 }70 void readUnlock(uint32_t widx) {71riDepart(widx);72 }73 void writeUnlock(uint32_t widx) {74wlocks[widx].store(UNLOCKED);75 }76 bool tryOrWaitWriteLock(uint32_t widx) {77uint16_t wstate = wlocks[widx].load();78if (wstate == UNLOCKED && wlocks[widx].cas(wstate,tl_tid)) {79if (ri.isEmpty(widx)) return true;80}81if (tl_myTS == NO_TIMESTAMP) {82tl_myTS = conflictClock.fetch_add(1);83announceTS[tl_tid].store(tl_myTS);84}86() {87wstate = wlocks[widx].load();88if (wstate == UNLOCKED) wlocks[widx].cas(wstate, tl_tid);89wstate = wlocks[widx].load();90if (wstate == tl_tid && ri.isEmpty(widx)) {93riDepart(widx);94return true;95}96tl_oTS = getLowestTS(widx);97if (tl_oTS < tl_myTS) {99riDepart(widx);100if (wlocks[widx].load() == tl_tid)101wlocks[widx].store(UNLOCKED);102return false;103}105}106 }410算法2 - 2PLSF使用的读写锁045  //与此线程发生冲突的线程的线程标识符047  //与此线程发生冲突的线程的时间戳/优先级（tl_otid）049  //当前线程事务的时间戳/优先级067 pause(); //暂时等待085 riArrive(widx); // 作为读者到达091 // 即使以前已经清除了读指示器，也可以清除092 // 由于锁已升级，因此处于读锁定状态098 // 由时间戳较低的线程获取的写/读锁0104 pause(); // 等待0在beginTxn()中。我们的实现使用写透传协议（undo-log），然而，也可以使用写回协议（redo-log），并且可以与急切锁定或延迟锁定一起使用[12]。02.1 算法概述2PLSF中的事务在进行读访问之前会获取读锁，并在进行写访问之前获取写锁。在事务中首次发生锁冲突时，会从名为conflictClock的全局原子时钟中获取一个时间戳，并在一个数组中宣布该数字，每个线程对应一个条目，announceTS[tl_tid]（第57行和83行）。当发现冲突锁时，未能获取锁的线程（冲突的事务）将读取当前持有锁的线程的线程ID（tid），并读取announceTS[tid]中的相应条目，以确定冲突事务的时间戳。在存在多个持有读锁的线程时发生冲突时，冲突的事务将扫描持有读锁的事务的时间戳，并等待具有最低时间戳的事务（第125行）。如果持有锁的事务的时间戳高于0试图获取锁的事务，然后冲突的事务等待锁被释放，否则冲突的事务将撤消其修改，释放所有锁并重新开始（第34行）。冲突的事务在引起冲突的事务完成之前不会重新开始（第26行）。当另一个事务提交时，它将清除其宣布的时间戳（在第32行），从而允许等待的线程开始并重新尝试其事务。这种行为是可能的，因为每个尝试读锁的线程都会单独在读指示器上宣布其到达，而大多数读写锁使用原子计数器[2，17]。我们的读写锁使用此机制来识别导致冲突的线程（第65行和102行），并将此信息保存在线程本地变量（tl_otid）中，以及相应的时间戳（tl_oTS）。请考虑与2PLno-wait的行为差异，每个中止的事务都会等待一段退避时间，因此容易出现活锁问题，或者与2PLwait-or-die的行为差异，后者必须等待所有其他时间戳较低的线程，即使它们没有冲突。420PPoPP ’23，2023年2月25日至3月1日，加拿大蒙特利尔，Pedro Ramalhete，Andreia Correia和Pascal Felber02.2 无饥饿性在STM的上下文中，无饥饿性的属性有时被定义为：每个被无限次重试的中止事务最终都会提交[3]。我们的2PLSF算法提供了更强的保证，对每个事务重试的次数有一个上限。当发生读写冲突时，检测到冲突的线程将进入tryOrWaitReadLock()的慢路径，并且如果是第一次重启，将获取一个时间戳（第56行）以确定其相对于其他事务的优先级。然后它将等待（第67行），直到成功获取读锁（第60行），或者当前持有写锁的事务具有较低的时间戳（第65行），在这种情况下，它将重启事务，恢复所有修改并释放到目前为止获取的所有锁，然后等待冲突事务提交后再重新启动事务（第26行）。当发生写写冲突或写读冲突时，检测到冲突的线程将进入tryOrWaitWriteLock()的慢路径，并且如果是第一次重启，将获取一个时间戳（第82行）以确定其相对于其他事务的优先级。然后它将等待（第104行），直到成功获取写锁（第94行），或者当前持有写锁或读锁的事务具有较低的时间戳（第96行），在这种情况下，它将重启事务，恢复所有修改并释放到目前为止获取的所有锁，然后等待冲突事务提交后再重新启动事务（第26行）。事务可能由于写写冲突、读写冲突或写读冲突而重启，但重启次数受到�个线程-1的限制。一旦时间戳在announceTS[tid]（第57行或83行）中宣布，直到事务提交（第32行）之前不会被清除。根据定义，所有后续的冲突事务都将具有较高的时间戳，取自conflictClock。这意味着当前事务在提交之前最多需要由其他事务重启�个线程-1次，因为在�个线程-1次尝试之后，该事务将成为具有最低时间戳的正在进行的事务，因此，在后续的锁冲突事件中，它将等待当前所有者线程释放锁。请注意，其他线程将释放锁，要么是因为它已提交，要么是因为它检测到与具有较低时间戳的事务的冲突。02.3 为什么无饥饿锁还不够0文献中存在几种具有无饥饿进展的互斥锁[19, 21,25]和具有无饥饿进展的读写锁。尽管我们不知道有无饥饿进展的高度可扩展的读写锁，可以同时对读和写锁进行获取，即使使用这样的算法，也无法获得无饥饿的并发控制。要理解原因，考虑一个具有两个事务的场景，其中一个事务访问�记录，然后紧跟着访问记录0�，而另一个事务访问�之后紧跟着的�记录。假设每个记录都受到单独锁的保护，如果第一个事务获取了�的锁，第二个事务获取了�的锁，那么两个事务都无法访问对方的记录，从而创建了死锁的情况。即使每个锁都提供了无饥饿进展，这种情况仍会发生。请注意，具有无饥饿进展的互斥锁算法是通过lock() API实现的，而并发控制是使用trylock()API获取锁，根据定义，trylock()不会等待，因此不是无饥饿进展。因此，我们的2PLSF算法使用了一个不同的API，我们称之为tryOrWaitLock()，它可以在获取锁时等待，成功获取锁时返回true，锁获取失败时返回false。02.4 读写锁0我们的读写锁设计时考虑了两个主要前提：只有在发生冲突时才解决冲突，并布置读指示器以减少伪共享。第一个前提是除非存在冲突，否则不需要对线程/事务进行排序。当部署在并发控制的上下文中时，大多数锁获取尝试都预计是成功的，即没有发生锁冲突。因此，我们通过在tryOrWaitReadLock()的成功获取的短代码路径（第52-54行）和tryOrWaitWriteLock()的成功获取的短代码路径（第76-79行）进行算法优化。只有当这个快速路径无法获取锁时，它才从conflictCLock中获取一个时间戳，以建立线程/事务的精确执行顺序（第56行和82行）。这种行为可能与对每个事务进行排序稍有不同，这就是2PLwait-or-die所做的，然而，通过仅在需要时递增conflictCLock，它消除了阻碍2PLwait-or-die可扩展性的重要瓶颈。我们将在第3节中展示这些效果有多大。第二个前提是通过使用定制的读指示器，2PLSF能够将内存使用量减少到每个线程和每个锁的一位，同时防止读指示器中的伪共享。图1显示了我们实现中使用的可扩展rw-locks的内存布局。我们的读写锁的布局是这样的，每个线程为每个锁保留一个位的读指示器。无饥饿锁通常使用原子递增指令（fetch_add()）来计数等待的线程。在我们的读写锁中，位对于每个线程是连续的，这意味着将读指示器设置回零可以使用store(memory_order_release)而不是fetch_add()，这在大多数体系结构中都是更快的操作，包括x86。在这种设计中，每个锁的内存使用量是每个线程的位数加上存储线程ID所需的位数（我们的实现中为16位）。此外，为了表示读指示器中的每个线程，使用了一个单独的位。(1 bit per thread)...4 million entries...4 million entries...4 million entriesarray with 4 million entries(64 MAX_THR entries4302PLSF：具有无饥饿自由的两阶段锁定PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0readIndicator0线程10线程20线程30（每个线程16位）tid tid tid tid tid ...0... announceTS0图1.2PLSF中使用的读写锁的内存布局。wlock最多需要16位来存储唯一的线程标识符，因此支持2^16个线程。相同颜色的块表示一个读写锁的变量。0每个线程都很重要，这样冲突的线程可以确定当前持有读锁或等待写锁的线程。在我们的实现中，我们使用了400万个读写锁（第96行），每个锁保护32字节的数据（第41行），但可以选择其他设置。在算法3中，我们展示了我们的读指示器实现和在每个冲突中找到最低时间戳的辅助函数。02.5 RW-Lock TryOrWaitLock当tryOrWaitReadLock()或tryOrWaitWriteLock()中发生冲突时，如果尚未分配时间戳，则为该事务分配一个唯一的时间戳，即这是该事务首次遇到锁冲突。然后，在一个特定于线程的入口的公告数组announceTS[tl_tid]中宣布时间戳（第57行）。tryOrWaitReadLock()函数然后进入一个等待循环，只有在出现以下条件之一时才退出：•持有写锁的事务宣布了较低的时间戳：通过返回false重新启动当前事务（第65行）。0•持有写锁的事务已释放该锁：此事务现在已获取读锁。通过返回true继续执行当前事务（第60行）。tryOrWaitWriteLock()函数进入等待循环，只有在以下条件之一发生时才会退出。•持有写锁的事务宣布了较低的时间戳：通过返回false重新启动当前事务（第102行）。0•读指示器中宣布时间戳最低的事务的时间戳低于当前事务：通过返回false重新启动当前事务（第102行）。0•使用CAS在wstate上获取了写锁（第78或88行）且读指示器为空（第79或90行）：返回true以继续执行当前事务（第94行）。0当线程调用tryOrWaitWriteLock()获取锁时，如果当前有另一个线程持有写锁或多个线程持有读锁，只要它们的时间戳高于线程的时间戳，调用线程将等待锁释放。一个重要的细节是，当线程�调用tryOrWaitWriteLock()并且有另一个线程�以较高的时间戳持有写锁时，线程�将为此锁标记其读指示器（第85行）。到达读指示器确保即使另一个线程�（具有较高时间戳）在wstate上成功执行CAS（第88行），线程�在CAS之后（第90行）不会看到空的读指示器，并且在看到较低的时间戳时重新启动（第96行）。因此，通过使写者标记读指示器，我们保证了可以获取锁（具有较高时间戳）的写者数量是有限的。02.6 正确性0与经典的2PL类似，在2PLSF中，所有数据访问都在锁的保护下进行。在stmRead()中，我们首先获取读锁（第12行），然后读取数据（第14行）。在stmWrite()中，我们首先获取写锁（第17行），然后写入内存位置（第19行）。在重新启动（第36和37行）或事务提交（第29和30行）时释放所有锁，从而像经典的2PL一样保证了不透明性。剩下的就是证明2PLSF使用的读写锁提供了正确的互斥性。这可以分为三种互斥性场景：写-写、读-写和写-读。通过比较并交换指令，将wlocks[widx]从UNLOCKED原子地更改为线程的唯一标识符（第78或88行），从而确保一次只有一个线程拥有写锁，从而保证了写-写的互斥性。在设置了写者状态的同时检查读指示器是否为空（第79和90行），从而提供了写-读的互斥性。这意味着当读者已经在读临界区时，写者将不会拥有锁。通过在设置了读指示器后检查写者状态（第53和60行），实现了读-写的互斥性。这意味着当写者已经在写临界区时，读者将不会拥有锁。这个证明的概要表明我们的读写锁提供了正确的互斥性。02.7 调试能力在实际中，2PL算法相对于具有乐观访问的并发控制具有重要优势：当使用调试器检查事务中的变量时，例如在事务代码中由用户引入的错误的情况下，对于具有乐观访问的STM，事务期间先前读取的任何变量可能在此期间已被另一个线程的事务修改。2PL和2PLSF没有这样的限制，因为它们对数据的每次读写访问都会获取锁。104 }110 }120 }123 }136}139 }150}153 }440PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 Pedro Ramalhete，Andreia Correia和Pascal Felber0算法3 - 读写锁的辅助函数和变量0uint64_t NUM_RI_WRD = NUM_RWL * MAX_THR / 64;0初始化为零0atomic readIndicators[NUM_RI_WRD][MAX_THR];0位0void riArrive(uint32_t widx) {0uint32_t ridx = widx2ridx(widx);0uint64_t ri = readIndicators[ridx].load();0readIndicators[ridx].store(ri | ribit(widx));0void riDepart(uint32_t widx) {0uint32_t ridx = widx2ridx(widx);0uint64_t ri = readIndicators[ridx].load();0readIndicators[ridx].store(ri & (~ribit(widx)));0true0bool riIsEmpty(uint32_t widx) {0对于(uint16_t itid = 0; itid < maxThreads; itid++) {0如果(itid == tid) 继续;0uint64_t offset = itid * NUM_RI_WRD / MAX_THR;0idx / 64)].load();0如果(ri & ribit(widx)) 返回false;0返回true;0返回tid * NUM_RI_WRD / MAX_THR + (widx / 64);0返回任何冲突线程的最低时间戳0uint64_t getLowestTS(uint32_t widx) {0对于(uint16_t itid = 0; itid < maxThreads; itid++) {0如果(itid == tid) 继续;0uint64_t offset = itid*NUM_RI_WRD/MAX_THR;0/ 64)].load();0如果((ri & ribit(widx)) == 0) 继续;0[itid].load();0如果(oTS < lowestTS) {0lowestTS = oTS;0tl_otid = itid;0返回lowestTS;0返回持有写锁的线程的时间戳（如果已获取）0uint64_t getTSOfWLock(uint32_t widx) {0uint64_t lowestTS = NO_TIMESTAMP;0如果(wstate != UNLOCKED && wstate != tid) {0uint16_t otid = wstate;0[otid].load();0如果(oTS < lowestTS) {0lowestTS = oTS;0tl_otid = otid;0返回lowestTS;0返回(1ULL << ((widx) % 64));0因此，在事务停止的时间点之前，提供了所有变量的一致视图。这意味着使用gdb等工具来调试使用2PL和2PLSF的用户事务代码变得更加容易。02.8 不可撤销性多写并发控制面临冲突重启的问题，导致每个事务可能重启多次，有时被称为 speculative执行。为了解决这个问题，一些并发控制提供了不可撤销性，即事务在执行过程中永远不会重启。根据定义，多个不可撤销的只读事务可以并发执行，然而，一次只能执行一个不可撤销的写事务。Welc等人提出了一种技术，用于为具有乐观读取（如TL2和LSA）的并发控制提供不可撤销的事务，通过在不可撤销事务的加载插入期间回退到获取读锁，从而绕过在提交时需要进行读集验证阶段的需求。然而，与基于2PL的其他方法相似，具有读写锁的这些技术由于锁上的争用而扩展性差。0如果我们愿意牺牲无饥饿自由，2PLSF可以提供不可撤销的只读事务。只需将不可撤销的只读事务的时间戳设为零，即可确保事务永远不会重新启动。可以通过添加一个零互斥量来进一步修改2PLSF，以提供不可撤销的写事务，当获取该互斥量时，事务有权选择零时间戳。该事务将永远不会重新启动，并在执行结束时释放零互斥量。这种方法有效地将所有不可撤销的写事务串行化，因为它们将等待获取零时间戳。02.9 内存回收0在部署并使用系统分配器时，必须进行额外的工作来动态分配和释放对象。在提交时，具有乐观访问的并发控制必须使用安全的内存回收方案（SMR），将分配列表中的每个对象传递给SMR。由于其简单性，通常选择的方案是基于时代的回收（EBR）[6, 12, 30]。051015 16 32 48 64 16 32 48 64 16 32 48 644502PLSF：具有无饥饿自由的两阶段锁定 PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0对于两阶段锁定算法，例如2PL和2PLSF，可以在提交时立即释放分配日志中的对象，而无需使用内存回收方案。这样做是安全的，因为在每次读访问时获取的读锁保证了无论读取的指针是什么，该指针都没有被其他事务修改（因为这将需要对指针进行写锁定），从而保证了对象是可达的。2PL不需要实现和执行内存回收方案，这减少了选择2PLSF与具有乐观读取的方法之间的工程工作量。此外，使用内存回收方案可能会引入额外的内存需求来存储已退役对象的列表，并且可能会对执行大量分配和释放的工作负载产生性能影响。实质上，无论内存回收方案在空间和时间上有多高效，2PL和2PLSF不需要回收方案是乐观并发控制的一个重要优势。比安全内存回收更强的属性是私有化。与其他2PL算法类似[8]，2PLSF提供了隐式私有化[20]，包括隐式代理私有化[16]。这个保证直接源于事务的悲观性质，并且没有任何额外的性能开销[8]。03 评估我们现在对2PLSF进行评估，并将其与其他最先进的STM实现进行比较，当应用于事务数据结构时，使用合成基准测试。我们在一台双插槽2.50 GHz Intel Xeon E5-2683v4的计算机上执行这些微基准测试，该计算机具有32个超线程核心（64个硬件线程）。该机器运行Ubuntu LTS20.04，并使用gcc10.3.0和-O2优化标志。在接下来的几节中，我们将研究使用各种STM实现部署事务性集合数据结构时的吞吐量。在最左边的图中，工作负载由50％的随机插入和50％的删除组成。中间的图中有10％的插入，10％的删除和80％的查找。最右边的图仅执行查找。每个数据点表示20秒内5次运行的平均值。03.1 不同的RW-Locks我们从逐步比较不同的2PL算法和锁开始。图2中标记为2PL-RW的数据点表示使用单个64位字实现的2PL算法，其中8位保留用于标识持有写锁的线程，剩余的位数用于056位读指示器，每个线程保留一个位来持有读锁。这个实现最多支持56个并发（读）线程。将每个线程分配到锁变量的特定位上可以快速识别当前线程是否已经持有读锁，从而能够在事务期间高效检测读-读场景。因此，当多个线程读取二叉搜索树的根指针时，会导致保护它的读写锁的争用，因为在同一个锁的变量中执行大量的fetch_add()指令。这在图2中是明显的，2PL-RW（深蓝色线与倒三角形）无法实现扩展，即使在只读工作负载（最右边的图）上也是如此。在两阶段锁并发控制中部署读写锁的想法并不新鲜，并且之前已经被Dice等人[8]在TLRW并发控制中研究过。如图2所示，并且如本节后面将展示的那样，除非使用可扩展的读写锁，否则2PL的扩展性将很差。0带有10^6个键的放松AVL树 i=50% r=50% l=0%0操作（×10 6/s）025 i=10% r=10% l=80%25050 i=0% r=0% l=100%50 2PLSF02PL-RW-Dist02PL-RW0图2.带有三种不同2PL算法的RAVL树。0如果一个实现使用了一个读写锁，其中每个线程的读指示器位于一个单独的缓存行上，那么它能够在大多数读取工作负载（图2中用轻蓝色线和上三角形表示的2PL-RW-Dist）中实现高可扩展性。使用单独的缓存行来存储读指示器的想法并不新鲜，并且之前已经被Dice等人[2]研究过。据我们所知，我们的方法是第一个将多个读指示器与每个线程结合起来以减少伪共享而不增加内存占用的方法。我们在算法1中描述的2PLSF并发控制使用与2PL-RW-Dist相同的读指示器布局，但是以一种可以保证无饥饿和高效冲突检测的方式进行。与大多数其他并发控制一样，2PL-RW-Dist使用了一种解决冲突的退避策略，这种策略在文献中被称为2PLNo-Wait[28,29]，而我们的2PLSF则没有退避。如图2所示，在读多工作负载（最右边的图）上，2PLSF方法与2PL-RW-Dist没有优势，然而，在写密集型工作负载（最左边的图）上，2PLSF在解决冲突方面显著快于2PL-RW-Dist，使其比2PL-RW-Dist快2倍以上。我们在执行的所有工作负载中都观察到了这个优势。00.10.20.3 16 32 48 64 16 32 48 64 16 32 48 640204060 16 32 48 64 16 32 48 64100100 16 32 48 6450050001234 16 32 48 64 16 32 48 64 16 32 48 64460PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔 Pedro Ramal