Java中的队列介绍#
开门见山，我们看一眼Java并发包中的常见队列：
| 队列 | 有界性 | 锁 | 数据结构 |
|---|---|---|---|
| ArrayBlockingQueue | Y | 加锁 | arraylist |
| LinkedBlockingQueue | optionally-bounded | 加锁 | linkedlist |
| ConcurrentLinkedQueue | N | CAS | linkedlist |
| LinkedTransferQueue | N | CAS | linkedlist |
| PriorityBlockingQueue | N | 加锁 | heap |
| DelayQueue | N | 加锁 | heap |
上面的无界其实是Integer.MAX_VALUE，下文视为无界。
这种无界的队列导致在阿里的手册里面是不建议直接使用内建的ThreadPoolExecutor，防止因为任务无限堆积导致OOM。（如Single、Fixed），建议手动创建线程池，指定阻塞队列的长度。
这种加锁导致了并发性能的降低。
队列的底层一般分成三种：数组、链表和堆。其中，堆一般情况下是为了实现带有优先级特性的队列，暂且不考虑。
我们就从数组和链表两种数据结构来看，基于数组线程安全的队列，比较典型的是ArrayBlockingQueue，它主要通过加锁的方式来保证线程安全；
基于链表的线程安全队列分成**LinkedBlockingQueue（加锁）和ConcurrentLinkedQueue（CAS）**两大类，前者也通过锁的方式来实现线程安全，而后者以及上面表格中的LinkedTransferQueue都是通过原子变量compare and swap（以下简称“CAS”）这种不加锁的方式来实现的。
通过不加锁（使用CAS）的方式实现的队列都是无界的（无法保证队列的长度在确定的范围内）；而加锁的方式，可以实现有界队列。
但是，在稳定性要求特别高的系统中，为了防止生产者速度过快，导致内存溢出，只能选择有界队列；（阿里手册也如此推荐）同时，为了减少Java的垃圾回收对系统性能的影响，会尽量选择array/heap格式的数据结构。这样筛选下来，符合条件的队列就只有ArrayBlockingQueue。
ArrayBlockingQueue的问题#
- 写操作加重入锁，慢，等待锁阻塞。要是可以 无锁或者CAS，则大幅优于加锁
- 伪共享（三级缓存、64字节缓存行、没有利用缓存行，这三个才24字节，可能会被截断不在一个缓存行，效率低），多线程竞争的时候效率低下
ArrayBlockingQueue有读写索引位置takeIndex和putIndex，以及元素数量count三个int。- 另外有一个缓存行的优化见：《缓存行与伪共享》
Disruptor的设计方案#
Disruptor通过以下设计来解决队列速度慢的问题：
- 环形数组结构
为了避免垃圾回收，采用数组而非链表。同时，数组对处理器的缓存机制更加友好。
- 元素位置定位
数组长度2^n，通过位运算，加快定位的速度。下标采取递增的形式。不用担心index溢出的问题。index是long类型，即使100万QPS的处理速度，也需要30万年才能用完。
- 无锁设计
每个生产者或者消费者线程，会先申请可以操作的元素在数组中的位置，申请到之后，直接在该位置写入或者读取数据。
下面忽略数组的环形结构，介绍一下如何实现无锁设计。整个过程通过原子变量CAS，保证操作的线程安全。
参考
https://github.com/LMAX-Exchange/disruptor/wiki
https://tech.meituan.com/2016/11/18/disruptor.html
http://ifeve.com/dissecting-disruptor-whats-so-special
http://ifeve.com/dissecting_the_disruptor_how_doi_read_from_the_ring_buffer