原文作者：
- Irina Calciu Brown University irina@cs.brown.edu
- Dave Dice Oracle Labs dave.dice@oracle.com
- Yossi Lev Oracle Labs yossi.lev@oracle.com
- Victor Luchangco Oracle Labs victor.luchangco@oracle.com
- Virendra J. Marathe Oracle Labs virendra.marathe@oracle.com
- Nir Shavit MIT shanir@csail.mit.edu
摘要
因为多核和多芯片计算机的快速增长，非一致性内存访问(NUMA)架构在主流计算机系统中的地位越来越重要。为了在这些新系统上获取最好的性能，我们需要重新修改当前程序组成部分的并发算法和同步原语。这篇论文重新设计了很关键的同步原语——读写锁。
据我们所知，本文论述的读写锁是第一个专门为NUMA架构设计的，以及这个读写锁的变种。这些变种考虑了在高并发读的情况下的读和写的公平性以及在同一个NUMA节点上让写批量运行。我们的算法利用群组所技术来处理写者之间的同步，比较适合NUMA架构，同时使用二进制标志来协调读者和写者，利用简化的读者计数器，可以在NUMA上使读者间取得更好的并发性。最经过我们的基准程序测试之后，这些简单的NUMA锁算法竟然比目前比较出色的读-写锁的效率还高出10倍以上。为了了评估在真实环境中我们算法的效率，我们也提供了用基准程序 kccachetest测试的结果。Kccachetest属于Kyoto-Cabinet 发行版，这是一个开源的数据库使用了大量的 pthread 线程库的读写锁。跟最好的锁比，我们的锁也把kccachetest的效率提升了40%。
1.介绍
因为微处理器的厂商不断的追求多核和多芯片系统(Intel的Nahalem 和Oracle Niagara平台是比较典型的例子)，计算机工业界正在快速采用分布式和缓存一致性的NUMA架构。这些系统都包含有多个节点，每个节点都有自己的内存，缓存和多核处理器。这些系统呈现了一个统一的编程模型，内存全局可见和缓存一致。在节点间的缓存一致性通信通道被称为外部互联。跟节点内的通道相比，这些节点间的链路一般延迟比较大且带宽比较低。为了降低延迟和少用占用互联带宽，NUMA策略鼓励节点内通信而不是节点间。
在NUMA架构上编写一个高效的软件是非常有挑战的意见事情，因为这类系统对内存和处理器之间的关系抽象的比较初级和“扁平化”，为程序员隐藏了真是的拓扑模型。程序员必须参阅架构手册和使用系统相关的库函数才能知道系统的拓扑结构。不考虑NUMA的多线程程序会有不少效率问题，主要是节点间的内存一致性的通信和节点间带宽引起。而且节点间互联通道是共享资源， 对其竞争和延迟，会导致有一个线程产生的缓存一致性通信会影响另外一个不相关的线程。在移植到NUMA架构之前，目前多线程程序中的并发数据和同步结构都需要仔细的设置。很重要的同步结构是读写锁。
读写锁放宽传统互斥锁的限制，允许多个读线程同时拥有锁。写线程仍需互斥访问。读写锁的使用范围非常广泛，包括操作系统内核，数据库，高端科学计算软件，软件内存事务中[6]。
读写锁已经被研究了几十年了[1,2, 11, 13–16],有简单的计数器和信号灯的方案[2]，利用中心等待队列[14,16]，也有用类似可伸缩的非零指示器（SNZI）[15]等更高级的数据结构。在所有这些方案中，SNZI依赖于中心数据结构来协调各个线程，所以会遇到可升缩性问题[15]。SNZI算法通过把读者放到SNZI树的叶子节点上来追踪写者（请求读锁的线程）。通过把SNZI树的叶子节点分到不同的NUMA节点，读线程就可以知道自己在NUMA上哪个节点了。而写线程依旧忽略NUMA，所以会有伸缩性问题。
Hsieh，Weihl和Vyukov独自提出了一种简单分布式的方式来实现读写锁。每个分布式的读写锁包括N（N是系统处理器个数）个读写锁。每一个读者分配一个读写锁，在执行读临界区之前必须获取这把读锁。通过强制的加锁次序来避免写者之间的死锁。这个方法可以用到NUMA架构上，把N限制为系统中NUMA节点的个数，每个读者分配节点专属的锁。我们把这个变化了的算法称作DV，一定程度上感知了NUMA，跟SNZI读写锁类似 。在没有写者的情况下，在各个节点上的读者在获取和释放读权限时不会产生任何节点间的写一致性交互。 然而每一个节点上的写者在获取写权限时都会潜在的产生大量的节点间一致性交互。所以随着写次数的增加，DV的效率也会显著下降。由于使用加锁次序来避免死锁，在后加锁的节点上的读者比先加锁节点上的读者更有效率优势，这是不公平的。
这篇论文展示了一组转为NUMA设计的读写锁，相比之前的读写锁算法具有更好的性能和伸缩性。我们从三方面入手来设计我们的锁。第一，跟DV类似，我们维护了一个分布式的数据结构用来存储读者元数据，读者通过更新他们节点的位置信息来说明自己的意愿。通过读指示器来更新减少了节点间一致性的交互。第二，写者优先把访问权限交给跟自己同一节点的其它已经阻塞的写者，可以增强节点内部缓存的锁和临界区中要访问的数据局部性。最后，我们的算法为读者和写者维护了一个非常紧凑的执行路径，减少了获取和释放操作带来的延迟。
我们的读写锁算法基于目前刚开发的群组所技术，他允许创建NUMA的互斥锁。简单说，写者使用群组所来同步同时维护写者之间的互斥。使用群组所方式，写者正在释放的锁会优先交给跟自己同节点的处于阻塞的写者，因此可以减少锁在节点间的转移。
我们的读写锁也包括了分布式的读指示器，这个数据结构可以追踪读者。读者获取锁时会在读指示器中记录，释放锁会从读指示器中去除。写者查询读指示器来发现并发的活跃读者。由于读指示器是分布式的，读者只需要访问他们所在节点的锁的元数据就可以了。我们还额外使用了一个简单的标识变量用来协调读者和写者。这个简单的算法是的NUMA上的读写锁的效率远比之前很出色的算好要好。
我们提供的不同的读写锁可以用公平性这个属性来区分。我们也展示了不同的“优先”策略：读者优先，写者优先，中性策略。读者优先策略是尽快让读者获取锁，而不管到达的次序。而写者优先策略对于写者本身没有偏向性。具体一点说，这些优先策略允许读者和写者在竞争锁时比排在他们前面的写者和读者更早获取锁。除了中性策略之外的优先策略，会导致参与获取没有优先锁的线程饥饿。我们通过允许一定的锁机制改变优先策略来避免饥饿问题，饥饿的线程就可以继续往前执行了。饥饿的线程变得没有“耐心”了，短暂的改变了优先策略。
我们对我们的读写锁进行了实证测试，自己相互之间的性能比较以及和先前的读写锁进行比较。我们的测试是在 256路 4节点的 Oracle SPARC T5440 服务器上进行的，我们的读写锁的性能在各中类型的任务中都比要远超之前的读写锁。在我们自己的基准程序中，我们的锁比之前最好的读写锁（基于SNZI的ROLL锁）的性能都要强10倍。
第二节讨论了我们所的设计方法，第三节详细论述了我们的锁算法。第四节使我们的实证测试结果，第五节是我们的结论。
2. 锁设计原理
NUMA的互斥锁已经有不少人深入研究过了。然后据我们所知，还没有人研究过NUMA上的读写锁。NUMA的互斥锁只追求一个目标，就是减少锁的迁移，这样可以在节点内部保持锁和临界区域数据的局部性。NUMA互斥锁尽量减少写非法和一致性失效的比例，缓存的失效需要从另外的节点通过互联通道传输过来。我们认为跟通常的读写锁一样，NUMA的读写锁需要额外考虑尽量让读者之间高并发的执行。
我们发现这两个目标很难兼顾，提升节点间读者的并发性需要把锁的元数据以及临界区的数据分发到这些节点，而减少锁的迁移需要减少这种分发。然而这种显而易见的矛盾可以通过只在写者间减少锁的迁移，但同时让读者间更加高并发来解决。为了让这个策略更加有效，我们必须尽可能让并发的写者来自同一个NUMA节点，以保持锁在本地写者之间传递。我们注意到聚集写者的方式并不是完全不合适的。相反，它可以让读者间更好的并发，因为可以更好的在同一个节点处理锁请求。我们用一个例子来说明这个设计的潜在好处。
Figure 1. 多核多芯片的NUMA例子。包括了2个芯片，每个芯片包括4个核。每个芯片是一个NUMA节点。每个核可以有多个硬件线程的上下文。每个核有它自己的L1 缓存，芯片中的所有核共享一个L2缓存。线程间的通讯通过本地缓存（L1和L2）远比通过远程缓存要快。因为后者需要通过互联通道交换一致性消息。在图片中，线程 r1..r6是想要获得读写锁的读锁，线程w1..w6是要获取写锁。
图二 图一的可能执行次序
图一描述了一个NUMA系统中有6个线程想要对锁L加读锁，6个线程想要对锁L加写锁。我们假设有所保护的临界区都访问相同的数据。 图二展示了使用不同的读写锁，可能的读者和写者临界区执行次序。图二(a)是一种可能的临界区执行次序，有初级的读写锁（没有聚集读者或者写者在一个节点上）来决定。这个调度次序显示这种锁没有提供读者间的高并发，因为它使用了更多的时间执行玩所有临界区域。它造成了很多读者的阻塞，高比例的在读者和写者之间切换降低了读者间的并发性 。图二（b)的调度策略使得读者间的并发性更高。通过聚合读请求，调度了一组读者同时执行临界区。然而在两个不同节点里的写者交替执行，这导致了大量的一致性交互，使得写者速度变慢。方框的宽度反应了临界区的相对执行时间，更宽的方框显示了节点间通讯的开销。图二（c)通过聚合在同一个节点内的写者解决（b）的问题。结果写者w2,w3,w5和w6在执行临界区时减少了一致性失效。我们会在第四节看到这个会极大的提升我们所的效率。
3.读写锁算法
我们的读写锁基于现有的群组所。我们的每一个读写锁实例包括一个用来同步读者的互斥锁，我们通过群组所来解决读者间的冲突。写者为了互斥访问必须先获取这把群组所。在执行临界区前，拥有群组所的写者通过保证没有并发的读者在执行或者即将执行临界区来保证没有读写冲突。我们读写锁的读者使用分布式读者指示器。读者为了获取读写锁，必须修改读者指示器。读者指示器是一个分布式的计数器，每个NUMA节点一个计数器。每一个读者加锁时对本节点的计数器加一，释放锁是减一。最关键的是写者只更新集中锁，同时检查读者指示器而不会更新它。
本节我们描述了用群组所来实现读者间的互斥，然后描述了三种读写锁算法，各自实现了三种优先策略（中性，读优先，写优先）中的一种。3.2到3.4简要描述了这三个算法。然后我们发现可以使用我们的读写锁中的互斥锁和读者指示器来替换他们的实现。最后我们描述了我们读写锁中实现的可伸缩性的读者指示器。
3.1 写者群组所
群组所是一项把NUMA无关的互斥锁改变成NUMA相关的互斥锁的技术。它使用了互斥锁实现的两个关键属性，（1）队列检测，锁的拥有者可以知道是否有线程正在请求锁；（2）线程无关，锁可以有一个线程来获取但是由另外一个线程来释放。
群组所是层次结构的，最上层有一把锁，第二层有多把锁，没把锁对应一个节点。最上层的锁是线程无关的，第二层的锁需要有队列检测功能。当一个线程拥有最上层的锁时才能认为它拥有群组所。
为了获得群组所，线程必须先获取它所在节点的锁然。在执行完临界区之后，群组所的拥有者需要用本节点锁的队列检测属性来检测是否有其它线程请求锁，如果本节点有后续请求这，就把这本节点的锁交给它。随着本节点锁的转交，顶层锁的拥有者也换成了这个后继线程。如果锁的拥有者没有发现有其它线程请求锁，那么它就自己释放锁。顶层锁的线程无关属性在这里就发挥作用了，锁的拥有者可以从一个线程换成其它所在节点的其它线程，知道被其它某个线程释放。为了避免饥饿和保证长期的公平性，群组所的实现中设定了一个最大锁交换次数（在我们的实现中，我们把这个数字设定为64）。我们的算法有意严格执行短期的 FIFO/FCFS的公平性用来提高总吞吐量。特别的，我们利用不公正性（允许获取锁的次序和申请锁的次序不一样）来达到减少锁迁移次数和提高竞争线程的吞吐率。谨慎合理的使用非公平性可以减少一致性交互，提高缓存命中率。
群组所的主要目的是减少节点间的一致性交互和一致性失效，这可以提高本节点cache的命中率。我们假设同一把锁下的临界区会引用相似的东西，请求锁L很好的预示着有L保护的临界区将会访问刚刚有另外一个锁L保护的临界区访问的数据。锁的所有权转移之后，将要被改写的数据更有可能出现在本地缓存当中，并且已经处于修改状态，因为它可能被之前的线程修改了。因此这个临界区的执行会比前面一个线程在另外一个节点中快。群组所减少了锁的元数据和有锁保护的数据在不同节点间迁移的次数。如果在另外的节点中缓存行处于修改状态，那么现在他在本地缓存中一定是非法或者不存在的。这个缓存航需要从另外节点中同步过来，并且把状态修改为共享。类似的，如果将要被改写的缓存行在本地缓存中不是修改状态，所有其他节点上的拷贝都会变成非法，如果缓存行不是共享状态，内容必须同步到写者的缓存中。读者间的共享是唯一不需要一致性通信的方式。我们比较少关心经典的NUMA问题，比如线程要访问的内存是否在线程旁边，更关心缓存中是否有共享数据以及它的状态。群组所尽量满足远程缓存数据以可以减少写非法和一致性失效，但不能解决远程的容量，冲突和缓存为命中。
在我们的读写锁使用中，我们开发新的群组所，经典的ticket锁用来做NUMA节点的锁，分区的ticket锁用来做顶层锁 。我们称它为C-PTL-TKT(Partitioned-Ticket-Ticket 群组所的简称）。我们公开了一个新的接口（isLocked)，读者通过这个接口来判断是否写锁已经被申请。这个函数是通过比较分区ticket锁中的请求和授权的序号来实现的。我们推荐在我们的读写锁中使用C-PTL-TKT，它可以节省节点管理的开销但仍然提供本地自旋。顶层和节点锁都是FIFO的，尽管C-PTL-TKT并不需要FIFO。
3.2 中性锁
图三 中性锁(C-RW-NP)。上半部分有读者回字形，下半部分有写者执行。 伪代码简要的展示了锁的获取，临界区的执行和锁的释放。在获取锁的阶段，读者和写者获取群组所，而读者还需要设置读者指示器，设置读者指示器是原子操作。
我们把中性锁简称为C-RW-NP(Cohort, Read-Write, Neutral-Preference)，保证了读者写者之间的公平性。这里的公平性是指读者对于写者，或者写者对于读者没有任何优先，都是平等的。因此所有读写线程都从集中的群组所通过，这种方式在以前就在用了。图三的伪代码简要描述了C-RW-NP锁。每个线程必须先获取群组所。读者使用群组所来获得者是读者指示器的权限（具体实现在3.6节），然后释放群组所并执行临界区域。读者在释放群组所后再执行临界区可以使读者之间的并发性更大。写者在获取群组所之后，必须确保没有读者。这个通过在读者指示器上自旋（行9-10）来等待所有读者离开临界区。这个算法非常的清楚简单，并且保证是中性的，因为读者和写者都需要获取群组所。然而，要求读者获取群组所降低了C-RW-NP锁的伸缩性，同时也增加了读者获取锁的延迟。C-RW-NP锁保留一部分缓存局部性，包括访问锁的元数据和临界区访问，因为所有操作都要通群组所。
我们注意到C-RW-NP锁并不保证FIFO，获取锁的次序有群组所的策略锁决定。
3.3 读者优先锁
图四 读者优先锁
从上面可以看到，C-RW-NP有一个很大的缺陷，因为他需要读者获取群组所。对读者来说请求群组所需要额外的开销，即使群组所是非竞争的。对集中锁的竞争会产生额外的一致性交互，从而对节点间互联通道的竞争，虽然通过群组所的方式可以一定程度上减少节点间一致性交互。然而在临界区访问路径上需要串行访问群组所还是会成为伸缩性的瓶颈 。算法通过群组所把读者和写者请求通过群组所来控制在很大程度上限制了读者之间的并发性。最坏的情况下，甚至会没有读并发的存在 ，读者和写者交替执行。我们的读优先锁(C-RW-RP)解决了这两个问题。
直观上来说把读者请求锁集中起来可以最大化读者之间的并发性，以此可以带来更好的伸缩性。但这需要读者优先于正在等待锁的写者。Courtois et al早期对读写锁的研究已经对此有所研究，后来者的工作一直在公平性和伸缩性之间进行平衡和选择。我们的C-RW-RP算法也继承了这种平衡。
图四的伪代码描述了C-RW-RP锁的实现。读者和写者之间的互动方式让人人回想起经典的Dekker锁，这种锁每个线程都需要让别的线程知道，然后在检查其它线程的状态。为了检测和解决冲突，读者必须对写者可见，写者必须对读者和写者同时可见。C-RW-RP的读者无须获取群组所，相反他们直接设置锁的读者指示器（行4）。然而每一个读者只有在没有写者的情况下才能往前执行。然后读者可执行他们的临界区，并通设置读者指示器释放锁。
写者首先获取CohortLock（行12），然后确认现在没有并发的处于“活跃”的读者。如果有并发的读者（读者指示器会显示），写者释放CohortLock（行13-14）并等待所有的读者完成（行15）。注意如果写者仅仅等待读者完成，但读者却源源不断的到达，那么写者就有饿死的风险了。为避免饿死，我们引入了一个读者栅栏（RBarrier），写者可以使用它暂时阻塞新的读者获取C-RW-RP锁。行（17-20）显示了写者使用栅栏（行23结束栅栏），行2-3显示了栅栏阻塞了新的读者。读者栅栏用一个集中的计数器来实现。写者会先等待事先确定的一个时间（行17），然后就不会在等待了。写者的等待时间比较长，所以栅栏不会经常被使用，而且我们也不希望栅栏成为竞争的瓶颈。在我们的实验中写者的等待时间是1000循环等待。这个等待时间是可以调优的。在写者使用栅栏后，所有的读者会慢慢的执行完，当所有读者执行完后，写者就会执行它的临界区，最后通过释放CohortLock来释放写权限。
尽管上面的算法很简单，但它有一个很大的性能问题，因为读者和写者之间的竞争交互和CohortLock的策略。考虑这种执行逻辑，有N个写者 W1，W2, W3…, Wn等待在群组所上。W1是锁的拥有者，但他还没有到大行13。这意味着在第五行的isLocked 函数返回true，阻塞了所有的读者。那个时候更多的读者到达了，自动增加了读者指示器，然后自旋等待isLocked函数返回false。下一步，W1执行 行13，发现有并发读者，在行14释放了群组所。同时，W1把锁交给了W2，W2又把锁交给了W3，如此往复。在这个过程中，群组所一直处于加锁状态，尽管锁的拥有者一直在变，对所有调用isLocked函数的读者来说，返回值一直是true。群组所拥有者在读者间循环改变，减少了不必要的一致性交互，也减少了读者的等待时间。在我们的实验中我们观察到这种在读者和写者间不必要的交互极大的降低了效率。而且循环还避免了加在写者上的次序问题。
为了避免这个问题，我们为C-RW-RP增加了一个新的WActive变量，来反映群组所的逻辑状态。我们修改了读者和写者间冲突检测逻辑，把图四 行5改成当WACtive true时自旋。同时，写者的代码（行11至行21）改成如下代码
写者获取群组所然后进入循环。循环一开始就等待读者指示器指示此时没有等待或者活跃的读者，如果长时间等待后也可以设置RBarrier。读者指示器指示没有活跃读者时，代码会把WActive设置成true，然后验证没有活跃或者等待的读者。如果情况是这样的，就结束循环，写者去执行自己的写临界区。如果读者指示器指示有读者，那么写者吧WActive设置成false，又从循环最开始执行，等待读者执行完毕。写者在等待读者执行完毕时，仍旧持有锁，这个可以避免在写者间交换锁带来的性能损失。写者执行完临界区之后，把WActive设置成false并释放群组所。读者只能在一个很小的时间窗口下才能阻塞写者，这个时间窗口就是写者在检测到有等待的读者时重置WActive那个时间点。我们把它称为C-RW-RP-opt。注意WActive只在群组所的保护下才能修改，当群组所被加锁时WActive为tru，否则为false。没有类似写优先 “opt”，因为读者可以快速解除他们的加读锁的意愿，让写者优先。
3.4 写优先锁
传统观点认为读优先策略的表现会比写优先和中性策略要好。因为应用程序开发人员选了读写锁而不是互斥锁，我们可以期待工作负载中读是占大部分的。直觉告诉我们把读者聚集起来可以获得更好的读者间并发性，以此获取更好吞吐率。尽管我们相信直觉，读写锁大多数情况下是加读锁较多，但我们也认为写优先策略间接也得获得相同的结果——把读者聚集起来。这是因为写优先策略会让很多读者等待，当所有读者完成临界区后大量读者可以并发同时执行。更进一步，我们也观察到读者优先策略会导致效率下降，在4.3节有描述，极大的降低了锁的潜在可伸缩性。
图五显示了写优先锁的伪代码，我们称它为 C-RW-WP。我们的C-RW-WP算法跟我们的C-RW-RP算法完全对称，唯一的区别写者代码变成了读者代码 ，读者的代码变成了写者代码 。读者设置读者指示器（行4），检查写者（行5），如果有写者，读者重置读者指示器并且等待写者执行结束。如果读者等待时间过长了（在我们的实验中是1000次循环），可以设置写者栅栏（行10）来阻塞新的写者获取群组所（行18-19）。写者首先确认写栅栏没有被设置（行18-19），然后获取群组所（行20），并且在执行临界区钱保证没有并发的读者（行21-22）。
3.5读写锁概述
我们可以观察到我们的读写锁不需要知道读者指示器和互斥锁的实现。我们的读写需要读者指示器提供到达，离开和isEmpty操作，互斥锁需要提供获取，释放和isLocked操作。任何支持这些操作的读者指示器和互斥锁都可以在我们的算法中使用。我们希望只要经过一点小的修改，支持这几种操作的读者指示器和互斥锁就可以使用。
我们的读写锁设计灵活，可以极大的方便程序员创建一个适合他们应用程序的读写锁。例如，本论文提出了一种NUMA的读写锁就是利用了NUMA的互斥锁和可伸缩性的读者指示器。在我们的实验中（第四节），我们也展示了读写锁的性能，这个读写锁使用了分布式的计数器作为读者指示器，MSC锁作为读者建的互斥锁。这种锁适合那些写比较少的应用程序。
3.6 追踪读者
Lev et al.发现读写锁的读者可以用读者指示器来追踪。写者检查是否有读者时不需要读者的个数，仅仅需要知道是否读者。
这个读者指示器可以用一个自动更新的计数器来实现，记录正在执行或者想要执行临界区的读者个数。然后，一个简单的计数器无法再NUMA系统上做到可伸缩。观察到这个现象后， Lev et al. 提议了一个基于SNZI的读写锁。基于SNZI的方案让读者指示器有了极大的可伸缩性，尽管算法复杂和读者在中低等的竞争中引入了开销（第四节有介绍）。结果，我们采用了一个简单的策略，我们把一个“逻辑”计数器分成了多个物理计数器，每个NUMA节点一个计数器。我们方法的主要目的是在读者比例不是很高时有比较少的而延迟，当有很多读者是，又有好的伸缩性。
一个读线程总是操作它所在节点的读者指示器。这保证了计数器的修改不会产生节点间的一致性交互。然而，当获取群组所后，写者必须检查所有读写锁的读者指示器以保证可以安全的执行临界区。这个增加了读者的开销。这里有一个非常清楚的权衡，假设读写锁大部分是加读锁的，我们通过让写者的执行路劲变长从而简化了读者的执行路径（仅仅是对本节点读者计数器做自增）。目前大多数的多核和多芯片系统只有很少几个NUMA节点（我们实验中用到的是4个），所以我们相信读者增加的开销不会成为主要的性能问题。将来NUMA系统的节点数变多，这个就有可能成为问题了，但是我们把这个解决方案留到以后解决。
分散的计数器有几种不同的实现方式。我们这里讨论两种方法。第一，每个节点一个整型计数器。每一读者在获取锁时原子的增加本节点的计数器，在释放锁时减少本节点计数器。使用对齐和填充，每一个节点的计数器被放在各自的缓存行中来避免伪共享。当写者获取锁时，要确认每一个节点的读者计数器为0，如果非0，写者通过自旋等待。
简单的分布式计数器的方法减少了节点间的一致性交互，但是还是有节点内的竞争。我们的第二个方法就是减少这个节点内的竞争，该方法为每一个节点引入了一对 进和出的计数器。读者在获取锁时增加ingress计数器，释放锁时增加egress计数器。通过把本节点计数器分为两个变量，我们把读者到达和离开的竞争分成了两个部分。在一个节点上，到达的线程可以独立的更新ingress变量，而同时离开的线程可以更新egress变量。Ingress和egress变量可能在同一个缓存行中。当ingress和egress相等时，逻辑上可认为读者计数器为0。有趣的是使用单一计数器或者使用 ingress-egress 计数器，性能上都要比SNZI的读者其实好，至少在我们的测试平台是这样的。我们相信这个好性能是平台相关的。如果有一个很多节点的系统，那么写者扫描这些节点需要大量的工作，用这种方式来解决读者和写者间的冲突就不可能了。但目前的平台上，ingress-egress计数器是我们推荐的实现。
当获取锁时，写者检查每一个节点的上的 ingress和egress的值是相当等。这无法自动完成，需要非常小心的去避免和正在修改技术的读者出现竞争。具体的说，在我们的C-RW-WP算法中，写者必须先读取egress变量，然后是ingress变量来爬段是否相等。注意这两个计数器都是单调递增的，必须永远保证egress小于等于ingress。
4.实验评估
我们展示了我们的NUMA读写锁的评估结果，以及和其它有名的读写锁的比较。通过特意编写的微小基准程序演示了这些所的伸缩性结果。我们的结果覆盖了非常广泛的配置，不同临界区和非临界区的长度，只读和读写的临界区等。我们的报告也揭示了读优先具有好的性能。所以我们展示了读指示器的实现是如何影响我们读写锁的伸缩性的。最后我们展示了kyoto-cabinet开源数据库包中的 kccahe-test基准程序的测试结果。我们实验的结果表明我们的NUMA锁的性能要远好于其它读写锁。
我们展示了我们所有锁算法的测试结果：C-RW-NP, C-RW-NP和C-RW-NP-opt, 以及C-RW-WP。除非特别说明，我们用 ingress-egress计数器作为我们读者指示器的实现。我们比较了基于SNZI的ROLL锁，分布式读写锁（DV），以及最近有 Shirako et al发布的NUMA无关的读写锁。因为我们的锁是基于群组所的，我们增加了一个简单的互斥锁以便理解我们读写锁的优点。最后，为了量化在我们的读写锁中使用群组所的好处，我们在C-RW-WP中使用MSC锁来比较他们的性能差异。我们把这个教唆 DR-MSC锁。
我们用C实现了所有以上算法，用GCC4.4.1 选项O3 在上32位机上编译。测试在Oracle T5440系列的系统上进行，他有4个Niagara T2+ Sparc的芯片，每个芯片包括8个核，每个核有2个流水线，每个流水线有4个线程上下文，总共有256线程上下文，处理器频率为1.4GHZ。每个芯片都有自己本节点的内存，4MB的L2缓存，每个核有8KB的L1数据缓存。每一个T2+芯片都是一个NUMA节点，这些节点有一个中心一致性hub连接。Solaris 10的调度器是会保存工作和维护缓存的，尽量避免线程迁移。在我们的测试中，线程迁移很少发生。显示的加入内存栅栏是非常有必要的，这在我们的伪代码里没有看到。
我们用LD_PRELOAD 库来实现以上的锁算法，这个库暴露了标准的POSIX pthread_rwlock_t变成接口。这允许我们通过改变LD_PRELOAD的实现来改变锁的实现方式而不用修改应用程序代码。
我们试用Solaris的 schedctl接口去查询线程运行在哪个CPU上，在SPARC和X86只需两个指令。然后把CPU的数量转换成NUMA的节点数量。在我们的实现中，线程在获取锁时都会去查询一下NUMA节点的数量。我们记录那个数字，并保证读者从同一个节点离开。在x86平台上，RDTSCP指令可以替代schedctl用来返回CPUID。
4.1 RWbench
为了了解我们锁的性能特性和与其他锁比较，我们实现了一个多线程的基准程序，这基准程序重复不断的执行临界区。这个基准程序叫RWbench，这个一个灵活的框架，可以让我们测试各种任务，临界区和非临界区的长度，不同分布的读写操作，不同的缓存访问等。所有这些可以通过配置变量来做到。它使用pthreads库的读写锁接口去获取和释放所，我们使用LD_PRELOAD库来选择锁的实现。
RWBench可以根据配置创建并发线程，每个线程循环执行10秒。在最外城的循环开始出，使用伯努利随机数来决定这个循环是读临界区还是读写临界区。选择的读写临界区的概率可以用变量来配置。临界区修改一个共享的64个整数的数组，有一个全局的读写锁来保护。只读操作会循环RCSLen次（可配置），每个循环会从共享数组中取出两个整数。读写操作循环WCSLen次（可配置），每个循环去除两个整数，对一个整数做加法，对另外一个整数做减法。主循环中的非临界区更新线程私有的64个整数 NCSLen次。基准程序结束后，确认整个数组的和是0。
基准程序在10秒后给出了吞吐率，以工作线程执行的最上层循环次数来表示。我们为每个配置运行呢3次，去平均值。观察的变化非常小。为了更贴近真实世界的执行环节，我们没有特意把线程跟硬件上下文绑定，而是依赖于Soloaris内核的调度器。不像其它NUMA锁，我们的锁无需绑定。
4.2 RWBench 可伸缩性测试
图六 RWBench的可伸缩性测试，读写分布为：2%，5%，10%和20%的写请求。所有的图是对数坐标。RCSLen=4, WCSLen=4，NCSLen=32。X轴为为线程数量，从1到255。Y轴是吞吐率，以每秒百万次循环来表示。
图六是RWBench的测试结果，包括不同的锁，不同的读写比列分布。我们认为测试中的读写分布已经覆盖了现实中很多应用程序的情况。我们也收集了写占50%时的数据，测试结果跟图六（d）相似。在这些实验中，我们有意使用小的临界区和非临界区，这样可以使我们更好的了解在高频率加锁的情况下的读写的行为。
首先，C-RW-WP是所有的锁中性能最好的。有趣的是DR-MCS在2%写的情况下性能第二，但随着写负载的增加性能急剧下降。这是因为写在性能中所占比列越来越高，DR-MCS存在过度的一致性交互，因为MCS锁不关心NUMA架构。DV在线程少的时候比较有竞争力，但是在竞争多时性能下降很快，大概是因为写者需要获取所有NUMA节点的读写锁，这会导致大量的一致性交互和读写时获取锁的延迟。
ROLL锁随着线程数量的增加有一定的伸缩性。这是因为在我们测试中的线程被Solaris的调度器分散在整个系统中 ，结果只有很少的线程被固定在SNZI树的叶节点上。最终测试结果是很多线程很容易“爬”上SNZI树，在根节点上竞争，这个根节点是全局共享的会郑家一致性交互。ROLL在很多线程的情况下可升缩性更好些，大概是因为SNZI数的叶节点上的负载足够减少访问根节点的线程数量，因为减少了整个系统的一致性交互。然后在20%写负载的情况下伸缩性就收到了限制，写者的NUMA无关性开始扮演可伸缩性的重要角色。另外一个NUMA无关的Shirako锁，在我们NUMA系统上没有什么伸缩性。
群组展示了又去的性能特点。因为他不提供任何读者间的并发性，群组的可伸缩性还不如最好的读写锁。然后锁着写者的增多，群组的性能开始和和我们其他的读写锁接近了，除了C-RW-WP在20%写的情况下，它跟其它锁相比也是有竞争力的。这说明了甚至在写较多的情况下，写者间的互斥部分会成为影响可伸缩性的重要因子，因此群组在NUMA系统上非常高效和伸缩性。这个跟其它锁比较来也是有竞争力的。
相对于简单的互斥锁，读写锁通常有更长的执行路径（延迟）和访问更多的共享元数据。后者可以降低伸缩性。把群组和真正的读写锁比较非常有趣，因为潜在的读者间的并发性无法弥补额外的来自读写锁的开销，特别当临界区非常小或者线程数量很少时。C-RW-NP只有在写负载为2%时，才可以是读者间的并发性很高。在所有其它情况下，它和群组类似，因为读者为了设置读者指示器也需要获取群组锁。
最后，C-RW-RP和C-RW-RP-opt之间的性能区别也清楚的展示了C-RW-RP写权限循环转移的缺陷。然后C-RW-RP-opt的可伸缩还不如C-RW-RP，因为它的读优先性能有问题，这会在下面描述。
4.3 读优先性能分析
从图六可以清楚的看到，我们的读者优先锁的性能远比写优先锁差。众所周知严格的读优先策略有可能让写者饿死。然而，我们观察到读优先引起的第二个现象——读者无法充分的并发执行。
我们有固定数量的线程，随机决定对读写锁是加读锁还是写锁。 我们假设读会比写多，访问读写锁中是读占主导地位。我们假设大多数线程是读的。过一段时间这些读线程会完成他们的操作，有一部分会变成写线程，但大多数仍然是读线程。这些写者会阻塞在栅栏上，让读线程优先。最后当没有活跃的读者时，写者才允许执行。但当写者完成他的操作，很快读者就会再次执行，因此阻塞了大量的写者。这个不受欢迎的模式可以一直持续。在任何时候，只要有一个写线程或者几个活跃状态的读线程，都会使获取写权限的线程阻塞。这个导致为充分利用读者间的并发性，致使系统未充分利用。尽管我们的负载是以读为主，我们有足够多线程和读优先的锁策略，我们的读者吞吐率还是很低减少了读者的并发性。由于读优先引起写饥饿导致写者无法变成读者，也限制了读者建的并发性。在RWBench中我们也观察到这个现象，我们观察到服务器线程查询和更新有读写锁保护的数据结构 。
有人可能会怀疑写优先策略是否也有类似的问题。尽管写者会阻塞读者，我们不认为写优先策略的问题同样严重。我们假设读写锁绝大部分时间处于读模式中。因此，即使一批写者阻塞了并发的读者，这些线程最终会请求读锁。结果读者只是停顿了一小会儿。一旦写者执行完毕，一组等待的读者可以并发执行了。
严格的 读/写优先策略会导致请求不是优先锁的线程阻塞。因此，为了避免这种情况，我们认为一个通用的读写锁算法需要检测有优先策略导致的饥饿，并且从饥饿中恢复过来。如果是写优先策略，如果读者等待时间太长了，可以用锁阻塞即将到来的写者，让等待中的读者先执行。事实上这种机制可以把读者聚集起来执行，产生更大的读者并发。更有效的是锁可以无缝的从写优先转换成中性的或者读优先。同样的，如果是读优先，写者阻塞很长时间后，写者把锁转换成中性的或者写优先的。这个机制在图五反饥饿中有阐述。我们用栅栏来阻塞写者，在图三中中性策略的“没耐心”的读者请求群组锁。读者首先使用最快的执行路径，但是如果他们无法继续向前执行了，他们就使用差一点的执行路径去获取群组锁。这个方法的效率也还可以。
4.4 读者指示器实现
就如第3.6节描述的，有很多种方式可以实现读者指示器。我们来比较一下我们所讨论过的三种实现方式的性能，整型计数器，一个节点一个整型计数器，每个NUMA节点一个 ingress-egress变量对。图七显示了用这些计数器的C-RW-WP的性能，其中读者占98%写者占2%。C-RW-WP-1RC代表了C-RW-WP用一个计数器实现。这个计数器明显是一个伸缩性的瓶颈，当线程数增加时会导致了极大的性能损失。C-RW-WP-4RC是C-RW-WP用了4个计数器，每个节点一个计数器。改进版的分布式计数器极大的提升了C-RW-WP的效率（用了4对ingress-egress变量对，一个节点一对）直至有96个线程，之后由于单个节点上竞争，性能开始下降。Ingress-egress降低了一半的竞争，伸缩性好于多个计数器的实现。
C-RW-WP的可伸缩性性能还能提高一点，通过基于节点的计数器和读者指示器来提高NUMA节点的局部性。C-RW-WP-Shuffle 是C-RW-WP的变种，它随机派发读者指示器给相应的线程。访问计数器的线程个数保持相等，但是有些线程可以在不同节点执行。我们从图中可以看到C-RW-WP中很大一部分性能改善来自NUMA的局部性。
4.5 kccachetest性能
Kccachetest由kyoto-cabinet发布包提供，是一个流行的开源数据库包。它是一个测试内存数据库的基准程序。CacheDB 大量使用了标准的pthread_rwlock_t操作，基准程序的性能对于锁的实现非常敏感。我们用刻薄的参数来运行程序，创建了一个没有持久化的内存数据库，然后随机选择了一些事务运行在那个数据库上。基准程序和数据库处于同一个进程中，通过调用和共享内存来通讯。基准程序被限制成最多具有64个线程。线程数据可以在命令行说说明，每一个工作线程循环选择一个操作运行在数据库上。有些情况下，仅仅是一些查找，删除操作，另外一些则是复杂的事务。每一个线程完成相同数量的操作，程序会显示出第一个线程开始运行到最后一个线程结束的时间间隔。不幸的是关键字范围的大小和内存数据库的数据是一个线程的函数。所以我们增加线程数量时会同时增加关键字范围和数据，这意味着不同线程数的结果很难互相比较。因此我们没有对kccachetest的结果画图，只做了一张表格。
图八显示了用不同的读写锁时kccachetest的效率。当线程少时，所有的锁都有竞争力，当线程数量增加时，他们的效率变化就大不一样了。Kccachetest有一系列的临界区组成，包括短的只读和读写临界区，长的复杂的读写临界区。总的来说，负载中读写临界区占大部分，会请求写锁。结果，群组所的性能和我们的NUMA读写锁差不多，比其他NUMA无关的锁要好很多，DR-MCS,DV,ROLL以及Shirako。DR-MCS伸缩性很差，因为写者请求MCS锁时会强制锁和数据的缓存行在节点间同步的次数比其它锁多。因为群组锁减少了锁的迁移，所以它的性能好点。我们的NUMA读写锁，除了C-RW-RP之外，进一步扩展了群组的优点。C-RW-RP的性能优于拥有者的转移而性能不好，结果就是可伸缩性不如其它锁。然而她确实比其他先前的锁都要好。总的来说，C-RW-WP和C-RW-NP的性能最好，比最好的读写锁（DV和Shirako）要好40%。
5. 结论
多核和多芯片系统的快速发展使NUMA架构变得普遍，基础的数据结构和同步愿意必须重新设计才能适应这些新环境。我们介绍了一些列惊人的简单NUMA读写锁，我们的锁比先前的锁性能要提高很多。写者使用中央锁元数据，读者使用分散的元数据。基准程序表明我们表现最好的锁比之前最好的锁要快10倍以上。在真实应用程序（kyoto cabinet数据库）用了我们的锁之后，效率提升了40%。
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/140714.html