Disruptor 介绍

并发的复杂性：

    在计算机科学中，并发的意思是两个或两个以上的任务同时并行的执行，但是也要通过争抢来接入资源。争抢的资源可能是数据库、文件系统、套接字、甚至或者说内存中的一块区域。
    并发的执行代码包括两个方面：互斥性和改变的可见性。互斥性是指线程对资源进行争用状态的改变的管理（这里的争用状态主要是指写的操作要保持互斥性），而改变可见性是指控制何时这种改变对其他线程可见。很明显，如果能消除争用就能够避免互斥性管理——如果有某种算法，能够确保任何给定的资源同一时刻只被一个线程修改，那么互斥性就不是必要的了。读和写操作需要所有改变对其他线程都是可见的，但是只有争用写操作需要保持互斥性。
    在任何并发的环境中，争用写操作是花费最大代价的。为了支持多个并发的线程对同一块资源进行写操作是需要花费复杂而昂贵的代价来进行协调的。最典型的解决这种协调的方法是引入某种锁的策略。

锁的代价：

     锁提供了互斥性并且确保改变对其他线程的可见性以一种命令式的方式发生。锁的代价消耗是难以置信的大——因为它们当遇到争用时需要进行仲裁。这种仲裁是通过一种上下文切换到操作系统的内核，挂起线程等待锁的释放。在这样的上下文切换过程中，也会交还控制权给操作系统——操作系统此时可能同时决定去做其他一些请理性的工作，这样正在执行中的上下文对象将会丢失之前预读的缓存中的数据和指令（这里的缓存指的是CPU缓存）。对现代CPU而言，这将会造成一系列的性能上的坏的影响。可以使用快速的用户模式的锁，但是这也仅当没有争用的时候能够带来真正的益处。

     理想的算法应该是仅仅使用一个单线程来处理所有的对一个资源的写操作，而有多个线程执行读取处理结果的操作。在一个多处理器或多核处理器环境下处理对资源的读操作需要内存栅栏来确保一个线程状态改变对其他处理器上运行的线程可见。

内存栅栏：

     一旦内存数据被推送到缓存，就会有消息协议来确保所有的缓存会对所有的共享数据同步并保持一致。这个使内存数据对CPU核可见的技术被称为内存屏障或内存栅栏。

     内存屏障提供了两个功能。首先，它们通过确保从另一个CPU来看屏障的两边的所有指令都是正确的程序顺序，而保持程序顺序的外部可见性；其次它们可以实现内存数据可见性，确保内存数据会同步到CPU缓存子系统。

     大多数的内存屏障都是复杂的话题。在不同的CPU架构上内存屏障的实现非常不一样。

     内存屏障或内存栅栏，也就是让一个CPU处理单元中的内存状态对其它处理单元可见的一项技术。

     现代的处理器为了提高效率，采用无序的方式执行其指令、在内存和对应的执行单元间加载和存储数据。处理器仅仅需要确保程序逻辑执行出正确的结果而不去关心其执行顺序。这不是单线程程序的特性。但是当线程间彼此共享状态时为了确保数据交换的成功处理，在需要的时点，内存的改变能够按次序发生就是很重要的了。内存栅栏是处理器用来指出代码块在哪里修改内存是需要有序的进行的。它们是硬件排序和线程间保持彼此改变可见性的重要手段。编译器会在适当的位置设置合适的软件栅栏来确保代码按照正确的顺序编译，处理器本身也会使用这样的软件栅栏作为硬件栅栏的一种补充。

    现代的处理器要比同代的内存快得多的多。为了填补这样一个速度差距的鸿沟，CPU使用了复杂的缓存系统——非常快的通过硬件实现的无链哈希表。这些缓存系统通过消息传递协议与其他处理器CPU的缓存系统保持协调一致。另外作为补充，处理器的“存储缓冲”可以将写操作从上述缓冲上卸载下来，在一个写操作将要发生的时候，缓存协调协议通过这样的一个“失效队列”快速的通知失效消息。

    这些对于数据来说意味着，当某个数据值的最后一个版本刚刚被写操作执行之后，将会被存储登记给一个存储缓冲——可能是CPU的某一层缓存、或者是一块内存区域。如果线程想要共享这一数据，那么它需要以一种有序的方式轮流对其他线程可见，这是通过处理器协调消息的协调来实现的。这些及时的协调消息的生成，是内存栅栏来控制的。

    读操作内存栅栏对CPU的加载指令进行排序，通过失效队列来得知当前缓存的改变。这使得读操作内存栅栏对其之前的已排序的写操作有了一个持久化的视界。

    写操作内存栅栏对CPU的存储指令进行排序，通过存储缓冲执行，因此，通过对应的CPU缓存来刷新写输出。写操作内存栅栏提供了一个在其之前的存储操作如何发生的、有序的视界。

    一个完整的内存栅栏即对加载排序也对存储排序，但这只针对执行该栅栏的CPU。

    在Java的内存模型中，对一个volatile类型成员变量的域的读和写，分别实现了读内存栅栏和写内存栅栏。（对volatile类型的成员变量虚拟机不采用优化策略，即不在每个线程中保存其副本，每次读取和修改都将到共享的内存域中进行）。

缓存行：

    现代处理器使用缓存的方式对成功的高性能操作而言具有重要的意义。这种处理器架构在数据搅动和指令存储方面有极大作用，反之，如果缓存出现丢失的话将对系能造成极大的影响。
    我们的硬件在移动内存数据的时候不是以字节和字长为单位的，为了更加有效的工作，缓存被组织成缓存行的形式，每个缓存行为32-256个字节大小，一般是64字节。这是缓存协调协议操作的粒度层级。这意味着如果两个变量在同一个缓存行内，并且它们是被两个不同的线程写入的话，它们将会呈现出相同的写争用问题，就好像它们是一个变量一样！这就是“伪共享”概念。所以为了提高性能，应该确保独立的且并发的写操作、并且写操作的变量不在同一个缓存行内，可以使争用最小化。
   
Disruptor的独特设计：

     Disruptor的目标是尽可能多的在内存中运行。

     处于Disruptor机制中心脏地位的是一个预先分配的有界数据结构形式——环状缓冲。数据通过一个或多个生产者添加到环状缓冲中，并通过一个或多个消费者从其中取出处理。

内存分配：

     环状缓冲（ring buffer）的所有内存空间是在启动的时候预先分配好的。环状缓冲既可以存储一整个数组的指向实体的指针、或者是代表实体本身的数据结构。由于Java语言本身的限制意味着实体是以对象的引用的形式存放在环状缓冲中的。每一个实体一般并不是直接存放的，而是放在一个容器里，而把容器放在缓冲中。这种实体存放空间的预分配的形式终结了支持垃圾回收机制的语言所带来的问题，因为实体会被重复使用并在Disruptor实例的生命周期中一致存在。这些实体的内存空间是在同一时刻分配好的，并且一般来说是在内存中连续的一块地址，因此支持缓存跳跃。

     在一个像Java这样被管理的运行时环境中开发低延迟系统时，垃圾回收可能会是个问题。分配的内存越多，垃圾收集器的负担就越大。当对象的生命周期都极短或者对象永不销毁的情况下，垃圾收集器可以达到最佳性能(实际上是最小的负担)。环状缓冲中的实体内存是预先分配好的，意味着它在垃圾回收器工作的时候是永不销毁的，所以只带来很少的负担。

    由于基于队列的系统在高负载时会导致执行率降低、并且导致分配的对象释放其所在空间上的延迟，所以一代又一代的垃圾收集器都在这一点上进行不断优化。这有两层意思：第一，对象不得不在每一代之间进行复制，这导致了不定的延迟。第二，这些对象可能会从旧代中收集，这可能会是更加消耗性的操作,可能增加“世界停止”一般的暂停,这发生在零碎的内存空间被重新压实的时候。在大内存堆中这会导致每GB数秒的暂停。

批量效应：

     当消费者等待环状缓冲中最新可用的游标序列号时会有一定几率发生一个在队列中不会发生的有趣的现象：如果消费者发现与它上次检查的时候相比，环状缓冲的游标已经向前走了许多步的话，它可以直接处理到那个最新的序列号而不必纠缠于并发机制。这样的结果是本来落后的生产者会重新赢得与之前突然爆发的生产者的赛跑比赛，重新平衡了系统。这种批量效应增加了处理吞吐量并减少和平稳了延迟。根据我们的观察，在内存子系统饱和之前，不管负载多大，这种效应的延迟始终接近一个时间常量，对应的变化曲线是线性的并遵循利特尔法则，这与我们使用队列时在负载不断增加时延迟呈指数级增长得到的J形曲线是截然不同的。

Disruptor的类结构图：





生产者通过ProducerBarrier使用序列号声明实体，在声明好的实体中写入改变，然后通过ProducerBarrier将实体提交回来并使其可以被消费者使用。而消费者仅仅需要提供一个BatchHandler的实现即可，该实现负责接收当一个新的实体可用时的回调请求。

Disruptor模式的核心——RingBuffer，可以提供存储使得数据的交换在不发生争用的情况下进行。经由生产者、消费者与RingBuffer的交互中分离出了传统并发所带来的问题。ProducerBarrier负责管理所有在环状缓冲中声明序列位置的并发问题，并跟踪各个消费者以确保这个环不会缠绕。（在RingBuffer这个环状的跑道上，最快的生产者超过了最慢的消费者，即为环的缠绕。）ConsumerBarrier用来提醒消费者是否有新的实体可用，这样消费者便可以构造图状的依赖关系用来表示一个处理关系中多个阶段。


Disruptor 是什么：

Disruptor 是一个 Java 的并发编程框架，大大的简化了并发程序开发的难度，在性能上也比 Java 本身提供的一些并发包要好

Disruptor 是一个高性能异步处理框架，它实现了观察者模式

Disruptor ：它是无锁的、CPU友好；它不会清除缓存中的数据，只会覆盖，降低了垃圾回收机制启动的频率。


Disruptor 为什么快：

1. 不使用锁，通过内存屏障和原子性的CAS操作替换锁

2. 缓存基于数组而不是链表，用位运算替代求模。缓存的长度总是2的n次方，这样可以用位运算 i & (length - 1) 替代 i % length

3. 去除伪共享，CPU的缓存一般是以缓存行为最小单位的，对应主存的一块相应大小的单元；当前的缓存行大小一般是64字节，每个缓存行一次只能被一个CPU核访问，如果一个缓存行被多个CPU核访问，就会造成竞争，导致某个核必须等其他核处理完了才能继续处理，响应性能。去除伪共享就是确保CPU核访问某个缓存行时不会出现争用

4.预分配缓存对象，通过更新缓存里对象的属性而不是删除对象来减少垃圾回收


核心类和接口：

EventHandler：用户提供具体的实现，在里面实现事件的处理逻辑。由用户实现并且代表了Disruptor中的一个消费者的接口。


Sequence：代表事件序号或一个指向缓存某个位置的序号。Disruptor使用Sequence来表示一个特殊组件处理的序号。和Disruptor一样，每个消费者(EventProcessor)都维持着一个Sequence。大部分的并发代码依赖这些Sequence值的运转，因此Sequence支持多种当前AtomicLong类的特性。事实上，这两者之间唯一的区别是Sequence包含额外的功能来阻止Sequence和其他值之间的共享。


WaitStrategy：功能包括：当没有可消费的事件时，根据特定的实现进行等待，有可消费事件时返回可事件序号；有新事件发布时通知等待的 SequenceBarrier。它决定了一个消费者将如何等待生产者将Event置入Disruptor。


Sequencer：生产者用于访问缓存的控制器，它持有消费者序号的引用；新事件发布后通过WaitStrategy 通知正在等待的SequenceBarrier。这是Disruptor真正的核心。实现了这个接口的两种生产者（单生产者和多生产者）均实现了所有的并发算法，为了在生产者和消费者之间进行准确快速的数据传递。


SequenceBarrier：消费者关卡。消费者用于访问缓存的控制器，每个访问控制器还持有前置访问控制器的引用，用于维持正确的事件处理顺序；通过WaitStrategy获取可消费事件序号。由Sequencer生成，并且包含了已经发布的Sequence的引用，这些的Sequence源于Sequencer和一些独立的消费者的Sequence。它包含了决定是否有供消费者来消费的Event的逻辑。


EventProcessor：事件处理器，是可执行单元，运行在指定的Executor里；它会不断地通过SequenceBarrier获取可消费事件，当有可消费事件时调用用户提供的 EventHandler实现处理事件。主要的事件循环，用于处理Disruptor中的Event，并且拥有消费者的Sequence。它有一个实现类是BatchEventProcessor，包含了event loop有效的实现，并且将回调到一个EventHandler接口的实现对象。


EventTranslator：事件转换器，由于Disruptor只会覆盖缓存，需要通过此接口的实现来更新缓存里的事件来覆盖旧事件。


RingBuffer：基于数组的缓存实现，它内部持有对Executor、WaitStrategy、生产者和消费者访问控制器的引用。


Disruptor：提供了对 RingBuffer 的封装，并提供了一些DSL风格的方法，方便使用。


Disruptor 模型：





其中的RingBuffer被组织成环形队列，但它与我们在常常使用的队列又不一样，这个队列大小固定，且每个元素槽都以一个整数进行编号，RingBuffer中只有一个游标维护着一个指向下一个可用位置的序号，生产者每次向RingBuffer中写入一个元素时都需要向RingBuffer申请一个可写入的序列号，如果此时RingBuffer中有可用节点，RingBuffer就向生产者返回这个可用节点的序号，如果没有，那么就等待。同样消费者消费的元素序号也必须是生产者已经写入了的元素序号。

RingBuffer：

      首先，因为它是数组，所以要比链表快，而且有一个容易预测的访问模式。（数组内元素的内存地址的连续性存储的）。这是对CPU缓存友好的—也就是说，在硬件级别，数组中的元素是会被预加载的，因此在ringbuffer当中，cpu无需时不时去主存加载数组中的下一个元素。（因为只要一个元素被加载到缓存行，其他相邻的几个元素也会被加载进同一个缓存行）

      其次，你可以为数组预先分配内存，使得数组对象一直存在（除非程序终止）。这就意味着不需要花大量的时间用于垃圾回收。此外，不像链表那样，需要为每一个添加到其上面的对象创造节点对象—对应的，当删除节点时，需要执行相应的内存清理操作。

      CPU和主内存之间有好几层缓存，因为即使直接访问主内存也是非常慢的。如果你正在多次对一块数据做相同的运算，那么在执行运算的时候把它加载到离CPU很近的地方就有意义了

     越靠近CPU的缓存越快也越小。所以L1缓存很小但很快(L1表示一级缓存)，并且紧靠着在使用它的CPU内核。L2大一些，也慢一些，并且仍然只能被一个单独的 CPU 核使用。L3在现代多核机器中更普遍，仍然更大，更慢，并且被单个插槽上的所有 CPU 核共享。最后，你拥有一块主存，由全部插槽上的所有 CPU 核共享。

     当CPU执行运算的时候，它先去L1查找所需的数据，再去L2，然后是L3，最后如果这些缓存中都没有，所需的数据就要去主内存拿。走得越远，运算耗费的时间就越长。所以如果你在做一些很频繁的事，你要确保数据在L1缓存中。





缓存行：

     数据在缓存中不是以独立的项来存储的，如不是一个单独的变量，也不是一个单独的指针。缓存是由缓存行组成的，通常是64字节（译注：这篇文章发表时常用处理器的缓存行是64字节的，比较旧的处理器缓存行是32字节），并且它有效地引用主内存中的一块地址。一个Java的long类型是8字节，因此在一个缓存行中可以存8个long类型的变量。




     非常奇妙的是如果你访问一个long数组，当数组中的一个值被加载到缓存中，它会额外加载另外7个。因此你能非常快地遍历这个数组。事实上，你可以非常快速的遍历在连续的内存块中分配的任意数据结构。它解释了我们的ring buffer使用数组的原因。

     因此如果你数据结构中的项在内存中不是彼此相邻的（链表），你将得不到免费缓存加载所带来的优势。并且在这些数据结构中的每一个项都可能会出现缓存未命中。

     不过，所有这种免费加载有一个弊端。设想你的long类型的数据不是数组的一部分。设想它只是一个单独的变量。让我们称它为head，这么称呼它其实没有什么原因。然后再设想在你的类中有另一个变量紧挨着它。让我们直接称它为tail。现在，当你加载head到缓存的时候，你也免费加载了tail。




     听想来不错。直到你意识到tail正在被你的生产者写入，而head正在被你的消费者写入。这两个变量实际上并不是密切相关的，而事实上却要被两个不同内核中运行的线程所使用。





设想你的消费者更新了head的值。缓存中的值和内存中的值都被更新了，而其他所有存储head的缓存行都会都会失效，因为其它缓存中head不是最新值了。请记住我们必须以整个缓存行作为单位来处理（这是CPU的实现所规定的），不能只把head标记为无效。




现在如果一些正在其他内核中运行的进程只是想读tail的值，整个缓存行需要从主内存重新读取。那么一个和你的消费者无关的线程读一个和head无关的值，它被缓存未命中给拖慢了。

当然如果两个独立的线程同时写两个不同的值会更糟。因为每次线程对缓存行进行写操作时，每个内核都要把另一个内核上的缓存块无效掉并重新读取里面的数据。你基本上是遇到两个线程之间的写冲突了，尽管它们写入的是不同的变量。

这叫作“伪共享”，因为每次你访问head你也会得到tail，而且每次你访问tail，你也会得到head。这一切都在后台发生，并且没有任何编译警告会告诉你，你正在写一个并发访问效率很低的代码。

你会看到Disruptor通过缓存行填充消除这个问题，至少对于缓存行大小是64字节或更少的处理器架构来说是这样的（有可能处理器的缓存行是128字节，那么使用64字节填充还是会存在伪共享问题），通过增加补全来确保ring buffer的序列号不会和其他东西同时存在于一个缓存行中。

因此没有伪共享，就没有和其它任何变量的意外冲突，没有不必要的缓存未命中。

在你的Entry类中也值得这样做，如果你有不同的消费者往不同的字段写入，你需要确保各个字段间不会出现伪共享。