无锁编程实现消息交换-高性能并发框架在交易系统中的应用


本期热点Focus 无锁编程实现消息交换—— 高性能并发框架在交易系统中的应用 朱星垠 上海证券交易所 技术开发部,上海 200120 E-mail :xyzhu@sse.com.cn 摘 要 :本文介绍了最近比较流行的并发编程的框架——Disruptor 在大型金融交易系统中的应用。Disruptor 是一个 并发组件,它有众多的优势,其中有一点是能够在无锁的情况下实现消息队列的并发操作,我们将在本文中对其中使 用的数据结构和操作方式做一个探究,并结合交易系统做一下展望。 关键字 :并发编程框架 ;无锁编程;低延迟 1 引言 LMAX是一个典型的高频 ( 事务 ) 交易系统 [1], 很多外汇交易公司用他们的系统。LMAX 这种新的零售 的金融交易平台,它的业务创新—允许任何人在一系 列的金融衍生品上进行交易。这样的一个交易平台需 要极其低的延迟—因为市场变动剧烈,交易必须被保 证快速的处理。这个平台的复杂性随着使用人数的增 加而增加。随着用户数量和交易次数的增加,就需要 有更快的处理速度。LMAX 在一台普通的 PC 服务器上 (8core 32G 内存 ) 就能实现惊人的 600 万 TPS/s 的性 能。而实现这一切的关键,就是开源的并发编程框架— Disruptor。Disruptor 是一个高性能的异步处理框架, 也可以认为是一个观察者模式或者事件 - 监听模式的实 现。许多应用在处理过程中,都需要依赖队列来交换 数据。测试实验显示,当使用普通队列进行数据交互 时,为了确保队列中数据的一致性,需要使用锁对被 操作的数据进行保护。在这种情况下,它的延时,和 IO 对磁盘的操作的延时是一个数量级的,非常慢。而 Disruptor 中引入了 RingBuffer 这一数据结构,很好地 解决了这个问题,在一定程度上,做到了无锁编程。 2 锁是低效的 Disruptor 与传统高性能模型是不同的,LMAX 团 队通过测试发现热门的 Actor 模型在高并发设计有瓶 颈 [2],Disruptor 的 RingBuffer 根 据 多 核 CPU 的 高 速缓存设计特点进行了优化,让每个 CPU 运行一个线 程,多个 CPU 就是多线程并发模式了。传统消息框架 使用先进先出队列,如 JDK 的链表等数据结构实现, RingBuffer 比链表之类数据结构要快,因为没有锁,是 CPU 友好型的。原来我们以为多个线程同时写一个类 的字段会发生争夺,这是多线程基本原理,所以使用 了锁机制,保证这个共用字段 ( 资源 ) 能够某个时刻只 能一个线程写,但是这样做的坏处是 :极大的增加了 延迟的耗时并有可能发生死锁。当线程都在争夺某一 个资源时,操作系统就会来解决这一个纷争。进程争 取资源的过程,就像孩子们在争抢一个玩具,而操作 系统的内核就像一个父亲确定把玩具给谁。这个情形 就类似于 :你想玩变形金刚,但是你妹把它藏了起来。 你爸除了管你俩胡闹,还有更多的事要料理。他洗完 了碗、收回了洗好的衣服才有空管你们。如果你执意 要使用锁的来进行编程,那么耗费的,不仅仅来自于 操作系统用于解决纷争的时间,更有可能的是,操作 系统会优先处理一些其他的进程。 26 27 本期热点 Focus 见表,通过一个简单的实验,我们可以对锁的花费 时间做一个简单的比较。这个实验调用一个函数 :对 一个 64 位的计数器进行自加 5 亿次。对于一个单线程, 没有加锁的情况下,这个测试耗时 300ms。如果你加 一把锁(对于单线程,没有竞争,除了加锁,没有其他 的操作复杂度)这个测试耗时是 10,000ms,差了两个 量级。更令人震惊的是,如果加了一个线程(在逻辑上, 我们认为是一个线程加一把锁的两倍时间)它却耗时 224,000ms。这几乎比不用单线程不用锁的情况慢了将 近 1000 倍。 用的数组位置,可以使用求余的操作计算当前的位置 : sequence mod array length = array index 如果我们去 Google 上搜索一下环形队列或者是环 形数组,我们会发现,普通意义上的环形数组是有一个 指向队列尾部的指针的,而 RingBuffer 则没有。我们 只需要记住它的序列号即可。原因是,我们需要保存 过往的信息,我们并不是主动地删除以前的记录。如图, 这样,当遇到一个应用需要我们重传某一段消息时,我 们可以轻松的完成任务。而确定以前的信息是否能够 被覆盖,则完全取决于外部的业务逻辑,和 RingBuffer 数据结构本身是无关的。 这样的一个数据结构,是可以保证我们提供非常可 靠的消息回滚机制的。当然它还具备其他的一些特性。 首先,它肯定是比链表要来得快,链表是需要遍历,而 它则是 O(1) 时间的访问,毋庸置疑。其次,在操作的 过程中,由于我们是事先开出一块内存申请 RingBuffer 的空间,并且不删除以前的记录,这样,我们不需要 主动用到垃圾回收的机制。 方法 时间(ms) 单线程 300 单线程带锁 10,000 两个线程带锁 224,000 单线程带 CAS 5,700 两个线程带 CAS 30,000 表 1 各种情况下的耗时 3 无锁编程 那 Disruptor 框架,它是如何解决上一节提出的 问 题? 很 简 单 :Disruptor没 有 用 锁 [3]。 当 我 们 对 Disruptor 框架内的这个队列进行研究时,可以发现这 其实是一个真正的单个数据结构 :一个RingBuffer。每 个生产者和消费者都有一个次序计算器,以显示当前缓 冲工作方式 . 每个生产者消费者写入自己次序计数器, 能够读取对方的计数器,生产者能够读取消费者的计 算器确保其在没有锁的情况下是可写的,类似地消费 者也要通过计算器在另外一个消费者完成后确保它一 次只处理一次消息。接下来我们将为对这个数据结构 RingBuffer 进行一个简要的剖析。 3.1 什么是 RingBuffer 如图所示,RingBuffer 就像是一个环形数组,你 使用这个数据结构在不同的线程之间传递数据。同时, RingBuffer 有一个指针,我们也可以把它看成是一个序 列号,它指在了下一个可用的位置,它是不停增加的。 当你从 RingBuffer 填写数据,或者是从中读取数据时, 换个序列号会递增,由于数组是环形的关系,它并会 覆盖环绕以前经过的位置。为了确认当前我们可以使 图 1 Ring Buffer 结构 图 2 无尾指针的 Ring Buffer 28 29 本期热点Focus 你可能会注意到我并没有提及 RingBuffer 中如何 读、写操作的问题。同样,我也只是把 RingBuffer 和 链表在进行比较。接下来,我们将看一下消费者和生产 模型在 RingBuffer 中进行读、写操作的方式,以此和 普通的队列进行一个比较,从而了解为什么 RingBuffer 不需要靠锁机制来保证它的数据一致性。 3.2 如何读数据 多线程通过一个大数组传递消息的方式就是生产 者和消费者的模式。每个消费者是一个个的线程,它 们都希望从数组队列中获得消息。在RingBuffer的 内部实现中,我们可以知道,每个线程通过一个代理 [4],去向 RingBuffer 获取数据,如图所示。我们知道 RingBuffer 中有一个序列号,而每个消费者,也就是每 个线程,则需要去首先获得这个序列号。在图这个示 例中,消费者在处理 7 号位置的消息,它期望获得第 8 个位置的数据。当它希望从 RingBuffer 中读取消息时, 代理会返回 RingBuffer 的序列号,是消费者可以到达 的最大值。 现在,消费者知道,从第 7 号位置到第 10 号位置 都已经成为了可以读的位置。然后,此线程就可以从代 理哪里获取这些个数据了。最后,它会更新自己的指针, 指向最后一个它读取的位置,如图所示。 图 3 消费者从 RingBuffer 中获取序列号 图 4 消费者在 RingBuffer 中获取消息数据 28 29 本期热点 Focus 从 RingBuffer 中的读数据的方式是比较特别的, 取代以往的那种每个消费者不停地询问“我能不能那 下一个数据?现在能拿吗?”,如今,消费者只需要简 单的说一句“当我能拿数据的时候,告诉我”,然后在 某一时刻,它会被告知,它能一下拿多少个数据。我 们知道,消费者只是去读取只写新写的数据,所以在 这一部分,是没有必要加锁的。 3.3 如何写数据 写数据的情况,比起读数据,会有一点点的复杂。 首先要说明的一点是,Disruptor 的 API 在写数据的过 程中,是带有事务概念的。你首先要在 RingBuffer 中 申请一个位置,然后你需要做的是去改变这个位置的 值,最后是提交数据,提交数据的前提是 RingBuffer 的指针,也就是序列号,正好指向了提交的值位置的 后面一位。可能会有人问这样一个 transaction 的过程 是如何保证它的完整性的,难道不用锁吗?确实,在 Disruptor 中,使用了 CAS 操作 [6],保证了这样一个 事务的完整性。所谓的 CAS,是比较(compare)和 交换(swap)的缩写,它是一条原子的 CPU 的指令, 以保证在多线程处理中的数据一致性。其原理为 :在 修改一个数据前,先保存它原始的值,进行修改之后, 再去检查此数值较之原始的值是否发生变化。如果一 致,则说明期间没有其他线程对其进行了操作,可以 替换。如发现变化,则重头再来。CAS 的速度,虽然 比不加锁的情况要慢,但也远远的快于对队列加锁的 情况。见表。 基于生产者和消费者的模型,同样,写数据的线 程被视作为一个生产者的线程 [5]。从生产者的角度看, 它其实只需要去向代理申请一个下一个可写的位置。代 理会返回 RingBuffer 中下一个可写的位置号给生产者。 如图所示,有一个消费者 1,它现在处于 RingBuffer 中最高序列号 10 的位置(图中蓝色标记)。还有一个 消费者 2,它由于其他的一些原因,稍稍落后于消费者 1,它处于 3 的位置。而生产者此时希望写数据的位置, 正好被消费者 2 占了,从生产者的角度,它不知道它 要写的位置被占领了,而它的代理则知道。于是,代 理停在那里做等待,直到消费者 2 移动到其他的位置。 过了一段时间,如图所示,消费者 2 已完成了一 批的读取工作,到了 6 号的位置。代理发现此时,原 来 3 号位置已经没有人占着了,于是生产者拿到了位 置,更新了数值,并进行了提交。我们前面说过,写 数据是一个事务的过程 :申请位置,更新,再提交这 3 个动作组成。RingBuffer 的序列号也由此更新到了 11。 最后,生产者的代理还会去通知消费者的代理,告诉它, “有事发生了!”。这样,消费者 1 又可以去拿到第 11 个位置的数据,而消费者 2,则可以去拿到 7~11 位置 的数据。如图所示。 图 5 生产者申请写位置 30 31 本期热点Focus 在 Disruptor 中,有一点很有趣的时,生产者也 可以进行批量的写入。如图所示,刚刚我们说到,消 费者2在第6号的位置,而Disruptor它知道整个 RingBuffer 的大小,也同样知道在 RingBuffer 中最慢 的一个消费者的位置,则它可以通知生产者,哪一段 区域它是可以进行批量的写入的。 如图8所示,生产者的代理知道 RingBuffer 的当 前指针指在了 11 的位置,并且消费者 2 指在了 6 的位 置,它就可以通知生产者,位置 4,5 是可以安全进行写 入的。 最后我们来看一下有多个生产者进行写数据时 的情况。如图所示。在有多个生产者的情况下,在 RingBuffer 中,我们将会多一个指针,这个个指针不同 于我们前面提到的那个序列号。这个指针指向下一个 可以被申请到的位置。(还记得我们在这一节开头讲过 的,写是一个事务过程,先申请,然后写,最后提交)。 图 6 生产者写新数据 图 7 生产者提交并通知 30 31 本期热点 Focus 图 8 生产者批量获取并写入 申请的时候,我们就需要用到这么一个指针,我们姑 且称之为 next 指针,或者 next 序列号。 让我们来看一下这个过程,首先,生产者1 先 去申请一个序列号。申请前,RingBuffer的序列号 指 向 了 11, 生 产 者 1 申 请 后,RingBuffer 的 next 指 针,指向了 12,并返回。生产者 2 随后申请,同样, RingBuffer 返 回 了 next 序 列 号 13。 但 注 意, 此 时, RingBuffer 的原本的序列号仍然指向 11 的位置。 图 9 多生产者申请写入 现在我们假设,生产者 1 在写入数据时发生了一 些情况,它没有及时的写入并且申请提交。而生产者 2 却很快的完成了这个过程,并且准备提交,并通知了生 产者的代理。在我们之前说的提交过程中,生产者必 须要等到 RingBuffer 的指针(序列号)指向它所提交 的位置的后面一位,才有资格提交。也就是说,如果 生产者 2 要提交它修改的数据 13,RingBuffer 的指针 (序列号)必须要指向 12 的位置。而此时,RingBuffer 32 33 本期热点Focus 的指针却指向 11 的位置。所以生产者 2 的提交过程 不成功,生产者代理必须等待生产者 1 提交成功,并把 RingBuffer 的指针指向 12 后才能完成。这个过程见图 10。 现在,生产者 1 它醒过来了,它提交了申请。由 于当前的 RingBuffer 的指针指向了 11 的位置,生产者 1 符合提交的条件,按照事务的方式,它修改了数值, 并在做了提交,最后把 RingBuffer 的指针加 1,指向 了 12 的位置。更新 RingBuffer 的指针的动作会通知到 生产者的代理,它发现有一个生产者此时在等待,并且 等待的条件也符合要求,所以生产者2 也得以提交数据。 最后,RingBuffer 的指针被更新到了 13,并且由生产 者的代理通知消费者的代理,告诉它们到 13 之前的所 有位置,现在都是可读的。完成了多生产者模式的提交。 如图 11 所示。 图 10 多生产者申请等待 图 11 多生产者提交顺序 32 33 本期热点 Focus 4 应用展望 在上一章中,我们简单地剖析了 Disruptor 中的核 心数据结构 RingBuffer 的意义,以及在多生产者,多 消费者操作过程中,读写的方式。我们知道,在任何 交易系统中,依赖队列来进行数据的交换是一个比较 常见的现象,所以如何使用高性能的数据结构,继承 Disruptor 中 RingBuffer 的思想,可能会是一种提高交 易系统的可行、可尝试的方法之一。另一个使用这种 无锁编程思想的一个原因是方便移植。确实,没有人 可以保证系统永远在某一特定的操作系统上运行,而 带锁的编程,往往又是和操作系统紧密结合的。如果 我们能把一部分的编程从锁中解放出来,确实,将有 可能会方便到以后的开发工作,毕竟锁和信号量的概 念是能以理解的并且难以测试的,我们需要为此花更 多的时间在计算机上,而不是放在我们金融领域的问 题上。 下面我们看一下我们现有交易系统的结构图的一 部分,见图 12。 图中,可以看到有一个环形队列,这里的这个队 列就是普通的环形数组(带有头尾指针的)。这个环形 数组在交易系统中,起到了消息传递的作用。系统中, 从这个消息队列中读取消息的时候,必须使用锁来对 其进行一致性的控制,因为同一个时间,我们有两个 生产者(AM82 进程和 MM52 进程)在不断竞争着往 Order Ring Buffer 中写入数据。在系统的设计中,我 们对产品按 SET 进行了划分,不同类型的订单会被分 发到不同的主机上,由单独这个机器上的两个生产者 进行写处理。所以两个生产者进程现在可以应付,并 且在性能上有所保证。但是如果我们今后有了新业务, 遇上新需求,碰到了一些绕不开的单点问题上(比如期 权业务中的保证金问题,保证金不能按 SET 划分,必 须控制在一台机器上),必须要引入更多的进程进行读 写时,Disruptor 中 RingBuffer 的设计思想和理念,应 该是一种很好的借鉴。 5 总结 已经有那么些年,我们发现并不再期望能够在单个 CPU 上有更快的性能,CPU 也从单核模式逐渐发展到 了多核模式。伴随着这样的发展,对程序员的要求也开 始变得更高,我们需要更多的并发程序。但是这并不简 单,锁、信号量、临界区等这一个一个的概念一直困 扰着我们,并在程序调试的过程中一次次的让我们抓 狂。我们往往把时间放在了多核程序上,而忽略了对 自己领域问题的研究。这显得有那么些别扭,毕竟程 序是为业务服务的。而我们惊喜的发现 Disruptor 仿佛 在这个困顿中找到了一丝的曙光。本文从 Disruptor 的 数据结构 RingBuffer 入手,初步简单的了解,分析了 RingBuffer 的设计及读写机制 :并发控制原理就是顺序 产生序列号 , 然后通过比较序列号实现生产者之间的顺 序依赖。我们期望通过 RingBuffer 的设计思想,对其 设计背后的哲学思想有所领悟,取其精华,为我们所用。 图 12 交易系统架构(部分) 34 35 本期热点Focus 参考文献 [1] Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads. http://disruptor.googlecode.com/files/Disruptor- 1.0.pdf [2] The LMAX Architecture. http://martinfowler.com/ articles/lmax.html [3] Dissecting the Disruptor: Why it’s so fast (part one)-Locks Are Bad. http://mechanitis.blogspot. com/2011/06/dissecting-disruptor-whats-so-special.html [4] Dissecting the Disruptor: How do I read from the RingBuffer. http://mechanitis.blogspot.com/2011/06/ dissecting-disruptor-how-do-i-read-from.html [5] Dissecting the Disruptor: Writing to the RingBuffer. http://mechanitis.blogspot.com/2011/07/dissecting- disruptor-writing-to-ring.html [6] Compare-and-swap http://en.wikipedia.org/wiki/ Compare-and-swap 34 35
还剩8页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf