Lecture 19: Transactions and Concurrency Control — 事务与并发控制
Lecture 19: Transactions and Concurrency Control — 事务与并发控制
讲义对应：CS 425 FA2026 Lecture 21「Concurrency Control, Transactions」。本章素材取自原始讲义
L19-20.FA25.pdf（Lecture 19-20: RPCs and Concurrency Control，57 页）的后半部分（事务与并发控制）：事务的定义与 ACID、串行等价（serial equivalence）、冲突操作判定、悲观并发控制（锁与两阶段锁）、乐观并发控制、时间戳排序、多版本并发控制，以及死锁问题的完整处理。该讲义前半部分的 RPC/RMI、stub/dispatcher、marshalling 与三种调用语义属于进程间通信一章，本章不重复。 边界声明：本章只讲单机/一般的事务与并发控制。分布式事务、两阶段提交（2PC）、Atomic Commit 问题、复制控制（one-copy serializability）由 Lecture 20 章节负责（素材L21.FA25.pdf）；分布式死锁检测所依赖的一致性全局快照见「Snapshots」一章（Chandy-Lamport 算法，素材L13.FA25.pdf），本章只引用其结论。 教材对应：Coulouris 5th Ed. Ch. 16 Transactions and Concurrency Control（16.1 事务的 ACID、16.2 嵌套事务、16.3 锁、16.4 乐观并发控制、16.5 时间戳排序）；补充 Ch. 17（分布式事务，见 Lecture 20）、Sec 14.5（全局快照）。 阅读材料：Bernstein, Hadzilacos & Goodman, Concurrency Control and Recovery in Database Systems（Ch. 3 锁、Ch. 4 时间戳、Ch. 5 多版本）；Kung & Robinson, On Optimistic Methods for Concurrency Control, ACM TODS 1981；Berenson et al., A Critique of ANSI SQL Isolation Levels, SIGMOD 1995；Cahill, Röhm & Fekete, Serializable Isolation for Snapshot Databases, SIGMOD 2008（SSI）。
19.1 概述
单个客户端的操作序列一旦跨越多个服务器对象（讲义里的订票例子：先查余票、再订票、再选座位），就必然会遇到一个新问题：如果执行到一半机器崩了，或者另一个客户端同时在改同一份数据，我们怎么保证这些操作”要么一起成功、要么一起不做”？ 这个问题的答案就是事务（Transaction）——一个原子的、不可分割的操作序列，加上 ACID 四条性质（原子性、一致性、隔离性、持久性）。而其中最难、也最有技术含量的一条是隔离性：当许多事务同时在跑，我们要让它们”互不干扰”，效果等价于它们一个一个串行执行。为隔离性服务的整套机制，就是本章的主角——并发控制（Concurrency Control）。
本章的主线可以概括成一条推理链：串行执行天然正确 → 并发的目标是”等价于某个串行执行” → 把这个等价性形式化为”冲突可串行化” → 用优先图无环来判定 → 于是得到四类实现手段：锁（2PL，悲观）、验证（OCC，乐观）、时间戳排序（TO，全局定序）、多版本（MVCC，读写分离）。 每类手段都能保证可串行化，但都要付出各自的代价：锁会死锁，验证会回滚，时间戳会饥饿，多版本会写偏斜。
这门课的位置：它向前承接 RPC（事务的每个操作往往就是一次 RPC）与「复制」主题，向后直接通向 Lecture 20 的分布式事务与 2PC（当对象分布在多个服务器上时，原子提交本身变成一个共识问题），也向回呼应快照与全局状态一章（分布式死锁检测必须建立在一个一致性全局快照之上）。
19.2 核心概念与分布式机制图解
19.2.1 事务（Transaction）
- 定义与目的：事务是客户端执行的一个操作序列，其中每个操作都是对服务器的远程调用（RPC）；这些操作要么全部完成并提交（commit）——把更新反映到服务器对象上，要么全部不生效（abort）——服务器上不留任何痕迹。讲义用订票程序的伪代码给出了最直观的样子：
int transaction_id = openTransaction();
x = server.getFlightAvailability(ABC, 123, date); // read(ABC, 123, date)
if (x > 0)
y = server.bookTicket(ABC, 123, date); // write(ABC, 123, date)
server.putSeat(y, "aisle"); // write(ABC, 123, date)
// commit entire transaction or abort
closeTransaction(transaction_id);
- 直观解释（”它是什么？”）：事务就像银行转账。从 A 账户扣 100 元和给 B 账户加 100 元是两条独立的写操作，如果系统在两条之间崩溃，钱就会凭空消失（A 少了 100，B 没多）。事务把这两条写打包成一个不可分割的单位：要么”扣款 + 入账”都发生，要么两条都不发生。现实类比：事务像婚礼上的誓言——要么两人都说了”我愿意”，要么这场婚礼根本不算数，绝不会出现”只有一方说了我愿意”的中间状态被别人看到。
- 机制图解：事务的生命周期与两种收尾方式。
BEGIN / openTransaction()
│
▼
┌──────────────────────┐
│ 读操作 R(x) / 写操作 W(x) │ ← 每个操作可能是一次 RPC
│ （可以反复读写多个对象） │
└──────────┬───────────┘
│
┌──────────┴───────────┐
▼ ▼
COMMIT（提交） ABORT（中止/回滚）
效果全部落到服务器 服务器上不留任何效果
数据进入"永久状态" 事务可以重试（retry）
- 关键假设与系统模型：一个事务被抽象成”由若干读写操作组成、以 commit 或 abort 结尾”的原子单位；操作作用于命名对象（数据项）。两个必须面对的现实是：① 客户端和服务器都可能崩溃；② 多个客户端的事务会并发执行。这两点分别把事务推向”恢复（recovery）”与”并发控制（concurrency control）”两个子问题——本章主要解决后者。
19.2.2 ACID 四性质（逐一严格定义）
事务被要求同时满足四条性质，讲义原文如下（并补充了每条的实现机制）：
① 原子性（Atomicity）—— all or nothing
- 事务要么完整成功地完成，其效果被记录到服务器对象上；要么完全没有效果。这是”故障时的全有或全无”。
- 实现机制：日志（logging）与恢复（recovery）。数据库在执行每个操作前先把”要做什么/怎么撤销”写进日志（undo 日志记旧值以便回滚，redo 日志记新值以便重放），崩溃重启后根据日志决定撤销（undo）未提交事务、重放（redo）已提交事务。日志必须先于数据落盘，否则崩溃后无从恢复。
② 一致性（Consistency）
- 如果服务器一开始处于一致状态，那么事务结束时服务器仍处于一致状态。这里的”一致”指的是不违反完整性约束（integrity constraints），例如”账户余额 ≥ 0”、”转账前后两个账户的总和不变”、”每个订单必须对应一个已存在的用户”。
- 注意：这个 C 是应用/业务语义层面的，与 CAP 定理里的 C（线性一致性，linearizability）完全不同——见 19.2.3 的澄清表。数据库只能帮你检查声明式约束（外键、
CHECK、唯一索引），“转账前后总额不变”这类业务不变量最终要靠应用自己来保证。
③ 隔离性（Isolation）
- 一个事务必须不受其他事务干扰地执行；其他事务不得看到它的中间（非最终）状态。等价说法：并发执行的效果必须等同于某个串行执行。
- 这是并发控制要解决的问题，也是本章 80% 篇幅的所在。
④ 持久性（Durability）
- 事务成功完成之后，它的所有效果都被保存到永久存储（permanent storage）中，即使随后系统崩溃也不会丢失。
- 实现机制：预写日志（Write-Ahead Logging, WAL） +
fsync。所谓 write-ahead，就是”日志先落盘，数据页可以稍后落盘“：提交时至少保证这条 commit 记录已经fsync到磁盘，之后即便内存里的脏页全部丢失，重启后也能用 redo 日志把它们重新做出来。
19.2.3 澄清一个最常见的混淆：ACID 的 C ≠ CAP 的 C
| 维度 | ACID 的 C（Consistency） | CAP 的 C（Consistency） |
|---|---|---|
| 所属层次 | 应用/业务语义层（不变量与完整性约束） | 分布式副本语义层（多副本对外表现） |
| 精确含义 | 事务把数据库从一个满足约束的状态带到另一个满足约束的状态 | 所有副本对同一数据呈现同一份”最新”值，读总能读到最近一次写（可线性化） |
| 谁来保证 | 应用 + 声明式约束；数据库只能检查外键、CHECK、唯一性等 | 复制协议：quorum 读写、共识（Paxos/Raft）、主从复制 + 线性一致读 |
| 能否被单一机制保证 | 不能：业务不变量（如”总额守恒”）必须由应用在事务里显式维护 | 能：由系统对客户端透明地保证 |
| 与 A/I/D 的关系 | C 是 A + I + D 共同作用后在业务上看到的结果 | 与 A（可用性）在分区时构成 CAP 权衡 |
| 典型误解 | “用了事务，系统就强一致了” | “ACID 里的 C 就是 CAP 里的 C” |
一句话记忆：ACID 的 C 是”钱不能凭空多出来或消失”，CAP 的 C 是”所有副本说法一致”。前者是业务不变量，后者是副本一致性；事务给不了后者，复制协议也给不了前者。
19.2.4 事务的两种失败处理：abort 与 crash
事务失败有两条性质完全不同的路径，实现上的处理方式也不同：
| abort（中止 / 回滚） | crash（崩溃） | |
|---|---|---|
| 触发者 | 应用主动放弃（用户取消、约束冲突）、并发控制协议判定冲突 | 进程/机器/电源故障，或服务器被杀死 |
| 系统是否知情 | 知情：这是一次正常的控制流 | 事后才知情：重启时通过日志发现 |
| 处理方式 | 撤销（undo）本次事务已做的写，释放其持有的锁，回到事务开始前的状态 | 重启后扫描日志：撤销所有未提交事务，重做已提交事务的更新 |
| 能否重试 | 可以，通常是立即或稍后重试（retry） | 客户端通常需要重新发起整个事务 |
| 对客户端语义 | 客户端应当预期”事务可能失败”，必须写重试逻辑 | 连接断开，客户端需要重新连接并重做 |
实践含义：abort 是”常态”，不是异常。任何声称”事务一定成功”的应用代码都是错的——乐观协议下 abort 可能频繁发生，锁协议下死锁牺牲者也会收到 abort。
19.2.5 为什么需要并发：吞吐、利用率与响应时间
- 提高吞吐（throughput）：一个事务在等磁盘 I/O 或网络往返时，CPU 是空闲的；让另一个事务占用 CPU，可以把CPU 与 I/O 重叠起来，每秒完成的事务数（transactions per second, TPS）因此显著提高。
- 提高资源利用率：减少 CPU 空转、减少磁盘队列空闲，让昂贵的硬件不闲着。
- 降低平均响应时间：短事务不必排在一个长事务后面等它跑完（head-of-line blocking）。
- 经济动机（讲义的说法很直白）：“Transactions per second directly related to revenue of companies” —— 每秒事务数直接关系到公司营收，所以这个指标必须被最大化。
反过来，最朴素的”正确做法”是把事务一个一个串行执行（服务器一次只跑一个事务）。它天然正确，但把并发度压到了 1，把上面三条收益全部丢掉。于是整个并发控制的目标可以精确表述为：
在保持 ACID（尤其是隔离性）正确性的前提下，尽可能提高并发度。
19.2.6 并发带来的三类经典异常（含交错时序图）
先约定记号：$R_i(x)$ 表示事务 $T_i$ 读数据项 $x$，$W_i(x)$ 表示 $T_i$ 写 $x$。下面沿用讲义里的机票例子：服务器上有数据项 ABC123、ABC789 表示两条航线的余票数。
异常一：丢失更新（Lost Update Problem）
两个事务都”读—改—写”同一个数据项，后写者覆盖了先写者的更新。
时刻 事务 T1 服务器数据项 ABC123 事务 T2
──── ──────────────────────── ──────────────────── ────────────────────────
t1 R1(ABC123) → 读到 x = 10 seats = 10
t2 R2(ABC123) → 读到 x = 10
t3 W1(ABC123, 10-1 = 9) seats = 9
t4 W2(ABC123, 10-1 = 9)
t5 commit seats = 9
t6 commit
最终 seats = 9 ✗
正确结果：串行执行（T1;T2 或 T2;T1）都得到 seats = 8
事实 ：两个事务各卖出一张票，却只扣了一张 —— T1 的更新被"丢失"了
两个事务都基于同一个旧值 10 计算新值 9，于是第二次写覆盖了第一次写。要发现它，只需比较冲突操作对的顺序：$(R_1, W_2)$ 给出 $(T_1,T_2)$，$(R_2, W_1)$ 给出 $(T_2,T_1)$——两对的顺序不一致，历史不可串行化（讲义称 “Caught!”）。
异常二：不一致检索 / 脏读（Inconsistent Retrieval Problem）
一个事务在读另一个事务未完成的中间状态：讲义的例子是”转账”与”对账”并发。
时刻 事务 T1（从 ABC123 转 5 张到 ABC789） 服务器状态 事务 T2（对账：求总票数）
──── ────────────────────────────────────── ────────────────── ───────────────────────────
t1 R1(ABC123) → x = 10 ABC123 = 10
t2 W1(ABC123, 10-5 = 5) ABC123 = 5
t3 R2(ABC123) → 读到 5
t4 R2(ABC789) → 读到 15
t5 R1(ABC789) → y = 15 ABC789 = 15
t6 W1(ABC789, 15+5 = 20) ABC789 = 20
t7 commit
t8 print("Total:" 5+15 = 20)
t9 commit
正确结果：无论串行顺序如何，总额恒为 25（10+15 = 5+20）
事实 ：T2 打印 Total: 20 —— 它读到了"钱已经转走、但还没到账"的中间状态
这就是不一致检索（inconsistent retrieval）：T2 的两次读分别落在 T1 的两个写之间，看到的是一个从未真实存在过的数据库状态。它同时也是脏读（dirty read）的一种——T2 读到了 T1 未提交的中间结果 $x=5$；如果 T1 随后 abort（比如转账目标账户不存在），T2 就是”基于一份从未存在的数据做了决策”。
脏读的极端形态（T1 最终回滚）：
t1 W1(x, 50) x = 50（未提交）
t2 T2 读到 x = 50，据此给客户发了 50 元优惠券
t3 abort x 回滚为 100 —— 那个 50 从来没有存在过
异常三：脏写（Dirty Write / 未提交依赖）
$T_2$ 覆盖了 $T_1$ 尚未提交的写；如果 $T_1$ 之后回滚，$T_2$ 的写就建立在错误前提上，而系统往往已经无法恢复（$T_2$ 的旧值信息被覆盖了）。
时刻 T1 数据项 x T2
──── ──────────────────── ───────────── ────────────────────
t1 W1(x, 50) x = 50（未提交）
t2 W2(x, 70) ← 覆盖了未提交的写
t3 abort（回滚） x = ? ← 无法回到 100，因为旧值被 T2 覆盖
t4 commit
所有隔离级别（包括 READ UNCOMMITTED）都禁止脏写——不是因为它破坏隔离性，而是因为它让回滚（undo）本身失去了可能，直接摧毁原子性与持久性。
补充异常：不可重复读（Non-repeatable Read）与幻读（Phantom Read）
- 不可重复读：同一事务内两次读同一个数据项得到不同结果，因为中间有别的事务提交了写。$T_1$ 读 $x=10$，$T_2$ 写 $x=20$ 并提交，$T_1$ 再读 $x$ 得到 20。这是同一行的读-写冲突。
- 幻读（phantom）：同一事务内两次执行同一个范围查询，第二次多出（或少掉）了”行”，因为别的事务插入/删除了满足条件的记录。$T_1$ 执行
SELECT count(*) FROM orders WHERE amount > 100得 5；$T_2$ 插入一条amount=200的订单并提交；$T_1$ 再查得 6。行锁锁不住”还不存在的行”，所以幻读需要谓词锁（predicate lock）或间隙锁（gap lock）（MySQL InnoDB 在 REPEATABLE READ 下用 next-key lock 处理）。
19.2.7 隔离级别（Isolation Levels）
完美隔离（SERIALIZABLE）代价高，于是 SQL 标准定义了一组”阶梯式”的隔离级别，允许应用按需在正确性与并发度之间取舍。现实类比：隔离级别像调节”你能看到别人多少未完成的草稿”——READ UNCOMMITTED 是”别人的草稿纸随便看”，READ COMMITTED 是”只给看已定稿的段落”，REPEATABLE READ 是”你开始读时就给你拍一张照片，之后一直看这张照片”，SERIALIZABLE 是”全图书馆一次只让一个人进来改书”。
| 隔离级别 | 脏读 Dirty Read | 不可重复读 Non-repeatable Read | 幻读 Phantom | 丢失更新 Lost Update |
|---|---|---|---|---|
| READ UNCOMMITTED | 可能 | 可能 | 可能 | 可能 |
| READ COMMITTED | 不可能 | 可能 | 可能 | 可能（标准的 P4 现象；UPDATE t SET x = x+1 这类原地更新因行锁 + 重读而安全，但应用层”先读后算再写”仍会丢失更新） |
| REPEATABLE READ | 不可能 | 不可能 | 可能（标准允许；InnoDB 用间隙锁实际阻止） | 不可能 |
| SERIALIZABLE | 不可能 | 不可能 | 不可能 | 不可能 |
| （任何级别） | 脏写在所有级别都被禁止（否则无法回滚） |
- 注意：这张表出自 SQL-92 标准；标准只定义了前三个”现象”（P1 脏读、P2 不可重复读、P3 幻读），丢失更新（P4）是后来的 Critique of ANSI SQL Isolation Levels（SIGMOD 1995）补充的，并且指出：标准文本本身存在歧义，许多商业数据库的实际行为与”标准答案”并不一致。
- 现实默认值：大多数数据库默认是 READ COMMITTED（PostgreSQL、Oracle、SQL Server）；MySQL InnoDB 默认是 REPEATABLE READ。原因很实际：READ COMMITTED 下读不上锁（配合 MVCC），并发度与吞吐更好，而多数应用实际上不需要可串行化。
- 可串行化快照隔离（Serializable Snapshot Isolation, SSI）：现代方案。它在快照隔离（SI）之上加一层冲突检测：SSI 跟踪读-写依赖（rw-antidependency），一旦发现“危险结构”（两个连续的 rw 依赖构成环）就中止其中一个事务。因为 SI 下所有事务读的是同一时刻的快照，检测可以做得比传统 2PL 更轻量：读不阻塞写、写不阻塞读，只有真正危险的模式才回滚。PostgreSQL 9.1+ 的
SERIALIZABLE就是 SSI。详见 19.2.19。
19.2.8 串行等价（Serial Equivalence）与冲突操作
- 串行历史（Serial History）：事务一个接一个地执行，没有任何交错（每个事务的操作连续成批地发生）。串行历史永远是正确的——它就是”一次只跑一个事务”的定义。
- 串行等价（Serially Equivalent）：一个交错（interleaving）$O$ 是串行等价的，当且仅当存在这些事务的某个串行顺序 $O^{\prime}$，使得
- 对所有对象与所有事务而言，$O$ 的最终结果（服务器对象的值 + 每个读操作返回的值）与 $O^{\prime}$ 相同；
- 且 $O^{\prime}$ 中每个事务的操作是连续成批出现的。
讲义的措辞很精炼：“你无法区分真实操作顺序 $O$ 的结果和那个（虚构的）串行顺序 $O^{\prime}$ 的结果。” 注意条件 1 里的”for all objects and transactions“——不只是服务器上的最终值要对，每个事务读到的值也要对（这一点在写代码验证时会变成关键：只比对最终状态会漏掉不一致检索）。
- 冲突操作（Conflicting Operations）：如果两个操作的联合效果取决于它们的执行顺序，就称它们冲突。讲义给出的清单：
- $read(x)$ 与 $write(x)$ —— 冲突（RW）
- $write(x)$ 与 $read(x)$ —— 冲突（WR）
- $write(x)$ 与 $write(x)$ —— 冲突（WW）
- $read(x)$ 与 $read(x)$ —— 不冲突（交换顺序不改变任何效果）
- $read/write(x)$ 与 $read/write(y)$（不同数据项）—— 不冲突
为什么”冲突”是核心概念：它把”结果是否可能改变”这个语义问题，化归成一个纯语法性质——只看操作类型和数据项名字就能判定，无需知道业务语义。整个并发控制理论都建立在这个化归之上。
- 冲突等价（Conflict Equivalence）：两个历史 $H_1$、$H_2$ 冲突等价，如果它们包含相同的事务和相同的操作，并且每一对冲突操作在两个历史中的先后顺序相同。
冲突可串行化（Conflict Serializable）：历史 $H$ 冲突可串行化，如果 $H$ 冲突等价于某个串行历史。
- 讲义给出的操作化判定流程（不画图也能判）：
- 取出所有冲突操作对，每对含一个来自 $T_1$、一个来自 $T_2$ 的操作；
- 若 $T_1$ 的操作在服务器上先被反映（先执行），把这一对标记为 $(T_1,T_2)$，否则标记为 $(T_2,T_1)$；
- 所有对必须被标记为同一种——全是 $(T_1,T_2)$ 或全是 $(T_2,T_1)$，否则不可串行化。
用这个方法回看 19.2.6 的丢失更新：冲突对 $(R_1(x), W_2(x))$ 标记为 $(T_1,T_2)$，而 $(R_2(x), W_1(x))$ 标记为 $(T_2,T_1)$——标记不一致，判为不可串行化。讲义在每个异常例子旁都写了 “Caught!“，正是这个检查抓出来的。
19.2.9 优先图（Precedence Graph）与串行化定理
- 定义与目的：把”冲突顺序”画成一张有向图，就可把”是否可串行化”变成”图里有没有环”这个线性时间可判的问题。
- 构图规则：
- 节点 = 事务；
- 若事务 $T_i$ 的某个操作与 $T_j$ 的某个操作冲突，且在历史中 $T_i$ 的操作先执行，则画一条有向边 $T_i \to T_j$。
- 机制图解（三个典型历史）：
历史与冲突 优先图 判定
──────────────────────────────────────────────────── ─────────────────── ─────────────────
例 1 H1 = R1(x) W1(x) R2(x) W2(x) T1 ──► T2 无环 ⇒ 冲突可
（串行执行 T1 后 T2） 串行化
等价串行序 T1,T2
例 2 H2 = R1(x) R2(x) W1(x) W2(x) T1 ──► T2 有环 ⇒ 不可
（丢失更新的交错） ▲ │ 串行化
冲突对：R1(x)~W2(x) ⇒ T1→T2 └─────┘ 环 T1→T2→T1
R2(x)~W1(x) ⇒ T2→T1
例 3 H3 = R1(a) W2(a) R2(b) W3(b) R3(c) W1(c) T1 ──► T2 ──► T3 有环 ⇒ 不可
（三条相互冲突的边首尾相接） ▲ │ 串行化
└─────────────┘ 环 T1→T2→T3→T1
例 4 H4 = W1(x) R2(x) W2(y) R3(y) T1 ──► T2 ──► T3 无环 ⇒ 冲突可
（事务首尾相接但不闭环） 串行化，序 T1,T2,T3
- 串行化定理（Serialization Theorem）：历史 $H$ 冲突可串行化 当且仅当它的优先图是无环的（acyclic）。
证明（两个方向都必须证）
（⇐ 充分性） 设 $H$ 的优先图 $G$ 无环。无环有向图必存在拓扑序（topological order）：把节点排成 $T_1, T_2, \ldots, T_n$，使得每条边都从序号小的指向序号大的。构造串行历史 $H_s$：按这个顺序把每个事务的操作连续地执行一遍。现在证明 $H$ 与 $H_s$ 冲突等价。
任取一对在 $H$ 中冲突的操作 $p \in T_i$、$q \in T_j$（$i \neq j$）。由构图规则，$H$ 中 $p$ 先于 $q$ 就等价于图中存在边 $T_i \to T_j$。拓扑序保证 $T_i$ 排在 $T_j$ 之前，于是在 $H_s$ 中 $T_i$ 的所有操作都在 $T_j$ 的所有操作之前，$p$ 仍在 $q$ 之前。每一对冲突操作的相对顺序都被保持 ⇒ $H$ 与 $H_s$ 冲突等价 ⇒ $H$ 冲突可串行化。$\blacksquare$
（⇒ 必要性） 设 $H$ 冲突可串行化，即存在串行历史 $H_s$（事务顺序 $T_{\pi(1)}, \ldots, T_{\pi(n)}$）与 $H$ 冲突等价。假设 $G$ 中存在环 $T_{i_1} \to T_{i_2} \to \cdots \to T_{i_k} \to T_{i_1}$。对每条边 $T_a \to T_b$，由定义存在一对冲突操作，在 $H$ 中 $T_a$ 的操作先执行；冲突等价要求 $H_s$ 中同样是 $T_a$ 先于 $T_b$，即 $T_a$ 必须排在 $T_b$ 之前。把这条要求沿环传递一圈得到：
\[\pi^{-1}(i_1) < \pi^{-1}(i_2) < \cdots < \pi^{-1}(i_k) < \pi^{-1}(i_1)\]这是一个严格不等式回到自身的矛盾。故 $G$ 不可能有环。$\blacksquare$
- 这个定理的价值：
- 它给出了正确性的可判定判据：无环 ⟺ 可串行化；检测环只需 DFS 或 Kahn 拓扑排序，$O(V+E)$，而 $E \le n^2$（$n$ 为并发事务数）。
- 它给出了构造性的等价串行序：拓扑序本身就是一个合法的串行顺序。
- 它成为后面所有算法的证明模板：只要证明”协议产生的历史其优先图必然无环”，就证明了协议保证可串行化。19.2.12 的 2PL、19.2.19 的 OCC、19.2.21 的时间戳排序都是套用这个模板。
19.2.10 视图可串行化（View Serializability）：更宽的标准与它的代价
- 定义：两个历史 $H_1$、$H_2$ 视图等价（view equivalent），如果
- 它们有相同的事务集合与操作集合；
- 对每个读操作 $R_i(x)$，两者中它读取的那个版本由同一个事务写入（或都读初始版本）——即读的来源（read-from）相同；
- 对每个数据项，最后一个写操作来自同一个事务（最终写相同）。
历史 $H$ 视图可串行化，如果它视图等价于某个串行历史。
- 关系：冲突可串行化 $\subsetneq$ 视图可串行化（前者是后者的充分非必要条件）。经典反例只需要一次”盲写”（blind write，不读就写）：
H = R1(x) W2(x) W1(x) W3(x)
· 视图等价视角：T2 的 W2(x) 随后被 T1 的 W1(x) 覆盖，最终写者是 T3，
T1 读到的仍是初始值 —— 与串行历史 T1;T2;T3 完全一致（读来源相同、最终写相同）
⇒ H 视图可串行化 ✔
· 冲突等价视角：冲突对 R1(x)~W2(x) 给出 T1→T2；
冲突对 W2(x)~W1(x) 给出 T2→T1 —— 两条边方向相反，优先图有环
⇒ H 冲突不可串行化 ✘
· 结论：视图可串行化确实比冲突可串行化更宽松
- 为什么实践中不用它：判定视图可串行化是 NP-完全的（直觉上，它要求对”每个读操作到底读了谁的版本”作全局推理，本质上要搜索所有可能的串行顺序）；而判定冲突可串行化只需 $O(V+E)$ 的环检测。因此所有实际系统、以及本课程的全部算法，都以冲突可串行化作为正确性标准。所谓”副作用”是：某些视图可串行化的历史会被保守地拒绝（回滚），这是可接受的安全性代价（拒绝一个安全历史只损失性能，不会出错）。
- 补充说明：Thomas 写规则（19.2.21）正是少数”故意放宽到视图可串行化”的优化——它产生的是视图可串行化（而非冲突可串行化）的历史，这也是它能”忽略一次过时写而不回滚”的原因。
19.2.11 锁与锁相容性（悲观并发控制的基础）
- 定义与目的：悲观（pessimistic）策略的假设是”冲突随时会发生“，因此在事务真正访问对象之前就阻止别人访问——最直接的手段就是锁（lock）。
- 排他锁（Exclusive Lock, X 锁 / 写锁）：每个对象有一把锁，同一时刻至多一个事务能进入(讲义：“Sound familiar? This is Mutual Exclusion!”)。
- 事务 $T$ 在读写对象 $O$ 之前必须调用
lock(O)；若已有别的事务在锁内则阻塞（block）； - 进入锁后 $T$ 可以对 $O$ 反复读写；
- 用完（或到提交点）调用
unlock(O)；若有事务在等待，唤醒其中一个。
- 事务 $T$ 在读写对象 $O$ 之前必须调用
- 读-写锁（Read-Write Locks）：讲义指出”现实负载中有大量只读或读多写少的事务”，而排他锁把并发度压得太低。改进：每把锁有两种模式：
- 共享锁 / 读锁（Shared / Read Lock, S 锁）：多个事务可同时持有（因为 read-read 不是冲突对）；
- 排他锁 / 写锁（Exclusive / Write Lock, X 锁）：独占；
read_lock(O)仅当锁内所有持有者都是通过读模式进入时才允许；write_lock(O)仅当没有任何其他事务持有该锁时才允许；- 锁升级（lock promotion / upgrade）：若 $T$ 已持
read_lock(O)又想写，就调用write_lock(O)把读锁升级为写锁——只有在自己是唯一持有者时才能成功，否则 $T$ 阻塞。
- 锁相容矩阵（Compatibility Matrix）：$\checkmark$ 表示可同时持有，$\times$ 表示冲突（后来的请求必须等待）。
当前持有锁
┌────────┬────────┬────────┐
请求锁 │ S │ X │ 空闲 │
──────────┼────────┼────────┼────────┤
S │ ✓ │ ✗ │ ✓ │ 读-读相容（不冲突）
──────────┼────────┼────────┼────────┤
X │ ✗ │ ✗ │ ✓ │ 写与任何操作都冲突
──────────┴────────┴────────┴────────┘
对应到 19.2.8 的冲突定义：读-读不冲突 ⇒ S-S 相容；
只要有一方是写 ⇒ 冲突 ⇒ 涉及 X 的组合全部不相容。
- 关键假设与系统模型：锁管理器维护锁表（每个对象：当前持有者集合 + 等待队列）。等待通常按 FIFO 排队以避免饥饿。阻塞的事务继续持有它已经拿到的锁——这正是死锁的根源（19.2.14）。
19.2.12 两阶段锁（Two-Phase Locking, 2PL）与它的正确性
- 定义与目的：光有锁还不够——讲义明确指出需要一个额外的纪律才能保证可串行化，它就是两阶段锁：
事务一旦开始释放锁，就再也不能获取（或升级）任何锁。
- 两个阶段：
- 增长阶段（Growing Phase）：只能获取或升级锁，不能释放；
- 收缩阶段（Shrinking Phase）：只能释放锁，不能获取。
锁数量
│ ◆ 锁点（lock point）= 持有全部锁的时刻
│ ／ ＼
│ ／ ＼
│ 增长阶段 ／ ＼ 收缩阶段
│ （只加锁） ／ ＼ （只放锁）
│ ／ ＼
│ ／ ＼
└────────●───────────────────────────●──────────► 时间
事务开始 提交/中止
（严格 2PL：锁一直持到这一刻）
为什么"锁点"是证明的关键：
对任意冲突对，若 Ti 的操作先于 Tj，
则 Ti 必须在 Tj 拿到那把锁之前就已经释放了它
⇒ Ti 的收缩阶段早于 Tj 的增长阶段结束
⇒ lock_point(Ti) < lock_point(Tj)
于是：冲突边 Ti → Tj 一律"从锁点小指向锁点大" ⇒ 图不可能有环 ⇒ 可串行化 ✔
- 定理：2PL 保证冲突可串行化。
证明（讲义版：反证法，两条事实互相矛盾）
设某个 2PL 系统的历史违反了串行等价，那么存在两个事务 $T_1, T_2$，使得冲突对的方向不一致，即：
- (A) 存在对象 $O_1$，$T_1$ 与 $T_2$ 在 $O_1$ 上的冲突操作的时间顺序是 $(T_1, T_2)$；
- (B) 存在对象 $O_2$，$T_2$ 与 $T_1$ 在 $O_2$ 上的冲突操作的时间顺序是 $(T_2, T_1)$。
由 (A)：$T_1$ 先在 $O_1$ 上执行了操作、然后释放了 $O_1$ 的锁，$T_2$ 之后才获得它（因为两者对 $O_1$ 的访问相冲突，锁保证了互斥，所以”先执行”必然意味着”先持锁、先释放”）。记 $s_i$ 为 $T_i$ 进入收缩阶段的时刻，$g_i$ 为 $T_i$ 在增长阶段获得那把锁的时刻。于是
\[s_1 \le \text{释放}(O_1) < \text{获得}(O_1) \le g_2 \le s_2 \quad\Longrightarrow\quad s_1 < s_2\]由 (B) 同理得 $s_2 < s_1$。两者不可能同时成立，矛盾。故 2PL 产生的历史必定串行等价（冲突可串行化）。$\blacksquare$
证明（优先图版：锁点单调 ⇒ 无环）
对每条冲突边 $T_i \to T_j$，用上面的推理可得 $\text{lock\point}(T_i) < \text{lock\_point}(T_j)$，其中锁点定义为事务结束增长阶段（即第一次释放锁）的时刻。假设优先图有环 $T{i_1} \to T_{i_2} \to \cdots \to T_{i_k} \to T_{i_1}$，沿环传递得到
\[\text{lock\_point}(T_{i_1}) < \text{lock\_point}(T_{i_2}) < \cdots < \text{lock\_point}(T_{i_k}) < \text{lock\_point}(T_{i_1})\]严格不等式回到自身，矛盾 ⇒ 无环 ⇒ 由 19.2.9 的串行化定理，历史冲突可串行化。$\blacksquare$
- 一个漂亮的推论：按锁点从早到晚排序，就得到等价的串行顺序。也就是说，2PL 的串行化顺序是由”谁先拿齐锁”决定的，这个顺序在事务执行过程中就固定下来了，不需要事后检测。
19.2.13 2PL 的三种变体：严格、强严格、保守
2PL 只约束”加锁/放锁的次序”，没有约束什么时候放锁。不同的放锁时机带来不同的额外性质：
| 变体 | 纪律 | 获得的额外性质 | 代价 |
|---|---|---|---|
| 基本 2PL | 满足两阶段即可，可以在收缩阶段随时放锁 | 冲突可串行化 | 允许级联回滚：$T_2$ 读了 $T_1$ 未提交的写，$T_1$ 回滚时 $T_2$ 也必须回滚（涟漪效应） |
| 严格 2PL（Strict 2PL） | 所有排他锁（X 锁）一直持有到事务提交/中止 | 无脏读、无级联回滚（可恢复 recoverable + 避免级联中止 ACA）；串行化顺序 = 提交顺序 | 锁持有时间更长，并发度略降 |
| 强严格 2PL（Rigorous 2PL） | 所有锁（含共享锁 S）都持有到提交 | 上述全部性质，且串行序恰好等于提交顺序；实现最简单（放锁就是”提交时清空锁表项”） | 并发度最低（连读锁都不早放），但最安全 |
| 保守 2PL（Conservative 2PL） | 事务开始时一次性申请它需要的全部锁；任何一个拿不到就全部放弃并重启 | 无死锁（不存在”持一部分等另一部分”的循环） | 必须预先知道整个访问集（很多场景做不到）；提前占锁导致并发度低、高峰期大量无谓重启 |
- 实践结论：严格 2PL（乃至强严格 2PL）是实际系统最常用的。原因很实际：级联回滚意味着”一个事务失败会连累一串事务”，这在高并发下会造成回滚风暴；而”锁持到提交”虽然降低了理论并发度，却把恢复逻辑简化到了极致。数据库教科书的经验法则是：在正确性相同的方案里，选恢复最简单的那个。
- 补充说明：讲义只点名了 strict two phase locking: releases locks only at commit point；强严格 2PL 与保守 2PL 是教科书的标准补充分类，用来解释”为什么工程上一律用严格变体”以及”如何用 2PL 彻底消灭死锁”。
19.2.14 死锁：2PL 不能避免死锁
这是 2PL 最重要的一条缺陷：它保证了可串行化，却完全无法避免死锁。讲义用「Downside of Locking – Deadlocks!」小节专门给出了这个例子：$T_1$ 先锁 ABC123 再锁 ABC789，$T_2$ 反过来先锁 ABC789 再锁 ABC123。两边各拿到一半，然后互相等对方手里那一半。
时刻 事务 T1 事务 T2
──── ────────────────────────────────── ──────────────────────────────────
t1 Lock(ABC123) ✔ （等待或做别的事）
t2 Lock(ABC789) ✔
t3 W1(ABC123, 10)
t4 W2(ABC789, 15)
t5 Lock(ABC789) ✗ 阻塞 —— 等 T2 ...
t6 Lock(ABC123) ✗ 阻塞 —— 等 T1
t7 …… 谁也不会释放，永远等待 …… …… 谁也不会释放，永远等待 ……
对应的等待图（Wait-for Graph）——节点是事务，边 $T_i \to T_j$ 表示”$T_i$ 正在等 $T_j$ 持有的锁”：
T1 ──────► T2 T1 等 T2 手里的 ABC789
▲ │
│ │ T2 等 T1 手里的 ABC123
└──────────┘
环 ⇒ 死锁。注意这与"不可串行化"是两回事：
死锁关心的是【活性 Liveness】（永远做不完），
不可串行化关心的是【安全性 Safety】（做完了但结果错）。
死锁发生的三个必要条件（讲义明确强调：必要不等于充分——三个条件都成立不一定真的死锁，但只要发生死锁，三条必然都成立）：
- 有些对象以排他（exclusive）模式被访问——存在互斥；
- 持有锁的事务不可被抢占（no preemption）——拿到的东西不会被强行夺走；
- 等待图中存在循环等待（cycle）。
补充说明（与操作系统课上的 Coffman 条件对照）：经典四条件是”互斥、持有并等待、不可抢占、循环等待”；这里把”互斥 + 持有并等待”压缩成了第 1 条（访问排他对象时，事务会一边持有已得的锁、一边等待新的锁）。理解成同一件事即可。
为什么 2PL 天然会死锁：2PL 只规定”加锁/放锁的相对顺序“，它要求事务在收缩阶段之前必须持有全部所需的锁——这恰恰是”持有并等待”。所以”提高可串行化保证”和”消灭死锁”在 2PL 框架内是两个正交的问题，必须分开解决。下面三节分别对应讲义给出的三条出路。
19.2.15 死锁预防之一：时间戳排序（Wait-Die 与 Wound-Wait）
核心思想：给每个事务在开始时分配一个全局唯一、单调递增的时间戳（timestamp），它代表”事务的年龄”：时间戳越小 = 越老（older）。当发生锁冲突时，用”谁更老”来决定是”等待”还是”回滚”，从而从结构上排除循环等待。这样构造出来的等待关系天然是偏序，图里不可能有环。
- Wait-Die（等待-死亡，非抢占式）：请求者 $T_i$ 想拿 $T_j$ 持有的锁时：
- 若 $T_i$ 更老（$\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$）⇒ 等待（wait）；
- 若 $T_i$ 更年轻 ⇒ 死亡（die）：回滚 $T_i$，并用原来的时间戳重启。
- 口诀：“老的等，年轻的死”。
- Wound-Wait（伤害-等待，抢占式）：请求者 $T_i$ 想拿 $T_j$ 持有的锁时：
- 若 $T_i$ 更老 ⇒ 伤害（wound） $T_j$：强行回滚持有者 $T_j$（$T_j$ 用原时间戳重启），$T_i$ 拿走锁；
- 若 $T_i$ 更年轻 ⇒ 等待（wait）。
- 口诀：“老的伤害年轻的，年轻的等老的”。
同一场景下两种策略的行为对比（$T_1$ 时间戳 10，$T_2$ 时间戳 20，$T_1$ 更老）：
场景：T1 持有 A，T2 持有 B；随后 T2 请求 A、T1 请求 B（若都不处理就是死锁）
┌──────────────────────────── Wait-Die（非抢占） ────────────────────────────┐
│ T2（更年轻）请求 A（T1 持有） → T2 更年轻 ⇒ 【die】回滚 T2，用 TS=20 重启 │
│ T1（更老） 请求 B（T2 持有） → T1 更老 ⇒ 【wait】T1 等待 │
│ 结果：T2 回滚释放 B → T1 拿到 B 继续；T2 重启后再跑。无死锁 ✔ │
│ 代价：年轻事务可能被反复"杀死"（每次重启仍是年轻），但老的终会完成 → 不饥饿 │
└──────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────── Wound-Wait（抢占式） ───────────────────────────┐
│ T2（更年轻）请求 A（T1 持有） → T2 更年轻 ⇒ 【wait】T2 等待 │
│ T1（更老） 请求 B（T2 持有） → T1 更老 ⇒ 【wound】强行回滚 T2，拿走 B │
│ 结果：T2 被伤害并释放锁 → T1 拿到 B 继续；T2 用 TS=20 重启。无死锁 ✔ │
│ 代价：被伤害者已经做的工作白费（回滚），但"伤害"次数通常少于 Wait-Die 的"死亡"） │
└──────────────────────────────────────────────────────────────────────────┘
为什么两者都绝不会死锁（证明）：考察各自产生的等待边 $T_i \to T_j$（$T_i$ 在等 $T_j$）：
- Wait-Die 中，只有更老的事务才会等待，所以每条等待边满足 $\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$——严格递增；
- Wound-Wait 中，只有更年轻的事务才会等待，所以每条等待边满足 $\mathrm{TS}(T_i) > \mathrm{TS}(T_j)$——严格递减。
两种情况下，”时间戳沿等待边严格单调”都成立。若等待图存在环 $T_{i_1} \to \cdots \to T_{i_k} \to T_{i_1}$，沿环传递会得到 $\mathrm{TS}(T_{i_1}) < \mathrm{TS}(T_{i_1})$（或 $>$），严格不等式回到自身，矛盾。故等待图无环 ⇒ 无死锁。$\blacksquare$
为什么 Wait-Die 不会饿死（starvation-free）：一个年轻事务 $Y$ 被回滚的唯一原因是”它请求了某个更老事务持有的锁”；而时间戳在开始时分配，所以在 $Y$ 启动之后再也不会出现比它更老的事务——能杀死 $Y$ 的只有那批有限个”启动更早”的事务，而它们每一个最终都会完成（老事务只等待年轻事务，年轻事务要么做完、要么被杀死后释放全部锁，老事务的等待因此总会被解除）。于是 $Y$ 至多被杀死有限次，最终必然成功。关键前提是：重启时沿用原时间戳，这样”$Y$ 永远是年轻的”这个事实不会因为重启而改变。反之，若重启时分配新时间戳，就可能出现”不断被更老的事务杀死”的活锁。
- 时间戳的另一种死锁预防用法——超时（Timeout）：拿不到锁就等一段固定时间，超时未获得就 abort 并重试。
- 优点：实现极简，不需要任何全局信息，在分布式系统中尤其常见（无法高效维护全局等待图时这是默认选择）。
- 缺点：可能误杀——一个只是执行得慢的长事务会被误判为死锁而回滚；超时时间难以调参（太短误杀多、太长真死锁拖久了才被发现）。
19.2.16 死锁避免与死锁检测/恢复
讲义给出的”combating deadlocks”三条路径如下（结合三种必要条件的逐一破坏）：
| 策略 | 具体做法 | 破坏了哪个必要条件 | 评价 |
|---|---|---|---|
| 死锁预防（Prevention） | ① 允许对对象做只读访问（用 S 锁代替 X 锁）；② 允许抢占（Wait-Die/Wound-Wait 回滚某个事务）；③ 一次性申请全部锁（保守 2PL，失败就整体放弃） | ① 互斥范围、② 不可抢占、③ 循环等待 | 从源头杜绝，但并发度下降、需要预知访问集；时间戳与超时属于此类 |
| 死锁避免（Avoidance） | 运行时检查”如果这次加锁会形成环就不加”（等价于维护等待图并只在无环时放行）；保守 2PL 也算 | 循环等待 | 不会真的出现死锁，但每次加锁都要做一次全局判断，开销大 |
| 死锁检测与恢复（Detection & Recovery） | 允许死锁发生：维护等待图，周期性地检测环；发现环就 abort 一个或多个事务来破环 | ——（事后处理） | 并发度最高、最通用；代价是检测开销 + 牺牲者的重做浪费；分布式下有”幻死锁”问题 |
死锁检测与恢复的具体步骤（讲义原文的流程，并补足实现细节）：
- 维护等待图（Wait-For Graph, WFG）：节点 = 事务，边 $T_i \to T_j$ 表示”$T_i$ 在等 $T_j$ 持有的锁”。可以在事务阻塞时增量添加边、获得锁或回滚时删除边——增量维护是 $O(1)$ 的，比重建快得多。
- 周期性地找环：用 DFS（记录灰色节点，遇到灰色节点即发现环，还可回溯出环上的路径）或 Kahn 拓扑排序（若排序结果不足 $n$ 个节点则有环）。复杂度 $O(V+E)$。
- 选牺牲者（victim）并回滚，打破环。讲义强调”abort one or more transactions”——环上回滚一个就够（环被断掉），但如果多个环共享节点，可能一次要回滚多个。
- 回滚后：释放牺牲者的全部锁、撤销其写（undo），并决定它是否重启（通常重启，但要避免它再次成为牺牲者）。
牺牲者选择（victim selection）的常见启发式（必须防止”同一个倒霉事务被反复选中”造成饥饿）：
| 启发式 | 理由 |
|---|---|
| 已做工作量最少的事务（rollback cost 最小） | 回滚浪费最小 |
| 持有锁最少的事务 | 释放的锁少 → 需要重做的等待者少，破环代价小 |
| 最年轻的事务（时间戳最大） | 它本来就应该排后面，回滚它符合时间戳序，且老事务优先完成 |
| 已回滚次数最少的事务 | 直接防止饥饿：rollback_count 高的事务优先级提升（类似于老化 aging） |
- 检测频率的权衡：检测太频繁 ⇒ 大量 CPU 花在遍历等待图上；检测太稀疏 ⇒ 死锁存在很久才被发现，期间所有相关事务都白等。工程经验：以”事务平均执行时间”的量级为周期，或当”最近一段时间没有事务成功提交”时触发一次检测。
19.2.17 分布式死锁检测（重点）
当数据分散在多个站点上，一个事务的锁可能横跨若干站点，任何一个站点都看不到完整的等待图。三个层次的方案如下。
（1）集中式检测（Centralized）
- 选一个中心死锁检测器（central coordinator）；每个站点把自己的局部 WFG 变化上报给它，中心拼出全局 WFG 后检测环。
- 优点：算法简单，环检测就是单机 DFS。
- 缺点：单点故障（中心挂了就没人检测）、通信瓶颈（所有等待边变化都要上报）、延迟高（要等路径信息汇聚）。讲义特别提到：”keep track of Wait-for graph (e.g., via Global Snapshot algorithm)”——即用 Chandy-Lamport 之类的算法取得一致性的全局快照来构造 WFG。
（2）分层检测（Hierarchical）
- 把站点组织成树状：叶子检测器负责一小簇站点，把”出口边”（跨簇的等待边）汇总给上一层检测器；上层再汇总。
- 优点：分摊了中心节点的负载，可扩展到较大规模。
- 缺点：层次结构需要维护；跨层环的检测有额外延迟；树根仍可能是瓶颈。
（3）分布式检测：Chandy-Misra-Haas 的边追踪（Edge Chasing）算法
- 不做全局快照，而是把探测消息（probe）沿等待边推送：只有当一条等待路径真的绕回起点时，才说明有环。细节与伪代码见 算法 19.3.4。
- 基本规则（$T_i$ 发起，探测消息记作 $\text{probe}(i, j, k)$：发起者 $i$，发送者 $j$，目标 $k$）：
- 当 $T_i$ 开始等待 $T_j$ 时，向 $T_j$ 所在站点发送 $\text{probe}(i, i, j)$；
- 站点收到 $\text{probe}(i, j, k)$：若 $k = i$（探测回到了发起者）⇒ 检测到死锁；否则若 $k$ 正在等待某些事务，则对每个 $k$ 等待的 $m$ 转发 $\text{probe}(i, k, m)$；若 $k$ 不在等待任何事务，则丢弃该探测（这条分支无环）；
- 优化——消息合并/抑制（message suppression）：站点记录已经转发过的 $(i, j, k)$，同一探测只转发一次；更激进的做法是”同一发起者 $i$ 的探测，若该站点已经转发过，则后续同类探测直接丢弃”。
- Obermarck 算法：另一条分布式路线，不用探测消息，而是在局部 WFG 之间传递路径信息（把各站点的局部等待图连同”外部等待”的出口点一起交换），据此在本地推导出全局环。相比边追踪，它把开销放在”路径信息的传播”上而不是”探测消息的洪流”上。
难点的核心：幻死锁（Phantom Deadlock）
定义：分布式检测器报出了一个全局并不存在的环。原因是——检测所依据的等待信息来自不同时刻，在信息传播的过程中，环上的某个事务已经提交或中止，环早已被打断，但”在途的探测消息”仍会绕回起点。
真实的环：T1 等 T2 等 T3 等 T1（三个事务分布在三个站点上）
站点0: T1 ──► T2 ──► T3 ──► T1
│ │ │ ▲
① 发探测(1,1,2) │ │ │
│ │ │ │
② site1 收到后转发 (1,2,3) │
│ │ │ │
③ site2 收到后转发 (1,3,1) ──┘
│
④ ★ 在这条探测消息到达 site0 之前，T2 因超时/其他原因【中止并释放全部锁】★
│ ⇒ 真实的等待边 T1→T2 断开了，全局只剩 T3→T1（无环）
│
⑤ site0 仍收到 (1,3,1)：k = i = 1 ⇒ "探测回来了！检测到死锁！"
⇒ 报出了一个【已经不存在的死锁】= 幻死锁 ✗
- 为什么它无法根除：在异步系统里，”环曾经存在过，但现在已经不存在”这件事无法仅靠收到的消息判断——因为消息只会告诉你”过去某个时刻存在这条边”，不会告诉你”它现在还成立”。这与快照一章的结论一致：没有任何一致性信息的分布式判定都会误报。
- 缓解手段：
- 用一致性全局快照（Chandy-Lamport 算法）拿到一个因果一致的等待图快照再检测——快照保证所有”边”来自同一个一致割（consistent cut），环在快照意义下是”真的存在过”的。这也解释了讲义为什么写 “keep track of Wait-for graph (e.g., via Global Snapshot algorithm)”。注意：即使如此，”存在过”仍不等于”现在仍存在”，幻死锁只能减少、不能彻底消除。
- 给探测消息带时间戳/事务状态：收到探测时校验目标事务是否仍处于等待状态（本例中 site0 可以在报死锁前先问一句”T1 还在等吗？T2 还在等吗？”），把误报率压低，但引入额外往返与新的竞态。
- 接受误报：牺牲者被回滚本来就是”可能白回滚”的，只要回滚是安全的（能正确 undo），误报只损失性能不破坏正确性。因此许多系统选择”允许幻死锁 + 让牺牲者重试”。
19.2.18 多粒度锁（Multi-granularity Locking）
- 定义与目的：数据是层次化的（数据库 → 表 → 页 → 行）。如果只在”行”上加锁，一个要扫描整张表的事务就得申请几百万把行锁（锁表爆炸、检查锁也要百万次）；如果只在”表”上加锁，两个只改不同行的事务又会互相阻塞（并发度暴跌）。多粒度锁让事务按需选择合适的粒度，并用意图锁（Intention Lock）解决”在不同层级上加锁如何互相检查”的问题。
数据库 DB
／ │ ＼
表 A 表 B 表 C
／ │ ＼ │
页1 页2 页3 页4
／│＼
行1 行2 行3
加锁规则（"从根往下、层层标记"）：
想读某个【行】 ⇒ 在 DB、表、页 上加 【IS】，在该行上加 【S】
想写某个【行】 ⇒ 在 DB、表、页 上加 【IX】，在该行上加 【X】
想读【整张表但可能要改其中几行】 ⇒ 在 DB 上加 IX，在表上加 【SIX】
想读/写【整张表】⇒ 在 DB 上加 IX/S，在表上加 X/S
- 三种意图锁的含义：
- IS（Intention Shared）：我打算在更低层级加共享锁（即我要读下面某些节点）；
- IX（Intention Exclusive）：我打算在更低层级加排他锁（即我要写下面某些节点）；
- SIX（Shared + Intention Exclusive）：我正在共享地读整个节点（相当于 S），同时打算修改它的某些下级（相当于 IX）。
- 完整锁相容矩阵（行 = 请求的锁，列 = 已持有的锁；$\checkmark$ = 相容可授予，$\times$ = 冲突需等待）：
请求 \ 已持有 │ NL │ IS │ IX │ S │ SIX │ X
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
NL │ ✓ │ ✓ │ ✓ │ ✓ │ ✓ │ ✓
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
IS │ ✓ │ ✓ │ ✓ │ ✓ │ ✓ │ ✗
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
IX │ ✓ │ ✓ │ ✓ │ ✗ │ ✗ │ ✗
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
S │ ✓ │ ✓ │ ✗ │ ✓ │ ✗ │ ✗
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
SIX │ ✓ │ ✓ │ ✗ │ ✗ │ ✗ │ ✗
─────────────┼───────┼───────┼───────┼───────┼───────┼───────
X │ ✓ │ ✗ │ ✗ │ ✗ │ ✗ │ ✗
─────────────┴───────┴───────┴───────┴───────┴───────┴───────
NL = 未加锁（No Lock）。读法与 19.2.11 的 S/X 矩阵一致：
IS 与 IS/IX 都相容（两人可以分别读、写不同的下级行）；
S 与 IX 不相容（有人要读整张表，就没人能改里面任何一行）。
- 为什么需要意图锁（关键收益）：假设没有意图锁。事务 $T$ 想给表 A 加 X 锁，它必须确认”当前没有任何事务持有表 A 中任何一行的锁”——这要求扫描全表所有行的锁记录，代价与表大小成正比。有了意图锁，$T$ 只需检查表 A 这一个节点上的锁：只要上面没有 S/IS/IX/SIX 等任何锁（即矩阵中所有含意图锁的组合都冲突），就说明没有人在动它的下级，可以放心授予表级 X 锁。代价是”向上多标记一层”，收益是”检查只需看一个节点”——这正是层次化锁协议的精髓：用 $O(\text{深度})$ 的额外标记，换取 $O(1)$ 的冲突检查。
- 锁升级（Lock Escalation）：当事务在同一个节点下积累了太多细粒度锁（例如对某表加了 5000 把行锁），锁管理器的内存与检查开销会变得不可接受。此时把它升级成一把粗粒度锁（例如把这 5000 把行锁换成该表的 1 把 X 锁）：
- 触发条件：单事务持有的行锁数超过阈值（SQL Server 默认约 5000）。
- 收益：锁表空间与检查次数大幅下降。
- 代价：阻塞范围扩大——原本只想改几行，现在把整张表锁住了，别的行级事务全被挡住，并发度骤降；极端情况下还可能人为制造死锁（升级请求与别人的细粒度锁互相等待）。
- 因此工程上要谨慎：要么设较高的阈值，要么避免让大事务在热点表上做全表更新。
19.2.19 乐观并发控制（Optimistic Concurrency Control, OCC）
- 动机：悲观锁的一切开销（加锁/解锁的系统调用、锁表维护、阻塞与唤醒、死锁检测与牺牲者回滚）在冲突很少的负载下全是浪费——花了大力气去预防几乎不会发生的事故。OCC 反过来假设”冲突是罕见的“：
读的时候不上锁，写的时候先写在私有工作区，等到提交时再验证这次执行是否与别人冲突；不冲突就提交，冲突就回滚重来。
- 讲义的两条动机描述：“Increases concurrency more than pessimistic concurrency control”、“Preferable than pessimistic when conflicts are expected to be rare — but still need to ensure conflicts are caught!”（必须仍然保证冲突能被抓到，否则就不是并发控制，而只是”没有控制”）。
Kung-Robinson 三阶段（Three Phases）
事务 Ti 的 OCC 生命周期
─────────────────────────────────────────────────────────────────────────
① 读阶段 Read Phase ② 验证阶段 Validation ③ 写阶段 Write Phase
┌───────────────────────┐ ┌──────────────────┐ ┌──────────────────┐
│ 读数据库已提交版本 │ │ 拿 Ti 的读集/写集 │ │ 把私有工作区 │
│ 所有修改只写进【私有 │──►│ 与所有更早的并发 │──►│ 原子地安装到数据库 │
│ 工作区】,不动数据库 │ │ 事务比对 │ │ （需要短暂的锁/临界区）│
│ 记录 读集 RS / 写集 WS │ │ 冲突 ⇒ 回滚重来 │ │ 完成 → 提交 │
└───────────────────────┘ └──────────────────┘ └──────────────────┘
↑ 无锁、不阻塞别人 ↑ 唯一的串行点：验证必须互斥地做
验证窗口（Validation Window）：判断"谁与谁重叠"靠的是三个时间点
Tj 开始读 ──────── Tj 结束读 ── Tj 验证并写 ────►
│ ← 重叠区间 → │
Ti 开始读 ─────────────── Ti 结束读 ─ Ti 验证并写 ──►
· Ti 与 Tj 重叠 ⇒ 必须检查它们的读写集是否相交（条件 2、条件 3）
· Tj 完全在 Ti 开始之前结束 ⇒ 天然有序，无需检查（条件 1）
- 验证规则（三种经典条件）：设 $T_j$ 排在 $T_i$ 之前（$\mathrm{TS}(T_j) < \mathrm{TS}(T_i)$，即 $T_j$ 先通过验证），则需要满足下列之一：
- 条件 1：$T_j$ 在 $T_i$ 开始之前就完成了 ⇒ 两者不重叠，所有冲突操作天然按 $T_j$ 在前排列，无需检查。
- 条件 2：$T_j$ 在 $T_i$ 开始前开始，但在 $T_i$ 完成前完成（两者重叠，且 $T_j$ 的写阶段在 $T_i$ 的读阶段之后）⇒ 此时 $T_i$ 不可能读到 $T_j$ 的过时值，唯一需要担心的是”两者都写同一数据项”造成的覆盖顺序颠倒 ⇒ 检查 $WS(T_i) \cap WS(T_j) = \varnothing$。
- 条件 3：其余的重叠情形（尤其 $T_j$ 的写阶段落在 $T_i$ 的读阶段之内）⇒ $T_i$ 可能读到 $T_j$ 覆盖前的过时值，也可能与 $T_j$ 争抢同一个数据项的写权 ⇒ 必须做强检查： \(WS(T_j) \cap \big(RS(T_i) \cup WS(T_i)\big) = \varnothing\)
- 补充说明（一个真实存在的实现陷阱）：教科书上条件 2/3 的划分依赖于”事务的时间戳在进入验证阶段时分配“这一约定。若时间戳在事务开始时分配、验证却发生在读阶段结束后，就可能出现”$T_j$ 的写阶段落在 $T_i$ 的读阶段内部”的情形——此时若按条件 2 只检查写-写，就会漏掉 $T_i$ 读到过时值的情况，破坏可串行性。安全的判据是：只要 $T_j$ 的提交（写阶段）落在 $T_i$ 的读区间 $[start_i, end_i]$ 之内，就必须用条件 3 的强检查。本讲 19.4.1 的代码就是这样实现的（把时间戳分配在验证阶段，并对”写阶段落在我的读区间内”的情况强制强检查）。
- 验证的正确性（结论，完整证明见算法 19.3.5）：若所有事务都通过验证，则任何一对冲突操作的实际执行顺序都与”验证顺序（时间戳顺序）”一致，因此整个已提交历史冲突等价于按验证顺序串行执行的历史 ⇒ 可串行化。
失败处理：验证失败 ⇒ 回滚该事务（丢弃私有工作区）并重新开始。讲义特别提醒了基本做法的副作用：“An abort may result in other transactions that read dirty data, also being aborted” ⇒ 级联回滚（cascading aborts）。缓解办法：读阶段永远只读已提交版本（本讲的实现如此），或者把验证推迟到”所有可能读到它的读都已验证”之后（这就是 MVCC + SSI 的思路）。
- OCC 的优缺点
| 维度 | 表现 |
|---|---|
| 优点 | 无锁开销（读路径完全不加锁）、无死锁（不做持有并等待）、读不阻塞、写不阻塞、低冲突时吞吐与延迟都极佳 |
| 缺点 | 高冲突时性能崩溃：验证失败 ⇒ 大量回滚 + 重做，白烧 CPU（实验里 OCC 的回滚次数随冲突率急剧上升，见 19.4.1 场景 D）；需要为每个事务维护私有工作区 + 读集/写集的内存；写阶段仍需短暂加锁（保证安装是原子的） |
| 适合场景 | 冲突率低、事务短、读多写少或写集不相交的负载；内存数据库（无磁盘 I/O，冲突窗口短） |
- 真实系统：
- 内存数据库 H-Store / VoltDB：所有数据在内存里，事务执行极快，OCC/确定性执行能发挥最大优势。
- Google Percolator（Bigtable 上的增量索引更新）：用 OCC + 2PC + 全局时间戳实现跨行事务，是大规模 OCC 的经典工业实现。
- PostgreSQL 的 SSI：在快照隔离之上做可串行化验证（本质是”基于快照的乐观验证”）。
- Redis 的
WATCH/MULTI/EXEC：最朴素的乐观锁——WATCH记住版本，EXEC时若被监视的键被改过就整体放弃，由客户端重试。 - 讲义提到的非事务系统：Cassandra / DynamoDB 的”最后写入获胜（LWW）”、Riak 的向量时钟冲突检测，讲义把它们归类为”乐观并发控制在键值存储中的变体“——因为没有事务，验证退化成”写时比时间戳”或”读时发现兄弟版本（siblings）”。
19.2.20 时间戳排序（Timestamp Ordering, TO）
核心思想：既然”可串行化”意味着”等价于某个串行顺序”，那就事先给每个事务定好它在这个串行顺序里的位置——在事务开始时分配一个全局唯一的时间戳 $\mathrm{TS}(T)$；然后强制所有操作按时间戳顺序执行：如果某个操作会违反时间戳顺序，就回滚事务。根本不用锁，因此也就没有死锁。
- 讲义给出的两条规则（原文逐字翻译）：
- $T$ 对对象 $O$ 的写，只有当所有读过或写过 $O$ 的事务的 id 都小于 $T$ 的 id 时才被允许；
- $T$ 对对象 $O$ 的读，只有当$O$ 最后一次是由 id 小于 $T$ 的事务写的时才被允许。 实现方式：为每个对象维护 read timestamp 与 write timestamp；规则被违反就 abort。
- 精确的操作规则（含伪代码级细节）：每个数据项 $x$ 维护两个值——$\mathrm{read\_TS}(x)$（读过 $x$ 的最大事务时间戳）与 $\mathrm{write\_TS}(x)$（写过 $x$ 的最大事务时间戳，指已提交的写）。
事务 T 读 x：
若 TS(T) < write_TS(x) ⇒ 拒绝：已有更年轻的事务写过 x，
T 若继续读就会读到【过时值】 ⇒ 回滚 T
否则 ⇒ 执行读；read_TS(x) ← max(read_TS(x), TS(T))
（把 x 的读时间戳推高到 T，用来阻止更老的事务以后写 x）
事务 T 写 x（基本 TO）：
若 TS(T) < read_TS(x) ⇒ 拒绝：已有更年轻的事务读过 x，
T 的写会让那次读"读了个寂寞"（不可重复读）⇒ 回滚 T
若 TS(T) < write_TS(x) ⇒ 拒绝：过时写（stale write），
顺序上 T 的写应当发生在那次写之前 ⇒ 回滚 T
否则 ⇒ 执行写；write_TS(x) ← TS(T)
严格 TO 的等待规则：为了让”读到的值”与”时间戳序”严格一致，工程实现（严格时间戳排序, Strict TO）通常规定：任何读写操作都必须等到所有时间戳更小、且写过该数据项的事务结束（提交或中止）之后才能执行。这带来一个非常漂亮的推论：等待只发生在”年轻者等年老者”的方向上（$\mathrm{TS}(T_{\text{waiter}}) > \mathrm{TS}(T_{\text{holder}})$），沿等待边时间戳严格递减 ⇒ 等待图不可能有环 ⇒ TO 无死锁（与 19.2.15 的证明完全同构）。本讲 19.4.1 的代码实现的就是这个版本。
正确性论证（直觉版，完整证明见算法 19.3.6）：把已提交事务按时间戳从小到大排序，声称这就是等价的串行顺序。任取一对冲突操作：若两者来自同一事务，事务内部顺序天然正确；若来自不同事务 $T_a, T_b$ 且 $\mathrm{TS}(T_a) < \mathrm{TS}(T_b)$，则读规则保证 $T_b$ 不会读到 $T_a$ 写之前的旧版本，写规则保证 $T_b$ 的写不会排到 $T_a$ 的前面（否则 $T_b$ 的请求会被拒绝）。因此所有冲突对的顺序都与时间戳顺序一致 ⇒ 历史冲突等价于按时间戳的串行历史 ⇒ 可串行化。$\blacksquare$
优点与缺点
| 维度 | 说明 |
|---|---|
| 优点 | 无死锁（不加锁、不循环等待）；不需要锁管理器；冲突判定是 $O(1)$ 的本地比较；天然给出一个全局一致的串行顺序（对分布式系统很友好——时间戳可以全局分配） |
| 缺点① | 可能饥饿（starvation）：一个老事务的写请求可能被一连串更年轻的事务的读请求反复”顶掉”（$\mathrm{TS}(T) < \mathrm{read\_TS}(x)$ 会一直成立），于是被反复回滚。本讲代码实验里可以看到：如果回滚后沿用原时间戳，系统会陷入活锁（几百次回滚仍无法收敛）；实践中通常改为回滚后重新分配一个更大的时间戳来打破僵局 |
| 缺点② | 级联回滚风险：基本 TO 若不等待未提交的写，就可能让 $T_b$ 读到 $T_a$ 未提交的写；$T_a$ 一旦回滚，$T_b$ 也必须回滚。严格 TO 通过在”未提交写者”上阻塞读来消除它 |
| 缺点③ | 不适合长事务：长事务持有老时间戳，任何年轻事务的读都会把 $\mathrm{read\_TS}$ 推高，从而把长事务的写全部判为非法——长事务被回滚的概率随时间线性上升 |
- 两个重要变体：
- 严格时间戳排序（Strict TO）：推迟读写直到”所有更早的事务”都完成。它保证可恢复性（recoverability）与无级联回滚，代价是引入等待（但等待方向单调 ⇒ 仍无死锁）。它对标的是 2PL 里的”严格 2PL”。
- Thomas 写规则（Thomas’ Write Rule）——一个极其实用的优化：当 $\mathrm{TS}(T) < \mathrm{write\_TS}(x)$ 时，不要回滚 $T$，而是直接忽略（ignore）这次写。 为什么可以这样做：条件是 $\mathrm{TS}(T) < \mathrm{write\_TS}(x)$，说明已经有一个更年轻的版本存在。此后任何对 $x$ 的读，其时间戳必须 $> \mathrm{write\_TS}(x) > \mathrm{TS}(T)$（否则会被读规则拒绝），因此没有任何事务可能读到 $T$ 写的这个版本；而在此之前发生的读也早已完成、与这次写无关。既然这个版本永远不会被读到，删掉它不改变任何”读的来源（read-from）”，也不改变最终写 ⇒ 历史仍然是视图可串行化的。 注意这个措辞：Thomas 规则产生的是视图可串行化（比冲突可串行化宽松），这正是它敢”不回滚”的底气。它的收益很直接：大量本来会引发回滚的过时写变成了一次安静的丢弃，在高冲突负载下显著降低回滚率。
- 补充说明（与键值存储的联系）：讲义最后把线索接到了”最终一致性”上——Cassandra / DynamoDB 用物理时钟时间戳 + 最后写入获胜（LWW）来定序，Riak 用向量时钟判断”新写是否因果更新”还是”并发冲突（siblings）”。这些正是时间戳排序在无事务系统中的退化形态：没有事务边界、没有回滚，只有”谁的时间戳大谁赢”。它们的代价是把冲突解决推给了应用，且依赖时钟同步（时钟不同步时，靠得近的两次写可能出现”更旧的写反而赢了”）。详见 NoSQL 一章。
19.2.21 多版本并发控制（MVCC）与快照隔离
- 定义与目的：多版本并发控制（Multi-Version Concurrency Control, MVCC）为每个数据项保留多个版本（每个版本带时间戳或事务 id）。读操作不去争抢当前值，而是读一个快照版本；写操作新建一个版本而不覆盖旧版本。核心收益一句话：
读不阻塞写、写不阻塞读（readers never block writers, writers never block readers）。 讲义的说法是”为每个对象维护 per-transaction 的版本，标记为临时的（tentative）版本，另有一个已提交版本；读或写时找出’正确的’那个 tentative 版本——’正确’的依据是事务 id，目标是让事务只读紧邻前一个事务写的版本”。
数据项 x 的版本链（version chain，按时间戳从旧到新）
[x = 100, ts=50] ──► [x = 80, ts=120] ──► [x = 70, ts=200] ──► (未提交: x=60, T9)
读事务 R（快照 ts=150）
│
└──► 沿链找到"最大的 ts ≤ 150"的那一版 = [x = 80, ts=120] ⇒ 读 80
完全不需要加锁，也不会被 T9 的写阻塞 ✔
写事务 W9（ts=200）
│
└──► 追加一个新版本 [x = 60, T9]（先标记为未提交）⇒ 不覆盖 ts=120 的旧版本
旧版本仍然活着 ⇒ 正在进行的读者继续读旧版本，不会被阻塞 ✔
冲突只剩下一类：【写-写冲突】——两个事务同时想写 x。
· first-updater-wins：写的时候就要拿到 x 的写锁/版本锁，谁先写谁赢，
后到者等锁或直接 abort；
· first-committer-wins：写的时候各写各的私有版本，提交时发现
"我基于的快照之后有人已经提交了对 x 的写" ⇒ abort 我自己（即快照隔离的实现方式）
- MVCC 如何”解决”读-写冲突：读-写冲突的本质是”读的人想看到一个稳定值，写的人想改它”。单版本系统只能用锁强制排队；多版本系统让读者留在旧版本上、写者去建新版本，两者物理上不碰面。这就是 MVCC 能让 PostgreSQL/InnoDB 在 READ COMMITTED 下做到”读完全不加锁”的原因。
- 但写-写冲突仍然存在，且必须显式处理（否则会有脏写、丢失更新），于是产生了两种经典策略：
| 策略 | 时机 | 行为 | 代表 |
|---|---|---|---|
| first-updater-wins（先更新者赢） | 写的时候 | 写前先”预约”该数据项的写权（加写锁）；拿不到就等待或 abort | 多数 MVCC 数据库的写路径 |
| first-committer-wins（先提交者赢） | 提交的时候 | 提交时检查”我读快照之后，我写过的数据项是否已被别人提交过写”；是则 abort | 快照隔离（SI） |
- 快照隔离（Snapshot Isolation, SI）：SI 的定义有两条：
- 每个事务读自己开始时的一个一致快照（该快照包含当时所有已提交事务的写）——避免了不可重复读与幻读；
- 写-写冲突用 first-committer-wins 解决：若事务 $T$ 要写的某个数据项在 $T$ 的快照之后已被别的已提交事务写过，则 $T$ 回滚。 SI 广泛存在于 Oracle、SQL Server、PostgreSQL、MySQL InnoDB（
REPEATABLE READ的实现），因为它既避免了大部分异常，又几乎不阻塞。
- SI 不是可串行化的！——写偏斜（Write Skew）
经典例子：医生值班。约束是”任何时刻至少有一名医生在值班“。当前 Alice 和 Bob 都在值班。两人同时想请假，各自执行同一个事务：
T_Alice: SELECT count(*) FROM on_call WHERE shift = 'A' AND on_call = true; -- 读到 2
if count > 1: UPDATE on_call SET on_call = false WHERE name = 'Alice';
T_Bob : SELECT count(*) FROM on_call WHERE shift = 'A' AND on_call = true; -- 也读到 2
if count > 1: UPDATE on_call SET on_call = false WHERE name = 'Bob';
在 SI 下：两个事务读的是同一个快照（都看到 2，满足 count > 1 的条件），
写的是【不同的行】（Alice 改 Alice 行，Bob 改 Bob 行）⇒ 没有写-写冲突
⇒ 两者都成功提交 ⇒ 结果是【没有人在值班】—— 约束被破坏 ✘
为什么 SI 抓不到它：这个异常依赖的是读-写冲突（rw-antidependency）——$T_{Alice}$ 读了 $T_{Bob}$ 将要修改的数据的”旧版本”。SI 只检测写-写冲突，对读写冲突视而不见，因此这类”两个事务各自读同一条件、各自写不同行、合起来违反约束”的模式会漏过去。这也解释了为什么”银行转账”这类异常 SI 能防（因为转账的两条写会碰撞）、而”医生值班”这类异常 SI 防不住（写集不相交）。
- 可串行化快照隔离（SSI）：在 SI 基础上额外跟踪读-写依赖，一旦检测到危险结构（两个连续的 rw 依赖 $T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_3$，且 $T_1, T_3$ 之间有写依赖或并发关系），就中止其中一个事务。它保留了 SI 的”读不阻塞写”，只在真正危险的少数情形下回滚。PostgreSQL 9.1+ 的
SERIALIZABLE就是 SSI。 - MVCC 的代价：
- 空间开销：多版本长期存活会占用大量存储（PostgreSQL 的”表膨胀 table bloat”是著名运维问题）；
- 垃圾回收（vacuum / purge）：必须回收”不再有任何活跃快照可能读到”的旧版本——回收太早会破坏快照一致性，太晚则空间失控；
- 实现复杂度：版本链的可见性判断（哪一版对本事务可见）是每个读操作的额外开销；索引也要版本化（或额外回表判断可见性）；
- 写偏斜不是唯一盲区：SI 还允许”只读事务异常（read-only anomaly）”等更加微妙的问题，这也是 SSI 存在的原因。
- 真实系统一览：PostgreSQL（MVCC + SSI 做 SERIALIZABLE）、MySQL InnoDB（MVCC + next-key lock 做 REPEATABLE READ）、Oracle（MVCC + 回滚段）、SQL Server（
READ_COMMITTED_SNAPSHOT行版本）、Spanner（MVCC + 悲观锁 + TrueTime 时间戳）、CockroachDB（MVCC + 串行化验证）。可见 MVCC 是”存储层”的普适技术，各家差别主要在于冲突检测策略与时间戳来源。
19.3 算法伪代码与正确性分析
本节给出六份伪代码。为便于书写，统一约定：
- 记号 $R_i(x)$/$W_i(x)$ 表示事务 $T_i$ 读/写数据项 $x$；$\mathrm{TS}(T)$ 为事务时间戳（越小越老）；$RS(T)$、$WS(T)$ 为读集与写集。
- 事务状态：
ready（可推进）、blocked（在等锁/等更早的写者）、committed、aborted。 - 共同的正确性判据：只要证明”协议产生的历史其优先图无环”，就由 19.2.9 的串行化定理得到可串行化。下面每个证明都套用这个模板。
算法 19.3.1：严格两阶段锁（Strict Two-Phase Locking）
假设与系统模型
- 单机（单锁管理器）或”锁管理器可被所有事务原子访问”；事务之间异步并发。
- 故障模型：crash-stop + 崩溃恢复（崩溃后重启，用 WAL 撤销未提交事务、重做已提交事务）。协议本身不处理崩溃，恢复由日志负责。
- 通道：本地调用，可靠（加锁请求不会丢失）；
lock调用返回 granted / blocked，不阻塞调用线程。 - 事务数 $n$ 任意；每个事务的访问集在运行前未知（与保守 2PL 的区别）。
伪代码
# 锁管理器（Lock Manager）
state:
holders[item] : map item -> map(tid -> mode) # 当前持有者及模式 ('S'/'X')
queue[item] : FIFO list of (tid, mode) # 只按 FIFO 排队，防止饥饿
upon request_lock(item, tid, mode):
if holders[item][tid] == 'X' or (holders[item][tid]=='S' and mode=='S'):
return GRANTED # 重入 / 已持更强锁
if (tid, mode) not in queue[item]: queue[item].append((tid, mode))
if queue[item][0] != (tid, mode): return BLOCKED # 必须排在队首，保证 FIFO
for (other, m) in holders[item]:
if other != tid and (mode == 'X' or m == 'X'): return BLOCKED # 相容矩阵判定
holders[item][tid] = mode
queue[item].remove((tid, mode))
return GRANTED
upon release_all(tid): # 严格 2PL：只在提交/中止时调用
for item in holders: holders[item].remove(tid)
for item in queue: queue[item].remove_if(t -> t.tid == tid)
# 事务执行器（每个事务 T 的驱动逻辑）
upon T.step():
if T.ops 已耗尽: # 收尾
release_all(T.tid) # ← 严格 2PL 的关键：此刻才放锁
T.state = COMMITTED
return DONE
op = T.ops[T.pc]
mode = ('S' if op 是读 else 'X')
if request_lock(op.item, T.tid, mode) == BLOCKED:
T.state = BLOCKED # 保持已持有的锁不动 → 可能死锁
return BLOCKED
if op 是读:
T.local[op.var] = read_from_db(op.item) # 持 S 锁后读（因为 X 锁未释放，绝不会读到脏数据）
else:
write_to_db(op.item, op.fn(T.local)) # 持 X 锁后直接写（严格 2PL 下无人能读到脏数据）
T.pc += 1
return PROGRESS
算法逻辑解说（用 19.4.1 场景 A 走一遍：x = 100，$T_1$ 扣 10，$T_2$ 扣 20）
- $T_1$ 要
R(x)：申请S(x)，队首且无冲突 ⇒ 授予，读到 100。 - $T_2$ 要
R(x)：申请S(x)，与 $T_1$ 的 S 相容 ⇒ 也授予，也读到 100。 - $T_1$ 要
W(x)：申请X(x)（锁升级）。它是队首，但持有者里除自己外还有 $T_2$ ⇒BLOCKED，$T_1$ 阻塞（注意它没有释放 S 锁）。 - $T_2$ 要
W(x)：申请X(x)，但 $T_1$ 已排在队首 ⇒BLOCKED。 - 系统进入”全员阻塞”状态 ⇒ 触发死锁检测（算法 19.3.2）：等待图有环 $T_1 \to T_2 \to T_1$ ⇒ 回滚牺牲者 $T_2$（最年轻）。
- $T_2$ 释放 S 锁 ⇒ $T_1$ 的升级成功，写 90、提交、放锁；$T_2$ 重跑：读到 90，写 70 ✓。
- 最终
x = 70，与串行执行一致 ✓。
正确性论证
- 安全性 Safety（2PL ⇒ 冲突可串行化）：
- 对每条冲突边 $T_i \to T_j$，设 $T_i$ 的操作为 $p$、$T_j$ 的操作为 $q$，两者访问同一数据项且至少一个是写。因为访问相冲突，两者必须持有不相容的锁模式，所以 $T_i$ 必须先获取、后释放该锁，$T_j$ 才能获取它。
- 记 $s_i$ 为 $T_i$ 进入收缩阶段（第一次释放任何锁）的时刻，$g_j$ 为 $T_j$ 增长阶段中获取该锁的时刻。由第 1 步：$s_i \le \text{release}_i < \text{acquire}_j \le g_j \le s_j$，即 $s_i < s_j$；而 $s_i$ 恰好就是 $T_i$ 的锁点（lock point）。
- 于是每条冲突边都满足 $\text{lock\_point}(T_i) < \text{lock\_point}(T_j)$——锁点沿边严格递增。
- 假设优先图有环 $T_{i_1} \to T_{i_2} \to \cdots \to T_{i_k} \to T_{i_1}$，沿环传递得 $\text{lock\point}(T{i_1}) < \cdots < \text{lock\point}(T{i_1})$，矛盾。故无环 ⇒ 由串行化定理冲突可串行化。$\blacksquare$
- 补充：这个证明只用到了”两阶段”这一条纪律，与放锁早晚无关，因此基本 2PL、严格 2PL、强严格 2PL 都满足可串行化。
- 安全性（严格 2PL 的额外保证）：
- 可恢复性（recoverable）：$T_j$ 若读了 $T_i$ 写的数据，则 $T_j$ 必然是在 $T_i$ 释放 X 锁之后才读到它——而严格 2PL 的 X 锁在提交时才释放，所以 $T_i$ 提交必早于 $T_j$ 读到该数据、也早于 $T_j$ 提交。故不存在”读了未提交数据却先提交”的情形，回滚时不会牵连已提交事务。
- 无级联回滚（avoids cascading aborts, ACA）：读者只会读到已提交事务的写（脏数据被 X 锁挡住），所以回滚 $T_i$ 不会迫使任何其他事务一起回滚。
- 串行化顺序 = 提交顺序：严格 2PL 下锁点与提交点重合，于是由安全性第 3 步得到”提交顺序就是等价的串行顺序”。
- 活性 Liveness：
- 无饥饿：锁授予严格 FIFO，任何请求者的排队位置只会前进（前面的人拿完就走），不会无限期被插队。
- 可能死锁：协议不保证无死锁（这正是它的代价）——所以必须外挂死锁检测（19.3.2）或死锁预防（19.3.3）/超时。若配合周期性检测，则活性在”检测器最终会发现环并牺牲一个事务”的前提下成立（见算法 19.3.2 的活性论证）。
复杂度
- 每次加锁：哈希查表 + 相容性检查，$O(1)$（若用位图表示模式集合则更快）。
- 每个事务的锁数上界 = 它访问过的不同数据项数 $\vert items(T)\vert $；总空间 $O(\sum_T \vert items(T)\vert )$。
- 释放：$O(\vert items(T)\vert )$（事务结束时需要清空它在所有队列中的排队项）。
- 死锁检测：增量维护 $O(1)$/边；一次全图检测 $O(V+E)$，其中 $V \le n$（活跃事务数）、$E$ 为等待边数，$E = O(V^2)$。
算法 19.3.2：等待图死锁检测与牺牲者回滚
假设与系统模型
- 单机（一个锁管理器即可看到全部等待关系）。分布式下的推广见算法 19.3.4。
- 同步/异步均可；要求锁管理器的状态更新是原子的（因此等待图永远是当前的，不会出现幻死锁）。
- 检测是周期性触发的（例如每 $T_{poll}$ 毫秒），或在”所有事务都阻塞”时立即触发。
伪代码
state:
wfg : directed graph, 节点 = 活跃事务, 边 (Ti -> Tj) 表示 Ti 在等 Tj 持有的锁
rollback_count[tid] : 该事务被牺牲的次数（用于防饥饿）
# ---- 边维护：在加锁/放锁的同一临界区里增量更新，O(1) ----
upon T_i 因 item 被阻塞（持有者是 T_j）:
for each T_j in holders[item] conflicting with requested mode:
wfg.add_edge(T_i, T_j)
upon T_i 获得 item 的锁 或 T_i 回滚:
wfg.remove_all_out_edges(T_i) # 它不再等任何人了
wfg.remove_all_in_edges(T_i) # 别人可能不再等它（若它释放了锁）
for each blocked T_a: 按其阻塞条件重新添加必要的边
# ---- 周期性检测 ----
upon detect_deadlock():
color = {} # 0 = 未访问, 1 = 在栈上(灰), 2 = 已完成(黑)
stack = []
function dfs(u):
color[u] = 1; stack.push(u)
for v in wfg.successors(u):
if color[v] == 1: # 遇到灰色节点 ⇒ 发现环
cycle = stack.from(v) # 截取环上的事务列表
return cycle
if color[v] == 0:
r = dfs(v); if r != null: return r
stack.pop(); color[u] = 2
return null
for u in wfg.nodes():
if color[u] == 0:
cycle = dfs(u)
if cycle != null:
victim = select_victim(cycle)
return abort_and_recover(victim)
upon select_victim(cycle):
# 启发式：优先（持有锁数少, 越年轻, 已回滚次数少）
return argmin over t in cycle of ( locks_held(t), -TS(t), rollback_count[t] )
upon abort_and_recover(victim):
rollback_count[victim] += 1
undo_all_writes(victim) # 用 undo 日志恢复旧值
release_all_locks(victim) # 唤醒因它而阻塞的事务（并更新 wfg 的边）
victim.restart() # 重启；沿用原时间戳可保证 TS 序稳定
算法逻辑解说（用 19.4.3 的三事务环：$T_1$ 持 A 等 B、$T_2$ 持 B 等 C、$T_3$ 持 C 等 A）
- 三个事务各自持有一把锁并申请下一把 ⇒ 三条等待边，等待图是一个三元环。
- 检测器从 $T_1$ 出发 DFS：$T_1 \to T_2 \to T_3 \to T_1$，$T_1$ 是灰色节点 ⇒ 得到环 $[T_1,T_2,T_3]$。
select_victim：三人各持 1 把锁、回滚次数都是 0，于是按”最年轻”选 $T_3$。- 回滚 $T_3$：undo 它对 C 的写、释放 C 的锁 ⇒ $T_2$ 拿到 C，继续执行并提交 ⇒ 死锁解除，系统重新推进。
- 恢复后重新检测：等待图只剩 $T_1 \to T_2$，无环 ✓。
正确性论证
- 安全性 Safety（报出的环一定是真死锁）：若 DFS 找到环 $T_{i_1} \to \cdots \to T_{i_k} \to T_{i_1}$，则每条边都表示”前者正在等待后者持有的锁”，即环上每个事务都在等待环上下一个事务持有的另一把锁，而它自己持有的锁又不会释放（阻塞期间锁不释放）⇒ 环上没有任何事务能推进，这是一个真正的死锁。另外，因为等待图由锁管理器在临界区内原子维护，不会出现幻死锁（信息永远是最新的）。$\blacksquare$
- 活性 Liveness（有死锁终会被发现，且系统不会永久卡死）：
- 检测完备性：只要检测器周期性运行（或在”一圈无人推进”时立即运行），活跃的环必然会被某次检测遍历到（DFS 会访问所有节点），因此死锁不会”永远不被发现”。
- 系统前进性：一次成功的检测至少回滚环上一个事务，撤销其全部等待边，环被破坏（可能的例外：多个环共享节点时，牺牲者可能同时在别的环上，需要再检测一轮——由于牺牲者会重启并重新竞争，且检测会重复进行，系统最终能推进；实践中通过”牺牲者优先选择不在多个环上的事务”来加速）。
- 无饥饿：
rollback_count参与牺牲者选择，使被反复牺牲的事务逐渐获得豁免（老化）。
复杂度
- 边维护：每次阻塞/唤醒 $O(\text{冲突持有者数})$，均摊 $O(1)$。
- 一次检测：$O(V + E)$，其中 $E$ 为等待边数（最坏 $O(V^2)$）。
- 空间：$O(V + E)$。
- 检测频率的代价：设每次检测成本 $C = O(V+E)$，则检测的额外开销为 $C / T_{poll}$（每秒）；$T_{poll}$ 太小 ⇒ CPU 浪费，太大 ⇒ 死锁存活时间变长、事务白等。经验做法是把 $T_{poll}$ 设为事务平均执行时间的量级。
算法 19.3.3：Wait-Die 与 Wound-Wait（时间戳死锁预防）
假设与系统模型
- 时间戳在事务开始时分配，全局唯一、单调；回滚后重启时沿用原时间戳（这是”不饥饿”论证的关键前提）。
- 每个事务的锁请求是原子的；Wait-Die 不允许抢占（只能回滚请求者自己），Wound-Wait 允许抢占（可以强行回滚锁的持有者）。
- 锁的授予与释放语义同 19.3.1（严格 2PL 的收尾方式）。
伪代码
# ---------- Wait-Die（非抢占：老的等，年轻的死）----------
upon request_lock(Ti, item, mode):
loop:
if 不相容的持有者集合 conflict(Ti, item, mode) 为空:
grant(Ti, item, mode); return GRANTED
let Tj = conflict 集合中的任意一个（通常取最老的或最先的）
if TS(Ti) < TS(Tj): # Ti 更老
block(Ti, waiting_for = Tj) # 【wait】老老实实等
return BLOCKED
else: # Ti 更年轻
abort(Ti) # 【die】回滚自己
restart(Ti, ts = TS(Ti)) # 【关键】沿用原时间戳重启
return ABORTED
# ---------- Wound-Wait（抢占：老的伤害，年轻的等）----------
upon request_lock(Ti, item, mode):
loop:
if 不相容的持有者集合 conflict(Ti, item, mode) 为空:
grant(Ti, item, mode); return GRANTED
for each Tj in conflict 集合:
if TS(Ti) < TS(Tj): # Ti 更老
abort(Tj) # 【wound】强行回滚持有者 Tj
restart(Tj, ts = TS(Tj)) # Tj 也用原时间戳重启
# 继续 loop：等 Tj 的锁真正释放后再检查一次
else: # Ti 更年轻
block(Ti, waiting_for = Tj) # 【wait】
return BLOCKED
算法逻辑解说（$T_1$ 时间戳 10、$T_2$ 时间戳 20；$T_1$ 持 A，$T_2$ 持 B；随后 $T_2$ 请求 A、$T_1$ 请求 B）
| 步骤 | Wait-Die 的处置 | Wound-Wait 的处置 |
|---|---|---|
| $T_2$（20）请求 A（$T_1$ 持有） | $T_2$ 更年轻 ⇒ die：$T_2$ 回滚，释放 B，用 20 重启 | $T_2$ 更年轻 ⇒ wait：$T_2$ 阻塞等 A |
| $T_1$（10）请求 B（$T_2$ 持有） | $T_1$ 更老 ⇒ wait：等 B（此时 B 已因 $T_2$ 死亡而释放，立刻拿到） | $T_1$ 更老 ⇒ wound：强行回滚 $T_2$，$T_1$ 拿到 B |
| 结果 | $T_2$ 白做一次（重做），$T_1$ 顺利推进 | $T_2$ 白做一次（被打断），$T_1$ 顺利推进 |
| 倾向 | 让老事务等待（老事务的响应时间变差），年轻事务被反复回滚 | 让年轻事务让路（老事务优先完成），等待发生在年轻一侧 |
正确性论证
- 安全性 Safety（无死锁）：
- Wait-Die 中，只有”$T_i$ 更老”时才会产生等待，所以每条等待边满足 $\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$ ⇒ 沿边严格递增。
- Wound-Wait 中，只有”$T_i$ 更年轻”时才会产生等待，所以每条等待边满足 $\mathrm{TS}(T_i) > \mathrm{TS}(T_j)$ ⇒ 沿边严格递减。
- 两种情况下，等待关系都是一个严格偏序（时间戳沿边单向严格变化）。若存在环 $T_{i_1}\to\cdots\to T_{i_k}\to T_{i_1}$，沿环传递会得到 $\mathrm{TS}(T_{i_1}) < \mathrm{TS}(T_{i_1})$（或 $>$），严格不等式回到自身，矛盾 ⇒ 等待图无环 ⇒ 无死锁。$\blacksquare$
- 注意前提：重启必须沿用原时间戳。否则一个刚被回滚的事务可能拿到更大的时间戳，等待边的单调方向就会被破坏，证明失效（这也是实现中必须遵守的纪律）。
- 安全性（可串行化）：两种协议都只是”在 2PL 的框架内决定谁等待、谁回滚”，回滚的事务用原时间戳重做并最终重新经历完整的 2PL 生命周期，所以产生的历史仍然是 2PL 历史 ⇒ 由算法 19.3.1 的证明，冲突可串行化。
- 活性 Liveness（无饥饿）：
- Wait-Die：能杀死年轻事务 $Y$ 的只有”比 $Y$ 更老”的事务；时间戳在开始时分配，所以 $Y$ 启动之后再也不会出现比它更老的事务——这个集合是有限且不再增长的。而每个老事务最终都会完成（老事务只等待更年轻的事务，年轻者要么做完、要么被杀死后释放全部锁，因此老事务的等待总会被解除）。有限次杀死之后，$Y$ 必然成功。$Y$ 之所以能保持”年轻”，正是因为重启时沿用原时间戳。
- Wound-Wait：最老的事务从不等待（它只会伤害别人），因此总有一个事务能推进；同理每个事务在被有限的更老事务”伤害”完之后必然完成。
- 补充：两种策略的取舍——Wait-Die 让老事务等，可能拖长老事务的响应时间；Wound-Wait 让老事务优先，平均上更少回滚（因为老事务有更多的已做工作，让它继续更划算），代价是”被伤害”的事务要重做全部工作。
复杂度
- 每次锁请求：冲突集合的检查 $O(\vert \text{holders}\vert )$，比较时间戳 $O(1)$；被回滚时需要 undo 其写并释放锁，$O(\vert items(T)\vert )$。
- 无需维护任何全局图、无需周期性检测 ⇒ 空间 $O(1)$（除锁表外），通信 $O(1)$。这是它在分布式系统中特别受欢迎的原因。
- 代价体现在回滚率：本讲 19.4.3 的实验里，高冲突负载下 TO/时间戳类策略的回滚次数显著高于 2PL（后者靠”阻塞等待”避免回滚）。
算法 19.3.4：Chandy-Misra-Haas 分布式死锁检测（边追踪）
假设与系统模型
- $N$ 个站点，事务分布在站点上；每个站点只知道自己本地事务的等待关系（局部 WFG）。
- 通道：可靠（探测消息不丢失）、FIFO（加速检测，非必需）；站点可能 crash-stop（崩溃会导致探测消息丢失 ⇒ 该分支的检测失效，因此实际系统会配合超时）。
- AND 等待模型：事务要拿到全部所需锁才能继续（本课程采用的口径）；OR 模型需要不同的算法。
- 目标：不发全局快照，用探测消息沿等待边传播来发现环。
伪代码
# 变量（每个站点 S 本地维护）
waits[t] : 事务 t 正在等待的事务集合（局部 WFG 的出边）
forwarded[t] : 事务 t 已经转发过的 (initiator, sender, target) 集合（消息抑制）
site_of[t] : 事务 t 所在站点（通过路由表查到）
# ---------- 1) 发起：当本地事务 Ti 开始等待本地或远程事务 Tj ----------
upon 本地事务 Ti 因 item 被 Tj 阻塞:
waits[Ti].add(Tj)
send PROBE(initiator=Ti, sender=Ti, target=Tj) to site_of[Tj]
# ---------- 2) 站点 S 收到探测消息 ----------
upon receive PROBE(i, j, k):
# 语义：发起者是 Ti，发送者 Tj 报告"Tj 正在等待 Tk"
if k == i: # 探测绕回发起者 ⇒ 存在环
report_deadlock(cycle_ending_at = i)
return
if (i, j, k) in forwarded[k]: # 【消息抑制】同样的探测不必重复转发
return
if waits[k] is empty: # Tk 不在等待任何人 ⇒ 这条路径不可能成环
return
forwarded[k].add((i, j, k))
for each m in waits[k]: # 沿等待边继续追击
send PROBE(initiator=i, sender=k, target=m) to site_of[m]
# ---------- 3) 本地等待关系变化时 ----------
upon Tt 获得锁（不再等待）或 Tt 提交/中止:
waits.remove(Tt)
forwarded.remove(Tt) # 它的历史转发记录一并作废
算法逻辑解说（3 个站点上的环：$T_1@S_0 \to T_2@S_1 \to T_3@S_2 \to T_1@S_0$）
| 序 | 事件 | 说明 |
|---|---|---|
| 1 | $S_0$ 发出 PROBE(1, 1, 2) 给 $S_1$ | $T_1$ 开始等待 $T_2$ |
| 2 | $S_1$ 收到：$k=2 \neq i=1$，且 waits[2] = {3} ⇒ 转发 PROBE(1, 2, 3) 给 $S_2$ | 探测沿等待边前进 |
| 3 | $S_2$ 收到：$k=3 \neq 1$，且 waits[3] = {1} ⇒ 转发 PROBE(1, 3, 1) 给 $S_0$ | 探测绕到最后一个事务 |
| 4 | $S_0$ 收到：$k = 1 = i$ ⇒ 检测到死锁，环为 $T_1\to T_2\to T_3\to T_1$ | 只有真正成环才会收到”自己的”探测 |
| 5 | 若 $S_1$ 重传了同一条 PROBE(1,1,2)：(1,1,2) 已在 forwarded 中 ⇒ 直接丢弃 | 消息抑制把重复探测的爆炸式放大压住 |
正确性论证
- 安全性 Safety（何时”报告 ⇒ 真死锁”成立）：设收到
PROBE(i, k, i)时报告死锁。- 这条探测路径可以还原成 $i \to t_2 \to t_3 \to \cdots \to t_k \to i$：
PROBE(i, sender, target)的每一跳都意味着”在发起这一跳的那一刻，sender 确实在等待 target“（因为只有当 sender 被 target 阻塞时，它的waits里才会有 target）。 - 若假设等待关系在整次检测期间保持不变，则路径上所有边同时成立 ⇒ 等待图确实含环 ⇒ 是真死锁。$\blacksquare$
- 这个证明依赖”等待关系不变”这一前提——去掉它，安全性就只剩”曾经存在过部分环”，于是出现幻死锁。
- 这条探测路径可以还原成 $i \to t_2 \to t_3 \to \cdots \to t_k \to i$：
- 幻死锁（phantom deadlock）的构造：在步骤 3 与步骤 4 之间，让 $T_2$（环上的中间节点）中止并释放全部锁：
- 真实的等待边只剩 $T_3 \to T_1$（无环）；
- 但 $S_1$ 早已把
PROBE(1,2,3)发出去了，$S_2$ 收到时它的本地waits[3] = {1}仍然成立，于是继续转发PROBE(1,3,1)； - $S_0$ 收到后 $k=i$ ⇒ 报出一个已经不存在的死锁。
- 本质原因：探测消息携带的是”发送时刻的等待信息”，而环的成立需要”同一时刻所有边都成立”。异步系统里这两者无法区分。这与快照一章的结论完全一致。
- 缓解：① 用一致性全局快照（Chandy-Lamport）获取一个因果一致的等待图再检测，使”快照意义下的环”是真实存在过的；② 探测消息携带时间戳/事务状态，报死锁前向环上站点确认”这些事务是否仍在等待”；③ 接受误报并保证回滚安全——牺牲者本来就可能白回滚，误报只损失性能不破坏正确性。
- 活性 Liveness（报告 ⇒ 能检测到）：
- 完整性：若存在一个”持续存在”的环（环上所有等待一直不被解除），则环上某事务 $T_i$ 的探测最终会沿环传播 $k$ 步回到 $T_i$，因为通道可靠、FIFO，且每一步的
waits都非空。因此死锁必然最终被检测到。 - 终止性：每条探测路径长度不超过”等待链的最大长度”（因为在无环的链上必然终止，而在有环时会立即报告并停止），配合消息抑制，探测风暴不会无限扩散。
- 注意：站点崩溃会丢失探测消息 ⇒ 完整性只在无故障（或配合超时重发）时成立。这也是为什么分布式系统里”超时 + 回滚”仍然是最常用的兜底手段。
- 完整性：若存在一个”持续存在”的环（环上所有等待一直不被解除），则环上某事务 $T_i$ 的探测最终会沿环传播 $k$ 步回到 $T_i$，因为通道可靠、FIFO，且每一步的
复杂度
- 消息复杂度：一次检测最坏为”沿等待图的所有路径”传播，最坏 $O(E)$ 条消息（$E$ 为全局等待边数），每条消息 $O(1)$ 大小；消息抑制把同一 $(i,j,k)$ 的重复转发降为一次。
- 时间：最坏 $O(\text{最长等待链长度})$ 个消息延迟（异步系统下没有时间上界，只能说”有限步内”)。
- 空间：每个站点 $O(\text{本地事务数} \times \text{局部边数})$（主要是
forwarded集合）。 - 对比集中式：集中式是”每有边变化就上报中心”（$O(E)$ 消息但集中在一条链路上，且有单点）；边追踪是”只有发起者才发消息”（开销按事务发起等待的次数计），路径信息留在原地、延迟更高。
算法 19.3.5：Kung-Robinson 乐观并发控制（OCC）
假设与系统模型
- 数据库提供已提交版本的读（本实现中读操作直接读当前已提交值，绝不允许脏读）；
- 每个事务有私有工作区；验证与写阶段在一个临界区中原子执行（这是 OCC 唯一的串行点，也是正确的必要条件）；
- 事务的时间戳在进入验证阶段时分配（即”验证顺序”），而不是开始时分配——这一点是验证条件正确的前提（见 19.2.19 的补充说明）；
- 事务之间异步；无故障注入（崩溃恢复由 WAL 负责，与协议正交）。
伪代码
state（全局）:
db : 已提交数据
committed : 已通过验证的事务列表（按验证顺序，携带其 start / read_end / commit_step / RS / WS）
verify_lock : 互斥锁，保护"验证 + 写阶段"这一段临界区
# ---------------- 阶段 ① 读阶段 ----------------
upon T.step_read_phase():
if T.pc >= |T.ops|: return ENTER_VALIDATION
op = T.ops[T.pc]
if op 是读 item:
T.local[op.var] = db[item] # 读已提交版本，不加锁
T.RS.add(item) # 记录读集
else: # 写
T.buffer[item] = op.fn(T.local) # 只写【私有工作区】，不碰 db
T.WS.add(item) # 记录写集
T.pc += 1
return PROGRESS
# ---------------- 阶段 ② 验证 + 阶段 ③ 写（同一临界区）----------------
upon T.enter_validation():
acquire(verify_lock) # ← 验证与写阶段必须原子（串行点）
T.read_end = now()
T.ts = next_timestamp() # 【时间戳在此分配】= 进入验证的顺序
for each Tj in committed: # 只与"先通过验证"的事务比较（TS(Tj) < TS(T))
if Tj.commit_step < T.start: # 条件 1：Tj 完全早于 T
continue # 所有冲突天然有序，无需检查
if Tj.read_end < T.read_end and Tj.commit_step > T.read_end:
# 条件 2：Tj 的写阶段发生在 T 的读阶段【之后】→ T 不可能读到 Tj 的过时值
# 唯一危险是"两者写同一数据项"导致覆盖顺序颠倒
if T.WS ∩ Tj.WS ≠ ∅: goto ABORT
else:
# 条件 3（含"Tj 的写阶段落在 T 的读阶段之内"这一最危险情形）：
# T 可能读到了 Tj 覆盖前的过时值，也可能与 Tj 争抢同一个写
if (T.RS ∪ T.WS) ∩ Tj.WS ≠ ∅: goto ABORT
# ---------------- 阶段 ③ 写阶段（仍在临界区内）----------------
for each (item, val) in T.buffer:
db[item] = val # 原子地安装，中间不被任何读观察到
committed.append(T)
release(verify_lock)
T.state = COMMITTED
return DONE
ABORT:
discard(T.buffer) # 丢弃私有工作区（数据库从未被污染）
release(verify_lock)
T.state = ABORTED # 由外层驱动重试（restart）
算法逻辑解说（19.4.1 场景 A：$x=100$，$T_1$ 扣 10，$T_2$ 扣 20，交错脚本 T1,T2,T1,T2）
- 读阶段：$T_1$ 读 $x=100$（$RS_1=\{x\}$），把 $100-10=90$ 写进私有工作区（$WS_1=\{x\}$，数据库里还是 100）；$T_2$ 读 $x=100$（$RS_2=\{x\}$），私有工作区里放 $80$。
- $T_1$ 进入验证：
committed为空 ⇒ 无条件通过；把 $x$ 装成 90，加入committed，commit_step = 5。 - $T_2$ 进入验证：对 $T_1$ 检查——$T_1.commit\_step = 5$ 不小于 $T_2.start = 2$ ⇒ 不满足条件 1；$T_1.read\_end = 3 < T_2.read\_end = 6$，但 $T_1.commit\_step = 5 \le T_2.read\_end = 6$（$T_1$ 的写阶段落在 $T_2$ 的读阶段之内）⇒ 走条件 3 的强检查：$(RS_2 \cup WS_2) \cap WS_1 = \{x\} \neq \varnothing$ ⇒ 回滚 $T_2$。
- $T_2$ 重做：这次读到 90，算出 70，验证通过 ⇒ 最终 $x = 70$ ✓，与串行执行一致。
正确性论证
- 安全性 Safety（验证通过的已提交集合冲突可串行化）：把已提交事务按验证顺序排列 $T_1, T_2, \ldots, T_m$，声称 $H$ 冲突等价于这个串行历史。任取 $T_j$（先验证）与 $T_i$（后验证）的一对冲突操作，按 $T_j$ 的写阶段相对于 $T_i$ 的读区间 $[start_i, read\_end_i]$ 的位置分三种情形：
- $T_j$ 的写阶段在 $start_i$ 之前（条件 1）：$T_j$ 的所有操作都在 $T_i$ 的所有操作之前 ⇒ 该冲突对顺序为 $T_j$ 在前 ✓，与串行序一致。
- $T_j$ 的写阶段落在 $[start_i, read\_end_i]$ 之内（条件 3）：验证要求 $WS(T_j) \cap (RS(T_i) \cup WS(T_i)) = \varnothing$。逐类核查冲突：
- $W_j(x)$ 与 $R_i(x)$：由 $RS(T_i) \cap WS(T_j) = \varnothing$ 排除 ⇒ 二者不可能同时访问 $x$，不存在“$T_i$ 读到 $T_j$ 覆盖前的过时值”的冲突；
- $W_j(x)$ 与 $W_i(x)$：由 $WS(T_i) \cap WS(T_j) = \varnothing$ 排除 ⇒ 不存在覆盖顺序颠倒；
- $W_i(x)$ 与 $R_j(x)$：$T_j$ 的读发生在 $T_j$ 的写阶段之前（更在 $T_j$ 的验证之前），而 $T_i$ 的写发生在 $T_i$ 的验证（晚于 $T_j$ 的验证）⇒ $T_j$ 的读先于 $T_i$ 的写 ✓ 顺序与串行序一致。
- $T_j$ 的写阶段在 $read\_end_i$ 之后：由于 $T_j$ 先通过验证，$T_j.commit\_step < T_i.read\_end$（$T_i.read\_end$ 就是 $T_i$ 进入验证的时刻），所以这一情形不可能出现；若实现允许”延迟验证”，则此时 $T_i$ 不可能读到 $T_j$ 的写，唯一危险仍是写-写覆盖 ⇒ 检查 $WS(T_i) \cap WS(T_j) = \varnothing$（即条件 2）。 三种情形下每一对冲突操作的顺序都与”验证顺序”一致 ⇒ $H$ 冲突等价于按验证顺序的串行历史 ⇒ 冲突可串行化。$\blacksquare$
- 关键依赖：证明里”$T_j.commit\_step < T_i.read\_end$”这一步依赖”验证与写阶段原子执行“以及”比较对象只有先通过验证的事务“。如果验证能被并发执行、或时间戳在事务开始时分配而验证延后，就必须用条件 3 的强检查兜底（否则会有反例）。
- 活性 Liveness：
- 每次回滚都会释放全部资源（无锁）并允许重试，系统不会进入死锁（OCC 不存在”持有并等待”）。
- 可能饥饿：若一个事务每次验证时都恰好被新提交的冲突事务挡住，它可能被反复回滚。经典缓解手段是”重试次数越多、优先级越高”，或让它在验证时抢占（把冲突的已提交事务回滚掉，代价更高故少用）。
- 完整性：在冲突有限的负载下，重试最终会成功（每次重试都读到更新的快照，而与之冲突的事务集合是有限的）。
复杂度
- 读阶段：$O(\vert ops\vert )$ 次数据库访问 + 私有工作区写入；无锁、无等待。
- 验证：对每个并发已提交事务做一次集合相交，$O(c \cdot (\vert RS\vert + \vert WS\vert ))$，其中 $c$ 是重叠事务数（用哈希集合可实现 $O(\vert RS\vert +\vert WS\vert )$ 每次比较）。
- 空间：每个活跃事务 $O(\vert RS\vert + \vert WS\vert + \vert ops\vert )$（私有工作区），$n$ 个并发事务即 $O(n \cdot \vert ops\vert )$。
- 通信：单机为 0；分布式 OCC 的验证需要跨站点交换读写集，开销显著（见 19.5）。
算法 19.3.6：时间戳排序 + Thomas 写规则
假设与系统模型
- 时间戳在事务开始时分配，全局唯一；回滚后重启可沿用原时间戳（会饿死）或重新分配更大的时间戳（本实现默认后者，用于演示”饥饿”与”收敛”的差别）。
- 每个数据项维护
read_TS（已执行读的最大时间戳）与write_TS（已提交写的最大时间戳）； - 写采用缓冲到提交（buffer 到 commit 才安装），因此读者绝不可能读到未提交数据 ⇒ 无脏读、无级联回滚（这就是”严格 TO”）；
- “等待更早的写者”是本协议的等待来源：等待只发生在年轻等年老的方向上。
伪代码
state:
item.value, item.read_TS, item.write_TS
item.pending_write_ts : 该数据项上【未提交】写者的时间戳集合
upon T.read(item):
if TS(T) < item.write_TS: # 已有更年轻的事务提交过写
abort(T, reason="会读到过时值"); return ABORTED
if 存在 pending 写者 Tj 且 TS(Tj) < TS(T): # 严格 TO：等更早的写者
block(T); return BLOCKED
item.read_TS = max(item.read_TS, TS(T)) # 抬高读时间戳，阻止更老的事务以后写
T.local[var] = item.value
return item.value
upon T.write(item, value):
if TS(T) < item.read_TS: # 更年轻的事务已经读过 → 我的写会作废它的读
abort(T, reason="不可重复读风险"); return ABORTED
if 存在 pending 写者 Tj 且 TS(Tj) < TS(T): # 严格 TO：等更早的写者
block(T); return BLOCKED
if TS(T) < item.write_TS: # 【过时写】
if not THOMAS_ENABLED:
abort(T, reason="过时写"); return ABORTED
else:
# ----- Thomas 写规则：忽略这次写，而不是回滚 -----
# 理由：item.write_TS > TS(T) 说明存在更新的版本；
# 此后任何读的 TS 必须 > write_TS > TS(T)（否则被读规则拒绝），
# 所以【没有任何事务可能读到我这次写的版本】→ 删除它不改变任何 read-from
log("ignore stale write"); return OK_IGNORED
T.buffer[item] = value # 先缓冲，提交时才安装
item.pending_write_ts.add(TS(T))
return OK_BUFFERED
upon T.commit():
for (item, val) in T.buffer:
item.value = val
item.write_TS = max(item.write_TS, TS(T)) # 只有到了提交，才更新 write_TS
item.pending_write_ts.remove(TS(T))
T.state = COMMITTED
算法逻辑解说（19.4.1 场景 A，$T_1$ 时间戳 1、$T_2$ 时间戳 2，交错 T1,T2,T1,T2）
- $T_1$ 读 $x$：$\mathrm{TS}=1 \ge write\_TS=0$ ⇒ 允许；$read\_TS(x) \gets 1$，读到 100。
- $T_2$ 读 $x$：$2 \ge 0$ ⇒ 允许；$read\_TS(x) \gets 2$，也读到 100。
- $T_1$ 写 $x$：检查 $\mathrm{TS}(T_1)=1 < read\_TS(x)=2$ ⇒ 回滚 $T_1$（”更年轻的事务已经读过，我的写会让它读了个寂寞”）。这正是经典 TO 的饥饿现象：如果重启时沿用时间戳 1，$read\_TS(x)$ 仍然是 2，$T_1$ 会永远回滚下去。
- 本实现默认”重启时分配更大的时间戳”：$T_1$ 拿到 $\mathrm{TS}=3$ ⇒ 重新读 $x$（$read\_TS \gets 3$，读到 100）、写 $x$（$3 \ge read\_TS = 3$ ✓，$\mathrm{TS}=3 \ge write\_TS=0$ ✓）⇒ 提交后 $x=90$、$write\_TS(x)=3$。
- $T_2$ 重做：读 $x$ 时发现 $\mathrm{TS}(T_2)=2 < write\_TS(x)=3$ ⇒ 回滚，拿到 $\mathrm{TS}=4$；再读得 90，写 70，提交 ⇒ 最终 $x = 70$ ✓。
- 若把 Thomas 规则打开并构造”老事务重复写同一数据项”的负载，可以看到日志里出现
ignore stale write——那次写被安静地丢弃，而不是引发一次回滚，这正是它降低回滚率的机制。
正确性论证
- 安全性 Safety（按时间戳的串行序）：把已提交事务按时间戳 $T_1, T_2, \ldots, T_m$（$\mathrm{TS}$ 递增）排列，声称这是等价的串行顺序。任取一对来自不同事务、访问同一数据项的冲突操作：
- 读-写（$R_i(x)$ 与 $W_j(x)$）：若 $\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$，则 $T_j$ 执行写时必须满足 $\mathrm{TS}(T_j) \ge write\_TS(x)$，而 $T_i$ 的读已把 $x$ 的版本固定在 $\mathrm{TS} \le \mathrm{TS}(T_i) < \mathrm{TS}(T_j)$ 的版本上，两者在时间戳序上不矛盾；反向若 $\mathrm{TS}(T_j) < \mathrm{TS}(T_i)$，则 $T_i$ 的读会被规则 $\mathrm{TS}(T_i) < write\_TS(x)$ 拒绝（因为 $T_j$ 已经写入并抬高了 $write\_TS$）⇒ 这种”读到更老版本却排在后”的情形不可能提交。故读的来源与时间戳序一致。
- 写-写（$W_i(x)$ 与 $W_j(x)$）：设 $\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$。$T_j$ 执行写时若 $\mathrm{TS}(T_j) < write\_TS(x)$（已被一个中间时间戳的写占据）⇒ 按基本 TO 回滚、按 Thomas 规则忽略；无论哪种，$T_i$ 的写都不会覆盖 $T_j$ 的写（时间戳大的写一定在”值序列”的后端生效）。故写的生效顺序与时间戳序一致。
- 每一对冲突操作的生效顺序都与时间戳序一致 ⇒ $H$ 冲突等价于按时间戳的串行历史 ⇒ 冲突可串行化。$\blacksquare$
- Thomas 写规则的正确性（更弱但够用）：开启 Thomas 规则后，”忽略一次过时写”意味着历史里少了一次写操作，因此得到的是视图可串行化而非严格意义上的冲突可串行化。论证分两步：
- 该版本永不被读：忽略发生在 $\mathrm{TS}(T) < write\_TS(x)$ 时。此后的任何读都要求 $\mathrm{TS}(\text{reader}) \ge write\_TS(x) > \mathrm{TS}(T)$，于是读者看到的一定是时间戳不小于 $write\_TS(x)$ 的版本（更年轻或同代），绝不会看到 $T$ 的版本；此前的读发生在这次写之前，自然也没见过它。
- 删除一个”永不被读、且不是最终写”的版本，不改变任何 read-from 关系与最终写 ⇒ 由视图等价的定义，历史仍视图等价于按时间戳的串行历史 ⇒ 视图可串行化。$\blacksquare$
- 直观结论：Thomas 规则用”稍微放宽正确性标准（视图可串行化）”换来了”显著降低回滚率”；而 19.2.10 已说明视图可串行化的历史在实际系统中是安全的。
- 无死锁（安全性的一部分）：本协议的等待只发生在”$\mathrm{TS}(T)$ 较大者等待 $\mathrm{TS}$ 较小者”的方向上（
block的两个触发条件都要求存在 pending 写者 $T_j$ 且 $\mathrm{TS}(T_j) < \mathrm{TS}(T)$）。于是每条等待边沿时间戳严格递减，与算法 19.3.3 的论证同构 ⇒ 等待图无环 ⇒ 无死锁。$\blacksquare$ - 活性 Liveness：
- 前进性：设 $T_{\min}$ 是当前活跃事务中时间戳最小者。它不可能被
block（block要求存在更早的写者，而 $T_{\min}$ 是最早的），因此 $T_{\min}$ 总能推进并在有限步内提交或回滚。用归纳法：每一轮至少消除一个事务。 - 饥饿：若回滚后沿用原时间戳，$T_{\min}$ 提交后，某个老事务仍可能因为
read_TS被更年轻的事务抬得过高而反复回滚、永不成功——这就是经典 TO 的饥饿/活锁（19.4.1 场景 D 中”沿用原时间戳”一列出现数百次回滚且多个事务始终未完成）。可行修法：① 回滚后分配新的（更大的）时间戳（本实现默认），把”老人优先”改成”先进先出”；② 只回滚”读时间戳”冲突中的年轻一方；③ 维护活跃事务集合，令 $\min(read\_TS(x), \{\mathrm{TS}(T): T \text{ 活跃}\})$ 而不是历史最大值——即及时回收过期的 read_TS。
- 前进性：设 $T_{\min}$ 是当前活跃事务中时间戳最小者。它不可能被
复杂度
- 每次读/写：$O(1)$（几次时间戳比较；
pending集合小，或用堆取最小值 $O(\log n)$）。 - 空间：每数据项 $O(1)$（加上 pending 集合）；每事务 $O(\vert WS\vert )$ 的写缓冲。
- 与 2PL 的对比：TO 零锁表、零等待结构，但需要全局时间戳分配器——单机是计数器，分布式下要么用中心分配器（瓶颈），要么用”时间戳区间预分配”（每站点一次领一段区间），后者是 Spanner/早期分布式数据库的常用做法。
19.3.7 六份算法的横向对照
| 算法 | 冲突检测时机 | 是否加锁 | 死锁 | 饥饿 | 关键正确性依据 |
|---|---|---|---|---|---|
| 严格 2PL | 访问前（加锁时） | 是（S/X） | 可能 | 否（FIFO） | 锁点沿冲突边严格递增 ⇒ 优先图无环 |
| 等待图死锁检测 | 阻塞后周期性 | 是 | 检测并破环 | 否（回滚计数老化） | 环 ⇒ 真死锁；回滚破环 ⇒ 前进 |
| Wait-Die / Wound-Wait | 加锁时（时间戳裁决） | 是 | 不可能 | 否（原时间戳重启 + 有限老事务集） | 等待边时间戳严格单调 ⇒ 无环 |
| CMH 边追踪 | 等待边产生时 | 是（配合锁） | 检测（可能幻报） | —— | 探测路径还原为等待边链；等待不变 ⇒ 环真实 |
| Kung-Robinson OCC | 提交时（验证） | 读不加锁/写阶段短暂临界区 | 不可能 | 理论上可能 | 三类冲突在验证条件覆盖下均按验证序排列 ⇒ 冲突等价 |
| TO + Thomas | 每次读写时 | 否 | 不可能 | 可能（需新时间戳或回收 read_TS） | 所有冲突对生效顺序 = 时间戳序 ⇒ 冲突等价（Thomas：视图等价） |
19.4 代码示例与分布式实现
本节给出三个可直接 python3 运行的程序（只用标准库、固定随机种子、无外部依赖）。第一个是四种并发控制协议的完整模拟器，第二个是优先图与可串行化判定工具，第三个是死锁演示与分布式边追踪检测器。三个程序互相独立，也都与 19.3 的伪代码一一对应。
19.4.1 完整并发控制模拟器（NoCC / 严格 2PL / OCC / TO）
"""cc_sim.py -- 并发控制模拟器：NoCC / Strict-2PL / OCC / 时间戳排序(TO)
只用标准库，固定随机种子，`python3 cc_sim.py` 直接运行。
"""
import itertools
import random
random.seed(425)
# ==================== 数据结构 ====================
class Item:
"""一个数据项：当前值 + read_TS + write_TS + 未提交写者列表"""
def __init__(self, value):
self.value, self.read_ts, self.write_ts, self.pending = value, 0, 0, []
class LockMgr:
"""共享/排他锁：holders[item]={tid:'S'|'X'}，queue[item]=[(tid,mode)]"""
def __init__(self):
self.holders, self.queue = {}, {}
def request(self, item, tid, mode):
held = self.holders.setdefault(item, {})
q = self.queue.setdefault(item, [])
if held.get(tid) == 'X' or (held.get(tid) == 'S' and mode == 'S'):
return True # 重入 / 已持更强锁
entry = (tid, mode)
if entry not in q:
q.append(entry) # FIFO 排队，防止饥饿
if q[0] != entry:
return False # 不是队首 -> 等待
if mode == 'X' and tid in held and len(held) > 1:
return False # 锁升级失败：别人持 S
if any(o != tid and (mode == 'X' or m == 'X') for o, m in held.items()):
return False # 与持有者冲突
held[tid] = mode
q.pop(0)
return True
def release_all(self, tid):
for held in self.holders.values():
held.pop(tid, None)
for item in self.queue:
self.queue[item] = [e for e in self.queue[item] if e[0] != tid]
def wait_for_edges(self, alive):
"""由锁表构造等待图：T_i -> T_j 表示 T_i 正在等 T_j"""
edges = set()
for item, q in self.queue.items():
held = self.holders.get(item, {})
for i, (tid, mode) in enumerate(q):
if tid not in alive:
continue
edges |= {(tid, t2) for t2, _ in q[:i] if t2 in alive}
edges |= {(tid, h) for h, hm in held.items()
if h != tid and h in alive and (mode == 'X' or hm == 'X')}
return edges
class Txn:
"""ops: ('R', item, var) 读入局部变量；('W', item, fn) 用 fn(local) 求新值"""
def __init__(self, tid, ts, ops):
self.tid, self.ts, self.ops, self.name = tid, ts, ops, "T%d" % tid
self.attempt = 0
self.restart(0)
def restart(self, step, new_ts=None):
if new_ts is not None:
self.ts = new_ts
self.attempt += 1
self.pc, self.state = 0, 'ready'
self.local, self.buffer = {}, {}
self.read_set, self.write_set, self.observed = set(), set(), {}
self.start, self.read_end, self.commit_step = step, None, None
self.committed_attempt, self.final_observed = None, {}
# ==================== 四种并发控制协议 ====================
class Protocol:
retry_same_ts = True # 回滚后是否沿用原时间戳（TO 会覆盖它）
def __init__(self, txns, db):
self.txns, self.db, self.clock = txns, db, max(t.ts for t in txns)
self.history = [] # (tid, attempt, 'R'/'W', item) 按真实时间顺序
self.log, self.deadlocks, self.victims = [], 0, []
def record(self, t, op, item):
self.history.append((t.tid, t.attempt, op, item))
def finish(self, t, step_no):
t.state, t.commit_step, t.committed_attempt = 'committed', step_no, t.attempt
t.final_observed = dict(t.observed)
return 'done'
def step(self, t, step_no):
raise NotImplementedError
class NoCC(Protocol):
name = "无并发控制"
def step(self, t, step_no):
if t.pc >= len(t.ops):
self.log.append("%s COMMIT" % t.name)
return self.finish(t, step_no)
op = t.ops[t.pc]
t.pc += 1
if op[0] == 'R':
t.local[op[2]] = t.observed[op[2]] = self.db[op[1]].value
t.read_set.add(op[1])
self.record(t, 'R', op[1])
self.log.append("%s R(%s)=%d" % (t.name, op[1], t.local[op[2]]))
else:
self.db[op[1]].value = op[2](t.local)
t.write_set.add(op[1])
self.record(t, 'W', op[1])
self.log.append("%s W(%s)=%d" % (t.name, op[1], self.db[op[1]].value))
return 'progress'
class Strict2PL(Protocol):
"""严格两阶段锁：排他锁持到提交；加锁后立即写数据库"""
name = "严格两阶段锁"
def __init__(self, txns, db):
Protocol.__init__(self, txns, db)
self.lm = LockMgr()
def step(self, t, step_no):
if t.pc >= len(t.ops):
self.lm.release_all(t.tid) # 提交时才释放全部锁
self.log.append("%s COMMIT（此刻才释放全部锁）" % t.name)
return self.finish(t, step_no)
op = t.ops[t.pc]
mode = 'S' if op[0] == 'R' else 'X'
if not self.lm.request(op[1], t.tid, mode):
self.log.append("%s 等待 %s 上的 %s 锁" % (t.name, op[1], mode))
return 'blocked'
t.pc += 1
if op[0] == 'R':
t.local[op[2]] = t.observed[op[2]] = self.db[op[1]].value
t.read_set.add(op[1])
self.record(t, 'R', op[1])
self.log.append("%s 取得 %s 锁并 R(%s)=%d" % (t.name, mode, op[1], t.local[op[2]]))
else:
self.db[op[1]].value = op[2](t.local)
t.write_set.add(op[1])
self.record(t, 'W', op[1])
self.log.append("%s 取得 X 锁并 W(%s)=%d" % (t.name, op[1], self.db[op[1]].value))
return 'progress'
class OCC(Protocol):
"""Kung-Robinson 三阶段 OCC：读阶段（私有工作区）-> 验证 -> 写阶段"""
name = "乐观并发控制"
def __init__(self, txns, db):
Protocol.__init__(self, txns, db)
self.committed = []
def conflict(self, t, u):
"""u 更早通过验证（TS(u) < TS(t)）；返回 True 表示 t 必须回滚"""
if u.commit_step < t.start:
return False # 条件 1：u 完全早于 t
if u.read_end < t.read_end and u.commit_step > t.read_end:
return bool(t.write_set & u.write_set) # 条件 2：只查写-写
return bool((t.read_set | t.write_set) & u.write_set) # 条件 3：读-写与写-写强检查
def step(self, t, step_no):
if t.pc >= len(t.ops):
t.read_end = step_no # 读阶段结束 -> 验证
self.clock += 1
t.ts = self.clock # 时间戳 = 进入验证阶段的顺序
bad = [u.name for u in self.committed if self.conflict(t, u)]
if bad:
t.state = 'aborted'
self.log.append("%s 验证失败（与 %s 冲突：读集 %s 写集 %s）-> 回滚"
% (t.name, ",".join(bad), sorted(t.read_set), sorted(t.write_set)))
return 'abort'
for item, val in t.buffer.items(): # 写阶段：原子安装
self.db[item].value = val
self.record(t, 'W', item)
self.committed.append(t)
self.log.append("%s 验证通过 -> 写阶段安装 %s" % (t.name, t.buffer))
return self.finish(t, step_no)
op = t.ops[t.pc]
t.pc += 1
if op[0] == 'R':
t.local[op[2]] = t.observed[op[2]] = self.db[op[1]].value
t.read_set.add(op[1])
self.log.append("%s(读阶段) R(%s)=%d" % (t.name, op[1], t.local[op[2]]))
else:
t.buffer[op[1]] = op[2](t.local) # 只写私有工作区
t.write_set.add(op[1])
self.log.append("%s(读阶段) 私有工作区 W(%s)=%d" % (t.name, op[1], t.buffer[op[1]]))
return 'progress'
class TimestampOrdering(Protocol):
"""严格时间戳排序（写缓冲到提交）+ Thomas 写规则"""
name = "时间戳排序+Thomas"
def __init__(self, txns, db, thomas=True, retry_same_ts=False):
Protocol.__init__(self, txns, db)
self.thomas, self.retry_same_ts, self.ignored = thomas, retry_same_ts, 0
def step(self, t, step_no):
if t.pc >= len(t.ops): # 提交：安装写缓冲
for item, val in t.buffer.items():
it = self.db[item]
it.value, it.write_ts = val, max(it.write_ts, t.ts)
it.pending = [p for p in it.pending if p[1] != t.tid]
self.record(t, 'W', item)
self.log.append("%s COMMIT（安装写缓冲 %s，更新 write_TS）" % (t.name, t.buffer))
return self.finish(t, step_no)
op = t.ops[t.pc]
it = self.db[op[1]]
if op[0] == 'R':
if t.ts < it.write_ts: # 已有更年轻的事务写过
t.state = 'aborted'
self.log.append("%s 读 %s 被拒（TS=%d < write_TS=%d）-> 回滚"
% (t.name, op[1], t.ts, it.write_ts))
return 'abort'
if any(p[0] < t.ts for p in it.pending):
return 'blocked' # 等更早的写者结束
it.read_ts = max(it.read_ts, t.ts)
t.local[op[2]] = t.observed[op[2]] = it.value
t.read_set.add(op[1])
self.record(t, 'R', op[1])
self.log.append("%s R(%s)=%d, read_TS:=%d" % (t.name, op[1], it.value, it.read_ts))
else:
if t.ts < it.read_ts: # 更年轻的事务读过 -> 写会作废它的读
t.state = 'aborted'
self.log.append("%s 写 %s 被拒（TS=%d < read_TS=%d）-> 回滚"
% (t.name, op[1], t.ts, it.read_ts))
return 'abort'
if any(p[0] < t.ts for p in it.pending):
return 'blocked'
if t.ts < it.write_ts: # 过时写
if not self.thomas:
t.state = 'aborted'
self.log.append("%s 写 %s 被拒（过时写）-> 回滚" % (t.name, op[1]))
return 'abort'
self.ignored += 1
self.log.append("%s 的 W(%s) 是过时写（TS=%d < write_TS=%d）-> Thomas 规则忽略"
% (t.name, op[1], t.ts, it.write_ts))
t.pc += 1
return 'progress'
t.buffer[op[1]] = op[2](t.local)
t.write_set.add(op[1])
it.pending.append((t.ts, t.tid))
self.log.append("%s 缓冲 W(%s)=%d" % (t.name, op[1], t.buffer[op[1]]))
t.pc += 1
return 'progress'
# ==================== 驱动器 ====================
def run(proto_cls, programs, values, schedule=None, max_steps=300, rnd=False, **kw):
db = {k: Item(v) for k, v in values.items()}
txns = [Txn(i + 1, i + 1, programs[i]) for i in range(len(programs))]
proto = proto_cls(txns, db, **kw) if kw else proto_cls(txns, db)
step_no, ptr, sched, restarts = 0, 0, list(schedule or []), 0
def abort(t):
nonlocal restarts
restarts += 1
if isinstance(proto, Strict2PL):
proto.lm.release_all(t.tid) # 牺牲者必须放锁
if isinstance(proto, TimestampOrdering):
for it in db.values():
it.pending = [p for p in it.pending if p[1] != t.tid]
nt = None if proto.retry_same_ts else proto.clock + 1
if nt:
proto.clock = nt
t.restart(step_no, nt)
while any(t.state == 'ready' for t in txns) and step_no < max_steps:
step_no += 1
moved = False
while sched and not moved: # 1) 显式交错脚本
t = txns[sched.pop(0)]
if t.state != 'ready':
continue
r = proto.step(t, step_no)
if r == 'blocked':
break
moved = True
if r == 'abort':
abort(t)
if moved:
continue
for _ in range(len(txns)): # 2) 轮转 / 随机调度
if rnd:
ready = [x for x in txns if x.state == 'ready']
if not ready:
break
t = random.choice(ready)
else:
t = txns[ptr % len(txns)]
ptr += 1
if t.state != 'ready':
continue
r = proto.step(t, step_no)
if r == 'blocked':
continue
moved = True
if r == 'abort':
abort(t)
break
if not moved: # 3) 一圈无人推进 -> 死锁
alive = {t.tid for t in txns if t.state == 'ready'}
victim = detect_deadlock(proto, alive)
if victim is None:
proto.log.append("全部阻塞但等待图无环（在等外部事件）")
break
proto.deadlocks += 1
proto.victims.append(victim)
v = [t for t in txns if t.tid == victim][0]
proto.log.append(">>> 检测到死锁！等待图有环，牺牲者 = %s，回滚重启" % v.name)
abort(v)
done = {t.tid: t.committed_attempt for t in txns if t.committed_attempt}
hist = [h for h in proto.history if h[1] == done.get(h[0])]
reads = {t.name: t.final_observed for t in txns if t.committed_attempt}
starved = sum(1 for t in txns if t.state == 'ready') # 未收敛（活锁 / 饥饿）
return proto, {k: v.value for k, v in db.items()}, reads, hist, restarts, starved
def detect_deadlock(proto, alive):
"""等待图 DFS 找环；返回环上时间戳最大的事务（最年轻者）"""
if not isinstance(proto, Strict2PL):
return None
adj = {}
for a, b in proto.lm.wait_for_edges(alive):
adj.setdefault(a, set()).add(b)
color, stack, cycle = {}, [], None
def dfs(u):
nonlocal cycle
color[u] = 1
stack.append(u)
for v in adj.get(u, ()):
if color.get(v, 0) == 1:
cycle = stack[stack.index(v):]
return True
if color.get(v, 0) == 0 and dfs(v):
return True
stack.pop()
color[u] = 2
return False
for u in sorted(alive):
if color.get(u, 0) == 0 and dfs(u):
return max(cycle)
return None
# ==================== 校验器：优先图 + 串行等价 ====================
def precedence_cycle(hist):
"""由历史构造优先图，返回 (是否有环, 边集合)"""
edges = set()
for i in range(len(hist)):
for j in range(i + 1, len(hist)):
ti, _, oi, xi = hist[i]
tj, _, oj, xj = hist[j]
if ti != tj and xi == xj and (oi == 'W' or oj == 'W'):
edges.add((ti, tj))
adj = {}
for a, b in edges:
adj.setdefault(a, set()).add(b)
color = {}
def dfs(u):
color[u] = 1
for v in adj.get(u, ()):
if color.get(v, 0) == 1:
return True
if color.get(v, 0) == 0 and dfs(v):
return True
color[u] = 2
return False
return any(color.get(u, 0) == 0 and dfs(u) for u in sorted(adj)), edges
def serial_runs(programs, values):
"""穷举所有串行顺序：{串行序: (最终状态, 各事务读到的值)}"""
out = {}
for perm in itertools.permutations(range(len(programs))):
db, reads = dict(values), {}
for k in perm:
local = {}
for op in programs[k]:
if op[0] == 'R':
local[op[2]] = db[op[1]]
else:
db[op[1]] = op[2](local)
reads["T%d" % (k + 1)] = dict(local)
out["->".join("T%d" % (k + 1) for k in perm)] = (db, reads)
return out
# ==================== 场景 ====================
def transfer_lost_update():
"""场景 A：丢失更新（两个事务各自扣款，语义上等价于共扣 30）"""
return [[('R', 'x', 'a'), ('W', 'x', lambda L: L['a'] - 10)],
[('R', 'x', 'b'), ('W', 'x', lambda L: L['b'] - 20)]]
def transfer_inconsistent_read():
"""场景 B：T1 从 x 转 100 到 y；T2 读 x、y 求总额写入 z（必须恒为 300）"""
return [[('R', 'x', 'a'), ('W', 'x', lambda L: L['a'] - 100),
('R', 'y', 'b'), ('W', 'y', lambda L: L['b'] + 100)],
[('R', 'x', 's1'), ('R', 'y', 's2'), ('W', 'z', lambda L: L['s1'] + L['s2'])]]
def deadlock_pair():
"""场景 C：T1 先锁 A 再锁 B；T2 先锁 B 再锁 A"""
return [[('W', 'A', lambda L: 1), ('W', 'B', lambda L: 2)],
[('W', 'B', lambda L: 3), ('W', 'A', lambda L: 4)]]
def conflict_workload(n, hot):
"""场景 D：n 个事务各自读改写 hot 个热点数据项之一"""
progs = []
for _ in range(n):
item = "k%d" % random.randint(0, hot - 1)
progs.append([('R', item, 'v'), ('W', item, lambda L: L['v'] + 1)])
return progs
def scenario(title, programs, values, schedule=None):
print("=" * 78)
print("场景 %s 初始状态 %s" % (title, values))
runs = serial_runs(programs, values)
print("所有串行执行的结果（最终状态 / 各事务读到的值）：")
for perm, (st, rd) in runs.items():
print(" %-12s -> %-28s %s" % (perm, st, rd))
if schedule:
print("本次使用的交错脚本（按操作给出事务序号）：%s" % (schedule,))
print("-" * 78)
rows = []
for cls in (NoCC, Strict2PL, OCC, TimestampOrdering):
proto, final, reads, hist, restarts, _ = run(cls, programs, values, schedule=schedule)
cyclic, edges = precedence_cycle(hist)
equ = [p for p, v in runs.items() if v == (final, reads)]
ok = bool(equ) and not cyclic
print("[%-14s] 最终状态=%s 读到的值=%s" % (cls.name, final, reads))
print(" 优先图边=%s 有环=%s 串行等价于=%s 判定：%s"
% (sorted(edges), "是" if cyclic else "否", equ or "无",
"可串行化" if ok else "不可串行化"))
print(" 回滚重启=%d 次 死锁=%d 次 牺牲者=%s Thomas 忽略的过时写=%d"
% (restarts, proto.deadlocks, proto.victims, getattr(proto, 'ignored', 0)))
if cls in (NoCC, Strict2PL):
for line in proto.log[:14]:
print(" | " + line)
rows.append((cls.name, final, ok, restarts, proto.deadlocks))
print("-" * 78)
print(" %-16s %-24s %-10s %-10s %s" % ("协议", "最终状态", "串行等价", "回滚次数", "死锁次数"))
for r in rows:
print(" %-16s %-24s %-10s %-10d %d" % (r[0], str(r[1]), "是" if r[2] else "否", r[3], r[4]))
print()
return rows
if __name__ == "__main__":
scenario("A. 丢失更新（x=100，T1 扣 10，T2 扣 20）", transfer_lost_update(), {'x': 100},
schedule=[0, 1, 0, 1])
scenario("B. 不一致检索（x=200,y=100，T1 转 100，T2 求总额写入 z）",
transfer_inconsistent_read(), {'x': 200, 'y': 100, 'z': 0},
schedule=[0, 0, 1, 1, 0, 0, 1])
scenario("C. 两阶段锁的死锁（T1 先锁 A 再锁 B；T2 先锁 B 再锁 A）", deadlock_pair(),
{'A': 0, 'B': 0})
print("=" * 78)
print("场景 D：冲突率扫描（8 个事务；hot = 热点数据项个数，越小冲突越激烈）")
print(" %-5s %-20s %-16s %-18s %-18s" %
("hot", "严格2PL(回滚/死锁)", "OCC 回滚", "TO 回滚(新时间戳)", "TO 回滚(原时间戳)"))
for hot in (8, 4, 2, 1):
progs = conflict_workload(8, hot)
vals = {"k%d" % i: 0 for i in range(8)}
p2, _, _, _, r2, _ = run(Strict2PL, progs, vals, rnd=True)
_, _, _, _, ro, _ = run(OCC, progs, vals, rnd=True)
_, _, _, _, rt, st = run(TimestampOrdering, progs, vals, rnd=True)
_, _, _, _, rf, sf = run(TimestampOrdering, progs, vals, rnd=True, retry_same_ts=True)
print(" %-5d %-20s %-16s %-18s %-18s" %
(hot, "回滚%d 死锁%d" % (r2, p2.deadlocks), "回滚%d" % ro,
"回滚%d 未完成%d" % (rt, st), "回滚%d 未完成%d" % (rf, sf)))
print("\n注：hot 越小冲突越激烈 -> OCC 回滚飙升；2PL 靠阻塞等待但会死锁；")
print(" TO 沿用原时间戳重试会活锁（老事务被反复回滚），重新分配时间戳才收敛。")
【代码做什么？】
- 建模”数据库 + 事务”：
Item是一个数据项（value+read_ts+write_ts+pending未提交写者列表）；Txn是一个事务，它的程序是一串操作('R', item, var)（读进局部变量）与('W', item, fn)（用fn(local)算出新值）——用 lambda 表达”新值依赖我读到的值”，丢失更新/不一致检索这类异常就自然产生了。 - 四种协议各实现一个
step(t, step_no)，每次推进一步并返回progress / blocked / abort / done：NoCC：直接读写数据库，作为对照组（展示异常）；Strict2PL：LockMgr实现 S/X 锁的相容性判定 + FIFO 等待队列，事务按”访问前加锁、提交时一次性释放全部锁”执行（严格 2PL）；OCC：读阶段把修改写进t.buffer（私有工作区），记录read_set/write_set；操作耗尽时进入验证 + 写阶段（在同一step里原子完成）；TimestampOrdering：每次读写先做时间戳规则判定，写进写缓冲、提交时才安装并更新write_ts；retry_same_ts开关用来对比”沿用原时间戳（会活锁）”与”重新分配时间戳”。
- 驱动器
run()支持三种调度：显式交错脚本（schedule=[0,1,0,1]，用来精确复现讲义里的异常交错）、轮转、随机（用于冲突率扫描）。当”绕一圈没有任何事务能推进”时，触发detect_deadlock()：由锁表构造等待图、DFS 找环、选出最年轻的牺牲者、回滚并重启。 - 两个独立校验器（不依赖协议自身的说法）：
serial_runs()：穷举所有串行顺序，记录每种顺序的”最终状态 + 每个事务读到的值”；precedence_cycle()：从真实发生的操作历史构造优先图并检测环。 只有”优先图无环”且“结果与某个串行执行完全一致（含读到的值）”才判定为可串行化。
- 四个场景 + 一张统计对比表：A 丢失更新、B 不一致检索、C 两阶段锁死锁、D 冲突率扫描（对照 2PL / OCC / TO）。
实际运行结果（节选）
场景 A. 丢失更新（x=100，T1 扣 10，T2 扣 20） 初始状态 {‘x’: 100} 所有串行执行的结果（最终状态 / 各事务读到的值）： T1->T2 -> {‘x’: 70} {‘T1’: {‘a’: 100}, ‘T2’: {‘b’: 90}} T2->T1 -> {‘x’: 70} {‘T2’: {‘b’: 100}, ‘T1’: {‘a’: 80}} 本次使用的交错脚本（按操作给出事务序号）：[0, 1, 0, 1] —————————————————————————— [无并发控制 ] 最终状态={‘x’: 80} 读到的值={‘T1’: {‘a’: 100}, ‘T2’: {‘b’: 100}} 优先图边=[(1, 2), (2, 1)] 有环=是 串行等价于=无 判定：不可串行化 回滚重启=0 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 | T1 R(x)=100 | T2 R(x)=100 | T1 W(x)=90 | T2 W(x)=80 | T1 COMMIT | T2 COMMIT [严格两阶段锁 ] 最终状态={‘x’: 70} 读到的值={‘T1’: {‘a’: 100}, ‘T2’: {‘b’: 90}} 优先图边=[(1, 2)] 有环=否 串行等价于=[‘T1->T2’] 判定：可串行化 回滚重启=1 次 死锁=1 次 牺牲者=[2] Thomas 忽略的过时写=0 | T1 取得 S 锁并 R(x)=100 | T2 取得 S 锁并 R(x)=100 | T1 等待 x 上的 X 锁 | T1 等待 x 上的 X 锁 | T2 等待 x 上的 X 锁 | »> 检测到死锁！等待图有环，牺牲者 = T2，回滚重启 | T2 等待 x 上的 S 锁 | T1 取得 X 锁并 W(x)=90 | T2 等待 x 上的 S 锁 | T1 COMMIT（此刻才释放全部锁） | T2 取得 S 锁并 R(x)=90 | T2 取得 X 锁并 W(x)=70 | T2 COMMIT（此刻才释放全部锁） [乐观并发控制 ] 最终状态={‘x’: 70} 读到的值={‘T1’: {‘a’: 100}, ‘T2’: {‘b’: 90}} 优先图边=[(1, 2)] 有环=否 串行等价于=[‘T1->T2’] 判定：可串行化 回滚重启=1 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 [时间戳排序+Thomas ] 最终状态={‘x’: 70} 读到的值={‘T1’: {‘a’: 80}, ‘T2’: {‘b’: 100}} 优先图边=[(2, 1)] 有环=否 串行等价于=[‘T2->T1’] 判定：可串行化 回滚重启=1 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 —————————————————————————— 协议 最终状态 串行等价 回滚次数 死锁次数 无并发控制 {‘x’: 80} 否 0 0 严格两阶段锁 {‘x’: 70} 是 1 1 乐观并发控制 {‘x’: 70} 是 1 0 时间戳排序+Thomas {‘x’: 70} 是 1 0
==============================================================================
场景 C. 两阶段锁的死锁（T1 先锁 A 再锁 B；T2 先锁 B 再锁 A） 初始状态 {‘A’: 0, ‘B’: 0} 所有串行执行的结果（最终状态 / 各事务读到的值）： T1->T2 -> {‘A’: 4, ‘B’: 3} {‘T1’: {}, ‘T2’: {}} T2->T1 -> {‘A’: 1, ‘B’: 2} {‘T2’: {}, ‘T1’: {}} —————————————————————————— [无并发控制 ] 最终状态={‘A’: 4, ‘B’: 2} 读到的值={‘T1’: {}, ‘T2’: {}} 优先图边=[(1, 2), (2, 1)] 有环=是 串行等价于=无 判定：不可串行化 回滚重启=0 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 | T1 W(A)=1 | T2 W(B)=3 | T1 W(B)=2 | T2 W(A)=4 | T1 COMMIT | T2 COMMIT [严格两阶段锁 ] 最终状态={‘A’: 4, ‘B’: 3} 读到的值={‘T1’: {}, ‘T2’: {}} 优先图边=[(1, 2)] 有环=否 串行等价于=[‘T1->T2’] 判定：可串行化 回滚重启=1 次 死锁=1 次 牺牲者=[2] Thomas 忽略的过时写=0 | T1 取得 X 锁并 W(A)=1 | T2 取得 X 锁并 W(B)=3 | T1 等待 B 上的 X 锁 | T2 等待 A 上的 X 锁 | »> 检测到死锁！等待图有环，牺牲者 = T2，回滚重启 | T1 取得 X 锁并 W(B)=2 | T2 等待 B 上的 X 锁 | T1 COMMIT（此刻才释放全部锁） | T2 取得 X 锁并 W(B)=3 | T2 取得 X 锁并 W(A)=4 | T2 COMMIT（此刻才释放全部锁） [乐观并发控制 ] 最终状态={‘A’: 4, ‘B’: 3} 读到的值={‘T1’: {}, ‘T2’: {}} 优先图边=[(1, 2)] 有环=否 串行等价于=[‘T1->T2’] 判定：可串行化 回滚重启=1 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 [时间戳排序+Thomas ] 最终状态={‘A’: 4, ‘B’: 3} 读到的值={‘T1’: {}, ‘T2’: {}} 优先图边=[(1, 2)] 有环=否 串行等价于=[‘T1->T2’] 判定：可串行化 回滚重启=0 次 死锁=0 次 牺牲者=[] Thomas 忽略的过时写=0 —————————————————————————— 协议 最终状态 串行等价 回滚次数 死锁次数 无并发控制 {‘A’: 4, ‘B’: 2} 否 0 0 严格两阶段锁 {‘A’: 4, ‘B’: 3} 是 1 1 乐观并发控制 {‘A’: 4, ‘B’: 3} 是 1 0 时间戳排序+Thomas {‘A’: 4, ‘B’: 3} 是 0 0
==============================================================================
场景 D：冲突率扫描（8 个事务；hot = 热点数据项个数，越小冲突越激烈） hot 严格2PL(回滚/死锁) OCC 回滚 TO 回滚(新时间戳) TO 回滚(原时间戳)
8 回滚2 死锁2 回滚2 回滚2 未完成0 回滚280 未完成2
4 回滚4 死锁4 回滚6 回滚8 未完成0 回滚280 未完成4
2 回滚9 死锁9 回滚10 回滚16 未完成0 回滚285 未完成5
1 回滚6 死锁6 回滚20 回滚22 未完成0 回滚285 未完成6
注：hot 越小冲突越激烈 -> OCC 回滚飙升；2PL 靠阻塞等待但会死锁； TO 沿用原时间戳重试会活锁（老事务被反复回滚），重新分配时间戳才收敛。
【分布式机制透视】
- 并发/时序如何体现：
run()的调度循环就是”操作系统调度器 + 网络延迟”的抽象——每调用一次step就推进一个操作，操作的相对顺序完全由调度决定。显式交错脚本等价于”精确控制网络消息到达顺序”，随机调度等价于”真实的竞态”。 - 哪些是真实分布式系统的对应物：
LockMgr+ FIFO 队列 ⇔ 数据库的锁管理器（真实系统里它是内存中的哈希表 + 每对象的等待队列）；detect_deadlock()里的等待图 ⇔ 单机数据库的死锁检测后台线程（真实系统每秒跑几次）；跨站点的推广就是 19.4.3 的 CMH 算法；OCC的buffer（私有工作区）⇔ 事务的局部变量 + 撤销日志；”验证 + 写阶段原子”⇔ 真实的验证临界区/短锁；TimestampOrdering的write_ts/read_ts⇔ 真实 TO 数据库在每个数据项头部维护的两个字段；”写缓冲到提交”⇔ 严格 TO 的延迟写；serial_runs()的穷举 ⇔ 真实系统的串行化验证（工程上用优先图/SI 的危险结构检测代替穷举，但语义完全相同）。
- 简化之处（必须清楚）：① 单机、无网络分区、无消息丢失（锁请求是本地调用）；② 没有真正实现崩溃恢复（
undo由”回滚后重启事务”隐式体现）；③ 事务程序是静态的（真实系统里访问集在执行中动态确定）；④ 时间戳是自增整数（分布式下需要一个分配器或区间预分配）。
【与理论的对应】
| 代码位置 | 对应本章理论 | 验证了哪条结论 |
|---|---|---|
LockMgr.request() 的相容性判定 | 19.2.11 锁相容矩阵 | S-S 相容、含 X 必冲突 |
LockMgr 持锁到 COMMIT 才 release_all | 19.2.13 严格 2PL | 无脏读、无级联回滚 |
场景 A 中 2PL 的 T1 等待 x 上的 X 锁 → >>> 检测到死锁 | 19.2.14 / 算法 19.3.2 | 2PL 不能避免死锁；等待图有环 |
场景 A 中 precedence_cycle 对 NoCC 报”有环=是” | 19.2.9 串行化定理 | 丢失更新的优先图确有环 |
OCC.conflict() 的三个分支 | 19.2.19 条件 1/2/3 + 算法 19.3.5 | 验证条件保证冲突按验证序排列 |
OCC 的时间戳在验证时分配 | 19.2.19 补充说明 | 否则条件 2 会漏掉”读到过时值” |
TimestampOrdering 的 t.ts < it.read_ts 拒绝写 | 19.2.20 TO 规则 | 老事务的写会作废年轻人的读 ⇒ 回滚 |
TimestampOrdering 的 blocked 只在 pending 更早时出现 | 算法 19.3.6 | 等待边从年轻指向年老 ⇒ 无死锁 |
| 场景 D “TO 回滚(原时间戳)” 一列出现数百次回滚且事务未完成 | 19.2.20 缺点① | 固定时间戳的 TO 会饥饿/活锁 |
19.4.2 优先图与冲突可串行化判定工具
"""serial_graph.py -- 优先图 / 冲突可串行化判定工具
历史用紧凑记号书写：'R1(x)' = T1 读 x，'W2(y)' = T2 写 y，按真实发生顺序排列。
直接用 `python3 serial_graph.py` 运行，会对若干精心构造的历史给出判定。
"""
import itertools
# ------------------------- 1. 解析与优先图构造 -------------------------
def parse(hist):
"""'R1(x) W2(x)' -> [(1,'R','x'), (2,'W','x')]"""
out = []
for tok in hist.split():
out.append((int(tok[1]), tok[0], tok[3]))
return out
def build_graph(ops):
"""两个来自不同事务的操作访问同一数据项且至少一个是写 => 冲突，画边"""
edges, conflicts = set(), []
for i in range(len(ops)):
for j in range(i + 1, len(ops)):
ti, oi, xi = ops[i]
tj, oj, xj = ops[j]
if ti != tj and xi == xj and (oi == 'W' or oj == 'W'):
edges.add((ti, tj))
conflicts.append((ops[i], ops[j]))
adj = {}
for a, b in edges:
adj.setdefault(a, set()).add(b)
return adj, sorted(edges), conflicts
def find_cycle(adj):
"""DFS 找环，返回环上的事务序列（无环返回 None）"""
color, stack = {}, []
def dfs(u):
color[u] = 1
stack.append(u)
for v in sorted(adj.get(u, ())):
if color.get(v, 0) == 1:
return stack[stack.index(v):] + [v]
if color.get(v, 0) == 0:
r = dfs(v)
if r:
return r
stack.pop()
color[u] = 2
return None
for u in sorted(adj):
if color.get(u, 0) == 0:
r = dfs(u)
if r:
return r
return None
def topo_order(adj, nodes):
"""Kahn 拓扑排序，返回一个等价串行序（有环返回 None）"""
indeg = {n: 0 for n in nodes}
for a in adj:
for b in adj[a]:
indeg[b] = indeg.get(b, 0) + 1
ready = sorted(n for n in nodes if indeg.get(n, 0) == 0)
order = []
while ready:
u = ready.pop(0)
order.append(u)
for v in sorted(adj.get(u, ())):
indeg[v] -= 1
if indeg[v] == 0:
ready.append(v)
ready.sort()
return order if len(order) == len(nodes) else None
def equivalent(ops, order):
"""检查串行序 order 是否与历史 ops 冲突等价（所有冲突对的相对顺序一致）"""
pos = {t: i for i, t in enumerate(order)}
for i in range(len(ops)):
for j in range(i + 1, len(ops)):
ti, oi, xi = ops[i]
tj, oj, xj = ops[j]
if ti != tj and xi == xj and (oi == 'W' or oj == 'W'):
if pos[ti] > pos[tj]: # 历史里 Ti 在前，串行序里却在后 -> 不等价
return False
return True
def analyze(name, hist):
ops = parse(hist)
nodes = sorted({t for t, _, _ in ops})
adj, edges, conflicts = build_graph(ops)
cyc = find_cycle(adj)
order = topo_order(adj, nodes)
print("历史 %s: %s" % (name, hist))
print(" 冲突操作对：%s" % " ".join("%s~%s" % (a, b) for a, b in conflicts))
print(" 优先图（邻接表）：%s" % (" ".join("%d->%s" % (a, sorted(adj[a])) for a in sorted(adj))
or "（无边）"))
if cyc:
print(" >>> 检测到环 %s（%s）=> 冲突不可串行化"
% ("->".join(map(str, cyc)), " ".join("%d->%d" % (cyc[i], cyc[i + 1])
for i in range(len(cyc) - 1))))
print(" 正确做法：至少回滚环上的一个事务（如 T%d）" % cyc[0])
else:
ok = equivalent(ops, order)
print(" >>> 无环 => 冲突可串行化；等价串行序 = %s（冲突等价校验：%s）"
% ("->".join("T%d" % t for t in order), "通过" if ok else "失败"))
print()
return not cyc
# ------------------------- 2. 测试历史 -------------------------
H_SERIAL = "R1(x) W1(x) R2(x) W2(x)" # 串行序 T1;T2
H_LOST_UPDATE = "R1(x) R2(x) W1(x) W2(x)" # 丢失更新的交错
H_INCONSISTENT = "W1(x) R2(x) R2(y) W1(y)" # 不一致检索
H_2PL_OK = "R1(x) W1(x) R1(y) W1(y) R2(y) W2(y)" # 严格 2PL 能产生的历史
H_2PL_BAD = "W1(x) R2(x) W2(y) R1(y)" # 2PL 不可能产生（放锁后又加锁）
H_VIEW_NOT_CONFLICT = "R1(x) W2(x) W1(x) W3(x)" # 视图可串行化但冲突不可串行化
H_CYCLE3 = "R1(a) W2(a) R2(b) W3(b) R3(c) W1(c)" # 三事务环
def exhaustive_2pl_check(n_trials=4000):
"""随机生成 2PL 产生的历史，验证『2PL 产生的历史必定冲突可串行化』"""
import random
random.seed(425)
bad = 0
for _ in range(n_trials):
nt = random.randint(2, 4)
items = ['x', 'y', 'z']
locks, held, released, seq = {}, {t: set() for t in range(1, nt + 1)}, set(), []
for _ in range(random.randint(4, 14)):
t = random.randint(1, nt)
it = random.choice(items)
owner = locks.get(it)
if owner not in (None, t):
continue # 已被别人锁住 -> 阻塞
if owner is None:
if t in released:
continue # 收缩阶段不得再加锁（2PL 的硬约束）
locks[it] = t
held[t].add(it)
seq.append((t, random.choice('RW'), it))
if t not in released and held[t] and random.random() < 0.3:
i = random.choice(sorted(held[t])) # 释放一个锁 -> 进入收缩阶段
locks[i] = None
held[t].discard(i)
released.add(t)
adj, _, _ = build_graph(seq)
if find_cycle(adj):
bad += 1
print(" 反例历史：%s" % " ".join("%s%d(%s)" % (o, t, x) for t, o, x in seq))
print("随机 2PL 历史 %d 条，其中优先图有环的 = %d 条（定理断言应为 0）" % (n_trials, bad))
return bad == 0
if __name__ == "__main__":
print("=" * 74)
print("优先图与冲突可串行化判定")
print("=" * 74)
analyze("s1（串行）", H_SERIAL)
analyze("s2（丢失更新）", H_LOST_UPDATE)
analyze("s3（不一致检索）", H_INCONSISTENT)
analyze("s4（2PL 可产生）", H_2PL_OK)
analyze("s5（2PL 不可产生）", H_2PL_BAD)
analyze("s6（视图可串行化 ≠ 冲突可串行化）", H_VIEW_NOT_CONFLICT)
analyze("s7（三事务环）", H_CYCLE3)
print("=" * 74)
print("定理校验：2PL 产生的历史必定冲突可串行化（优先图无环）")
print("=" * 74)
assert exhaustive_2pl_check(), "出现反例！"
print("结论：未发现反例，与 2PL 的可串行化定理一致。")
print()
print("说明：s6 中 T1 是'读后写'，T2 与 T3 都是盲写（不读直接写）——")
print(" T2 的 W(x) 随后被 T1 的 W(x) 覆盖，最终写者是 T3，")
print(" T1 读到的仍是初始值，与串行序 T1;T2;T3 完全一致，")
print(" 所以它是【视图可串行化】的；但在冲突等价的意义上，")
print(" 历史里 W2(x) 先于 W1(x)，而串行序要求 W1(x) 先于 W2(x)，")
print(" 两条边 1->2 与 2->1 同时存在 —— 冲突等价不成立。")
【代码做什么？】
parse()把紧凑记号（R1(x)= $T_1$ 读 $x$）解析成操作序列。build_graph()逐对检查操作：来自不同事务、访问同一数据项、且至少一个是写 ⇒ 画一条与执行顺序同向的边（这就是 19.2.9 的构图规则），并顺带打印出所有冲突操作对。find_cycle()用三色标记 DFS 找环，并还原出环上的事务序列（打印T1->T2->T3->T1这种可读形式），从而给出”至少回滚哪一个”的建议。topo_order()用 Kahn 算法求拓扑序——它就是定理”（⇐）方向”的构造性证明：无环 ⇒ 拓扑序 ⇒ 该序就是等价的串行顺序。随后equivalent()再独立校验一次”所有冲突对的相对顺序在串行序里是否被保持”，把定理的两个方向都落到代码上。exhaustive_2pl_check()用随机生成器产生 4000 条严格按 2PL 纪律（拿不到锁就跳过、进入收缩阶段后绝不再加锁）的历史，逐条检查优先图是否有环——对 19.2.12 的定理做统计意义上的证伪尝试。
实际运行结果（节选）
========================================================================== 优先图与冲突可串行化判定 ========================================================================== 历史 s1（串行）: R1(x) W1(x) R2(x) W2(x) 冲突操作对：(1, ‘R’, ‘x’)~(2, ‘W’, ‘x’) (1, ‘W’, ‘x’)~(2, ‘R’, ‘x’) (1, ‘W’, ‘x’)~(2, ‘W’, ‘x’) 优先图（邻接表）：1->[2]
无环 => 冲突可串行化；等价串行序 = T1->T2（冲突等价校验：通过）
历史 s2（丢失更新）: R1(x) R2(x) W1(x) W2(x) 冲突操作对：(1, ‘R’, ‘x’)~(2, ‘W’, ‘x’) (2, ‘R’, ‘x’)~(1, ‘W’, ‘x’) (1, ‘W’, ‘x’)~(2, ‘W’, ‘x’) 优先图（邻接表）：1->[2] 2->[1]
检测到环 1->2->1（1->2 2->1）=> 冲突不可串行化 正确做法：至少回滚环上的一个事务（如 T1）
历史 s3（不一致检索）: W1(x) R2(x) R2(y) W1(y) 冲突操作对：(1, ‘W’, ‘x’)~(2, ‘R’, ‘x’) (2, ‘R’, ‘y’)~(1, ‘W’, ‘y’) 优先图（邻接表）：1->[2] 2->[1]
检测到环 1->2->1（1->2 2->1）=> 冲突不可串行化 正确做法：至少回滚环上的一个事务（如 T1）
历史 s4（2PL 可产生）: R1(x) W1(x) R1(y) W1(y) R2(y) W2(y) 冲突操作对：(1, ‘R’, ‘y’)~(2, ‘W’, ‘y’) (1, ‘W’, ‘y’)~(2, ‘R’, ‘y’) (1, ‘W’, ‘y’)~(2, ‘W’, ‘y’) 优先图（邻接表）：1->[2]
无环 => 冲突可串行化；等价串行序 = T1->T2（冲突等价校验：通过）
历史 s5（2PL 不可产生）: W1(x) R2(x) W2(y) R1(y) 冲突操作对：(1, ‘W’, ‘x’)~(2, ‘R’, ‘x’) (2, ‘W’, ‘y’)~(1, ‘R’, ‘y’) 优先图（邻接表）：1->[2] 2->[1]
检测到环 1->2->1（1->2 2->1）=> 冲突不可串行化 正确做法：至少回滚环上的一个事务（如 T1）
历史 s6（视图可串行化 ≠ 冲突可串行化）: R1(x) W2(x) W1(x) W3(x) 冲突操作对：(1, ‘R’, ‘x’)~(2, ‘W’, ‘x’) (1, ‘R’, ‘x’)~(3, ‘W’, ‘x’) (2, ‘W’, ‘x’)~(1, ‘W’, ‘x’) (2, ‘W’, ‘x’)~(3, ‘W’, ‘x’) (1, ‘W’, ‘x’)~(3, ‘W’, ‘x’) 优先图（邻接表）：1->[2, 3] 2->[1, 3]
检测到环 1->2->1（1->2 2->1）=> 冲突不可串行化 正确做法：至少回滚环上的一个事务（如 T1）
历史 s7（三事务环）: R1(a) W2(a) R2(b) W3(b) R3(c) W1(c) 冲突操作对：(1, ‘R’, ‘a’)~(2, ‘W’, ‘a’) (2, ‘R’, ‘b’)~(3, ‘W’, ‘b’) (3, ‘R’, ‘c’)~(1, ‘W’, ‘c’) 优先图（邻接表）：1->[2] 2->[3] 3->[1]
检测到环 1->2->3->1（1->2 2->3 3->1）=> 冲突不可串行化 正确做法：至少回滚环上的一个事务（如 T1）
========================================================================== 定理校验：2PL 产生的历史必定冲突可串行化（优先图无环） ========================================================================== 随机 2PL 历史 4000 条，其中优先图有环的 = 0 条（定理断言应为 0） 结论：未发现反例，与 2PL 的可串行化定理一致。
说明：s6 中 T1 是’读后写’，T2 与 T3 都是盲写（不读直接写）—— T2 的 W(x) 随后被 T1 的 W(x) 覆盖，最终写者是 T3， T1 读到的仍是初始值，与串行序 T1;T2;T3 完全一致， 所以它是【视图可串行化】的；但在冲突等价的意义上， 历史里 W2(x) 先于 W1(x)，而串行序要求 W1(x) 先于 W2(x)， 两条边 1->2 与 2->1 同时存在 —— 冲突等价不成立。
【分布式机制透视】
- 这段程序模拟的是”历史回放式验证“：真实系统（如 SSI 的 PostgreSQL、CockroachDB 的验证器）不可能穷举串行顺序，而是增量维护依赖图并在检测到”危险结构”时回滚。本程序给出的是同一理论的可判定版本——它存在的意义是当裁判：任何并发控制协议声称自己可串行化，都可以用这个工具去检验它产生的历史。
exhaustive_2pl_check()的随机生成器落实了一条分布式调度纪律：锁的授予/阻塞决定”谁能前进”，而纪律本身（收缩阶段不再加锁）是协议的一部分。这正是分布式 2PL（跨站点的锁管理器 + 全局死锁检测）的本地版本。
【与理论的对应】
- 历史
s2（丢失更新）与s3（不一致检索）都被判”有环 ⇒ 冲突不可串行化”，与 19.2.6 的两张交错图一一对应； - 历史
s5给出一个 2PL 不可能产生的历史：它的两条冲突边方向相反，任何 2PL 调度都无法实现（因为 2PL 要求锁点单调，做不到”先放锁再加锁”)； - 历史
s6展示了 视图可串行化 ⊊ 冲突可串行化（盲写反例），解释了为什么 19.2.10 说”判定视图可串行化是 NP-完全的”，而工程上只做冲突可串行化； - 最后的定理校验输出
优先图有环的 = 0 条，是对 2PL ⇒ 冲突可串行化 的一次机器验证。
19.4.3 死锁演示与分布式死锁检测（含幻死锁）
"""deadlock.py -- 死锁检测三件套：
1) 集中式等待图（WFG）检测与牺牲者回滚
2) Chandy-Misra-Haas 分布式边追踪（edge chasing）算法
3) 幻死锁（phantom deadlock）的构造
`python3 deadlock.py` 直接运行。
"""
from collections import deque
# ==================== 第 1 部分：集中式等待图 ====================
def find_cycle(adj):
color, stack = {}, []
def dfs(u):
color[u] = 1
stack.append(u)
for v in sorted(adj.get(u, ())):
if color.get(v, 0) == 1:
return stack[stack.index(v):] + [v]
if color.get(v, 0) == 0:
r = dfs(v)
if r:
return r
stack.pop()
color[u] = 2
return None
for u in sorted(adj):
if color.get(u, 0) == 0:
r = dfs(u)
if r:
return r
return None
def centralized_demo():
print("=" * 74)
print("第 1 部分：集中式等待图（WFG）死锁检测")
print("=" * 74)
holds = {1: {'A'}, 2: {'B'}, 3: {'C'}} # 各事务当前持有的锁
waits = {1: ('B', 2), 2: ('C', 3), 3: ('A', 1)} # 事务 -> (想要的数据项, 持有者)
print("锁表：%s" % {t: sorted(s) for t, s in holds.items()})
print("等待：%s" % {t: "%s <- T%d" % (it, h) for t, (it, h) in waits.items()})
adj = {t: {h} for t, (_, h) in waits.items()}
print("等待图：%s" % " ".join("T%d->T%d" % (t, list(adj[t])[0]) for t in sorted(adj)))
cyc = find_cycle(adj)
print("DFS 检测结果：环 = %s => 死锁！" % "->".join("T%d" % t for t in cyc))
# 牺牲者选择：优先锁最少者，其次最年轻者
cands = sorted(set(cyc), key=lambda t: (len(holds[t]), -t))
victim = cands[0]
print("牺牲者选择：候选 %s；按（持有锁数, 越年轻越优先）排序 -> 牺牲者 = T%d"
% (["T%d(锁%d)" % (t, len(holds[t])) for t in sorted(set(cyc))], victim))
for it in sorted(holds[victim]):
owner = [t for t, (i, h) in waits.items() if h == victim and i == it]
for w in owner:
print(" 回滚 T%d：释放 %s -> T%d 的等待被满足" % (victim, it, w))
del waits[w]
del holds[victim]
waits.pop(victim, None)
adj = {t: {h} for t, (_, h) in waits.items()}
print("恢复后等待图：%s，再检测 -> %s"
% (adj, "仍有环" if find_cycle(adj) else "无环，死锁解除"))
print()
# ==================== 第 2 部分：CMH 边追踪 ====================
class CMHSite:
def __init__(self, sid):
self.sid = sid
self.waits = {} # 本地事务 -> 它正等待的事务集合
self.forwarded = set() # 消息合并/抑制：已转发过的 (initiator, sender, target)
self.reports = []
def add_wait(self, t, target):
self.waits.setdefault(t, set()).add(target)
def drop_wait(self, t):
self.waits.pop(t, None)
def cmh_demo(phantom=False):
print("=" * 74)
print("第 2 部分：Chandy-Misra-Haas 边追踪%s" % ("（含幻死锁场景）" if phantom else ""))
print("=" * 74)
owner = {1: 0, 2: 1, 3: 2} # 事务 -> 站点
sites = {0: CMHSite(0), 1: CMHSite(1), 2: CMHSite(2)}
edges = [(1, 2), (2, 3), (3, 1)] # T1 等 T2 等 T3 等 T1
for a, b in edges:
sites[owner[a]].add_wait(a, b)
print("等待边：%s 事务分布：T1@site0, T2@site1, T3@site2"
% " ".join("T%d->T%d" % e for e in edges))
q = deque([("PROBE", 1, 1, 2, owner[2], "site0"), # (类型, 发起者, 发送者, 目标, 目的站, 备注)
("PROBE", 1, 1, 2, owner[2], "T1 重传同一探测")]) # 故意重传，演示消息抑制
if phantom:
q.insert(2, ("EVENT", 2, 0, 0, 1, "T2 中止并释放全部锁（等待边 T1->T2 断开）"))
seq = 0
while q:
seq += 1
kind, i, j, k, dst, note = q.popleft()
if kind == "EVENT":
print("%2d. [事件] %s" % (seq, note))
sites[1].drop_wait(i) # T2 不再等待
sites[0].drop_wait(1) # T1 的等待随之结束
print(" site1 局部等待表变为 %s，site0 局部等待表变为 %s"
% (sites[1].waits, sites[0].waits))
continue
print("%2d. site%d 收到 PROBE(发起者=T%d, T%d -> T%d) %s"
% (seq, dst, i, j, k, "<%s>" % note if "重传" in note else ""))
if (i, j, k) in sites[dst].forwarded:
print(" 该探测已转发过 -> 抑制，不再重复发送（消息合并优化）")
continue
sites[dst].forwarded.add((i, j, k))
if k == i:
print(" *** T%d 收到由自己发起的探测回来了 => 检测到死锁！环 = T%d->...->T%d->T%d"
% (k, i, j, k))
sites[dst].reports.append(i)
continue
targets = sites[dst].waits.get(k, set())
if not targets:
print(" T%d 当前不在等待任何事务 -> 探测终止（该分支无环）" % k)
continue
for m in sorted(targets):
q.append(("PROBE", i, k, m, owner[m], "转发"))
print(" 转发 PROBE(发起者=T%d, T%d -> T%d) 给 site%d" % (i, k, m, owner[m]))
reported = set(x for s in sites.values() for x in s.reports)
print("检测结论：%s" % ("报告存在死锁，发起者为 T%d" % min(reported) if reported
else "未检测到死锁"))
if phantom:
print("真相：此刻全局等待边只剩 %s —— 环已被 T2 的中止打断，"
% sorted((a, b) for a, b in edges if a != 2 and b != 2))
print(" 但探测消息已经上路，于是报出了一个【不存在的死锁】= 幻死锁（phantom deadlock）。")
print()
if __name__ == "__main__":
centralized_demo()
cmh_demo(phantom=False)
cmh_demo(phantom=True)
print("=" * 74)
print("对比：集中式检测要收集全局 WFG（单点 + 通信开销）；边追踪把探测消息")
print(" 沿等待边推送，只有真正成环时才收到自己的探测消息；代价是每条新等待边")
print(" 都要发探测消息（O(边数)），而且异步系统下无法避免幻死锁 —— 只能用")
print(" 一致性全局快照（Chandy-Lamport）或给探测消息带时间戳来减少误报。")
【代码做什么？】
- 第 1 部分（集中式）：构造三事务环（$T_1$ 持 A 等 B、$T_2$ 持 B 等 C、$T_3$ 持 C 等 A），由锁表构造等待图，DFS 找到环，按”持有锁数少、更年轻”的启发式选出牺牲者 $T_3$，回滚它（释放锁 + 让等待者继续），再检测一次确认无环——完整走了一遍算法 19.3.2。
- 第 2 部分（分布式 CMH 边追踪）：把三个事务分布到三个站点，用消息队列模拟探测消息的传播：
- $S_0$ 发
PROBE(1,1,2)→ $S_1$ 转发PROBE(1,2,3)→ $S_2$ 转发PROBE(1,3,1)→ $S_0$ 发现 $k=i$ ⇒ 报告死锁； - 故意重传同一条探测：第二次到达时命中
forwarded集合 ⇒ 消息抑制，不再重复转发（这就是讲义强调的消息合并优化）； - 在”幻死锁”模式里，往消息队列中间插入一个事件：$T_2$ 中止并释放全部锁。此后探测消息照旧传播、照着过期的等待信息继续转发，最终仍然报出死锁——而此刻全局等待边只剩 $T_3 \to T_1$，环已经不存在了。
- $S_0$ 发
实际运行结果（节选）
========================================================================== 第 1 部分：集中式等待图（WFG）死锁检测 ========================================================================== 锁表：{1: [‘A’], 2: [‘B’], 3: [‘C’]} 等待：{1: ‘B <- T2’, 2: ‘C <- T3’, 3: ‘A <- T1’} 等待图：T1->T2 T2->T3 T3->T1 DFS 检测结果：环 = T1->T2->T3->T1 => 死锁！ 牺牲者选择：候选 [‘T1(锁1)’, ‘T2(锁1)’, ‘T3(锁1)’]；按（持有锁数, 越年轻越优先）排序 -> 牺牲者 = T3 回滚 T3：释放 C -> T2 的等待被满足 恢复后等待图：{1: {2}}，再检测 -> 无环，死锁解除
========================================================================== 第 2 部分：Chandy-Misra-Haas 边追踪 ========================================================================== 等待边：T1->T2 T2->T3 T3->T1 事务分布：T1@site0, T2@site1, T3@site2
- site1 收到 PROBE(发起者=T1, T1 -> T2)
转发 PROBE(发起者=T1, T2 -> T3) 给 site2 - site1 收到 PROBE(发起者=T1, T1 -> T2)
该探测已转发过 -> 抑制，不再重复发送（消息合并优化） - site2 收到 PROBE(发起者=T1, T2 -> T3)
转发 PROBE(发起者=T1, T3 -> T1) 给 site0 - site0 收到 PROBE(发起者=T1, T3 -> T1)
*** T1 收到由自己发起的探测回来了 => 检测到死锁！环 = T1->…->T3->T1 检测结论：报告存在死锁，发起者为 T1
========================================================================== 第 2 部分：Chandy-Misra-Haas 边追踪（含幻死锁场景） ========================================================================== 等待边：T1->T2 T2->T3 T3->T1 事务分布：T1@site0, T2@site1, T3@site2
- site1 收到 PROBE(发起者=T1, T1 -> T2)
转发 PROBE(发起者=T1, T2 -> T3) 给 site2 - site1 收到 PROBE(发起者=T1, T1 -> T2)
该探测已转发过 -> 抑制，不再重复发送（消息合并优化） - [事件] T2 中止并释放全部锁（等待边 T1->T2 断开） site1 局部等待表变为 {}，site0 局部等待表变为 {}
- site2 收到 PROBE(发起者=T1, T2 -> T3)
转发 PROBE(发起者=T1, T3 -> T1) 给 site0 - site0 收到 PROBE(发起者=T1, T3 -> T1)
*** T1 收到由自己发起的探测回来了 => 检测到死锁！环 = T1->…->T3->T1 检测结论：报告存在死锁，发起者为 T1 真相：此刻全局等待边只剩 [(3, 1)] —— 环已被 T2 的中止打断， 但探测消息已经上路，于是报出了一个【不存在的死锁】= 幻死锁（phantom deadlock）。
========================================================================== 对比：集中式检测要收集全局 WFG（单点 + 通信开销）；边追踪把探测消息 沿等待边推送，只有真正成环时才收到自己的探测消息；代价是每条新等待边 都要发探测消息（O(边数)），而且异步系统下无法避免幻死锁 —— 只能用 一致性全局快照（Chandy-Lamport）或给探测消息带时间戳来减少误报。
【分布式机制透视】
- 消息如何传递：用一个
deque当作”网络 + 各站点的收件箱”，每条消息携带(发起者, 发送者, 目标, 目的站)。真实系统里这就是三个进程之间的 socket 通信；把消息队列换成socketpair/multiprocessing.Queue即可获得”真并发”的版本，但语义完全相同（异步、乱序、可能延迟）。 - 每个站点的状态：
waits（局部等待图出边）+forwarded（已转发探测集合）。关键设计点是”站点只知道自己那部分等待关系”——这正是分布式死锁检测困难的根源：没有任何单点拥有全局视野。 - 时序如何体现幻死锁：事件插入的位置就是”消息在途时系统状态发生变化”。程序故意让
PROBE(1,2,3)在 $T_2$ 中止之后才到达 $S_2$——由于 $S_2$ 对本地的waits[3] = {1}判断仍然成立，它照常转发，于是 $S_0$ 收到了”绕回来的探测”。这段时序就是幻死锁的定义。 - 对应真实系统：Cassandra 等系统在跨节点事务/锁上使用”超时 + 探测消息”的组合；实际的分布式数据库（Spanner、CockroachDB）更倾向于尽量避免跨节点持锁（用时间戳/TrueTime 定序），从根本上绕开分布式死锁检测这个难题。
【与理论的对应】
| 代码位置 | 对应本章理论 |
|---|---|
find_cycle() + select_victim() | 算法 19.3.2 的检测与牺牲者选择 |
| 环上三人各持 1 把锁 ⇒ 按”最年轻”选 $T_3$ | 19.2.16 牺牲者启发式（锁最少 → 最年轻） |
PROBE(i, j, k) 沿 waits 转发 | 算法 19.3.4 的边追踪规则 |
if k == i: report_deadlock | “探测绕回发起者 ⇒ 存在环” |
forwarded 命中即丢弃 | 消息合并/抑制优化 |
| 幻死锁场景 | 19.2.17 的难点：等待信息来自不同时刻，异步系统无法区分”曾经有环”与”现在有环” |
| 程序结尾引出的对策 | 用一致性全局快照（Chandy-Lamport，见 Snapshots 一章）或给探测消息带时间戳 |
19.5 性能与可扩展性分析
19.5.1 四类并发控制方法总览
| 维度 | 2PL（严格 / 保守） | OCC（Kung-Robinson） | 时间戳排序（+ Thomas） | MVCC（+ SI / SSI） |
|---|---|---|---|---|
| 何时检测冲突 | 访问前：加锁的那一刻 | 提交时：验证阶段 | 每次读写时：即时比较时间戳 | 读写时判断可见性；写-写冲突在写/提交时判 |
| 是否加锁 | 是（S/X 锁，严格变体持到提交） | 读不加锁；写阶段需短暂临界区 | 完全不加锁 | 读不加锁；写需要版本锁/写锁（first-updater-wins） |
| 是否可能死锁 | 会（2PL 的固有问题）；保守 2PL/时间戳预防可消除 | 不会（无持有并等待） | 不会（等待边单向 ⇒ 无环） | 不会（多为无等待的版本判定；少数实现有写锁等待） |
| 是否可能饥饿 | 基本不会（FIFO 排队；牺牲者老化） | 理论上可能（反复验证失败） | 会（老事务被反复回滚，见 19.4.1 场景 D） | 理论可能（写冲突反复失败），实践中靠优先级缓解 |
| 并发度 | 中～低（写-写、读-写都互斥；保守 2PL 最低） | 高（读阶段完全无阻塞） | 高（无等待）、但回滚会降低有效并发 | 最高（读不阻塞写、写不阻塞读） |
| 适合场景 | 冲突高、需要确定性行为、事务较短 | 冲突低、读多写少、内存数据库 | 冲突中低、需要全局定序（分布式友好）、事务短 | 读多写少、长读事务、需要高并发（几乎所有现代 DBMS） |
| 不适合场景 | 长事务、热点数据（锁等待与死锁爆炸） | 高冲突（回滚风暴）、长事务（验证期长） | 长事务（时间戳老化）、随机重试的高冲突 | 写密集 + 需要可串行化（SI 要加 SSI 检测） |
| 额外开销 | 锁表内存 + 上下文切换 + 死锁检测 | 私有工作区/读写集内存 + 重做成本 | 全局时间戳分配 + 回滚重做 | 多版本存储 + 垃圾回收（vacuum） |
| 正确性标准 | 冲突可串行化（严格变体另有 ACA） | 冲突可串行化（验证条件） | 冲突可串行化（Thomas 规则下为视图可串行化） | SI 不是可串行化；SI+SSI 才是 |
| 真实系统 | MySQL InnoDB 的锁路径、SQL Server、Spanner（悲观锁 + TrueTime） | VoltDB/H-Store、Google Percolator、Redis WATCH/MULTI | 早期 TSO 数据库、Spanner 的 TrueTime 定序思想、DynamoDB/Cassandra 的 LWW | PostgreSQL（+SSI）、MySQL InnoDB、Oracle、SQL Server、CockroachDB |
19.5.2 吞吐 vs 冲突率：悲观与乐观的交叉点
并发控制的性能几乎完全由冲突率（单位时间内两个活跃事务访问同一数据项的强度）决定。把吞吐（TPS）画成冲突率的函数，会看到两条方向相反的曲线：
吞吐
(TPS)
▲
│ ╲ 悲观（2PL）
│ ╲ ╱
│ ╲ ╱
│ ╲ ╱
│ ╲ ╱
│ ╲ ╱
│ OCC/TO ╲ ╱
│ （乐观） ╲ ╱
│ ╲ ╱
│ ✕ ← 交叉点：冲突率在此附近时两者相当
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲ ← 乐观协议：冲突率高时
│ ╱ ╲ 回滚风暴，吞吐断崖式下跌
└──────────────────────────────────────────────► 冲突率
低冲突区（乐观更好） 高冲突区（悲观更好）
为什么曲线会交叉：
· 低冲突：乐观协议的"没有锁开销 + 没有死锁处理"占优；
悲观协议白白花了加锁/解锁/阻塞唤醒的钱。
· 高冲突：悲观协议的锁等待是"有序排队"，虽然慢但结果都是有用功；
乐观协议的回滚是"全部白做 + 重做"，冲突越激烈白做越多，
还可能引发连锁回滚 ⇒ 有效吞吐急剧下降。
交叉点的位置取决于：事务长度、冲突窗口（读阶段有多长）、回滚成本。
—— 内存数据库（窗口短）交叉点偏向高冲突侧；
磁盘数据库（窗口长）交叉点明显偏低，因此传统 DBMS 长期以 2PL 为主。
用 19.4.1 场景 D 的实验数据印证（8 个事务读改写热点数据项，hot 越小冲突越激烈）：
| hot（热点项数） | 8（低冲突） | 4 | 2 | 1（高冲突） |
|---|---|---|---|---|
| 严格 2PL：回滚 / 死锁次数 | 2 / 2 | 4 / 4 | 9 / 9 | 6 / 6 |
| OCC：回滚次数 | 2 | 6 | 10 | 20 |
| TO（新时间戳）：回滚次数 | 2 | 8 | 16 | 22 |
| TO（沿用原时间戳）：回滚次数 | 280（未完成 2） | 280（未完成 4） | 285（未完成 5） | 285（未完成 6） |
读法：冲突越激烈，乐观协议（OCC/TO）的回滚次数单调上升，而 2PL 的回滚次数基本平稳——2PL 把代价转化为”等待”（时间变长但工作不浪费），乐观协议把代价转化为”重做”（时间与 CPU 双重浪费）。最后一行的 TO 则展示了饥饿：几百次回滚之后仍有事务没能完成（活锁）。
19.5.3 延迟（Latency）的三个来源
| 协议 | 延迟构成 | 特点 |
|---|---|---|
| 2PL | 执行时间 + 锁等待时间（排队）+ 可能的死锁检测与回滚重做 | 延迟方差大：抢到锁的事务很快，排在后面的事务可能等很久（尤其热点数据项）。长尾延迟（tail latency） 是 2PL 的著名问题 |
| OCC | 执行时间（快，无阻塞）+ 验证时间 + 失败时的重做（期望值要按失败率加权） | 低冲突时延迟最低且方差小；高冲突时重做使平均延迟迅速上升，且尾部可能反复重试 |
| 时间戳排序 | 执行时间 + 检查时间；严格 TO 有”等更早写者”的等待 | 无锁、延迟可预测；但回滚重做同样计入 |
| MVCC | 读操作无等待（读快照版本）；写操作需版本判定/加写锁 | 读延迟几乎等于纯计算时间——这是 MVCC 被广泛采用的核心原因；代价是版本存储与 GC |
一条工程经验：“平均延迟”往往不是问题，”P99 延迟”才是。2PL 的锁等待会让少数事务等很久，OCC 的反复重试也会拉高尾延迟，而 MVCC 的读路径几乎没有尾延迟——这是现代数据库普遍采用 MVCC 的直接原因。
19.5.4 可扩展性（Scalability）
- 单机：锁管理器是集中式数据结构（哈希表 + 每对象等待队列），所有事务都要碰它 ⇒ 高核数下锁管理器本身就是瓶颈（真实系统的做法是分区锁管理器：按数据项哈希把锁表分片，减少争用）。
- 分布式 2PL：锁必须跨站点持有，于是
- 一次加锁 = 一次跨网络往返（延迟从几十纳秒变成几十微秒～毫秒）；
- 事务持锁期间跨站点，导致全局死锁检测成为必需（19.2.17），检测本身又要通信；
- 站点故障会让”持锁者”消失，需要额外的锁恢复协议（这与 Lecture 20 的 2PC 强耦合）。 结论：2PL 在分布式下延迟高、协调开销大，但在需要强一致的场景仍被采用（如 Spanner，用悲观锁 + TrueTime 来换取可串行化）。
- 分布式 OCC：读阶段完全本地（无通信），但验证阶段需要全局协调——要检查”我的读集是否与并发提交的写集相交”，就必须把读写集发到某个仲裁者或做分布式求交，通信量 $O(\vert RS\vert +\vert WS\vert )$ 且验证点是新的瓶颈。它适合”冲突很少 + 事务很短”的场景（因此常见于内存数据库与单分区事务）。
- 分布式 TO：不需要锁协调，但需要全局时间戳分配器（中心分配器是瓶颈；常用”各站点一次预领一个时间戳区间”来摊销），此外”等待更早的写者”在跨站点时也会引入延迟。
- MVCC 的可扩展性：读路径天然可扩展（各副本/各节点读自己的快照），写路径取决于版本冲突检测策略；瓶颈从”锁争用”转移到版本存储与 GC（CockroachDB、TiDB 用”按时间戳的 MVCC + 范围分区”把 GC 也做成分布式的）。
19.5.5 死锁的代价
- 检测频率的二次代价：检测太频繁 ⇒ CPU 花在遍历等待图上（每 $T_{poll}$ 一次 $O(V+E)$）；太稀疏 ⇒ 事务白等（每个死锁事务浪费”死锁存活时间 × 其资源占用”）。经验做法是以”事务平均执行时间”为周期，或”最近没有事务提交”时立刻检测。
- 牺牲者的重做浪费：被回滚的事务已经消耗的 CPU、I/O 全部作废，还要重新执行一次。因此牺牲者选择偏好”回滚成本最小“的事务（工作量少、持有锁少、最年轻）。
- 级联回滚的放大效应：基本 2PL 下，一个事务回滚可能迫使读过它脏数据的事务一并回滚，形成回滚风暴；这就是严格 2PL（X 锁持到提交）成为默认选择的原因——它用”多持一会儿锁”换掉了”连锁回滚”这个尾部风险。
- 对比：Wait-Die/Wound-Wait 用额外的回滚换取”完全不检测死锁”，把”偶发的检测开销”换成了”常态的回滚开销”；Raft/Paxos 式的共识系统则进一步把冲突消灭在”单点定序”层面（见共识与复制各章）。
19.5.6 MVCC 的空间开销与垃圾回收
- 版本存储：每个数据项的多个版本都要占空间。若一个长事务（快照）长时间不结束，它之后产生的所有旧版本都不能回收——PostgreSQL 的”表膨胀（table bloat）”与 “long-running transaction 阻塞 vacuum” 就是这样来的。
- 回收（vacuum / purge）：只有当”没有任何活跃快照可能读到某个旧版本“时才能回收它。工程上因此要：
- 限制事务与快照的最长存活时间（
idle_in_transaction_session_timeout、快照上限）； - 后台定期 vacuum（PostgreSQL 的 autovacuum）；
- 用版本水位线（low-water mark） 批量回收（CockroachDB/TiDB 的 GC TTL）。
- 限制事务与快照的最长存活时间（
- 取舍：MVCC 用空间与 GC 复杂度换来了”读不阻塞写、写不阻塞读”的延迟优势——在存储便宜、延迟昂贵的今天，这笔交易通常是划算的。
19.5.7 真实系统中的实践
| 系统 | 并发控制方案 | 关键点 |
|---|---|---|
| PostgreSQL | MVCC + 多级隔离；SERIALIZABLE 用 SSI | 默认 READ COMMITTED；SSI 通过跟踪 rw-依赖检测”危险结构”，读不阻塞写；需要 autovacuum 对抗表膨胀 |
| MySQL InnoDB | MVCC + next-key lock（行锁 + 间隙锁） | 默认 REPEATABLE READ；用间隙锁防幻读，代价是更多锁与死锁；SELECT ... FOR UPDATE 显式加锁 |
| Oracle / SQL Server | MVCC（回滚段 / 行版本） | READ COMMITTED 默认；提供 SI 级别的 SNAPSHOT 隔离；长事务导致的 undo 空间压力是运维重点 |
| Spanner | 悲观锁 + 2PC + TrueTime 时间戳 | 用”跨数据中心持锁 + Paxos 组”实现外部一致性（线性一致）的可串行化；为此接受较高的写延迟 |
| CockroachDB | MVCC + 串行化验证（＋分布式事务） | 事务读快照、提交时验证；按范围分区与时间戳水位线做 GC；冲突时回滚重试（客户端可见的 RETRY） |
| VoltDB / H-Store | OCC + 分区 + 确定性执行 | 单分区事务在内存中顺序执行，彻底避免锁与死锁；跨分区事务代价高 |
| Redis（事务） | 乐观锁（WATCH + MULTI/EXEC） | 没有回滚：EXEC 时若被监视的键被改过则整体放弃，由客户端重试 |
一句话总结这条链路：单机靠锁，高并发靠 MVCC，低冲突靠乐观，跨机房靠”时间戳 + 共识”。
19.6 关键要点
- 本讲黄金法则：可串行化是并发控制的正确性标准；2PL 用锁与两阶段保证它但会死锁，OCC 用推迟验证保证它但会回滚，时间戳排序用全局顺序保证它但会饥饿，MVCC 用多版本让读不阻塞写但需要额外处理写偏斜。 四者不是”谁更好”，而是”用哪种代价换取可串行化”。
- 串行化定理是整章的骨架：历史冲突可串行化 $\iff$ 优先图无环。所有协议的正确性证明都是”证明自己产生的历史优先图无环”：2PL 靠锁点单调，Wait-Die/Wound-Wait 与 TO 靠时间戳沿等待边严格单调，OCC 靠验证条件保证冲突按验证序排列。
- 安全性与活性是两件事：死锁破坏的是活性（大家都做不完），不可串行化破坏的是安全性（做完了但结果错）。2PL 牺牲活性换安全性，因此”2PL 保证可串行化”与”2PL 会死锁”毫无矛盾。
- 冲突的定义是一切的起点：读-读不冲突，读-写、写-读、写-写冲突；这个纯语法化的定义把语义问题变成了图论问题，也正是”读写锁能提高并发度”的根本原因。
- 隔离级别是旋钮，不是开关：大多数系统默认 READ COMMITTED；需要可串行化时优先考虑 SSI（读不阻塞写），而不是直接退化到 2PL。SI 不等于可串行化，写偏斜就是它的漏洞。
- 分布式把每个问题都放大一档：局部等待图 ≠ 全局等待图，因此有幻死锁；”检测需要一致性快照”这一条与快照一章的结论完全一致——异步系统里没有免费的全局判断。
19.7 常见陷阱与注意事项
- 把 ACID 的 C 当成 CAP 的 C。
- 错在哪：ACID 的 C 是”不违反业务完整性约束”（应用语义），CAP 的 C 是”多副本对外表现如单一副本（线性一致）”（复制语义）。
- 正确做法：看到”一致性”先问是哪个层次；用事务保证不了副本一致，用复制协议也保证不了业务不变量（后者必须由应用在事务里显式维护）。
- 用”最终数据状态”判断可串行化。
- 错在哪：不一致检索（19.2.6 异常二）最终落盘的数据可能恰好正确（转账两条写都生效了），但某个事务读到的总额是错的。只比最终状态会漏判。
- 正确做法：按定义比较”所有对象 + 所有事务“的结果——包括每个事务读到的值。19.4.1 的
serial_runs()同时比较最终状态与读值，正是为此。
- 以为”加了锁就万事大吉”（忽略两阶段的必要性）。
- 错在哪：没有”收缩阶段不得再加锁”的纪律，锁本身并不能保证可串行化——一个事务可以放了 A 的锁再拿 B 的锁，从而产生循环的冲突边。
- 正确做法：要么两阶段（2PL），要么用时间戳/验证来定序；”锁 + 任意加解锁顺序”不是并发控制协议。
- 以为 2PL 能防死锁，或以为死锁意味着不可串行化。
- 错在哪：2PL 只约束加/放锁次序，完全不管”持有并等待”，因此死锁必然可能（19.2.14）；而死锁是活性问题，与历史的可串行化无关。
- 正确做法：把两件事分开解决——用严格/保守 2PL、Wait-Die/Wound-Wait 或超时来对付死锁，用 2PL 本身来保证可串行化。
- OCC 验证里照抄教科书条件 2 而不检查”写阶段是否落在我的读阶段内”。
- 错在哪：若 $T_j$ 的写阶段正好落在 $T_i$ 的读阶段内部，$T_i$ 可能读到了 $T_j$ 覆盖前的过时值，而条件 2 只检查写-写，会漏掉它 ⇒ 可串行性被破坏。
- 正确做法：把时间戳分配在验证阶段（验证顺序即时间戳序），并且只要”对方的提交落在我的读区间内”就一律走条件 3 的强检查（本讲代码即如此）。
- 以为快照隔离（SI）就安全了。
- 错在哪：SI 只检测写-写冲突，对读-写冲突视而不见，”医生值班”式的写偏斜会让两个事务都提交并破坏约束（19.2.21）。
- 正确做法：真正需要可串行化时用 SSI（PostgreSQL 的
SERIALIZABLE），或把约束做成显式冲突（例如先SELECT ... FOR UPDATE锁住被检查的行，把读写冲突转成写写冲突）。
- 用局部等待图判断全局死锁。
- 错在哪：每个站点只看到自己那部分等待关系，局部有环不等于全局有环，而信息的时序错位会造成幻死锁（19.2.17：环在探测消息传播期间被打断，却仍被报告）。
- 正确做法：要么依赖一致性全局快照（Chandy-Lamport）构造全局等待图，要么接受误报但保证回滚安全（牺牲者本来就可能白回滚），并给探测消息带时间戳/状态确认。
- 把 Thomas 写规则当成”任何冲突的写都能忽略”。
- 错在哪：Thomas 规则只适用于”过时写“——即 $\mathrm{TS}(T) < \mathrm{write\_TS}(x)$、已经有更年轻的版本存在、且此后没有任何事务可能读到它的情形。若错把”$\mathrm{TS}(T) < \mathrm{read\_TS}(x)$”（更年轻的事务读过）也当成可忽略，就会产生不可重复读。
- 正确做法：严格区分两条规则——读过就打回（回滚），写得过时才能忽略；实现上还要正确处理”未提交写者（pending）”，否则会把未提交的写误当已提交而错误忽略。
19.8 思考题（带答案）
题 1（推演题） 给定并发历史
\[H = R_1(x)\; W_2(x)\; R_2(y)\; W_3(y)\; R_3(z)\; W_1(z)\](1) 画出优先图并判定是否冲突可串行化；(2) 若不可串行化，最少回滚几个事务才能得到一个可串行化的历史？回滚哪个（些）最方便？(3) 该历史能否被严格 2PL 产生？
答案： (1) 逐对检查冲突操作（不同事务、同一数据项、至少一个写）：
- $R_1(x)$ 与 $W_2(x)$ ⇒ 边 $T_1 \to T_2$；
- $R_2(y)$ 与 $W_3(y)$ ⇒ 边 $T_2 \to T_3$；
- $R_3(z)$ 与 $W_1(z)$ ⇒ 边 $T_3 \to T_1$。
优先图为 $T_1 \to T_2 \to T_3 \to T_1$，有环 ⇒ 冲突不可串行化。
(2) 环上任意一个事务回滚即可破环（回滚一个，保留其他两个）。例如回滚 $T_2$ 后，剩下的冲突只有 $R_3(z)$ 与 $W_1(z)$ ⇒ 边 $T_3 \to T_1$，无环；等价串行序为 $T_3, T_1$。若按”回滚工作量最少”选，则应比较各事务已执行的操作数与持有的锁数；本题三者规模相同，通常再按”最年轻者优先”选 $T_3$。
(3) 不能。严格 2PL 的历史必然冲突可串行化（算法 19.3.1 的锁点单调性证明），而 $H$ 有环。反过来说，如果某个调度器产出了 $H$，那么它一定违反了 2PL——例如 $T_1$ 必须先拿 $x$ 再拿 $z$（$R_1(x) \to W_1(z)$，是”先加锁后加锁”），$T_2$ 必须先拿 $x$（被 $T_1$ 挡住）、再拿 $y$，$T_3$ 需要 $y$ 和 $z$——把三条链串起来会得到一个”某事务在收缩之后又加锁”的矛盾。
题 2（”直观但错误的想法”） 某同学说：“既然可串行化的定义是’结果等价于某个串行执行’，那我只要在每个事务结束时对比一下最终数据状态是否正确，不对就回滚重做，不就能保证可串行化了吗？这样实现起来最简单，还不用加锁。” 这个想法错在哪？
答案：错在把”结果”理解成了”最终落盘的数据”。可串行化的定义要求对所有对象和所有事务的结果一致，其中读操作返回的值同样是”结果”的一部分：
- 反例就是不一致检索：转账事务的两条写最终都落盘了，数据看起来完全正确；但并发执行的对账事务读到了”钱已转出、尚未到账”的中间状态，打印出的总额少了 100。此时”最终状态正确”成立，可串行化却不成立。
- 更深一层：这种”事后靠最终状态回滚”的方案无法知道该回滚谁。若两个事务都提交了、结果错了，撤销哪一个？撤销任一都会丢掉一个本应生效的更新（丢失更新场景里，$x=80$ 既不是 70 也不是任何串行结果，撤销 $T_1$ 或 $T_2$ 都需要它自己的旧值，而旧值可能已被覆盖）。
- 正确做法：要么在执行过程中阻止冲突（锁/时间戳），要么在提交时用读集+写集判断冲突（OCC 验证），要么用多版本让读者看到一致快照（MVCC）。判据必须是”冲突操作的顺序”，而不是”最终数据的模样”。
题 3（推演题） 两个事务 $T_1$（时间戳 10）与 $T_2$（时间戳 20）。$T_1$ 已持有 $A$ 上的 X 锁，$T_2$ 已持有 $B$ 上的 X 锁。现在 $T_1$ 请求 $B$、$T_2$ 请求 $A$。请分别给出 Wait-Die 与 Wound-Wait 的处置，并说明为什么两者都不会死锁；再说明如果回滚后重新分配新时间戳会破坏哪一条性质。
答案：
- Wait-Die：$T_2$（20，更年轻）请求 $A$（被更老的 $T_1$ 持有）⇒ $T_2$ 死亡：回滚 $T_2$、释放 $B$、用原时间戳 20 重启。$T_1$（10，更老）请求 $B$ ⇒ $T_1$ 等待（此时 $B$ 已因 $T_2$ 回滚而释放，$T_1$ 立即获得）。$T_2$ 重启后重新竞争。
- Wound-Wait：$T_2$（更年轻）请求 $A$ ⇒ $T_2$ 等待。$T_1$（更老）请求 $B$ ⇒ $T_1$ 伤害 $T_2$：强行回滚 $T_2$，$T_1$ 拿走 $B$。$T_2$ 用原时间戳 20 重启。
- 为什么都不会死锁：Wait-Die 中只有”更老者”会等待，因此每条等待边 $T_i \to T_j$ 满足 $\mathrm{TS}(T_i) < \mathrm{TS}(T_j)$，沿边严格递增；Wound-Wait 中只有”更年轻者”会等待，等待边沿时间戳严格递减。两种情况都是严格偏序，环上会出现 $\mathrm{TS}(T) < \mathrm{TS}(T)$ 的矛盾 ⇒ 等待图无环 ⇒ 无死锁。
- 如果回滚后重新分配更大的时间戳：等待边的单调方向不再是一致同向的（例如一个刚重启的事务拿到了比原持有者更大的时间戳，它可能在某处等待、在别处又让别人等待），“无死锁”的证明失效，两者都可能出现死锁；同时 Wait-Die 的”不饥饿”论证也失效（重启后变”更年轻”，可能被不断更新的老事务反复杀死）。这也解释了为什么这两种协议实现时都强调”沿用原时间戳重启“。
题 4（计算题） 某 OCC 实现中，事务按下列时刻执行（时间单位为调度步；时间戳在进入验证阶段时分配，即验证顺序）。请判断哪些事务能提交：
| 事务 | 开始读 | 读阶段结束（=验证并写） | 读集 RS | 写集 WS |
|---|---|---|---|---|
| $T_1$ | 1 | 3 | $\{x\}$ | $\{x\}$ |
| $T_2$ | 5 | 8 | $\{x\}$ | $\{y\}$ |
| $T_3$ | 2 | 9 | $\{y\}$ | $\{z\}$ |
答案：按验证顺序为 $T_1$（第 3 步）、$T_2$（第 8 步）、$T_3$（第 9 步），故 $\mathrm{TS}(T_1) < \mathrm{TS}(T_2) < \mathrm{TS}(T_3)$。
- $T_1$：
committed为空 ⇒ 通过，安装 $x$，commit_step = 3。 - $T_2$：与 $T_1$ 比较——$T_1$ 的
commit_step = 3 < T_2.start = 5⇒ 满足条件 1（$T_1$ 完全早于 $T_2$）⇒ 无需检查 ⇒ 通过，安装 $y$，commit_step = 8。 - $T_3$：依次比较
- 与 $T_1$：$T_1$ 的
commit_step = 3不小于 $T_3.start = 2$（条件 1 不满足）；$T_1.read\_end = 3 < T_3.read\_end = 9$ 且 $T_1.commit\_step = 3$ 不大于 $T_3.read\_end = 9$ ⇒ 走条件 3 强检查：$(RS_3 \cup WS_3) \cap WS_1 = \{y,z\} \cap \{x\} = \varnothing$ ⇒ 通过； - 与 $T_2$：$T_2$ 的
commit_step = 8不小于 $T_3.start = 2$；$T_2.read\_end = 8 < T_3.read\_end = 9$ 且 $T_2.commit\_step = 8$ 不大于 9 ⇒ 仍走条件 3 强检查：$(RS_3 \cup WS_3) \cap WS_2 = \{y,z\} \cap \{y\} = \{y\} \neq \varnothing$ ⇒ 冲突 ⇒ $T_3$ 回滚。
- 与 $T_1$：$T_1$ 的
- 结论：$T_1$ 与 $T_2$ 提交，$T_3$ 回滚重试。原因是 $T_3$ 在读阶段读到了 $y$，而 $T_2$ 在 $T_3$ 的读阶段内部（第 8 步 ≤ 第 9 步）提交了对 $y$ 的写——$T_3$ 读到的 $y$ 可能已经过时，因此必须回滚。这正是 19.2.19 补充说明强调的”写阶段落在我的读区间内 ⇒ 必须强检查”的情形：如果这里错误地按条件 2 只查写-写（$WS_3 \cap WS_2 = \{z\} \cap \{y\} = \varnothing$）就放行，就会产出一个读到过时值的不可串行化历史。