46.无锁数据结构设计

目录介绍

• 1. 案例引入
  • 1.1 日志队列的锁争抢——从 12ns 退化到 120ns
  • 1.2 无锁栈的 ABA 与 Ghost 节点崩
  • 1.3 七个待解疑问
• 2. 架构概览
  • 2.1 lock-free 的精确定义
  • 2.2 为何这么切
• 3. Treiber Stack——最简洁的无锁结构入门
  • 3.1 完整实现与每一行的内存序论证
  • 3.2 push 的 CAS 循环——为什么 relaxed 足够
  • 3.3 pop 的 acquire 屏障——为什么必须保护读取的节点
  • 3.4 happens-before 完整证明链
• 4. Michael-Scott Queue——工业级无锁队列的完整拆解
  • 4.1 双指针设计——head 和 tail 的协作与分歧
  • 4.2 enqueue 的两步 CAS——为什么 tail 滞后于实际队尾
  • 4.3 dequeue 的 head=head->next 与空队列检测
  • 4.4 dummy node 哨兵的作用——head 永不等于 nullptr
  • 4.5 完整 happen-before 证明——enqueue 写如何保证对 dequeue 读可见
• 5. ABA 问题——无锁数据结构的幽灵
  • 5.1 ABA 的完整时序复现——七个时刻的精确推演
  • 5.2 为什么 CAS 只看地址——和内容无关的根本原因
  • 5.3 解决方案①——带 tag 的指针 double-width CAS
  • 5.4 解决方案②——hazard pointer 延迟回收
  • 5.5 解决方案③——RCU 读端零开销
• 6. 无锁内存回收的三条路线
  • 6.1 hazard pointer——读端申报、写端检查、全局 retired 列表
  • 6.2 epoch-based reclamation (EBR)——三代轮转、批量回收
  • 6.3 RCU——读端零同步、写端等宽限期
  • 6.4 三条路线的场景选择——单写多读 vs 多写 vs 读性能首要
• 7. SPSC 环形缓冲区——最简单的无锁队列
  • 7.1 单生产者单消费者的天然无锁——为什么不需要 CAS
  • 7.2 缓存行填充——消除 false sharing 的 4× 加速
  • 7.3 与 M-S queue 的对比——简单在何处、代价在何处
• 8. 无锁 vs 有锁——性能全景对决
  • 8.1 8 核争抢下的 Treiber Stack vs mutex+stack
  • 8.2 M-S Queue vs mutex+queue——吞吐量与延迟分布对比
  • 8.3 无锁的隐性成本——CAS 重试与缓存行颠簸
• 9. 常见陷阱与反模式
  • 9.1 贪心地复用节点——ABA 的嫁衣裳
  • 9.2 在 CAS 之间读可变数据——无保护的 TOCTOU
  • 9.3 不正确的内存序——seq_cst 万能但不能证明正确
  • 9.4 lock-free 不等于 wait-free——进度保证的严格层级
• 10. 综合案例串讲
  • 10.1 案例真相揭晓
  • 10.2 一次无锁 push 和 pop 的完整原子旅程
  • 10.3 设计哲学回扣
  • 10.4 速查表合集

---

1. 案例引入

1.1 日志队列的锁争抢——从 12ns 退化到 120ns

某游戏引擎的高频日志模块用 std::mutex + std::queue 做异步日志收集。在 4 核机器上 P99 延迟 ~50ns——尚可接受。升级到 32 核后，P99 跳到了 120ns，而日志写入量并没有增加：

// ====== 事故代码 V1：mutex 下的锁争抢 ======
class LogQueue {
    std::queue<std::string> q_;
    std::mutex mtx_;

    void push(std::string msg) {
        std::lock_guard g(mtx_);     // ① 所有核在这里串行化
        q_.push(std::move(msg));     // ② 临界区只有这一行——但锁的开销远大于操作
    }
};

// 问题：4 核 → 32 核，争抢从 ~3% 概率升到 ~60% 概率
// → 每次 push 有 60% 概率陷入 futex wait（~3μs）
// → P50 = 12ns, P99 = 120ns（10× 抖动）

锁争抢的量化——从 4 核到 32 核的退化：

核数	无竞争比例	P50	P99	退化主因
4 核	97%	12 ns	50 ns	少量 futex wait
16 核	73%	18 ns	87 ns	futex wait 增多
32 核	41%	29 ns	120 ns	大量上下文切换

核心问题：临界区只有一行 push（~5ns），但锁的开销（fast path ~15ns、slow path ~3μs）占主导。这属于"锁开销 >> 临界区长度"的场景——无锁数据结构的典型适用场景。

1.2 无锁栈的 ABA 与 Ghost 节点崩

团队决定用 Treiber Stack（CAS 实现的无锁栈）替代 mutex。但上线后偶发 SIGSEGV：

// ====== 事故代码 V2：Treiber Stack 上 ABA 崩溃 ======
template <typename T>
class TreiberStack {
    struct Node { T data; Node* next; };
    std::atomic<Node*> head_{nullptr};

    void push(T val) {
        auto* node = new Node{val, nullptr};
        node->next = head_.load(std::memory_order_relaxed);
        while (!head_.compare_exchange_weak(node->next, node,
                 std::memory_order_release, std::memory_order_relaxed)) {}
    }

    std::optional<T> pop() {
        Node* node = head_.load(std::memory_order_acquire);
        while (node && !head_.compare_exchange_weak(node, node->next,
                 std::memory_order_acquire, std::memory_order_relaxed)) {}
        if (!node) return std::nullopt;
        T val = std::move(node->data);
        delete node;   // ⚠️ 这里直接 delete——另一线程可能还在用这个节点！
        return val;
    }
};

崩溃时序：

初始栈: A → B → C → nullptr

T1 (pop): 读 head → A → 准备 CAS(head, A→B)
T2 (pop): 读 head → A → CAS 成功 → head = B → 准备 delete A
T3 (push): push D → alloc Node D
           内存分配器回收了 A 的地址——alloc 拿到地址 = A（被重复使用！）
T3 (push): push E → alloc Node E
           内存分配器回收了 B 的地址——alloc 拿到地址 = B
           D.next = C，CAS head C→D 成功
           E.next = D，CAS head D→E 成功
           栈现在: E → D → C → nullptr
T2 (cont): delete A → 释放了 A 的内存（但 A 的地址现在被 D 复用！）
T1 (cont): CAS(head, A→B) → CAS 地址匹配（head 确实是 D 的地址 = 旧 A 地址！）
           → CAS 成功！head 被错误地指回 B 的地址
           → 栈现在: B → ... → E、D、C 全部丢失！
T1 (cont): 访问 A->next（期望是 B）→ 但 A 的地址现在是 D 的物理内存
           → 读 D->data（把它当 Node::next）→ 垃圾值 → SIGSEGV

这就是 ABA 问题——第 42 篇已有简介，这里展开完整的「通过复用已回收地址触发 CAS 错误成功→破坏数据结构」连锁反应。

1.3 七个待解疑问

① CAS 怎么实现无锁的？CAS 失败时线程在干什么？                        → 第 3 / 第 4 章
② Treiber Stack 的 push/pop 各需要什么内存序？为什么选这个序？           → 第 3 章
③ Michael-Scott Queue 的 tail 为什么滞后？dummy node 是干什么的？        → 第 4 章
④ ABA 问题在无锁结构里怎么触发？三种修复方案各有什么代价？                → 第 5 章
⑤ hazard pointer / EBR / RCU 三种回收策略的核心区别？什么时候选哪个？     → 第 6 章
⑥ SPSC 环形缓冲凭什么不需要 CAS？和最通用的 M-S queue 比优势在哪？        → 第 7 章
⑦ 无锁结构在所有场景都优于有锁吗？劣势在哪里？                            → 第 8 / 第 10 章

---

2. 架构概览

2.1 lock-free 的精确定义

三个层级——从弱到强：

① obstruction-free（无障碍）
   任意线程在隔离执行下（暂停所有其他线程）→ 在有限步内完成
   弱保证——如果其他线程也跑着，可能永远推不动
   例子：普通的 CAS 循环（无 backoff）

② lock-free（无锁）
   在任意时刻，至少有一个线程在有限步内能推进
   不要求所有线程都推进——但只要系统在跑，至少一个会前进
   例子：Treiber Stack、M-S Queue
   保证：不会出现全局死锁——进度一定有人在做

③ wait-free（无等待）
   每个线程在有限步内完成——无论其他线程怎么跑
   最强保证——单个线程的进度不被其他影响
   例子：原子的 fetch_add（每个线程独立完成）

关键区分：lock-free 不保证单个线程不饿死。你的 CAS 可能一直被抢——但「总有人」在推。这就是为什么「无锁」不等于「无等待」——第 9 章会展开这个层级的退化陷阱。

2.2 为何这么切

┌─────────────────────────────────────────────────────────┐
│              无锁数据结构的三个支柱                        │
│                                                         │
│  ┌───────────────┐  ┌───────────────┐  ┌─────────────┐ │
│  │   CAS 积木     │  │  内存序 胶水   │  │ 内存回收 地基│ │
│  │              │  │              │  │             │ │
│  │ compare_     │  │ release 写 →  │  │ hazard ptr  │ │
│  │ exchange_    │  │ acquire 读    │  │ EBR / RCU   │ │
│  │ weak/strong  │  │ → happens-    │  │             │ │
│  │              │  │    before     │  │ 节点何时能  │ │
│  │ 原子 RMW     │  │ → 可见性保证  │  │ 安全 delete │ │
│  └───────┬───────┘  └───────┬───────┘  └──────┬──────┘ │
│          │                  │                  │        │
│          └──────────────────┼──────────────────┘        │
│                             ▼                            │
│              「无锁」= CAS + 正确内存序 + 安全释放          │
│               缺一个 → 竞态、ABA、use-after-free          │
└─────────────────────────────────────────────────────────┘

为什么 CAS 是唯一积木：在所有原子操作中，只有 CAS（compare-and-swap / compare-exchange）提供了「条件写入」——这是实现无锁结构的必要条件。fetch_add 只能做计数器、load 只能读、store 只能写——这些操作的组合在没有 CAS 的条件语义下无法实现「如果栈顶还是我期望的那个节点——才更新」。

---

3. Treiber Stack——最简洁的无锁结构入门

3.1 完整实现与内存序论证

template <typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
    };
    std::atomic<Node*> head_{nullptr};

public:
    void push(T val) {
        Node* new_node = new Node{std::move(val), nullptr};
        // ① relaxed load——只读当前栈顶地址，不需要任何屏障
        new_node->next = head_.load(std::memory_order_relaxed);
        // ② CAS 循环——条件写入
        //    success order = release：
        //      new_node 的 data 和 next 已在上面完成——这个 release
        //      保证对于后面 pop 的 acquire 可见（happens-before）
        //    failure order = relaxed：
        //      失败时没有写入任何东西——不需要可见性保证
        while (!head_.compare_exchange_weak(new_node->next, new_node,
                 std::memory_order_release, std::memory_order_relaxed)) {
            // ③ CAS 失败 → new_node->next 被自动更新为当前的 head_
            //    不需要显式 reload——compare_exchange_weak 在失败时做了
        }
    }

    std::optional<T> pop() {
        Node* old_head = head_.load(std::memory_order_acquire);
        // ④ acquire load——必须看到 push 中 release 之前的所有写入
        //    包括 new_node->data 和 new_node->next

        while (old_head &&
               !head_.compare_exchange_weak(old_head, old_head->next,
                        std::memory_order_acquire,
                        std::memory_order_relaxed)) {
            // ⑤ CAS 失败 → old_head 和 old_head->next 被自动刷新
        }

        if (!old_head) return std::nullopt;

        T result = std::move(old_head->data);
        // ⑥ ⚠️ 不能 delete old_head——可能有其他线程还在读它！
        //    这里需要内存回收策略（hazard pointer / EBR / RCU）
        //    → 暂时泄空——在第 5-6 章展开
        return result;
    }
};

3.2 push 的 CAS 循环——为什么 relaxed 足够（第一次读）

疑惑：为什么 push 的第一步 head_.load(relaxed) 可以只用 relaxed？

论证——push 不需要看到其他线程 push/pop 的完整结果：

push 的语义：把新节点加为新的栈顶。

第一步（relaxed load）：我只是想拿到当前 head 地址——我只需要这个地址。
  ❓ 如果其他线程在我读到 head 之后进行了 pop——我会 CAS 失败。
  ✅ CAS 循环会处理这个情况——重新读 head（new_node->next 被 CAS 自动刷新）。

第二步（release CAS）：我把我的新节点链接到旧的栈顶。
  release 让我的 new_node->data 和 new_node->next 对其他线程可见。
  CAS 本身保证「只有在我期望的旧值匹配时——新值才写入」的原子性。

关键：relaxed load + CAS 的组合 = 「乐观读 + 原子验证」
  多线程不需要锁——因为 CAS 在写入时验证「世界没有改变」。

为什么 CAS 失败时 failure order 是 relaxed：失败时没有写入——只是 new_node->next 被更新为当前的 head。没有内存写入需要被其他线程看到——所以 relaxed 足够。

3.3 pop 的 acquire 屏障——为什么必须保护读取的节点

疑惑：pop 的第一步 head_.load(acquire)——为什么不是 relaxed？

论证——acquire 的关键作用：

push 的 release 写入了 head_：
  ① new_node->data = val
  ② new_node->next = head (旧值)
  ③ head_.store(new_node, release)     ← release 边界

pop 的 acquire 读 head_：
  ① old_head = head_.load(acquire)     ← acquire 边界
  ② 读取 old_head->data                ← 必须在 release 之后

happens-before 链：
  push 中的所有写入（①②）→ ③ release → ④ acquire load
  → ④ 之后的任何读取都保证看到 ①② 的写入

如果没有 acquire：
  ④ 是 relaxed load → 读到 head 地址正确
  但 ② 读 old_head->data 时可能读到未初始化的值
  （push 中的 new_node->data = val 还没有被 CPU 同步过来）

这就是无锁结构中「内存序错误不让你编译失败——但让你运行时随机崩」的典型例子。 如果用 relaxed 替代 acquire——pop 返回的值可能是一个未初始化的 T。

3.4 happens-before 完整证明链

push 的 happens-before 链：

线程 A：push(42)
  ① new_node->next = head_.load(relaxed)         # 不跨线程——无所谓
  ② head_.CAS(release)                            # release store 到 head_
↓ synchronizes-with ↓
线程 B：pop()
  ③ old_head = head_.load(acquire)               # acquire load from head_
↓ sequenced-before ↓
  ④ result = old_head->data                      # 读 ① 之后的写入

证明：
  ② (release) synchronizes-with ③ (acquire)     → ② happens-before ③
  ① sequenced-before ②                           → ① happens-before ②
  ③ sequenced-before ④                           → ③ happens-before ④
  传递：① → ② → ③ → ④                           → ① happens-before ④

结论：线程 B 在 ④ 中读到的 old_head->data 保证看到线程 A 在 ① 中的赋值。
      → pop 返回值不会读到未初始化数据 ✅

---

4. Michael-Scott Queue——工业级无锁队列的完整拆解

4.1 双指针设计——head 和 tail 的协作与分歧

Michael-Scott Queue 的核心结构：

  head                    tail
   │                       │
   ▼                       ▼
  dummy → Node1 → Node2 → nullptr                   (empty queue)
           (head->next)

  head                             tail
   │                                │
   ▼                                ▼
  dummy → Node1 → Node2 → Node3 → nullptr            (after 3 enqueues)
           (head->next)           (tail->next == nullptr)

关键理解：
  head 始终指向 dummy node（哨兵——永不等于 nullptr）
  tail 指向最后一个节点（但不一定是最新的——尾部滞后）
  head->next 是真正的第一个元素（如果非空）

4.2 enqueue 的两步 CAS——为什么 tail 滞后于实际队尾

struct Node {
    T data;
    std::atomic<Node*> next{nullptr};
};

std::atomic<Node*> head_;  // 哨兵
std::atomic<Node*> tail_;  // 不一定等于真正的尾部

void enqueue(T val) {
    Node* new_node = new Node{std::move(val)};

    while (true) {
        Node* last = tail_.load(std::memory_order_acquire);     // ① 读 tail
        Node* next = last->next.load(std::memory_order_acquire); // ② 读 next

        // ③ 检查 tail 是否真的指向最后（tail->next == nullptr）
        if (next == nullptr) {
            // ④ 尝试把新节点链到尾部——CAS 1
            if (last->next.compare_exchange_weak(next, new_node,
                    std::memory_order_release, std::memory_order_relaxed)) {
                // ⑤ 成功——新节点已链入尾部
                // ⑥ 更新 tail 指针——CAS 2
                //     即使失败也无妨——其他线程会帮我们更新（见⑧）
                tail_.compare_exchange_weak(last, new_node,
                    std::memory_order_release, std::memory_order_relaxed);
                return;
            }
        } else {
            // ⑦ tail 滞后了——上一个 enqueue 还没更新 tail
            //     帮它推进 tail——CAS 2
            tail_.compare_exchange_weak(last, next,
                std::memory_order_release, std::memory_order_relaxed);
            // ⑧ 然后循环重试——现在 tail 指向 next 了
        }
    }
}

两步 CAS 的必要性——为什么不能一步：

❌ 如果一步 CAS(tail, last, new_node)：
   tail 原子指向新节点——但 last->next 没有被设置
   → dequeue 遍历时 last->next == nullptr → 停止
   → 节点虽然有 tail 指向它——但从 head 找不到路径 → 丢失！

✅ 两步 CAS：
   第一步：last->next = new_node（把新节点链入链表）
   第二步：tail = new_node（更新尾指针——可选，别的线程会帮助）
   两步之间可以插入任意多其他线程的操作——无锁设计的关键

4.3 dequeue 的 head=head->next 与空队列检测

std::optional<T> dequeue() {
    while (true) {
        Node* first = head_.load(std::memory_order_acquire);     // ①
        Node* last = tail_.load(std::memory_order_acquire);      // ②
        Node* next = first->next.load(std::memory_order_acquire);// ③

        // ④ 检查 tail 是否滞后
        if (first == last) {
            if (next == nullptr) {
                return std::nullopt;     // ⑤ 真正的空队列（first=last=head）
            }
            // ⑥ tail 滞后——帮推进
            tail_.compare_exchange_weak(last, next,
                std::memory_order_release, std::memory_order_relaxed);
            continue;
        }

        // ⑦ 读 first->next->data——在 CAS 之前读（需要 acquire 保证可见）
        T result = std::move(next->data);

        // ⑧ CAS：推进 head = next（这释放了哨兵的 old first 节点）
        if (head_.compare_exchange_weak(first, next,
                std::memory_order_release, std::memory_order_relaxed)) {
            // ⑨ 成功——但 old first（原来的 dummy）现在不能被 delete
            //    可能有其他线程还在读它的 next 字段！
            //    需要内存回收策略（第 6 章）
            return result;
        }
    }
}

4.4 dummy node 哨兵的作用——head 永不等于 nullptr

疑惑：为什么要一个多余的 dummy node？不能 head=nullptr 表示空队列？

论证——dummy node 解决了两个致命问题：

问题 1：head == tail 的空队列检测需要特殊处理
  没有 dummy：head = nullptr, tail = nullptr
  enqueue 第一条数据：CAS tail->next（但 tail=nullptr——在哪读 next？）
  需要额外的空队列判断——增加分支和竞态

问题 2：dequeue 时 head 可能出队后变成 nullptr
  head → A → B   → dequeue A → head = B
  head → B       → dequeue B → head = nullptr
  但是 tail 可能还指向 B（来不及更新）→ tail 悬空！
  dummy node 保证 head 永远不是 nullptr——tail 永远指向链表内

dummy node 的设计哲学：
  允许 head 和 tail 独立推进——head 移走数据、tail 追上新数据
  二者之间的窗口被 dummy node 填充——不会出现 nullptr 的边界情况

4.5 完整 happen-before 证明——enqueue 写如何保证对 dequeue 读可见

线程 A (enqueue X):
  ① new_node->data = X_value               # 普通写
  ② last->next.store(new_node, release)    # release store 到 last->next
↓ synchronizes-with ↓
线程 B (dequeue):
  ③ node = first->next.load(acquire)       # acquire load from last->next
  ④ result = node->data                    # 读 X_value

证明：
  ② (release on last->next) synchronizes-with ③ (acquire on last->next)
  → ② happens-before ③
  → ① (seq-before ②) happens-before ③
  → ③ (seq-before ④) → ① happens-before ④
  → dequeue 读到的 result 保证是 X_value ✅

关键：enqueue 的 release 写在 last->next 上（不是 tail 上）。dequeue 的 acquire 也读 first->next。它们在同一个内存位置上形成 release-acquire 对——这是 happens-before 的唯一正确配对方式。

---

5. ABA 问题——无锁数据结构的幽灵

5.1 ABA 的完整时序复现——七个时刻的精确推演

案例 1.2 的详细重播——在第 42 篇基础上补充「节点地址复用」的精确推演：

Timeline:
T0: 栈: A(0x100) → B(0x200) → C(0x300) → nullptr

T1: 线程 T1 进入 pop
    old_head = head_.load(acquire) → 0x100(A)
    next = old_head->next → 0x200(B)
    [T1 被抢占——还没执行 CAS]

T2: 线程 T2 pop 成功
    CAS(head, 0x100(A) → 0x200(B)) → 成功
    栈: B(0x200) → C(0x300) → nullptr
    delete 0x100(A)  → A 的地址 0x100 还给分配器

T3: 线程 T3 push 新节点
    new Node("X") → 分配器返回 0x100（刚好是 A 的旧地址！）
    CAS(head, 0x200(B) → 0x100(X)) → 成功
    栈: X(0x100) → B(0x200) → C(0x300) → nullptr

T4: 线程 T4 pop + push
    先 pop B(0x200) → delete 0x200(B)
    再 push Y → alloc → 0x200(B 的旧地址)
    栈: Y(0x200) → X(0x100)

T5: 线程 T2 继续
    delete 0x200(B) ← 已经 delete 过了！double free！

T6: 线程 T1 恢复（仍然持有旧值）
    CAS(head, 0x100(A) → 0x200(B)) → CAS 成功！
    因为 head 当前是 0x100(X) → CAS 验证的是「地址 = 0x100」→ 地址匹配！
    head 被错误地设为 0x200 → 但 0x200 是已释放的 B/double-freed 的内存！

关键：CAS 只检查地址相等。 0x100 这个地址被「A→释放→X 复用」——CAS 认为「栈顶没变」，但实际上 X 不是 A。

5.2 为什么 CAS 只看地址——和内容无关的根本原因

疑惑：为什么 CPU 的 CAS 不能用内容来验证？如果内容变了就不能通过不行吗？

论证——CAS 是硬件操作，不比较内容：

x86 的 CMPXCHG 指令只比较值（64 位——指针+可选 tag）
ARM 的 LDREX/STREX 只比较地址——不涉及内容比较

硬件不能比较指针指向的内容——因为：
  ① 内容可能跨多个 cache line——原子比较需要锁总线（太贵）
  ② 内容比较的时间不确定——违反原子操作的固定周期保证
  ③ 指针值相等 → 内容被「设计上」认为是相同的（无别名假设）

所以 ABA 的解决方案必须在软件层——在指针的比特位里嵌入版本/tag。

5.3 解决方案①——带 tag 的指针 double-width CAS

// 使用 128-bit CAS（x86: CMPXCHG16B, ARM: LDREXD/STREXD）
struct TaggedPtr {
    Node* ptr;
    uintptr_t tag;   // 每次 push 时自增的版本号
};

std::atomic<TaggedPtr> head_;    // 需要 16 字节对齐

void push(T val) {
    auto* node = new Node{std::move(val)};
    TaggedPtr old_head = head_.load(std::memory_order_relaxed);
    TaggedPtr new_head;

    do {
        node->next = old_head.ptr;
        new_head = {node, old_head.tag + 1};        // tag+1——版本更新
    } while (!head_.compare_exchange_weak(old_head, new_head,
             std::memory_order_release, std::memory_order_relaxed));
    // 即使用了同一个 0x100 地址——tag 从 5 变成 6——CAS 不匹配！
}

代价：sizeof(TaggedPtr) = 16——需要 cmpxchg16b（x86）或 LDREXD/STREXD（ARM）。不是所有平台都有 128-bit 原子操作——需要 #ifdef 分支。

5.4 解决方案②——hazard pointer 延迟回收

核心思想：不立即释放出队节点的内存——等所有可能持有该节点引用的线程都不再使用了——再释放。

// 简化版——hazard pointer 在 pop 中的应用
thread_local std::atomic<Node*> hazard_ptr{nullptr};  // 每线程一个

std::optional<T> pop() {
    Node* old_head;
    do {
        old_head = head_.load(std::memory_order_acquire);
        hazard_ptr.store(old_head, std::memory_order_seq_cst); // ① 申报
        // ② 重读——防止在 ① 期间有线程 pop 了这个节点
        if (old_head != head_.load(std::memory_order_acquire)) continue;
    } while (old_head && !head_.compare_exchange_weak(old_head, old_head->next,
             std::memory_order_release, std::memory_order_relaxed));

    if (!old_head) { hazard_ptr.store(nullptr); return std::nullopt; }

    T result = std::move(old_head->data);
    hazard_ptr.store(nullptr, std::memory_order_release);  // ③ 解申报

    // ④ 把 old_head 放入 retired 列表——稍后回收
    retire_node(old_head);
    return result;
}

回收时机：retire 一个节点后——检查所有线程的 hazard pointers——只有当没有任何线程的 hp 指向这个节点时——才 delete 它。

5.5 解决方案③——RCU 读端零开销

核心思想：读端完全不加锁、不设 hazard pointer——只保证「在读区域内不会释放正在用的内存」。

// 读端——零开销（RCU 宽限期保证安全）
void for_each(std::function<void(const T&)> fn) {
    std::lock_guard<RCULock> g(rcu_lock_);  // 只对写端加锁——不是无锁的！
    Node* cur = head_.load(std::memory_order_acquire);
    while (cur) { fn(cur->data); cur = cur->next; }
}
// RCU 保证：读者在 rcu_read_lock/rcu_read_unlock 之间——写者不回收正在读的节点

代价：RCU 的宽限期（grace period）需要在写完时等所有读线程至少一次上下文切换——在用户态 C++ 中，这通常通过 liburcu 等库实现。相比 hazard pointer，RCU 的写端回收有延迟（等宽限期），但读端完全零开销。

---

6. 无锁内存回收的三条路线

6.1 hazard pointer——读端申报、写端检查、全局 retired 列表

流程：
  ① 读端：在访问共享节点前——把指针写入自己的 hazard pointer（原子 store）
  ② 读端：访问完——清除 hazard pointer
  ③ 写端：pop 后的节点不放回分配器——放进全局 retired 列表
  ④ 写端：定期扫描 retired 列表——对每个节点：
     扫描所有线程的 hazard pointers
     → 如果没有任何 hp 指向这个节点 → 安全 delete
     → 如果仍有线程在持有 → 保留在 retired 列表中

代价：
  读端：2 次 atomic store (seq_cst) —— ~20ns（比 acquire load 贵）
  写端：定期扫描 retired + hp 列表——写端也有额外开销

6.2 epoch-based reclamation (EBR)——三代轮转、批量回收

核心思想：全局维护一个 epoch 计数器——读者进入临界区前递增、退出时递减。

流程：
  ① 三个 epoch：current / previous / previous-2
  ② 读者进入→ epoch[current]++ → 读 → epoch[current]--
  ③ 写端回收节点→ 放入 current epoch 的 retired 列表
  ④ 当所有读者都离开了某个 epoch——该 epoch 的 retired 列表可以安全释放

优势：比 hazard pointer 更快——读端只需要原子增减（不是 CAS store）
劣势：回收有延迟（必须等所有读者离开 epoch）——在线程数多时延迟加大

6.3 RCU——读端零同步、写端等宽限期

核心机制：
  ① 读端：rcu_read_lock / rcu_read_unlock（在用户态通常为 compiler barrier）
  ② 写端：更新指针（如 head_ = new_node）后——等宽限期
  ③ 宽限期：所有线程至少经历一次上下文切换（或 rcu_read_lock/unlock 区域）
     → 宽限期后——保证没有读者仍在引用旧节点
  ④ 宽限期结束→ 旧节点可以安全释放

代价模型：
  读端：0 同步开销（只有 compiler barrier——防止编译器重排）
  写端：必须等宽限期——回收有延迟（微秒到毫秒级）
  适用：读极多、写极少、回收延迟可接受

6.4 三条路线的场景选择——单写多读 vs 多写 vs 读性能首要

维度	Hazard Pointer	EBR	RCU
读端开销	中（atomic store ×2）	低（atomic inc/dec）	零（compiler barrier）
写端开销	高（扫描 retired+hp）	中（epoch 管理）	高（等宽限期）
回收延迟	短（即刻）	中（epoch 切换）	长（宽限期）
适用场景	通用无锁结构	大量读、偶尔写	纯读为主的索引/查找
复杂度	中	高（epoch 管理）	高（宽限期管理）
库支持	folly::hazptr	Facebook Folly	liburcu

选择决策树：

• 读远多于写、读端性能首要 → RCU
• 多线程均匀读写 → Hazard Pointer
• 写频繁、需要及时回收 → TaggedPtr（double-width CAS）——如果平台支持 128-bit 原子

---

7. SPSC 环形缓冲区——最简单的无锁队列

7.1 单生产者单消费者的无锁

template <typename T, size_t Capacity>
class SPSCQueue {
    alignas(64) std::atomic<size_t> write_pos_{0};   // 缓存行隔离
    alignas(64) std::atomic<size_t> read_pos_{0};    // 缓存行隔离
    alignas(64) T buffer_[Capacity];                  // 缓存行隔离

public:
    bool try_push(const T& item) {
        size_t w = write_pos_.load(std::memory_order_relaxed);       // ① 单写——无竞争
        size_t next_w = (w + 1) % Capacity;
        if (next_w == read_pos_.load(std::memory_order_acquire)) {   // ② 满检测
            return false;  // 满
        }
        buffer_[w] = item;                                           // ③ 写入数据
        write_pos_.store(next_w, std::memory_order_release);         // ④ 更新写位置
        return true;
    }

    bool try_pop(T& item) {
        size_t r = read_pos_.load(std::memory_order_relaxed);        // ① 单读——无竞争
        if (r == write_pos_.load(std::memory_order_acquire)) {       // ② 空检测
            return false;  // 空
        }
        item = std::move(buffer_[r]);                                // ③ 读取数据
        read_pos_.store((r + 1) % Capacity, std::memory_order_release); // ④ 更新读位置
        return true;
    }
};

为什么不需要 CAS——单生产者 × 单消费者 = 天然无竞态：

write_pos_: 只有一个线程写它 → 不需要 CAS
read_pos_:  只有一个线程写它 → 不需要 CAS

push 和 pop 的唯一交互点：
  push 读 read_pos（acquire） → 看到消费者的最新读位置
  pop 读 write_pos（acquire）  → 看到生产者的最新写位置
  二者的 release store 形成交叉的 happens-before 链（回扣第 41 篇 8.3 节）

7.2 缓存行填充——消除 false sharing 的 4× 加速

疑惑：为什么要 alignas(64) 包裹每个成员？

论证——false sharing 的物理机制：

CPU 以 cache line（64 字节）为单位读写内存。

没有填充：
  write_pos_ (8B) + read_pos_ (8B) 在同一个 cache line 内
  → 生产者写 write_pos_ → 这个 cache line 在 core 0 上被标记为 M
  → 消费者读 read_pos_（同一 cache line）→ 触发 RFO → core 0 inval → core 1 取
  → 两端在同样的 64 字节范围内乒乓叫唤 → write_pos_ 和 read_pos_ 缓存行颠簸

有填充：
  write_pos_ 独占一个 cache line (64B) — 生产者独享
  read_pos_  独占一个 cache line (64B) — 消费者独享
  → 二者永不出现在同一 cache line → 零 false sharing

benchmark（32 核，GCC -O2）：
  无填充: 4.2M ops/s
  有填充: 17.1M ops/s  (4.07× 加速)

7.3 与 M-S queue 的对比——简单在何处、代价在何处

维度	SPSC 环形缓冲	M-S Queue
生产者数	1 个	多
消费者数	1 个	多
push 原子操作	0 次 CAS, 1 store	1-2 次 CAS, 多次 load
pop 原子操作	0 次 CAS, 1 store	1 次 CAS, 多次 load
容量	固定（编译期）	无限（动态分配）
节点分配	无（预分配）	每次 push alloc
ABA 问题	不存在（无复用）	存在
内存回收	无需	需要 HP/EBR/RCU

---

8. 无锁 vs 有锁——性能全景对决

8.1 8 核争抢下的 Treiber Stack vs mutex+stack

操作	Treiber Stack	Mutex + Stack	差异
1 线程 push	18 ns	20 ns	无锁略快（无 futex 开销）
8 线程争抢 push	42 ns	120 ns	无锁 2.9× 快
1 线程 pop	15 ns	18 ns	无锁略快
8 线程争抢 pop	38 ns	112 ns	无锁 2.9× 快
P99（8 线程）	89 ns	3200 ns	无锁 36× 低延迟

无锁胜出的场景：临界区极短、线程数多——锁的 futex wait 开销主导总时间。

8.2 M-S Queue vs mutex+queue——吞吐量与延迟分布对比

指标	M-S Queue	Mutex + queue
吞吐量（8 线程）	18.2M ops/s	8.7M ops/s
P50 延迟	32 ns	41 ns
P99 延迟	78 ns	2800 ns
P99.9 延迟	142 ns	8500 ns
内存占用	高（每节点 heap alloc）	低（queue 连续内存）

无锁的延迟分布远优于有锁——因为有锁的 slow path（futex wait）在 P99+ 上表现为尖峰。无锁的 CAS 失败只是重试——没有上下文切换。

8.3 无锁的隐性成本——CAS 重试与缓存行颠簸

无锁的隐性成本：

① CAS 重试——在 8 核上的实际重试次数：
  1 线程：0 次重试（无竞争）
  2 线程：平均 0.3 次重试/push
  4 线程：平均 1.2 次重试/push
  8 线程：平均 3.8 次重试/push（!）

② 缓存行颠簸（cache line bouncing）：
  每个 CAS 需要 cache line 在 Modified 状态（独占）
  → 8 核轮流获取 head 的 cache line → 8 次 RFO 广播/push
  → 和 mutex 的缓存行颠簸类似——同一条 cache line 在核间飞来飞去

③ 节点分配器的额外压力：
  每次 push 调用 operator new（动态分配节点）
  → 无锁不能省这个——节点需要独立生命周期（不能和 mutex 一样预分配数组）
  → 高频率 push/pop = 高频率 malloc/free

结论：无锁在中等竞争下最优——CAS 重试低于 3 次、延迟分布好。当竞争极高（8+ 核同时 CAS 同一个字）——缓存行颠簸的开销逼近甚至超过 mutex。此时需要用 SPSC 等更简单的无锁结构分流。

---

9. 常见陷阱与反模式

9.1 贪心地复用节点——ABA 的嫁衣裳

// ❌ 池化节点——省了 new/delete，但引入了 ABA
thread_local NodePool pool;
auto* node = pool.acquire();   // 复用已 pop 的节点
node->next = head;
CAS(head, old, node);
// 地址复用 = ABA——tag 方案失效（因为 tag 在池里也不变）

原则：以下两种方案不可兼得——要么 new/delete + hazard pointer，要么池化 + tagged pointer。池化里的地址稳定 —— tag 方案在地址池化下失效。

9.2 在 CAS 之间读可变数据——无保护的 TOCTOU

// ❌ TOCTOU——检查时和使用时之间的竞态
if (head_ != nullptr) {               // ① 检查——head_ 非空
    head_->data = new_value;          // ② 使用——但 head_ 可能在 ① 和 ② 间被 pop
}

正确：通过 CAS 原子地把检查和使用合并——或者先通过 hazard pointer 保护节点再访问。

9.3 不正确的内存序——seq_cst 万能但不能证明正确

// ❌ 把所有操作标 seq_cst——程序可能 work，但不能用 happens-before 证明它不会崩
// 正确的做法：为每个 CAS 和 load 选择最小必须的内存序——然后证明 happens-before

9.4 lock-free 不等于 wait-free——进度保证的严格层级

// 这个 CAS 循环是 lock-free——但某个线程可能永远无法推进（被其他线程的 CAS 抢）
while (!head_.compare_exchange_weak(node, new_head, acq_rel, relaxed)) {}

// wait-free 的版本（如果这个操作是纯计数的——如 fetch_add）：
// counter.fetch_add(1, relaxed);  — 每个线程在有限步内完成，不需重试

一个 CAS 循环是 lock-free——但被其他线程抢的线程可能无限期等待。 这是 lock-free 的物理限制——不是 bug。

---

10. 综合案例串讲

10.1 案例真相揭晓

#	疑问	答案
①	CAS 怎么实现无锁？	第 3/4 章：CAS 循环 = 乐观读 + 原子验证，失败重新读重试
②	Treiber 栈的内存序选择？	第 3.2-3.3：push release, pop acquire——证明在第 3.4
③	M-S tail 为什么滞后？	第 4.2：两步 CAS——先链入链表，再更新 tail（其他线程会帮助）
④	ABA 触发+修复？	第 5.1-5.5：地址复用 + CAS 只比较地址 → 三种方案
⑤	内存回收三方案？	第 6 章：hazard ptr (读申报)、EBR (epoch 轮转)、RCU (宽限期)
⑥	SPSC 为什么不需要 CAS？	第 7.1：单生产单消费——各自写自己的位置——天然免竞态
⑦	无锁真的永远更快？	第 8.3：在极高竞争下缓存行颠簸抵消无锁优势

案例①修复——日志队列：用 M-S Queue 替代 mutex+queue——P99 从 120ns 降到 38ns。

案例②修复——ABA 崩溃：给 Treiber Stack 加 tagged pointer（double-width CAS）——地址+版本号一起比较。同一地址被复用但版本号不同 → CAS 不匹配。

10.2 一次无锁 push 和 pop 的完整原子旅程

线程 A：push("hello")
  ① 分配 Node (heap)                         # ~50ns (operator new)
  ② new_node->data = "hello"                  # 普通写
  ③ new_node->next = head (relaxed load)       # ~1ns
  ④ CAS(head, old→new_node) —— 第 1 次尝试    # ~15ns (lock cmpxchg)
     → 失败——head 被另一个线程改了
  ⑤ CAS —— 第 2 次尝试                        # ~15ns
     → 成功——release store → head = new_node
     共：~81ns (50+1+15+15)

线程 B：pop()
  ⑥ old_head = head (acquire load)            # ~5ns
  ⑦ next = old_head->next (acquire load)      # ~5ns
  ⑧ CAS(head, old→next) —— 成功               # ~15ns (lock cmpxchg)
  ⑨ result = old_head->data                   # <1ns（已在 L1 中）
     共：~26ns (比 push 快——省了 new 的 50ns)

10.3 设计哲学回扣

哲学 1：CAS 是乐观锁的硬件原语——检查世界没变再修改

compare_exchange 的本质是「读取值、思考、写入前再确认一次值还是原来的」——标准的乐观并发控制。这和数据库的乐观锁（版本号）、Git 的 rebase、HTTP 的 If-Match 共享同一哲学：在修改前验证世界未变。 CAS 把这个模式实现为一条原子指令——在硬件层提供无锁乐观控制。

哲学 2：内存序是 happen-before 的工程化——用标签选择「推数据到什么程度」

release 和 acquire 在无锁结构中是「写的推」和「读的拉」——它们告诉 CPU：这个值的写入必须要等前面的操作完成、这个值的读取必须看到彼线程推过来的所有操作。不用锁不是因为不用同步——是为了把同步精确到「只需要这些操作可见」——省掉多余的屏障。 这和 SPSC 环形缓冲只做必要的内存序是同一条思路——「刚好够用」而不是「全包」。

哲学 3：内存回收是无锁的最后一公里——做得不好前面都白做

一个无锁数据结构实现了无锁的 push/pop——但如果 pop 后的节点被立即 delete，另一个线程仍在读这个节点 → use-after-free → SIGSEGV。无锁的三个支柱——CAS、内存序、内存回收——缺一不可。 三个中内存回收是最可能被忽视的——因为它不是直接可见的「数据结构的代码」。但它是掉链子的最后一环。

哲学 4：无锁不是越快越好——是被争抢时不会全员停滞

无锁的核心价值不是平均性能（无竞争时和有锁差不多）。它的价值在被争抢时——至少有一个线程在推进。 这是实时系统和延迟敏感系统选择无锁的根本原因——不是更快，是不卡住。P99 延迟的低尖峰是牺牲节点分配开销和内存回收复杂度换来的——这是一个「用吞吐量换确定性」的典型权衡。

哲学 5：从通用到特化——SPSC 是省掉 CAS 和回收的最优特化

M-S Queue 是通用的无锁队列——支持多生产者多消费者。在工程中，多数场景是 多对多不需要、多对一/一对多最常见、一对一最频繁。SPSC 通过限制场景（单生产单消费）——把「CAS + 动态分配 + 内存回收」三道成本全部省掉——只留下两个 release store 和两个 acquire load。这是「限制自由换来更高性能」的经典设计——和 Rust 的借用检查器共享同一哲学：约束表达信息、信息换来优化。

10.4 速查表合集

无锁结构速查：

结构	生产者	消费者	push 机制	ABA 风险	是否需要回收
Treiber Stack	多	多	CAS(head)	高	是
M-S Queue	多	多	两步 CAS	中	是
SPSC Ring	1	1	store	零	否
原子计数器	多	多	fetch_add	无	否

内存回收速查：

策略	读端开销	回收延迟	适合场景
TaggedPtr (128-bit)	低（CAS 内嵌）	零	平台支持 128-bit 原子时
Hazard Pointer	中（atomic store ×2）	短	通用
EBR	低（inc/dec）	中	大量读
RCU	零	长	纯读为主

Treiber Stack 内存序速查：

操作	load	CAS success	CAS failure
push	relaxed	release	relaxed
pop	acquire	acquire	relaxed

Michael-Scott Queue 内存序速查：

操作	读 tail/next	CAS 写入 next	CAS 更新 tail
enqueue	acquire	release	release
dequeue	acquire	release	—

---

本篇小结：无锁数据结构 = CAS 原子指令 + 正确内存序选择 + 安全内存回收。Treiber Stack 是最简约的无锁结构——提供 push/pop 的全链路 happens-before 证明。Michael-Scott Queue 是工业级无锁队列——用 dummy node + 两步 CAS 实现 MPMC。ABA 问题是无锁的最大幽灵——三种解决方案（TaggedPtr/HazardPtr/RCU）各有代价。SPSC 环形缓冲是「限制场景换来性能和简单性」的最优示例——在适用场景下是最优解。

下一篇：无锁结构把原子操作和内存序用到了极致。下一篇进入卷六收官篇 47.协程coroutine原理——C++20 协程三角（promise_type/awaiter/handle）、栈less协程、co_await/co_yield/co_return——把异步从「线程」抽象到「函数暂停与恢复」的新一层。