Disruptor：一种高性能、在并发线程间数据交换领域用于替换有界限队列方案.doc

Disruptor：一种高性能的、在并发线程间数据交换领域用于替换有界限队列的方案 作者： Martin Thompson Dave Farley Micheal Barker Patricia Gee Andrew Stewart1 摘要 LMAX公司被创建去构建一种高性能的金融交易平台。作为我们为达到这样的目标所做的工作的一部分，我们论证了一些设计这个系统的方案。但是随着我们的测试，我们发现传统方案的一些根本的局限性。 许多应用使用队列来实现在其线程间的数据交互。通过测试我们发现，非常戏剧性的使用队列造成的延迟与磁盘IO操作（RAID、SSD磁盘）造成的延迟同样的多！如果在一个端对端操作中使用多个队列，这将会增加数百毫秒的总延迟。显然，这是一个需要优化的领域。 进一步的研究和专注于计算机科学的学习使我们认识到，传统方案固有的合并特点导致了在多线程实现中出现了争用现象，这意味着或许应该有更好的解决办法。 考虑下现代CPU的工作原理，有一种我们称之为“硬件机制共鸣”的编程优化方法，使用优化设计方案、专注于分离问题我们最后创建了一套数据结构和对应的设计模式，我们称之为Disruptor。 测试表明，使用Disruptor的三个线程管道的平均延迟要比相当的使用队列的方案低得多，而且在同样的配置下，Disruptor的吞吐量大约为队列的8倍。 这些性能上的提高，使我们开始重新思考并发编程的方式。Disruptor，这个全新的模式对于任何需要高吞吐低延迟特性的异步事件驱动架构来说都是一个理想的借鉴基础。 在LMAX公司，我们在Disruptor模式基础上构建了次序匹配引擎、实时风险管理系统、高可用性内存事务处理系统，这些项目都获得了巨大的成功。这些系统的性能都为业界设置了新的标杆在我们看来、在目前一段可以预期的时间内不会被超越！（译者注：好狂妄的老外） Disruptor并不是只能应用于金融业的解决方案，它是一种通用的机制，以简单的实现来最大程度的提高性能，用来解决并发编程中的复杂问题。尽管Disruptor中的一些概念似乎不大主流，但是以我们的成功经验证明，使用这种模式构建系统要比使用同类机制实现起来简单得多。 Disruptor框架显著的减少了写的争用、具有更低的系统开销和比之同类其他机制更好的缓存（译者注：这里指CPU的缓存）友好特性，所有这些优点使Disruptor具有更加强大的吞吐性能和平稳的低延迟处理能力。使用中等的时钟频率的处理器，我们测试得到了每秒2500万消息发送，上述延迟低于50纳秒（译者注：1纳秒=一秒的10亿分之一，神乎其技啊！）。这样的性能相对于我们见过的任何其他的实现方案来说都是显著的提高。这已经非常接近现代CPU处理器在核心之间交换数据的理论极限了。（译者注：再次惊叹，神乎其技啊！）2 概述 Disruptor是我们在LMAX公司构建世界上最快的高性能金融交易平台过程中的研究成果。早期，我们的设计是基于SEDA派生和Actors模式的，使用管道来提供吞吐量。在评测了各种不同的实现之后，事实证明在各个管道的事件排队是主要的系统消耗来源。我们也发现队列产生相当的延迟和较高的时间偏差。我们花费了大量的精力去实现更高性能的队列，但是，事实证明队列作为一种基础的数据结构带有它的局限性在生产者、消费者、以及它们的数据存储之间的合并设计问题。Disruptor就是我们在构建这样一种能够清晰地分割这些关注问题的数据结构过程中所诞生的成果。3 并发的复杂性 在我们这一段里我们来讨论并发。在计算机科学中，并发的意思是两个或两个以上的任务同时并行的执行，但是也要通过争抢来接入资源。争抢的资源可能是数据库、文件系统、套接字、甚至或者说内存中的一块区域。 并发的执行代码包括两个方面：互斥性和改变的可见性。互斥性是指线程对资源进行争用状态的改变的管理（译者注：从后面看出，这里的争用状态主要是指写的操作要保持互斥性），而改变可见性是指控制何时这种改变对其他线程可见。很明显，如果能消除争用就能够避免互斥性管理如果有某种算法，能够确保任何给定的资源同一时刻只被一个线程修改，那么互斥性就不是必要的了。读和写操作需要所有改变对其他线程都是可见的，但是只有争用写操作需要保持互斥性。 在任何并发的环境中，争用写操作是花费最大代价的。为了支持多个并发的线程对同一块资源进行写操作是需要花费复杂而昂贵的代价来进行协调的。最典型的解决这种协调的方法是引入某种锁的策略。3.1 锁的代价 锁提供了互斥性并且确保改变对其他线程的可见性以一种命令式的方式发生。锁的代价消耗是难以置信的大因为它们当遇到争用时需要进行仲裁。这种仲裁是通过一种上下文切换到操作系统的内核，挂起线程等待锁的释放。在这样的上下文切换过程中，也会交还控制权给操作系统操作系统此时可能同时决定去做其他一些请理性的工作，这样正在执行中的上下文对象将会丢失之前预读的缓存中的数据和指令（译者注：这里的缓存指的是CPU缓存）。对现代CPU而言，这将会造成一系列的性能上的坏的影响。可以使用快速的用户模式的锁，但是这也仅当没有争用的时候能够带来真正的益处。 我们将会举一个简单的演示例子说明锁的代价。这个实验的主要内容是调用一个函数，执行一个循环5亿次的增量为64bit的计数循环。我们用Java编写这个程序后在2,4Ghz的Intel Westmere EP处理器（译者注：一款6核企业级应用CPU）上单线程执行，仅仅花费大约300毫秒的时间。其实用什么语言对这个实验来说并不重要，使用相同基本底层原语的语言编写的程序执行时间都差不多。 但是，一旦使用了锁来提供互斥性，那么即使当锁还未被争抢的时候，资源的消耗（译者注：这里主要指时间上的损耗）仍会显著的提高。而当多个线程开始发生争用现象时，花费在巨大的排队操作上的工作将会使程序对资源的消耗继续增加。这个小实验的结果如下面的表格所示：3.2 CAS 在需要修改的内存数据仅为一个字长时，有些更有效的方案可以用来替代锁来进行内存修改。这些替代方案是基于原子性、互锁性的现代CPU实现的指令的。这些指令通常被称为“CAS”(Compare And Swap)操作，例如x86处理器上的lock cmpxchg。CAS操作是一种特殊的机器码指令，它在一定条件下可以允许对内存中一个字长的操作成为原子操作。在上一小节的计数器小实验中，每个线程轮流在一个循环中读取计算器并尝试在同一个原子指令中将计算器累加为新的值。累加后的新值和累加前的旧值一起作为该指令的参数，如果指令执行后计数器的值与指令的新值参数相同，则指令执行成功，将计数器的值置为新值；否则，如果计数器此时与指令的新值参数不同，则该CAS操作失败，此时回到线程重新读取计数器增量加到原来的新值参数上作为新的新值参数（译者注：即设指令为f，新值参数为B，旧值参数为A，计数增量为k：由f(A,B)改为f(B,B+k)重新执行指令），重复上述过程，直到指令执行成功。CAS方法比锁要有效得多，因为它不需要切换上下文到操作系统内核去仲裁。但是，CAS操作也并不是没有资源消耗的，处理器必须锁定它的指令通道去确保原子性，并且要创建一个内存栅栏（memory barrier）来使得状态的变化对其他线程可见。具体到实际的编程实现上，CAS操作在Java开发中，可以使用java.util.concurrent.Atomic.*包中的类来实现。 如果程序的关键部分要比我们上面举的计数器例子复杂，这就需要更加复杂的使用多个CAS操作的机器指令来协调线程间的争用。用锁来编写并发程序很难；用CAS操作和内存栅栏开发无锁算法来编写并发程序有时候更难！而且这样的程序更加难以测试，难以确保其正确性！（译者注：好绝望啊orz） 理想的算法应该是仅仅使用一个单线程来处理所有的对一个资源的写操作，而有多个线程执行读取处理结果的操作。在一个多处理器或多核处理器环境下处理对资源的读操作需要内存栅栏来确保一个线程状态改变对其他处理器上运行的线程可见。3.3 内存栅栏 现代的处理器为了提高效率，采用无序的方式执行其指令、在内存和对应的执行单元间加载和存储数据。处理器仅仅需要确保程序逻辑执行出正确的结果而不去关心其执行顺序。这不是单线程程序的特性。但是当线程间彼此共享状态时为了确保数据交换的成功处理，在需要的时点，内存的改变能够按次序发生就是很重要的了。内存栅栏是处理器用来指出代码块在哪里修改内存是需要有序的进行的。它们是硬件排序和线程间保持彼此改变可见性的重要手段。编译器会在适当的位置设置合适的软件栅栏来确保代码按照正确的顺序编译，处理器本身也会使用这样的软件栅栏作为硬件栅栏的一种补充。 现代的处理器要比同代的内存快得多的多。为了填补这样一个速度差距的鸿沟，CPU使用了复杂的缓存系统非常快的通过硬件实现的无链哈希表。这些缓存系统通过消息传递协议与其他处理器CPU的缓存系统保持协调一致。另外作为补充，处理器的“存储缓冲”可以将写操作从上述缓冲上卸载下来，在一个写操作将要发生的时候，缓存协调协议通过这样的一个“失效队列”快速的通知失效消息。 这些对于数据来说意味着，当某个数据值的最后一个版本刚刚被写操作执行之后，将会被存储登记给一个存储缓冲可能是CPU的某一层缓存、或者是一块内存区域。如果线程想要共享这一数据，那么它需要以一种有序的方式轮流对其他线程可见，这是通过处理器协调消息的协调来实现的。这些及时的协调消息的生成，是又内存栅栏来控制的。 读操作内存栅栏对CPU的加载指令进行排序，通过失效队列来得知当前缓存的改变。这使得读操作内存栅栏对其之前的已排序的写操作有了一个持久化的视界。 写操作内存栅栏对CPU的存储指令进行排序，通过存储缓冲执行，因此，通过对应的CPU缓存来刷新写输出。写操作内存栅栏提供了一个在其之前的存储操作如何发生的、有序的视界。 一个完整的内存栅栏即对加载排序也对存储排序，但这只针对执行该栅栏的CPU。 一些CPU还有上述三种元件的变体，但是介绍这三种元件已经足够来理解相关的复杂联系了。在Java的内存模型中，对一个volatile类型成员变量的域的读和写，分别实现了读内存栅栏和写内存栅栏。（译者注：对volatile类型的成员变量虚拟机不采用优化策略，即不在每个线程中保存其副本，每次读取和修改都将到共享的内存域中进行）这在关于Java内存模型的一篇文章中已经有很详细的描述（/developerworks/library/j-jtp02244/index.html），上述这种特性已经随着Java 5一起发布。3.4 缓存行 (译者注：这里缓存行实际上是单词cache line的拙劣翻译-_-! 意思是CPU缓存与物理内存间交互时所一次发生的数据，一般为64个字节) 现代处理器使用缓存的方式对成功的高性能操作而言具有重要的意义。这种处理器架构在数据搅动和指令存储方面有极大作用，反之，如果缓存出现丢失的话将对系能造成极大的影响。 我们的硬件在移动内存数据的时候不是以字节和字长为单位的，为了更加有效的工作，缓存被组织成缓存行的形式，每个缓存行为32-256个字节大小，一般是64字节。这是缓存协调协议操作的粒度层级。这意味着如果两个变量在同一个缓存行内，并且它们是被两个不同的线程写入的话，它们将会呈现出相同的写争用问题，就好像它们是一个变量一样！这就是“伪共享”概念。所以为了提高性能，应该确保独立的且并发的写操作、并且写操作的变量不在同一个缓存行内，可以使争用最小化。 当访问内存时，一个具有预读功能的CPU会通过预读的方式来减少访问时花费的延迟CPU会预读有可能下次需要访问的数据、并在后台将其提取到缓存中。这种机制仅仅在处理器侦测到某种访问上的模式是时候启动，就好像是本来一步一步走路的内存访问突然来了个“跳跃”一样。比如，在对一个数组中的内容进行遍历的时候，上述的预读跳跃是会启动的，所以相应的内存数据会被提前提取到CPU缓存中，最大可能的提高了访问效率。上述跳跃一般来讲是不大于2048个字节的，或者说CPU能够预测到的字节也不大于这个数字。但是，像链表或树集这种由分散在内存空间不同位置的节点组成的数据结构，是没有办法启动预读跳跃的。这种在内存中没有规律的存储限制了系统预读内存行，会导致内存的访问效率下降两个数量级。3.5 队列所带来的问题 一般来说队列是使用链表或者数组来作为其中元素的基本存储的。如果一个内存中的队列没有被限制大小成为无界队列时，在很多种类的问题当中它可能会没有被校验的增长直到灾难性的出现内存耗尽为止，这种情况发生在生产者“跑”的比消费者快的时候。无界的队列在生产者确保不会跑的比消费者快的并且内存资源比较稀缺的系统中比较有用，但是如果这种假设不成立队列变得无限制的增长的话总会有一定的风险的。为了避免这种灾难发生，队列一般会被限制大小成为有界队列，方法是要么使用数组来实现队列、要么实时的去跟踪队列的大小。 队列的实现可能会在队首、队尾和记录队列大小的变量上发生写操作争用。在使用过程中，由于生产者和消费中跑的快慢不同，队列总是处于将满或者将空状态，而很少处于一种生产者快慢相当的平衡的中间状态。这种大部分时间处于将满或将空状态的倾向导致了大量的争用和昂贵的缓存协调代价。而且问题还在于即使用不同的并发对象（比如锁或CAS变量）来分别实现头尾机制，它们通常会占用同一块缓存行。（译者注：发生伪共享，导致并行失败） 使用单个大粒度的带锁队列，生产者声明队首、消费者声明队尾、中间的存储节点用来设计并发，这样的实现管理起来非常复杂。队列上为了put和take操作的大粒度的锁实现起来很简单，但是会导致吞吐量上很大的瓶颈问题。如果只使用队列自有的语义模型来消除并发矛盾的话，那么除了单生产者单消费者这种情况之外，其他情况实现起来相当复杂。 在Java中使用队列还有另外一个问题，队列是很容易产生垃圾的结构。首先对象会被分配并置放在队列中，其次如果是使用链表实现的队列，那么对象需要被分配去实现链表中的节点。当不再被引用的时候，所有这些为支持队列实现所分配的对象需要被重新声明。（译者注：实际上是说在Java中，队列的垃圾回收代价很大，特别是对链表式队列而言）3.6 管线和图 在许多种类的问题中把几个阶段处理捆绑为一个管线是个好办法，这些管线一般具有并行的路径，组成一种图状的拓扑结构。每个阶段之间的链接一般使用队列来实现，每个阶段具有其自己的线程。 这种方案的代价可不便宜在每个阶段我们不得不花费工作单元进队和出队的开销。当有多个目标其路径分叉时会加倍这种开销，并且当上述分叉路径必须合并时也会遭受无法避免的争用的代价。 如果处理图状依赖拓扑结构时，能够避免在各阶段之间使用队列的开销的话，那将是非常理想的。4 LMAX Disruptor的独特设计 在试着定位上面几段中描述的那些个问题的时候，一个通过严格剔除像队列导致的一系列问题为目标的设计浮现出来了。这个方案关注确保任何一块数据同一时刻只被一个线程执行写操作，因此便消除了写争用，这便是“Disruptor”框架。之所以叫这个名字，是因为它在处理依赖性拓扑结构的时候与Java 7中支持分叉合并的Phasers（译者注：Java7中引入的一种新的并发特性，属于一种新型并发barrier）有着相似的地方。 LMAX公司的Disruptor框架的设计被定位于上述问题，通过尝试最大化内存分配的效率、以缓存友好的工作方式优化在现代硬件上的性能。 处于Disruptor机制中心脏地位的是一个预先分配的有界数据结构形式环状缓冲。数据通过一个或多个生产者添加到环状缓冲中，并通过一个或多个消费者从其中取出处理。4.1 内存分配 环状缓冲（ring buffer）的所有内存空间是在启动的时候预先分配好的。环状缓冲既可以存储一整个数组的指向实体的指针、或者是代表实体本身的数据结构。由于Java语言本身的限制意味着实体是以对象的引用的形式存放在环状缓冲中的。每一个实体一般并不是直接存放的，而是放在一个容器里，而把容器放在缓冲中。这种实体存放空间的预分配的形式终结了支持垃圾回收机制的语言所带来的问题，因为实体会被重复使用并在Disruptor实例的生命周期中一致存在。这些实体的内存空间是在同一时刻分配好的，并且一般来说是在内存中连续的一块地址，因此支持缓存跳跃（译者注：即前文中提到的预读跳跃）。John Rose有一篇关于Java语言的建议,介绍什么样的值类型允许Java的数组能够像其他语言、例如C语言中那样确保分配给其的内存是连续的，从而避免使用指针寻址。 在一个像Java这样被管理的运行时环境中开发低延迟系统时，垃圾回收可能会是个问题。分配的内存越多，垃圾收集器的负担就越大。当对象的生命周期都极短或者对象永不销毁的情况下，垃圾收集器可以达到最佳性能(译者注：实际上是最小的负担)。环状缓冲中的实体内存是预先分配好的，意味着它在垃圾回收器工作的时候是永不销毁的，所以只带来很少的负担。 由于基于队列的系统在高负载时会导致执行率降低、并且导致分配的对象释放其所在空间上的延迟，所以一代又一代的垃圾收集器都在这一点上进行不断优化。这有两层意思：第一，对象不得不在每一代之间进行复制，这导致了不定的延迟。第二，这些对象可能会从旧代中收集，这可能会是更加消耗性的操作,可能增加“世界停止”一般的暂停,这发生在零碎的内存空间被重新压实的时候。在大内存堆中这会导致每GB数秒的暂停。4.2 梳理影响因素 4.3 使用序列号4.4 批量效应 当消费者等待环状缓冲中最新可用的游标序列号时会有一定几率发生一个在队列中不会发生的有趣的现象：如果消费者发现与它上次检查的时候相比，环状缓冲的游标已经向前走了许多步的话，它可以直接处理到那个最新的序列号而不必纠缠于并发机制。这样的结果是本来落后的生产者会重新赢得与之前突然爆发的生产者的赛跑比赛，重新平衡了系统。这种批量效应增加了处理吞吐量并减少和平稳了延迟。根据我们的观察，在内存子系统饱和之前，不管负载多大，这种效应的延迟始终接近一个时间常量，对应的变化曲线是线性的并遵循利特尔法则，这与我们使用队列时在负载不断增加时延迟呈指数级增长得到的J形曲线是截然不同的。4.5 依赖关系 队列代表着一个生产者与消费者之间的简单单步管线依赖。如果消费者之间形成了某种链状或图状依赖关系的话，在图状依赖的每个阶段就都需要一个队列。在图的各个依赖阶段之间导致大量的队列固定时间消耗。在我们设计LMAX公司的金融交易平台的时候，我们的研究表明，基于队列的方案在事务处理中的执行延迟大量是花费在排队上了（译者注：大量花费在排队上而不是事务本身的处理逻辑）。 因为使用Disruptor模式分离了生产者与消费者矛盾，使得我们可以仅仅使用核心的环状缓冲来表示复杂的多个消费者之间的依赖关系。这减少了大量的执行上的固定消耗，并增加了吞吐处理能力、减少了延迟。 一个环状缓冲可以用来存储表示一整个工作流的复杂数据结构的实体。在设计这样的数据结构的时候必须注意，在被独立的不同消费者写入的时候要避免导致缓存行的伪共享。4.6 Disruptor的类结构图 下面的类图描述了Disruptor框架的核心关系。如图中所示，易于使用的类可以简化编程模型。在建立了依赖关系之后，编程模式变得很简单。生产者通过ProducerBarrier使用序列号声明实体，在声明好的实体中写入改变，然后通过ProducerBarrier将实体提交回来并使其可以被消费者使用。而消费者仅仅需要提供一个BatchHandler的实现即可，该实现负责接收当一个新的实体可用时的回调请求。这种结果驱动编程模型是基于事件的，与Actor模型有很多相似的地方。 在分离了使用队列实现所带来的问题之后，便可以实现更灵活的设计。Disruptor模式的核心RingBuffer，可以提供存储使得数据的交换在不发生争用的情况下进行。经由生产者、消费者与RingBuffer的交互中分离出了传统并发所带来的问题。ProducerBarrier负责管理所有在环状缓冲中声明序列位置的并发问题，并跟踪各个消费者以确保这个环不会缠绕。（译者注：在RingBuffer这个环状的跑道上，最快的生产者超过了最慢的消费者，即为环的缠绕。）ConsumerBarrier用来提醒消费者是否有新的实体可用，这样消费者便可以构造图状的依赖关系用来表示一个处理关系中多个阶段。4.7 代码示例 下面的代码是一个单生产者单消费者的例子，使用了方便的BatchHandler接口来实现消费者。消费者使用单独的线程来接收那些可用的实体。/Callback handler which can be implemented by consumersfinalBatchHandler batchHandler = newBatchHandler()public void onAvailable(final ValueEntryentry) throws Exception/ process a new entry as it becomesavailable.public void onEndOfBatch() throws Exception/ useful for flushing results to an IOdevice if necessary.public void onCompletion()/ do any necessary clean up beforeshutdown;RingBufferringBuffer =newRingBuffer(ValueEntry.ENTRY_FACTORY, SIZE,ClaimStrategy.Option.SINGLE_THREADED,WaitStrategy.Option.YIELDING);ConsumerBarrierconsumerBarrier = ringBuffer.createConsumerBarrier();BatchConsumerbatchConsumer =newBatchConsumer(consumerBarrier, batchHandler);ProducerBarrierproducerBarrier = ringBuffer.createProducerBarrier(batchConsumer);/Each consumer can run on a separate threadEXECUTOR.submit(batchConsumer);/Producers claim entries in sequenceValueEntryentry = producerBarrier.nextEntry();/copy data into the entry container/make the entry available to consumersproducerBmit(entry);5 吞吐量性能测试 作为对比，我们选取了Doug Lea的优秀数据结构java.util.concurrent.ArrayBlockingQueue来作为参照，这种队列在我们测试中在所有的有界队列中是性能最好的。这些测试设置成一个阻塞的编程用来匹配Disruptor。这些个测试的详细代码已经包含在Disruptor的开源项目里了。注意：想运行这些测试的话需要能够并行运行四个线程能力的硬件环境。（译者注：恩，没错，这个Disruptor是个白富美框架，想护到她的，实力低于i5双核4线程的就赶紧去升级CPU吧。）在上面的配置中，每条数据流的弧是用ArrayBlockingQueue来实现的，与之对比Disruptor使用的是一种内存栅栏。下面的表格列出了每秒操作数的性能测试的结果，使用Java 1.6.0_25 64-bit Sun JVM，Windows 7，Intel Core i7 860 2.8GHz 不带超线程，另一组使用Intel Core i7-2