高并发数据结构Disruptor解析（1）

最近想解决下MyCat开统计后TPS吞吐量总上不去的问题，于是想起了Disruptor这个东西。之前想研究过，但是，由于当时并不太需要，而且感觉官方示例比较怪异，就是知道他比较快，没有想用。现在捡起来好好研究下。
首先，推荐大家并发编程网的Disruptor译文. 官网的翻译，翻译的不错，从硬件到软件，谈了Disruptor相对于传统阻塞队列的优化。这里主要针对源代码谈实现和应用。
首先，先拿一张图看一下Disruptor的主要元素：
为什么RingBuffer这么快，首先抛出两个原因：

1. 首先是CPU false sharing的解决，Disruptor通过将基本对象填充冗余基本类型变量来填充满整个缓存行，减少false sharing的概率。
2. 之后是无锁队列的实现，对于传统并发队列，至少要维护两个指针，一个头指针和一个尾指针。在并发访问修改时，头指针和尾指针的维护不可避免的应用了锁。Disruptor由于是环状队列，对于Producer而言只有头指针，而且锁是乐观锁，在标准Disruptor应用中，只有一个生产者，避免了头指针锁的争用。所以，我们可以理解Disruptor为无锁队列。

工作流程可以描述为：
每个RingBuffer是一个环状队列，队列中每个元素可以理解为一个槽。在初始化时，RingBuffer规定了总大小，就是这个环最多可以容纳多少槽。这里Disruptor规定了，RingBuffer大小必须是2的n次方。这里用了一个小技巧，就是将取模转变为取与运算。在内存管理中，我们常用的就是取余定位操作。如果我们想在Ringbuffer定位，一般会用到某个数字对Ringbuffer的大小取余。如果是对2的n次方取余，则可以简化成：

1
2
1m % 2^n = m & ( 2^n - 1 )

2

Producer会向这个RingBuffer中填充元素，填充元素的流程是首先从RingBuffer读取下一个Sequence，之后在这个Sequence位置的槽填充数据，之后发布。
Consumer消费RingBuffer中的数据，通过SequenceBarrier来协调不同的Consumer的消费先后顺序，以及获取下一个消费位置Sequence。
Producer在RingBuffer写满时，会从头开始继续写，替换掉以前的数据。但是如果有SequenceBarrier指向下一个位置，则不会覆盖这个位置，阻塞到这个位置被消费完成。Consumer同理，在所有Barrier被消费完之后，会阻塞到有新的数据进来。

Sequence

下面我们来看下Sequence这个类的源代码，首先，Sequence的类继承结构如下所示：
这里对于Sequence的核心就是value这个volatile long类型的变量，它就是代表下一个位置。那么p1，p2，。。。这些用来干啥呢？这些为了避免CPU伪共享的出现（false sharing）

CPU缓存结构：

CPU为了加速访问，就像数据库和缓存关系相似，存在L1缓存，L2缓存，L3缓存来缓存内存中的数据。
级别越小，CPU访问越快：
**缓存行：**CPU缓存并不是将内存数据一个一个的缓存起来，而是每次从内存中取出一行内存，称为缓存行（Cache Line），对于我的电脑，缓存行长度是 64Bytes。对于Java，也就是说，假设X和Y对象，他们两个内存相邻，而且加起来的长度小于64 Bytes
这里会涉及到缓存行失效的问题，如下图：
假设有两个线程分别访问并修改X和Y这两个变量，X和Y恰好在同一个缓存行上，这两个线程分别在不同的CPU上执行。那么每个CPU分别更新好X和Y时将缓存行刷入内存时，发现有别的修改了各自缓存行内的数据，这时缓存行会失效，从L3中重新获取。这样的话，程序执行效率明显下降。为了减少这种情况的发生，其实就是避免X和Y在同一个缓存行中，可以主动添加一些无关变量将缓存行填充满，比如在X对象中添加一些变量，让它有64 Byte那么大，正好占满一个缓存行。

Java对象占用内存：

对于一个Java对象，按顺序排列内存中元素：

• 对象头，保存一些锁的信息和其他对象信息，64位Hotspot JVM占用12 Bytes，如果是数组的话还有4Bytes的长度位

• 基本类型占用：Java8种基本类型的内存，按下面的顺序排列

• long，double：8字节

  • int，float：4字节
  • char，short：2字节
  • boolean，byte：1字节

• 引用类型占用：4字节

• 补齐：最后整个长度必须为8的倍数，不足补位，如果补齐长度是4字节，而且对象头是12字节，就在对象头后补齐4字节。

最后我们看内存中Sequence的状态，我们这里只关心变量部分，常量部分不考虑。Sequence的核心就是value这个值，我们要并发的修改不同Sequence的value的值，我们要保证每个缓存行里面只有一个Sequence的value。一般现在的电脑CPU缓存行是64字节，如下图所示，即使最极端的情况下（Cache line开头或者结尾是value），也能保证每个CacheLine中只有一个Disruptor中的Sequence，这样我们能明显减少false sharing带来的性能损耗