【交易技术前沿】无锁编程实现消息交换：高性能并发框架

xman

朱星垠


　　上海证券交易所 技术开发部，上海 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友好型的。原来我们以为多个线程同时写一个类的字段会发生争夺，这是多线程基本原理，所以使用了锁机制，保证这个共用字段(资源)能够某个时刻只能一个线程写，但是这样做的坏处是：极大的增加了延迟的耗时并有可能发生死锁。当线程都在争夺某一个资源时，操作系统就会来解决这一个纷争。进程争取资源的过程，就像孩子们在争抢一个玩具，而操作系统的内核就像一个父亲确定把玩具给谁。这个情形就类似于：你想玩变形金刚，但是你妹把它藏了起来。你爸除了管你俩胡闹，还有更多的事要料理。他洗完了碗、收回了洗好的衣服才有空管你们。如果你执意要使用锁的来进行编程，那么耗费的，不仅仅来自于操作系统用于解决纷争的时间，更有可能的是，操作系统会优先处理一些其他的进程。


　　见表，通过一个简单的实验，我们可以对锁的花费时间做一个简单的比较。这个实验调用一个函数：对一个64位的计数器进行自加5亿次。对于一个单线程，没有加锁的情况下，这个测试耗时300ms。如果你加一把锁（对于单线程，没有竞争，除了加锁，没有其他的操作复杂度）这个测试耗时是10,000ms，差了两个量级。更令人震惊的是，如果加了一个线程（在逻辑上，我们认为是一个线程加一把锁的两倍时间）它却耗时224,000ms。这几乎比不用单线程不用锁的情况慢了将近1000倍。


方法
时间（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填写数据，或者是从中读取数据时，换个序列号会递增，由于数组是环形的关系，它并会覆盖环绕以前经过的位置。为了确认当前我们可以使用的数组位置，可以使用求余的操作计算当前的位置：sequence mod array length = array index


　　如果我们去Google上搜索一下环形队列或者是环形数组，我们会发现，普通意义上的环形数组是有一个指向队列尾部的指针的，而RingBuffer则没有。我们只需要记住它的序列号即可。原因是，我们需要保存过往的信息，我们并不是主动地删除以前的记录。如图，这样，当遇到一个应用需要我们重传某一段消息时，我们可以轻松的完成任务。而确定以前的信息是否能够被覆盖，则完全取决于外部的业务逻辑，和RingBuffer数据结构本身是无关的。


　　这样的数据结构，是可以保证我们提供非常可靠的消息回滚机制的。当然它还具备其他的一些特性。首先，它肯定是比链表要来得快，链表是需要遍历，而它则是O(1)时间的访问，毋庸置疑。其次，在操作的过程中，由于我们是事先开出一块内存申请RingBuffer的空间，并且不删除以前的记录，这样，我们不需要主动用到垃圾回收的机制。



　　你可能会注意到我并没有提及RingBuffer中如何读、写操作的问题。同样，我也只是把RingBuffer和链表在进行比较。接下来，我们将看一下消费者和生产模型在RingBuffer中进行读、写操作的方式，以此和普通的队列进行一个比较，从而了解为什么RingBuffer不需要靠锁机制来保证它的数据一致性。


　　3.2 如何读数据


　　多线程通过一个大数组传递消息的方式就是生产者和消费者的模式。每个消费者是一个个的线程，它们都希望从数组队列中获得消息。在RingBuffer的内部实现中，我们可以知道，每个线程通过一个代理[4]，去向RingBuffer获取数据，如图所示。我们知道RingBuffer中有一个序列号，而每个消费者，也就是每个线程，则需要去首先获得这个序列号。在图这个示例中，消费者在处理7号位置的消息，它期望获得第8个位置的数据。当它希望从RingBuffer中读取消息时，代理会返回RingBuffer的序列号，是消费者可以到达的最大值。


　　现在，消费者知道，从第7号位置到第10号位置都已经成为了可以读的位置。然后，此线程就可以从代理哪里获取这些个数据了。最后，它会更新自己的指针，指向最后一个它读取的位置，如图所示。


　　从RingBuffer中的读数据的方式是比较特别的，取代以往的那种每个消费者不停地询问“我能不能那下一个数据？现在能拿吗？”，如今，消费者只需要简单的说一句“当我能拿数据的时候，告诉我”，然后在某一时刻，它会被告知，它能一下拿多少个数据。我们知道，消费者只是去读取只写新写的数据，所以在这一部分，是没有必要加锁的。



　　3.3 如何写数据


　　写数据的情况，比起读数据，会有一点点的复杂。首先要说明的一点是，Disruptor的API在写数据的过程中，是带有事务概念的。你首先要在RingBuffer中申请一个位置，然后你需要做的是去改变这个位置的值，最后是提交数据，提交数据的前提是RingBuffer的指针，也就是序列号，正好指向了提交的值位置的后面一位。可能会有人问这样一个transaction的过程是如何保证它的完整性的，难道不用锁吗？确实，在Disruptor中，使用了CAS操作[6]，保证了这样一个事务的完整性。所谓的CAS，是比较（compare）和交换（swap）的缩写，它是一条原子的CPU的指令，以保证在多线程处理中的数据一致性。其原理为：在修改一个数据前，先保存它原始的值，进行修改之后，再去检查此数值较之原始的值是否发生变化。如果一致，则说明期间没有其他线程对其进行了操作，可以替换。如发现变化，则重头再来。CAS的速度，虽然比不加锁的情况要慢，但也远远的快于对队列加锁的情况。


　　基于生产者和消费者的模型，同样，写数据的线程被视作为一个生产者的线程。从生产者的角度看，它其实只需要去向代理申请一个下一个可写的位置。代理会返回RingBuffer中下一个可写的位置号给生产者。如图所示，有一个消费者1，它现在处于RingBuffer中最高序列号10的位置（图中蓝色标记）。还有一个消费者2，它由于其他的一些原因，稍稍落后于消费者1，它处于3的位置。而生产者此时希望写数据的位置，正好被消费者2占了，从生产者的角度，它不知道它要写的位置被占领了，而它的代理则知道。于是，代理停在那里做等待，直到消费者2移动到其他的位置。


　　过了一段时间，如图所示，消费者2已完成了一批的读取工作，到了6号的位置。代理发现此时，原来3号位置已经没有人占着了，于是生产者拿到了位置，更新了数值，并进行了提交。我们前面说过，写数据是一个事务的过程：申请位置，更新，再提交这3个动作组成。RingBuffer的序列号也由此更新到了11。最后，生产者的代理还会去通知消费者的代理，告诉它，“有事发生了！”。这样，消费者1又可以去拿到第11个位置的数据，而消费者2，则可以去拿到7~11位置的数据。如图所示。



　　在Disruptor中，有一点很有趣的是，生产者也可以进行批量的写入。如图所示，刚刚我们说到，消费者2在第6号的位置，而Disruptor它知道整个RingBuffer的大小，也同样知道在RingBuffer中最慢的一个消费者的位置，则它可以通知生产者，哪一段区域它是可以进行批量的写入的。



　　如上图所示，生产者的代理知道RingBuffer的当前指针指在了11的位置，并且消费者2指在了6的位置，它就可以通知生产者，位置4,5是可以安全进行写入的。


　　最后我们来看一下有多个生产者进行写数据时的情况。如图所示。在有多个生产者的情况下，在RingBuffer中，我们将会多一个指针，这个个指针不同于我们前面提到的那个序列号。这个指针指向下一个可以被申请到的位置。（还记得我们在这一节开头讲过的，写是一个事务过程，先申请，然后写，最后提交）申请的时候，我们就需要用到这么一个指针，我们姑且称之为next指针，或者next序列号。



　　让我们来看一下这个过程，首先，生产者1先去申请一个序列号。申请前，RingBuffer的序列号指向了11，生产者1申请后，RingBuffer的next指针，指向了12，并返回。生产者2随后申请，同样，RingBuffer返回了next序列号13。但注意，此时，RingBuffer的原本的序列号仍然指向11的位置。


　　现在我们假设，生产者1在写入数据时发生了一些情况，它没有及时的写入并且申请提交。而生产者2却很快的完成了这个过程，并且准备提交，并通知了生产者的代理。在我们之前说的提交过程中，生产者必须要等到RingBuffer的指针（序列号）指向它所提交的位置的后面一位，才有资格提交。也就是说，如果生产者2要提交它修改的数据13，RingBuffer的指针（序列号）必须要指向12的位置。而此时，RingBuffer的指针却指向11的位置。所以生产者2的提交过程不成功，生产者代理必须等待生产者1提交成功，并把RingBuffer的指针指向12后才能完成。这个过程见下图。


　　现在，生产者1它醒过来了，它提交了申请。由于当前的RingBuffer的指针指向了11的位置，生产者1符合提交的条件，按照事务的方式，它修改了数值，并在做了提交，最后把RingBuffer的指针加1，指向了12的位置。更新RingBuffer的指针的动作会通知到生产者的代理，它发现有一个生产者此时在等待，并且等待的条件也符合要求，所以生产者2也得以提交数据。最后，RingBuffer的指针被更新到了13，并且由生产者的代理通知消费者的代理，告诉它们到13之前的所有位置，现在都是可读的。完成了多生产者模式的提交。如图所示。


　　4 应用展望


　　在上一章中，我们简单地剖析了Disruptor中的核心数据结构RingBuffer的意义，以及在多生产者，多消费者操作过程中，读写的方式。我们知道，在任何交易系统中，依赖队列来进行数据的交换是一个比较常见的现象，所以如何使用高性能的数据结构，继承Disruptor中RingBuffer的思想，可能会是一种提高交易系统的可行、可尝试的方法之一。另一个使用这种无锁编程思想的一个原因是方便移植。确实，没有人可以保证系统永远在某一特定的操作系统上运行，而带锁的编程，往往又是和操作系统紧密结合的。如果我们能把一部分的编程从锁中解放出来，确实，将有可能会方便到以后的开发工作，毕竟锁和信号量的概念是能以理解的并且难以测试的，我们需要为此花更多的时间在计算机上，而不是放在我们金融领域的问题上。


　　下面我们看一下我们现有交易系统的结构图的一部分，见图。


　　图中，可以看到有一个环形队列，这里的这个队列就是普通的环形数组（带有头尾指针的）。这个环形数组在交易系统中，起到了消息传递的作用。系统中，从这个消息队列中读取消息的时候，必须使用锁来对其进行一致性的控制，因为同一个时间，我们有两个生产者（AM82进程和MM52进程）在不断竞争着往Order Ring Buffer中写入数据。在系统的设计中，我们对产品按SET进行了划分，不同类型的订单会被分发到不同的主机上，由单独这个机器上的两个生产者进行写处理。所以两个生产者进程现在可以应付，并且在性能上有所保证。但是如果我们今后有了新业务，遇上新需求，碰到了一些绕不开的单点问题上（比如期权业务中的保证金问题，保证金不能按SET划分，必须控制在一台机器上），必须要引入更多的进程进行读写时，Disruptor中RingBuffer的设计思想和理念，应该是一种很好的借鉴。


　　5 总结


　　已经有那么些年，我们发现并不再期望能够在单个CPU上有更快的性能，CPU也从单核模式逐渐发展到了多核模式。伴随着这样的发展，对程序员的要求也开始变得更高，我们需要更多的并发程序。但是这并不简单，锁、信号量、临界区等这一个一个的概念一直困扰着我们，并在程序调试的过程中一次次的让我们抓狂。我们往往把时间放在了多核程序上，而忽略了对自己领域问题的研究。这显得有那么些别扭，毕竟程序是为业务服务的。而我们惊喜的发现Disruptor仿佛在这个困顿中找到了一丝的曙光。本文从Disruptor的数据结构RingBuffer入手，初步简单的了解，分析了RingBuffer的设计及读写机制：并发控制原理就是顺序产生序列号, 然后通过比较序列号实现生产者之间的顺序依赖。我们期望通过RingBuffer的设计思想，对其设计背后的哲学思想有所领悟，取其精华，为我们所用。


　　    　　　　　　　　　　　　　　　　　　　　　　原文作者：朱星垠　　来源：本文选自《交易技术前沿》第八期