Skip to main content

如何解决CAS的ABA问题？

作者：程序员马丁

在线博客：https://open8gu.com

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

回答话术​

当我们提到 CAS 的时候，就必然会一并提到 CAS 的 ABA 问题。

根据前文，我们知道在 CAS 中判断某个变量是否可修改的依据，就是这个变量的当前值是否与预期值相等。而根据这个逻辑，假如有线程 1 要将一个变量从 A 修改为 B，而在此之前，有另一个线程 2 先将其 A 先改成了 C 最后又改回了 A，此时对于线程 1 来说，变量依然还是预期值 A，因此可以顺利完成 CAS，这就是 ABA 问题。

在诸如转账这类实际业务场景中，如果我们单纯的对金额进行 CAS，那么由于失败重试等机制的存在，就可能因为 ABA 问题造成各种超支或者漏收问题，要避免这类问题，就需要通过额外的措施进行保证。

常见的两种处理方式，第一种是直接通过分布式锁等方式进行并发控制，避免操作同步进行。而第二种则是引入单调递增的版本号，先 CAS 递增版本号成功后再 CAS 修改目标值，通过这种双重 CAS 来避免 ABA 问题。我们熟悉的“乐观锁”其实就是基于这种双重 CAS 实现的一种解决方案，而在 JDK 中也基于这种机制提供了 AtomicReference 和 AtomicStampedReference 这些同步工具。

问题详解​

1. ABA 会造成什么后果？​

1.1. 举个例子​

在我们之前提到的简单变量交换的场景中，CAS 中“比较”这个动作是不在意目标变量中间状态的变化，但是对应大多数业务场景来说却不是一样。

以经典的转账问题为例：

  1. 现在我们账户里面有 100 块钱，我们进行了一次提现，想要将这 100 全部取出，服务器端分配了线程 A 来完成这个 cas(100, 0) 的操作，不过因为一些问题，线程 A 突然卡住了；
  2. 由于线程 A 卡住了，页面迟迟没有响应，因此我们直接又开了一个页面，再次发起了一次提现，服务器端直接分配了线程 B 来完成了这个操作 cas(100, 0)，现在账户里面的钱已经全部取出；
  3. 就在这时，一个客户给我们进行了一次转账，恰好转了 100 块，现在我们账户余额又是 100 了；
  4. 随后，线程 A 终于恢复了运行，它继续执行 cas(100, 0) 的操作，由于账户余额现在恰好是 100，此时 A 线程认为可以完成扣款操作，因此又把余额扣成了 0；
  5. 客户通知我们已经转账了，然后我们一登录发现账户余额是 0，这下就出问题了。

1.2. 问题分析​

在这个场景最核心的问题在于，线程 A 与线程 B 执行的两次转账操作中，我们仅比较了当前余额是否等于 100，但是实际第一次扣款时的 100 块余额，与客户转账后的 100 块余额在业务上的含义是不同的，此时我们仅比较金额是否与预期值一致实际上是不合理的。

换而言之，当进行 CAS 时，我们真正要比较的条件不是“当前余额 100”，是“当前余额 100 且尚未发生其他扣款或转账操作”。如果已经发生了扣款或者转账，那么即使当前余额仍然是 100，但是此次扣减余额的操作依然应该是失败的，因为余额的状态已经与预期发生了改变。

2. 如何解决 ABA 问题​

2.1. 问题出现的条件​

分析上述的示例，我们可以意识到，出现 ABA 问题需要两个前提条件：

  • 变量的值可以回退：值必须可以是可以回退的，否则如果它是一个单调递增或递减的值，那么其实也就不存在 ABA 问题了。比如，我们操作的不是一个可以动态增减的余额，是一个固定金额且只能往下减的现金抵用券，那么就不会有这 ABA 问题。
  • 变量的修改操作是并行的：如果变量的修改操作串行，那么自然也就不存在并发的修改，也不存在 ABA 问题了。比如，我们在扣减余额时直接通过分布式锁和幂等表保证操作唯一且顺序进行，其他修改操作就必须要等待此操作完成，那么自然也就没有后续的问题。

总而言之，我们只需要破除任意一个前置条件，ABA 问题自然就迎刃而解。其中加锁的方案不必多说，我们重点关注第一点，也就是想办法让值无法回退。

2.2. 双重 CAS​

要修改的变量值能不能回退，这个问题由业务场景决定，我们难以干涉，那么最简单的方案就是另外再加一个不能回退的变量值 —— 也就是版本号。

我们保证每次进行 CAS 时，原子性完成这么一个步骤：即对目标值进行 CAS 之前，先对版本号进行 CAS 递增，如果版本号 CAS 成功再对目标值进行 CAS。这种解决方案被称为双重 CAS。

image.png

我们熟悉的“乐观锁”实际就是一种变相的双重 CAS：

Integer id = 10086;
while(true) {
    // 每次都查询最新的版本号
    Example example = exampleDAO.getById(id);
    example.setName("foo");
    // 当成功更新时返回结果，否则进行自旋
    if (tableDAO.updateById(table) > 0) {
        return "success";
    }
}

// updateById 方法对应的更新 SQL 如下：
// 
// UPDATE 
//   example t 
// SET 
//   t.name = ${name},
//   t.version = t.version + 1
// WHERE
//   t.id = ${id} 
//   AND t.version = ${version}

以上述代码为例，在循环中的每一次操作中，实际上都要完成两个步骤：

  • 比较版本号，如果版本号不等于预期值就失败，否则就让版本号递增；
  • 如果版本号 CAS 成功，那么就更新对应表数据；

我们可以注意到，在第二步实际上是没有“比较”这个动作的，这是因为数据库在底层直接给我们加了行锁避免的并发写，这也是我们称呼其为“变相的 CAS”的原因。如果没有行锁，那么我们就需要通过 CAS 来控制对数据行的并发更新，如此一来那就是一个标准的双重 CAS 了。

3. 双重 CAS 在 JUC 中的应用​

3.1. AtomicStampedReference​

在 JUC 中，也基于双重 CAS 机制提供了一些同步工具类，比如 AtomicStampedReference 和 StampedLock。

这里我们写一个简单的 Demo，你可以感受一下它与 AtomicReference 的差异：

// 单 CAS
AtomicReference<Integer> ref1 = new AtomicReference<>(0);
ref1.compareAndSet(0, 1); // CAS 更新目标值，当前值与预期值一致时更新目标值

// 双重 CAS
AtomicStampedReference<Integer> ref2 = new AtomicStampedReference<>(0, 0);
int stamp = ref2.getStamp();
ref2.compareAndSet(
    0, 1, // CAS 更新目标值，当前值与预期值一致时更新目标值
    stamp, stamp + 1 // CAS 更新版本号，当前版本号与预期版本号一致时递增版本号
);

可以看到，AtomicStampedReference 在 AtomicReference 的基础上额外增加了一个变量 stamp，它实际上就是一个版本号，我们也可以按直译称呼其为邮戳。当进行 CAS 时，我们除了要比较并修改目标变量外，还需要额外的比较并修改 stamp，只有 stamp 值 CAS 成功以后，才能真正的去 CAS 预期值。

3.2. 如何保证双重 CAS 的原子性？​

到这里，我们可能会有一个疑问，单 CAS 可以通过 Unsafe 来保证整个过程的原子性，但是双重 CAS 更新的是两个值，要怎么保证原子性呢？

这里我们把 AtomicStampedReference 的源码拿上来，去掉所有的无关的方法以后是这样的：

public class AtomicStampedReference<V> {

    private static class Pair<T> {
        final T reference;
        final int stamp;
    }

    private volatile Pair<V> pair;

    public boolean compareAndSet(
        V expectedReference, V newReference,
        int expectedStamp, int newStamp) {
        
        Pair<V> current = pair;
        return
            // 先比较目标值是否相等
            expectedReference == current.reference &&
            // 再比较邮戳是否相等
            expectedStamp == current.stamp &&
            // 需要更新，则直接替换内部持有的 Pair 对象
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

    private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return PAIR.compareAndSet(this, cmp, val);
    }
}

我们可以看到，源码中实际上将目标值和邮戳封装到了一个 Pair 对象里面，当进行 CAS 的时候，就分为两步：

  1. 先比较预期值是否一致，再比较邮戳是否一致，任意不一致则 CAS 失败；
  2. 如果都一致，则使用新的预期值与邮戳创建一个新的 Pair 对象，并进行 CAS 替换掉旧的 Pair 对象；

如果有同学重写过 Object 的 equals 方法，对上面这段比较的代码应该不会陌生，由于 Pair 本身只具备目标值 reference 和邮戳 stamp 两个属性，因此这种比较方式实际上相当于直接基于 Pair 对象进行比较，这里我们把它换个写法，你可以感受一下：

public boolean compareAndSet(
    V expectedReference, V newReference,
    int expectedStamp, int newStamp) {
    Pair<V> current = pair;
    
    if (expectedReference != current.reference) {
        return false;
    }
    if (expectedStamp != current.stamp) {
        return false;
    }
    if (newReference == current.reference 
        && newStamp == current.stamp) {
        return true;
    }
    return casPair(current, Pair.of(newReference, newStamp)));
}

总而言之，通过这种巧妙的比较方式，最终只需要保证 CAS 操作一个变量即可。

Table of Contents