一文读懂InnoDB经典并发控制协议——两阶段锁

两阶段锁协议定义及证明

两阶段锁（Two-Phase Locking，2PL）协议是最经典的并发控制协议，内容十分简单：

在每个事务中，所有的加锁操作先于所有的解锁操作。

就是这样一个简单的协议，便可以保证遵守该协议的调度都符合冲突可串行化！在两阶段锁协议中，事务被分割成两个阶段：加锁（Lock）阶段和解锁（Unlock）阶段，如图1所示。

图1.两阶段锁协议

引理：(T1,T2，...，Tn)是优先图中的一个路径，那么对于事务T1和Tn，存在两个操作p1（x）和qn（y）满足 UNLOCK(p1(x))＜LOCK（qn（y））。

图2所示为三个事务使用两阶段锁的场景，首先看一下n=2的情况。若T1→T2说明有在两个事务中分别有两个操作是冲突的，记为p1（x）和q2（x）。根据冲突操作的定义，两个操作冲突说明它们作用于同一元素，而且至少有一个是写操作。

然后看一下n=3的情况：

因为两阶段锁协议规定，“在每个事务中，所有的加锁操作先于所有的解锁操作”所以在事务T2中有：

结合前面的不等关系式可知：

最后可以得到UNLOCK（p1（x））→LOCK（q3（y））。

图2.三个事务使用两阶段锁的场景

同理可扩展至任意N个事务（严格证明需要用数学归纳法）。

定理：优先图（G）是无环的。假设G中有环，设该环为(T1,T2，...，Tn)那么根据上面的引理，UNLOCK(p1(x))→LOCK（q1（y）），这样的话在T1中存在一个解锁操作先于一个加锁操作，与两阶段锁协议矛盾。因此G是无环的。

其实从上面的证明可以看出，两阶段锁协议是完成证明的充分条件，因此有：

定理：Gen（2PL）⊆CSR。2PL产生的调度是冲突可串行化的。

注意，上面的结论反过来不一定成立。下面通过举例来说明存在冲突可串行化的调度但不能通过两阶段锁协议得到。例如，调度S：w1（x）r2（x）c2r3（y）c3w1（y）c1，不满足两阶段锁协议的冲突可串行化调度如图3所示。

图3.不满足两阶段锁协议的冲突可串行化调度

S满足冲突可串行化：

但不能通过两阶段锁协议得到。因为r2（x）会等待w1（x）释放对数据x的锁。因此r2（x）会一直阻塞直至T1提交，最后根据两阶段锁协议得到的调度是这样的：

下面进行形式化的证明：

已知UNLOCK（w1（x））→LOCK（r2（x））→r2（x），并且r3（y）→UNLOCK（r3（y））→LOCK（w1（y）），又因为r2（x）→r3（y），那么UNLOCK（w1（x））→LOCK（w1（y））违反两阶段锁协议。需要注意的是两阶段锁协议可能会发生死锁（Deadlock）。下面看一个例子，如图4所示。

在这个调度中，w1（y）被w2（y）阻塞，同时w2（x）被r1（x）阻塞，形成死锁。破局方式就是中断其中一个事务，让其回滚。

图4.死锁

死锁检测的标准方法就是构建事务间的等待图（Wait-For Graph，WFG）。例子中w1（y）被w2（y）阻塞，就在等待图中添加边T1→T2，表示T1被T2阻塞，在等待T2对某个元素进行解锁操作之后才能继续。同理在等待图中继续添加边T2→T1，等待图如图5所示。如果等待图中有环，表明调度中存在死锁。