Disruptor(一)RingBuffer数据结构

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

并发程序设计几个概念

1、: 锁是用来做并发最简单的方式,当然其代价也是最高的。内核态的锁的时候需要操作系统进行一次上下文切换,等待锁的线程会被挂起直至锁释放。在上下文切换的时候,cpu 之前缓存的指令和数据都将失效,对性能有很大的损失。用户态的锁虽然避免了这些问题,但是其实它们只是在没有真实的竞争时才有效。
2、CAS: CAS 的涵义不多介绍了。使用 CAS 时不像上锁那样需要一次上下文切换,但是也需要处理器锁住它的指令流水线来保证原子性,并且还要加上 Memory Barrier 来保证其结果可见。
3、MemoryBarrier: 大家都知道现代 CPU 是乱序执行的,也就是程序顺序与实际的执行顺序很可能是不一致的。在单线程执行时这不是个问题,但是在多线程环境下这种乱序就可能会对执行结果产生很大的影响了。memory barrier 提供了一种控制程序执行顺序的手段, 关于其更多介绍,可以参考Memory_barrier
4、CacheLine: cacheLine 解释起来其实很简单,就是 CPU 在做缓存的时候有个最小缓存单元,在同一个单元内的数据被同时被加载到缓存中,充分利用 cacheLine 可以大大降低数据读写的延迟,错误利用 cache line 也会导致缓存不同替换,反复失效。

并发内存队列考虑的问题

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

Disruptor 数据结构 RingBuffer

RingBuffer 是一个环(首尾相接的环),你可以把它用做在不同上下文(线程)间传递数据的 buffer。基本来说,RingBuffer 拥有一个序号,这个序号指向数组中下一个可用的元素。
image.png
随着你不停地填充这个 buffer(可能也会有相应的读取),这个序号会一直增长,直到绕过这个环。
image.png
要找到数组中当前序号指向的元素,可以通过 mod 操作
sequence mod array.length = array.index
以上面的 RingBuffer 为例(java 的 mod 语法):11 % 8 = 3,RingBuffer 槽的个数是 2 的 N 次方,更有利于基于二进制的计算机进行计算,,这样计算余数只需要通过位操作 index & ( size - 1 )就能够得到实际的 index。和维基百科里面的关于[环形 buffer]的实现方式,与其最大的区别在于:没有尾指针。我们只维护了一个指向下一个可用位置的序号。

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

RingBuffer 的优点

1、在可靠消息传递方面有很好的性能
不删除 buffer 中的数据(这些数据一直存放在 buffer 中,直到新的数据覆盖他们),这样当另外一个服务通过 nak (拒绝应答信号) 告诉我们没有成功收到消息时,我们能够重新发送给他们。
2、底层使用数组,访问比链表快
数组内元素的内存地址的连续性存储的,而且有一个容易预测的访问模式,这是对 CPU 缓存友好的—也就是说,在硬件级别,数组中的元素是会被预加载的,因此在 RingBuffer 当中,cpu 无需时不时去主存加载数组中的下一个元素。(因为只要一个元素被加载到缓存行,其他相邻的几个元素也会被加载进同一个缓存行)。
3、避免 GC 问题
可以为数组预先分配内存,使得数组对象一直存在(除非程序终止),这就意味着不需要花大量的时间用于垃圾回收。不像链表那样,需要为每一个添加到其上面的对象创造节点对象—对应的,当删除节点时,需要执行相应的内存清理操作。

/images/mp_qrcode.jpg
文章目录
  1. 并发程序设计几个概念
  2. 并发内存队列考虑的问题
  3. Disruptor 数据结构 RingBuffer
  4. RingBuffer 的优点