CMU-15445 LAB3:事务隔离，two-phase locking，锁管理器

概述

本lab将实现一个锁管理器，事务通过锁管理器获取锁，事务管理器根据情况决定是否授予锁，或是阻塞等待其它事务释放该锁。

背景

事务属性

众所周知，事务具有如下属性：

1. 原子性：事务要么执行完成，要么就没有执行。
2. 一致性：事务执行完毕后，不会出现不一致的情况。
3. 隔离性：多个事务并发执行不会相互影响。
4. 持久性：事务执行成功后，所以状态将被持久化。

一些定义

将对数据对象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）的正确性。我看了下解答，用的是反正法。我还看到一个用归纳法证的，比较有趣。
前提：

1. 假设t1, t2, ... tn，n个事务遵循two-phase locking协议。
2. 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上的锁，造成死锁。

死锁处理

有两类基本思路：

1. 死锁预防，这类方法在死锁出现前就能发现可能导致死锁的操作。
2. 死锁检测，这类方法定期执行死锁检测算法，看是否发生死锁，如果发生了，执行死锁恢复算法。

这里介绍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的具体代码可以参考我的手实现：

参考资料：

1. http://www.mathcs.emory.edu/~cheung/courses/554/syllabus/7-serializability/2pl.html
2. 《database system concepts》 chapter 14, 15