第 18 章：并发控制¶

锁¶

排它锁（exclusive mode lock，X）：数据上了排它锁后可读可写；自然地，其它进程既不能读它也不能写它，所以叫排它锁。

共享锁（shared lock，S）：数据上了共享锁后可读，但是不能写。此时其他进程不能写这个数据。一个数据可以被多个事务上共享锁，但是不能给已经有排它锁的数据上共享锁。

两段锁协议¶

两段锁协议（Two-Phase Locking Protocol，2PL）分为两个阶段：

加锁阶段 Growing Phase
解锁阶段 Shrinking Phase

这样加解锁的话，每个事务都有自己的锁点（lock points，一个事务加上它的最后一个锁的时候）。这种协议可以保证最后的事务一定是冲突可串的。

严格的两段锁：一旦上了排它锁，就必须直到事务执行完或者中止了才能解锁。
强的两段锁：一旦上了排它锁和共享锁，就必须直到事务执行完或者中止了才能解锁。

两段锁协议的证明¶

一个反证法¶

假设现在有一些事务。假设用 2PL 得出的调度不是冲突可串的，那么它的前驱图里面有环。

不失一般性地，我们让这个环长成 \(T_0 \to T_1 \to T_2 \to \cdots \to T_{n - 1} \to T_0\)。出于 2PL 的规则，如果有 \(T_i \to T_j\) 这样一条边，那么 \(T_i\) 的锁点 \(a_i\) 一定早于 \(T_j\) 的 \(a_j\)，因为 \(T_i\) 先访问到。代到上面就可以推出 \(a_0 < a_0\)，肯定不对。所以假设不成立，前驱图里面没环，所以调度总是冲突可串的。

一个正攻¶

对于事务 \(T_0 \cdots T_{n - 1}\)，\(T_i\) 的锁点是最先来的。那么可以把 \(T_i\) 的所有读写操作放到调度的最前面来，而不造成冲突。如果造成冲突，假设 \(w_j(y)\) 比 \(w_i(y)\) 来得早，那么要么 \(T_i\) 的锁点比 \(T_j\) 的晚，要么这不是个 2PL。

锁转换¶

加锁阶段可以把 S 锁加强成 X 锁。
解锁阶段可以把 X 锁削弱成 S 锁。

锁管理器¶

锁管理器作为一个进程，处理和锁相关的事情。对于一个上锁请求，它会给相应内容加锁，或者要求上锁的事务先回滚（如果会发生死锁时）。

锁管理器通过锁表来管理锁。

锁表¶

锁表是链表的链表的集合，对于每个数据维护已经上锁的事务和等待上锁的事务。

基于图的加锁协议¶

对于数据 \(D = \{d_1, d_2, \cdots, d_h\}\)，如果对于所有事务，想访问 \(d_j\) 就必须先访问 \(d_i\)，那么就连一条单向边 \(d_i \to d_j\)。最终这样会形成一个 DAG，叫做数据库图。

对于树状协议，这个 DAG 是一棵树。事务上锁时有这些限制：

只能上 X 锁。
除了第一个锁，给一个数据上锁时其树上的父亲必须已经上锁。解锁没有这个限制。
同一个事务不能给同一个数据上两次锁。

这样在保证冲突可串行化的同时，可以防止死锁；并且因为解锁没有限制，它相比 2PL 可以更快解锁，提高并行化速度。但它不能防止级联回滚；并且也会导致锁到不访问的数据上。

基于时间戳的协议¶

根据事务的时间戳来对它们的序列化顺序进行排序。对于每个数据 Q 维护 W-TS(Q) 和 R-TS(Q)，分别是读过它的事务的最大的时间戳的值和写过它的事务的最大的时间戳的值。

现在有一个事务 \(T_i\)，它有时间戳 TS(T_i)，想读数据 Q。

如果 TS(T_i) \(\leq\) W-TS(Q)，也就是说它要读的这个东西已经被一个更晚的事务给写了。它得回滚。
如果 TS(T_i) \(\geq\) W-TS(Q)，就会把 R-TS(Q) 和 TS(T_i) 取最大。

现在有一个事务 \(T_i\)，它有时间戳 TS(T_i)，想写数据 Q。

如果 TS(T_i) < R-TS(Q)，也就是说它要写的这个东西本来要被一个更晚的事务读，但是那个事务没读到。它得回滚。
如果 TS(T_i) < W-TS(Q)，那么写的顺序就出问题了。它得回滚。
否则就会把 W-TS(Q) 和 TS(T_i) 取最大。

因为时间自带的偏序关系，事务之间不会存在环。但是给出来的调度方案可能存在级联现象，有时候甚至还不支持回退。

意向锁¶

共享型意向锁 IS
排它型意向锁 IX
共享排它型意向锁 SIX