如何运用ConcurrentLinkedQueue的Wait-Free算法深入解析高并发队列的无锁化机制？

本文共计1028个文字，预计阅读时间需要5分钟。

Wait-Free表示每个线程的操作都能在有限步内完成，不依赖于其他线程的进度；Lock-Free则只保证至少有一个线程能进步，但单个线程可能无限重试。ConcurrentLinkedQueue 实际上是Lock-Free的，而非Wait-Free。它的offer()和poll()方法可能因CAS失败而循环重试，没有步数限制。

很多人误以为它 Wait-Free，是因为 Doug Lea 在注释里提过“wait-free algorithm”，但那是指 Michael & Scott 原始论文中的理想模型；JDK 实现做了简化：用延迟更新 head/tail 换取吞吐量，代价就是单次操作不可预测耗时。

关键点在于：它不阻塞、不挂起、不 yield，失败就立刻重读重试 —— 这才是你看到“高并发不卡死”的底层原因。

为什么 tail 不总在队尾，head 不总指有效元素

这是延迟更新策略的直接结果，不是 bug，而是性能权衡：

• tail 只在必要时推进：比如当前 tail.next != null，说明已有线程把新节点连上去了，这时才用 CAS 把 tail 跳到那个节点（hop two nodes）
• head 更保守：只在 poll() 成功删除一个节点后才推进；中间可能卡在傀儡节点（item == null），而真实数据节点已在链表中
• 多线程同时 poll() 时，某个线程删掉节点后会把原 head 的 next 设为自引用（p == q），触发其他线程回退到 head 重新扫描

所以 size() 遍历全链表计数时，可能数出 5 个节点；而此时 poll() 返回 null，只是因为 head 还没推进过去 —— 两者完全异步，不能互推。

CAS 失败后重试逻辑怎么写才不丢数据

源码里所有重试都围绕两个核心动作展开，必须严格遵循其模式：

• 在 offer() 循环中，每次 CAS 失败后先检查 p.next：若为 null，说明 p 仍是尾，继续重试；若不为 null，说明别人已连上新节点，那就先帮着把 tail 推进（casTail(t, q)），再重来
• 在 poll() 循环中，若 head.item == null，要尝试用 CAS 把 head 推到 head.next；失败则重读 head，而不是直接返回 null
• 永远不要在 CAS 失败后直接 return 或 throw，除非明确知道操作已无意义（比如 poll() 碰到自引用节点且 head == head.next）

漏掉“帮别人推进”这步，就会导致 tail 长期滞留，后续线程反复在旧位置竞争 CAS，实际吞吐反而下降。

什么时候不该用 ConcurrentLinkedQueue

它快，但快得有前提：

• 写多读少、或读写均衡场景下表现好；但纯读场景（比如只调 peek()）几乎无优势，因为 peek() 仍要处理傀儡节点逻辑
• 不允许 null 元素 —— offer(null) 直接抛 NullPointerException，这点和 LinkedList 不同，容易在线上踩坑
• size() 是 O(n) 遍历，高并发下调用会严重拖慢性能；需要长度建议改用 AtomicInteger 单独计数
• 内存占用比 ArrayBlockingQueue 高：每个元素额外带一个 Node 对象 + volatile 字段开销，在堆压力敏感场景需评估

真正难的是理解“无锁”不等于“无同步”——它把锁的开销转成了 CPU 循环和内存屏障，而这些成本在 GC 日志、火焰图里并不显眼，却实实在在吃掉了 L3 缓存带宽。