ConcurrentLinkedQueue
ConcurrentLinkedQueue 是基于链表节点的无界并发队列,元素按先进先出(FIFO)的顺序取出。它不用锁,而是用 CAS(比较并交换)协调入队和出队:只有共享字段仍然是线程读到的那个值时,才写入新值,否则重新读取再试。沿着入队和出队的过程,可以看出操作分别在哪一次 CAS 成功时生效,以及为什么头尾指针可以暂时落后。「无锁」也不等于没有代价:size 是 O(n),队列空了也不会等待。下文以 OpenJDK 21 为准。
1. 面试核心
先记住这几条,再读正文- ConcurrentLinkedQueue 是无界 FIFO 队列,
offer与poll通过 CAS 协调,不获取队列的互斥锁。卡 · 头尾指针 - 入队在 CAS 成功链接
next时生效,出队在 CAS 成功把item清空时生效。卡 · 头尾指针 - lock-free 保证的是系统整体总有操作在推进,单个线程仍可能因为 CAS 竞争而反复重试。
size()要遍历节点,成本是 O(n),并发更新时返回的只是调用期间的观察值。- 队列为空时
poll()直接返回 null,不会等待;需要等待任务到来时,应该用 BlockingQueue。卡 · size 的成本
2. 头尾指针
先分清两件事:头尾指针指向哪里,和队列里实际有哪些元素。队列用 head、tail 两个指针记录查找的起点;每个节点用 item 保存元素,用 next 指向下一个节点。头尾指针允许暂时落后于真实位置,线程沿着 next 找到有效位置后,再顺手把指针往前推。
head tail
↓ ↓
[removed] -> [A] -> [B] -> [C] -> null
图中 removed 节点的元素已经被取走了,但它仍然是 head 指向的起点。为什么允许这样?如果每次操作都必须同时更新节点和头尾指针,就要多做一次 CAS,竞争也更多;允许指针落后,一次操作只需完成最关键的那一次 CAS,剩下的推进工作由后续线程协助完成。另一个好处是,某个线程执行到一半被暂停了,其他线程也能沿着节点继续操作,不需要等它释放什么锁。
3. offer 入队
入队要把新节点接到实际的末尾,难点是多个生产者同时竞争时,只能有一个接上去。节点链接过程如下:
- 创建一个
item为新元素、next为 null 的节点。 - 从读到的
tail出发,向后找到实际的末端节点(它的next是 null)。 - 对末端节点的
next执行 CAS,把 null 改成新节点。 - 视情况推进
tail;这一步失败了也没关系,元素已经入队了。
多个生产者盯上同一个末端时,只有一个 CAS 能把 next 从 null 改成自己的节点。失败的线程重新读取链接,找到新的末端再试。CAS 成功的那一刻,元素就已经入队,tail 可以晚一点再更新。
这种算法提供 lock-free 保证:只要线程在持续执行,整个系统总有操作能完成。一个线程的 CAS 失败,恰恰说明有别的操作成功推进了共享位置。但对这个失败的线程来说,竞争持续激烈时它可能要重试很多次,所以要分清「整体有进展」和「单个线程多久能完成」。
4. poll 出队
出队要保证一个元素只被一个消费者领走。poll 从 head 往后找第一个 item 不为 null 的节点,再用 CAS 把这个 item 改成 null。CAS 成功的消费者返回原来的元素,失败的消费者重新查找。所以 item 被清空的那一刻,元素就已经逻辑删除了,节点本身可以之后再清理。
逻辑删除之后,线程会尝试推进 head,让旧节点脱离主链。旧的头节点还会把 next 指向自己,作为「已脱离主链」的标记;其他线程沿链走到这个节点时,看到这个标记,就从当前的 head 重新开始找。
清理节点链接时,既要照顾正在并发遍历的线程,也要让垃圾回收(GC)能回收旧节点。所以 head 和 tail 只是算法的查找起点,队列里实际有什么,要看哪些节点的 item 仍然有效。
5. 竞争下的重试成本
无锁算法不再依赖「持锁线程赶紧干完」,但竞争本身并没有消失。多个线程频繁更新相邻的节点时,要付出这些重试与内存成本:
- CAS 失败后,要重新读取共享字段,再尝试更新。
- 多个 CPU 核心争用同一个缓存行时,核心之间要来回同步数据。缓存行是 CPU 缓存传输和保持一致性的基本单位。
- 每次入队都要分配一个节点,节点用完又增加 GC 的工作量。
- 指针落后或者经过已删除的节点时,要沿
next多走几步才能找到有效位置。
这些开销随生产者数量、竞争程度和消费速度变化。所以要按真实负载,比较无锁队列、有界阻塞队列、分片队列或批量处理的吞吐和延迟,而不是默认无锁一定更快。
6. size 的成本
ConcurrentLinkedQueue 不维护一个元素计数器,size 要沿链表把有效节点数一遍:
int pending = queue.size();
在 OpenJDK 21 的实现里,这是 O(n) 的操作。统计过程中队列仍在入队出队,所以返回值只是调用期间的一个观察。下面用它来限制容量,会同时遇到遍历开销和并发竞态两个问题:
if (queue.size() < limit) {
queue.offer(job);
}
检查和入队是两个独立的操作,多个生产者可能同时通过检查,再各自插入,最后超出上限。所以这段代码限制不住容量。需要容量上限和背压(队列满时让生产者慢下来)时,应该用有界的 BlockingQueue。
也可以自己管理并发许可:入队前先拿到一个名额,入队失败或者消费完成后按约定归还。这要求许可和任务交接的每一条失败路径都配合好,上限才能维持正确。
7. 弱一致迭代
ConcurrentLinkedQueue 的迭代器是弱一致的:它可以和入队、出队同时运行,能看到期间的一部分变化,不会因为并发修改抛出 ConcurrentModificationException。从迭代器创建起一直留在队列里的元素,保证会被返回一次;但整次遍历的结果仍然可能来自多个时刻。
这种遍历适合监控和诊断。遍历只是观察元素,并不会领取任务,两者的区别见迭代一致性。
需要固定一份完整状态时,要让相关线程停止修改并协调可见性,或者先把队列的所有权转移出来再复制。其他方案见一致快照协议。
8. 空值与对象发布
任务交接要解决两个问题:怎么知道有没有拿到元素,以及消费者能不能看到任务对象里的字段。
第一个问题靠 null:poll 用 null 表示当前没有元素,所以 ConcurrentLinkedQueue 不允许放入 null,否则就分不清「取到了 null」和「队列为空」。
第二个问题靠 happens-before 关系:生产者在入队之前对对象做的写入,对成功取到这个元素的消费者可见。这是由 CAS 和节点字段的内存同步保证的,所以没有锁也有可见性保证。但这个保证只覆盖入队之前的写入;入队之后生产者如果继续修改同一个对象,就和消费者构成了并发访问,需要另外同步。
另外,成功 poll 只说明当前消费者领到了一个元素。处理失败后怎么重试、怎么避免重复的副作用,要由业务协议决定;进程崩溃后要恢复任务,则需要持久化存储。
9. 适用场景
选 ConcurrentLinkedQueue 之前,先想清楚队列空了怎么办、任务积压了怎么办。它适合这样的进程内交接需求:
- 多个生产者和消费者在同一进程内按 FIFO 交接元素。
- 业务不需要队列提供容量限制,遍历时接受弱一致的视图。
- 调用方已有唤醒机制,或者能自己管理队列为空时的轮询。
业务需要下面这些等待与调度能力时,应该换其他队列或消息系统:
- 需要按容量上限给生产者施加背压时,用有界队列。
- 消费者需要在队列为空时睡眠等待时,用 BlockingQueue。
- 任务需要持久化或跨进程传递时,用相应的消息系统。
- 任务需要按优先级、延迟或严格的公平规则处理时,选提供相应协议的实现。
10. 常见问题
10.1 lock-free 与 wait-free
lock-free 保证持续执行时系统整体总有操作在推进,但某个线程可能一直重试。wait-free 的保证更强,要求每个操作都在有限步内完成。ConcurrentLinkedQueue 提供的是前一种,所以单个线程的完成时间仍然受竞争影响。
10.2 空队列等待策略
需要「队列为空时等待、任务到了再唤醒」,就用 BlockingQueue。用 ConcurrentLinkedQueue 自己实现的话,持续自旋轮询会白白占用 CPU,固定 sleep 又会让已经到达的任务多等一会儿。如果已经有带唤醒机制的事件循环,可以配合非阻塞队列使用,由事件循环负责休眠和唤醒。
10.3 isEmpty 与 poll 的时序
直接调用 poll 并处理 null 就行,不要先调 isEmpty。isEmpty 返回 false 之后,其他消费者仍然可能抢先取走最后一个元素,随后的 poll 照样返回 null,提前检查并没有省掉 null 判断。
10.4 FIFO 与线程公平性
FIFO 约束的是元素按入队顺序被取出,不约束线程的顺序。哪个生产者或消费者先拿到执行机会,取决于线程调度和 CAS 竞争,先开始操作的线程也可能更晚完成。
11. 面试题卡片
12. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明