C++ 无锁队列：从有界数组到 Hazard Pointers 内存回收

Table of Contents

前言：面试官到底想考察什么？

在 C++ 高级开发或基础架构的面试中，手写“无锁队列（Lock-Free Queue）”是一道极其硬核的考察题。很多候选人会基于简单的静态数组和 compare_exchange_weak 尝试实现一个多生产者-多消费者队列。

然而，真正的 Lock-Free 实现远比想象中复杂。单纯依赖头尾指针的 CAS 竞争，往往会陷入退化为自旋锁、消费者数据竞争以及ABA问题的泥潭。本文将带你经历无锁编程的四重境界，从扫盲到底层机制，彻底看透并发数据结构的底层逻辑。

第一重境界：为什么直觉写出的“无锁数组”往往是错的？

初学者通常会使用三个原子变量 head、tail 和 write 来控制并发：生产者通过 CAS 抢占 tail 槽位，写完数据后循环等待更新 write；消费者顺着 head 读取数据。这种设计在实际工程和面试中都是扣分项，主要存在三个致命缺陷：

违背无锁语义（假无锁，真自旋）： 如果一个生产者在抢到槽位后被操作系统挂起，后续所有抢到槽位的生产者都会在更新 write 时陷入无限循环等待（Spinlock）。这违背了无锁编程“系统中至少有一个线程在有限步内取得进展”的严谨定义。
读写数据竞争（Data Race）： 多个消费者并发执行 pop 时，通常会先读取数据再执行 CAS 更新 head。如果队列中存放的是复杂对象（如 std::string），多线程并发读写同一个对象会导致极大概率的段错误（Segmentation Fault）。
极严重的伪共享（False Sharing）： 将 head、tail 连续声明在同一个缓存行（Cache Line）中，高并发下会导致 CPU 多核之间的 L1/L2 缓存频繁失效，性能暴跌。

第二重境界：满分答卷——基于 Sequence 的工业级有界队列

为了解决上述问题，工业界的标准解法（例如 Dmitry Vyukov 提出的经典算法，被广泛应用于各路高并发网络库）是为环形数组的每一个槽位（Cell）分配一个独立的原子序列号（Sequence）。

这种设计的精妙之处在于：将“抢占槽位”和“确认数据可读/可写”操作，通过序列号的状态机完美绑定，彻底消除了全局的 write 锁等待和数据读写竞争。

C++ 核心代码实现

#include <atomic>
#include <cstddef>
#include <new>

// 硬件缓存行大小，通常为 64 字节，用于防止伪共享
#define HARDWARE_DESTRUCTIVE_INTERFERENCE_SIZE 64

template<typename T>
class MPMCQueue {
private:
    struct Cell {
        std::atomic<size_t> sequence;
        T data;
    };

    // 使用按位与(&)代替取模(%)提升性能，要求容量必须是 2 的幂
    size_t const buffer_mask_;
    Cell* const buffer_;

    // 强制对齐，防止 head 和 tail 落在同一个缓存行中产生伪共享 (False Sharing)
    alignas(HARDWARE_DESTRUCTIVE_INTERFERENCE_SIZE) std::atomic<size_t> enqueue_pos_;
    alignas(HARDWARE_DESTRUCTIVE_INTERFERENCE_SIZE) std::atomic<size_t> dequeue_pos_;

public:
    // 容量必须是 2 的幂
    explicit MPMCQueue(size_t buffer_size)
        : buffer_mask_(buffer_size - 1)
        , buffer_(new Cell[buffer_size])
        , enqueue_pos_(0)
        , dequeue_pos_(0) 
    {
        // 初始化每个槽位的序列号为它的初始索引
        for (size_t i = 0; i != buffer_size; i += 1) {
            buffer_[i].sequence.store(i, std::memory_order_relaxed);
        }
    }

    ~MPMCQueue() {
        delete[] buffer_;
    }

    // 禁用拷贝和赋值
    MPMCQueue(MPMCQueue const&) = delete;
    void operator=(MPMCQueue const&) = delete;

    bool push(T const& data) {
        Cell* cell;
        size_t pos = enqueue_pos_.load(std::memory_order_relaxed);
        for (;;) {
            cell = &buffer_[pos & buffer_mask_];
            size_t seq = cell->sequence.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)pos;

            // 槽位的 seq 等于当前期望的 pos，说明该槽位为空且轮到我们写入
            if (dif == 0) {
                if (enqueue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) {
                    break; // 成功抢占槽位
                }
            } else if (dif < 0) {
                return false; // 队列已满
            } else {
                pos = enqueue_pos_.load(std::memory_order_relaxed); // 其他线程已修改，更新重试
            }
        }

        // 抢占成功，当前线程独占该槽位，安全写入数据
        cell->data = data;
        // 写入完成后，将 seq 加 1，向消费者发出“可读”信号
        cell->sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& data) {
        Cell* cell;
        size_t pos = dequeue_pos_.load(std::memory_order_relaxed);
        for (;;) {
            cell = &buffer_[pos & buffer_mask_];
            size_t seq = cell->sequence.load(std::memory_order_acquire);
            intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);

            // 槽位的 seq 等于 pos + 1，说明数据已由生产者写入完毕，可以消费
            if (dif == 0) {
                if (dequeue_pos_.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) {
                    break; // 成功抢占消费权
                }
            } else if (dif < 0) {
                return false; // 队列为空
            } else {
                pos = dequeue_pos_.load(std::memory_order_relaxed);
            }
        }

        // 安全读取数据
        data = cell->data;
        // 读取完成后，将 seq 更新为下一次该槽位被写入时的期望 seq
        cell->sequence.store(pos + buffer_mask_ + 1, std::memory_order_release);
        return true;
    }
};

核心亮点解析（面试官的加分项）

精确的内存序（Memory Ordering）： 拒绝无脑使用极其昂贵的 seq_cst。在读取时使用 memory_order_acquire，更新时使用 memory_order_release。在 ARM 架构（如 M 芯片）下能带来数倍的性能提升。
彻底解决 ABA 与挂起： 队列的 pos 是一直递增的。每个 Cell 拥有自己的状态机 sequence。如果某个生产者挂起，只会停留在自己的 Cell 里，完全不会阻挡其他线程操作其他槽位（真正的 Lock-Free）。
消灭伪共享（False Sharing）： 使用 alignas 将关键原子变量强制对齐到硬件缓存行大小（64 Bytes），消除了高并发下生产者和消费者之间的 Cache Line 互相失效。

第三重境界：突破容量限制——无锁链表与 MS Queue

有界数组虽然性能极高，但在很多场景下，我们无法预估队列的峰值容量。如果需要一个无界（Unbounded）的无锁队列，就必须使用链表。

工业界最著名的无锁链表队列是 Michael-Scott Queue (MS Queue)（也是 Java 中 ConcurrentLinkedQueue 的底层算法）。

MS Queue 的核心思想与“协作机制”：

链表始终包含一个虚拟头节点（Dummy Node）。
入队（Push）需要两步 CAS：
- CAS 1： 将新节点链接到当前 tail 节点的 next 指针上。
- CAS 2： 将全局的 tail 指针向后移动，指向新节点。
互助推进： 因为 Push 操作被拆分成了两步，如果线程 A 完成了 CAS 1 后被挂起，线程 B 进来发现 tail->next 不为空，B 会主动帮助 A 执行 CAS 2（推进 tail），然后才去干自己的活。这正是 Lock-Free “系统总在前进”的完美体现。

第四重境界：深渊挑战——安全内存回收（SMR）

在 C++ 中实现无锁链表，你会撞上一堵极高的墙：内存回收（Safe Memory Reclamation）。

在具有垃圾回收（GC）的语言中，出队的节点只要没有引用就会被自动清理。但在 C++ 中，如果我们对出队的节点直接执行 delete，极易引发灾难：

幽灵读取： 消费者 A 读取了 head 准备执行 CAS；此时消费者 B 飞速完成了 Pop，并把该节点 delete 了。线程 A 醒来继续访问被释放的内存，直接 Core Dump（段错误）。如果这块内存被系统重新分配，还会引发经典的 ABA 问题。

为了在 C++ 中实现真正的无锁链表，必须引入高级内存回收机制，目前有两大主流流派：

1. 风险指针（Hazard Pointers）

核心思想：“在看之前，先打个招呼”。

每个线程都有一个自己私有的“风险指针”列表。当线程 A 想要访问某个节点时，先把该节点的地址写进自己的 Hazard Pointer 中。
当线程 B 试图销毁一个节点时，不能直接 delete，而是把它放进“待释放链表”。当积累到一定数量时，B 会扫描所有线程的 Hazard Pointers。如果发现该节点还在被别人看着，就留到下次再说；如果没有人看，才安全地 delete 它。

2. 基于世代的回收（Epoch-Based Reclamation, EBR）

吞吐量极高的机制，思想类似于 Linux 内核的 RCU（Read-Copy-Update）。

维护一个全局的“世代（Epoch）”计数器。每个线程执行操作前，宣布自己进入了当前世代。
弹出的待释放节点被打上当前世代的标签。
当所有活动线程都离开了世代 N（或进入了世代 N+1 以后），系统就可以断定：绝对没有任何线程还在访问世代 N 摘除的节点。此时系统会一次性安全地批量回收旧世代内存。

总结：无锁编程的取舍艺术

面试进行到这一步，你向面试官展示的不仅是写出几行代码，而是对于并发系统的宏观架构能力：

确定边界： 如果容量可知且要求极致低延迟，首选基于 Sequence 的有界环形数组（无内存分配、无 ABA 节点问题、Cache 友好）。
面对无界： 如果必须使用动态容量，选择 MS Queue 链表结构，并向面试官阐述其“线程互助”推进的思想。
敬畏内存： 在 C++ 环境下脱离 GC 谈无锁链表就是耍流氓，必须引入 Hazard Pointers 或 EBR 才能构建可用于生产环境的基础架构。

C++ 无锁队列：从有界数组到 Hazard Pointers 内存回收

AI 摘要