乐观锁的简单实现

基于线程和共享内存的并发模型向来都是难于编写，难于调试的。但是在 Web 应用里它又是如此常见，因此仍旧有必要去做深入了解。更现代的并发模型（Actor，Channel，函数式，STM……）要学，线程和锁的并发模型也要学，这才称得上是健全！

这里记录一下对乐观锁的学习以及对使用乐观锁的AtomicInteger简单实现。我自认为我的实现会比网络上流传的更通俗易懂些（使用递归进行自旋而非无限循环）。但考虑到我们无法在代码层面直接实现原子的 CAS，这里必须得加锁。所以这里的代码其实并无任何实用意义，仅能用作学习了。

乐观和悲观

Happy，Lucky，Smile，Yeah！

就看待 data race 的态度（同样也是方式）而言，锁可以分为悲观锁和乐观锁。其中，悲观锁假设自己在操作数据时一定有其他线程试图对数据进行修改，所以必须要能够独占数据；而乐观锁假设操作时数据不会被修改，仅在最终修改数据前检查数据是否被改变。

悲观锁在 Java 中即为常见，如 synchronized 关键字就是给方法或代码块加上这种悲观锁。当一个线程进入 synchronized 的代码块，它就将获得对应（对象）的锁，从而便能够独占数据，保证当前操作是同步、原子的。而乐观锁的典型实现是 concurrent 包下的各种 Atomic 类，其使用乐观锁保证对其的操作为原子操作，从而保证对其使用是线程安全的。其最常使用在计数等操作中。

CAS

乐观锁的实现依赖所谓的 CAS（Compare And Set）操作，即在操作数据前，先将数据的原始值保存，再对数据进行拷贝和操作，获取结果值，然后检查这过程中数据是否改变，如果未改变则设置数据为新值，否则认为操作失败，进行自旋或其他操作（自旋其实就是递归执行自己，这时的基线条件就是操作成功，但使用循环应该会性能更高）。其中该检查和设置的过程即为 CAS，其必须是原子的。它的代码描述比文字描述或许更通俗易懂——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
volatile int counter = 0; // 不知道究竟有无必要保证可见性，但是加了其实也没啥损失
void increment() {
    int oldCounter = counter; // 获取数据
    int newCounter = oldCounter + 1; // 操作
    boolean success = compareAndSet(oldCounter, newCounter);
    if (success) {
        return;
    }
    increment(); // 自旋
}
// 注意加了锁！在 Java 中，该操作利用了现代处理器上相应指令，因而是原子操作，性能远好于锁
synchronized boolean compareAndSet(int oldValue, int newValue) {
    if (oldValue == counter) { // compare
        counter = newValue; // set
        return true;
    }
    return false;
}

上面的代码实际上已经可以跑了 w，这里的“操作”也可以看出一种模式，我们来进行一些抽象——

1
2
3
4
5
6
7
int operateAndGet(IntUnaryOperator operation) {
    int oldCounter = counter;
    int newCounter = operation.applyAsInt(oldCounter);
    if (compareAndSet(oldCounter, newCounter))
        return newCounter; // 如果是 getAndOperate，则返回 oldCounter
    return operateAndGet(operation); // 自旋
}

ABOAOBA

上面的 CAS 操作已能满足大多数需求，但仍旧存在一个问题——如果当前线程在操作数据时，数据从 A 变成 B 再变成 A，当前线程在 CAS 操作时是感受不到这种变化的，它会认为数据没有被改变，因此会应用自己的操作。这称为 ABA 问题，它在某些场景下可能造成问题。

ABA 问题的解决方案是使用一个单独的数据（称为 Version）来描述数据的状态，对数据的任何操作都将改变 Version，从而利用 Version 而非数据本身来检查数据是否改变。下面的代码是一个AtomicInteger的实现，其使用版本号来进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class MyAtomicInteger {
    private volatile int counter = 0;
    private volatile long version = 0;
    public int get() {
        return counter;
    }
    public int operateAndGet(IntUnaryOperator operation) {
        long oldVersion = version;
        int oldCounter = counter;
        int newCounter = operation.applyAsInt(oldCounter);
        if (compareAndSet(oldVersion, newCounter))
            return newCounter;
        return operateAndGet(operation);
    }
    private synchronized boolean compareAndSet(long oldVersion, int newValue) {
        if (oldVersion == version) {
            counter = newValue; // 设置数据
            version = oldVersion + 1; // 设置 Version
            return true;
        }
        return false;
    }

    // 进行简单的测试，使用并行流模拟并发情况
    public static void main(String[] args) {
        MyAtomicInteger counter = new MyAtomicInteger();
        IntStream.range(0, 10000).parallel().forEach(__ -> counter.operateAndGet(i -> i + 1));
        System.out.println(counter.get());
    }
}

乐观锁在数据库中也比较常用，Mybatis-Plus 提供了对乐观锁的插件支持，其原理是使用实体的其中一个字段充当 Version，在 Update 时将版本号也作为查询条件，这时若影响行数为 0，便说明版本号不对应，操作失败了。

顺便，对上面的 AtomicInteger 的实现，concurrent 包下的 AtomicInteger 的实现和使用 synchronized 对操作进行包装的 int 进行比较，检查其执行一亿次自增所耗时间，得到了如下的结果——

1
2
3
MyAtomicInteger: 4996
AtomicInteger:   1675
synchronized:    4841

funny，这说明 compareAndSet 操作是这里的性能瓶颈，毕竟加了锁。