数据库并发控制原理综述

た入场券 2021-12-23 21:29 441阅读 0赞

并发控制是数据库中的一大重点，本文就数据库中的并发控制做简要分析和介绍。

在讨论数据库并发之前我们先引入**事务**的概念：

数据库事务通常包含了**一个序列的对数据库的读/写操作（一个单元的一系列SQL语句的集合）**。

我们引入事务无非是为了实现以下两个目的：

1.  为数据库操作序列提供一个**从失败中恢复到正常状态**的方法，同时提供数据库**即使在异常状态下仍能保持一致性**的方法。（即系**统的错误恢复**）
2.  当多个应用程序并发访问数据库时，可以在这些应用程序之间提供一个隔离方法，以保证彼此之间的操作不会互相干扰。（即**并发数据库访问**）

当事务被提交给\*\*数据库管理系统（`DataBaseManagerService，DBMS`）\*\*之后，`DBMS`需要确保该事务中的所有操作都成功完成且其结果被永久保存在数据库中，如果事务中有的操作没有成功完成，则事务中的所有操作都需要回滚，回到事务执行前的状态。同时，该事务对数据库或者其他事务的执行不会产生影响，即所有的事务都好像在独立的运行。

了解了事务的概念后，我们来引入并发，在最原始的单处理机系统中，事务只能一个一个地串行执行，即每个时刻之后一个事务执行，上一个事务执行完成之后下一个事务才有机会执行，如下图（a）所示，这样做的缺点很明显，就是计算机资源的利用率很低(比如A事务需要使用CPU资源，B事务需要使用IO资源，二者所需的资源不冲突，但是在串行方式下同一时刻只能利用到CPU或只能利用到IO，资源使用率很低)。为了提高资源的利用率，出现了一种叫做**交叉并发**的方式，即让不同事务分时间段进行交叉执行，这样可以减少处理机的空闲时间，如下图（b）所示。![image-20190625223920610][]

上面描述的是单处理机的情况，可以发现这种情况下没有实现真正的并行运行，导致计算机资源利用率较低，这时就引入了多处理机下的并发执行，即当计算机有多个处理机时，就可以同时在不同的处理机上运行不同的事务，这样做到真正意义上的并发运行，这样做的优点是计算机的资源利用率得到了有效提高，缺点就是由于并发会产生很多串行执行时不会产生的冲突和错误，会引起数据库的不一致性，为了解决这一缺点，我们就需要对数据库中的并发进行控制，这也是我们本文的重点，即**数据库系统的并发控制**。

并发操作引起的数据不一致性包括三个方面：

1.  丢失修改(`lost update`)：卖票问题，A代表票的余量，事务X集合事务Y将A读入，假设此时A=10，事务X将票卖出一张即A=A-1=9，将A写入，数据库中A此时为9，事务Y也将票卖出一张即A=A-1=9，将A写入数据库即数据库中此时A=9，可是明明卖出去了两张票，相当于事务X对A的修改丢失了。
2.  不可重复读(`non-repeatable read`)：不可重复读是指事务T1读取数据后，事务T2对数据库执行更新操作，致使事务T1无法再现前一次读取的结果。具体来说分为以下三类情况
    
     *  T1读取数据后T2对数据进行修改，导致T1之后读取的数值与之前读取的不一样
     *  T1读取数据之后T2对数据进行删除，导致T1之后再按相同条件读取的数据少了一部分
     *  T1读取数据之后T2对数据进行插入，导致T1之后再按相同条件读取的数据多了一部分
    
    后两种情况有时也称为**幻影/幻读**现象。
3.  读脏数据：事务T1将数据修改后写入数据库，T2此时将数据读取，T2读取后T1又由于某种原因撤销了之前的对数据的修改，导致T2读取的数据与原数据库中的数据不一致，即**脏数据**。

产生上述三类错误的原因在于并发操作破坏了事务的隔离性，而数据库系统的并发控制就是为了解决这一问题从而保证不同事务之间可以独立执行、各自不受影响，目前并发控制的主要技术有：封锁、时间戳、乐观控制法、多版本并发控制等。

本文我们讲解目前大多数数据库都在采用的并发控制技术，即\*\*封锁（Locking）\*\*技术。

### 封锁 ###

封锁是实现并发控制的一个非常重要的技术，所谓 **封锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁**，加锁之后事务T就对该数据对象有了一定的控制，在事务T释放该锁之前，其他事务不能对该数据对象进行更新。目前来说数据库系统主要提供两种锁：

*  **排他锁（写锁），exclusive Locks，简称X锁**：若事务T对数据对象A加写锁，则只允许T**读取**和**修改**A，**其他事务都不能再对A加任何类型的锁，直到T释放A上的锁为止**。
 *  **共享锁（读锁），Share Locks，简称S锁**：若事务T对数据对象A加读锁，则只允许T**可以读取**但**不能修改**A，其他事务只能再对A加读锁，而不能加写锁，直到T释放A上的读锁为止。

#### 封锁协议 ####

在运用X锁和S锁这两种基本封锁对数据对象加锁时，还需要约定一些规则，例如何时申请X锁或S锁、持锁时间、何时释放等，这些规则称为**封锁协议**。

针对不同的事务隔离级别，有不同的封锁协议，这里介绍四级封锁协议：

*  **一级封锁协议**：事务T在修改数据R之前必须先对其加**写锁**，直到事务结束才释放。一级封锁协议**防止了丢失修改**，但不能保证可重复读和不读脏数据。
 *  **二级封锁协议**：在一级封锁协议的基础上增加事务T在**读数据R前必须加读锁**，**读完就可以释放**。二级封锁协议进一步**防止读脏数据**，但不能保证可重复读。
 *  **三级封锁协议**：一级封锁协议的基础上增加事务T在**读数据R前必须加读锁，直到事务结束才释放**。三阶封锁协议除了防止丢失修改和读脏数据外，进一步**防止了不可重复读**。
 *  **四级封锁协议**：四级封锁协议是对三级封锁协议的增强，其实现机制也最为简单，直接对事务中所读取或者更改的数据所在的**表加表锁**，也就是说，其他事务不能 **读写** 该表中的任何数据。

### 活锁和死锁 ###

\*\*活锁：\*\*事务T1锁住数据D，事务T2等待数据D，事务T1释放数据D的锁时事务T3抢占数据D的锁，事务T2继续等待，事务T3释放数据D的锁时事务T4抢占数据D的锁，事务T2继续等待……这样导致事务T2老是执行不了，这就是活锁的场景。

避免活锁的方案就是先来先服务，即谁先申请锁，谁先得到锁，即如果事务T2先申请了数据D的锁，这是当数据D的锁释放后一定将数据D的锁给事务T2，而不会给其他事务，这样就保证了不会出现活锁。

\*\*死锁：\*\*事务T1持有数据D1的锁，还需要数据D2的锁才能继续执行，即在等待数据D2的锁，事务T2持有D2的锁，还需要数据D1的锁，即在等待数据D1的锁，这样事务T1和事务T2相互等待，陷入死锁。

目前在数据库中解决死锁主要有两类方法：

1.  采取预防措施来预防死锁
2.  允许死锁发生，定期采用一定手段检测死锁，若检测到发生了死锁，则将死锁解除

#### 死锁的预防 ####

##### 一次封锁法 #####

将事务执行过程中所使用的数据一次性全部加锁，这样就不会发生某个事务由于等待某个数据的锁而出现死锁的情况。缺点是可能会需要扩大锁的范围，降低并发度。

##### 顺序封锁法 #####

预先对数据对象排个序，所有事务都按照这个顺序来实施封锁。

缺点是维护资源的封锁顺序很困难。

#### 死锁的诊断与解除 ####

##### 超时法 #####

如果某个事务等待某个锁超过一定时间就认为它出现了死锁。

缺点是如果超时时间设置过短会导致本来没有发生死锁的事务被误判为发生了死锁，如果超时时间设置过大，不能及时发现死锁。

##### 等待图法 #####

![image-20190625233317014][]

如上图，如果T1等待T2，则画一条从T1指向T2的有向边，若T2等待T1，则画一条从T2指向T1的有向边，依次类推，这样就可以构成一个图，如果检测到图中有回路，则说明出现了死锁。

检测到死锁之后就需要解除死锁，现在一般采用的解除死锁的方法是选择一个处理死锁代价最小的事务进行取消，释放其占有的锁，以使其他事务可以正常执行。

### 并发控制的可串行性 ###

数据库管理系统对并发事物不同的调度可能会产生不同的结果，那么什么样的调度才是正确的呢？很明显，**串行调度一定是正确的**，而**执行结果与串行调度的执行结果一样**的调度也是正确的，我们将这样的调度称为**可串行化调度**。

#### 可串行化调度 ####

可串行化调度的定义：多个事务的并发执行是正确的，当且仅当其执行结果与按照个顺序串行地执行这些事物时的结果相同，将这种调度策略称为**可串行化调度**。

其实说白了，就是如果按照当前的调度方案执行完所有事务后，数据库中数据的状态和以任意顺序串行执行所有事务的结果相同，则当前的调度方案就是正确的调度，即可串行化调度（可以将当前调度等价为某个串行化的调度）。

#### 冲突可串行化调度 ####

我们首先明确什么是**冲突操作**，冲突操作是指**不同事务**对**同一数据**的**读写**操作和**写写**操作：  
$$

1.  R\_i(x)与W\_j(x) : 事务T\_i读x，事务T\_j写\\
2.  W\_i(x)与W\_j(x):事务T\_i写x，事务T\_j写x  
    $$

除了(1)式中的两组读写组合，其他任何操作都是**不冲突的操作**。

我们在进行事务调度的时候应该注意，不同事务的冲突操作和同一事务的两个操作时不能交换的，比如(1)式中， 与 R i ( x ) 与 W j ( x ) 与R\_i(x)与W\_j(x) 与Ri(x)与Wj(x)的顺序不可交换， 与 W i ( x ) 与 W j ( x ) 与W\_i(x)与W\_j(x) 与Wi(x)与Wj(x)的顺序不可交换。

现在我们来定义**冲突可串行化调度**：一个调度Sc，在保证**不改变冲突操作的次序**的前提下，通过**交换不同事务之间的不冲突操作**，最后得到了一个**可串行化的事务序列**，则称Sc为冲突可串行化调度。

我们来以一个实例进行说明：

对于调度`Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)`

`w2(A)`与`r1(B)w1(B)`是**不冲突操作**，交换二者得到：`Sc2=r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)`

`r2(A)`与`r1(B)w1(B)`是不冲突操作，交换二者得到：`Sc3=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)`

得到的`Sc3`刚好是以`事务T1`、`事务T2`的顺序**串行执行**的结果，所以`Sc1`是**冲突可串行化的调度**。

学会判断一个调度是否是冲突可串行化的调度后，我们就可以引入如下结论了：

冲突可串行化调度是可串行化调度的充分条件，也就是说，**如果一个调度是冲突可串行化调度，其一定是可串行化调度**(但是反过来说是不对的，即如果一个调度室可串行化调度，其不一定是冲突可串行化调度)。

以上结论可以作为**判断一个调度是否是可串行化调度的原则**。

[image-20190625223920610]: /images/20211223/f9c0ec05b3ee4ef4a868926b7a9c8d3f.png
[image-20190625233317014]: /images/20211223/0d39beef3f89467b8dd2ffae1579f27d.png