Disruptor(一)Disruptor概念和RingBuffer数据结构

Disruptor是LMAX公司开源的一个高效的内存无锁队列。

谈到并发程序设计,有几个概念是避免不了的。

1、锁: 锁是用来做并发最简单的方式,当然其代价也是最高的。内核态的锁的时候需要操作系统进行一次上下文切换,等待锁的线程会被挂起直至锁释放。在上下文切换的时候,cpu之前缓存的指令和数据都将失效,对性能有很大的损失。用户态的锁虽然避免了这些问题,但是其实它们只是在没有真实的竞争时才有效。

2CAS CAS的涵义不多介绍了。使用CAS时不像上锁那样需要一次上下文切换,但是也需要处理器锁住它的指令流水线来保证原子性,并且还要加上Memory Barrier来保证其结果可见。

3MemoryBarrier: 大家都知道现代CPU是乱序执行的,也就是程序顺序与实际的执行顺序很可能是不一致的。在单线程执行时这不是个问题,但是在多线程环境下这种乱序就可能会对执行结果产生很大的影响了。memory barrier提供了一种控制程序执行顺序的手段, 关于其更多介绍,可以参考 http://en.wikipedia.org/wiki/Memory_barrier

4CacheLine cacheLine解释起来其实很简单,就是CPU在做缓存的时候有个最小缓存单元,在同一个单元内的数据被同时被加载到缓存中,充分利用cacheLine可以大大降低数据读写的延迟,错误利用cache line也会导致缓存不同替换,反复失效。

并发内存队列时需要考虑的问题

1、数据结构问题

是选用定长的数组还是可变的链表

2、并发控问题

使用锁还是CAS操作,是使用粗粒度的一把锁,还是将队列的头、尾、和容量三个变量分开控制,即使分开,能不能避免它们落入同一个Cache line中。数据的入队和出队都是很耗时的,尤其在性能要求极高的场景中,这种消耗更显得奢侈。

Disruptor数据结构RingBuffer

RingBuffer是一个环(首尾相接的环),你可以把它用做在不同上下文(线程)间传递数据的buffer。基本来说,RingBuffer拥有一个序号,这个序号指向数组中下一个可用的元素。

随着你不停地填充这个buffer(可能也会有相应的读取),这个序号会一直增长,直到绕过这个环。

要找到数组中当前序号指向的元素,可以通过mod操作

sequence mod array.length = array.index

以上面的RingBuffer为例(javamod语法):11 % 8 = 3,RingBuffer槽的个数是2N次方,更有利于基于二进制的计算机进行计算,,这样计算余数只需要通过位操作index & ( size – 1 )就能够得到实际的index。和维基百科里面的关于环形buffer的实现方式,与其最大的区别在于:没有尾指针。我们只维护了一个指向下一个可用位置的序号。

RingBuffer本身并不控制是否需要重叠,对于如何避免RingBuffer产生重叠,以及如何对RingBuffer进行读写操作,移到了数据结构(RingBuffer)的外(队列通常注重维护队列的头尾元素,添加和删除元素等),由于生产者和消费者是分开考虑和控制的,因此有可能能够通过一个核心的环形队列来表示全部的依赖关系,可以大大提高吞吐,降低延迟。

RingBuffer的优点

1、在可靠消息传递方面有很好的性能

不删除buffer中的数据(这些数据一直存放在buffer中,直到新的数据覆盖他们),这样当另外一个服务通过nak (拒绝应答信号) 告诉我们没有成功收到消息时,我们能够重新发送给他们。

2、底层使用数组,访问比链表快

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

3、避免GC问题

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