无锁队列ConcurrentLinkedQueue原理详解

ConcurrentLinkedQueue 并非真正“等待无关”（Wait-Free），而是更务实的“无锁”（Lock-Free）设计：它通过纯用户态的 CAS 自旋重试避免线程阻塞和调度开销，虽不保证单线程操作的有限步完成，却确保系统整体持续进展；借助傀儡节点、tail/head 的懒更新策略巧妙降低竞争冲突，以牺牲 size() 的实时准确性为代价换取高性能与可扩展性——理解其精妙权衡，才能避开生产环境中的典型误用陷阱。

ConcurrentLinkedQueue 的 Wait-Free 不是“完全不等待”，而是“不阻塞、不挂起、不依赖调度”——它靠无限重试 + CAS 成功即返回，来规避锁带来的线程切换开销。

Wait-Free 和 Lock-Free 的区别在哪？

很多人把 ConcurrentLinkedQueue 说成 Wait-Free，其实它属于更宽松的 Lock-Free（无锁），不是严格意义上的 Wait-Free（等待无关）。关键区别在于：

• Wait-Free 要求：每个线程在有限步内必完成自己的操作，不管其他线程是否运行、是否暂停
• Lock-Free 只保证：整个系统总有一个线程能取得进展（即不会全局死锁），但单个线程可能无限重试
• ConcurrentLinkedQueue 的 offer() 和 poll() 都可能因 CAS 失败而循环重试，没有上界步数保证 —— 这就是典型的 Lock-Free，不是 Wait-Free

为什么 CAS 循环重试不算“等待”？

所谓“不等待”，是指不进入 OS 级等待状态（如 WAITING 或 BLOCKED），不交出 CPU 时间片。它的重试是纯用户态自旋：

• 每次 CAS 失败后，立刻用 UNSAFE.compareAndSwapObject 重读最新 head 或 tail 地址，再试一次
• 没有 Thread.sleep()、没有 LockSupport.park()、不触发 JVM 线程状态变更
• 在低争用时，通常 1～2 次 CAS 就成功；高争用下可能几十次，但仍是“忙等”，不是“挂起等”

傀儡节点和延迟更新如何降低 CAS 频率？

如果每次插入都强制把 tail 精确指向真实尾节点，CAS 冲突会爆炸式增长。它用两个设计压降重试次数：

• 初始化时 head == tail 指向同一个 item == null 的傀儡节点，所有真实数据插在它之后
• tail 不严格追尾：允许它“滞后”一到多个节点，只在必要时（比如发现 tail.next != null）才用 CAS 推进 —— 这叫“懒更新”
• 同理，head 也不总指有效元素，poll() 时先跳过傀儡或已删除节点，再尝试推进，避免每次读都更新 head

size() 返回不准是设计使然，不是 bug

size() 必须遍历链表计数，而 offer()/poll() 是无锁异步修改。这就导致：

• poll() 返回 null 但 size() > 0：说明 head 还卡在傀儡节点，而第一个真实节点已被其他线程标记为待删除（item = null），但尚未推进 head
• size() 可能漏掉刚 offer() 但还没连到 tail.next 的节点（还在本地变量里）
• 所以生产代码中，永远不要用 size() 做逻辑判断（比如 “if (q.size() > 0) q.poll()”），应直接 poll() 并判空

真正难啃的是 CAS 失败后的重试路径是否覆盖所有竞态，以及傀儡节点清理时机 —— 这些细节藏在 updateHead() 和 findNode() 里，不看源码很难凭直觉写对等价逻辑。

到这里，我们也就讲完了《无锁队列ConcurrentLinkedQueue原理详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！