高性能内存队列 Disruptor
最后更新于
Disruptor 是一个高性能的队列，核心的业务逻辑处理器是在内存中运行的，不仅如此，它还提供了一种编程的框架模型：基于 Disruptor 构建一个生产者多消费者模式，不同参与者之间的通信通过一个有界的内存队列进行传递，非常类似 Golang 语言中的 channel。Disruptor 是由 LMAX 交易所团队开发并开源的，能够在无锁的情况下实现 Queue 的并发操作，基于 Disruptor 开发的交易所系统单线程能支撑每秒 600 万订单。
Disruptor是一个并发编程框架，用于交换和协调作为一系列连续事件的工作。它可以被用来替代通过队列将处理阶段连接在一起的场景。Disruptor 设计的特点是产生的垃圾比队列少得多，并且分离了并发性问题，因此可以采用非锁定算法，从而获得更大的可扩展性和性能。
它的工作原理是有许多阶段，每个阶段都是单线程的，具有本地状态和内存。不存在全局内存，所有的通信都是通过管理的环形缓冲器传递消息/状态来实现的。
几乎任何图形或管道结构都可以通过一个或多个Disruptor模式组成。
Paper 地址：Disruptor Paper
LMAX 的目标是成为世界上最快的交易平台。显然，为了实现这一目标，我们需要做一些特别的事情，以实现我们的 Java 平台的极低延迟和高吞吐量。性能测试表明，使用队列在系统各阶段之间传递数据会带来延迟，因此我们专注于优化这一领域。
Disruptor 是我们研究和测试的结果。我们发现，CPU 级别的缓存缺失(cache miss)和需要内核仲裁的锁(这个是在CPU层面实现的锁机制，比如 CPU 在 BUS 总线上发送一个 Lock 信号或者 MESI 缓存一致性协议)都是非常昂贵的，所以我们创建了一个框架，对它所运行的硬件有 "硬件亲和性"，并且是无锁的。JDK 中的队列实现缺乏了队列和处理阶段的分离，以及多线程之间的竞争都会影响性能。
并发不仅意味着两个或多个任务并行发生，而且意味着它们争夺对资源的访问。争用资源可能是数据库，文件，套接字，甚至是内存中的位置。并发基本关注两件事情：互斥和变更的可见性；互斥是管理竞争资源的更新；变更的可见性是控制被修改的变量何时被其他线程访问到。
如果能避免共享资源的争用，就可以避免掉对互斥的需要；如果能保证任何给定的资源只被一个线程修改，那么就可以解决资源变更的可见性问题。读取和写入操作要求所有的改变都对其他线程可见。然而，只有争先恐后的写操作需要相互排斥的变化。在任何并发环境中，最昂贵的操作是争夺性的写访问。要让多个线程写到同一个资源，需要复杂而昂贵的协调。通常，这是通过采用某种锁定策略来实现的。
Lock 以一种顺序的方式保证了互斥和变更的可见性。锁是非常昂贵的，因为它们在争夺时需要仲裁。这种仲裁是通过向操作系统内核切换上下文来实现的，操作系统内核将暂停在锁上等待的线程，直到它被释放。在这样的上下文切换过程中，以及向操作系统释放控制权的过程中，执行上下文可能会丢失之前缓存的数据和指令，而操作系统可能会决定在它拥有控制权的时候做其他的内部管理任务。这对现代处理器的性能会产生严重的影响。可以采用快速用户模式锁，但是这些锁只有在不争夺的情况下才会有真正的好处。
当更新的目标是一个字时，可以采用一种比使用锁更有效的方法来更新内存。这些替代方法是基于现代处理器中实现的原子或互锁的指令。这些通常被称为CAS（Compare And Swap）操作，例如x86上的 "lock cmpxchg"。CAS操作是一种特殊的机器码指令，它允许内存中的一个字被有条件地设置为一个原子操作。对于 "增加一个计数器的实验"，每个线程可以在一个循环中读取计数器，然后尝试将其原子化地设置为新的增加值。新旧值作为参数提供给这条指令。如果当操作被执行时，计数器的值与提供的预期值一致，那么计数器就会被更新为新的值。另一方面，如果该值不符合预期，CAS操作将失败。这时，试图执行改变的线程就会重试，从该值开始重新读取计数器的增量，如此反复，直到改变成功。这种CAS方法比锁的效率高得多，因为它不需要向内核切换上下文来进行仲裁。然而，CAS操作并不是没有成本的。处理器必须锁定其指令流水线以确保原子性，并采用内存屏障来使其他线程看到这些变化。在Java中，通过使用java.util.concurrent.Atomic* 类，可以进行CAS操作。
如果程序的关键部分比计数器的简单增量更复杂，它可能需要一个使用多个CAS操作的复杂状态机来协调争夺。使用锁来开发并发程序是困难的；使用CAS操作和内存屏障来开发无锁算法则要复杂很多倍，而且很难证明它们是正确的。
理想的算法是只有一个线程拥有对单一资源的所有写入，其他线程读取结果的算法。在多处理器环境中读取结果需要内存屏障，以使在其他处理器上运行的线程看到这些变化。
现代处理器出于性能考虑，在内存和执行单元之间进行指令的失序执行以及数据的失序加载和存储。处理器只需要保证程序逻辑产生相同的结果，无论执行顺序如何。对于单线程程序来说，这不是一个问题。然而，当线程共享状态时，重要的是所有的内存变化都按顺序出现在所需的点上，以使数据交换成功。内存屏障被处理器用来指示代码位置，来说明内存更新的顺序很重要。它们是线程之间实现硬件排序和变化可见性的手段。编译器可以设置免费的软件屏障，以确保编译代码的顺序，这种软件内存屏障是对处理器本身使用的硬件屏障的补充。
现代的 CPU 比内存的速度快的多，为了弥合这一鸿沟，CPU使用了复杂的缓存系统，这实际上是没有链式的快速硬件哈希表。这些高速缓存通过消息传递协议与其他处理器的高速缓存系统保持一致。此外，处理器还有 "存储缓冲区 "来卸载对这些高速缓存的写入，以及 "失效队列"，以便高速缓存一致性协议能够在写入即将发生时快速确认失效信息以提高效率。
这对数据来说意味着，任何数值的最新版本在写入后的任何阶段都可能在一个寄存器、一个存储缓冲区、许多层缓存中的一个，或在主内存中。如果线程要共享这个值，就需要以一种有序的方式使其可见，这可以通过协调交换缓存一致性信息来实现。这些消息的及时产生可以由内存屏障来控制。
读屏障和写屏障是怎么实现的？
读取内存屏障通过在无效队列中为进入其高速缓存的变化标记一个点，来命令执行该指令的CPU的加载指令。这给了它一个一致的世界观，用于在读屏障之前的写操作。
写屏障通过标记存储缓冲区中的一个点来命令执行它的CPU的存储指令，从而通过它的缓冲区将写操作刷新出去。这个屏障向世界提供了一个有序的视图，即在写屏障之前发生了哪些存储操作。
一个完整的内存屏障在执行它的 CPU 上同时对加载和存储进行排序
在现代处理器中使用高速缓存的方式对于成功的高性能运行有着巨大的意义。这样的处理器在处理缓存中的数据和指令时效率极高，但相对而言，当发生缓存缺失时，效率就会大大降低。
我们的硬件并不是以字节或字为单位来移动内存的。为了提高效率，缓存被组织成通常为32-256字节大小的缓存行，最常见的缓存行是64字节。这也是缓存一致性协议运作的粒度水平。这意味着，如果两个变量在同一缓存行中，而它们被不同的线程写入，那么它们就会出现与单个变量相同的写入争夺问题。这是一个被称为 "伪共享 "的概念。为了实现高性能，必须确保独立但同时写入的变量不共享同一个缓存行，这样才能最大限度地减少竞争。
当以可预测的方式访问内存时，CPU能够通过预测下一个可能被访问的内存并在后台将其预取到缓存中来隐藏访问主内存的延时成本。这只有在处理器能够检测到一种访问模式的情况下才行得通，例如以可预测的 "步幅 "访问内存。当对数组的内容进行迭代时，跨度是可预测的，因此内存将被预取到高速缓存中，使访问效率最大化。通常情况下，跨度必须小于2048字节，才能被处理器注意到。然而，像链接列表和树这样的数据结构，其节点在内存中的分布更为广泛，没有可预测的访问步长。内存中缺乏一致的模式限制了系统预取缓存行的能力，导致了主内存访问而效率降低2个数量级以上。
队列通常是使用链表或者数组作为基础数据结构，有界队列在生产中被广泛使用，因为无界队列可能会在生产者快于消费者时把内存撑爆，从而导致服务挂掉，队列应该收到大小的限制，一般是通过根据其大小实现，或者使用数组来实现。
队列的实现倾向于在头部、尾部和大小变量上有写争论。在使用时，由于消费者和生产者之间的步伐不同，队列通常总是接近满或接近空。它们很少在生产和消费的速度均衡的中间地带运行。这种总是满载或空载的倾向导致了高水平的争夺和/或昂贵的缓存一致性。问题是，即使头部和尾部机制使用不同的并发对象（如锁或CAS变量）分开，它们通常也会占用同一个缓存行。
除了在队列上使用单一的大颗粒锁之外，管理生产者对队列头部的声明，消费者对队列尾部的声明，以及中间节点的存储，这些问题使得并发实现的设计非常复杂。在整个队列上的大颗粒锁的 put 和 take 操作很容易实现，但对吞吐量来说是一个重大瓶颈。如果在队列的语义中把并发关注点分开，那么除了单一生产者-单一消费者的实现之外，其他的实现都会变得非常复杂。
在 Java 中，使用队列还有一个问题，因为它们是垃圾的重要来源。首先，对象必须被分配并放在队列中。其次，如果是以链表为基础，必须分配代表链表节点的对象。当不再被引用时，所有这些被分配来支持队列实现的对象都需要被重新回收。
许多类别的问题表明将几个处理阶段连接成一个 Pipeline 是有意义的；这种管道通常有平行的路径，被组织成类似于图的拓扑结构。每个阶段之间的联系通常由队列实现，每个阶段都有自己的线程。
如果依赖关系图能够被表达出来，而不产生把队列放在阶段之间的成本，那就更理想了。
确保任何数据只能由一个线程拥有，以便进行写入访问，从而消除了写入竞争。这种设计被称为 "Disruptor"。Disruptor 为了解决上述所有的问题，试图最大限度地提高内存分配的效率，并以一种有利于缓存的方式运行，以便在现代硬件上发挥最佳效果，它的核心是一个预先分配好的环形缓冲区形式的有界数据结构。数据通过一个或多个生产者添加到环形缓冲区，并由一个或多个消费者处理。
内存预分配 - 主要解决 GC 可能带来的问题（如延迟抖动），更进一步降低老年代 GC 带来的停顿，没有 GC 就不会有那么多问题
环形缓冲区的所有内存都是在启动时预先分配的。环形缓冲区可以存储一个指向条目的数组，也可以存储代表条目的结构数组。Java语言的限制意味着条目是作为对象的指针与环形缓冲区相关联的。这些条目中的每一个通常不是被传递的数据本身，而是它的一个容器。这种预先分配条目的做法消除了支持垃圾收集的语言中的问题，因为这些条目将被重复使用，并在Disruptor实例的持续时间内存在。这些条目的内存是同时分配的，而且很有可能是在主内存中连续布置的，因此支持缓存跨步。
在像Java这样的管理运行环境中开发低延迟系统时，垃圾收集可能是个问题。分配的内存越多，对垃圾收集器的负担就越大。当对象的寿命很短或者实际上是不死的时候，垃圾收集器的工作效果最好。预先分配环形缓冲区中的条目意味着，就垃圾收集器而言，它是不朽的，所以代表了很小的负担。
基于队列的系统在高负载下会导致处理速度的降低，进而导致被分配的对象存活的时间比预期的要长，因此有可能这些对象会被复制到老年代；这样会导致，对象必须要在不同代之间进行复制，导致了延迟抖动；另一方面导致这些对象必须在老年代被收集，从而增加了 Stop the world 的可能性，当内存空间被压缩时，就会出现暂停，可能会导致每 GB 数据持续数秒的停顿。
关注点分离 - 将队列中条目的存储、生产者位置的争用、消费者位置的争用等做分离，减少争用的可能性
当在使用垃圾收集的语言中设计一个金融交易所时，过多的内存分配可能是有问题的。所以，正如我们所描述的，链表支持的队列不是一个好的方法。如果处理阶段之间的数据交换的整个存储可以预先分配，那么垃圾收集就会降到最低。此外，如果这种分配可以在一个统一的块中进行，那么该数据的遍历将以一种对现代处理器采用的缓存策略非常友好的方式进行。符合这一要求的数据结构是一个预先填充了所有槽位的数组。在创建环形缓冲区时，Disruptor利用抽象的工厂模式来预先分配条目。当一个条目被索取时，生产者可以将其数据复制到预先分配的结构中。
在大多数处理器上，序列号的余数计算有很高的成本，它决定了环中的插槽。这个成本可以通过使环的大小为2的幂而大大降低。一个 buffer size - 1 的位掩码可以用来有效地执行剩余运算。
有界队列在队列的头部和尾部存在争夺。环形缓冲区的数据结构不受这种争论和并发原语的影响，因为这些问题已经被划分为生产者和消费者屏障，必须通过这些屏障来访问环形缓冲区。这些障碍的逻辑描述如下：在 Disruptor 的大多数常见使用中，通常只有一个生产者。典型的生产者是文件阅读器或网络监听器。在只有一个生产者的情况下，在序列/条目分配上没有竞争。在有多个生产者的使用情况下，生产者会相互竞争，以索取环形缓冲区中的下一个条目。对下一个可用条目的争夺可以通过对该槽的序列号进行简单的CAS操作来管理。
一旦生产者将相关数据复制到声称的条目中，它就可以通过提交序列将其公开给消费者。这可以在没有CAS的情况下，通过一个简单的忙碌旋转来完成，直到其他生产者在他们自己的提交中达到这个序列。然后，这个生产者可以推进游标，表示下一个可供消费的条目。生产者可以在写到环形缓冲区之前，通过跟踪消费者的序列作为一个简单的读操作来避免 wrapping ring。
消费者在读取条目之前，要等待一个序列在环形缓冲区中变得可用。在等待时可以采用各种策略。如果CPU资源很宝贵，他们可以在生产者发出信号的锁内等待一个条件变量。这显然是一个争论点，只有在CPU资源比延迟或吞吐量更重要时才会使用。消费者也可以循环检查代表环形缓冲区中当前可用序列的游标。这可以通过平衡CPU资源和延迟，在有或没有线程让出的情况下进行。如果我们不使用锁和条件变量，就会打破生产者和消费者之间的争夺性依赖，这样的扩展性非常好。无锁的多生产者--多消费者队列确实存在，但它们需要对头、尾、大小计数器进行多次CAS操作。Disruptor不会遭受这种CAS争用。
序列 - 以一种没有竞争的方式来协调生产者和消费者，并以此可以构建复杂的依赖关系
序列是Disruptor中如何管理并发的核心概念，每个生产者和消费者在如何与环形缓冲区交互时都有一个严格的序列概念。生产者在索取环中的一个条目时，按顺序索取下一个槽。在只有一个生产者的情况下，下一个空位的序列可以是一个简单的计数器，在多个生产者的情况下，可以是一个使用CAS操作更新的原子计数器。一旦一个序列值被认领，环形缓冲区中的这个条目就可以被认领的生产者写入。当生产者完成更新该条目时，它可以通过更新一个单独的计数器来提交更改，该计数器代表了消费者可用的最新条目的环形缓冲器上的游标。环形缓冲区的游标可以由生产者使用内存屏障在繁忙的旋转中进行读写，而不需要CAS操作。
消费者通过使用内存屏障来读取游标，等待一个给定的序列变得可用。一旦游标被更新，内存屏障就会确保环形缓冲区中的条目的变化对等待游标前进的消费者是可见的。
每个消费者都有自己的序列，当他们处理环形缓冲区的条目时，他们会更新这些序列。这些消费者序列允许生产者跟踪消费者，以防止环的包裹。消费者序列还允许消费者以一种有序的方式协调对同一条目的工作。
在只有一个生产者的情况下，无论消费者图的复杂性如何，都不需要锁或CAS操作。整个并发协调可以通过讨论的序列上的内存障碍来实现。
批量操作 - 可以做到批量消费，这样更利于吞吐量和平滑延迟
当消费者在环形缓冲区中等待一个正在前进的游标序列时，出现了一个有趣的机会，这在队列中是不可能的。如果消费者发现环形缓冲器中的游标自上次检查以来已经前进了若干步，那么它可以在不涉及并发机制的情况下处理该序列。这导致落后的消费者在生产者突飞猛进时迅速重新跟上生产者的步伐，从而平衡了系统。这种类型的批处理增加了吞吐量，同时减少和平滑了延迟。根据我们的观察，这种效应导致延迟时间接近恒定，而不考虑负载，直到内存子系统饱和，然后曲线是线性的，遵循 Little 定律。这与我们在队列中观察到的随着负载增加而产生的延迟的 "J "曲线效应非常不同。
依赖图 - 解决复杂关系的依赖问题，减少使用 queue 的数量，从而降低延迟和增加吞吐量
队列代表生产者和消费者之间简单的一步流水线依赖关系。如果消费者形成一个链状或图状的依赖结构，那么在图的每个阶段之间都需要队列。这在依赖阶段的图中多次产生了队列的固定成本。在设计LMAX金融交易所时，我们的分析表明，采取基于队列的方法会导致排队成本在处理交易的总执行成本中占主导地位。
由于生产者和消费者的关注点是用Disruptor模式分开的，因此有可能在核心部分只使用一个环形缓冲器来表示消费者之间复杂的依赖关系图。这使得执行的固定成本大大降低，从而在减少延迟的同时提高了吞吐量。
一个单一的环形缓冲器可以用来存储具有复杂结构的条目，代表整个工作流程的凝聚力。在设计这种结构时必须注意，以便独立的消费者所写的状态不会导致错误的共享缓存行。
LMAX 是一个面向全球的交易所，而交易所对延迟是很敏感的，因为订单之间的撮合要非常快，才不至于影响后面订单的撮合，也就是说在高并发情况下，交易所要尽可能低延迟的提高成交数量。据开源 Disruptor 的团队介绍它每秒可以处理千万级以上的消息，并且消息的平均延迟在 50 纳秒（很牛的性能数据）。之所以有这么高的性能，Disruptor 的团队探索了很多影响性能的因素，最终选择了：
Cache line 与硬件友好性设计，避免了伪共享，(Disruptor 是如何来避免伪共享的 ?)
内存预先分配，降低运行时的 GC，使用了 RingBuffer 这个数据结构，空间是预先分配好的且运行时不需要回收
缓存友好性，利用 RingBuffer 环形数组，尽可能提高 CPU 的缓存命中率
使用 CPU 级别的原子操作 CAS，运用无锁算法来提高并发操作的性能，CAS 的无锁操作比内核级别的 Lock 代价要小很多
模式和框架上的创新，摒弃了传统的并发队列的做法，使用 producer sequencing 和 consumer sequencing, 并且 consumer 之间可以形成 dependency graph
没有竞争的数据结构和工作流
非常快速的消息传递
让你体验真正的并行
sequencer.next() 申请 event 被放置的位置（每个 RingBuffer 会关联一个 sequencer），申请的方式是 Spin + CAS, 并 cache sequence 和解决 wrap point 的问题，申请位置的逻辑涉及到空间不足的问题，因为消费太慢，生产太快会引发这个问题，在 next() 实现中会考虑这种情况，如果空间不足就会阻塞生产者线程
执行 translator.translateTo(...), 这个是由用户自定义的，用来 get(sequence) 后，对这个自定义的事件进行修改 ，因为 RingBuffer 里的对象是预先分配好的，所以需要用 translate 对时间做更新填充，在申请位置时已经保证了只有一个线程会操作特定位置的对象，所以这个操作是安全的
执行 publish, 让 sequence 位置的事件可用
可见，整个流程就是申请位置成功后，更新事件的内容，最后让这个位置的事件可用，有点两阶段提交的思想，先 prepare, 然后 commit；此外，在 publish 时，如果申请不到位置，会被阻塞，如果使用的是 tryPublish 会返回 false。
其实 Disruptor 类不是必须要使用的，只是利用它可以很方便的利用 Disruptor 这个框架进行开发，其中 RingBuffer 是整个核心的部分，Sequencer/SequenceBarrier/EventProcessor/WaitStrategy 等都是核心的组成部分；而 Event 和 EventHandler 的是需要我们根据业务自己去实现的部分，从实现来看，Disruptor 的整体实现还是非常不错的，类和功能的划分职责清晰，也能提供很好的编程接口，对于内部的复杂实现也做了很好的隐藏，同时又预留了不错的扩展性，比如可以定制 WaitStrategy, 可以实现自己的 EventProcessor, 也可以基于 Disruptor 去扩展功能。很多地方都体现了面向抽象编程，面向接口而非实现。
Disruptor 经典的应用场景是生产消费模型，JUC 里面也有很多这种队列，但是这些队列大多是基于条件阻塞方式的，性能还不够优秀；
而 Disruptor 通过以下设计来解决队列速度慢的问题：
RingBuffer 数据结构
为了避免垃圾回收，采用数组而非链表。同时，数组对处理器的缓存机制更加友好。
元素位置定位
数组长度 2^n，通过位运算，加快定位的速度。下标采取递增的形式。不用担心 index 溢出的问题。index是 long 类型，即使 100 万 QPS 的处理速度，也需要 30 万年才能用完
无锁设计
每个生产者或者消费者线程，会先申请可以操作的元素在数组中的位置，申请到之后，直接在该位置写入或者读取数据
优先考虑遵循 Single Writer Principle (单一写入者原则)
Disruptor 的调优方向有：单写入者多写入者的选择、等待策略的选择等
根据单一写入者原则，在保证只有一个 Producer 线程写入时，可能会获得额外的性能提升，通过性能测试结果观察，性能差距还是很明显的。
等待策略，当 RingBuffer 满时，默认的策略是阻塞等待。内部 BlockingWaitStrategy 使用典型的锁和条件变量来处理线程唤醒；其他的等待策略还有：SleepingWaitStrategy, YieldingWaitStrategy, BusySpinWaitStrategy等，不同场景下对等待策略的要求是不一样的
BlockingWaitStrategy 是最常使用的策略，它利用锁和等待-通知机制的方式来实现，所以她在 CPU 使用方面是最小的，但是它需要多线程之间的通信，所以可能也是最慢的（原因可能是需要唤醒，然后竞争，依赖线程调度，还有可能竞争失败，重新竞争）
SleepingWaitStrategy 这个策略是在 while loop 中 sleep(1), 在 Linux 系统中这会让线程大概睡眠 60 微秒，它的好处是，生产线程不需要采取任何行动，只需要增加适当的计数器，并且不需要信号条件变量的成本。然而，在生产者和消费者线程之间移动事件的平均延迟会更高。在不需要低延迟，但希望对生产线程有低影响的情况下，它的效果最好。一个常见的用例是用于异步日志。
YieldingWaitStrategy 可用于低延迟系统，在该系统中可以选择燃烧 CPU 周期，以改善延迟。YieldingWaitStrategy将忙于旋转，等待序列增量到适当的值。在循环的主体中，Thread.yield()将被调用，允许其他排队的线程运行。当需要非常高的性能，并且事件处理程序线程的数量少于逻辑核心的总数时，例如，你启用了超线程，这是推荐的等待策略。它比 BusySpin 的方式更容易放弃 CPU
BusySpinWaitStrategy 是性能最高的等待策略，但对部署环境的限制也最高。只有当事件处理程序线程的数量小于物理核心数量时，才应使用这种等待策略。例如，超线程应被禁用。
The LAMX Architecture by Martin Fowler, 中文版翻译
Introduction to the Disruptor
