队列

队列	加锁方式	是否有界	数据结构
ArrayBlockingQueue	加锁	有界	ArrayList
LinkedBlockingQueue	加锁	*	LinkedList
ConcurrentLinkedQueue	CAS	*	LinkedList
LinkedTransferQueue	CAS	*	LinkedList
disruptor	CAS	有界	ringBuffer

Disruptor

是一个高性能的异步处理框架，或者可以认为是线程间通信的高效低延时的内存消息组件

Disruptor实现高性能主要体现了去掉了锁，采用CAS算法，同时内部通过环形队列实现有界队列。

• 环形数据结构
  为了避免垃圾回收，采用数组而非链表。同时，数组对处理器的缓存机制更加友好。

• 元素位置定位
  数组长度2^n，通过位运算，加快定位的速度。下标采取递增的形式。不用担心index溢出的问题。index是long类型，即使100万QPS的处理速度，也需要30万年才能用完。

• 无锁设计
  每个生产者或者消费者线程，会先申请可以操作的元素在数组中的位置，申请到之后，直接在该位置写入或者读取数据。整个过程通过原子变量CAS，保证操作的线程安全。

• 缓存行填充
  数据在缓存中不是以独立的项来存储的，如不是一个单独的变量，也不是一个单独的指针。缓存是由缓存行组成的，通常是64字节，并且它有效地引用主内存中的一块地址。一个Java的long类型是8字节，因此在一个缓存行中可以存8个long类型的变量。
  数组中的一个值被加载到缓存中，它会额外加载另外7个。因此你能非常快地遍历这个数组。当缓存行中两个值同时被修改时,第一个修改的生效,第二个失败,整个缓存行需要从主内存重新读取,产生伪共享.
  Disruptor消除这个问题，至少对于缓存行大小是64字节或更少的处理器架构来说是这样，通过增加补全来确保ring buffer的***不会和其他东西同时存在于一个缓存行中。
  public long p1, p2, p3, p4, p5, p6, p7; // cache line padding private volatile long cursor = INITIAL_CURSOR_VALUE; public long p8, p9, p10, p11, p12, p13, p14; // cache line padding