数据库系统概论：并发控制之时间戳协议、有效性检查协议

基于时间戳的协议

基于时间戳的协议

基于时间戳的协议，存在两个时间戳

• 事务时间戳 $TS(T_i)$
• 数据时间戳 $timestamp(Q)$

成功执行了 W/R 的所有事务中的最大时间戳

• $\text{W-timestamp(Q)}$
• $\text{R-timestamp(Q)}$

事务 $T_i$ 如果要读数据 $Q$：

• 如果一个事务的 $TS(T_i) < \text{W-timestamp(Q)}$ 需要读 Q 则拒绝，因为已经被写；事务回滚；
• 反之，则允许，并更新 $\text{R-timestamp(Q)} = TS(T_i)$

事务 $T_i$ 如果要写数据 $Q$：

• 如果一个事务的 $TS(T_i) < \text{R-timestamp(Q)}$ 需要写 Q 则拒绝，因为已经被写；事务回滚；
• 如果一个事务的 $TS(T_i) < \text{W-timestamp(Q)}$ 需要写 Q 则拒绝，因为已经被写；事务回滚；
• 否则，允许执行，并更新 $\text{W-timestamp(Q)} = TS(T_i)$

优点：保证了可串行性、不会存在死锁（因为按序分配资源）

缺点：

• 导致级联回滚、一些事务的不可恢复。若 $T_i$ 夭折，$T_j$ 读了 $T_i$ 的数据，则 $T_j$ 需要回滚，与 $T_j$ 相关的事务也需要回滚。
• 解决方案：
  • 事务到最后才写，所有写动作作为一个原子操作
  • 所有事务终止，重新赋予时间戳开始

Thomas 写规则

如果一个事务的 $TS(T_i) < \text{W-timestamp(Q)}$ 需要写 Q 则拒绝，因为已经被写；但只是撤销该写操作而不撤销事务。

其保证了视图可串行化。提高了并发度。

为什么基于时间戳的协议没被广泛使用

因为难以保证所有使用数据库的机器产生相同的、没有任何偏差的时间戳。

解决方案：只用一台机器来产生时间戳。但也因此产生性能瓶颈。

基于有效性检查的协议

也被称为乐观并发控制。思路是不管是否存在冲突，做了再说，再检查是否有冲突。有就撤销，没有就提交。

比较适用于读比较多的环境，因为其产生冲突的可能性比较小。

事务执行分为三个阶段：

1. $\text{Start}(T_i)$: 事务的 write 操作写入一个临时局部变量
2. $\text{Validation}(T_i) = TS(T_i)$: 有效性检查阶段：决定局部变量的值是否违反可串行化。如果违反，则撤销事务。
3. $\text{Finish}(T_i)$: 通过有效性检查的事务则提交。

事务不冲突条件（满足之一即成立）：

1. $\text{Finish}(T_i) < \text{Start}(T_j)$
2. $\text{Start}(T_j)<\text{Finish}(T_i) < \text{Validation}(T_j)$ 且 $T_i$ 写/读的数据 $T_j$ 读/写的数据不相交