承接的问题
9.3 把 Unsafe 换成了 VarHandle，那是工具层面的迁移。这一节换个角度：只给你 compareAndSet 和几个 volatile 字段，怎么从零搭出一个并发安全的栈和队列。
无锁结构看起来简单得可疑——Treiber 栈的全部状态就是一个 top 指针。但真正的难点不在"怎么写对一次 CAS"，而在：当某个线程卡在半路、指针落后、节点已经被别人摘掉时，其他线程要不要替它把事情做完。教科书里的 Michael-Scott 队列给了"帮助推进 tail"这一条；JDK 的 ConcurrentLinkedQueue 在此之上又加了一层，处理"已经被逻辑删除、但还没被物理摘除"的节点。
本节先写两个能跑的实现，再用 javap -p 和一百万次入队的数据，说明 ConcurrentLinkedQueue 的那些"多余"方法到底在兜什么底。CAS 与 ABA 的概念推演在卷一第 8 章已经讲过，这里只做实现。
手写 Treiber 栈
Treiber 栈只维护一个栈顶。push 造一个新节点、把 next 指向当前栈顶、CAS 换掉 top；pop 反过来。全部原子操作走 VarHandle，没有一处 Unsafe：
public final class TreiberStack<E> implements ConcurrentStack<E> {
static final class Node<E> {
final E value;
Node<E> next;
Node(E value) { this.value = value; }
}
private static final VarHandle TOP;
private static final VarHandle NEXT;
static {
try {
MethodHandles.Lookup l = MethodHandles.lookup();
TOP = l.findVarHandle(TreiberStack.class, "top", Node.class);
NEXT = l.findVarHandle(Node.class, "next", Node.class);
} catch (ReflectiveOperationException e) {
throw new ExceptionInInitializerError(e);
}
}
private volatile Node<E> top;
public void push(E value) {
Node<E> n = new Node<>(value);
for (;;) {
Node<E> t = top;
NEXT.set(n, t); // 普通写：节点还没发布
if (TOP.compareAndSet(this, t, n)) {
return;
}
}
}
public E pop() {
for (;;) {
Node<E> t = top;
if (t == null) {
return null;
}
if (TOP.compareAndSet(this, t, t.next)) {
return t.value;
}
}
}
}
两个细节值得说清楚。
第一，NEXT.set(n, t) 是普通写，不是 setRelease。理由和 ConcurrentLinkedQueue.Node 的构造器一样：这个节点还没被任何线程看见，set 和后面的 compareAndSet 之间不会插进对它的读；而 compareAndSet 本身带 release 语义，一旦成功，next 的写必然先于新栈顶的可见性。源码注释把这称为"one-and-a-half CASes"——入队只付一次 CAS，外加一次普通写。
第二，pop 里读 t.next 时 t 已经可能是"过期栈顶"。但没关系：CAS 的期望值是 t 这个引用，只要 top 还是 t，t.next 就没被改过——因为 next 一旦发布就不再变。这是 Treiber 栈比队列简单的地方：节点是只读的，改动只发生在 top。
javap -p 验证一下真的没有 Unsafe，也没有 casHead 之类的辅助方法：
$ javap -p -classpath out jucch10.TreiberStack
Compiled from "TreiberStack.java"
public final class jucch10.TreiberStack<E> implements jucch10.ConcurrentStack<E> {
private static final java.lang.invoke.VarHandle TOP;
private static final java.lang.invoke.VarHandle NEXT;
private volatile jucch10.TreiberStack$Node<E> top;
private final boolean countFailures;
private final java.util.concurrent.atomic.LongAdder failures;
public jucch10.TreiberStack();
public jucch10.TreiberStack(boolean);
public void push(E);
public E pop();
public long casFailures();
jucch10.TreiberStack$Node<E> snapshotTop();
boolean commitTop(jucch10.TreiberStack$Node<E>, jucch10.TreiberStack$Node<E>);
jucch10.TreiberStack$Node<E> nodeOf(E);
public java.lang.String toString();
static {};
}
Michael-Scott 队列：允许 tail 落后
队列比栈难，因为要同时维护 head 和 tail 两个指针，而它们各自都能落后于真实位置。教科书版 MS 队列用一个 dummy 头结点：head 指向 dummy，tail 指向最后一个结点，入队在 tail.next 上做 CAS：
public void enqueue(E value) {
Node<E> n = new Node<>(value);
for (;;) {
Node<E> t = tail;
Node<E> next = t.next;
if (next == null) {
if (NEXT.compareAndSet(t, null, n)) {
TAIL.compareAndSet(this, t, n); // 失败也无所谓
return;
}
} else {
TAIL.compareAndSet(this, t, next); // tail 落后了，帮它推一格
}
}
}
public E dequeue() {
for (;;) {
Node<E> h = head;
Node<E> first = h.next;
if (first == null) {
return null;
}
if (HEAD.compareAndSet(this, h, first)) {
return first.value;
}
}
}
关键在 else 分支。线程 A 成功把新节点挂到 t.next，但还没来得及推进 tail 就被切走了；线程 B 进来看到 tail 还是 t、而 t.next 非空——此时 B 不干等，而是顺手把 tail CAS 到 t.next，然后继续自己的入队。推进 tail 不是某个线程的私事，是所有路过线程的公共义务。
这条"帮助"不是可选的优化。如果去掉它，B 会在原地自旋到 A 恢复；在 A 被换出、B 占着 CPU 的场景下，这就是活锁。
本机跑 4 个生产者各 25 万次入队、4 个消费者并发出队，顺便统计了两个计数器：
TreiberStack popped=1000000/1000000 sum=499999500000(expect 499999500000) sumSq=333332833333500000(expect 333332833333500000) ok=true casFailures=4674262 464ms
MSQueue dequeued=1000000/1000000 sum=499999500000(expect 499999500000) sumSq=333332833333500000(expect 333332833333500000) ok=true casFailures=1921775 tailHelps=1064455 356ms
tailHelps=1064455 是一百万次入队里，“看到 tail 不是真实末尾"的次数——平均每次入队都会撞上一次。这不是异常路径，这是常态。任何把 tail 当成权威末尾去读的代码都会读错，ConcurrentLinkedQueue.size() 之所以要遍历，根子就在这里。
同一份数据还暴露了栈的代价：一百万次 push 加一百万次 pop，CAS 失败了 467 万次，平均每次操作 2.3 次失败重试。队列因为有"帮助推进"把竞争摊到了 head 和 tail 两个点上，失败次数反而只有 192 万。这个数字在 10.3 会变成主角。
CLQ 比教科书多出来的那一层
ConcurrentLinkedQueue 的 offer 和上面的 MS 队列几乎一样，真正的差别在删除路径。先看它的结点和四个句柄：
// JDK 25 源码摘录，已删减
static final class Node<E> {
volatile E item;
volatile Node<E> next;
Node(E item) {
ITEM.set(this, item); // relaxed write，靠 CAS 发布
}
void appendRelaxed(Node<E> next) {
NEXT.set(this, next);
}
boolean casItem(E cmp, E val) {
return ITEM.compareAndSet(this, cmp, val);
}
}
private static final VarHandle HEAD;
private static final VarHandle TAIL;
static final VarHandle ITEM;
static final VarHandle NEXT;
注意 casHead / casTail 这两个名字在 JDK 25 里已经不存在（旧版教材里到处是它们），javap -p 只能看到 HEAD/TAIL/ITEM/NEXT 四个静态句柄和 updateHead/succ/tryCasSuccessor/skipDeadNodes 四个方法。
item 和 next 都是 volatile，因为出队不是一个动作，而是两个：先把 item CAS 成 null（逻辑删除，线性化点），再把节点从链上摘掉（物理摘除，纯优化）。中间这段时间里，节点还在链上但已经没有元素了，这叫死结点。看这三个方法怎么配合：
// JDK 25 源码摘录，已删减
final void updateHead(Node<E> h, Node<E> p) {
if (h != p && HEAD.compareAndSet(this, h, p))
NEXT.setRelease(h, h); // 旧 head 自环，作为 succ() 的路标
}
final Node<E> succ(Node<E> p) {
if (p == (p = p.next))
p = head; // 撞到自环说明手里的指针已经离线
return p;
}
private boolean tryCasSuccessor(Node<E> pred, Node<E> c, Node<E> p) {
if (pred != null)
return NEXT.compareAndSet(pred, c, p);
if (HEAD.compareAndSet(this, c, p)) {
NEXT.setRelease(c, c);
return true;
}
return false;
}
private Node<E> skipDeadNodes(Node<E> pred, Node<E> c, Node<E> p, Node<E> q) {
if (q == null) {
if (c == p) return pred;
q = p;
}
return (tryCasSuccessor(pred, c, q)
&& (pred == null || ITEM.get(pred) != null))
? pred : p;
}
updateHead 里那句 NEXT.setRelease(h, h) 是整个设计的枢纽。头指针前移之后，旧 head 被"自环”——h.next == h。这样任何还攥着 h 的线程，下次调 succ(h) 时会发现 p == p.next，立刻知道自己的视图过期了，跳回最新 head 重来。没有这个自环，旧线程会顺着一条已经从链上消失的路径一直走下去。
skipDeadNodes 则是"顺手做清洁"：遍历时遇到一串 item == null 的死结点，用一次 CAS 把 pred.next 直接指到第一个活结点，一次性摘掉整串。注意它的返回值不是布尔而是 Node——CAS 成功后返回 pred（可以继续用），失败或 pred 自己已经死了则返回 p（下次从 p 重新开始）。这种"返回下一个可信起点"的写法，是无锁遍历的通用套路。
还要注意 skipDeadNodes 里那条 if (q == null) { ... }：尾结点永远不摘。摘掉尾结点会让并发入队者失去挂载点，直接破坏队列。
最后是 MAX_HOPS。它出现在 bulkRemove 里：
// JDK 25 源码摘录，已删减
private static final int MAX_HOPS = 8;
private boolean bulkRemove(Predicate<? super E> filter) {
restartFromHead: for (;;) {
int hops = MAX_HOPS;
for (Node<E> p = head, c = p, pred = null, q; p != null; p = q) {
q = p.next;
final E item;
boolean pAlive;
if (pAlive = ((item = p.item) != null)) {
if (filter.test(item)) {
if (p.casItem(item, null))
removed = true;
pAlive = false;
}
}
if (pAlive || q == null || --hops == 0) {
// p 可能已经自环：CAS head 必然失败，CAS pred.next 无害
if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
hops = MAX_HOPS;
pred = p;
c = q;
}
} else if (p == q)
continue restartFromHead;
}
return removed;
}
}
MAX_HOPS = 8 的意思是"容忍连续 8 个死结点，然后再做一次批量折叠"。为什么不每遇到一个死结点就摘一次？因为每次摘除都是一次 CAS，而 CAS 失败的代价比多走几个指针高得多。8 是个摊销参数：源码注释写的是 “Amortized cost of clear() is (1 + 1/MAX_HOPS) CASes per element”，平均每个元素 1.125 次 CAS。
把三层帮助推进并排放：
| 层 | 谁在做 | 解决什么 | 代价 |
|---|---|---|---|
| tail 帮助 | 每个入队线程 | tail 落后于真实末尾 | 一次可能失败的 CAS |
| head 前移 + 自环 | 每个出队/peek 线程 | head 落后；旧指针在链外游荡 | 一次 CAS + 一次 release 写 |
| 死结点折叠 | 遍历/批量删除线程 | 逻辑删除后结点堆积 | 每 8 个结点一次 CAS |
教科书 MS 队列只有第一层。第二、三层是 JDK 为了"允许任意线程做逻辑删除"付的账——remove(Object)、removeIf、迭代器的 remove() 都会制造死结点，如果没人清理，一条长时间运行的队列会越走越慢。
在 libraryd-conc 里落地
借阅事件队列是典型的 MPSC：多个借阅线程往里投事件，一个审计线程消费。用 MS 队列实现，事件本身不可变，消费者只读：
package com.plume.conc.core;
import java.time.Instant;
/** 借阅事件：投递后不再修改，因此适合放进无锁队列。 */
public record BorrowEvent(String isbn, String memberId, Type type, Instant at) {
public enum Type { BORROW, RETURN, REJECT }
}
/** 多生产者单消费者的审计事件队列；内部就是本节那个 MS 队列。 */
public final class AuditEventQueue {
private final MSQueue<BorrowEvent> queue = new MSQueue<>();
public void publish(BorrowEvent event) {
queue.enqueue(event); // 永不阻塞，也不丢
}
/** 审计线程调用；队列空时返回 null，由调用方决定休眠还是让出。 */
public BorrowEvent poll() {
return queue.dequeue();
}
}
这里有个容易忽略的选择：为什么不用 ConcurrentLinkedQueue，自己写一个 MS 队列？答案是不该自己写。ConcurrentLinkedQueue 多了死结点折叠、弱一致迭代器、size()，这些在审计场景都会用到（比如按 ISBN 批量重放）。本节手写只是为了看清结构；生产代码用 ConcurrentLinkedQueue 就好。
真正需要"自己写无锁结构"的场景很少，一般是：元素是定长原始类型、想省掉装箱；或者需要 ConcurrentLinkedQueue 没有的操作（比如"批量取走前 N 个"）。后者的正确做法是在 MS 队列上包一层批量出队，而不是重写链表。
另一半落点是库存快照栈。“试算—回滚"是个天然的栈：借书前压一份库存快照，扣减失败就弹回来。
package com.plume.conc.core;
import java.util.concurrent.atomic.AtomicReference;
/** 库存快照栈：只在单线程内使用栈语义，跨线程只读最新快照。 */
public final class StockSnapshotStack {
public record Snapshot(String isbn, int stock, long version) {}
private final AtomicReference<Snapshot> latest = new AtomicReference<>();
public void push(Snapshot snapshot) {
Snapshot prev;
do {
prev = latest.get();
if (prev != null && prev.version() >= snapshot.version()) {
return; // 版本回退，丢弃这次试算
}
} while (!latest.compareAndSet(prev, snapshot));
}
public Snapshot current() {
return latest.get();
}
}
这个类暴露了一个重要边界：它叫"栈”，但没有 pop。因为并发场景下"弹出上一个快照"这件事本身就不安全——你不知道弹出来的是不是自己压的那一个。能安全并发的只是"比较并替换成一个更新的版本"，不是"回退到上一个"。 需要回滚时，压一个新的、版本号更高的快照（内容取旧的），而不是弹栈。
常见错误与边界
第一，把 head 或 tail 当权威位置读。ConcurrentLinkedQueue.size() 要遍历、isEmpty() 走 first()，都是因为这两个指针随时可能落后。任何 if (tail.next == null) 队列空 的判断都是错的。
第二，忘了 succ() 的自环判断。自己写遍历时直接 p = p.next，一旦遇到被摘除的节点就会原地打转或提前结束。JDK 的每个遍历方法都走 succ()，这不是风格问题。
第三，在无锁队列上做"批量原子操作"。if (!q.isEmpty()) q.poll() 这两步之间队列可能已经被别人清空，这不是 bug 而是语义——无锁容器的单个操作原子，组合不原子（15.2 会展开）。
第四，以为无锁一定比有锁快。本机 4 线程同抢一个栈顶时，Treiber 栈的 CAS 失败率是每次操作 2.3 次，吞吐反而比 ReentrantLock 低一个数量级，10.3 有完整数据。
第五，在 Node 里放可变字段。Treiber 栈的 pop 依赖"next 发布后不再变"这个不变量；一旦允许修改 next（比如做节点复用），ABA 立刻登场，10.2 专门讲。
小结
Treiber 栈的全部复杂度在一个 top 指针上：一次 CAS 完成 push 或 pop，节点发布后只读。MS 队列多了一个 tail，于是多了"帮助推进"这个义务——本机一百万次入队里，tail 有一百零六万次不是真实末尾，帮助不是异常分支而是主路径。ConcurrentLinkedQueue 在此之上又加了 item 的逻辑删除、updateHead 的自环路标、skipDeadNodes 的批量折叠和 MAX_HOPS = 8 的摊销参数，因为它的删除是"任意线程都可能发起"的，必须容忍死结点。
下一节处理这一节刻意绕开的问题：节点被复用时，引用相同不代表状态相同。
阅读导航：上一节 9.3 用 VarHandle 替换 Unsafe ｜ 下一节 10.2 ABA 与内存回收
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。