如何理解ABA问题

CAS and ABA Issue

Posted by S.L on March 8, 2020

我们都知道CSA(CompareAndSwap),它比较当前工作内存中的值和主内存中的值,如果相同则执行规定操作, 否则继续比较直到主内存和工作内存中的值一致为止.

但你听过ABA问题吗?这个在CAS场景下可能会发生的问题,你如何理解它对业务的影响呢?

ABA问题

ABA问题是指在CAS操作时,其他线程将变量值A改为了B,但是又被改回了A,等到本线程使用期望值A与当前变量进行比较时,发现变量A没有变,于是CAS就将A值进行了交换操作,但是实际上该值已经被其他线程改变过。

那么是CAS本身有问题吗?当然不是。并不是CAS的问题导致了ABA而是ABA问题在CAS下发生时不是很容易被联想到!CAS 只是简单的比较并交换,只要是符合 compare 条件(没有被其他线程修改了我预期的值导致和我预期的不一样)就会被swap (设置为我想要的值),本身是没有问题的。

所以我们应该把问题描述清楚,如果在用CAS的时候发生了ABA问题,我们应该怎么解决?

Java的CAS实现

CAS是一条CPU的原子指令(cmpxchg指令),不会造成所谓的数据不一致问题,Unsafe提供的CAS方法(如compareAndSwapXXX)底层实现即为CPU指令cmpxchg。

这里我们可以看一下Java的原子类AtomicLong.getAndIncrement()的实现,来理解一下CAS这一乐观锁(JDK 1.8)。

public class AtomicLong extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 1927816293512124184L;
   
    // setup to use Unsafe.compareAndSwapLong for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicLong.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile long value;

其中,valueOffset表示该变量在内存偏移地址,alueOffset的值在AtomicInteger初始化时, 在静态代码块中通过Unsafe的objectFieldOffset方法获取。在AtomicInteger中提供的线程安全方法中, 通过字段valueOffset的值可以定位到AtomicInteger对象中value的内存地址,从而可以根据CAS实现对value字段的原子操作。

看一下其中的两个典型的方法:

public final boolean compareAndSet(long expect, long update) {
    return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
}
    
public final long getAndIncrement() {
   return unsafe.getAndAddLong(this, valueOffset, 1L);
}

下面的图来自美团技术团队,注意里面对valueOffset的标记含义,它是用来从baseAddress来检索具体的value的地址的偏移量。

接着看一下 Unsafe.getAndAddLong() 的实现:

public final long getAndAddLong(Object var1, long var2, long var4) {
   long var6;
   do {
       var6 = this.getLongVolatile(var1, var2); // 不断读取volatile的值
   } while(!this.compareAndSwapLong(var1, var2, var6, var6 + var4)); // 不断循环直到满足条件
   return var6;
}

可以看到这个是一个非阻塞算法,非阻塞算法通常叫作乐观算法,因为它们继续操作的假设是不会有干扰。如果发现干扰,就会回退并重试。

这里需要注意使用了 volatile 原语保证了可见性。volatile变量的读操作,会强制使CPU缓存失效,强制从内存读取变量。 因为并没有使用锁,只能通过其他机制保证内存的可见性问题。

没有使用锁会有什么问题呢?

这里就是产生ABA问题的关键,因为获取和比较是两个独立的操作,在获取数据之后和比较之前由于CPU对线程的调度问题,可能会发生很多事情,也就是这里的ABA。

比如我们常见的两个线程同时执行一个业务逻辑,如果不通过锁加以控制,同时判断某个条件是合理的,然后都去执行某一个操作, 可能会对业务有一定的影响,如货物超发或者计数值为负数等。而ABA问题只不过是其中的一个特例,一个线程执行完之后恰好结果和 没有变更之前的值是一样的,但是A完成了一次业务逻辑,B在某种情况下需要对这件事情加以感知来控制自身的业务是否仍照旧就执行。

如何解决CAS时的ABA

既然不能加独占锁,那么只能通过乐观锁的机制来做了,即增加版本号:每次变量更新的时候把变量的版本号加1,那么A-B-A就会变成A(v1)-B(v2)-A(v3) ,只要变量被某一线程修改过,该变量对应的版本号就会发生递增变化,从而解决了ABA问题。

独占锁的替代就是乐观锁,即通过版本号控制,形成逻辑上的独占效果。

在JDK的 java.util.concurrent.atomic 包中提供了 AtomicStampedReference 来解决ABA问题,该类的compareAndSet是该类的核心方法,实现如下:

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

我们可以发现,该类检查了当前引用与当前标志是否与预期相同,如果全部相等,才会以原子方式将该引用和该标志的值设为新的更新值,这样CAS操作中的比较就不依赖于变量的值了。

举个ABA影响业务的例子

这个还是比较难的,如果你没理解可能还是会局限于数字变化这种模糊的例子,如果真能结合业务或者实际的场景才算真的理解。

假设,现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:

head.compareAndSet(A,B);

在T1执行上面这条指令之前,线程T2介入,将A、B出栈,再push D、C、A,而对象B此时处于游离状态

此时轮到线程T1执行CAS操作,检测发现栈顶仍为A,所以CAS成功,栈顶变为B,但实际上B.next为null,所以此时链表处于断裂的状态,即B是游离的,C和D是一起的,但不是栈顶元素。 栈顶元素是B,但是B已经是栈里的唯一元素了,所以就造成了数据的丢失!

总结

ABA的影响本质上是物理上的同一个A(引用)在不同的时间点上可能是两个业务状态(注意引用没变,内部的状态可能变了), 前面的业务状态生效并不能代表新的业务状态的生效,如本例中,T1完成出栈没有问题,但是在T2变更了A的业务状态之后再执行T1的CAS,那么就不是之前的业务结果了。

在ABA中丢失的是:时间和该时间的业务含义。

References

  • https://www.cnblogs.com/yanlong300/p/9073338.html
  • https://tech.meituan.com/2019/02/14/talk-about-java-magic-class-unsafe.html

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.