无锁数据结构的实现原理CAS 操作的正确性与 ABA 问题一、锁是跑车堵在三环CAS 是走应急车道在高并发后端系统中数据竞争是一个绕不开的话题。最常见的解决方案是加锁——synchronized、ReentrantLock、读写锁各种锁机制为开发者提供了便捷的互斥访问保证。但锁有一个与生俱来的问题当一个线程持有锁时其他所有需要访问同一数据的线程全部阻塞等待。在高竞争场景下线程上下文切换的开销甚至可能超过业务逻辑本身。有没有一种办法完全不使用锁却能在多线程环境下安全地修改共享数据答案就是 CAS——Compare And Swap比较并交换。它不是通过阻塞来实现互斥而是通过乐观重试来完成原子更新。打个比方锁是红灯停绿灯行CAS 是看到没车就过有车就退回来重新看。二、CAS 的底层指令支持与原子性保证CAS 操作在 Java 中以Unsafe.compareAndSwapInt等形式暴露出来在 JDK 层面由AtomicInteger、AtomicReference等进行封装。但真正的原子性保证来源于 CPU 指令层面。在 x86 架构下CAS 对应的是CMPXCHG指令。当加上LOCK前缀时CPU 会锁定总线或缓存行确保在比较和交换的整个过程中没有其他核心能修改同一块内存。这是硬件级的原子性保证比操作系统层面的锁轻量得多。ARM 架构则使用LDREX/STREX指令对来实现类似效果。LDREX加载值的同时标记该内存地址STREX存储时检查标记是否仍然有效——如果其他核心在此期间修改了这块内存标记失效存储失败。这和 CAS 的逻辑是等价的都是乐观并发控制的硬件表达。值得注意的是CAS 只保证单个变量的原子性。如果需要同时对两个共享变量进行原子更新单个 CAS 无法胜任必须引入更复杂的机制。三、无锁栈的实现与关键注释下面用 Java 实现一个基于 CAS 的无锁栈。和ConcurrentLinkedDeque的思路类似但把复杂度降到最低只关注 CAS 本身的工作方式。import java.util.concurrent.atomic.AtomicReference; /** * 基于 CAS 的无锁栈 * * 核心思路 * - 使用 AtomicReference 持有栈顶节点的引用 * - push 和 pop 都通过 CAS 循环尝试直到成功 * - 不需要任何显式锁 * * 为什么这样设计 * - 栈只有栈顶一个竞争点是 CAS 的最佳应用场景之一 * - 每个操作只涉及一个 CAS 变量避免了多变量原子更新的难题 */ public class LockFreeStackT { // 栈顶节点的原子引用。所有线程通过 CAS 竞争修改这个引用 private final AtomicReferenceNodeT top new AtomicReference(null); /** * 节点定义值 指向下一个节点的引用 */ private static class NodeT { final T value; final NodeT next; Node(T value, NodeT next) { this.value value; this.next next; } } /** * 入栈操作 * * 逻辑 * 1. 读取当前栈顶 oldTop * 2. 创建新节点其 next 指向 oldTop * 3. CAS 尝试将栈顶从 oldTop 更新为新节点 * 4. 如果 CAS 失败说明有并发 push 或 pop重新读取重试 */ public void push(T value) { // 创建新节点。value 不可为 null避免 ABA 问题中 null 值的歧义 NodeT newNode new Node(value, null); while (true) { // 读取当前栈顶 NodeT oldTop top.get(); // 新节点的 next 指向当前栈顶 newNode.next oldTop; // CAS 尝试如果栈顶仍然是 oldTop就更新为 newNode // 这里使用 AtomicReference 的便捷方法简化 CAS 逻辑 if (top.compareAndSet(oldTop, newNode)) { return; // CAS 成功入栈完成 } // CAS 失败说明有其他线程修改了栈顶循环重试 } } /** * 出栈操作 * * 逻辑与 push 对称 * 1. 读取当前栈顶 oldTop * 2. 如果栈为空返回 null * 3. CAS 尝试将栈顶从 oldTop 更新为 oldTop.next * 4. 如果 CAS 失败重试 */ public T pop() { while (true) { NodeT oldTop top.get(); if (oldTop null) { return null; // 栈空返回 null } NodeT newTop oldTop.next; // CAS 尝试将栈顶从 oldTop 改为 newTop if (top.compareAndSet(oldTop, newTop)) { return oldTop.value; // 成功弹出 } // CAS 失败重试 } } /** * 判断栈是否为空 */ public boolean isEmpty() { return top.get() null; } }代码中有几个细节值得展开讨论。compareAndSet方法的参数语义是如果当前值等于期望值 oldTop就原子地更新为新值。这个过程在 CPU 层面是单条指令完成的中间不会被其他线程打断。CAS 失败后的循环重试就是所谓的自旋。在高竞争场景下自旋会消耗 CPU 周期但因为不涉及线程挂起和上下文切换在短时间内比锁的代价更低。四、ABA 问题的本质与解决方案CAS 机制有一个著名的陷阱ABA 问题。假设栈顶节点的值是 A。线程 1 读到 A准备做 CAS。在线程 1 执行 CAS 之前线程 2 连续做了两次操作首先弹出 A栈顶变成 B然后又推入 A栈顶变回 A。线程 1 再次 CAS 时会发现栈顶仍然是 A——但此时 A 的语义已经变了它下面的节点已经不是线程 1 以为的那个 B 了。这就是 ABA 问题的本质CAS 只能判断值有没有变但无法判断值变了几次又变回来了。在栈这个场景下ABA 问题可能导致 pop 操作错误地将一个已经被释放的节点当作栈顶来操作。解决 ABA 问题的主流方案有两种。第一种是加版本号。Java 的AtomicStampedReference在引用之外附加一个整型版本号每次 CAS 不仅检查引用是否一致还检查版本号是否匹配。第二种是让节点不可变且不回收。无锁栈中的节点在 pop 后虽然从栈中移除但只要还有线程持有对它的引用就不真正回收——这依赖于 GC 的延迟回收特性。在实际工程中对于简单的无锁栈来说Java 的 GC 已经天然解决了 ABA 问题。因为被 pop 的节点不会被立即释放旧引用指向的仍然是有效的对象。但在 C/C 等手动内存管理环境中这就成了一个必须显式处理的问题。五、总结CAS 是无锁编程的基石。它绕过了锁的阻塞和上下文切换开销在高竞争场景下有显著的性能优势。但它的代价也很明确代码从直观的加锁-操作-解锁变成了循环-CAS-重试的模式可读性和可维护性都下降不少。ABA 问题虽然在实际中不常爆发但理解它的本质有助于写出更安全的多线程代码。是否使用无锁方案答案是如果竞争不激烈锁就够用了如果性能瓶颈确实在锁上再用 CAS 也不迟。