概述
本 lab 将实现一个锁管理器, 事务通过锁管理器获取锁, 事务管理器根据情况决定是否授予锁, 或是阻塞等待其它事务释放该锁.
背景
事务属性
众所周知, 事务具有如下属性:
原子性: 事务要么执行完成, 要么就没有执行.
一致性: 事务执行完毕后, 不会出现不一致的情况.
隔离性: 多个事务并发执行不会相互影响.
持久性: 事务执行成功后, 所以状态将被持久化.
一些定义
将对数据对象 Q 的操作进行抽象, read(Q): 取数据对象 Q,write(Q) 写数据对象 Q.
schedule
考虑事务 T1,T1 从账户 A 向账户 B 转移 50.
- T1:
- read(A);
- A := A - 50;
- write(A);
- read(B);
- B := B + 50;
- write(B).
事务 T2 将账户 A 的 10% 转移到账户 B.
- T2:
- read(A);
- temp := A * 0.1;
- A := A - temp;
- write(A);
- read(B);
- B := B + temp;
- write(B).
假设账户 A,B 初始值分别为 1000 和 2000.
我们将事务执行的序列称为 schedule. 如下面这个 schedule,T1 先执行完, 然后执行 T2, 最终的结果是具有一致性的. 我们称这种 schedule 为 serializable schedule.
- T1 T2
- read(A);
- A := A - 50;
- write(A);
- read(B);
- B := B + 50;
- write(B).
- read(A);
- temp := A * 0.1;
- A := A - temp;
- write(A);
- read(B);
- B := B + temp;
- write(B).
但是看下面这个 shedule:
- T1 T2
- read(A);
- A := A - 50;
- read(A);
- temp := A * 0.1;
- A := A - temp;
- write(A);
- read(B);
- write(A);
- read(B);
- B := B + 50;
- write(B).
- read(B);
- B := B + temp;
- write(B).
执行完账户 A 和 B 分别为 950 和 2100. 显然这个 shecule 不是 serializable schedule.
考虑连续的两条指令 I 和 J, 如果 I 和 J 操作不同的数据项那么, 这两个指令可以交换顺序, 不会影响 schedule 的执行结果. 如果 I 和 J 操作相同的数据项, 那么只有当 I 和 J 都是 read(Q) 时才不会影响 schedule 的结果. 如果两条连续的指令, 操作相同的数据项, 其中至少一个指令是 write, 那么 I 和 J 是 conflict 的.
如果 schedule S 连续的条指令 I 和 J 不 conflict, 我们可以交换它们执行的顺序, 从而产生一个新的 schedlue S', 我们称 S 和 S'conflict equivalent. 如果 S 经过一系列 conflict equivalent 变换, 和某个 serializable schedule 等价, 那么我们称 S 是 conflict serializable.
比如下面这个 schedule S:
- T1 T2
- read(A);
- write(A);
- read(A);
- write(A);
- read(B);
- write(B);
- read(B);
- write(B);
经过多次 conflict equivalent 变换, 生成新的 schedule S',S'是 serializable schedule.
- T1 T2
- read(A);
- write(A);
- read(B);
- write(B);
- read(A);
- write(A);
- read(B);
- write(B);
所以 S 是 conflict serializable 的.
two-phase locking
不对加解锁进行限制
前面提到多个事务并发执行的时候, 可能出现数据不一致得情况. 一个很显然的想法是加锁来进行并发控制.
可以使用共享锁 (lock-S), 排他锁 (lock-X).
问题来了.
在什么时候加锁? 什么时候释放锁?
考虑下面这种加解锁顺序:
事务一从账户 B 向账户 A 转移 50.
- T1:
- lock-X(B);
- read(B);
- B := B - 50;
- write(B);
- unlock(B);
- lock-X(A);
- read(A);
- A := A + 50;
- write(A);
- unlock(A).
事务二展示账户 A 和 B 的总和.
- T2:
- lock-S(A);
- read(A);
- unlock(A);
- lock-S(B);
- read(B);
- unlock(B);
- display(A+B).
可能出现这样一种 schedule:
- T1 T2
- lock-X(B);
- read(B);
- B := B - 50;
- write(B);
- unlock(B);
- lock-S(A);
- read(A);
- unlock(A);
- lock-S(B);
- read(B);
- unlock(B);
- display(A+B).
- lock-X(A);
- read(A);
- A := A + 50;
- write(A);
- unlock(A).
假设初始时 A 和 B 分别是 100 和 200, 执行后事务二显示 A+B 为 250, 显然出现了数据不一致.
我们已经加了锁, 为什么还会出现数据不一致?
问题出在 T1 过早 unlock(B).
two-phase locking
这时引入了 two-phase locking 协议, 该协议限制了加解锁的顺序.
该协议将事务分成两个阶段,
Growing phase: 事务可以获取锁, 但是不能释放任何锁.
Shringking phase: 事务可以释放锁, 但是不能获取锁.
最开始事务处于 Growing phase, 可以随意获取锁, 一旦事务释放了锁, 该事务进入 Shringking phase, 之后就不能再获取锁.
按照 two-phase locking 协议重写之前的转账事务:
事务一从账户 B 向账户 A 转移 50.
- T1:
- lock-X(B);
- read(B);
- B := B - 50;
- write(B);
- lock-X(A);
- read(A);
- A := A + 50;
- write(A);
- unlock(B);
- unlock(A).
事务二展示账户 A 和 B 的总和.
- T2:
- lock-S(A);
- read(A);
- lock-S(B);
- read(B);
- display(A+B).
- unlock(A);
- unlock(B);
现在无论如何都不会出现数据不一致的情况了.
two-phase locking 正确性证明
课本的课后题 15.1 也要求我们证明 two-phase locking(以下称 2PL rule) 的正确性. 我看了下解答, 用的是反正法. 我还看到一个用归纳法证的, 比较有趣.
前提:
假设 T1, T2, ... Tn,n 个事务遵循 two-phase locking 协议.
Sn 是 T1, T2, ... Tn 并发执行的一个 schdule.
目标:
证明 Sn 是 conflict serializable 的 schedule.
证明开始:
起始步骤, n = 1 的情况:
T1 遵守 2PL rule.
S1 这个 schedule 只包含 T1.
显然 S1 是 conflict serializable 的 schedule.
迭代步骤:
迭代假设: 假设 Sn-1 是 T1, T2, ... Tn−1 形成的一个 schedule, 并且 Sn-1 是 conflict serializable 的 schedule. 我们需要证明 Sn-1 是 conflict serializable 的 schedule,Sn 也是 conflict serializable 的 schedule.
假设 Ui(•) 是事务 i 的解锁操作, 并且是 schedule Sn 中第一个解锁的操作:
可以证明, 我们可以将事务 i 所有 ri(•) and wi(•) 操作移到 Sn 的最前面, 而不会引起 conflict.
证明如下:
令 Wi(Y) 是事务 i 的任意操作, Wj(Y) 是事务 j 的一个操作, 并且和 Wi(Y)conflict. 等价于证明不会出现如下这种情况:
假设出现了这种情况, 那么必然有如下加解锁顺序:
又因为所有事务都遵守 2PL rule, 所以必然有如下加解锁顺序:
冲突出现了, Ui(•) 应该是 Sn 中第一个解锁操作, 但是现在却是 Uj(Y). 所以假设不成立, 所以结论:"我们可以将事务 i 所有 ri(•) and wi(•) 操作移到 Sn 的最前面, 而不会引起 conflict" 成立.
我们将事务 i 的所有操作移到 schedule 最前面,
又因为 Sn-1 是 conflict serializable 的所以 Sn 是 conflict serializable 的.
证明完毕
two-phase locking 不能保证不会死锁
two-phase locking 可以保证 conflict serializable, 但可能会出现死锁的情况.
考虑这个 schedule 片段:
- T1 T2
- lock-X(B);
- read(B);
- B := B - 50;
- write(B);
- lock-S(A);
- read(A);
- lock-S(B);
- lock-X(A);
T1 和 T2 都遵循 2PL rule, 但是 T2 等待 T1 释放 B 上的锁, T1 等待 T2 释放 A 上的锁, 造成死锁.
死锁处理
有两类基本思路:
死锁预防, 这类方法在死锁出现前就能发现可能导致死锁的操作.
死锁检测, 这类方法定期执行死锁检测算法, 看是否发生死锁, 如果发生了, 执行死锁恢复算法.
这里介绍 wait-die 这种死锁预防机制, 该机制描述如下:
事务 Ti 请求某个数据项, 该数据项已经被事务 Tj 获取了锁, Ti 允许等待当且仅当 Ti 的时间戳小于 Tj, 否则 Ti 将被 roll back.
wait-die 正确性证明
为什么该机制能保证, 不会出现死锁的情况呢?
如果 Ti 等待 Tj 释放锁, 我们记 Ti->Tj. 那么系统中所有的事务将组成一个称作 wait-for graph 的有向图. 容易证明: wait-for graph 出现环和系统将出现死锁等价.
wait-die 这种机制就能防止出现 wait-for graph 出现环. 为什么? 因为 wait-die 机制只允许时间戳小的等待时间戳大的事务, 也就是说在 wait-for graph 中任意一条边 Ti->Tj,Ti 的时间戳都小于 Tj, 显然不可能出现环. 所以不会出现环, 也就不可能出现死锁.
LockManager 的具体代码可以参考我的手实现: https://github.com/gatsbyd/cmu_15445_2018
参考资料:
《Database System concepts》 chapter 14, 15
来源: https://www.cnblogs.com/gatsby123/p/10800089.html