跳到主要内容
约 8 分钟3 张卡

ConcurrentLinkedQueue

ConcurrentLinkedQueue 是基于链式节点的无界并发队列，按先进先出（FIFO）取出元素。它用比较并交换（CAS）协调入队与出队：只有共享字段仍符合预期时，才写入新值。本文先解释 OpenJDK 21 的头尾指针和 CAS 路径，再分析竞争重试、计数与对象发布的边界。

1. 面试核心​

先记住这几条，再读正文
  • 队列特性。 ConcurrentLinkedQueue 是无界 FIFO 队列，offer 与 poll 通过 CAS 协调，无需获取队列互斥锁。卡 · 头尾指针
  • 操作生效点。 ConcurrentLinkedQueue 入队在 CAS 成功链接 next 时生效，出队在 CAS 成功清空 item 时生效。卡 · 头尾指针
  • 进展保证。 lock-free 保证持续执行时系统整体有操作取得进展，单个线程仍会因 CAS 竞争而反复重试。
  • size 的成本。 ConcurrentLinkedQueue 的 size() 需要以 O(n) 成本遍历节点，并发更新时返回调用期间的观察值。
  • 等待机制。 ConcurrentLinkedQueue 的 poll() 在队空时返回 null，需要等待任务到来时应使用 BlockingQueue。卡 · size 的成本

2. 头尾指针​

常考卡 · ConcurrentLinkedQueue 怎样用 CAS 完成入队和出队

理解入队和出队前，需要先区分头尾指针与实际存活的元素。队列用 head、tail 记录查找起点，节点用 next 指向下一个节点，用 item 保存元素。头尾指针允许暂时落后，线程沿链接找到有效位置后，再协助推进指针。

head                             tail
 ↓                                ↓
[removed] -> [A] -> [B] -> [C] -> null

图中的 removed 表示元素已被取走，但节点仍是当前的头部起点。允许指针落后，可以减少一次操作必须完成的 CAS 次数，后续线程会协助推进。某个线程暂停时，其他线程也能沿节点继续操作，无需等待它释放队列锁。

3. offer 入队​

入队要把新节点接到实际末端，关键是让多个生产者竞争时只有一个成功链接。可以沿以下节点链接过程理解：

  1. 创建 item 为新元素、next 为 null 的节点。
  2. 从观察到的尾部向后寻找实际末端。
  3. 对末端节点的 next 执行 CAS，把 null 改为新节点。
  4. 视情况推进 tail；失败也不影响元素已经成功链接。

多个生产者竞争同一末端时，只有一个 CAS 能把 next 从 null 改成新节点。失败者重新读取链接，找到新的末端后再试。成功链接意味着元素已经入队，更新 tail 可以稍后完成。

这种算法提供 lock-free 保证，也就是持续执行时，系统整体有操作取得进展。某个线程的 CAS 失败，说明共享位置已经被其他操作推进。它自己仍会因持续竞争而长时间重试，因此要区分整体进展与单线程完成时间。

4. poll 出队​

出队需要让一个元素只由一个消费者成功领取。poll 从 head 向后查找首个 item 非 null 的节点，再通过 CAS 把 item 改为 null。成功的消费者返回原来的元素，其他消费者重新查找。因此，元素在 item 清空时就已被逻辑删除，节点可以稍后再清理。

逻辑删除后，线程尝试推进 head，让旧节点脱离主要链路。旧头节点还可以把 next 指向自己，标记它已经脱离主链。其他线程遇到这个标记时，就从当前 head 重新查找。

节点链接的清理需要兼顾并发遍历与垃圾回收（GC）。所以，head 和 tail 只记录算法的查找起点，实际队列内容要根据有效节点判断。

5. 竞争下的重试成本​

常考卡 · ConcurrentLinkedQueue 怎样用 CAS 完成入队和出队

无锁算法减少了对持锁线程进度的依赖，但竞争仍需要协调。多个线程频繁更新相邻节点时，会承担以下重试与内存成本：

  • CAS 失败后要重新读取共享字段，再尝试更新。
  • 缓存行是缓存传输和保持一致性的基本数据单位。多个 CPU 核心争用同一缓存行时，核心间的通信开销会增加。
  • 每次入队需要分配节点，节点释放又会增加 GC 工作。
  • 指针落后或经过已删除节点时，需要沿 next 多走几步才能找到有效位置。

这些开销会随生产者数量、竞争程度和消费速度变化。因此，应按真实负载比较无锁队列、有界阻塞队列、分片队列或批量处理的吞吐与延迟。

6. size 的成本​

常考卡 · ConcurrentLinkedQueue 与 LinkedBlockingQueue 怎样选择

查询长度也需要考虑成本。ConcurrentLinkedQueue 的 size 会沿链表统计有效节点：

int pending = queue.size();

OpenJDK 21 采用的这个实现需要 O(n) 成本。统计期间仍可入队和出队，所以返回值只是调用期间的观察。下面用它检查容量，会同时遇到遍历开销和并发竞态：

if (queue.size() < limit) {
    queue.offer(job);
}

检查和入队是两个独立操作，多个生产者可以同时通过检查，再分别插入。因此，这段代码无法可靠限制容量。需要容量和背压时，可以使用有界 BlockingQueue。

也可以显式管理并发许可：入队前先取得名额，入队失败或消费结束后按约定释放。许可与任务交接的每条失败路径都要配合，才能维护正确上限。

7. 弱一致迭代​

ConcurrentLinkedQueue 的迭代器可以与入队、出队同时运行，并观察期间的部分状态，这称为弱一致语义。它不会因并发修改抛出 ConcurrentModificationException。从迭代器创建起持续留在队列中的元素，会被返回一次；整个遍历结果仍可来自多个时刻。

这种遍历适合监控和诊断，观察元素与领取任务的区别见 迭代一致性。

需要固定完整状态时，应让相关线程暂停修改并协调可见性，或转移队列所有权后再复制。其他方案见一致快照协议。

8. 适用场景​

常考卡 · ConcurrentLinkedQueue 与 LinkedBlockingQueue 怎样选择

选择 ConcurrentLinkedQueue 前，要确认调用方怎样处理空队列和任务积压。它适合以下进程内交接需求：

  • 多个生产者和消费者需要按 FIFO 交接元素。
  • 业务无需队列提供容量限制，读取允许弱一致视图。
  • 调用方已有唤醒机制，或能自行管理空队列的轮询。

业务需要以下等待与调度能力时，应选择其他队列或消息系统：

  • 需要队列按容量上限向生产者施加背压时，使用有界队列。
  • 消费者需要在队空时睡眠等待任务时，使用 BlockingQueue。
  • 任务需要持久化或跨进程传递时，使用相应的消息系统。
  • 任务需要按优先级、延迟或严格公平规则处理时，选择提供对应协议的实现。

9. 空值与对象发布​

常考卡 · 无锁队列怎样保证入队前的字段写入对消费者可见？

任务交接既要区分有没有元素，也要保证接收线程能读到任务字段。ConcurrentLinkedQueue 拒绝 null，因为 poll 用它表示当前没有元素。

队列为对象交接建立 happens-before 关系，也就是生产者入队前的写入对成功取得元素的线程可见。CAS 和节点的内存同步共同支持这种发布，所以无锁操作仍有可见性保证。入队后继续修改同一个对象时，生产者与消费者仍需另行同步。

成功 poll 只表示当前消费者领取了一个元素。处理失败后的重试与重复副作用由业务协议管理，进程崩溃后的恢复则需要持久存储。

10. 常见问题​

10.1 lock-free 与 wait-free​

lock-free 保证持续执行时系统整体有操作取得进展，某个线程仍可反复重试。wait-free 的保证更强，要求每个操作都在有界步骤内完成。ConcurrentLinkedQueue 提供的是前一种保证，因此单个线程的完成时间仍受竞争影响。

10.2 空队列等待策略​

10.3 isEmpty 与 poll 的时序​

10.4 FIFO 与线程公平性​

11 · 面试题卡片​

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。
逐张翻看 3 张 →
头尾指针常考
ConcurrentLinkedQueue 怎样用 CAS 完成入队和出队
快手蚂蚁集团
考察 3 点 · 相关 §2 §5
size 的成本常考
ConcurrentLinkedQueue 与 LinkedBlockingQueue 怎样选择
快手
考察 3 点 · 相关 §6 §8
空值与对象发布常考
无锁队列怎样保证入队前的字段写入对消费者可见？
本站自测
考察 1 点 · 相关 §9

11.1 ConcurrentLinkedQueue 怎样用 CAS 完成入队和出队​

出现公司：快手、蚂蚁集团

考察重点

  • 说明节点链接与逻辑删除分别使用什么 CAS。
  • 说明 head、tail 为什么允许暂时落后，以及后续线程如何协助推进。
  • 说明 lock-free 与 wait-free 分别对整体和单线程提供什么进展保证。

相关内容：头尾指针至竞争下的重试成本。

参考回答

入队通过 CAS 链接新节点，出队通过 CAS 清空有效节点的 item，由成功者取得元素。

入队线程先创建节点，沿 tail 查找实际末端，再把末端 next 从 null 改为新节点。出队线程则沿 head 找到首个有效节点，把 item 改为 null，完成逻辑删除。

这两处 CAS 成功时，入队与领取结果已经确定。head、tail 可以稍后推进，其他线程也能协助完成，从而减少每次操作必须更新的字段。算法提供 lock-free 进展，单线程仍可因竞争持续重试；wait-free 才要求每个操作在有界步骤内完成。

11.2 ConcurrentLinkedQueue 与 LinkedBlockingQueue 怎样选择​

出现公司：快手

考察重点

  • 说明非阻塞无界队列与可阻塞有界队列的协议差异。
  • 说明 size 的成本，以及两种队列怎样处理容量限制和消费者等待。
  • 说明 CAS 重试与锁条件等待各自带来哪些成本。

相关内容：size 的成本、适用场景。

参考回答

已有唤醒机制且无需队列提供容量限制时，可用 ConcurrentLinkedQueue。

需要缓冲上限和条件等待时，可用显式设置容量的 LinkedBlockingQueue。

ConcurrentLinkedQueue 是无界非阻塞队列，poll 在队空时返回 null，size 则需要遍历。先查 size 再入队既增加成本，也无法原子地保证容量上限。LinkedBlockingQueue 提供 put、take 和限时操作，可以等待任务或空位，并把积压压力传给生产者。

前者要承担 CAS 重试，后者要承担锁竞争与条件等待。最终应按需要的交接协议选择，再用实际负载比较吞吐和延迟。

11.3 无锁队列怎样保证入队前的字段写入对消费者可见？​

出现公司：暂无已核验的公开来源（本站自测）

考察重点：解释无锁队列如何发布入队前的字段写入，以及入队后继续修改为何需要同步。

相关内容：空值与对象发布。

参考回答

ConcurrentLinkedQueue 通过元素交接的 happens-before 关系，让消费者看到入队前的字段写入。

实现用 CAS 和节点的内存同步发布元素，即使没有队列互斥锁，也能保证相应的可见性。

队列传递的是对象引用，入队后继续修改同一个对象时，生产者会与消费者并发访问。因此，后续字段修改需要独立同步，或约定入队后只由消费者使用该对象。

12. 参考资料​

本页
有对应面试题卡片