CMU-15445 LAB3:事务隔离,two-phase locking,锁管理器
概述
本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的具体代码可以参考我的手实现:
参考资料:
- http://www.mathcs.emory.edu/~cheung/courses/554/syllabus/7-serializability/2pl.html
- 《database system concepts》 chapter 14, 15
上一篇: php 地区分类排序算法