严格两阶段锁 | Codeboy's Blog

形式陈述

以下协议约束事务调度中的逻辑读写、锁请求与提交／中止事件；锁动作控制这些事件何时允许发生。

严格两阶段锁为读取得共享锁 $S(x)$ ，为写取得排他锁 $X(x)$ ；共享锁彼此兼容，排他锁与同项其他锁不兼容。普通两阶段锁要求事务先处于增长阶段，只取得或升级锁；一旦释放第一把锁便进入收缩阶段，之后不得再取得新锁。

本页采用数据库教材中常称 rigorous 2PL 的严格口径：事务的共享锁和排他锁都持有到 commit 或 abort，再统一释放。有些文献把“strict 2PL”限定为只把排他锁持有到结束；引用性质时必须核对术语。本口径直接生成严格事务调度。

名称中的“两阶段”是同一事务的锁增长阶段与收缩阶段，不是两阶段提交的 prepare/decision 协调；两种协议既不互相实现，也不互相蕴含。严格调度与“严格可串行化”仍是不同性质：后者还要求串行见证保持不重叠事务的实时先后。在全部逻辑访问都正确加锁、事务边界与应答边界一致的本页协议中，下述锁点排序也能满足这项额外要求；不能把它误说成单靠严格调度就已得到。

对每个事务取其最后一次成功获锁的时刻作为 lock point。若冲突操作使前驱图出现边 $T_i\to T_j$ ，相应不兼容锁迫使 $T_i$ 的相关锁先获得并在 $T_j$ 获锁前释放，因此事务的锁点可以给出一致次序。所有边沿该次序前进，图无环，于是调度满足冲突可串行化。每个事务的锁点又位于它开始与完成之间，所以一个事务已经完成、另一个才开始时，二者锁点也按该实时顺序排列。对已提交事务取这个顺序，就同时得到严格可串行化见证；空事务可在自己的调用区间内任取位置。谓词访问若未被锁协议覆盖，前述冲突证明的前提已经不成立。

锁升级也受两阶段纪律约束。事务可把 $S(x)$ 升为 $X(x)$ ，但升级等价于取得更强锁，必须发生在仍可增长的阶段；两个事务都持有 $S(x)$ 再同时请求升级，会互相等待。意向锁只是在层级粒度中协调表、页、行锁，不能绕开兼容矩阵。

直觉

两阶段纪律禁止“放下一把锁后又伸手拿新锁”。否则事务可能先向一个邻居让路，再在另一数据项上反过来排到它前面，形成难以统一的冲突次序。把锁一直持有到事务结束，还让别人看不到或覆盖未提交写，恢复时不必追赶读过脏值的后继事务。

严格不等于不会等待。锁把不安全交错变成阻塞，多个阻塞仍可能闭合成死锁；正确性与进展是两份义务。

锁点证明解释的是已经获准的操作次序，等待队列策略则决定谁何时能取得锁。FIFO、公平唤醒或 wound-wait 可以影响饥饿与死锁恢复，却不会把违反两阶段纪律的提前释放变成可串行。

例子与边界

$T_1$ 先锁账户 A、再锁 B， $T_2$ 先锁 B、再锁 A：

text

T1: X(A) granted
T2: X(B) granted
T1: request X(B) -> wait
T2: request X(A) -> wait

wait-for 图出现 $T_1\to T_2\to T_1$ ，形成死锁。两者都遵守两阶段规则；规则保证已经完成的调度可串行，却不保证每个事务完成。规定所有事务按 A、B 的全局次序申请，可破坏这个循环，但仍可能因长事务造成饥饿或高延迟。

若 $T_1$ 写 A 后仍持有 $X(A)$ ， $T_2$ 的读和写都会等到 $T_1$ commit/abort，因而没有脏读或脏写。只持有排他锁到结束、却提前释放共享锁的较弱术语版本仍可严格保护写入，但不具有“所有读写锁都在终点释放”的本页接口。

行锁还不足以自动阻止幻读。事务读取谓词“余额小于零”后，另一事务可插入新行；要维持可串行化，锁管理器需对索引范围、谓词或间隙建立冲突。锁升级、锁粒度和意向锁改变性能与冲突表示，不能省略其兼容规则。

多粒度锁把IS、IX、SIX的权限、兼容和祖先取得次序完整展开，让粗粒度请求能够发现下方细锁；谓词与区间锁进一步把尚不存在的潜在键也纳入保护。前者规定锁在不同层级怎样相遇，后者规定查询的逻辑范围，二者仍沿用本页的终点持有纪律。

abort 路径必须与 commit 一样作为终点释放锁。若事务先释放 $X(x)$ ，再异步执行 undo，下一事务可能读到将被撤销的值；正确顺序是保持排他保护，完成所需回滚，再让其他事务访问恢复后的版本。

推论与应用

严格两阶段锁同时连接隔离与恢复：前驱图证明给出串行顺序，终点释放又使未提交写不被其他事务消费。它是生成严格调度的一种充分机制，不是严格性定义的唯一实现，更不与任意“事务使用了锁”同义。

数据库还需死锁检测、超时或预防策略，并在中止受害者时释放全部锁和撤销写入。若系统在日志尚不能恢复更新前就授予并释放锁，锁层正确也救不了崩溃原子性；并发控制与恢复协议必须在 commit 路径上对接。

审计锁实现时，可从 grant/release trace 重建每个事务的增长边界与 lock point，再检查任何 release 后是否出现新 grant。只看 SQL 执行顺序会漏掉锁升级、谓词锁和内部索引访问，因而不足以证明严格 2PL。

参考资料

Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987, Chs. 3–4。
Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1992, Chs. 7–8。
Kapali P. Eswaran et al., “The Notions of Consistency and Predicate Locks in a Database System,” Communications of the ACM 19(11), 1976, pp. 624–633。

形式陈述 ​

反向链接

形式陈述