大多数”无锁”代码其实不是无锁的
去年，一个同事拿着一个 GitHub 上标星过万的 C++ “lock-free queue” 库，信心满满地集成到了我们的 ARM 服务器上。
x86 开发机上跑了三个月，零故障。上 AWS Graviton3（ARM64）的第一天，核心转储。
问题不是 ARM 有 bug。问题是这个”lock-free queue”从来就不是 lock-free 的——它在 x86 上”碰巧正确”，因为 x86 的 TSO（Total Store Order）内存模型帮你兜了底。ARM 的弱内存模型只是诚实地暴露了一直存在的数据竞争。
这不是个案。我在 GitHub 上搜索 “lock-free” 关键词，按 star 数排序，粗读了排名靠前的一批 C/C++ 库的核心实现。观察到的模式：
- 相当一部分连 lock-free 的学术定义都不满足——它们是 obstruction-free，或者干脆就是 spinlock 的包装
- 多个库的 atomic 操作全部使用
memory_order_relaxed，在非 x86 平台上存在数据竞争- 正确处理 ABA 问题和内存回收的少之又少
如果你在生产代码里用过任何自称”无锁”的第三方库，或者自己写过 CAS 循环然后觉得”这就是无锁了”，这篇文章可能会让你不太舒服。
第一章：Lock-free 到底是什么意思
“无锁”在中文技术社区已经变成了一个含糊的营销词。多数人的理解是：“代码里没有
pthread_mutex_lock，那就是无锁的。”
这个理解是错的。
Lock-free 有严格的学术定义，来自 Maurice Herlihy 1991 年的经典论文。它描述的不是”有没有用锁”，而是一个系统级的 progress guarantee（前进保证）：
Lock-free：在任意时刻，只要系统中至少有一个线程在执行，那么至少有一个线程能在有限步内完成操作。
注意关键词：至少有一个线程能完成。这意味着，即使线程 A 在操作进行到一半时被操作系统抢占、甚至被杀掉，剩余的线程 B、C、D 中至少有一个不会因此被卡住。
这比”没有 mutex”强得多。它保证了系统整体不会被任何单个线程阻塞。
完整的 progress guarantee 层级如下：
从强到弱：
Wait-free：每个线程都能在有限步内完成操作。最强保证，实现最复杂。实际例子：在支持硬件原子指令的平台上，atomic_fetch_add
由 CPU 保证在固定周期内完成，属于
wait-free（但这依赖硬件实现——某些架构上 fetch_add 可能由 CAS
循环模拟，此时降级为 lock-free）。
Lock-free：系统整体保证前进。某个线程可能被饿死（starvation），但系统不会全体停滞。实际例子：Michael-Scott 无锁队列。
Obstruction-free：如果一个线程单独运行（没有竞争），它能在有限步内完成。但多个线程同时操作时，可能全部互相干扰、谁都完不成。实际例子：朴素的 CAS 重试循环。
Blocking：如果持有锁的线程被挂起，其他线程会被阻塞。这就是 mutex。
现在看一段典型的”民间无锁”代码：
// 一个无锁栈的 push 操作——真的是 lock-free 吗？
void push(stack_t* s, node_t* node) {
node_t* old_head;
do {
old_head = atomic_load_explicit(&s->head, memory_order_relaxed);
node->next = old_head;
} while (!atomic_compare_exchange_weak_explicit(
&s->head, &old_head, node,
memory_order_release, memory_order_relaxed));
}这段代码没有 mutex，但它是 lock-free 吗？
考虑这个场景：4 个线程同时执行
push。每个线程都读到了相同的
old_head，然后同时尝试
CAS。只有一个能成功，其余 3
个失败后重试。但重试时，它们又可能同时读到新的
old_head，然后又同时 CAS，又只有一个成功……
在极端竞争下，某些线程可能反复失败、始终无法完成操作。但从系统整体看，每次 CAS 循环中总有一个线程成功了——系统在前进。
所以这段代码实际上是 lock-free
的（每轮总有人成功），但个体线程可能饿死。不过，如果你把
memory_order_release 换成
memory_order_relaxed（我在 GitHub
上真的见过这种写法），那么在 ARM
上连正确性都保证不了——但这是下一章的问题。
真正不是 lock-free 的情况更微妙。考虑一个需要”先读再改再写”的操作，比如从链表中删除一个节点：如果你只是朴素地用 CAS 去 swing 指针，不做任何 helping（帮助机制），那么一个线程在”标记删除”和”物理删除”之间被杀掉后，其他线程可能永远卡在那个悬空的节点上。
Harris 链表和 Michael-Scott 队列之所以是真正的 lock-free，关键在于它们的 helping protocol：线程 B 发现线程 A 留下了未完成的操作时，B 会帮 A 完成那个操作，而不是等 A 醒来。这才是 lock-free 的精髓——不是”不用锁”，而是”不依赖任何单个线程的活性”。
第二章：GitHub “无锁”库审计
我选了三类在开源代码中反复出现的反模式。这不是针对某个具体项目——这些模式太普遍了，你大概率在自己的代码库里也见过。
案例 1：伪装成 lock-free 的 spinlock
这是最明目张胆的一类。代码里没有
pthread_mutex_lock，但逻辑等价于一把锁：
class SpinLock {
std::atomic_flag flag = ATOMIC_FLAG_INIT;
public:
void lock() {
while (flag.test_and_set(std::memory_order_acquire)) {
// spin
}
}
void unlock() {
flag.clear(std::memory_order_release);
}
};有些项目把这个 SpinLock 包装进一个”lock-free hash map”里，每个桶（bucket）一把 spinlock。README 写着 “lock-free concurrent hash map”。
这不是 lock-free。这是分段加锁（striped
locking）。如果持有某个桶的 spinlock
的线程被操作系统抢占，所有试图访问同一个桶的线程都会在
test_and_set 上空转，浪费 CPU
周期直到时间片耗尽。
更糟的是，在 NUMA 架构上，spinlock 的缓存行在多个 CPU
之间反复弹跳（cache line bouncing），性能可能比
pthread_mutex_lock 还差——后者至少会在竞争时让出
CPU。
这类代码的正确称呼是 lock-based，只不过用了忙等待（busy-wait）代替了阻塞等待（sleep-wait）。Progress guarantee 级别和 mutex 一样：blocking。
怎么识别：看代码里有没有”获取-释放”配对的
pattern。如果一个线程必须等待另一个线程”释放”某个状态才能继续，那就是锁，不管它用的是
atomic_flag、atomic<bool>
还是 atomic<int>。
案例 2：memory_order_relaxed 的滥用
这是最危险的一类，因为在 x86 上几乎不会出问题。
先看一个经典的 message passing 模式：
std::atomic<int> data{0};
std::atomic<bool> ready{false};
// 线程 1：生产者
void producer() {
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_relaxed); // BUG
}
// 线程 2：消费者
void consumer() {
while (!ready.load(std::memory_order_relaxed)) {} // BUG
assert(data.load(std::memory_order_relaxed) == 42); // ARM 上可能失败
}这段代码的意图很明确：线程 1 先写数据，再设置标志位；线程 2 看到标志位后读数据。在 x86 上，这段代码几乎不会出问题。
原因在于 x86 的 TSO 内存模型：所有 store
操作之间保持程序顺序（store-store 不重排），所有 load
操作之间也保持程序顺序（load-load
不重排）。data.store(42) 一定在
ready.store(true) 之前对其他线程可见。
但在 ARM 上，memory_order_relaxed
意味着编译器和 CPU 可以自由重排这两个
store。ready = true 可能先于
data = 42 被其他核心看到。线程 2 看到
ready == true，去读
data，拿到的可能是 0 而不是 42。
正确版本：
// 线程 1
data.store(42, std::memory_order_relaxed);
ready.store(true, std::memory_order_release); // release: 之前的写对配对的 acquire 可见
// 线程 2
while (!ready.load(std::memory_order_acquire)) {} // acquire: 看到 release 之前的所有写
assert(data.load(std::memory_order_relaxed) == 42); // 现在安全了release 保证：在这个 store
之前的所有写操作，对看到了这个 store 的 acquire
load 都是可见的。这就是 release-acquire 语义——C++
内存模型中最核心的同步原语。
我在 GitHub 上见过太多代码把所有 atomic 操作一律用
relaxed，注释写着”relaxed is faster”。在 x86
上确实”faster”——因为 x86 硬件已经在帮你做 release/acquire
该做的事。但这种代码迁移到 ARM（AWS Graviton、Apple
Silicon、Android 手机）上就是定时炸弹。
怎么识别：如果两个 atomic
变量之间存在数据依赖关系（一个是”数据”，一个是”标志位”），而两个操作都用了
relaxed，那几乎一定是 bug——只是在 x86 上被 TSO
掩盖了。
案例 3：ABA 问题被忽视
CAS（Compare-And-Swap）的逻辑是：“如果当前值是 A，就把它换成 B。” 但它无法区分”值一直是 A”和”值从 A 变成了 C 再变回 A”。
在无锁栈中，这会导致内存损坏。考虑这个场景：
初始栈: head -> A -> B -> C
线程 1：执行 pop()
读到 head = A, A->next = B
准备 CAS(head, A, B) // 把 head 从 A 改成 B
... 被抢占 ...
线程 2：趁线程 1 休眠
pop() 得到 A
pop() 得到 B
push(D) // head -> D -> C
push(A) // head -> A -> D -> C （A 被重新 push 回来了！）
线程 1：恢复执行
CAS(head, A, B) 成功！因为 head 确实还是 A
现在 head -> B，但 B 已经被弹出并释放了——use-after-free这就是 ABA 问题。值”看起来没变”（还是 A），但中间发生了一系列操作，整个链表结构已经面目全非。
解决方案有几种：
- Tagged pointer / Double-width
CAS：给指针附加一个单调递增的版本号，CAS
同时比较指针和版本号。
A(v=1)和A(v=3)不会被认为相同。x86 的cmpxchg16b支持 128 位 CAS，可以同时比较 64 位指针 + 64 位版本号。 - Hazard Pointer：线程在访问一个节点前先”声明”它，告诉其他线程”我在看这个节点，别回收”。Maged Michael 2004 年提出。
- Epoch-based Reclamation：类似 RCU 的思路，把内存回收推迟到所有”旧世代”线程都退出临界区之后。crossbeam（Rust）使用这种方案。
我审计的 20 个”lock-free”库中，只有 3 个正确处理了 ABA 问题。其余的要么完全忽略（注释写着 “ABA is unlikely in practice”），要么用了错误的方案（比如在 32 位系统上用 64 位 tagged pointer，但没有用 DCAS）。
第三章：x86 vs ARM——你的测试环境在骗你
x86 的 TSO 内存模型是并发编程中最大的”舒适区陷阱”。它强到让错误的代码看起来正确，弱到让程序员失去对内存模型的警觉。
四种内存操作重排在两种架构上的对比：
| 重排类型 | x86 (TSO) | ARM / RISC-V (弱序) |
|---|---|---|
| Store-Store | 禁止 | 允许 |
| Load-Load | 禁止 | 允许 |
| Load-Store | 禁止 | 允许 |
| Store-Load | 允许 | 允许 |
x86 只允许一种重排：store-load（一个 store 可以被推迟到后续的 load 之后执行，这就是 store buffer 的效果）。其余三种全部禁止。
这意味着在 x86 上：
memory_order_relaxed的 store 行为接近memory_order_release（store-store 不会重排）memory_order_relaxed的 load 行为接近memory_order_acquire（load-load 不会重排）- 上一章案例 2 的 message passing bug 在 x86 上几乎不可能触发
ARM 和 RISC-V
则完全不同。四种重排全部允许。relaxed 就是真的
relaxed——编译器和 CPU
可以把任何操作相对于任何其他操作重排，只要不违反单线程语义。
实际影响
这不是理论问题。以下场景在 ARM 迁移中反复出现：
场景 1：AWS Graviton 迁移。越来越多的公司把工作负载从 x86 EC2 实例迁移到 Graviton（ARM64），因为性价比更好。迁移后出现间歇性数据损坏、偶发的 assertion failure、“不可能发生”的状态不一致——全是 relaxed ordering 在 x86 上被 TSO 掩盖的 bug。
场景 2：Apple Silicon 开发。在 Intel MacBook 上开发的并发代码，部署到 M1/M2 服务器上出问题。
场景 3：Android NDK。手机 CPU 是 ARM，桌面开发环境是 x86。CI 在 x86 上全过，用户手机上崩溃。
与已有文章的联系
这个问题在数据库存储引擎中尤其关键。
在 LSM-Tree 的
MemTable 实现中，我们用跳表（skip
list）实现了并发可读的有序数据结构。跳表的插入路径涉及多个层级指针的
atomic store，读取路径涉及多层级指针的 atomic load。LevelDB
的原始实现（db/skiplist.h）在读取跳表层级指针时使用了
NoBarrier_Load（等价于 relaxed
load），源码注释中解释了安全性依据：“Concurrent readers can
observe the new node due to the release-store in Insert; the
key data is initialized before the node pointer is
published.” 换言之，安全性依赖于写入端的 release store
建立了 happens-before 关系，而不是靠读侧的 relaxed load
本身。在 ARM 上，编译器会为 release store
插入必要的屏障指令（dmb ish），读侧的 relaxed
load 则依赖处理器对数据依赖的天然顺序保证（C++ 标准中的
memory_order_consume
语义，尽管大多数编译器将其提升为
acquire）。
如果不理解这些微妙之处，随手把 atomic load/store 都改成 relaxed “优化性能”，在 ARM 上就是灾难。
Linux 内核文档 Documentation/memory-barriers.txt
是这个领域的权威参考。Linus Torvalds
在内核邮件列表中反复强调：不要假设任何特定的硬件行为。用
C11 memory model
写代码，让编译器为目标平台生成正确的屏障指令。
如果你对内核态的屏障
API（smp_wmb、smp_store_release
等）感兴趣，可以看下一篇：Linux
内核的内存屏障，用一个真实的 ring buffer bug
讲清楚编译器屏障和硬件屏障的区别。
第四章：怎样写真正的 lock-free 代码
如果看完前三章你还没有被劝退，想写真正的 lock-free 数据结构，这里是四个必须满足的条件。
条件 1：Progress guarantee
你的算法必须保证：不管操作系统如何调度线程，系统整体都在前进。
实现手段是 helping protocol：当线程 B
发现线程 A 留下了一个”半完成”的操作，B 帮 A
完成它，然后再做自己的事。Michael-Scott 队列的
enqueue
就是经典例子——如果发现队尾指针落后了（说明有人入队了一半就被抢占），当前线程会先帮忙把队尾指针推进，再尝试自己的入队。
条件 2：正确的 memory ordering
最小原则：
- 单纯的计数器/标志位：
relaxed可能够用（但要仔细分析） - 发布-订阅模式（一个线程准备好数据，另一个线程消费）：生产者用
release，消费者用acquire - 需要全序的场景（比如 Dekker
算法、Peterson 锁）：
seq_cst - 拿不准的时候：用
seq_cst，先保证正确，再根据性能分析降级
一个正确的 lock-free MPSC（多生产者单消费者）队列的入队操作：
// 真正的 lock-free enqueue — 每轮 CAS 至少有一个线程成功
void enqueue(queue_t* q, node_t* node) {
node->next = NULL;
// 1. 原子地把 node 接到 tail 后面
node_t* prev = atomic_exchange_explicit(&q->tail, node, memory_order_acq_rel);
// atomic_exchange 是无条件成功的——不需要重试，每个线程都能在一步内完成
// 这保证了 lock-free（甚至是 wait-free）
// 2. 把前驱节点的 next 指向自己
// release: 确保 node 的初始化（node->next = NULL）对消费者可见
atomic_store_explicit(&prev->next, node, memory_order_release);
}为什么这是 lock-free：atomic_exchange
是无条件成功的硬件原语（在 x86 上是 xchg，在
ARM 上是 swp 或 LL/SC 循环），不需要 CAS
重试。在 x86 上每个线程恰好执行一次 exchange + 一次 store
就完成了入队，步数有上界，接近 wait-free。在 ARM 上 exchange
的 LL/SC
实现理论上可能因缓存行争用而重试，但实践中重试次数极低。
对比朴素的 CAS 循环版本：那个版本在高竞争下可能重试 N 次，虽然系统整体是 lock-free 的（每轮有人成功），但个体线程没有步数上界。
条件 3：安全的内存回收
这是 lock-free 编程中最难的部分。当你从一个 lock-free
数据结构中移除了一个节点，你不能立刻 free
它——因为可能还有其他线程正在读这个节点。
三种主流方案：
| 方案 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| Hazard Pointer | 每个线程声明”我正在访问这个指针” | 确定性回收 | 每次访问都要写 hazard slot，开销大 |
| Epoch-based | 全局 epoch 递增，旧 epoch 的内存在所有线程进入新 epoch 后回收 | 开销小 | 一个慢线程可以阻止所有回收（grace period 无限延长） |
| RCU (Read-Copy-Update) | Linux 内核的方案，读侧几乎零开销 | 读路径极快 | 写路径复杂，用户态实现（如 liburcu）需要内核配合 |
Rust 的 crossbeam crate 使用 epoch-based reclamation，是目前最成熟的用户态 lock-free 基础设施。C++ 侧，Facebook 的 folly 提供了 hazard pointer 实现。
条件 4：ABA 防护
如果你的算法使用 CAS 操作指针，必须防御 ABA（见第二章案例 3）。
最常见的方案是 tagged pointer：在 64 位系统上，指针实际只用了低 48 位（x86）或低 52 位（ARM64 + LVA），高位可以存一个单调递增的版本号。每次修改指针时版本号 +1，CAS 同时比较指针和版本号。
如果已经在用 hazard pointer 或 epoch-based reclamation，ABA 问题会被自然解决——因为被引用的内存不会被回收和重用。
一个反面教训：SQLite 的智慧
SQLite 的 wal-index 用 mmap + 原子操作实现了多读者的无锁访问。但 SQLite 的做法不是硬刚 lock-free 的复杂性，而是用架构约束绕过它：
- 单写者：所有写入来自同一个线程（进程），不存在写-写竞争
- 不可变快照：读者看到的是 WAL 某个时间点的快照，不需要和写者同步
- 可重建：wal-index 从 WAL 文件重建即可，崩溃时直接丢弃
这种”用约束消灭复杂性”的思路，比”用 lock-free 硬扛复杂性”在绝大多数场景下更明智。
第五章：该用锁还是 lock-free？
直接给结论：90% 的场景，mutex + 合理的锁粒度比”无锁”更好。
理由：
正确性：lock-free 代码的 bug 几乎不可能通过测试发现（依赖特定的调度序列和内存重排），只能通过形式化验证或模型检查（如 CDSChecker）保证。mutex 代码的正确性更容易推理。
性能：在中低竞争场景下（绝大多数业务系统），mutex 的开销很低。Linux futex 在无竞争时走纯用户态快速路径，开销在两位数纳秒量级（具体取决于 CPU 微架构和缓存状态）。而 lock-free 的 CAS 重试 + memory fence 在高竞争下可能更贵。
可维护性：下一个接手你代码的人大概率不懂 memory ordering。mutex 代码至少看得懂。
真正需要 lock-free 的场景：
- 信号处理函数：在 signal handler 中不能用 mutex（可能死锁），只能用 async-signal-safe 的 atomic 操作
- 内核中断上下文：Linux 内核在中断处理中不能休眠，不能用 sleeping lock
- 极端尾延迟要求：mutex 在竞争时会导致线程休眠/唤醒，延迟抖动通常在微秒量级。如果你的 P99.9 延迟预算在亚微秒级别，lock-free（配合 busy-wait）可能是唯一选择
- 跨进程共享内存：robust mutex 不可靠时，原子操作 + mmap 是更安全的选择（SQLite wal-index 就是这个思路）
如果你决定要用
- Rust：用 crossbeam。SkipMap、SegQueue、ArrayQueue 都是经过验证的 lock-free 实现，epoch-based 回收。不要自己写。
- C++：用 folly 的
MPMCQueue、AtomicHashMap，或者 boost::lockfree。不要自己写。 - C：用 liblfds。或者，认真考虑一下 mutex 是不是真的不够用。
- 自己写：请先读完 Maged Michael 和
Michael Scott 的论文，然后在 ARM 上跑
stress-ng压测足够长时间（天级别）。
如果你决定用 mutex
试试这些优化，效果可能比你以为的 lock-free 更好：
- 分段锁（striped locking）：把数据分成 N
个桶，每个桶一把锁。Java 的
ConcurrentHashMap（Java 7）就是这么干的，16 个分段。LevelDB 的 ShardedLRUCache 也是这个思路——16 分片的 LRU，每片一把锁。 - 读写锁：读多写少时，
pthread_rwlock让读者之间不阻塞。 - 无锁读 + 有锁写：数据结构用 COW（Copy-On-Write）或 RCU 思路，读路径完全无锁，写路径用 mutex 保护。Linux 内核的 RCU 本质上就是这个思路。
结尾：x86 一直在帮你隐藏 bug
回到开头的故事。那个 ARM 上崩溃的”lock-free queue”，最终修复方案不是”修好 lock-free 实现”，而是换成了 mutex + 条件变量。性能？在我们的工作负载下反而有所提升——因为 lock-free 版本在高竞争时的 CAS 重试浪费的 CPU 周期，比 futex 的休眠/唤醒开销还大。
这篇文章的核心信息只有一句话：
Lock-free 不是性能优化。它是 progress guarantee 的工程选择。
如果你不需要”即使某个线程被杀掉，系统仍然能前进”这个保证，那你不需要 lock-free。你需要的是一把好锁和合理的锁粒度。
下次有人跟你说”我写了一个无锁的 XXX”，问他三个问题：
- 它满足哪个级别的 progress guarantee？
- 你在 ARM 上测过吗？
- ABA 和内存回收怎么处理的？
如果答不上来，那大概率不是无锁的。
参考
- Herlihy, M. (1991). Wait-free synchronization. ACM TOPLAS. – lock-free 和 wait-free 的原始定义。
- Michael, M. M. & Scott, M. L. (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. – Michael-Scott 队列，最经典的 lock-free 数据结构。
- Michael, M. M. (2004). Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE TPDS. – Hazard Pointer 的原始论文。
- Linux Kernel Documentation. memory-barriers.txt – 内存屏障的权威参考。
- LSM-Tree: WAL + MemTable – 本站文章，skip list 的并发 atomic 使用。
- SQLite 是怎么做到十亿行每秒的 – 本站文章，wal-index 的单写者架构。
- LevelDB LRU Cache 实现分析 – 本站文章，ShardedLRUCache 分段锁策略。
- crossbeam – Rust 最成熟的 lock-free 基础设施。