2. 无锁数据结构：从互斥锁到CAS，再到无锁队列的演进之路

说到并发编程，锁是个绕不开的话题。我刚开始做高频交易系统那会儿，团队里有个老哥特别喜欢用互斥锁，觉得简单可靠。结果呢？系统延迟动不动就飙到微秒级，交易信号都凉了锁还没解开。嗯，今天我们就聊聊这条演进之路——从互斥锁到CAS，再到无锁队列。

2.1 互斥锁：简单但昂贵

互斥锁（Mutex）是最基础的同步手段。它的逻辑很简单：谁拿到锁，谁就进临界区。但代价呢？

• 上下文切换：线程拿不到锁时，操作系统会把它挂起，换另一个线程跑。这一挂一换，几百纳秒就没了。
• 缓存颠簸：锁释放后，其他线程抢锁，缓存行在多个核心间来回传递。
• 优先级反转：低优先级线程拿着锁，高优先级线程只能干等。

我在项目中遇到过最夸张的一次：一个简单的计数器，用互斥锁保护，结果在16核机器上跑出了单核的性能。说白了，锁成了整个系统的瓶颈。

2.2 CAS：硬件级的原子操作

CAS（Compare-And-Swap）是CPU提供的一条原子指令。它的语义很简单：

bool CAS(int* addr, int expected, int new_value) {
    if (*addr == expected) {
        *addr = new_value;
        return true;
    }
    return false;
}

你想想看，这比互斥锁强在哪？不阻塞。线程发现CAS失败，可以立刻重试，或者做别的事。没有上下文切换，没有内核态开销。

但CAS也不是银弹。我刚开始用CAS时踩过一个坑：ABA问题。线程1读到值是A，然后被切出去了。线程2把A改成B又改回A。线程1回来一看，嗯，还是A，CAS成功。但中间的状态变化完全丢失了。

2.3 从CAS到无锁队列

有了CAS，我们就可以构建更高级的无锁数据结构。无锁队列是其中最经典的。它的核心思想：多个生产者、多个消费者同时操作，不需要任何锁。

我常用的无锁队列实现有两种：

类型	原理	适用场景
有界环形队列	固定大小的数组，用CAS更新头尾指针	高频交易、实时数据流
无界链表队列	动态分配节点，CAS链接	消息队列、任务调度

这里我重点讲有界环形队列，因为高频交易里它用得最多。为什么？延迟可控。固定大小意味着不会动态分配内存，不会触发GC，不会出现不可预测的停顿。

2.4 无锁环形队列的实现要点

一个典型的无锁环形队列长这样：

template<typename T, size_t N>
class LockFreeQueue {
    std::atomic<size_t> head_{0};
    std::atomic<size_t> tail_{0};
    T buffer_[N];
    
public:
    bool push(const T& value) {
        size_t tail = tail_.load(std::memory_order_relaxed);
        size_t next = (tail + 1) % N;
        if (next == head_.load(std::memory_order_acquire)) {
            return false;  // 队列满
        }
        buffer_[tail] = value;
        tail_.store(next, std::memory_order_release);
        return true;
    }
    
    bool pop(T& value) {
        size_t head = head_.load(std::memory_order_relaxed);
        if (head == tail_.load(std::memory_order_acquire)) {
            return false;  // 队列空
        }
        value = buffer_[head];
        head_.store((head + 1) % N, std::memory_order_release);
        return true;
    }
};

注意看内存序的使用：memory_order_acquire 和 memory_order_release。这是无锁编程的精髓——用最轻量的内存屏障保证可见性。我见过有人图省事全用 memory_order_seq_cst，性能直接掉一半。

2.5 无锁队列的避坑指南

无锁队列看着简单，实际坑不少。我列几个常见的：

• 伪共享：head和tail如果在一个缓存行里，两个核心同时操作会互相拖慢。解决办法：把它们放到不同的缓存行里（用alignas(64)）。
• 内存回收：无锁链表队列里，节点被pop后不能立刻free，因为可能有其他线程还在读。我一般用Hazard Pointer或RCU来解决。
• ABA问题：前面说过了，带版本号的指针是标准解法。

我曾经在一个项目里用无锁队列做订单簿的更新通道。刚开始没注意伪共享，延迟在200ns左右。后来把head和tail分开缓存行，延迟直接降到80ns。嗯，有时候性能优化就是这么朴实无华。

2.6 性能对比：互斥锁 vs 无锁队列

我拿一个实际压测数据说话。场景：8个生产者，8个消费者，每个线程发100万条消息。

实现方式	平均延迟	P99延迟	吞吐量
互斥锁 + std::queue	1.2μs	8.5μs	8.3M msg/s
CAS + 无锁队列	180ns	420ns	55.6M msg/s

差距很明显。无锁队列的P99延迟只有互斥锁的1/20。在高频交易里，这意味着你能多处理几十笔交易。

2.7 本章小结

从互斥锁到CAS，再到无锁队列，本质上是从阻塞到非阻塞的演进。互斥锁让线程睡觉，CAS让线程自旋，无锁队列让线程各干各的。你想想看，在高频交易这种延迟敏感的场景下，哪个更合适？

当然，无锁编程不是万能药。它增加了代码复杂度，调试起来也更痛苦。我的建议是：先测量，再优化。如果互斥锁能满足性能要求，就别折腾无锁。但如果你的系统延迟要求是纳秒级的，嗯，无锁数据结构是你绕不开的路。