无锁队列并非真的无锁

近几年经常被提起的无锁队列,似乎被视为解决高并发的万能良药。无锁队列是一种通过CPU提供的原子操作指令 CASFAA,以及循环重试,来实现的乐观并发控制算法。虽然无锁队列算法并未显式调用锁,但事实上,在多核环境下,所谓的无锁队列算法本质上就是实现了锁的功能。

首先,原子指令本身就是一种带锁的操作,只是锁的颗粒度较小而已。单核 CPU 系统的情况比较简单,因为单条指令操作总是原子的;而 SMP 的情况就比较复杂了,需要使用缓存一致性(Cache Coherence)的机制来确保操作的原子地执行。

早期 CPU 不支持原生的 CMPXCHG 指令,要实现 CAS 原子操作,必须先用 LOCK 指令锁住总线或需要访问的内存块。

Intel Core i7 处理器

Intel Core i7 处理器

从上图可以得知,每个 CPU 核心都有对应的本地缓存。由于系统存在多套缓存,必然导致数据一致性问题。CPU 通过缓存一致性协议(Cache Coherency Protocols)来解决这个问题。虽然不同协议的实现方式不同,但是为了保证 CPU 数据写入的事务串形化,都会隐含实现锁的功能。

其次,由于无锁队列是一种乐观并发控制的实现,所以必须处理 CAS 失败的情况。为了尽可能地保证写入成功,需要不断重试 CAS 操作,直到写入成功为止。这种类似于自旋锁的机制会导致一定的 CPU 开销。随着并发数的上升,CAS 操作失败的几率会上升,最终导致耗尽 CPU 资源。某些优化算法就是在重试循环中加入 Sleep 指令来降低 CPU 开销。

此外,在设计无锁队列的数据结构时,还需要避免伪共享(False Sharing)现象。即在频繁写入的数据附近加入填充数据,以避免 CPU Cache 失效而带来的性能损失。

伪共享

伪共享

伪共享,即多个 CPU 内核缓存了相同地址的 Cache Line。当其中一个 CPU 内核修改了该内存,导致其他 CPU 内核中的 Cache Line 失效,从而引发的性能问题。