Gaussdb(DWS)无锁队列介绍

无锁队列旨在解决多线程资源争抢时加锁造成的性能慢问题，Gaussdb(DWS)无锁队列已经作为公共组件可以被其他模块调用。相比网络上其他的无锁队列实现，Gaussdb(DWS)无锁队列因为其良好的设计具备了更为出色的性能，据测试，Gaussdb(DWS)无锁队列在性能上优于其他实现3倍以上，如此强大的实现，今天就一起来了解一下。

一、Gaussdb(DWS)无锁队列数据结构

Gaussdb(DWS)无锁队列数据结构如下所示：

class ArrayLockFreeQueue {
public:
    ArrayLockFreeQueue();
    virtual ~ArrayLockFreeQueue();

    int Initialize(uint32_t queueSize, MemoryContext context = NULL);
    uint32_t Size();
    bool Push(void *data);
    void *Pop();

private:
    void **m_theQueue;                                     //存储数组
    volatile char* volatile m_written;                  //辅助数组：表示数据正在写入
    volatile uint32_t m_queueSize;                     //存储数组的大小

    volatile uint32_t m_indexCompare;              //比较下标，用于将数组转化为环状
    volatile uint32_t m_writeIndex;                    //写下标
    volatile uint32_t m_readIndex;                     //读下标
    volatile uint32_t m_maximumReadIndex;    //最大可读下标

    inline uint32_t CountToIndex(uint32_t count);
};

队列作为一种C++容器适配器，无锁队列也不例外，从方法上讲，其包含了普通队列的Size()、Pop()、Push()操作。

从成员变量而言，无锁队列内部由一个大小为m_queueSize的数组实现，用以存储队列元素；读下标和写下标分别对应数组中对应的当前可读和可写的元素，顾名思义，Pop操作就是读出读下标对应的元素，Push操作就是将元素写入写下标对应的位置。从读下标往右，一直到写下标，都是可读元素，如下图所示：

上图中，蓝色元素表示可读，黄色元素表示可写/为空，可以看出，当下标m_readIndex大于m_writeIndex时，可读元素实际上在数组中呈环状，为了在环状读写中获得正确的下标，Gaussdb(DWS)无锁队列定义了无锁队列比较下标m_indexCompare，其值为m_queueSize-1，所以当下标按序增长时，只要做index&m_indexCompare就可以得到正确下标。

在这里，请读者理解一个概念，或者是在此约定，可读并不代表读到准确的数据，试想这样的一个场景：

当线程A做push操作时，首先step1，将m_writeIndex更新为m_writeIndex+1；然后step2，将数据放入m_theQueue[m_writeIndex]。在这两步之间，如果读到了m_theQueue[m_writeIndex]，显然会产生数据同步问题。为了避免这种情况，定义了最大可读下标m_maximumReadIndex表征可读准确数据的最大下标。（为什么不是先执行step2，再执行step1呢？，请大家思考）

至此，就介绍了Gaussdb(DWS)无锁队列所有的成员变量和方法，函数CountToIndex即就是根据m_indexCompare计算访问数据的正确下标。

二、Gaussdb(DWS)无锁队列方法实现

无锁队列的实现，就是队列+CAS操作，本章将介绍Gaussdb(DWS)无锁队列的Push和Pop操作

（1）Push

Push（）操作的执行逻辑如下图所示，首先获取当前最新的写下标和读下标，然后根据读写下标判断队列是否已满，判断条件为：写下标向后移动一位为读下标（由于Gaussdb(DWS)下标超出size后不做转换，所以读下标需要+size大小），有人一定会困惑，此时当前写下标不是还有一个空闲位置吗？但是由于当读下标等于写下标时，即可能代表队列空，也可能代表队列满，具有二义性。所以规定写下标向后移动一位为读下标代表满队列，此时已经不可以写了，因此，遍历队列中的所有元素，其实是遍历size-1次队列元素。

若队列未满，则首先更新写下标，这样别的线程就不会和本线程写数据冲突，更新失败，需要重新获取读/写下标（已经被其他线程更新）再次更新写下标；写下标更新完成后，则将需要push的数据放置在数组中；紧接着，将辅助数组的对应位置置1，表示数据已写入，但是最大可读下标未更新。然后利用CAS操作对最大可读下标进行更新，这里多线程存在竞争，更新失败说明该线程A使用的写下标前还有线程B未更新最大可读下标，通常情况下，线程A需要等待线程B将最大可读下标更新后再更新，这里线程A的动作是什么也不干进行等待，降低了效率，但是由于Gaussdb(DWS)无锁队列有辅助数组标明了数据已经放置在数组中，因此线程A可以直接退出，由线程B后续检查后一位置的m_Written值，对最大可读下标进行更行。更新完毕后，将m_Written置0，表示最大可读下标更新完成。

（1）Pop

Pop（）操作的执行逻辑如下图所示，首先获取当前最新的写下标和读下标，然后根据读写下标判断队列是否为空，判断条件之前已经分析过，读写下标相等时认为队列空。然后利用CAS操作修改读下标，返回数据即可。

最后，补充说明下函数CountToIndex的使用，他的使用场景为需要根据读下标访问数组元素时先行调用。