无锁环形缓冲(Lock-free RingBuffer)，又称无锁管道，是一个在不使用锁的情况下允许多线程访问的缓冲区，是在竞争条件下维护数据的最高性能选择之一。该方法早在1994年的 Implementing Lock-Free Queues 论文中就开始被研究，该文尝试实现了无锁链表，而本文将尝试实现无锁的环形数组。
构成
一个RingBuffer主要包含如下字段：
- buf 缓冲数组，每个元素作为结构体node，包含了pos字段表示元素位置，data字段表示用户插入的数据。
- cap 容量，整数
- mask 容量减一，整数
- queue 插入数据的指针，整数
- dequeue 获取数据的指针，整数
- disposed 是否停止阻塞，布尔
方法有如下：
- Put(v) 插入数据
- Get() 获取数据
- Cap() 获取容量
- Len() 数据数量
- Dispose() 中断阻塞
算法过程
下面用图来分析插入和获取数据的过程。
一开始，一个容量为4的缓存区里面每个node都自带从0开始递增的pos，queue和dequeue指针都是0。
当插入数据时，会在queue指向的位置插入数据，该位置pos加一；然后queue指针会移动指向下一个node，即值加一。
同理，我们再依次插入两个数据，这时queue为3，指向第4个node。
当获取数据时，会获取dequeue指向的位置的数据，然后该位置的pos=dequeue+cap，dequeue移动到下一个node，即加一。之所以pos=dequeue+cap是为了表示该位置已经空出，以便于插入时能通过queue判断出这一情况。
我们继续插入数据，这次会把数据插入到第4个node中，然后queue移动。
当获取数据后，第一个node就空了出来，意味着我们可以把数据插入到第一个node中。
当插入数据时，会作判断，必须是pos-queue=0时，我们才认为可以在该位置插入该数据，如果pos-queue<0，意味着该位置的数据还没被获取，你不能去覆盖它，一般遇到这种情况会在一个循环中阻塞，直到该位置的数据被Get()或者被Dispose()。实际实现时，pos, queue等属性可能会作为无符号整型，pos-queue<0的判断则应该变为pos-queue>0。
若想获得当前缓冲区中有多少数据还没被获取，即Len()函数，则只要queue-dequeue即可。若想中断阻塞或将管道改为非阻塞，则只需要将disposed字段置为true，循环会自行打断。程序实现可以参考我写的这一版rtd/ringbuf.h。
无锁原因
之所以环形缓冲能实现无锁，是因为采用了双指针和CAS。双指针分别指向插入数据位置和获取数据位置，读写时互不干扰，唯一会发生干扰的情况就是当缓冲区满了，两者指向同一位置，必须等到该位置数据被Get之后，即其中一个指针被移开，数值发生了变化后，才能继续插入，而又这里仅仅涉及数值上的比较和更改，这部分完全可以简化为CAS原子操作。
Golang里面的channel用的也是类似方法，但也并非完全无锁，作为标准库必须最大程度确保安全，侧面说明了目前无锁队列的研究并没有完全结束。最理想的情况应该是基于链表实现的无锁队列，因为链表可以实现动态扩容，而环形数组会遇到装满后而必须阻塞的情况。无锁环形数组比较著名的应用有Disruptor，而无锁链表尽管多年来出了不少论文，但在工业上被使用的情况还是很少。
Comments