加载中…
正文 字体大小:

Disruptor:High performance alternative to bounded queues for&nbsp

(2012-11-14 23:42:27)
标签:

hpc

java

分类: 分布式

前言:译自Lmax团队的一篇论文,里面夹杂自己的点评,甚至有自己的臆测,算是夹带私货吧。原文请自行google搜索。原文题目为:Disruptor:High performance alternative to bounded queues for exchanging data between concurrent threads

【1摘要】

Lmax的应用场景是一个高性能的财务交易系统。作为我们工作的一部分,为了达到我们的目的,我们评估了若干种不同的方法。但是经过测量我们发现一些通常的做法都有局限之处。

许多应用程序通过队列来在不同的处理阶段之间交换数据。我们的性能测试显示,如果按照传统的方式来使用队列,延时代价的量级和磁盘IO操作的延时量级是同一个量级-非常慢。如果采用多个队列,很显然这又会增加了几百个毫秒的额外开销用于协调这些队列。这里有很大的优化空间。

通过进一步对计算机科学的研究和调研,我们意识到通用方法中很多关注点都是纠结在一起的,这就导致了多线程的竞争。关注点纠结在一起明显给了我们一个信号,我们还可以做的更好。

我们通过充分考虑现代CPU是怎么工作的(这也就是我们常说的机制共鸣),通过隔离关注,我们提出了一个数据结构和基于该数据结构的使用模式,这就是disruptor。

测试也显示,对于一个三阶段的任务管道(把任务处理分为三个阶段),Disruptor的平均延时的数量级要小于基于传统队列的方法三个数量级。另外disruptor的吞吐量是传统方法的8倍。

这些性能改进也意味着对于并发编程我们前进了一大步。对于高吞吐量和低延时的异步事件处理系统,这种新的模式是一个非常理想的基础组件。

在Lmax中,我们已经建立起一个订单匹配引擎,实时风险管理系统,以及一个高可用性的内存事务处理系统,这些系统都是基于disruptor。这些系统的性能都是很牛的。

这个系统不只是专门为财务行业涉及的,它具有相当的通用性,他能够解决并发编程中的一个复杂问题:如何最大化性能。这个系统的实现非常简单。尽管这里面的有些概念不是那么直观,但相比于其他机制,基于这种模式的系统往往更加简单。

相比于其他方法,disruptor的写竞争比较少,并发overhead更低,而且更加cache friendly,吞吐量更高,延时抖动更低。对于一个普通时钟频率的处理器,disruptor每秒处理的消息量为2500万,延时低于50纳秒。这个性能指标已经接近于现代处理器在多核之间交换数据的上限。

【2概述】

Disruptor是我们开发的世界上最快的财务交易系统Lmax的产物。早期的设计主要是集中在类似于SEDA和Actors这样的架构,这样的架构主要利用pipeline来交换数据。通过仔细分析这两种架构的各种实现,我们发现在pipeline的不同stage之间交换event的队列是性能的主要杀手。我们发现队列带入了剧烈的延时抖动。我们为了达到更好的性能于是花了很多精力来开发一个新的队列实现。然而,我们都知道队列是一种很基础的数据结构,它需要处理生产者,消费者,数据存储等许多方面,这些方面纠结在一起十分棘手。Disruptor的队列实现就很好得实现了所谓的“关注隔离”,而且并发性很好。

【3并发的复杂性】

在这篇文档中,计算机科学中通常所讲的并发不仅仅是说有两个或者多个任务同时执行,他还意味着对资源的竞争访问。这些竞争的资源可能是数据库,文件,socket或者内存中的某个地址。

代码的并发执行主要有两个方面,互斥和变化的可见性。互斥主要用来管理对某些资源的竞争更新。变化的可见性主要是用来控制什么时候这些变化对其他线程可见。如果你能够在应用层面上限制并发更新那么你就有可能避免互斥。比如,如果你的算法能够确保任何资源只会被一个线程更新,那么互斥就是不必要的。读或者写要求所有的变化对其他线程可见,但实际上只有竞争写操作才真正需要互斥。

并发环境中最耗费时间的操作其实就是并发写操作。多线程对同一个资源的写需要复杂昂贵的协调。通常这是通过某种锁来实现协调。

【3.1锁的代价】

锁提供了互斥,并能够确保变化能够以一个确定的顺序让其它的线程看见。锁其实是很昂贵的,因为他们在竞争的时候需要进行进行仲裁。这个仲裁会涉及到操作系统的内核切换,它会挂起所有在等待这把锁的线程,直到锁持有者释放该锁。由于在内核进行仲裁过程中,原有的线程会丧失对操作系统的控制,操作系统此时会做一些其它的日常工作,那么原有线程的指令缓存和数据缓存则有可能被丢掉。这会对处理器造成严重的性能问题。当然用户状态的锁是另一种选择,但用户锁只有在没有竞争的时候才真正会带来益处,因为用户态的锁往往是通过自旋锁来实现(或者带休眠的自旋锁),而自旋在竞争激烈的时候开销是很大的(一直在消耗CPU资源)。

为了探究影响到底有多大,我们写了一个程序。这个程序很简单,就是调用循环500 million次做递增的函数。这个java函数在单线程,2.4G Intel Westmere EP的CPU上只需要300ms。

一旦引入锁,即使没有发生竞争,程序的执行时间也会发生显著的增加。实验结果如下:

wps_clip_image-15098

【3.2CAS的代价】

除了锁之外,另外一种方法是CAS。CAS依赖于处理器的支持,当然大部分现代处理器都支持。CAS相对于锁是非常高效的,因为它不需要涉及内核上下文切换进行仲裁。但cas并不是免费的,它会涉及到对指令pipeline加锁,并且会用到barrier(用来刷新内存状态,简单理解就是把缓存中,寄存器中的数据同步到内存中去)。CAS操作在JAVA中是支持的-java.util.concurrent.Automaic

CAS的一个问题就是太复杂了,本来用锁进行并发编程就已经很头疼了,用CAS来实现复杂逻辑就更头痛了。

最理想的算法就是只有一个线程来负责对单个资源的所有写,而其它所有的线程都是读结果。在多核环境中读取结果会要求memory barrier来使得变化对运行在另外的CPU核心上的线程可见。

【3.3Memory Barrier】

现代处理器为了获得更高的性能,它执行指令时会按照需求调整指令顺序,内存和处理单元之间的数据加载和读取指令的顺序也会被调整。处理器只会确保程序逻辑产生程序想要的结果而不会关心指令执行顺序。对于单线程程序,指令顺序并不会造成问题。但对于多线程程序而言,由于线程之间需要共享状态,因此内存变化的顺序就变得非常重要,他们被要求在某些执行点上必须让内存的变化对其它线程可见。处理器用memory barrier来标识代码片段,这些被标识的代码意味着内存更新的顺序在这里非常重要。有很多方法可以在线程之间确保指令的硬件执行顺序和变化的可见顺序。编译器可以在代码中的合适位置放入软件barrier来确保代码的执行顺序,当然处理器本身也会有硬件barrier。

现代CPU相比内存系统来讲速度是非常快的。因此在CPU和内存之间引入了缓存系统,缓存系统你可以认为是一个非常快的硬件哈希表。不同CPU之间的缓存是通过message passing protocol来保持缓存之间的耦合性。另外,处理器还会有“存储buffer”卸载缓存压力。处理器还会包含一个“失效队列”,这个队列是用来处理缓存耦合协议的,如果当有一个写操作发生,缓存耦合协议能够很快响应“失效队列”中的“失效消息”。

对于数据而言,最新版本的数据在写入之后的任何阶段,有可能在寄存器里,有可能在存储buffer里,也有可能在众多缓存层次中之一,或者在内存中。如果线程要共享这个值,那么这个值必须要按照一定的顺序对其它线程可见,这种顺序的可见性是通过cache耦合消息来实现的。Memory barrier可以用来定期产生这些消息。

Read memory barrier用来为CPU的读取指令排序,排序是这么实现的:read memory barrier会在“失效队列”中标记一个节点,这个节点意味着read barrier之前读取的所有数据都已不可靠(这也就告诉我们可能有变化发生),之后的所有read操作都需要重新从内存中加载,因此之后的操作从而能够看到数据的最新变化,barrier之前的所有线程的写指令和barrier之后的读指令就有了一个先后顺序。Read memory barrier使得排在read memory barrier之前的写操作成为一个整体,在这个整体内部写操作的顺序是不确定的,但这个整体形成了一个完整的视图,整个整体的结果对后面的操作是可见。

Write barrier用来为CPU的存储指令排序,write barrier会在“存储buffer”中标记一个节点,这个节点之前的数据变化(write操作)会flush缓存,把数据变化直接写到内存中去。Write barrier之前的写操作会作用到内存中去,从而对其他线程可见。

还有一种barrier是full barrier,它的作用相当于read barrier + write barrier。

综上所述,实际上read barrier意味着read操作不能穿越这个read barrier,write barrier意味着write操作不能穿越这个write barrier。所以很形象吧?

回过头来总结下,执行read barrier的CPU是多线程中的消费者的角色,它通过read barrier能够尽快看到生产者线程的执行结果。而执行write barrier的CPU往往充当生产者的角色,它通过write barrier把自己执行的结果尽可能快得让其它线程看见。

在Java内存模型中,对volatile域的读取和写入实际上就是对应的read barrier和write barrier。Java内存模型规范对此有明确的定义。

【3.4 缓存行】

我们都知道如果数据在缓存里而不是内存里,那数据操作的效率将会极大提高。如果缓存丢失频繁发生,那效率就会很低下。

现代CPU操作缓存并不是以字节或字为单位,而是以cache-line为单位,一个cache-line的大小在不同的CPU体系结构中有所不同,范围大概是从32字节到256字节不等,最常见的cache-line的大小是64字节。Cache-line是cache耦合协议进行工作的基本单位。这就意味着如果两个变量不幸在同一个cache-line里,而且它们分别由不同的线程来进行写入操作,那么此时这两个变量的写入会发生竞争,就好像多线程在竞争写入同一个变量一样。这种现象被称之为JVM的伪共享。对于那些性能要求比较高的应用而言,我们实现时需要充分避免这种情况的发生,让并发写入操作作用到不同的cache-line中去。

现代CPU的另外一个神器就是预取,这里的预取包括指令预取和数据预取。指令预取就不说了,比较简单,就是CPU知道下一步执行的指令是哪些,它在执行当前指令的同时在后台会提前把后面要执行的指令加载到CPU的缓存中来,所有的代码都会从指令预取中受益,不管这个代码写得有多烂。另外一种就是数据预取,CPU非常智能,它根据访问模式可以预测下一个可能访问的内存地址是哪一块,从而在执行当前操作指令的同时,在后台提前把下一步可能需要访问的内存提前加载到CPU缓存中来。这就要求我们写的程序最好能够按照一个固定的模式来访问内存,访问的模式是可预测的,这样来帮助CPU预测下一步需要加载的内存。遍历数组就是一个非常好的例子,它的访问模式就是可预测的,因此遍历数组是非常高效的。一般要让遍历的步伐小于2048个字节,因为CPU可以注意到在任意方向上的较小的遍历步伐形成的访问模式,如果遍历步伐太大,CPU可能无法正确预测访问模式,尤其在遍历的方向会不断发生变化的时候。对于链表或者树这种数据结构,由于节点分布的范围太广,而且不均匀,因此它们的访问模式就是不可预测的,因此效率比较低。需要提醒的是,内存的运行效率要低于缓存两个数量级,两个数量级上的差别足以提醒我们要善待缓存。

【3.5队列引起的问题】

队列通常有两种实现,基于链表的队列和机遇数组的队列。如果一个队列是处在内存中并且队列的长度是不受限制的,那么这个队列的长度可以一直增长直到系统内存耗尽。这种情况一般是在生产者的效率大于消费者的情况下发生。所以如果系统中生产者的效率小于消费者而且内存资源比较充足,那么可以使用这种长度不受限的队列。但是允许队列一直增长而不受限制总是不太安全,因此大部分情况下队列的长度还是固定的。队列的长度固定这就意味着要么队列的实现是数组的,要么队列的长度会一直被维护跟踪。

队列的头(消费者要频繁使用),尾(生产者要频繁使用)以及长度(生产者和消费者都需要频繁更改)通常是竞争的资源。当队列在使用时,在大多数情况下队列要么是几乎是满的,要么几乎是空的,这是由于生产者和消费者不同的工作节奏造成,由于领域问题的复杂性,在实际的系统中消费者和生产者的节奏几乎不可能匹配。几乎满/空的队列会导致严重的竞争(以一个几乎为空的队列为例,大量的消费者线程竞争极少数的商品,很多线程一定会被阻塞,大量线程被阻塞是非常糟糕的,因为这就意味着CPU的能力没有被榨干,同理,几乎为满的队列会让大量的生产者线程陷入剧烈的竞争),严重的竞争也就意味着CPU需要进行昂贵的缓存同步(缓存同步是为了让变化尽可能快得对其他线程可见)。大部分队列设计者会聪明得为队列的头指针和尾指针使用不同的同步对象(比如锁或者CAS变量)来提高并发性,但往往会把这两个对象(头指针锁和尾指针锁)放在一个对象中的相邻的位置(这是由编程的习惯性导致的,大部分程序员会把功能相似或者有某种对应关系的域定义放在类的相近位置),不幸的是这两个对象有可能在同一个cache-line中。

生产者关注队列头,消费者关注队列尾和头尾之间的存储节点,这使得管理一个并发的队列非常复杂。当然,也有简单的方法,用一把粗粒度的锁把整个队列都锁住,无论是take操作还是put操作都需要持有这把锁。这么做固然简单,但效率差也是显而易见的。如果想要很好得解决队列场景下的并发问题,那么队列的实现就必然很复杂,当然如果你是单生产者-单消费者的场景,那么也许队列实现没有必要那么复杂。

如果你用的语言是JAVA,那么你还需要考虑垃圾回收的影响。首先商品对象需要被分配然后放入队列,其次如果你用的是基于链表的队列,那么你还得要考虑分配代表节点容器的对象。当这些对象不再被引用时,它们需要被回收。因此基于链表的队列固然灵活,但由此会引入大量的垃圾回收,相比而言数组队列由于一次分配终生使用从而避免了垃圾回收,如果单纯考虑性能,可以多考虑数组队列。

【3.6管道和图】

设计复杂问题的时候,很多架构师一个通常的做法是把整个工作分成各个不同的stage,这些stage组成一个复杂的依赖关系图来共同完成整个系统的工作,这些stage我们也可以称之为它们组成了一个pipeline。各个stage之间通过队列来交换信息。每个stage针对每个队列设置一个专门的消费者线程来维护,每个stage也有自己专门的一个生产者线程。这么说可能比较晦涩,我来举个例子吧。

wps_clip_image-18431

上面图讲的是如何组装一台小汽车,要组装一台汽车,我们第一阶段要有个底座,接着装引擎,装驾驶员座椅,装乘客座椅,装后座座椅等等等等,最后是装四个轮子。这里每个圆圈都代表一个stage。箭头代表依赖关系(或者路径),这很容易理解,只有四个门和引擎盖都装好了(body complete)才能进行喷漆工作。每个箭头都意味着一个队列,箭头两端代表着生产者和消费者。每个消费者和消费者都意味着一个线程。比如对于paint而言,它拥有五个消费者线程来处理队列。

这么做看起来很朴素,但其实Actor和SDEA等大名鼎鼎的架构都是源自类似的朴素简陋的思想。这么做固然好,但也是有代价的,让我们来分析下代价。首先有队列就意味着有出队和入队的操作,这就意味着开销。对于chassis stage而言,它作为生产者,它的开销 =  路径数 * 入队开销(对于chassis stage,同样的消息我需要重复传播4次到4个不同的目的stage,浪费啊...)。对于paint stage而言,它有五个消费者线程来处理不同的队列,这五个消费者线程互相竞争CPU,内存以及其他资源(比如为了给paint stage准备数据,大家一起往一个对象里填充数据),如果线程数目不是5个,而是500个,这个压力还是很大的。通过分析我们看到,由于各个stage在业务中的作用不同,造成了压力分布的不均衡,比如bonnet stage就比较闲,paint stage就比较忙。而且对于类似chassis这样的stage,同样的消息要重复插入多次,带来了开销浪费。不均衡和浪费正是我们感觉不爽的地方。

能改进么?可以。同样是这样的依赖关系图,如果我们能把各个stage之间联系的队列去掉,用一种统一的数据结构来代替,这样就避免了重复,这该多么理想。而且基于统一的数据结构,如果我们能够用统一的可控的线程组来控制,就能使得压力比较均匀,这不也是我们求之不得么?实际上disruptor的思想就是来自于此。

【4 Lmax disruptor设计】

为了解决上面提出的问题,设计中我们严格得实现了关注分离。设计中,我们确保对于任何数据而言只有一个线程来进行写访问,从而避免写冲突。

Lmax disruptor设计之初的目的就是为了解决前面提出的问题,它试图最大化内存分配效率,以一种cache friendly的方式来工作,从而使得它的性能能够得到优化。

Disruptor的核心数据结构是一个ring buffer,这个ring buffer是一个预先分配的,大小固定的数据结构。一个或多个生产者向该buffer添加数据,一个或多个消费者处理buffer中的数据。

【4.1内存分配】

Ring buffer的所有内存是在启动时预先分配的。Ring buffer要么是一个引用(不那么严谨的话,我们也可将它称之为指针)数组,每个元素是指向对象的引用(针对C#, java这样的语言),要么是一个结构数组,每个元素代表的就是对象实体(针对C,C++这样的语言)。由于java语言的限制,Java实现的Ring buffer实际上只能是一个指针数组。每个元素只能是一个指针,而不是数据本身。这种预先分配的策略就能够避免Java内存回收引起的一些性能问题,因为这些元素对象在整个disrutpor运行期间不会被回收(disruptor一直引用这些对象,JVM无法回收这些可达的对象)。由于这些对象是在开始阶段同时分配的,因此有很大的可能这些对象在内存中是连续的,即使不连续它们在内存中得间隔也有可能是固定的,这样非常有利于缓存的数据预取。John Rose提出了一个草案希望未来JAVA能够支持所谓的“value type”,就像C语言那样,如果这样的话,disruptor就能够确保对象在内存中一定是连续的,而不仅仅只是有很大可能性了。

对于JAVA这样的环境来讲,垃圾回收对于低延时系统是一个严重的挑战。内存越大,垃圾回收造成的性能压力也就越大。垃圾回收喜欢的对象要么寿命非常短,要么对象干脆是不死的。Ring buffer的预先分配使得我们的对象变成了不死的对象,这是大大减轻垃圾回收的压力。

通常的队列系统(没有采用预分配数组的队列系统,这些队列中的元素都是些临时对象,一旦消费者处理完之后就会被垃圾回收)如果压力很大,那么有可能会造成原先分配的临时对象在内存中存活的时间变得比较长,这很好理解,举个例子,由于消费者线程压力太大,不能及时处理完队列中的元素,这些元素本来在队列中只存在5s,结果由于忙不过来,要10s才能被处理,也就是说10s之后才有可能被回收。这就意味着:

1) 这些对象需要不断地在年轻代内部之间以及年轻代和老年代之间进行拷贝,这回造成延时波动

2) 当这些对象被移入老年代之后,由于老年代满足一定的条件也会触发对老年代对象的回收清理,这种回收清理(major collection)会释放那些死亡对象,如果发现需要释放的对象太多,那么这种代价会越昂贵,而且释放会造成大量的碎片,为了清理这些内存碎片时需要进行一些内存的合并,这些合并甚至有可能导致程序的暂停(stop the world),严重影响性能。如果在老年代中需要被清理的对象数目越多,那么内存释放的代价就会越大,造成的老年代碎片也就会越多,那么stop the world发生的可能性也会越大,这是非常可怕的。

如果对象是永生不死的,1)的代价无法避免,但2)的代价就会大大降低,因为这些对象一直会存在,那么老年代触发major collection时它扫描一下所有对象,发现这些对象都无法释放,什么都不用干,那就直接收工。由于对象不会被释放,那也就不会有碎片,那么stop the world的概率也就大大降低了。永生对象在2)中所做的只不过是进行一次扫描,这个代价非常小。

如果对象存活时间比较长但又不是永生不死的,每个GB的内存每次回收可以造成数秒的延时,这太糟糕了。

【4.2关注分离】

在实现队列的时候,后很多方面要考虑,而且这些方面纠结在一起,令问题十分棘手:

1) 队列元素的存储

2) 生产者会声明下一个需要交换的队列元素的序号,队列需要协调这个序号

3) 协调消费者,消费者需要获得元素就绪的通知

对于Java这样的需要垃圾回收的语言,太多的内存分配会造成严重的性能问题。因此,基予链表的队列实现不会是一个好的选择。如果队列的数据存储是预先分配好的那么垃圾回收的影响会被降至最小。如果队列元素的内存分配是统一大小的,不会有的元素大,有的元素小,那么数据的遍历就会非常的cache friendly。满足这样要求的数据结构就只能是数组,而且数组中的元素实现被填充。Disruptor使用抽象工厂模式来预先分配元素。生产者通过copy的方式将数据拷贝到预先分配的元素结构中去。

对于现代处理器而言,取余操作是一种比较昂贵的操作。但在ring buffer中取余是一个使用频率很高的操作,因为需要计算某一个序号在buffer中的位置需要用到取余。一个替代的方法是将ring buffer的长度设置为2的幂,这样通过简单的位操作就可以获取余数,这样代价就小多了。

我们前面提到,定长队列会在队列头和队列尾形成激烈的竞争(尤其是队列是满的或空的时候,很多消费者和生产者会被阻塞)。而ring buffer则可以避免这种竞争,因为ring buffer把这种竞争移到生产者barrier或者消费者barrier中去,这就是说竞争会影响某一个消费者或者某一个生产者的性能,但不会在队列本身造成大量的阻塞线程。

Disruptor的典型应用场景是只有一个生产者,典型的生产者是文件读取或者网络侦听。如果只有一个生产者,那么对于队列元素分配或者序号分配就不会造成竞争。

当然Disruptor也可以用于多个生产者的情况,这种情况下生产者可能会彼此竞争来获取ring buffer中下一个可以用于填充元素对象的位置,这是通过序号的CAS操作来决定的。也就是Lock-free编程。

当生产者将相关的数据拷贝到相应的位置中去,它需要提交这个序号(把序号写入公共变量让所有人可以访问)将它向消费者公开使得消费者可以消费该数据。但问题来了,什么时候可以提交该序号呢?多个生产者一起工作的时候,如果生产者a在序号98,生产者b在序号99,生产者c在序号100,当c完成数据拷贝时,b和a还在拷贝过程中,此时c不能马上提交这个序号,因为如果一旦c提交100,有可能消费者会马上消费该元素,这样消费者就跑到位于尾部的生产者后面去了,这违反了队列的先入先出的特性。如果不使用CAS,一种简单的做法是生产者线程一直自旋,直到另外的生产者线程的序号大于等于自己的序号为止。这样的话,该生产者就可以不断得单调移动消费者的游标(该游标指示消费者可以从某个位置开始消费元素,该游标应该是单向移动的,只能前进,不能后退,如果不采用前面提到的自旋方法,那么游标就必须能过回退,这是不满足队列FIFO特性的),指示下一个有效可供消费的元素。为了避免生产者的速度远远大于消费者的速度从而造成生产者的写入会覆盖前面还未读取的元素(这个很好理解,ring buffer是一个环,一直向一个方向移动最终会回到原点),生产者在向ring buffer写入数据之前需要读取一下消费者的游标现在在哪里,从而避免覆盖的产生。

消费者在读取元素之前需要等待一个序号,该序号指示了有效的可以读取的元素。怎么样等待这个序号,有很多种策略。如果CPU资源比较宝贵,那么消费者可以等待某一个锁的条件变量,由生产者通过singalAll来唤醒消费者。这种方式明显会带来竞争,而且适用的场景是CPU资源的稀缺性要远高于系统的延时/吞吐量。另外一种策略是所有消费者线程循环检查游标,该游标表示有效的可供读取的元素的位置。这种策略需要耗费大量的CPU,如果你希望获得CPU资源上的一些妥协,你可以通过thread.yield()按照一定的频率来交出CPU的控制权,避免独霸过多的CPU资源。这种方法由于没有用锁和条件变量,因此打破了生产者和消费者之间的依赖关系。如果你想支持多生产者-多消费者的场景,你就不得不采用很多CAS操作,这些CAS操作作用在头,尾,队列长度等等,这就带来了复杂性。但disruptor避免了这种复杂的CAS竞争。

【4.3顺序化】

顺序化是disruptor管理并发的核心概念。每个生产者和消费者都维护自己的序号,这个序号用来和ring buffer交互。当一个生产者希望在ring buffer中添加一个元素时,它首先要做的是声明一个序号,这个序号被称之为生产者的声明序号,该序号用来指示下一个空闲的slot的位置,一旦序号被声明,那么该序号就不会被其它生产者重复操作,生产者就可以操作该声明序号的slot数据。如果在单生产者的场景下,这个声明序号可以是一个简单的整数。对于多生产者的场景,简单的整数就不能满足了,这个序号就必须是一个原子变量比如AutomicInteger,并且更新操作必须建立在CAS操作上比如AutomicInteger.compareAndSet(解释下,比如两个生产者A和B,目前的序号为20,A和B同时希望找到下一个空闲slot,它们通过向后遍历检查,都发现22对应一个空闲slot,这时候A,B都想把序号从20更新到22,然后向22插入数据,但B快一点,更新成功,那么A通过CAS发现序号已经被人改了,A则返回从22开始继续寻找下一个有效的slot,通过CAS保证了每个生产者所声明的序号只会被该生产者所独自占有)。当生产者完成更新元素后,它就通过更新一个单独的序号来提交变化,这个单独的序号是一个游标,用来指示消费者可以消费的最新的元素(简单理解可以把这个游标当作队列尾部指针,那么消费者可以消费自己刚刚消费的序号和该队尾游标之间的slot元素)。生产者可以通过一种自旋的方式来更新队尾游标,如下:

wps_clip_image-25795

这段程序的目的很简单,就是用来更新队尾游标。当生产者声明某一序号并向该序号的slot更新元素之后,它需要更新队尾游标,从而使得消费者知道一个新的元素已经被添加到队列中来了。它不能马上更改cursor为该生产者的声明序号,为什么呢?原因很简单,假如下面这个例子:

#12   #13(Cursor)   #14 (Producer-A)   #15 (Producer-B)  #16 (Producer-C)

比如上面的例子,生产者A,B,C分别在slot #14, #15, #16,它们正在添加数据,此时队尾游标cursor = slot #13。 A,B,C谁先完成添加工作的顺序是不一定的,比如B最先完成,如果它此时直接更新cursor为#15,而不幸的是A此时还没有完成,那么cursor=15就是一个错误,因为我们知道cursor代表队尾,而队尾暗示着任何小于cursor的slot都是有效的可供消费的队列元素,可#14明显不是,因为A还没有完成所有的添加工作。而通过上面的代码,我们就能保证队尾游标的更新顺序一定是A,B,C

消费者通过memory barrier来读取这个队尾游标cursor,一旦消费者发现cursor更新了,这就意味着有新的元素被加入队列了,同时也意味着某一生产者的更新得到了提交,那么消费者就可以自由消费了。

每个消费者都各自维护一个序号来表示自己最新消费的slot序号。生产者通过跟踪这些序号来确保不会生产者不会由于生产速度远大于消费者导致越界。同时由于这些序号都是可以用于协调消费者之间的工作。根据前面提到的生产者和消费者更新的方法,我们注意到,多个消费者工作时所处理的slot一定是连续的,多个生产者工作时所处的slot也一定是连续的,队列中间没有元素空洞。

通过上面的分析,我们发现只有生产者声明序号才有可能需要CAS,其它操作不需要CAS。如果是在单生产者的场景下,甚至任何CAS都不需要,我们知道CAS操作难以控制,避免了CAS使得问题更加简单。

【4.4 Batch Effect】

Ring Buffer还有一个普通队列所没有的特性,那就是batch effect。如果一个消费者发现ring buffer的队尾游标距离自己上次处理的序号相差比较多,那么该消费者可以一次性读取这两者之间的所有队列元素(这里的读取指的是元素的深度拷贝),然后一次性处理。这个特性很有用,因为在现实世界中,消费者和生产者的节奏往往很不相同,或者在某些时间节点节奏不均衡,前面也提到了这种节奏的不匹配会造成消费者或者生产者比较饥饿,而batch effect可以平衡系统消除饥饿,降低延时,平滑延时。通过观察,我们发现,batch effect可以让延时保持在一个常数时间,不管系统的压力有多大。

因为ring buffer是一个队列系统,那么它天生就可以平滑延时,不至于在系统压力高峰时被迫降低生产者的吞吐量。这里讲延时可以保持在一个常数时间指的是生产者的延时可以保持恒定,直到内存资源被耗尽。消费者由于批量处理,则具有更好的程序局部性,更加cache friendly,使得消费者的吞吐量也得到提高。需要注意的是,Batch Effect只是尽可能快得减少元素在ring buffer中存在的时间,增加ring buffer的吞吐量,但对于元素处理事务的吞吐量,Batch Effect贡献有限。

【4.5 依赖图】

队列从本质上来讲表示一个简单的消费者和生产者之间的只具有一步的pipeline。如果消费者形成了一个链条,或者一个图状的依赖关系,那么图中的每个阶段之间都会需要一个队列。大量的队列就带来了开销。在设计LMAX财务交易系统的过程中,我们发现基于队列的设计方法会导致大量的队列开销,而这些为数众多的队列所带来的开销耗费了事务处理的大部分时间。

在Disruptor设计模式中,生产者和消费者被很好得隔离开了,因此通过使用一个简单的ring buffer也可以在消费者之间构造复杂的依赖关系。这就导致大幅度降低执行的延时,从而提高了吞吐量。

一个ring buffer可以用来处理一个具有复杂的依赖关系图的流程。设计ring buffer的时候需要特别注意,需要避免消费者之间造成的jvm伪共享。

【4.6 Disruptor类框图】

下图是Disruptor框架的核心类图。这个图里遗漏了一些简化编程模型的类。一旦业务流程的依赖关系图构建完毕,那么编程模型就变简单了。生产者通过ProducerBarrier来顺序申请entry,同时把生产者输出的变化写入这些申请entry中,然后再通过ProducerBarrier来提交变化使得这些变化对消费者可见。作为一个消费者,它所需要做的只不过是提供一个BatchHandler实现,这个实现是一个回掉函数,当一个新的entry可见时,这个回掉函数会被调用。这使得Disruptor编程模型是一个event based的模型,但和Actor模型有很多相似之处。

关注分离常常又和灵活性纠结在一起,我们希望队列能够关注分离,同时又希望它们具有很高的灵活性。Ring buffer是Disruptor模式的核心,它为数据交换提供了存储,同时又避免了竞争。通过ring buffer,生产者和消费者之间的并发问题被隔离开了。ProducerBarrier就是用来管理ring buffer中的slot中的slot声明,同时跟踪相关的消费者从而避免冲突覆盖。而ConsumerBarrier在有新的元素有效时会负责通知消费者。通过这些barrier,消费者之间就构造成了一个依赖关系图,这个依赖关系关系图实际上代表了流程处理过程中的各个stage。

wps_clip_image-2380

【4.7 代码示例】

下面的代码示例是一个单生产者和单消费者的场景,它通过BatchHandler来实现消费者。消费者运行在一个单独的线程上,它用来接收元素(一旦元素有效的时候)。

wps_clip_image-17556

wps_clip_image-5286

【5 吞吐量性能测试】

为了更有说服力,这里采用了Doug Lea的ArrayBlockingQueue的实现。对于有限长度队列而言,ArrayBlockingQueue的性能已经是最快了。测试是按照阻塞的方式进行的。

wps_clip_image-30171

上图代表了几种应用场景,比如一个生产者P1,三个消费者C1,C2,C3等等。对于ArrayBlokingQueue,上图中的每一个箭头就代表一个队列。而对于Disruptor模式,所有的箭头都是通过barrier来表示。下图就是测试的数据,取了三次最好的结果做对比。

wps_clip_image-6249

由此可见Disruptor的性能远远高于ABQ(=ArrayBlockingQueue)。

【6 吞吐量性能测试】

为了测量延时,我们采用3个阶段的pipeline作为测试场景,为了能够测出系统的最佳状态,我们让吞吐量压力维持在一个合适的水准,这个压力不至于耗尽队列资源。这个压力是通过每插入一个事件就等待1ms的方式来实现的,然后一直这样重复5000万次。为了精确测量延时,我们需要精确考量CPU的时间戳计数器(TSC)。我们采用了那些TSC恒定的CPU来作为测试机器,因为老的CPU为了节省功耗,往往会自动调节TSC。Intel Nehalem之后的CPU都支持恒定的TSC。

我们依然采用ArrayBlockingQueue用来对比。有人可能会问:为什么不用ConcurrentLinkedQueue来做对比呢?ConcurrentLinkedQueue的性能不是更好么?的确是这样,但是由于Disruptor模式的ringbuffer是一个长度固定的队列系统,而ConcurrentLinkedQueue是一个长度没有限制的队列,两者对于长度无限制的队列,生产者如果效率过高,且又无法阻塞,这样会抢占消费者的CPU资源,从而影响最后的测试结果。

Disruptor每一轮(一次完整的流水线)的延时为52纳秒,相比之下ArrayBlockQueue每一轮的延时为32757纳秒。跟踪显示ArrayBlockQueue性能损失主要是由条件变量的加锁/通知引起的。

wps_clip_image-28395

wps_clip_image-16086

【7 结论】

Disruptor向增加吞吐量,降低并发上下文之间切换造成的延时迈出了重要一步,这在许多应用中都是非常重要的考虑。我们的测试显示,与其它线程间交换数据的方法相比,disruptor的性能是最好的。我们相信disruptor应该是所有数据交换方法中最好的。通过关注隔离,通过限制写竞争,通过最小化读竞争,通过代码的cache-friendly,我们创造了一种在线程之间交换数据的高效的方法。

Batch Effect运行消费者能够一次性没有竞争的处理大量的元素,这为高性能系统提供了一个新的特性。对于大多数系统而言,随着吞吐量压力的增加,延时也会呈指数级增加,形成一个类似J的曲线。然而在Disruptor系统中,随着吞吐量压力的增加,延时依然会很平滑,直到内存被耗尽。(关于这一点,我本人有不同的意见,首先平滑吞吐量压力是所有队列系统都具有的特点,这并非disruptor所独有。而且Batch Effect只是一次性取走数据,这里其实有一个概念的混淆,这里衡量延时实际上采用的元素被取走所耗费的时间,在这个指标下一次性读取大量的数据当然会带来好处,但实际上如果你是以元素被处理所耗费的时间作为衡量标准,你会发现一次性读取大量的数据未必有多大受益,因为这些元素依然要一个接一个的处理,读取的数据越多,那么读取的最后一个元素被处理需要等待的时间也就越长,从这方面来看似乎好处有限。但Disruptor本身专注的只是数据交换而已,而非具体业务逻辑,因此用元素读取的延时作为衡量指标也说的过去,只是Disruptor所声明的batch effect带来的优势并不是它独有的,大部分队列系统也都具有)。

我们相信Disruptor为高性能计算树立一个新的标杆,而且能够紧跟CPU和计算机科学中的趋势。

0

阅读 评论 收藏 转载 喜欢 打印举报
前一篇:性能优化
后一篇:Lambda Calculus
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇性能优化
    后一篇 >Lambda Calculus
      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有