并发相关结构：无锁队列与环形缓冲区

前面的大多数数据结构默认都生活在一个相对“安静”的世界里：

只有一个执行流在操作它；
读写顺序清晰；
不会同时有多个线程抢着插入、删除和查询。

但真实系统里，大量高性能服务都处在并发环境下。这时候，问题就变了：

结构本身对单线程很高效，还远远不够；它还必须在多个线程同时访问时保持正确，并且尽量少阻塞。

这就是并发数据结构出现的背景。无锁队列和环形缓冲区，正是两类非常典型的并发相关结构。它们并不一定是日常业务代码里天天手写的内容，但非常值得理解，因为它们能让你真正意识到：

数据结构设计，不只是时间复杂度；
还包括线程竞争、内存可见性、CAS、等待开销等现实约束。

一、为什么并发场景会让普通结构不够用

假设你有一个普通队列，在单线程里它很好用。但如果：

一个线程在入队；
另一个线程同时在出队；
第三个线程又在读队头；

如果没有额外同步机制，结构状态就可能被破坏。最常见的问题包括：

两个线程同时修改头尾指针；
数据还没写完就被别的线程读到；
某次更新被另一线程覆盖掉；
逻辑上应该有序的操作在时间上交错错乱。

所以并发环境下，结构设计必须额外考虑：

原子性；
可见性；
顺序性；
竞争开销。

二、什么是无锁队列

无锁队列通常指：

在多线程环境下，不依赖传统互斥锁来保证并发安全，而是主要借助原子操作实现正确入队和出队的队列结构。

“无锁”并不意味着完全没有同步，而是说：

不通过大粒度互斥锁把整个结构锁住；
而是尽量用更细粒度、非阻塞的方式协调并发访问。

它的目标通常是：

降低锁竞争；
提高吞吐；
避免线程因为锁被长期阻塞。

三、无锁结构为什么常和 CAS 一起出现

CAS，也就是 Compare-And-Swap，是很多无锁结构最核心的原子操作之一。

它的基本逻辑通常是：

检查某个位置当前值是否等于预期值；
如果相等，就原子地更新成新值；
如果不相等，说明别的线程已经改过了，本次失败，需要重试。

无锁队列之所以大量用到 CAS，是因为它能让多个线程在不加大锁的情况下，竞争性地安全更新头尾指针。

四、无锁队列的核心难点是什么

表面看起来只是“并发入队出队”，但实际上难点很多，例如：

多线程同时更新头尾指针；
节点已经被别的线程回收；
读到的是旧值还是新值；
ABA 问题；
内存屏障与可见性问题。

所以无锁结构的真正挑战，并不在于“代码少”，而在于正确性证明和边界处理非常复杂。

五、什么是环形缓冲区

环形缓冲区可以理解成：

用一个固定长度数组，在逻辑上把首尾连接起来，通过头尾指针循环移动实现持续读写的缓冲结构。

你可以把它想成一个首尾相接的环：

写指针一路往前写；
读指针一路往前读；
到末尾后就回到开头。

这和前面学过的循环队列有非常直接的联系，本质上就是循环队列思想在系统缓冲场景中的工程化体现。

六、环形缓冲区为什么特别适合生产者消费者模型

因为它非常适合：

一边持续写入；
一边持续读取；
数据像流水一样推进。

典型场景包括：

日志缓冲；
网络收发队列；
音视频流处理；
中间件消息传递；
高性能事件队列。

它的优势通常在于：

内存连续；
不需要频繁分配释放节点；
对缓存友好；
非常适合定长或流式数据。

七、环形缓冲区和链式队列有什么区别

1. 链式队列

更灵活；
不依赖固定容量；
但节点分散，指针开销大。

2. 环形缓冲区

连续内存；
固定容量；
很适合高速流式读写；
但容量上限明确，需要处理满 / 空状态。

所以环形缓冲区的强项不是“通用”，而是“高吞吐、低开销、连续缓冲”。

八、并发环形缓冲区为什么很常见

因为在很多生产者消费者场景里，最重要的不是结构有多灵活，而是：

写入快；
读取快；
不要频繁 malloc / free；
不要把 CPU 浪费在锁竞争上。

于是环形缓冲区就成了非常自然的选择，特别是在：

单生产者单消费者 SPSC；
多生产者多消费者 MPMC；

等模型中都会有很多经典实现变体。

九、为什么并发数据结构经常要分场景讨论

因为：

单生产者单消费者；
多生产者单消费者；
单生产者多消费者；
多生产者多消费者；

它们的复杂度完全不一样。

例如：

SPSC 环形缓冲区可以非常简洁高效；
MPMC 队列则通常复杂得多，需要更严密的同步设计。

这说明并发结构并不是“写个线程安全版就完了”，而是要结合实际并发模型做针对性设计。

十、并发数据结构为什么常强调无锁或低锁

因为锁并不是没有代价的。

加锁带来的问题通常包括：

线程阻塞；
上下文切换；
竞争激烈时吞吐下降；
死锁和优先级反转风险。

所以在高性能系统里，人们会尽量寻找：

无锁；
低锁；
或分段锁、无等待等设计。

这也是为什么并发数据结构会成为一个独立且很深的方向。

十一、学习并发结构时最容易踩的坑

1. 只看单线程复杂度，不看并发竞争成本

并发结构最贵的部分，很多时候不是算法本身，而是同步。

2. 误以为“无锁”就一定更简单或更快

无锁结构实现和调试都可能非常复杂。

3. 忽略内存可见性和原子性问题

这类问题单线程里根本不会暴露。

4. 不区分 SPSC、MPSC、MPMC 场景

不同模型差别非常大。

总结

并发相关结构的重要性，不只是因为它们高阶，而是因为它们让你真正看到：数据结构一旦进入多线程世界，设计目标就不再只是时间复杂度。真正值得先建立起来的，是这些核心认识：

并发环境下，数据结构必须额外处理原子性、可见性和竞争问题；
无锁队列通常借助 CAS 等原子操作来减少锁竞争；
环形缓冲区本质上是循环队列思想在流式缓冲和高吞吐场景中的工程化实现；
连续内存、顺序访问和固定容量，是环形缓冲区的典型优势；
并发结构的设计必须结合具体生产者消费者模型来看；
真正学会这部分，不是会写一段 lock-free 模板，而是理解“结构正确性 + 同步代价”才是并发数据结构真正的核心。

把这一篇理解透之后，后面再回看缓存、消息队列、事件驱动系统时，你会更容易把“数据结构”理解成系统性能的一部分，而不是只属于算法题世界的抽象概念。

参考资源：