13. 并发控制

1. Motivation (动机)

• 事前控制：我们不能等到调度执行完了再检查它对不对（那太晚了）。我们需要一种协议 (Protocol)，强制事务遵守，从而保证生成的调度本质上就是可串行化的。

• 权衡 (Trade-off)：

  • 优点：保证数据一致性 (Consistency) 和隔离性。

  • 缺点：限制了并发度，可能导致 死锁 (Deadlock) 或 饿死 (Starvation)。

---

2. Concepts (核心概念)

2.1 锁的基本模式 (Lock Modes)

事务在访问数据前必须先申请锁。

• Exclusive (X) 排他锁/写锁：持有 X 锁的事务既可以读也可以写。

• Shared (S) 共享锁/读锁：持有 S 锁的事务只能读。

锁兼容性矩阵 (Compatibility Matrix)：

• 口诀：“X 锁不仅排外，还排内；只有 S 和 S 能共存。”

  • 只要有人加了 X 锁，其他人都不能加任何锁。

2.2 多粒度锁 (Multiple Granularity)

允许以不同大小的粒度（如 数据库 表 行）锁定数据，形成树形结构。

• 意向锁 (Intention Locks)：为了告诉上层节点“我的子孙节点正在被锁定”。

  • IS (Intention-Shared)：打算在下层加 S 锁。

  • IX (Intention-Exclusive)：打算在下层加 X 锁。

  • SIX (Shared + IX)：当前节点加 S 锁（读整个表），同时允许在下层个别行加 X 锁（改某几行）。

• 加锁顺序：从根到叶 (Root-to-Leaf)。

• 解锁顺序：从叶到根 (Leaf-to-Root)。

2.3 死锁与饿死

• Deadlock (死锁)：循环等待 (Circular Wait)。A 等 B，B 等 A，大家都动不了。

• Starvation (饿死)：不公平。某个事务总是被插队，或者总是被选为“受害者”回滚，永远无法完成。

---

3. Protocols (核心协议) —— ★★★ 考试重点

3.1 基于锁的协议 (2PL Family)

这是并发控制的核心。请务必区分这三种变体：

协议名称	规则 (Rule)	核心性质 (Properties)
2PL (两阶段锁定)	分为 增长阶段 (只能加锁) 和 缩减阶段 (只能解锁)。 严禁解锁后再加锁。并且严格的要求，锁之间保持互斥。	✅ 保证冲突可串行化。 ❌ 可能死锁。 ❌ 可能级联回滚 (Cascading Rollback)。
Strict 2PL (严格 2PL)	所有的 排他锁 (X) 必须持有直到事务 Commit/Abort。	✅ 避免级联回滚 (Cascadeless)。 ✅ 保证可恢复性。
Rigorous 2PL (强 2PL)	所有锁 (S 和 X) 都必须持有直到事务 Commit/Abort。	✅ 最容易实现。 ✅ 序列化顺序 = 提交顺序。

锁转换 (Lock Conversion)：

• 升级 (Upgrade)：S X (只能在增长阶段)。

• 降级 (Downgrade)：X S (只能在缩减阶段)。

这个表格非常关键，它是数据库并发控制的考点。光看定义很抽象，我来通过一个具体的“银行转账与查询”的例子，带你跑一遍这三个协议，你立刻就懂了。

---

场景设置

假设有两个事务：

• (修改者)：读取账户 A (S锁)，然后修改账户 A (X锁)。最后提交。

• (读取者)：读取账户 A。

我们需要关注的核心区别是： 什么时候释放锁？ 以及 这会导致什么后果？

---

1. 普通 2PL (两阶段锁定) —— “急着释放”

规则：只要进入缩减阶段（不再申请新锁），就可以释放锁了，不用等提交。

• 过程：

  1. 申请 A 的 X锁，修改了余额（比如从 100 改成 200）。

  2. 觉得自己改完了，后面也没别的操作了，于是立刻释放 A 的锁 (Unlock A)。

  3. 注意：此时 还没有 Commit！

  4. 趁虚而入，申请 A 的 S锁，读到了 200。

  5. 突然， 系统崩溃了，或者回滚了 (Abort)，余额变回 100。

• 后果：

  • 读到的 200 是个“鬼数据”（脏读）。

  • 因为 回滚了， 也必须跟着回滚。这就是 级联回滚 (Cascading Rollback)。

  • 评价：虽然并发度高（别人能插队进来），但不安全，容易连累别人。

---

2. Strict 2PL (严格 2PL) —— “写锁拿稳”

规则：写锁 (X) 必须死死攥在手里直到提交；但 读锁 (S) 可以提前扔掉。

• 过程：

  1. 申请 A 的 X锁，修改余额为 200。

  2. 想释放锁？不行！ 协议规定：这是 X 锁，必须等到 Commit 才能放。

  3. 想读 A？被阻塞 (Blocked)，只能干等。

  4. 执行 Commit (数据落盘，变为永久)。

  5. 释放 A 的 X 锁。

  6. 终于获得锁，读到了 200。

• 后果：

  • 读到的一定是已经提交的数据。消灭了脏读，也就避免了级联回滚。

  • 区别点：如果 手里还有一个 B 的 S锁 (读锁)，它是可以在 Commit 之前提前释放 B 的，让别人去读 B。

  • 评价：这是大多数数据库系统的默认选择，平衡了安全性和灵活性。

---

3. Rigorous 2PL (强 2PL) —— “全部拿稳”

规则：不管 写锁 (X) 还是 读锁 (S)，通通必须攥到提交那一刻。

• 过程：

  1. 读取 B (持有 S锁)，修改 A (持有 X锁)。

  2. 想提前释放 B 的读锁让别人看一眼？不行！

  3. 想提前释放 A 的写锁？更不行！

  4. 所有锁一直拿到 Commit 的那一瞬间，全部同时释放。

• 后果：

  • 绝对安全，逻辑最简单（不需要区分 X 还是 S，提交时一把梭全放开）。

  • 但并发度最低（别人想读 B 都得等你彻底干完活）。

  • 评价：实现最容易，且事务提交的顺序就等于串行化的顺序。

---

一图胜千言 (总结对比)

为了方便记忆，你可以想象这三个协议是三种不同性格的人：

协议	性格人设	对话旁白	结局
2PL	急性子	“我活儿干完了，虽然还没签字画押(Commit)，但锁先还给你吧，大家抓紧时间！”	容易出事，害得别人读了脏数据要一起返工。
Strict 2PL	严谨派	“我改过的东西(X锁)必须等签字(Commit)后才能给你看；但我只看了一眼的东西(S锁)可以先还你。”	安全，不会连累别人。（最常用）
Rigorous 2PL	强迫症	“只要是我手里的东西，不管改没改，不等到最后签字那一刻，谁也别想碰！”	最安全，但大家排队时间最长。

考试解题技巧：

• 如果题目问 “Avoid Cascading Rollback” (避免级联回滚) -> 选 Strict 2PL。

• 如果题目问 “Easier to implement” (易于实现) 或 “Commit order = Serialization order” -> 选 Rigorous 2PL。

3.2 死锁处理 (Deadlock Handling)

A. 死锁预防 (Prevention) —— 基于时间戳

系统基于事务开始的时间戳 (Timestamp) 决定优先级。

设定： 是老事务（时间戳小）， 是新事务（时间戳大）。

策略	场景 1: 老抢新 (T_old​→T_young​)	场景 2: 新抢老 (T_young​→T_old​)	记忆口诀 (老事务视角)
Wait-Die (非抢占)	Wait (老事务等)	Die (新事务死/回滚)	“老人很佛系” (老人愿意等，年轻人碰壁就死)
Wound-Wait (抢占)	Wound (老事务杀掉新事务)	Wait (新事务等)	“老人很霸道” (老人直接抢，年轻人乖乖排队)

B. 死锁检测 (Detection) —— 等待图法

• Wait-for Graph (等待图)：

  • 节点 = 事务。

  • 边 = 正在等待 释放资源。

• 判定：图中有环 (Cycle) 存在死锁。

C. 死锁恢复 (Recovery)

1. Select Victim (选受害者)：选回滚代价最小的。

2. Rollback (回滚)：尽量只回滚一部分，够打破死锁就行。

3. Starvation (防饿死)：如果同一个事务老是被选为 Victim，它的优先级必须提升（cost 必须包含回滚次数）。

---

4. Example (综合习题详解)

场景：基于 Slide 33 的调度 。

: Lock_X(A) Unlock(A) Commit.

: 在 Unlock(A) 之后，立即 Lock_X(A) 并 Read(A)。此时 尚未 Commit。

详细分析步骤：

Q1: Is S conflict serializable? (S 是冲突可串行化的吗？)

• 方法：画 优先图 (Precedence Graph)。

• 分析：检查所有冲突操作的顺序。

• 结论：Yes。优先图中没有环。

Q2: Is S a cascading or cascadeless schedule? (S 是级联还是无级联？)

• 方法：检查是否存在“读取未提交数据 (Dirty Read)”。

• 事实：

  1. Unlock(A) (释放了锁，但没提交)。

  2. Lock_X(A) 并读取了 A。

  3. 这意味着 读到了 的脏数据。

• 结论：Cascading (级联调度)。

  • 后果：如果 后来故障回滚， 必须跟着回滚。

Q3: Is S obey the 2PL protocol? (S 遵守标准 2PL 吗？)

• 方法：检查每个事务是否遵循“增长阶段 缩减阶段”且不走回头路（即解锁后不再加锁）。

• 事实：

  • 先加锁 A, B (增长)，然后解锁 A, B (缩减)。中间没有穿插。

  • 其他事务也符合此规律。

• 结论：Yes (遵守)。

Q4: Is S obey the Rigorous 2PL protocol? (S 遵守强 2PL 吗？)

• 方法：检查是否“所有锁都持有到了 Commit 时刻”。

• 事实：

  • 在 Commit 之前，就已经执行了 Unlock(A)。

  • 强 2PL 要求：Commit 之前严禁解锁。

• 结论：No (不遵守)。

---

5. Summary (复习要点)

1. 2PL vs Strict/Rigorous：

   • 普通 2PL：解锁早，并发高，但会脏读/级联回滚。

   • Strict/Rigorous：解锁晚（Commit 时），并发低，但安全（无级联）。

2. 死锁预防口诀：

   • Wait-Die: 老人等 (Wait)。

   • Wound-Wait: 老人杀 (Wound)。

3. 等待图：有环 = 死锁。