外观
23 - ConcurrentLinkedQueue 与无锁队列
适用 JDK:JDK 8+。实现细节以现代 OpenJDK 的无锁链式队列思路为背景,正确性应以公开 API 契约为准。
摘要
多个生产者提交任务、多个消费者取出任务时,队列首先要保证并发入队和出队的正确性。ConcurrentLinkedQueue 提供线程安全的 FIFO(First In, First Out,先进先出)队列:元素按入队顺序取出。它的入队和出队不需要等待队列变得非满或非空,但没有容量限制、等待和关闭协议。
因此,不能仅凭“无锁”就把 BlockingQueue 换成它。选型要分别回答两个问题:如何安全地交接元素,以及消费者跟不上时如何限制积压。
1. API 语义先于实现
下面是使用片段,需导入 java.util.Queue 和 java.util.concurrent.ConcurrentLinkedQueue;Task、task 与 handle 由业务代码提供:
java
Queue<Task> queue = new ConcurrentLinkedQueue<>();
queue.offer(task);
Task next = queue.poll();
if (next != null) {
handle(next);
}offer(task) 将任务放入队列,poll() 取出并移除队头元素。队列不允许 null,因此 poll() 返回 null 表示这次操作观察到了空队列;其他线程仍可能随后入队。它不会等待元素出现,也没有限时 offer、take 或固定容量。
FIFO 约束的是队列中的取出顺序,不是业务处理完成顺序。多个消费者取走任务后,处理耗时不同,后取出的任务可能先完成。
如果消费者在空队列上持续循环 poll(),所谓“非阻塞”可能变成高 CPU 空转。需要等待通知时,应使用阻塞队列、信号机制或事件循环,而不是无条件自旋。
2. 无锁链式队列的核心思路
先把链式队列理解为一串节点:节点保存元素,并通过引用连接到后继节点。生产者在链尾接入新节点,消费者从队头取走元素。并发难点在于,多个线程可能同时尝试修改同一个链接或节点状态。
CAS(Compare-And-Set,比较并设置)只在当前值仍等于预期值时提交更新。该类算法通常通过 CAS 推进尾部链接和头部位置:生产者竞争把新节点链接到链尾,消费者竞争移除元素或越过已经移除元素的节点。若其他线程抢先改变状态,当前线程就需要重新观察并重试,或协助推进已有操作。
这就是无锁(lock-free)强调的进展方式:某个线程暂停时,其他线程仍可能完成操作,算法关注系统整体能继续推进。它不保证每个线程公平地完成操作,也不表示没有争用;高竞争下的 CAS 重试仍可能消耗 CPU。
线性化是指一次并发操作可以被视为在调用开始到返回之间的某个瞬间完成。对入队、出队而言,关键是元素何时被接入或移除,而不是所有内部指针何时更新完毕。因此,公开操作的线性化语义与内部指针短暂滞后并不矛盾:head、tail 不必每一步都精确指向队头和队尾,后续线程可以协助推进。业务代码不能依赖这些内部字段,也不能据此把遍历或批量操作当作整体原子操作。
3. 与 BlockingQueue 的边界
| 需求 | 更合适的起点 |
|---|---|
| 非阻塞地暂存少量已受外部容量控制的事件 | ConcurrentLinkedQueue |
| 队满时拒绝、等待或超时 | 有界 BlockingQueue |
| 队空时让消费者休眠等待 | BlockingQueue.take() |
| 生产者与消费者直接移交 | SynchronousQueue |
| 端到端需求式背压 | Reactive Streams 协议 |
ConcurrentLinkedQueue 逻辑上无界,offer() 通常不会以“队满”返回失败;这不表示机器内存无限。如果生产速率长期高于消费速率,未处理任务会不断留在队列中,既占用内存,也让后续任务等待更久。
背压是把下游处理能力不足的信号传回上游,让上游减速或减少提交。无界队列本身不会建立这种反馈;业务需要另设容量与过载协议,相关设计见 19 - BlockingQueue 与生产者—消费者模型。表中的选择是设计起点,仍需结合等待方式和实际负载评估,不能据此断言无锁队列一定更快。
4. size() 不是容量控制
链式并发队列的 size() 通常需要遍历,可能是 O(n),即工作量随元素数量增长;遍历期间队列仍在变化,得到的长度也不能作为精确的容量依据。下面是错误用法片段,沿用前面的业务变量,limit 表示期望上限:
java
if (queue.size() < limit) {
queue.offer(task); // 多线程可同时越过检查
}即使某次长度读取准确,“检查长度”和“入队”也是两个操作。两个生产者可能都看到还剩一个位置,然后分别入队,最终越过上限。单个方法线程安全,不会让这段组合逻辑自动成为原子操作。
需要不可越过的容量上限时,直接选择有界容器。若使用外部令牌控制容量,令牌代表可占用的名额:入队前先取得名额,入队失败时归还,消费后按协议归还。还要明确限制的是排队元素数还是包含处理中任务的总数,因为二者的归还时机不同;异常路径不能遗漏归还,也不能重复归还。
5. 弱一致遍历和批量操作
弱一致遍历是指:遍历可以与队列修改同时进行,但结果不是某个全局时刻的冻结快照。不能要求遍历看到所有并发新加入的元素,也不能把遍历结束理解为队列中的工作已经完成。它适合诊断或尽力观察元素;需要精确清算、去重或确认全部任务完成时,不能单靠一次遍历。
isEmpty() 后再 poll()、遍历后再删除也属于多个操作的组合。例如,检查时队列非空,另一个消费者却可能在当前线程调用 poll() 前取走最后一个元素,所以仍须处理 null。业务不变量(必须始终成立的约束)应由单个原子操作或更高层协议保证。
removeIf、removeAll、retainAll 等批量方法也不能被理解为整队列事务。它们与并发入队、出队交错时,可能只作用于遍历期间观察到的部分元素。需要“冻结后清算”时,应停止生产并完成所有权切换,或通过切换协议让新任务进入新队列,再处理旧队列。仅替换一个队列引用并不足够:还要确认没有生产者继续向旧队列提交,并协调仍在消费旧队列的线程。
6. 内存可见性与对象所有权
线程在元素入队前完成的操作,对另一个线程随后访问或移除该元素具有队列 API 规定的内存一致性效果。也就是说,队列交接不仅传递对象引用,还让消费者能够看到生产者入队前完成的初始化。
这项保证不覆盖生产者在入队后继续进行的无同步修改。消费者此时可能已经取走对象并读取字段,队列本身不会替这些后续读写建立同步。
最容易推理的做法是传递不可变消息,或在移交后将对象所有权交给消费者。这里的所有权是一项业务约定:交出对象的一方不再修改它,需要修改时由接收方负责,或另行建立同步协议。
7. 验证与排障
- 空队列时观察消费者是否空转占用 CPU,检查轮询之外是否有等待或通知机制;
- 除队列估算长度外,记录最旧元素年龄(从入队到观察时经过的时间)、生产和消费速率,区分短时突发与持续积压;
- 注入消费者暂停,观察上游是否按预定策略等待、拒绝或限流,验证容量保护是否真正生效;
- 使用 JCStress(Java 并发测试工具)或线性化历史检查验证自研队列,不要只检查最终元素数;历史检查需要记录操作的调用、返回和结果,判断它们能否对应合法的顺序执行;
- 出现内存增长时,从队列节点追踪仍被引用的任务对象与上下文,确认积压保留了哪些数据。
以上是验证建议,不是本文已经执行的测试或测量记录。
7.1 自研无锁队列需要证明什么
仅验证元素最终没有丢失还不够:数量相同仍可能掩盖重复、丢失互相抵消或顺序错误。至少要说明:
- 每次
offer、poll的线性化点,即逻辑上完成该操作的状态变化或观察位置; - 空队列与最后一个元素出队的竞态;
- CAS 失败后如何重试或协助其他线程推进;
- 节点回收和 ABA 是否由运行时对象生命周期或额外版本机制覆盖;ABA 指状态从 A 变为 B 又回到 A,使仅比较当前值的 CAS 无法识别中间变化,不能未经分析就认定某种回收方式已排除它;
- 算法提供 lock-free、wait-free 还是更弱的进展保证;wait-free 比整体进展要求更强,要求每个操作都能在有界步骤内完成。
业务系统通常应优先使用 JDK 容器;自研实现需要 JCStress、历史线性化检查和多架构验证,不能只靠高并发循环测试。
8. 总结
选择 ConcurrentLinkedQueue 时,应同时为积压、空队列等待和停止消费设计业务协议。
- 无锁不等于无争用,也不保证单线程公平。
size()不能用于并发容量判断。- 持续过载场景应先设计容量协议,再选择队列实现。
协议延伸:24 - Flow 与 Reactive Streams 背压通过需求量控制异步信号,而不是依赖轮询队列长度。