我是 Andy.Qin，一个想创造哆啦 A 梦的 Maker，更多好文章能够到我的博客：qin.news
介绍
Disruptor 是英国外汇交易公司 LMAX 开发的一个高功能行列，研发的初衷是处理内存行列的推迟问题（在功能测验中发现居然与 I/O 操作处于同样的数量级）。根据Disruptor 开发的体系单线程能支撑每秒 600 万订单，2010 年在 QCon 演讲后，获得了业界重视。2011 年，企业应用软件专家 Martin Fowler 专门编撰长文介绍。同年它还获得了 Oracle 官方的 Duke 大奖。
本文主要参考它 2011 年的论文 《LMAX Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads》还结合了美团技术团队对它剖析的文章。论文中文翻译参考了肥兔子爱豆畜子翻译的中文版。
这里所说的行列是体系内部的内存行列，而不是Kafka这样的分布式行列。
许多应用程序依托行列在处理阶段之间交流数据。咱们的功能测验标明，当以这种方法运用行列时，其推迟本钱与磁盘（根据RAID或SSD的磁盘体系）的IO操作本钱处于同一数量级都很慢。假如在一个端到端的操作中有多个行列，这将使整个推迟添加数百微秒。
测验标明，运用 Disruptor 的三阶段流水线的均匀推迟比根据行列的同等方法低 3 个数量级。此外，在相同的装备下，Disruptor 处理的吞吐量约为 8 倍。
并发问题
在本文以及在一般的计算机科学理论中，并发不只意味着两个以上使命一起并行产生，而且意味着它们在拜访资源时相互竞赛。争用的资源可所以数据库、文件、socket，甚至是内存中的一个方位。
代码的并发履行触及两件事：互斥和内存可见性。互斥是关于怎么办理保证某些资源的独占式运用。内存可见性是关于操控内存更改何时对其他线程可见。假如你能够避免多线程竞赛的去更新同享资源，那么就能够避免互斥。假如您的算法能够保证任何给定的资源只被一个线程修正，那么互斥是不必要的。读写操作要求一切更改对其他线程可见。可是，只有争用的写操作需要对更改进行互斥。
在任何并发环境中，最贵重的操作是争用写拜访。要让多个线程写入同一资源，需要杂乱而贵重的和谐。一般，这是经过选用某种锁策略来完结的。
可是锁的开销是非常大的，在论文中规划了一个试验：
- 这个测验程序调用了一个函数，该函数会对一个 64 位的计数器循环自增 5 亿次。
- 机器环境：2.4G 6 核
- 运算： 64 位的计数器累加 5 亿次
单线程状况下，不加锁的功能 > CAS 操作的功能 > 加锁的功能。
在多线程状况下，为了保证线程安全，有必要运用 CAS 或锁，这种状况下，CAS 的功能超越锁的功能，前者大约是后者的 8 倍。
保证线程安全一般运用锁或许原子变量。
采取加锁的方法，默许线程会抵触，拜访数据时，先加上锁再拜访，拜访之后再解锁。经过锁界定一个临界区，一起只有一个线程进入。
原子变量能够保证原子性的操作，意思是某个使命在履行进程中，要么悉数成功，要么悉数失利回滚，恢复到履行之前的初态，不存在初态和成功之间的中心状况。例如 CAS 操作，要么比较并交流成功，要么比较并交流失利。由 CPU 保证原子性。
经过原子变量能够完结线程安全。履行某个使命的时分，先假定不会有抵触，若不产生抵触，则直接履行成功；当产生抵触的时分，则履行失利，回滚再从头操作，直到不产生抵触。
CAS 操作是一种特别的机器代码指令，它答应将内存中的字有条件地设置为原子操作。比方关于前面的“递增计数器试验”比如，每个线程都能够在一个循环中自旋，读取计数器，然后尝试以原子方法将其设置为新的递增值。
如图所示，Thread1 和 Thread2 都要把 Entry 加 1。若不加锁，也不运用 CAS，有或许 Thread1 取到了myValue=1，Thread2 也取到了 myValue=1，然后相加，Entry 中的 value 值为 2。这与预期不相符，咱们预期的是 Entry 的值经过两次相加后等于3。
CAS 会先把 Entry 现在的 value 跟线程最初读出的值相比较，若相同，则赋值；若不相同，则赋值履行失利。一般会经过 while/for 循环来从头履行，直到赋值成功。CAS无需线程进行上下文切换到内核态去履行，在用户态履行了 CPU 的原语指令 cmpxchg，CAS 相当于在用户态代码里边刺进了一个 cmpxchg 指令，这样 CPU 一向在用户态履行，履行到 cmpxchg 指令就开端履行内核态内存空间的操作体系的代码。履行指令要比上下文切换的开销要小，所以 CAS 要比重量级互斥锁功能要高。（用户态和内核态没有切换）
假如程序的关键部分比计数器的简单增量更杂乱，则或许需要运用多个CAS操作的杂乱状况机来编列争用。运用锁开发并发程序是困难的；而运用 CAS 操作和内存屏障开发无锁算法要愈加杂乱多倍，而且难于测验和证明正确性。
内存屏障和缓存问题
出于提升功能的原因，现代处理器履行指令、以及内存和履行单元之间数据的加载和存储都是不保证次序的。不论实践的履行次序怎么，处理器只需保证与程序逻辑的次序产生相同的成果即可。这在单线程的程序中不是一个问题。可是，当线程同享状况时，为了保证数据交流的成功与正确，在需要的时分、内存的改变能够以正确的次序显式是非常重要的。处理器运用内存屏障来指示内存更新次序很重要的代码部分。它们是在线程之间完结硬件排序和更改可见性的方法。
内存屏障（英语：Memory barrier），也称内存栅栏，内存栅障，屏障指令等，是一类同步屏障指令，它使得 CPU 或编译器在对内存进行操作的时分, 严厉按照一定的次序来履行, 也就是说在内存屏障之前的指令和之后的指令不会由于体系优化等原因此导致乱序。
大多数处理器提供了内存屏障指令:
- 完全内存屏障(full memory barrier)保证了早于屏障的内存读写操作的成果提交到内存之后，再履行晚于屏障的读写操作。
- 内存读屏障(read memory barrier)仅保证了内存读操作；
- 内存写屏障(write memory barrier)仅保证了内存写操作。
现代的 CPU 现在比当前一代的内存体系快得多。为了弥合这一距离，CPU 运用杂乱的高速缓存体系，这些体系是有用的快速硬件哈希表，无需链接。这些缓存经过音讯传递协议与其他处理器缓存体系保持一致。此外，处理器还具有“存储缓冲区”（store buffer/load buffer，比 L1 缓存更接近 CPU，跟寄存器同一个等级，用来当作 CPU 与高速缓存之间的缓冲。究竟高速缓存由于一致性的问题也会堵塞）来缓冲对这些缓存的写入，以及作为“失效行列”，以便缓存一致性协议能够在行将产生写入时快速承认失效音讯，以进步效率。
这对数据意味着，任何值的最新版本在被写入后的任何阶段都能够位于寄存器、存储缓冲区、L1/L2/L3 缓存之一或主内存中。假如线程要同享此值，则需要以有序的方法使其可见，这是经过和谐缓存一致性音讯的交流来完结的。这些信息的及时产生能够经过内存屏障来操控。
L1、L2、L3 别离表明一级缓存、二级缓存、三级缓存，越接近 CPU 的缓存，速度越快，容量也越小。所以 L1 缓存很小但很快，而且紧靠着在运用它的 CPU 内核；L2 大一些，也慢一些，而且依然只能被一个单独的 CPU 核运用；L3 更大、更慢，而且被单个插槽上的一切 CPU 核同享；最后是主存，由悉数插槽上的一切 CPU 核同享。
当 CPU 履行运算的时分，它先去 L1 查找所需的数据、再去 L2、然后是 L3，假如最后这些缓存中都没有，所需的数据就要去主内存拿。走得越远，运算耗费的时间就越长。所以假如你在做一些很频频的事，你要尽量保证数据在 L1 缓存中。
别的，线程之间同享一份数据的时分，需要一个线程把数据写回内存，而另一个线程拜访内存中相应的数据。
假如你用一种能被猜测的方法拜访内存的话，CPU 能够猜测下个或许拜访的值从内存先缓存到缓存中，来降低下次拜访的推迟。可是假如是一些非次序的、步长无法猜测的结构，让 CPU 只能拜访内存，功能上与拜访缓存差许多。所以为了有用运用 CPU 高速缓存的特性，咱们应当尽量运用次序存储结构。
行列的问题
行列一般运用链表或数组作为元素的底层存储。假如答应内存中的行列是无界的，那么关于许多类的问题，它能够不受束缚地增长，直到耗尽内存而到达灾难性的成果，当出产者超越顾客时就会产生这种状况。无界行列在能够在出产者能够保证不超越顾客的体系中运用，由于内存是一种宝贵的资源，可是假如这种假定不成立，而行列增长没有限制，那么总是有风险的。为了避免这种灾难性的成果，行列的巨细一般要受到限制（有界）。要使行列保持有界，就需要对其底层选择数组结构或主动盯梢其巨细。
行列的完结往往要在 head、tail 和 size 变量上有写争用。在运用时，由于顾客和出产者之间的速度差异，行列一般总是接近于满或接近于空。它们很少在出产和消费速率均衡的中心地带运作。这种总是满的或总是空的倾向会导致高等级的争用、和/或贵重的缓存一致性。问题在于，即便 head 和 tail 运用不同的并发对象（如锁或CAS变量）来进行读写锁别离，它们一般也占用相同的 cacheline。
办理出产者请求行列的 head，顾客请求行列的 tail，以及中心节点的存储，这些问题使得并发完结的规划非常杂乱，除了在行列上运用一个粗粒度的锁之外，还难以办理。关于 put 和 take 操作，运用整个行列上的粗粒度锁完结起来很简单，但对吞吐量来说是一个很大的瓶颈。假如并发重视点在行列的语义中被别离开来，那么关于除单个出产者-单个顾客之外的任何场景，完结都变得非常杂乱。
而运用相同的 cacheline 会产生伪同享问题。比方 ArrayBlockingQueue 有三个成员变量：
- takeIndex：需要被取走的元素下标；
- putIndex：可被元素刺进的方位的下标；
- count：行列中元素的数量；
这三个变量很容易放到一个缓存行中，可是之间修正没有太多的关联。所以每次修正，都会使之前缓存的数据失效，然后不能完全到达同享的作用。
如上图所示，当出产者线程 put 一个元素到 ArrayBlockingQueue 时，putIndex 会修正，然后导致顾客线程的缓存中的缓存行无效，需要从主存中从头读取。一般的处理方案是，增大数组元素的间隔使得由不同线程存取的元素位于不同的缓存行上，以空间换时间。
Disruptor 处理思路
启动时，将预先分配环形缓冲区的一切内存。环形缓冲区能够存储指向 entry 的指针数组，也能够存储表明 entry 的结构数组。这些 entry 中的每一个一般不是传递的数据自身，相似对象池机制，而是它的容器。这种 entry 的预分配消除了支持废物回收的语言中的问题，由于 entry 将被重用，并在整个 Disruptor 实例存活期间都有用。这些 entry 的内存是一起分配的。
一般的数据结构是像下面这样的：
咱们能够运用一个环状的数组结构改进成下面这样：
数组的接连多个元素会一并加载到 CPU Cache 里边来，所以拜访遍历的速度会更快。而链表里边各个节点的数据，八成不会出现在相邻的内存空间，自然也就享用不到整个 Cache Line 加载后数据接连从高速缓存里边被拜访到的优势。遍历拜访时 CPU 层面的分支猜测会很精确。这能够使得咱们更有用地运用了 CPU 里边的多级流水线，咱们的程序就会跑得更快。
在像 Java 这样的托管运行时环境中开发低推迟体系时，废物搜集机制或许会带来问题。分配的内存越多，给废物搜集器带来的负担就越大。当对象的寿数很短或实践上是常驻的时分，废物搜集器工作得最好。在环形缓冲区中预先分配 entry 意味着它关于废物搜集器来说是常驻内存的，废物回收的负担就很轻。一起，数组结构对处理器的缓存机制愈加友好。数组长度 2^n，经过位运算，加快定位的速度。下标采取递增的形式。不必担心 index 溢出的问题。index 是 long 类型，即便 100 万 QPS 的处理速度，也需要 30 万年才能用完。
一般的 Cache Line 巨细在 64 字节左右，然后 Disruptor 在非常重要的字段前后加了许多额定的无用字段。能够让这一个字段占满一整个缓存行，这样就能够避免未同享导致的误杀。
每个出产者或许顾客线程，会先请求能够操作的元素在数组中的方位，请求到之后，直接在该方位写入或许读取数据。
下面用非环形的结构模仿无锁读写。
一个出产者的流程
- 请求写入m个元素；
- 若是有m个元素能够入，则回来最大的序列号。这儿主要判别是否会掩盖未读的元素；
- 若是回来的正确，则出产者开端写入元素。
多个出产者流程
多个出产者的状况下，会遇到“怎么避免多个线程重复写同一个元素”的问题。Disruptor 的处理方法是，每个线程获取不同的一段数组空间进行操作。这个经过 CAS 很容易到达。只需要在分配元素的时分，经过 CAS 判别一下这段空间是否现已分配出去即可。
但怎么避免读取的时分，读到还未写的元素。Disruptor 在多个出产者的状况下，引入了一个与 Ring Buffer 巨细相同的 buffer，Available Buffer。当某个方位写入成功的时分，便把 Availble Buffer 相应的方方位位，符号为写入成功。读取的时分，会遍历 Available Buffer，来判别元素是否现已安排妥当。
读数据流程
出产者多线程写入的状况会杂乱许多：
- 请求读取到序号n；
- 若 writer cursor >= n，这时依然无法确定接连可读的最大下标。从 reader cursor 开端读取 available Buffer，一向查到第一个不可用的元素，然后回来最大接连可读元素的方位；
- 顾客读取元素。
如下图所示，读线程读到下标为 2 的元素，三个线程 Writer1/Writer2/Writer3 正在向 RingBuffer 相应方位写数据，写线程被分配到的最大元素下标是 11。
读线程请求读取到下标从3到11的元素，判别 writer cursor>=11。然后开端读取 availableBuffer，从 3 开端，往后读取，发现下标为7的元素没有出产成功，所以WaitFor(11)回来6。
然后，顾客读取下标从 3 到 6 共计 4 个元素（多个出产者状况下，顾客消费进程示意图）。
写数据流程
多个出产者写入的时分：
- 请求写入 m 个元素；
- 若是有 m 个元素能够写入，则回来最大的序列号。每个出产者会被分配一段独享的空间；
- 出产者写入元素，写入元素的一起设置 available Buffer 里边相应的方位，以符号自己哪些方位是现已写入成功的。
如下图所示，Writer1 和 Writer2 两个线程写入数组，都请求可写的数组空间。Writer1 被分配了下标 3 到下表 5 的空间，Writer2 被分配了下标 6 到下标 9 的空间。
Writer1 写入下标 3 方位的元素，一起把 available Buffer 相应方方位位，符号现已写入成功，往后移一位，开端写下标 4 方位的元素。Writer2 同样的方法。最终都写入完结。
总结
整体上来看 Disruptor 在进步吞吐量、削减并发履行损耗上做出了很大贡献，经过贴合硬件机制的方法进行规划，消除写争用，最小化读争用，并保证代码与现代处理器运用的 Cache 特性良好合作。咱们能够看下 Log4j 2 的功能数据，Log4j 2 的 Loggers all async 就是根据 Disruptor 的。
总结来说 Disruptor 是功能极高的无锁行列，提供了一种很好的运用硬件特性完结尽或许从缓存读取来加速拜访的无锁方案。
本文正在参与「金石方案」
