10 无锁：CAS、ABA，与你大概率不该写它的理由

CAS：一条指令，一个世界

Compare-And-Swap（比较并交换）是所有无锁结构的地基。它的语义是这样一个「原子的 if」：

/* CAS 的语义 —— 但这整个函数是「一条 CPU 指令」，不可分割 */
bool CAS(int *addr, int expected, int newval) {
    if (*addr == expected) {     /* 值还是我以为的那个吗? */
        *addr = newval;          /* 是 → 换成新值 */
        return true;             /* 成功 */
    }
    return false;                /* 不是 → 有人改过了,我失败了 */
}

/* x86:  LOCK CMPXCHG
   ARM:  LDREX / STREX (load-exclusive / store-exclusive)
   —— 硬件保证这个「读+比较+写」不会被任何东西打断。 */

用它写一个自增：

// 这是所有原子自增的真实实现
func Increment(addr *int64) {
    for {
        old := atomic.LoadInt64(addr)          // 1. 读当前值
        new := old + 1                          // 2. 算新值
        if atomic.CompareAndSwapInt64(addr, old, new) {
            return                              // 3. 换成功了 → 走人
        }
        // 换失败了 = 在 1 和 3 之间,有别人改了它
        // → 什么都不做,循环重来一次
    }
}
// 这个 for 循环叫「CAS 自旋」。它是无锁编程的基本形状。

◆ 定论 · 锁 vs CAS，本质区别是什么

	锁（悲观）	CAS（乐观）
态度	「肯定会有人来抢，我先把门锁上」	「大概没人来抢，我先干，干完检查一下有没有被人插队」
冲突时	挂起线程（陷内核，~1µs）	重试（纯用户态自旋，~几十 ns）
低竞争	快（futex 快路径）	更快
高竞争	还行 —— 大家排队睡觉，不烧 CPU	很糟 —— 一堆线程在疯狂自旋重试，烧 CPU，而且大部分重试都失败
有死锁吗	有	没有（不持有任何东西，怎么会死锁）
有饥饿吗	可能有	有 —— 某个倒霉线程可能永远 CAS 失败（这叫 lock-free 但不是 wait-free）

关键反直觉：CAS 不是「永远更快」。它在高竞争下会比锁更慢 —— 因为自旋在烧 CPU，而且每次失败的 CAS 都会让那条缓存行在核之间弹一次（第 6 章）。

「无锁」不等于「没有等待」

这是个术语坑，值得澄清：

lock-free（无锁）：保证至少有一个线程能取得进展。不保证每个线程都能。—— CAS 自旋属于这一类：某个倒霉的线程可能一直 CAS 失败（饥饿），但整个系统一定在推进。
wait-free（无等待）：保证每一个线程都能在有限步内完成。这个要求强得多，算法也复杂得多。
（有意思的是：atomic.AddInt64 / getAndIncrement 是 wait-free 的 —— 因为 x86 的 LOCK XADD 是一条指令，硬件层面就完成了，不需要重试循环。而你手写的 CAS 循环只是 lock-free。）
obstruction-free：最弱的一档。只保证「如果其他线程都停下来，我能完成」。

ABA 问题：值回来了，但世界变了

CAS 的判据是「值还是我以为的那个吗」。这个判据有个致命的洞：

值可以变回去。

ABA：一个无锁栈的灾难栈：A → B → C

线程 1 读 top=A，准备 CAS(top, A, B) 被抢占，睡了一会儿… 醒来：top 还是 A？CAS 成功！

线程 2 pop A pop B free(B)! push A 回来

灾难线程 1 醒来时，top 确实还是 A —— 所以它的 CAS 成功了。
于是它把 top 设成了 B。
但 B 已经被 free 掉了。整个栈现在指向一块已释放的内存。
CAS 成功了，数据结构毁了。而且这个 bug 会在很远的地方以「随机崩溃」的形式出现。

怎么修 ABA

方案	做法	用在哪
版本号 / 标签指针	CAS 的不是「指针」，是「指针 + 版本号」。每次改动版本号 +1。 A → B → A 之后，版本号从 5 变成了 7，CAS 就会失败。	Java 的 `AtomicStampedReference` x86-64 的 `CMPXCHG16B`（一次原子地比较交换 128 位）
GC 帮你挡了	Java / Go / Python 里，ABA 在「内存被释放」这个层面上基本不存在 —— 因为只要线程 1 还持有对 B 的引用，GC 就不会回收它。	这是托管语言的一个隐形福利。但注意：逻辑上的 ABA 仍然可能出问题（比如「余额从 100 变到 50 再变回 100」，你的 CAS 会认为「没人动过」—— 而实际上发生了两笔交易）。
Hazard Pointer / RCU / Epoch	手工的「延迟回收」机制：在没有任何线程可能还在访问这块内存之前，不要真的释放它。	C/C++ 的无锁库、Linux 内核（RCU）、Rust 的 `crossbeam`（epoch-based）。这是无锁编程真正难的地方 —— 不是算法，是内存回收。

内存序：那些 acquire / release 到底在说什么

如果你写 C++ 或 Rust 的原子操作，会看到一堆 memory_order_*。它们说的是「这个原子操作，顺便帮我挡住哪些重排」（回到第 6 章）：

内存序	保证	什么时候用
`relaxed`	只保证这个操作本身是原子的，不挡任何重排	纯计数器（比如统计指标）—— 你只关心最终总数对，不关心顺序
`acquire`（读）	这个读之后的操作，不许被重排到它之前	「拿锁」的那一侧 / 读一个标志位
`release`（写）	这个写之前的操作，不许被重排到它之后	「放锁」的那一侧 / 写一个「我准备好了」的标志位
`seq_cst` （顺序一致，默认）	全局有一个统一的操作顺序，所有线程看到的一样。最强，也最慢。	不确定的时候用它。Java 的 `volatile`、Go 的 `sync/atomic` 给的都是这个级别。

acquire/release 配对，就是一次 happens-before 的建立：

/* 生产者 */
data = 42;                                 /* 普通写 */
atomic_store_explicit(&ready, 1, release); /* release 写:上面那行不许被排到我后面 */

/* 消费者 */
if (atomic_load_explicit(&ready, acquire)) /* acquire 读:下面那行不许被排到我前面 */
    assert(data == 42);                    /* 保证成立! */

/* 这就是「release-acquire 配对」——
   它是所有锁、所有 channel、所有 Future 的底层原理。 */

◈ 三语 · 你需要关心内存序吗

Kotlin/Java：不需要。volatile 和 Atomic* 直接给你 seq_cst。
（JDK 9+ 有 VarHandle 能让你玩细粒度内存序 —— 如果你在用它，你应该知道自己在干嘛。）
Go：不需要，而且不给你选。Go 的 sync/atomic 只提供 seq_cst。Go 团队故意不暴露弱内存序 —— Russ Cox 的原话大意是：「这是一个几乎所有人都会用错的工具。」这是一个正确的产品决策。
Python：不需要。GIL 覆盖了一切。
C++ / Rust：需要，而且这是你痛苦的来源。

现在，那个不讨喜的忠告

⚠ 陷阱 · 不要手写无锁数据结构

除非你在写基础库，否则：不要。

理由一：你算的账是错的。你以为无锁比锁快 —— 但第 9 章说过，没竞争的锁只要几纳秒。而高竞争下的 CAS 自旋会比锁更慢。所以无锁的性能优势窗口，比你想的窄得多。你有测过吗？

理由二：正确性极难验证。一个无锁队列的正确性证明，是一篇论文的工作量。Michael-Scott 无锁队列（1996）是并发领域的经典之作 —— 它只有几十行代码，而它的论文有 9 页。而且业界后来还在它的变体里发现过 bug。

理由三：错了不会崩，会静静地腐蚀数据。锁写错了通常是死锁（响亮地失败，好定位）。无锁写错了是数据结构被破坏（安静地失败，在很远的地方以随机崩溃/数据不一致的形式出现）。后者贵一百倍。

理由四：现成的已经足够好了。ConcurrentHashMap、LongAdder、ConcurrentLinkedQueue、Go 的 sync.Map、channel —— 这些是 Doug Lea、Russ Cox 这个级别的人，花了很多年，配合形式化验证和大规模压测写出来的。你的下午写不出更好的。

◆ 定论 · 那你该用 CAS 吗？该，但用在这三个地方

用现成的原子类型。AtomicInteger / atomic.Int64 / LongAdder。计数器、标志位、状态机的状态字段 —— 这些场景 CAS 是最优解，而且已经封装好了。

用 CAS 做「乐观更新」。这是个非常实用的模式，而且它的思想能直接搬到分布式系统里：

// 无锁地更新一个不可变的配置对象(写时复制)
for {
    old := config.Load()             // atomic.Pointer[Config]
    new := old.WithTimeout(5)        // 造一个新的(不改老的!)
    if config.CompareAndSwap(old, new) {
        break                        // 换成功了
    }
    // 失败 = 有人先改了 → 拿新的重来
}
// 读者:config.Load() —— 完全无锁,零开销。
// ↑ 这个模式在「读极多、写极少」的配置/路由表场景下是最优的。

认出它的分布式版本。数据库的乐观锁（UPDATE ... WHERE version = 3）、HTTP 的 If-Match / ETag、etcd 的 compare-and-swap —— 它们全都是 CAS，只是把「一条 CPU 指令」换成了「一次网络往返」。理解了 CAS，你就免费理解了这一整类。

🕘 掌故 · Go 为什么把 sync.Map 藏起来

Go 有一个 sync.Map，无锁读、性能很好。但 Go 官方文档明确说：

「大多数代码应该用普通的 map 加锁。sync.Map 是为两种特定场景设计的：(1) key 写一次读多次；(2) 多个 goroutine 各读写不相交的 key 集合。」

这是一个很有品味的态度：他们提供了这个工具，但同时明确地告诉你「你大概率不需要它」。

而在很多真实基准测试里，普通 map + sync.RWMutex 在通用场景下比 sync.Map 更快 —— 因为 sync.Map 为了无锁读付出的簿记成本，在写稍微多一点时就赚不回来。

教训：「更高级的并发原语」≠「更快」。永远先测。

✚ 动手

1. 写一个基准测试对比三种计数器：synchronized 的、AtomicLong 的、LongAdder 的。先跑 1 个线程，再跑 32 个线程。你会看到排名完全颠倒 —— 这一次测量会教会你「性能要看竞争度」这件事。

2. 把上面那个「写时复制配置」的模式，在你项目里找一个地方用上。（热更新的配置、路由表、feature flag —— 这些都是完美的场景。）

3. 下次有人在设计评审上提「我们手写一个无锁队列」时，问他三个问题：你测过锁的版本吗？你打算怎么处理 ABA？你打算怎么验证它是对的？

幕 II 结束。你现在知道机器是怎么运作的了 —— 缓存、重排、锁、CAS。接下来是本书的主体：三门语言，站在这些机器之上，各自搭了一个完全不同的抽象。而它们的分歧，从二十年前的一个架构选择就开始了。