《Disruptor一种高性能的、在并发线程间数据交换领域用于替换有界限队列的方案》由会员分享，可在线阅读，更多相关《Disruptor一种高性能的、在并发线程间数据交换领域用于替换有界限队列的方案（11页珍藏版）》请在金锄头文库上搜索。
1、Disruptor：一种高性能的、在并发线程间数据交换领域用于替换有界限队列的方案作者： Martin ThompsonDave FarleyMicheal BarkerPatricia GeeAndrew Stewart1 摘要LMAX 公司被创建去构建一种高性能的金融交易平台。作为我们为达到这样的目标所做的工作的一部分，我们论证了一些设计这个系统的方案。但是随着我们的测试，我们发现传统方案的一些根本的局限性。许多应用使用队列来实现在其线程间的数据交互。通过测试我们发现，非常戏剧性的使用队列造成的延迟与磁盘 IO 操作（RAID、SSD 磁盘）造成的延迟同样的多！如果在一个端对端操作中使用多
2、个队列，这将会增加数百毫秒的总延迟。显然，这是一个需要优化的领域。进一步的研究和专注于计算机科学的学习使我们认识到，传统方案固有的合并特点导致了在多线程实现中出现了争用现象，这意味着或许应该有更好的解决办法。考虑下现代 CPU 的工作原理，有一种我们称之为“硬件机制共鸣” 的编程优化方法，使用优化设计方案、专注于分离问题我们最后创建了一套数据结构和对应的设计模式，我们称之为 Disruptor。测试表明，使用 Disruptor 的三个线程管道的平均延迟要比相当的使用队列的方案低得多，而且在同样的配置下，Disruptor 的吞吐量大约为队列的 8 倍。这些性能上的提高，使我们开始重新思考并发
3、编程的方式。Disruptor ，这个全新的模式对于任何需要高吞吐低延迟特性的异步事件驱动架构来说都是一个理想的借鉴基础。在 LMAX 公司，我们在 Disruptor 模式基础上构建了次序匹配引擎、实时风险管理系统、高可用性内存事务处理系统，这些项目都获得了巨大的成功。这些系统的性能都为业界设置了新的标杆 在我们看来、在目前一段可以预期的时间内不会被超越！（译者注：好狂妄的老外）Disruptor 并不是只能应用于金融业的解决方案，它是一种通用的机制，以简单的实现来最大程度的提高性能，用来解决并发编程中的复杂问题。尽管 Disruptor 中的一些概念似乎不大主流，但是以我们的成功经验证明，
4、使用这种模式构建系统要比使用同类机制实现起来简单得多。Disruptor 框架显著的减少了写的争用、具有更低的系统开销和比之同类其他机制更好的缓存（译者注：这里指 CPU 的缓存）友好特性，所有这些优点使 Disruptor 具有更加强大的吞吐性能和平稳的低延迟处理能力。使用中等的时钟频率的处理器，我们测试得到了每秒 2500 万消息发送，上述延迟低于 50 纳秒（译者注：1 纳秒=一秒的 10 亿分之一，神乎其技啊！）。这样的性能相对于我们见过的任何其他的实现方案来说都是显著的提高。这已经非常接近现代 CPU 处理器在核心之间交换数据的理论极限了。（译者注：再次惊叹，神乎其技啊！）2 概述D
5、isruptor 是我们在 LMAX 公司构建世界上最快的高性能金融交易平台过程中的研究成果。早期，我们的设计是基于 SEDA 派生和 Actors 模式的，使用管道来提供吞吐量。在评测了各种不同的实现之后，事实证明在各个管道的事件排队是主要的系统消耗来源。我们也发现队列产生相当的延迟和较高的时间偏差。我们花费了大量的精力去实现更高性能的队列，但是，事实证明队列作为一种基础的数据结构带有它的局限性 在生产者、消费者、以及它们的数据存储之间的合并设计问题。Disruptor 就是我们在构建这样一种能够清晰地分割这些关注问题的数据结构过程中所诞生的成果。3 并发的复杂性在我们这一段里我们来讨论并发
6、。在计算机科学中，并发的意思是两个或两个以上的任务同时并行的执行，但是也要通过争抢来接入资源。争抢的资源可能是数据库、文件系统、套接字、甚至或者说内存中的一块区域。并发的执行代码包括两个方面：互斥性和改变的可见性。互斥性是指线程对资源进行争用状态的改变的管理（译者注：从后面看出，这里的争用状态主要是指写的操作要保持互斥性），而改变可见性是指控制何时这种改变对其他线程可见。很明显，如果能消除争用就能够避免互斥性管理 如果有某种算法，能够确保任何给定的资源同一时刻只被一个线程修改，那么互斥性就不是必要的了。读和写操作需要所有改变对其他线程都是可见的，但是只有争用写操作需要保持互斥性。在任何并发的环
7、境中，争用写操作是花费最大代价的。为了支持多个并发的线程对同一块资源进行写操作是需要花费复杂而昂贵的代价来进行协调的。最典型的解决这种协调的方法是引入某种锁的策略。3.1 锁的代价锁提供了互斥性并且确保改变对其他线程的可见性以一种命令式的方式发生。锁的代价消耗是难以置信的大 因为它们当遇到争用时需要进行仲裁。这种仲裁是通过一种上下文切换到操作系统的内核，挂起线程等待锁的释放。在这样的上下文切换过程中，也会交还控制权给操作系统 操作系统此时可能同时决定去做其他一些请理性的工作，这样正在执行中的上下文对象将会丢失之前预读的缓存中的数据和指令（译者注：这里的缓存指的是 CPU 缓存）。对现代 CPU
8、 而言，这将会造成一系列的性能上的坏的影响。可以使用快速的用户模式的锁，但是这也仅当没有争用的时候能够带来真正的益处。我们将会举一个简单的演示例子说明锁的代价。这个实验的主要内容是调用一个函数，执行一个循环 5 亿次的增量为 64bit 的计数循环。我们用 Java 编写这个程序后在 2,4Ghz的 Intel Westmere EP 处理器（译者注：一款 6 核企业级应用 CPU）上单线程执行，仅仅花费大约 300 毫秒的时间。其实用什么语言对这个实验来说并不重要，使用相同基本底层原语的语言编写的程序执行时间都差不多。但是，一旦使用了锁来提供互斥性，那么即使当锁还未被争抢的时候，资源的消耗（
9、译者注：这里主要指时间上的损耗）仍会显著的提高。而当多个线程开始发生争用现象时，花费在巨大的排队操作上的工作将会使程序对资源的消耗继续增加。这个小实验的结果如下面的表格所示：3.2 CAS在需要修改的内存数据仅为一个字长时，有些更有效的方案可以用来替代锁来进行内存修改。这些替代方案是基于原子性、互锁性的现代 CPU 实现的指令的。这些指令通常被称为“CAS”(Compare And Swap)操作，例如 x86 处理器上的lock cmpxchg。CAS 操作是一种特殊的机器码指令，它在一定条件下可以允许对内存中一个字长的操作成为原子操作。在上一小节的计数器小实验中，每个线程轮流在一个循环中读
10、取计算器并尝试在同一个原子指令中将计算器累加为新的值。累加后的新值和累加前的旧值一起作为该指令的参数，如果指令执行后计数器的值与指令的新值参数相同，则指令执行成功，将计数器的值置为新值；否则，如果计数器此时与指令的新值参数不同，则该 CAS 操作失败，此时回到线程重新读取计数器增量加到原来的新值参数上作为新的新值参数（译者注：即设指令为 f，新值参数为 B，旧值参数为 A，计数增量为 k：由 f(A,B)改为 f(B,B+k)重新执行指令），重复上述过程，直到指令执行成功。CAS 方法比锁要有效得多，因为它不需要切换上下文到操作系统内核去仲裁。但是，CAS 操作也并不是没有资源消耗的，处理器必
11、须锁定它的指令通道去确保原子性，并且要创建一个内存栅栏（memory barrier）来使得状态的变化对其他线程可见。具体到实际的编程实现上，CAS 操作在 Java 开发中，可以使用java.util.concurrent.Atomic.* 包中的类来实现。如果程序的关键部分要比我们上面举的计数器例子复杂，这就需要更加复杂的使用多个CAS 操作的机器指令来协调线程间的争用。用锁来编写并发程序很难；用 CAS 操作和内存栅栏开发无锁算法来编写并发程序有时候更难！而且这样的程序更加难以测试，难以确保其正确性！（译者注：好绝望啊 orz）理想的算法应该是仅仅使用一个单线程来处理所有的对一个资源的写
12、操作，而有多个线程执行读取处理结果的操作。在一个多处理器或多核处理器环境下处理对资源的读操作需要内存栅栏来确保一个线程状态改变对其他处理器上运行的线程可见。3.3 内存栅栏现代的处理器为了提高效率，采用无序的方式执行其指令、在内存和对应的执行单元间加载和存储数据。处理器仅仅需要确保程序逻辑执行出正确的结果而不去关心其执行顺序。这不是单线程程序的特性。但是当线程间彼此共享状态时为了确保数据交换的成功处理，在需要的时点，内存的改变能够按次序发生就是很重要的了。内存栅栏是处理器用来指出代码块在哪里修改内存是需要有序的进行的。它们是硬件排序和线程间保持彼此改变可见性的重要手段。编译器会在适当的位置设置
13、合适的软件栅栏来确保代码按照正确的顺序编译，处理器本身也会使用这样的软件栅栏作为硬件栅栏的一种补充。现代的处理器要比同代的内存快得多的多。为了填补这样一个速度差距的鸿沟，CPU 使用了复杂的缓存系统 非常快的通过硬件实现的无链哈希表。这些缓存系统通过消息传递协议与其他处理器 CPU 的缓存系统保持协调一致。另外作为补充，处理器的“存储缓冲”可以将写操作从上述缓冲上卸载下来，在一个写操作将要发生的时候，缓存协调协议通过这样的一个“失效队列 ”快速的通知失效消息。这些对于数据来说意味着，当某个数据值的最后一个版本刚刚被写操作执行之后，将会被存储登记给一个存储缓冲 可能是 CPU 的某一层缓存、或者
14、是一块内存区域。如果线程想要共享这一数据，那么它需要以一种有序的方式轮流对其他线程可见，这是通过处理器协调消息的协调来实现的。这些及时的协调消息的生成，是又内存栅栏来控制的。读操作内存栅栏对 CPU 的加载指令进行排序，通过失效队列来得知当前缓存的改变。这使得读操作内存栅栏对其之前的已排序的写操作有了一个持久化的视界。 写操作内存栅栏对 CPU 的存储指令进行排序，通过存储缓冲执行，因此，通过对应的CPU 缓存来刷新写输出。写操作内存栅栏提供了一个在其之前的存储操作如何发生的、有序的视界。一个完整的内存栅栏即对加载排序也对存储排序，但这只针对执行该栅栏的 CPU。一些 CPU 还有上述三种元件
15、的变体，但是介绍这三种元件已经足够来理解相关的复杂联系了。在 Java 的内存模型中，对一个 volatile 类型成员变量的域的读和写，分别实现了读内存栅栏和写内存栅栏。（译者注：对 volatile 类型的成员变量虚拟机不采用优化策略，即不在每个线程中保存其副本，每次读取和修改都将到共享的内存域中进行）这在关于Java 内存模型的一篇文章中已经有很详细的描述（http:/ Java 5 一起发布。3.4 缓存行(译者注：这里缓存行实际上是单词 cache line 的拙劣翻译-_-! 意思是 CPU 缓存与物理内存间交互时所一次发生的数据，一般为 64 个字节)现代处理器使用缓存的方式对成
16、功的高性能操作而言具有重要的意义。这种处理器架构在数据搅动和指令存储方面有极大作用，反之，如果缓存出现丢失的话将对系能造成极大的影响。我们的硬件在移动内存数据的时候不是以字节和字长为单位的，为了更加有效的工作，缓存被组织成缓存行的形式，每个缓存行为 32-256 个字节大小，一般是 64 字节。这是缓存协调协议操作的粒度层级。这意味着如果两个变量在同一个缓存行内，并且它们是被两个不同的线程写入的话，它们将会呈现出相同的写争用问题，就好像它们是一个变量一样！这就是“伪共享 ”概念。所以为了提高性能，应该确保独立的且并发的写操作、并且写操作的变量不在同一个缓存行内，可以使争用最小化。当访问内存时，一个具有预读功能的 CPU 会通过预读的方式来减少访问时花费的延迟CPU 会预读有可能下次需要访问的数据、并在后台将其提取到缓存中。这种机制仅仅在处理器侦测到某种访问
