并发控制（Concurrency Control）

1. 基本概念与问题背景

1.1 并发控制的核心问题

问题描述：多个事务 $T_{1}, T_{2}, . . ., T_{n}$ 同时访问数据库中的数据项，可能违反一致性约束
经典示例：
- 约束：所有实习生工资相等
- $T_{1}$ ：给每个实习生加 $1000
- $T_{2}$ ：将每个实习生的工资翻倍
- 若这两个事务交错执行，结果将不符合约束

1.2 解决方案概述

朴素方案：串行化执行（"serial schedule"）
- 缺点：效率太低，尤其涉及外部客户端和 I/O 操作时
高级方案：定义隔离级别（isolation levels）
- 提供关于事务之间影响的不同保证
- 在一致性和性能之间取得平衡

1.3 SQL 标准隔离级别

隔离级别	脏读	不可重复读	幻读	特点
Read Uncommitted	是	是	是	最弱隔离，最高并发
Read Committed	否	是	是	常用默认级别
Repeatable Read	否	否	是	可重复读取
Serializable	否	否	否	最强隔离，等价于串行执行

重要提示：许多商业数据库默认不使用可串行化，有些甚至无法支持它。

2. 可串行化调度

2.1 基本定义

可串行化调度：调度的执行结果等价于某个串行调度的结果
两种等价性：
- 冲突等价：通过交换非冲突操作可以互相转换
- 视图等价：读写关系相同

3. 冲突可串行化（Conflict Serializability）

3.1 基本概念

冲突操作定义

两个操作冲突当且仅当：

它们属于不同事务
访问同一数据项
至少有一个是写操作

具体包括：

$r_{i} (A)$ 和 $w_{j} (A)$
$w_{i} (A)$ 和 $r_{j} (A)$
$w_{i} (A)$ 和 $w_{j} (A)$

冲突等价定义

调度 $S_{1}$ 和 $S_{2}$ 是冲突等价的，如果可以通过一系列非冲突操作的交换将 $S_{1}$ 转换为 $S_{2}$ 。

3.2 判定方法：构建前驱图 $P (S)$

构图规则

节点：每个事务 $T_{i}$ 是图中的一个节点
边：若存在冲突操作 $p_{i} (A)$ 在 $q_{j} (A)$ 之前，则添加边 $T_{i} \to T_{j}$
判定：图无环 ⟺ 调度是冲突可串行化的

算法步骤

输入：调度 S
输出：是否冲突可串行化

1. 初始化前驱图 P(S)，节点为所有事务
2. 遍历调度中的每对操作 (op1, op2)：
   if op1 和 op2 冲突且 op1 在 op2 之前:
       添加边 T_i → T_j
3. 检查图中是否存在环
4. 返回结果：无环则冲突可串行化

实例分析

给定调度： $S = w_{3} (A), w_{2} (C), r_{1} (A), w_{1} (B), r_{1} (C), w_{2} (A), r_{4} (A), w_{4} (D)$

步骤1：找出冲突操作对

操作对	冲突类型	添加边
$w_{3} (A)$ → $r_{1} (A)$	w-r	$T_{3} \to T_{1}$
$w_{3} (A)$ → $w_{2} (A)$	w-w	$T_{3} \to T_{2}$
$w_{2} (C)$ → $r_{1} (C)$	w-r	$T_{2} \to T_{1}$
$r_{1} (A)$ → $w_{2} (A)$	r-w	$T_{1} \to T_{2}$

步骤2：构建前驱图

$T_{3} \to T_{1}$
$T_{3} \to T_{2}$
$T_{2} \to T_{1}$
$T_{1} \to T_{2}$ ← 与上一条形成环

结论：存在环 $T_{1} \to T_{2} \to T_{1}$ ，因此不是冲突可串行化的。

3.3 理论基础

定理：

P (S) 无环 ⟺ S 是冲突可串行化的

证明思路：

充分性：若 $S$ 冲突可串行化，则存在等价串行调度，其前驱图无环
必要性：若 $P (S)$ 有环，则不存在拓扑排序，无法构造等价串行调度

4. 视图可串行化（View Serializability）

4.1 基本概念

视图等价定义

两个调度 $S_{1}$ 和 $S_{2}$ 是视图等价的，当且仅当满足以下三个条件：

读源一致性：若 $T_{i}$ 在 $S_{1}$ 中读取了 $T_{j}$ 对数据项 $A$ 的写入，则在 $S_{2}$ 中也如此
初值一致性：若 $T_{i}$ 在 $S_{1}$ 中读取了数据项 $A$ 的初始值，则在 $S_{2}$ 中也如此
终值一致性：若 $T_{i}$ 在 $S_{1}$ 中是最后写入数据项 $A$ 的事务，则在 $S_{2}$ 中也如此

视图可串行化定义

若调度 $S$ 与某个串行调度视图等价，则 $S$ 是视图可串行化的。

4.2 判定方法：构建标签前驱图 $L P (S)$

算法步骤

输入：调度 S
输出：是否视图可串行化

1. 添加虚拟事务：
   - T_b：对所有数据项执行初始写操作
   - T_f：对所有数据项执行最终读操作

2. 构建标签前驱图：
   对每个读操作 r_j(A)：
   - 找到其读取的写操作 w_i(A)
   - 添加边 T_i → T_j（标签0）
   - 对其他写同一数据项的事务 T_k，添加相应标签边

3. 尝试选择边的组合使图无环
4. 若存在无环组合，则视图可串行化

标签边规则

设存在 $w_{i} (A) \to r_{j} (A)$ ，且有其他事务 $T_{k}$ 也写入 $A$ ：

条件	添加的标签边
$T_{i} \neq T_{b}$ 且 $T_{j} \neq T_{f}$	$T_{k} \to T_{i}$ (标签p)， $T_{j} \to T_{k}$ (标签p)
$T_{i} = T_{b}$ 且 $T_{j} \neq T_{f}$	$T_{j} \to T_{k}$ (标签p)
$T_{i} \neq T_{b}$ 且 $T_{j} = T_{f}$	$T_{k} \to T_{i}$ (标签p)

实例分析

给定调度： $Q = r_{1} (A), w_{2} (A), w_{1} (A), w_{3} (A)$

步骤1：添加虚拟事务

Q^{'} = w_{b} (A), r_{1} (A), w_{2} (A), w_{1} (A), w_{3} (A), r_{f} (A)

步骤2：分析读写关系

$r_{1} (A)$ 读取 $w_{b} (A)$ 的值 → $T_{b} \to T_{1}$ (标签0)
$r_{f} (A)$ 读取 $w_{3} (A)$ 的值 → $T_{3} \to T_{f}$ (标签0)

步骤3：构建标签前驱图 基础边： $T_{b} \to T_{1}$ ， $T_{3} \to T_{f}$ 标签边选择可以使图保持无环。

结论： $Q$ 是视图可串行化的，但不是冲突可串行化的（因为包含"盲写"）。

4.3 "无用写"和"盲写"的影响

无用写（Useless Write）

定义：没有被任何事务读取的写操作
特点：不影响最终状态，但在视图可串行化中仍需考虑其对读操作的影响
示例：
```
S = w1(A) r2(A) w2(B) r1(B) w3(A) w3(B)
```
- 如果只关心最终状态，可以忽略 T1 和 T2
- 如果关注事务的读取行为（即 view equivalence），则不能忽略这些事务

定义：事务写入一个数据项但没有先读取它
重要结论：所有不是冲突可串行化但却是视图可串行化的调度都包含盲写
数学证明要点：
- 假设调度 S1 是视图可串行化的，并且没有任何盲写
- 存在一个串行调度 Ss，使得 S1 与 Ss 视图等价
- 若 S1 中存在 w1(A) 后 r2(A)，则在 Ss 中也必须是 T1 先执行
- 因此，在这种情况下，视图可串行化和冲突可串行化是等价的

4.4 视图可串行化的复杂性

判定复杂度：NP-完成问题
实际应用：相较于冲突可串行化，判断更复杂，不适合实时检测
理论价值：在理论研究和某些特定场景中仍有应用价值

4.5 与冲突可串行化的关系

特性	冲突可串行化	视图可串行化
包含关系	是视图可串行化的子集	包含所有冲突可串行化调度
盲写处理	不允许	允许
判定复杂度	$O (n^{2})$	NP-完全
实际应用	广泛使用	理论研究为主
实现方法	2PL等锁协议	特殊验证算法

5. 并发控制协议

5.1 两阶段锁协议（2PL）

基本规则

规则1：良好形成：事务必须在操作前加锁，操作后解锁
规则2：合法调度：一次只有一个事务可以持有某个对象的锁
规则3：两阶段：事务分为增长阶段（获取锁）和缩减阶段（释放锁）

锁类型与兼容性

基本锁类型：

共享锁（Shared Lock, S）：允许多个事务同时读取
排他锁（Exclusive Lock, X）：独占访问，用于写操作
升级锁（Upgrade Lock, U）：防止死锁，可升级为排他锁

兼容性矩阵：

持有锁\请求锁	S	X	U
S	✅	❌	✅
X	❌	❌	❌
U	❌	❌	❌

记录级锁 vs 页面级锁存

记录级锁（Record-Level Locking）：控制对具体数据项的并发访问
页面级锁存（Page-Level Latching）：保护物理存储结构，在页面操作期间短暂持有
区别：锁用于事务级别的并发控制，锁存用于物理层面的数据结构保护

正确性证明

定理：遵循2PL协议的调度是冲突可串行化的。

证明思路：

假设存在环 $T_{i} \to T_{j} \to . . . \to T_{i}$
环中每条边表示冲突操作，需要相应的锁
由2PL性质，存在锁的获取和释放时间约束
推导出矛盾，证明不存在环

5.2 多粒度锁

锁层次结构

数据库
  ├── 表
      ├── 页
          ├── 记录

意向锁

IS（Intention Shared Lock）：准备在下层加共享锁
IX（Intention Exclusive Lock）：准备在下层加排他锁
SIX（Shared + Intention Exclusive Lock）：当前层共享，下层可能排他

扩展兼容性矩阵：

持有锁\请求锁	IS	IX	S	SIX	X
IS	✅	✅	✅	✅	❌
IX	✅	✅	❌	❌	❌
S	✅	❌	✅	❌	❌
SIX	✅	❌	❌	❌	❌
X	❌	❌	❌	❌	❌

5.3 死锁处理

死锁检测

等待图（Wait-for Graph）：
- 每个节点表示一个事务
- 边 $T_{i} \to T_{j}$ 表示事务 $T_{i}$ 等待事务 $T_{j}$ 释放锁
- 当图中出现环时，表示存在死锁
- 解决方案：选择一个事务作为"受害者"进行回滚

死锁预防策略

1. 资源排序（Resource Ordering）

方法：对所有资源进行编号，事务只能按编号递增顺序请求锁
缺点：现实中难以实现，因为事务可能无法提前知道需要哪些资源

2. 超时机制（Timeout）

方法：如果事务等待时间超过预设阈值（如L秒），则回滚该事务
特点：简单但不够灵活，难以选择合适的L值

3. Wait-Die 机制

规则：事务具有时间戳（ts），只有当 ts(Ti) < ts(Tj) 时，Ti 才能等待 Tj，否则 Ti 死亡并重试
防饥饿：如果事务死亡后使用原始时间戳重试，则不会发生饥饿

4. Wound-Wait 机制

规则：如果 ts(Ti) < ts(Tj)，则 Ti 可以"伤害" Tj（即让 Tj 回滚），否则 Ti 等待
防饥饿：死亡事务使用原始时间戳重试，可以避免饥饿

死锁处理对比

方法	优点	缺点	适用场景
等待图检测	精确，无误杀	检测开销大	死锁频率低
超时机制	简单，开销小	可能误杀，参数难调	简单系统
Wait-Die	无死锁，防饥饿	可能过多回滚	读多写少
Wound-Wait	无死锁，防饥饿	可能过多回滚	写多读少

5.4 乐观并发控制

三阶段协议

读取阶段：事务读取数据并在私有工作空间中修改
验证阶段：检查是否与其他事务冲突
写入阶段：若验证通过，将修改写入数据库

适用场景

冲突概率较低
读操作远多于写操作
事务执行时间较短

6. 事务处理的高级主题

6.1 可恢复调度与级联回滚

级联回滚（Cascading Rollback）

定义：某个事务的回滚导致其他事务也必须回滚
产生原因：Tj 写入了数据项A，Ti 读取了A。如果 Tj 被中止，而 Ti 已经提交，则可能导致数据不一致

示例：

T1: w(A)
T2:      r(A) w(B)
T3:                r(B) commit
T1:                      abort  // 导致T2和T3都需要回滚

可恢复调度（Recoverable Schedule）

定义：如果一个事务 Ti 从另一个事务 Tj 读取数据，那么在 Ti 提交之前，Tj 必须已经提交
数学表达：若 Tj ⇒S Ti 且 Ci ∈ S，则 Cj <S Ci
目的：避免不一致状态，保证数据库的一致性

避免级联回滚（ACA, Avoids Cascading Aborts）

定义：事务只能读取已提交事务写入的数据
实现：严格两阶段锁（Strict 2PL） - 所有写锁在事务提交后才释放
优点：彻底避免级联回滚，简化恢复过程

调度类型层次关系

串行调度 ⊂ 冲突可串行化 ⊂ 视图可串行化 ⊂ ACA ⊂ 可恢复调度 ⊂ 所有调度

6.2 分布式事务处理

两阶段提交协议（2PC）

参与者：

协调者（Coordinator）：负责协调多个参与者的提交或中止操作
参与者（Participants）：执行实际的事务操作

协议流程：

阶段一：准备阶段（Prepare Phase）
- 协调者向所有参与者发送 PREPARE 消息
- 参与者执行事务操作，写入日志，但不提交
- 参与者回复 YES（准备好）或 NO（无法执行）
阶段二：提交阶段（Commit Phase）
- 如果所有参与者都回复 YES，协调者发送 COMMIT 消息
- 如果任何参与者回复 NO，协调者发送 ABORT 消息
- 参与者根据收到的消息执行相应操作

优缺点：

优点：保证分布式事务的原子性
缺点：可能出现阻塞，协调者失效时参与者无法决定

三阶段提交协议（3PC）

改进：

在2PC基础上引入超时机制和额外的准备阶段
减少阻塞风险，提高可用性
阶段：Can-Commit, Pre-Commit, Do-Commit

6.3 长事务处理

嵌套事务（Nested Transactions）

结构：事务内部可以包含子事务，形成树状结构
提交规则：
- 子事务可以独立提交或中止，不影响父事务
- 父事务提交时，所有子事务必须已提交
- 父事务中止时，所有子事务必须回滚
优点：提供更细粒度的控制，支持部分回滚

补偿事务（Compensation Transactions）

目的：用于撤销长事务的部分操作
特点：
- 补偿事务不能完全恢复数据库到原始状态
- 只能保证逻辑一致性，而非物理一致性
应用：适用于无法简单回滚的长时间运行的事务

Sagas

定义：一种处理长事务的方法，将长事务分解为多个短事务
组成：
- 每个步骤都有对应的补偿事务
- 语义原子性：要么执行所有步骤，要么执行所有补偿步骤
执行模式：
- 前向恢复：继续执行剩余步骤
- 后向恢复：执行已完成步骤的补偿操作

Saga示例：

预订旅行 = 预订机票 + 预订酒店 + 预订租车
补偿操作 = 取消机票 + 取消酒店 + 取消租车

6.4 恢复机制

日志记录与LSN

日志序列号（Log Sequence Number, LSN）：
- 每条日志记录有一个唯一编号
- 页面上的LSN用于判断是否需要应用日志中的操作
- 支持幂等性（idempotent）操作

逻辑操作日志

内容：包括插入、删除、更新等逻辑操作
特点：
- Undo/Redo操作需要幂等性
- 支持更高级别的恢复操作
- 便于理解和调试

恢复过程

策略：

重建崩溃时刻的状态：
- 找到最后一个检查点 Ck，确定活跃事务集合 ac
- 从检查点开始扫描日志，应用Redo操作
回滚未提交的事务：
- 扫描日志反向应用Undo操作
- 对于未完全回滚的事务，继续读取更早的日志记录并执行Undo

示例日志：

| chk pt
| ...
| lsn=21 T1 a1 p1
| ...
| lsn=27 T1 a2 p2
| ...
| lsn=29 T1 a3 p3
| ...
| lsn=31 T1 a3-1 p3    // Undo a3
| ...
| lsn=35 T1 a2-1 p2    // Undo a2
| ...

关键原则：

已提交事务被前滚并写入数据库
未提交事务被回滚且不写入数据库

6.5 多层视图与物理实现

逻辑操作与物理操作分离

逻辑层面：处理事务的语义操作（插入、删除、更新）
物理层面：处理页面分裂、索引维护等底层操作
优点：提高并发性和恢复效率

检查点机制

目的：将内存中的脏页写入磁盘，减少恢复时间
类型：
- 静态检查点：暂停所有事务活动
- 动态检查点：在事务运行过程中执行
- 模糊检查点：允许部分脏页延迟写入

7. 总结与对比

7.1 可串行化类型对比

特性	冲突可串行化	视图可串行化
严格程度	更严格	相对宽松
盲写支持	❌	✅
判定复杂度	多项式时间	NP-完全
实用性	高（广泛应用）	低（主要用于理论）
实现方法	2PL等锁协议	特殊验证算法

7.2 并发控制方法对比

方法	优点	缺点	适用场景
两阶段锁	理论完备，易实现	可能死锁，并发度有限	通用场景
乐观控制	高并发，无死锁	冲突时代价高	读多写少
时间戳排序	无死锁，去中心化	可能饥饿，回滚频繁	分布式环境

7.3 事务处理模式对比

模式	适用场景	优点	缺点
短事务	OLTP系统	简单，高并发	功能受限
长事务	批处理，工作流	功能完整	并发度低
嵌套事务	复杂应用	灵活控制	实现复杂
Saga模式	微服务架构	高可用性	一致性较弱

7.4 实践建议

生产环境：优先选择冲突可串行化 + 严格两阶段锁协议
高并发场景：考虑乐观并发控制或降低隔离级别
长事务场景：使用Saga模式 + 补偿事务
分布式系统：采用两阶段提交或最终一致性模型
特殊需求：可考虑视图可串行化的理论优势

8. 关键计算方法速查

问题	解决方法	关键步骤
判断冲突可串行化	构建前驱图 $P (S)$	找冲突操作 → 画图 → 检查环
判断视图可串行化	构建标签前驱图 $L P (S)$	加虚拟事务 → 标签边 → 选择无环组合
设计锁协议	分析数据访问模式	确定粒度 → 选择锁类型 → 处理死锁
优化并发性能	权衡一致性与性能	分析冲突概率 → 选择协议 → 调整参数
设计恢复策略	日志与检查点结合	确定检查点频率 → 设计日志格式

8.1 记忆口诀

冲突操作：r-w, w-r, w-w 必冲突，r-r 永不冲突
判定串行化：冲突看环路，视图看标签，前驱图无环，可串行化成
锁协议：两阶段锁保冲突，严格锁防级联，多粒度提效率
死锁处理：检测用图环，预防靠排序，超时简单行，时间戳无锁
恢复机制：检查点定期做，日志记录要详细，前滚已提交，回滚未完成

8.2 常见错误提醒

串行化判断：不要混淆冲突等价和视图等价的概念
锁协议：注意区分锁（lock）和锁存（latch）的用途
死锁预防：Wait-Die和Wound-Wait容易搞混方向
恢复过程：区分物理恢复和逻辑恢复的适用场景
分布式事务：考虑网络分区对一致性的影响

并发控制（Concurrency Control） ​

1. 基本概念与问题背景 ​

1.1 并发控制的核心问题 ​

1.2 解决方案概述 ​

1.3 SQL 标准隔离级别 ​

2. 可串行化调度 ​

2.1 基本定义 ​

3. 冲突可串行化（Conflict Serializability） ​

3.1 基本概念 ​

冲突操作定义 ​

冲突等价定义 ​

3.2 判定方法：构建前驱图 P(S) ​

构图规则 ​

算法步骤 ​

实例分析 ​

3.3 理论基础 ​

4. 视图可串行化（View Serializability） ​

4.1 基本概念 ​

视图等价定义 ​

视图可串行化定义 ​

4.2 判定方法：构建标签前驱图 LP(S) ​

算法步骤 ​

标签边规则 ​

实例分析 ​

4.3 "无用写"和"盲写"的影响 ​

无用写（Useless Write） ​

盲写（Blind Write） ​

4.4 视图可串行化的复杂性 ​

4.5 与冲突可串行化的关系 ​

5. 并发控制协议 ​

5.1 两阶段锁协议（2PL） ​

基本规则 ​

锁类型与兼容性 ​

记录级锁 vs 页面级锁存 ​

正确性证明 ​

5.2 多粒度锁 ​

锁层次结构 ​

意向锁 ​

5.3 死锁处理 ​

死锁检测 ​

死锁预防策略 ​

1. 资源排序（Resource Ordering） ​

2. 超时机制（Timeout） ​

3. Wait-Die 机制 ​

4. Wound-Wait 机制 ​

死锁处理对比 ​

5.4 乐观并发控制 ​

三阶段协议 ​

适用场景 ​

6. 事务处理的高级主题 ​

6.1 可恢复调度与级联回滚 ​

级联回滚（Cascading Rollback） ​

可恢复调度（Recoverable Schedule） ​

避免级联回滚（ACA, Avoids Cascading Aborts） ​

调度类型层次关系 ​

6.2 分布式事务处理 ​

两阶段提交协议（2PC） ​

三阶段提交协议（3PC） ​

6.3 长事务处理 ​

嵌套事务（Nested Transactions） ​

补偿事务（Compensation Transactions） ​

Sagas ​

6.4 恢复机制 ​

日志记录与LSN ​

逻辑操作日志 ​

恢复过程 ​

6.5 多层视图与物理实现 ​

逻辑操作与物理操作分离 ​

检查点机制 ​

7. 总结与对比 ​

7.1 可串行化类型对比 ​

7.2 并发控制方法对比 ​

7.3 事务处理模式对比 ​

7.4 实践建议 ​

8. 关键计算方法速查 ​

8.1 记忆口诀 ​

8.2 常见错误提醒 ​

并发控制（Concurrency Control）

1. 基本概念与问题背景

1.1 并发控制的核心问题

1.2 解决方案概述

1.3 SQL 标准隔离级别

2. 可串行化调度

2.1 基本定义

3. 冲突可串行化（Conflict Serializability）

3.1 基本概念

冲突操作定义

冲突等价定义

3.2 判定方法：构建前驱图 $P (S)$

构图规则

算法步骤

实例分析

3.3 理论基础

4. 视图可串行化（View Serializability）

4.1 基本概念

视图等价定义

视图可串行化定义

4.2 判定方法：构建标签前驱图 $L P (S)$

算法步骤

标签边规则

实例分析

4.3 "无用写"和"盲写"的影响

无用写（Useless Write）

盲写（Blind Write）

4.4 视图可串行化的复杂性

4.5 与冲突可串行化的关系

5. 并发控制协议

5.1 两阶段锁协议（2PL）

基本规则

锁类型与兼容性

记录级锁 vs 页面级锁存

正确性证明

5.2 多粒度锁

锁层次结构

意向锁

5.3 死锁处理

死锁检测

死锁预防策略

1. 资源排序（Resource Ordering）

2. 超时机制（Timeout）

3. Wait-Die 机制

4. Wound-Wait 机制

死锁处理对比

5.4 乐观并发控制

三阶段协议

适用场景

6. 事务处理的高级主题

6.1 可恢复调度与级联回滚

级联回滚（Cascading Rollback）

可恢复调度（Recoverable Schedule）

避免级联回滚（ACA, Avoids Cascading Aborts）

调度类型层次关系

6.2 分布式事务处理

两阶段提交协议（2PC）

三阶段提交协议（3PC）

6.3 长事务处理

嵌套事务（Nested Transactions）

补偿事务（Compensation Transactions）

Sagas

6.4 恢复机制

日志记录与LSN

逻辑操作日志

恢复过程

6.5 多层视图与物理实现

逻辑操作与物理操作分离

检查点机制

7. 总结与对比

7.1 可串行化类型对比

7.2 并发控制方法对比

7.3 事务处理模式对比

7.4 实践建议

8. 关键计算方法速查

8.1 记忆口诀

8.2 常见错误提醒