竞争、缓存与事务

资源竞争

比方说打印机同一时刻只能被一个应用程序调用,这便是进程层面的资源竞争;我们说「进程是资源分配的最小单位;线程是 CPU 调度的最小单位。」在同一进程的多线程环境下,便有可能发生线程层面的资源竞争;同理,在多机环境下也有主机间竞争资源的情况。

拿使用打印机这个场景来说,倘若同时有两个进程操作打印机,一定会导致打印出来的东西一团糟。= =!对这类情况来说,要实现资源的安全使用,必须保证同一时刻只有一个角色使用资源。要达到这一点可以从角色和资源两方面来考虑:

  1. 将角色们(比如多线程)并发占用资源的行为转为串行操作:比方说有考试系统在面临大量考生涌入这个场景,为不同考生按批次设置数分钟进入考试界面的延迟。
  2. 对资源进行加锁,标识它已被占用,无法再被使用。

比方说具体到 Java 在 JDK 层面的锁实现 ReentrantLock.java

1
2
3
4
5
6
7
8
9
10
final boolean tryLock() {
int c = getState();
if (c == 0) {
if (compareAndSetState(0, 1)) {
setExclusiveOwnerThread(current);
return true;
}
}
return false;
}

可以看出,当一个线程尝试获取锁时,会先判断当前资源的状态是否为 0(未使用),是的话将之设为 1(已使用),这时别的线程就没法使用这个资源啦;否则说明该资源已被别的资源占用,这个线程就暂时没法使用该资源啰。

对于集群来说,利用 Redis 为多机环境实现锁,原理和上面一致,一个简单的伪代码实现如下:

1
2
3
4
5
6
7
8
9
public boolean tryLock(...){
if(SETNX key value){
// ...
return true;
}else{
// ...
return false;
}
}

SETNX 的意思是「SET if not exists」,命令在指定的 key 不存在时,为 key 设置一个 value 值,若成功返回 1;若失败返回 0。

Redis 提供的 SETNXReentrantLock.java 中的 compareAndSetState() 效果一样:先判断能不能设置值,能的话就设置值并返回成功,否则返回失败。对应到业务逻辑就是 先判断锁是否已被占用,若没占用就加锁并返回成功,否则返回失败。 同时,这两个命令都是内部实现的原子操作——判断、设置是两个动作,为了避免这两个动作中间被别的角色插足产生问题,就必须保证命令是一个原子操作。

多机环境对资源的竞争可以从两方面入手做限制。一是具体到真正影响资源的层面。比方说多台机器竞争的是同一个数据库里的数据,可以在数据库层面使用锁来防止资源竞争导致的问题;二是在多台机器的上层再做一层抽象,引入一个统一的资源调度——比方说在多机之上利用 Redis 设置分布式锁来管理多机环境的资源竞争。

在更上层做抽象可以减轻下层的压力。比方说有两个删除同一资源的操作同时走两台服务器去执行——显然这两个操作其实只用执行一个,我们越早确认这一点就能越早放弃其中一个以避免它再去服务器执行一遍,浪费资源。

锁的优化及好多概念

「使用资源」这个说法太宽泛了,比方说 A 在读一个资源时 B 也来读其实不会有啥安全问题,若因 A 在读一个资源就将该资源上锁,其它的 B、C……就都得等着 A 释放资源,反倒降低了效率。

因此有必要对「使用资源」的情况一一进行分析,并针对不同的情况使用不同的策略以提高效率。

比方说从「读资源」「修改(写)资源」分析,可以有如下概念:

  • 乐观锁/悲观锁
    • 我们乐观地假定每次访问资源都只是「读」操作,因此允许同一时刻有多个角色使用(读)资源
    • 我们悲观地假定每次访问资源都是「写」操作,因此同一时刻只允许一个角色使用(写)资源
  • 独享锁/共享锁
    • 同一时刻只能有一个角色使用资源
    • 同一时刻允许多个角色使用资源
  • 互斥锁/读写锁
    • 独享锁/共享锁是一种广义的说法,互斥锁/读写锁是其具体实现。

上面聊这些概念时都假定了同一时刻会有多个角色访问资源的情形,要是我们再乐观点,考虑「一个资源会有被并发访问的可能但多数时间都不会到这一步」等特殊情况,就可以再为此做一些优化,减少对锁的维护所消耗的资源。

比方说 Java 里有四种锁状态:

  • 无锁状态:还没有线程占用资源。
  • 偏向锁状态:只有一个线程占用资源。
  • 轻量级锁状态:假定锁占用时间很短,不会产生资源竞争。
  • 重量级锁状态:锁占用资源的时间较长,产生资源竞争,线程被阻塞。

在轻量级锁与重量级锁之间还会有一个「自旋」的操作。它假定「产生了资源竞争,但锁占用时间不长」,那么线程便尝试通过自旋来获取资源,以优化线程切换造成的资源浪费。

我们又怎么判断「应该自旋多久呢?」虽然通过自旋可以减少线程阻塞导致线程切换使用的资源,但要是锁持有时间确实比较长,那么自旋操作反倒因为线程的空等待浪费了资源。针对这一点,JVM 假定不同线程持有同一个对象锁的时间基本相当,会根据上一次自旋的时间与结果来调整下一次自旋的时间。

  • 自旋锁

另一方面,我们应该使用什么策略来分配资源呢?比方说我们可以使用「先来后到」的资源分配方式,但对于不同的场景,这种策略不一定总是高效的。从这个角度考虑,可以引出:

  • 公平锁/非公平锁

一方面将资源有所侧重地分配可能在业务流程上更高效;另一方面,比如一个线程来竞争资源时,如果直接将资源分配给它,就能减少从另外一堆线程中将某个线程从阻塞唤醒的线程切换动作,节约系统资源。

引入缓存

在计算机里,我们「使用资源」时往往操作的是这个资源的缓存。例如操作系统层面有主存和缓存;JVM 层面有主存和工作内存;应用层面会为数据库引入 Redis 等做缓存,数据库自己可能也带有缓存机制。

例如 JVM 在 JMM(Java 内存模型)定义所有的变量都存放在主存(物理内存),每个线程都有自己的工作内存(高速缓存)。倘若一个线程修改了自己缓存中的值,那么就可能涉及到两点:

  1. 缓存中的值与主存同步。
  2. 某线程的缓存里的值与其它线程的缓存中的值同步。

为此,JMM 规定了三点:

  • 线程解锁前,必须把共享变量的值刷新回主内存;
  • 线程加锁前,必须读取主内存的最新值到自己的工作内存;
  • 加锁解锁同一把锁。

类似的,在操作系统层面通过内存屏障来保证数据一致:

  • 缓存有更新,立马同步回主存;
  • 主存有更新,立马使缓存失效。

比方说应用层面可能有些对数据的一致性要求没那么高的场景,可以在缓存使用定期从主存更新数据的策略。若有要求呢?可查阅 2PC、3PC 等一致性协议及算法。


拿 JDK 层面来说,多线程对 int 类型的值做计算是不安全的,因为会有多个线程同时对各自缓存中的值做计算,再同步回主存的情况。由于它们各自独立计算再往主存同步,相互之间没有交流,导致部分线程的计算操作没有被继承,而是被覆盖丢失了。

为了避免这种问题,需要将每个线程的每次计算操作当作一个「原子操作」来进行,即每次线程切换时,能保证我这次计算已经作为一个原子操作执行完了(更新到主存)。

对于这类问题,操作系统是通过「总线锁定」来解决的。在操作系统层面,数据间通过总线来通信,一个 CPU 想要改变某个共享数据时,会通过总线通知其它 CPU 不可使用该数据。

而在 JDK 层面引入了原子操作类,通过 CAS(compare and swap)保证做计算操作的原子性。简单来说,每个线程尝试对缓存中的数据进行操作前,会以自旋的方式不断拿一个预期值(当然是此时主存里的值)去和缓存值做比较,如果两者不一致,就说明主存里的值已经被别的线程改动过了,当前线程应该等待缓存被更新为最新的值再去做计算。若一致,则说明现在缓存里的值可能是最新的值,当前线程可以对数据进行操作。这个比较并计算的操作(CAS)是利用指令层面的特性实现的,能保证原子性。不过 CAS 也有一些细节上的问题:

  • ABA 问题:假如一个值从 A 变为 B 又改回 A,对于当前线程来说看起来没有变化,实际上改变过两次。
    • 这个问题对于不需要记录变化次数的场景来说其实没有影响,如需要考虑,可以用版本号机制——每次变化都更新版本号。当值相同且版本号一致时,我们才判断这个值没有变化过。
  • 一直自旋,时间长开销大。
    • 设置超时时间、超时次数。
  • 只能保证一个共享变量的原子操作。
    • CAS 利用指令层面的特性,若涉及多个变量,就无法保证多个变量之间不会被别的操作插入,因此无法保证多个共享变量的原子操作。若涉及多个变量可以通过加锁解决。
    • 但也有特殊的 CAS 算法尝试对两个共享变量使用 CAS 保证原子性。

数据库里的事务

事务也需要保证原子性——一个事务内的操作要么全部执行成功要么全部失败。在并发编程的概念中,原子性包含「原子操作」与「操作互不可见」两点,而事务中的原子性只有「事务中的操作作为原子操作」一点,「操作互不可见」单独指「隔离性」——一个事务所做的修改在最终提交以前,对其它事务是不可见的。

和上面的场景类似,事务也会有并发的情况呀——由于事务的粒度比较大,拿来分析资源竞争产生的问题就比较清晰。

事务可能会产生以下四种并发一致性问题:

  • 读脏数据:事务 A 读到了事务 B 尚未提交的数据后,事务 B 又回滚了。因此事务 A 读到了 B 造成的脏数据。
  • 丢失修改:事务 A 和 事务 B 同时对数据进行修改,A 修改后 B 接着修改,A 提交后 B 接着提交。B 提交后导致 A 的修改没生效,于是 A 丢失了修改。
  • 不可重复读:事务 A 两次读取某些数据期间事务 B 修改了其中的数据,导致事务 A 这两次读取到的数据不一致。(数据不一致)
  • 幻读:事务 A 两次读取同一区域的数据期间事务 B 新增或删除了这区间的数据,导致两次读取到同一区域的数据数目不一致。(数目不一致)

事务和其它资源竞争的场景一样,倘若只有读的操作,就不会出现冲突了……针对并发不一致问题,数据库会有四种不同程度的隔离级别:

  • 未提交读(READ UNCOMMITTED):一个事务能读到其它事务尚未提交的修改。最低级别,啥都不能保证。
  • 提交读(READ COMMITTED):一个事务只能读取到其它事务已提交的修改。可避免脏读。
  • 可重复读(REPEATABLE READ):保证在同一个事务中多次读取同一数据的结果是一样的。可避免脏读、不可重复读。
  • 串行化(SERIALIZABLE):强制事务串行执行,这样多个事务互不干扰,不会出现并发一致性问题。可避免脏读、不可重复读、幻读。

可见「串行化」是以「并发转串行」的思路来解决并发竞争资源的问题的——实际上是通过加锁机制实现。四种隔离级别中也只有「串行化」是从根本上解决「事务竞争资源」这一问题。但「串行化」对性能损耗较大——针对一些要求低点或者我们能确保不会出问题的的场景,就可以选择其它的隔离级别。

具体到某种事务隔离级别是怎样通过锁来实现的可以参见 MySQL 的 MVCC 机制。

与其它多机环境一样,事务也会有分布式事务的场景。比方说跨行转账业务——银行 A 扣钱,银行 B 存钱。这也必须作为一个原子操作进行。关于分布式事务如何保证 ACID 可见 XA、Saga 等。