多线程开发中无锁队列的设计和实现

  首先,本人对多核编程的了解还不深入,也不知道等待无关(Wait-Free)、锁无关(Lock-Free)、基于锁(Lock-Based)这些高端的东西,其实原本我只是想接触一个不用锁的数据结构这么个意思,没想到lockfree还有这么大的一个坑。

  现在熟悉多线程开发的人,都知道多线程开发环境下的利器就是:互斥锁、条件变量、任务队列。
  条件变量主要是用于异步唤醒的,当资源不满足的时候线程挂起睡眠,当别的线程修改条件后通知唤醒该进程;任务队列是实现生产者消费者数据交互和缓冲的主要通道,通常使用固定长度的数组做round-robin Ring数组或者采用链表的方式进行管理。当然,在实践中,除了使用经典的条件变量唤醒的方式,还有就是通过管道:生产者向管道写命令,消费者在管道阻塞的读命令,这种方式可以天然的使用read/write阻塞和非阻塞行为,同时也很方便融入现在大量的异步框架中,这是在memcached中发现的,也算是一个编程的小技巧吧。
  对于单个生产者和单个消费者的情况比较的简单,每一端自身不存在竞争条件,使用round-robin Ring数组本身就可以实现无锁队列了,而链表因为元素和其前后驱有耦合性,所以问题要复杂一些。其他的数据结构还需要看底层的容器类型,比如std::queue就是个适配器类,底层的容器类型可以是std::deque或者std::list。反正这种情况下锁的竞争不会十分的激烈,在此就不再讨论了。

  对于成百上千的同构生产者和消费者,锁的竞争就会比较的激烈。提出这个问题的原因,是看到附录总的文章,mutex作为多线程最常用的同步手段,底层是用futex系统调用实现的,作者测试发现通过这种方式同步,大部分的时间都被浪费到了futex系统调用的开销上面了,其原理是通过系统调用陷入内核态,将当前线程放入到mutex的等待队列上面去,然后调度其它线程执行。不过我对作者第一篇测试99%的时间用于futex系统调用甚是怀疑,因为系统调用还涉及到信号处理、内核抢占等东西,把这笔账全部算在mutex很不公平。不过,系统调用陷入内核态,以及线程切换的过程中会有上下文的保存和加载,同时伴随着大量的缓存失效等,这算是连锁带来的实实在在巨大开销。同时,这也让我感觉到当前很多系统架构,动辄开很多的线程池是否真的值得有效:虽然线程池的创建的开销少了,但是线程间频繁切换以及带来的缓存失效,也会对性能造成巨大的负面影响。
lockfree

  所以,锁不是多线程开发的金钥匙,大量使用锁总是有害的(死锁、活锁、持锁线程挂起),同时也是程序的性能杀手,在所以在实践中除了小心使用、缩小锁保护的临界区之外,能使用无所的数据结构当然是最有效的提高性能的方法了。

  通过附录中的文章,基本对无锁队列的原理有一个大概的了解了,同时也意识到这类高性能的开发需要CPU架构、CPU缓存、编译器的特性、语言的特定模型等诸多知识,是同平台、编译器紧密相关的知识,但是抛却极致方面的最求,基本的思路都比较一致:
  a. 使用round-robin Ring数组而非链表作为存储结构,一方面如我所说元素之间耦合性低,涉及到的修改很少;二来数组这种顺序存储类型对CPU和缓存机制是十分友好的,同时不会频繁的申请和释放节点,不会有内存碎片的问题。
  b. 同步需求包括生产者之间、消费者之间以及队列饥饿和队列饱和的情况。同质者之间的竞争基本是采用“先占坑再埋坑”的思路,确保一个线程占用一个slot,做出修改之后再发布这个slot使其它线程可见,而具体实现有附录中用CAS的,也有用其他复杂检测的机制来实现的。关于队列饥饿和队列饱和,这种情况在实践中会经常的出现,因为生产者和消费者阻抗匹配是十分理想的情况,现实情况或多或少会有生产快于消费以及生产慢于消费的情况,而且这种差异会慢慢累积下去,所以对于round-robin Ring这种空队列和满队列需要格外考虑。

  参考文件中关于并发框架Disruptor译文我觉得还是很值的一读的,先不讨论Disruptor的实现原理,单单就高性能开发方面,就看着让人觉得大开眼界的感觉:
  a. 新名词,锁分为悲观锁和乐观锁,悲观锁是独占锁也就是常常遇到的独占锁,当一个线程获得该锁会阻止所有其他线程得到锁;乐观锁是当线程需要写入的时候会请求锁,检查上次读完后目标数据是否已经修改了,如果修改了会重新读取并比较,其行为很像CAS,但是让我感兴趣的是还没接触过CAS形式的锁。
  b. 处理器的缓存都是按照缓存行的形式组织的,一般一个缓存行64字节(或32-256字节),所以如果数组元素不大,那么缓存行对数组是十分友好的(后续元素预加载的效果),可以将数组接下来的元素都加载到缓存行中,而链表就没有这个优势了,相邻的元素很可能都无法命中缓存。但是结构中的数据,head和tail通常都是连续定义的,这导致的一个问题是head、tail常常会在同一个缓存行中,这时候修改了一个端会使缓存行失效,另外一段也就被“失效”了,称之为“伪缓存”,这里等于加剧了生产者和消费者的竞争,解决的方法是在两者之间添加一个cache line padding,迫使两者在不同的缓存行中。
  c. Disruptor的设计感觉对读描述的较少,用了ConsumerBarrier等于起到一个代理的作用,这个代理顺序分配当前的对象,同时也知道Producer当前已经发布的cursor位置,但是消费者消费完空出slot的信息不知道是怎么通知ProducerBarrier的,文中没有提到;同时消费者的速度有差异,慢的消费者处理完后可以跳过前面已经被消费的元素。这里看来,怎么维持一个全局最小的消费者cursor是个关键。
  d. 生产者采用了“先占坑再埋坑”的思路,先申请一个空闲的位置,然后填充对应的书,完成后提交这个数据称为消费者可见。生产者维持了一个全局的cursor,而提交更新这个cursor必须是顺序提交的,也就是即使前面的生产者已经完成了生产,也必须等待后面的生产者提交之后才能提交。

  附录文章Lock-Free Multi-Producer Multi-Consumer Queue on Ring Buffer则是实现的一个生产者消费者对称设计的无锁任务队列,基本数据结构是round-robin Ring数组,同时也是“先占坑再埋坑”的思路,不过“埋坑”的时候没有采用顺序提交的情况,而是每个生产者和消费者维持了自己的生产或者消费位置,最后程序可以协调让cursor快进,这在很大程度上减少的多个生产者、消费者空等待的情况。

  说了这么多的基础知识,然后就是的进行了一个简单的实现,借鉴了前面两者采用了最简单的实现方式:生产者和消费者对称设计、顺序提交的模式,使用CAS进行无锁同步。然后呢,我也像模像样地测试了一下,结果让我大跌眼镜:在16对生产者、消费者进行一千万次请求下,使用mutex和条件变量耗时3s,而我的无锁队列为18s,慢了整整6倍!!!

  后面看了下别人评论,现在CAS有被滥用的趋势,很多成熟的Lockfree方案在并发量大的时候会遇到瓶颈,甚至性能会急剧恶化下去。然后告诫就是:只有确定需要无锁结构,并且知道你在干什么的时候,才使用无锁结构!!!
  代码在lockless,忘大拿帮我看看有啥问题没?还是本身就应该是这么慢!

参考