数据库事务并发控制

事务四大性质（ACID）

• 原子性（atomicity）：事物的所有操作在数据库中要么全部正确反映出来，要么完全不反映。

• 一致性（consistency）：执行隔离事务时保持数据库的一致性。

• 隔离性（isolation）：尽管多个事务可能并发执行，但系统保证，对于任一一对事务，两者之间都感受不到系统中有其他事务在并发执行。

• 持久性（durability）：一个事务完成后，它对数据库的改变必须是永久的，即使系统出现故障。

可串行化

考虑下面一个调度

T1	T2
$read(A)$
$write(A)$
	$read(A)$
	$write(A)$
$read(B)$
$write(B)$
	$read(B)$
	$write(B)$

该调度中T1的write(A)指令与T2的read(A)指令冲突，因为如果交换该两条指令的顺序，可能会使得read的结果不相同，所以这两条指令无法交换顺序，而对于T1的read(B)和T2的write(A)不冲突，因为两者操作的数据不相同，如果我们对其中不冲突的指令进行顺序的交换，可以变成如下调度

T1	T2
$read(A)$
$write(A)$
$read(B)$
$write(B)$
	$read(A)$
	$write(A)$
	$read(B)$
	$write(B)$

T2事务紧跟在T1事务后面，所以这是一个可串行化的调度。

而对于以下调度

T3	T4
$read(Q)$
	$write(Q)$
$write(Q)$

这个调度是不可串行化的，因为它既不等价于串行调度<T3, T4>，也不等价于串行调度<T4, T3>。串行化顺序可以通过拓扑排序得到，如果是有冲突的，则该拓扑中一定存在环。

当然，有时候基于图可能会无法检测出某个调度是否是可串行化的。

事务隔离级别

由高到低

• 可串行化（serializable）：保证可串行化调度。所有读写都要加锁，索引也要加锁，需要强两阶段锁协议。

• 可重复读（repeatable read）：只允许读取已提交数据，而且在一个事务两次读取一个数据项期间，其他事务不得更新该数据。相对于可串行化，不需要索引锁。

• 已提交读（read committed）：只允许读取已提交数据，但不要求可重复读。比如，事务两次读取一个数据项期间，另一个事务更新了该数据并提交。相对于可重复读，读锁在使用完后立即释放。

• 未提交读（read uncommitted）：允许读取未提交数据。相对于已提交读，不需要加读锁。

所有隔离级别都不允许脏写，即如果一个数据项已经被另一个尚未提交或中止的事务写入，则不允许对该数据项执行写操作。

两阶段封锁协议（2PL）

两阶段封锁协议是保证可串行化的一个协议，要求每个事务分两个阶段提出加锁和解锁申请。

• 增长阶段：事务可以获取锁，但不能释放锁。
• 收缩阶段：事务可以释放锁，但不能获取锁。

单纯的两阶段锁可能会导致级联回滚，例如下图

当T2操作的数据是已经被T1操作过，但是T1突然中止，T1需要回滚，T2由于在T1的基础上操作也会进行回滚，此时就会发生了级联回滚。同时可以发现，此时的T2发生了脏读。

解决的方式是修改为强两阶段锁协议，它要求事务提交前不能释放任何锁。

该协议还有一个缺点是可能发生死锁，无论是否是强弱两阶段锁

死锁检测与预防

和事务可串行化一样，可以利用图来检测死锁，如果等待图出现环，则发生死锁

利用时间戳的两种不同死锁预防机制：

• wait-die：基于非抢占技术。当事务$T_i​$申请的数据项当前被$T_j​$持有，仅当$T_i​$的时间戳小于$T_j​$的时间戳（即$T_i​$比$T_j​$老）时，允许$T_i​$等待。否则，$T_i​$回滚。
• wound-wait：基于抢占技术。当事务$T_i$申请的数据项当前被$T_j$持有，仅当$T_i$的时间戳大于$T_j$的时间戳（即$T_i$比$T_j$年轻）时，允许$T_i$等待。否则$T_j$回滚。

基于时间戳的协议

该协议保证任何有冲突的$read$和$write$操作按时间戳顺序执行，且保证无死锁，因为不存在等待的事务。

1. 假设事务$T_i$发出$read(Q)$：

   a. 若$TS(T_i) \lt W-TS(Q)$，则$T_i$需要读入的$Q$值已被覆盖。因此，$read$操作被拒绝，$T_i$回滚。

   b. 若$TS(T_i) \ge W-TS(Q)$，则执行$read$操作，$R-TS(Q)=max(R-TS(Q),~TS(T_i))$。

2. 假设事务$T_i$发出$write(Q)$：

   a. 若$TS(T_i) \lt R-TS(Q)$，则$T_i$产生的$Q$值是先前所需要的值，且系统已假定该值不会再产生。因此，$write$操作被拒绝，$T_i$回滚。

   b. 若$TS(T_i) \lt W-TS(Q)$，则$T_i$试图写入的$Q$值已过时。因此，$write$操作被拒绝，$T_i$回滚。

基于有效性检查的协议

要求每个事务在其生命周期中按两个或三个阶段执行。

1. 读阶段：该阶段中，系统执行事务$T_i$。各数据项值被读入并保存在事务$T_i$的局部变量中。所有$write$操作都是对局部变量进行修改。
2. 有效性检查阶段：对事务$T_i$进行有效性检查，判断是否可以执行$write$操作而不违反可串行性。如果失败，则事务回滚。
3. 写阶段：若事务通过检查阶段，则局部变量被复制到数据库中。

多版本机制（MVCC）

该机制中，每个$write(Q)$操作创建$Q$的一个新版本。当事务发出一个$read(Q)$操作时，将会选择一个版本进行读取，需要保证被读取的版本能够保持可串行性。

每个版本包含三个数据字段：

• Content：版本内容。
• W-TS(Q)：创建$Q_k$版本的事务的时间戳。
• R-TS(Q)：所有成功地读取$Q_k$版本的事务的最大时间戳。

该机制运作如下：

假设事务$T_i$发出$read(Q)$或$write(Q)$操作，令$Q_k$表示$Q$满足如下条件的版本，其写时间戳是小于或等于$TS(T_i)$的最大写时间戳。

1. 如果事务$T_i$发出$read(Q)$，则返回值是$Q_k$的内容。
2. 如果事务$T_i$发出$write(Q)$，且若$TS(T_i) \lt R-TS(Q_k)$，则系统回滚事务$T_i$，另一方面，若$TS(T_i)=W-TS(Q_k)$，则系统覆盖$Q_k$的内容，否则如果$TS(T_i) \gt R-TS(Q_k)$，创建$Q$的一个新版本。