http://mechanitis./search/label/disruptor http:///disruptor/, 并发框架Disruptor译文 http://blog.sina.com.cn/s/blog_68ffc7a4010150yl.html, 论文译文 LMAX需要搭建high performance的交易平台, 所以需要基于并发编程模型 (并发编程模型和访问控制) 如图这样比较简单的处理流程, 就需要4个queue和大量的message发送, disruptor设计了一种高效的替代方案 解决如下问题,
1, 用何种数据机构来实现Queue如何使用Disruptor(一)Ringbuffer的特别之处 实现queue首先想到链表, 但使用链表有下列问题, 那么用数组实现, 可以部分解决前3点问题, 但仍然无法解决竞争点问题, 以及由于数组的fix size, 带来扩展性问题 Disruptor采用特殊的ring buffer来作为queue实现的数据结构, 解决了上述的问题
2, 减少竞争点, 分离关注对于传统的3个竞争点, Disruptor成功的通过ring buffer将其降低到1个, 提高了效率
3, Lock-free前面说了disruptor减少竞争点, 但是不可能完全消除竞争, 对于写入标志位, 当多个producer的时候仍然存在竞争, 竞争就需要加锁. 锁是很低效的, 论文中的3.1讲的比较清晰, 并通过实验数据证明了这点, 使用锁会慢1000倍
CAS的问题就是更为复杂, 比使用lock更难于理解, 并且虽然相对于lock已经很高效, 但是由于上面提到的耗费, 仍然比不使用任何锁机制要慢的多
4, 解决伪共享(False Sharing)剖析Disruptor:为什么会这么快?(二)神奇的缓存行填充 前面提到, CPU cache的预读会大大提高执行效率, 这也是为什么选择数组来替代链表的很重要的原因, 因为数组集中存储可以通过预读大大提高效率 所以cache是优化的关键, cache越接近core就越快,也越小 cache-line(缓存行) 缓存是由缓存行组成的, 通常是64字节, 一个Java的long类型是8字节,因此在一个缓存行中可以存8个long类型的变量. 这里谈的伪共享问题, 也是一种主要的cache丢失的case, 需要通过缓存行填充来解决 上面的提到的cache-line, 对于象数组这样连续存储的数据结构非常高效, 但是不能保证所有结构都是连续存储的, 比如对于链表, 就很容易出现伪共享问题, 即这种预读反而使效率降低. 那么如何解决这个问题? 当然显而易见, 这种缓存行填充是非常浪费的, cache本身就是很昂贵的资源, 所以必须慎用 在Disruptor里我们对RingBuffer的cursor和BatchEventProcessor的序列进行了缓存行填充 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 以cursor为例, 本身是独立的变量, 和其他的数据没有关联关系, 并且cursor会频繁的被所有线程读取, 所以如果由于其他不相关的变量的更改而导致cursor所在的cache-line被频繁reload, 是非常低效的. 所以, disruptor在cursor前后都pading了7个long, 从而避免cursor和任意其他的变量在同一个cache-line 使用缓存行填充的准则, 独立变量, 变量被大量线程touch, 会被频繁使用和读取
5, 使用内存屏障http:///linux-memory-barriers/, 非常详细的介绍了内存屏障的原理 首先, 内存屏障本身不是一种优化方式, 而是你使用lock-free(CAS)的时候, 必须要配合使用内存屏障 因为CPU和memory之间有多级cache, CPU core只会更新cache-line, 而cache-line什么时候flush到memory, 这个是有一定延时的 所以如果要保证使用CAS能保证线程间互斥, 即乐观锁, 必须当一个core发生更新后, 其他所有core立刻知道并把相应的cache-line设为过期, 否则在这些core上执行CAS读到的都是过期数据 Java中用volatile来实现内存屏障
volatile保证了线程间的可见性, 但是同样如果要实现互斥, 必须借助CAS, 以避免读取到更新之间的数据变更
内存屏障另一种用途, CPU出于对执行指令和数据加载的优化会调整执行顺序, 所以在代码里面先写的指令不一定会被先执行, 当然是在保证逻辑一致性的前提下. 所以可以看到内存屏障, 虽然和lock比是高效的, 但毕竟限制了CPU的优化并会强制flush cache-line, 所以仍然是比较昂贵的操作.
6, 如何使用Disruptor替代Queue我本来以为是用一个ringbuffer替代一个queue, 原来是用一个ringbuffer替代所有的queue, 怎么实现的? 如图, 所有consumer都是从RingBuffer里面读数据 那么有个问题是C3, 如何获得C1和C2的执行结果? 如图, 当C3拿到Entry时, 里面有3个值, 本来的value, C1处理的结果, C2处理的结果, 并且不同的consumer写的字段不一样来避免冲突
看起来非常的复杂, 但是在使用时, 对用户很多机制其实是透明的, 比如上面的workflow的代码如下 ConsumerBarrier consumerBarrier1 = ringBuffer.createConsumerBarrier(); BatchConsumer consumer1 = new BatchConsumer(consumerBarrier1, handler1); BatchConsumer consumer2 = new BatchConsumer(consumerBarrier1, handler2); ConsumerBarrier consumerBarrier2 = ringBuffer.createConsumerBarrier(consumer1, consumer2); BatchConsumer consumer3 = new BatchConsumer(consumerBarrier2, handler3); ProducerBarrier producerBarrier = ringBuffer.createProducerBarrier(consumer3);
总结总体来说, disprutor从两个方面来对Actor模式的queue做了优化 最重要的是, Mechanical Sympathy(机械的共鸣), 了解硬件的工作方式来编写和硬件完美结合的软件, 很高的境界 其次, 是通过ringbuffer来实现queue来替代链表的实现, 尤其当场景比较复杂需要很多queue的时候, 效率应该会得到很大的提高
其实, disruptor并没有实现queue的互斥consumer, 每个consumer都是自己保持序号, 各读各得, 但是对于普通queue, 被一个线程pop掉的数据, 其他线程是无法读到的 |
|