【数据库】并发控制

并发控制

在数据库系统，经常需要多个用户同时使用。同一时间并发的事务可达数百个，这就是并发引入的必要性。

常见的并发系统有三种：

串行事务执行（X），每个时刻只有一个事务运行，不能充分利用系统资源
交叉并发（V），并行事务并行操作轮流交叉运行，适应于单处理机系统，能够减少处理机的空闲时间，提高系统的效率。
同时并发，多个处理机同时运行多个事务，理想的并发方式，但是受限于硬件环境。

但是并发控制可能导致一些问题，所以主要有三个任务：

对并发操作的正确调度
保证事务隔离性
保证数据库的一致性

并发操作的后果

并发控制可能导致的数据不一致性有三类：

丢失修改
不可重复读
读脏数据

为了说明这三种情况，我们用 $R (x)$ 表示读数据 $x$ ， $W (x)$ 表示写数据 $x$ .

一、丢失修改

考虑下面的情况：

$T_1$	$T_2$
$R (A) = 16$
	$R (A) = 16$
$A = A - 1, W (A) = 15$
	$A = A - 1$ , $W (A) = 15$

那么 $T_1$ 对 $A$ 的修改丢失了。

二、不可重复读

不可重复读是在 $T_1$ 读取数据后， $T_2$ 更新，导致 $T_1$ 无法再现读取结果。

（1）RUR(Read, Update, Read)

$T_1$	$T_2$
$R (A) = 50, R (B) = 100, S = 150$
	$R (B) = 100, W (B) = 200$
$R (A) = 50, R (B) = 200, S = 250$

（2）RDR(Read, Delete, Read)

$T_1$	$T_2$
$R (A) = 50, R (B) = 100, S = 150$
	将B记录从数据库中删除
无法读取到B的记录

（3）RAR(Read, Add, Read)

$T_1$	$T_2$
A中有两条记录， $\sum A_i = 100$
	将记录50插入到集合A中
A中有三条记录， $\sum A_i = 150$

三、读脏数据

事务 $T_1$ 修改某一数据，并写回磁盘，然后 $T_2$ 读取之后， $T_1$ 因为某种原因被撤销，这个时候 $T_2$ 的数据可能不一致。

$T_1$	$T_2$
$R (C) = 100, W (C) = 200$
	$R (C) = 200$
ROLLBACK C，C恢复为100

封锁

一、封锁的概念

封锁是指事务在某个数据对象操作前先对系统请求进行加锁。加锁之后，事务就有了数据对象控制权。

基本封锁类型有两种：排它锁（Exclusive Locks, X锁）和共享锁（Share Locks, S锁）

排它锁又称写锁，如果 $T$ 对 $A$ 加X锁，那么其它事务不能加任何其他锁。这个时候，其它事务不能读取和修改。

共享锁又称读锁，如果 $T$ 对 $A$ 加S锁，那么其它事务只能对 $A$ 加 $S$ 锁。这个时候，其它事务可以读 $A$ ，但是在 $T$ 释放锁之前不能进行修改。

换言之，存在锁的相容矩阵：

二、封锁协议

申请锁、持有锁、释放锁的规则，叫做封锁协议。

一级封锁协议是事务中队数据修改之前必须对其加排它锁直到事务结束。

一级封锁协议可以有效防止丢失更新。

二级封锁协议是在一级协议的基础上，要求读取数据之前必须加共享锁，读完再释放。这样可以防止读脏数据。

二级封锁协议可以有效防止读脏数据。

三级封锁协议是在二级基础上，增加某事务施加的共享锁，保持到事务结束再释放。

三级封锁协议可以解决不可重复得问题。

活锁和死锁

一、活锁

考虑有四个事务T1,T2,T3,T4

T1封锁数据R，T2请求R，所以T2等待。T3也请求R，然后T1释放R的锁之后系统调度给T3，T4请求R，T3释放R的锁之后系统调度给T4，导致T2永远等待。这就是活锁。

避免活锁比较简单，只需要采取先来先服务的策略，在多个事务请求封锁同一个数据对象的时候按照请求封锁的先后次序对事务排序。

二、死锁

考虑两个事务T1、T2。T1封锁R1，T2封锁R2。T1此时请求封锁R2，而T2封锁R2，所以T1等待T2释放R2的锁。此时T2又申请R1，T1已经封锁R1，T2只能等待T1释放R1的锁。此时，T1、T2形成死锁。

如果希望预防死锁，一般有两个思路：

一次封锁法。要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。但是这样比较难确定封锁对象，也会导致并发度降低。
顺序封锁法。对数据对象规定封锁顺序，按照顺序进行封锁。但是这样难以确定事务要封锁哪些对象。

因此，死锁的预防比较难，多采用诊断解决的思路。

最简单的诊断方法就是使用超时法，如果事务等待时间超过规定时限，就说明发生死锁。这样实现简单，但是可能误判，并且如果时限过长，可能会让死锁无法及时发现。

等待图法是一个比较好的方式。设 $G=\langle V,E\rangle$ ， $V$ 是正运行的事务， $E$ 是事务等待情况，如果 $T_1$ 等待 $T_2$ ，就连接 $T_1T_2$ 。如果图中存在回路，说明系统出现死锁。

检测到死锁后，选择一个处理死锁代价最小的事务，将其撤销。释放事务持有的所有锁，让其他事务能运行下去。

可串行性

多个事务的并发执行想要保证正确性，需要结果和某一次序串行执行结果相同。

一、可串行化的判定

可串行性是并发事务正确调度的准则，只有并发调度是可串行化的才能认为是正确调度。

考虑下面的两个事务：

T1：读B，A=B+1，写回A
T2：读A，B=A+1，写回B

对于下面的这些策略：

这两种策略相当于串行执行，因此并行执行的结果应当和二者之一相同。而对于下面的例子：

不可串行化。

二、冲突可串行化

冲突可串行化给出了一个可串行化的充分条件：

一个调度Sc在保证冲突操作次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’。如果Sc’是串行的，称调度Sc为冲突可串行化的调度。

这里需要先引入冲突操作的概念。所谓冲突操作是指如下操作：

事务Ti读x，Tj写x
事务Ti写x，Tj写x

下面举一个例子。

证明：调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)可串行化。

r1(A)、w1(A)、w2(A)不可交换，r1(B)、w1(B)、w2(B)不可交换。

这样，可以交换为r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(N)

这是一个串行调度T1T2，所以Sc1是冲突可串行化调度。

需要注意的是，这个条件并不是必要的。下面举一个反例。

T1=W1(Y)W1(X), T2=W2(Y)W2(X), T3=W3(X)

调度W1(Y)W2(Y)W2(X)W1(X)W3(X)结果与T1T2T3相同，可串行化，但并非冲突可串行化。

两段锁

在封锁的时候，对数据对象加锁需要遵守约定，比如何时申请加锁、锁持续时间和何时释放。两段封锁协议（2PL）是最常用的封锁协议，并且能产生可串行化调度。

两段锁协议是指所有事务需要分两个阶段对数据项加锁和解锁：

在数据读写之前，事务需要先取得封锁
释放封锁之后，事务不再申请和获得其它封锁

这里的两段，具体来说就是事务的两个阶段：

扩展阶段，获得封锁，可以申请获得数据项上任何类型的锁，但是不能释放任何锁
收缩阶段，释放封锁，可以释放任何数据线上的任何类型的锁，但是不能申请任何锁。

比如事务A按照两段锁协议的封锁序列是：

Slock A, Slock B, Xlock C, Unlock B, Unlock A, Unlock C

如果多个调度都符合两段锁协议，一定是一个可串行化调度。

但是两段锁可能会出现死锁，所以还需要引入一次封锁法。也就是事务必须一次将所有使用数据全部加锁，否则就不能继续执行，这样可以回避死锁。

封锁粒度

封锁对象的大小称为封锁粒度。封锁对象分成逻辑单元和物理单元。

在关系数据库中，逻辑单元包括属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库；物理单元包括页和物理记录。

封锁粒度和系统并发度与并发控制的开销密切相关。

粒度大，封锁数据单元少，并发度低，开销小
粒度小，并发度高，开销大

下面举两个例子。

（1）若封锁粒度是数据页，事务T1需要修改元组L1，则T1必须对包含L1的整个数据页A加锁。如果T1对A加锁后事务T2要修改A中元组L2，则T2被迫等待，直到T1释放A。如果封锁粒度是元组，则T1和T2可以同时对L1和L2加锁，不需要互相等待，提高了系统的并行度。

（2）事务T需要读取整个表，若封锁粒度是元组，T必须对表中的每一个元组加锁，开销极大。

因此，在一个系统中需要同时支持多种封锁粒度供不同事务选择，也就是 多粒度封锁。在选择粒度的时候，要同时考虑封锁开销和并发度：

对处理多个关系大量元组的事务，以数据库为封锁单位
对处理大量元组的事务，以关系为封锁单位
对少量元组的用户事务，以元组为封锁单位。

可以用一颗树来表示粒度，称作多粒度树：

在这个树中，对一个结点加锁相当于节点所有子孙加同类型的锁。这里就引入了显式封锁和隐式封锁：显式封锁是直接加到数据对象上的封锁，隐式封锁是由于上级结点加锁导致的子节点加锁。

因此，系统在检查封锁冲突的收，需要检查显式封锁和隐式封锁。具体来说就是：

数据对象有没有显式封锁与之冲突
本事务显式封锁是否与上级节点隐式封锁冲突
上面的显式封锁是否与本事务隐式封锁冲突

意向锁

在此基础上，引入意向锁，来提高对某个数据对象加锁时系统的检查效率。

如果对一个结点加意向锁，说明其下层节点正在被加锁；对任意结点加基本锁，必须对上层节点加意向锁。

常用的意向锁有三种：

意向共享锁（IS锁），表示后裔节点拟（意向）加S锁
意向排它锁（IX锁），表示后裔节点拟（意向）加X锁
共享意向排它锁（SIX锁），表示对它加S锁，再加IX锁。

对于这些锁，相容矩阵如下：

锁强度的哈斯图如下：

这里锁强度是对其他所的排斥程度，强锁对弱锁是安全的。

在引入意向锁之后，执行封锁操作：

申请时按照从上到下的次序
释放时按照从下到上的次序

例如，T1对R1加S锁，需要下面的操作

对数据库加IS锁
检查数据库和R1是否加了不相容锁，也就是X或IX锁
无需搜索R1中元组是否加了X锁。

这样，意向锁提高了系统并发度，减少了加减锁的开销，得到广泛应用。