一、概述在 Java 并发编程中队列是一种极其常用的数据结构。JDK 提供了两类并发安全队列阻塞队列如LinkedBlockingQueue使用锁ReentrantLock实现当队列空或满时线程会阻塞。非阻塞队列如ConcurrentLinkedQueue基于 CASCompare And Swap无锁算法通过不断重试而非挂起线程来实现线程安全。ConcurrentLinkedQueue是一个无界、线程安全、非阻塞的队列底层采用单向链表结构。它遵循 FIFO先进先出原则不允许null元素。在高并发场景下其性能通常优于阻塞队列因为避免了线程上下文切换的开销。适用场景生产者-消费者模型、任务队列、事件处理等对吞吐量要求较高且不希望线程阻塞的场景。二、核心数据结构1. Node 节点类队列的每个元素被包装成一个Node对象private static class NodeE { volatile E item; // 节点存储的元素 volatile NodeE next; // 后继指针 Node(E item) { // 使用 Unsafe 直接设置 item 字段避免指令重排序问题 UNSAFE.putObject(this, itemOffset, item); } boolean casItem(E cmp, E val) { // 原子地替换 item 值 return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); } void lazySetNext(NodeE val) { // 延迟设置 next允许其他线程稍后才看到这个修改但性能更好 UNSAFE.putOrderedObject(this, nextOffset, val); } boolean casNext(NodeE cmp, NodeE val) { // 原子地设置 next 指针 return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); } // Unsafe 相关静态代码块获取字段偏移量 private static final sun.misc.Unsafe UNSAFE; private static final long itemOffset; private static final long nextOffset; static { try { UNSAFE sun.misc.Unsafe.getUnsafe(); Class? k Node.class; itemOffset UNSAFE.objectFieldOffset(k.getDeclaredField(item)); nextOffset UNSAFE.objectFieldOffset(k.getDeclaredField(next)); } catch (Exception e) { throw new Error(e); } } }关键点解释volatile修饰item和next保证多线程环境下的可见性一个线程修改后其他线程立刻看到最新值。Unsafe提供的 CAS 操作casItem和casNext是原子操作用于实现无锁并发修改。CAS 操作会检查预期值是否匹配匹配则更新为新值整个过程是原子的通过 CPU 指令cmpxchg实现。lazySetNext使用putOrderedObject它仍然保证了最终一致性但允许延迟写StoreStore 屏障不强制立即冲刷到主内存性能优于volatile写常用于引用替换后不再依赖旧引用的情况。2. 头尾指针private transient volatile NodeE head; private transient volatile NodeE tail; public ConcurrentLinkedQueue() { // 初始化时 head 和 tail 都指向一个 item null 的哨兵节点 head tail new NodeE(null); }哨兵节点head和tail最初指向一个空节点item null。这样做简化了边界条件处理避免频繁判断头尾是否为空。volatile修饰保证head和tail引用的可见性任何线程都能及时看到队列的头尾变化。三、offer 操作 —— 入队原理offer(E e)方法用于在队列末尾添加一个元素。由于队列无界它总是返回true除非参数为null抛出异常。该方法不会阻塞线程而是通过自旋 CAS不断尝试追加节点。源码逐段分析public boolean offer(E e) { checkNotNull(e); // (1) 不允许 null 元素 final NodeE newNode new Node(e); // (2) 创建新节点 for (NodeE t tail, p t;;) { // (3) p 用于遍历t 保存最初的 tail NodeE q p.next; // (4) 获取 p 的后继节点 if (q null) { // (5) 如果 p 是最后一个节点 if (p.casNext(null, newNode)) { // (6) CAS 将 p.next 从 null 设置为 newNode if (p ! t) // (7) 如果 p 不是最初的 tail则尝试更新 tail 指针 casTail(t, newNode); return true; } } else if (p q) { // (8) 遇到哨兵自引用节点由 poll 产生 p (t ! (t tail)) ? t : head; // (9) 重新定位使用新 tail 或 head } else { // (10) 正常情况继续向后遍历 p (p ! t t ! (t tail)) ? t : q; } } }详细流程场景1单线程首次添加初始队列head和tail指向哨兵节点itemnull, nextnull。head/tail → 哨兵节点 (null) p t 哨兵q p.next null进入if (q null)执行p.casNext(null, newNode)成功。此时p t都指向哨兵不执行casTail直接返回true。队列状态哨兵节点 → newNode(item1) → nullhead仍指向哨兵tail仍指向哨兵延迟更新。为什么要延迟更新 tail因为每次添加都 CAS 更新tail会有额外开销。允许tail滞后最多一个节点减少 CAS 竞争提升吞吐量。场景2多线程竞争追加假设当前队列已有节点哨兵 → node1 → nulltail仍指向哨兵滞后状态。线程 A 和线程 B 同时调用offer线程 A 执行for循环t tail哨兵p tq p.next node1。q ! null且p ! q进入else分支p q即 p 移动到 node1。此时线程 B 也进入循环但可能线程 A 已经将 node1 的next修改实际上线程 A 尚未修改成功。我们看 CAS 竞争线程 A 继续循环发现p node1q p.next null于是尝试p.casNext(null, newNodeA)成功。此时p ! t所以线程 A 继续尝试casTail(t, newNodeA)将tail从哨兵更新为newNodeA。线程 B 此时可能还在遍历它看到的tail可能已被线程 A 更新为newNodeA也可能还是哨兵。最终线程 B 会找到真正的尾节点newNodeA然后在其后追加newNodeB。关键点CAS 保证了同时只有一个线程能成功修改next指针失败的线程会重新读取最新的tail并继续尝试直到成功。这个过程是无锁的自旋不会阻塞线程。场景3遇到自引用节点p q当执行poll移除元素后可能产生节点的next指向自身的情况自引用。此时p q说明当前节点是已经被逻辑删除的节点。代码会重新定位如果tail已被其他线程更新则使用新tail否则使用head从头开始找有效节点。这样保证遍历不会陷入死循环。四、poll 操作 —— 出队原理poll()方法从队列头部获取并移除一个元素如果队列为空则返回null。同样采用自旋 CAS 实现。源码逐段分析public E poll() { restartFromHead: for (;;) { for (NodeE h head, p h, q;;) { E item p.item; // (1) 获取当前节点的值 if (item ! null p.casItem(item, null)) { // (2) CAS 将 item 设为 null if (p ! h) // (3) 如果 p 不是原来的 head则更新 head updateHead(h, ((q p.next) ! null) ? q : p); return item; // (4) 返回被移除的值 } else if ((q p.next) null) { // (5) 如果后继为 null说明队列为空 updateHead(h, p); return null; } else if (p q) // (6) 遇到自引用跳转到外层循环重新开始 continue restartFromHead; else // (7) 继续向后遍历 p q; } } } final void updateHead(NodeE h, NodeE p) { if (h ! p casHead(h, p)) // 原子地将 head 从 h 更新为 p h.lazySetNext(h); // 将原 head 的 next 指向自身自引用便于 GC }流程场景1队列非空正常移除初始队列哨兵 → node1(item1) → node2(item2) → nullhead指向哨兵。进入内层循环h head 哨兵p hitem p.item null。item ! null不成立进入else if ((q p.next) null)这里q node1不为空继续。else if (p q)不成立执行p q现在p node1。继续循环item node1.item item1非空尝试p.casItem(item1, null)成功。由于p ! h进入updateHead(h, p)h是哨兵p是 node1。casHead(哨兵, node1)成功将head指向 node1。然后h.lazySetNext(h)将哨兵的next指向自身哨兵 → 哨兵变成自引用节点。返回item1。此时队列状态head指向 node1item1 已被置为 nullnode1 的next仍指向 node2哨兵节点被孤立等待 GC。为什么设置自引用将已移除的节点的next指向自身有助于垃圾回收并作为“删除标志”让遍历代码能识别并跳过。场景2队列为空时并发竞态假如队列只有一个哨兵节点且head tail 哨兵next null。线程 A 调用pollp head 哨兵item null(q p.next) null进入else if执行updateHead(h, p)但h pcasHead不会执行返回null。如果此时线程 B 正在执行offer线程 A 可能在判断q null时线程 B 还没来得及将newNode链接到next因此线程 A 返回null但如果线程 B 已经 CAS 成功那么线程 A 会看到q ! null继续遍历并成功移除元素。这种弱一致性是并发队列的正常行为。场景3遇到自引用节点p q当某个节点的next指向自身由updateHead产生遍历到该节点时p q会触发continue restartFromHead跳回最外层循环重新获取最新的head避免死循环。五、关键设计总结1. 为什么不用锁锁的代价线程阻塞和唤醒涉及用户态/内核态切换上下文开销大。CAS 自旋在低到中度竞争下通过 CPU 指令原子操作和循环重试性能远高于锁。虽然自旋会占用 CPU但对于短操作如入队/出队非常高效。2.head和tail的延迟更新入队时并不总是立即更新tail允许tail滞后一个节点。这样做减少了 CAS 竞争因为tail是共享变量每次都更新会引发缓存一致性流量。出队时head也不是每次立即更新而是当p ! h时才更新即“跳两步”策略。这进一步减少了 CAS 操作。3. 哨兵节点与自引用哨兵节点避免了对head/tail为null的特殊处理统一代码逻辑。自引用移除了节点的next指向自身既可以帮助 GC又作为“无效节点”标记让遍历算法能够跳过。4. 弱一致性与size()的不精确性ConcurrentLinkedQueue的迭代器是弱一致性的它不会抛出ConcurrentModificationException但迭代时可能看不到其他线程添加的新元素。同理size()方法需要遍历整个链表在遍历过程中队列可能被修改因此返回值只是一个估计值不适合用于精确判断队列是否为空应使用isEmpty()。六、性能与适用场景优势高吞吐量无锁设计减少了线程切换和锁争用。无界不会因为队列满而阻塞生产者但需注意内存无限增长风险。低延迟CAS 操作通常在几十纳秒到几百纳秒之间。注意事项不适合需要精确容量控制和阻塞等待的场景此时应选LinkedBlockingQueue或ArrayBlockingQueue。大量自旋可能造成 CPU 飙升尤其是在极高竞争下但实际中ConcurrentLinkedQueue表现优秀。典型应用线程池的任务队列如ForkJoinPool内部使用类似设计。事件处理框架中的无锁事件队列。高并发日志记录异步日志缓冲。七、结语ConcurrentLinkedQueue是基于 CAS 的非阻塞并发队列的经典实现。通过volatile保证可见性UnsafeCAS 保证原子性精妙的自旋和延迟更新策略实现了高性能的线程安全队列。理解它的原理不仅能帮助我们正确使用它更能加深对无锁编程、ABA 问题这里未涉及但 CAS 需注意、内存屏障等底层并发概念的认识。在实际开发中根据场景选择合适的并发队列需要阻塞功能选择BlockingQueue追求极致吞吐且能容忍弱一致性则ConcurrentLinkedQueue是绝佳选择。
