并发控制

问题的产生

多用户数据库系统（如飞机订票系统、银行系统）允许多个用户同时使用，特点：在同一时刻并发运行的事务数可达成千上万个。

多事务执行方式

方式	说明	特点
(1) 串行执行	每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行	不能充分利用系统资源，发挥数据库共享资源的特点
(2) 交叉并发方式（Interleaved Concurrency）	单处理机系统中，并行事务的并行操作轮流交叉运行	不是真正的并行，但能减少处理机空闲时间，提高系统效率
(3) 同时并发方式（Simultaneous Concurrency）	多处理机系统中，每个处理机可以运行一个事务，实现真正的并行运行	受制于硬件环境，需要更复杂的并发控制机制

事务并发执行带来的问题

会产生多个事务同时存取同一数据的情况
可能会存取和存储不正确的数据，破坏事务一致性和数据库的一致性

DBMS必须提供并发控制机制。并发控制机制是衡量一个DBMS性能的重要标志之一。

一、并发控制概述（12.1）

1.1 并发控制机制的任务

对并发操作进行正确调度
保证事务的隔离性
保证数据库的一致性

1.2 并发操作带来的数据不一致性

R(x)：读数据x；W(x)：写数据x

1. 丢失修改（Lost Update）—— "写-写冲突"

两个事务T1和T2读入同一数据并修改，T2的提交结果破坏了T1提交的结果，导致T1的修改被丢失。

     T1              T2
① R(A)=16
②                R(A)=16
③ A←A-1
   W(A)=15
④                            A←A-1
                             W(A)=15
              ↑ 丢失修改 ↑

2. 脏读（Dirty Read）—— "读-写冲突"

事务T1修改某一数据并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销——T2读到的数据与数据库中的数据不一致，是"脏"数据（不正确的数据）。

     T1               T2
① R(C)=100
   C←C*2
   W(C)=200                      ← T1将C修改为200
②                R(C)=200        ← T2读到C为200（脏数据）
③ ROLLBACK
   C恢复为100                    ← T1撤销，C恢复原值100

3. 不可重复读（Non-repeatable Read）—— "读-写冲突"

事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。

     T1               T2
① R(A)=50
   R(B)=100                       ← T1读取B=100
   求和=150
②                R(B)=100
                 B←B*2
                 W(B)=200         ← T2将B修改为200
③ R(A)=50
   R(B)=200                       ← T1重读B，B已变为200
   和=250 (验算不对)               ← 与第一次读取值不一致

*4. 幻读（Phantom Row）

事务T1读取数据后，事务T2执行插入或删除操作，使T1无法再现前一次读取结果：

T1按条件读取某些数据记录后，T2删除了其中部分记录 → T1再次读取发现某些记录消失了
T1按条件读取某些数据记录后，T2插入了一些记录 → T1再次读取发现多了一些记录

1.3 数据不一致性的本质

由于并发操作破坏了事务的隔离性。并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性。

1.4 并发控制的主要技术

封锁（Locking） ← 商用DBMS普遍采用
时间戳（Timestamp）
乐观方法（Optimistic scheduler）
多版本并发控制（MVCC）

二、事务的隔离级别（12.2）

并发控制越严格，事务的隔离性就越强，数据的一致性就越有保障，但系统的效率也会随之下降。不同的应用场景对数据一致性的要求不相同。

2.1 SQL标准定义的四种隔离级别

SQL标准定义了四种隔离级别，由低到高分别是：

级别	隔离级别	说明	默认使用
1	读未提交（READ UNCOMMITTED）	允许一个事务读取另一个未提交事务正在修改的数据
2	读已提交（READ COMMITTED）	只允许一个事务读其他事务已提交的数据	Oracle
3	可重复读（REPEATABLE READ）	一个事务开始读取数据后，其他事务就不能再对该数据执行UPDATE操作	MySQL
4	可串行化（SERIALIZABLE）	最高隔离级别，事务执行顺序是可串行化的

2.2 隔离级别与数据不一致性的关系

隔离级别	丢失修改	脏读	不可重复读	幻读
读未提交	✗	✗	✗	✗
读已提交	✓	✓	✗	✗
可重复读	✓	✓	✓	✗
可串行化	✓	✓	✓	✓

✗ = 可能出现，✓ = 可以避免

2.3 隔离级别选择原则

事务隔离级别并不是越高越好
应根据应用的特点和需求选择合适的事务隔离级别
隔离级别越高，一致性越好，但系统效率越低

2.4 MySQL实现说明

MySQL的InnoDB引擎才支持事务
可重复读（REPEATABLE READ）是MySQL默认的隔离级别
为了实现可重复读，MySQL采用了MVCC（多版本并发控制）的方式

三、封锁（12.3）

3.1 封锁的基本概念（12.3.1）

什么是封锁

封锁就是事务T在对某个数据对象（如表、记录等）操作之前，先向系统发出请求，对其加锁
加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象
封锁是实现并发控制的一个非常重要的技术

基本封锁类型

类型	别称	说明
排它锁（X锁，eXclusive Locks）	写锁	若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。保证其他事务在T释放A上的锁之前不能再读取和修改A
共享锁（S锁，Share Locks）	读锁	若事务T对数据对象A加上S锁，则其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。保证其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改

锁的相容矩阵

        T2
         │  X    S    -
T1  ─────┼──────────────
   X     │  N    N    Y
   S     │  N    Y    Y
   -     │  Y    Y    Y

Y = Yes（相容的请求），N = No（不相容的请求）

T1 \ T2	X锁	S锁	无锁
X锁	N	N	Y
S锁	N	Y	Y
无锁	Y	Y	Y

3.2 封锁协议（12.3.2 Locking Protocol）

封锁协议是对数据对象加锁时约定的规则（何时申请封锁、何时释放封锁）。封锁协议级别越高，一致性程度越高。

三级封锁协议

一级封锁协议

事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放（COMMIT或ROLLBACK）
特征：只有长写锁
可防止丢失修改，保证事务T可恢复
如果仅仅是读数据不对其进行修改，不需要加锁
不能保证可重复读和不读"脏"数据

二级封锁协议

一级封锁协议 + 事务T在读取数据R之前必须先对其加S锁，读完后方可释放
特征：长写锁 + 短读锁
除防止丢失修改外，还可进一步防止脏读
但由于读完数据后即可释放S锁，不能保证可重复读

三级封锁协议

一级封锁协议 + 事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放
特征：长读锁 + 长写锁
可防止丢失修改、读"脏"数据以及不可重复读

封锁协议小结

协议	X锁释放时机	S锁释放时机	不丢失修改	不脏读	可重复读	对应隔离级别
一级	事务结束	—	✓	✗	✗	读未提交
二级	事务结束	操作结束	✓	✓	✗	读已提交
三级	事务结束	事务结束	✓	✓	✓	可串行化

四、活锁和死锁（12.4）

封锁技术带来的新问题：死锁、活锁、饿死。

4.1 活锁（Live Lock）（12.4.1）

场景：

T1封锁了数据R
T2请求封锁R → 等待
T3也请求封锁R → 当T1释放R后，系统先批准T3的请求，T2继续等待
T4也请求封锁R → T3释放后系统又批准T4...
T2可能永远等待，这就是活锁

避免活锁：采用先来先服务（FCFS）的策略

当多个事务请求封锁同一数据对象时，按请求封锁的先后次序排队
该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁

4.2 死锁（Dead Lock）（12.4.2）

场景：

T1: lock R1 ──→ 请求 lock R2 (等待T2释放)
T2: lock R2 ──→ 请求 lock R1 (等待T1释放)
→ T1等待T2，T2等待T1，形成死锁（"死死拥抱" Deadly Embrace）

解决死锁的两类方法

方法	说明
1. 预防死锁	破坏产生死锁的条件
2. 死锁的诊断与解除	检测到死锁后撤销事务

方法一：预防死锁

产生死锁的原因：两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁。预防死锁就是要破坏产生死锁的条件。

(1) 一次封锁法

每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行
问题：降低系统并发度（扩大了封锁范围）；很难事先精确地确定每个事务所要封锁的数据对象

(2) 顺序封锁法

预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁
问题：维护成本高（数据对象极多且不断变化）；难以事先确定每个事务要封锁哪些对象

结论：操作系统中广为采用的预防死锁策略不很适合数据库特点。DBMS更普遍采用的是诊断并解除死锁的方法。

方法二：死锁的诊断与解除

死锁的诊断

(1) 超时法

如果一个事务的等待时间超过了规定的时限，就认为发生了死锁
优点：实现简单
缺点：有可能误判死锁；时限设置太长，死锁发生后不能及时发现

(2) 事务等待图法

事务等待图是一个有向图 G = (T, U)
- T：结点的集合，每个结点表示正运行的事务
- U：边的集合，每条边表示事务等待的情况
- 若T1等待T2，则从T1到T2有一条有向边
并发控制子系统周期性地（如每隔数秒）生成事务等待图
如果发现图中存在回路，则表示系统中出现了死锁

解除死锁

选择一个处理死锁代价最小的事务，将其撤销
释放此事务持有的所有的锁，使其它事务能继续运行下去

五、并发调度的可串行性（12.5）

5.1 基本概念

事务的调度：给定一组事务，其包含操作的执行顺序称为这组事务的调度
并发事务：给定任意两个事务，如果它们在执行时间上有重叠，且存在数据库中的某一个数据项，其中一个事务写该数据项，另一个事务读或写该数据项，则称这两个事务是并发事务
串行调度：如果在一个调度中，只有当上一个事务运行结束之后，才会开启下一个事务
串行调度是正确的调度（但资源利用率低）

5.2 可串行化调度（12.5.1）

可串行化（Serializable）调度：对于多个并发执行的事务的调度，当且仅当其结果与按某一次序串行执行这些事务时的结果相同
可串行性（Serializability）：是并发事务正确调度的准则
一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度

判断可串行化的枚举法

给定n个事务：

枚举该组事务所有可能的串行执行结果（n! 种）
按照该组事务的实际执行，获得执行后数据库的状态
比较实际执行结果与每一个串行执行结果

如果其中有一个符合，则说明实际执行是可串行化的。但复杂度 O(n!)，只有理论价值，无法用于指导实际系统设计。

示例

两个事务：T1 = 读B；A=B+1；写回A，T2 = 读A；B=A+1；写回B。设A、B初值均为2。

串行调度(a) [T1→T2]：结果 A=3, B=4 ✓
串行调度(b) [T2→T1]：结果 B=3, A=4 ✓
不可串行化调度（交叉执行导致结果与任何串行都不同） ✗
可串行化调度（交叉执行但结果等于串行调度(a)） ✓

5.3 冲突可串行化调度（12.5.2）

冲突可串行化：一个比可串行化更严格的条件，商用系统中的调度器采用

冲突操作：不同的事务对同一个数据的读写操作和写写操作：

Ri(x) 与 Wj(x) —— 事务Ti读x，Tj写x
Wi(x) 与 Wj(x) —— 事务Ti写x，Tj写x
其他操作是不冲突操作

冲突可串行化调度：

如果一个调度Sc在保证冲突操作次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc'，如果Sc'是串行的，则Sc为冲突可串行化调度

不能交换的操作：

不同事务的冲突操作
同一事务的两个操作

结论：冲突可串行化 → 一定是可串行化调度（充分条件，非必要条件）

反例：存在不满足冲突可串行化但仍可串行化的调度：

T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)
L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)（串行调度）
L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)（不满足冲突可串行化，但结果与L1相同，仍是可串行化的）

六、两段锁协议（12.6，Two-Phase Locking，2PL）

6.1 基本概念

DBMS普遍采用两段锁协议
理论上证明：使用两段封锁协议产生的是可串行化调度，从而保证调度的正确性

6.2 两段锁协议定义

指所有事务必须分两个阶段对数据项加锁和解锁：

在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
在释放一个封锁之后，事务不再申请和获得任何其他封锁

6.3 "两段"的含义

阶段	说明
第一阶段：扩展阶段	事务可以申请获得任何数据项上的任何类型的锁，但不能释放任何锁
第二阶段：收缩阶段	事务可以释放任何数据项上的任何类型的锁，但不能再申请任何锁

示例：

遵守2PL (Ti)：   Slock A → Slock B → Xlock C → Unlock B → Unlock A → Unlock C
                 |←—————— 扩展阶段 ——————→|←—————— 收缩阶段 ——————→|

不遵守2PL (Tj)： Slock A → Unlock A → Slock B → Xlock C → Unlock C → Unlock B
                 ↑ 释放A后继续申请B和C的锁，违反2PL

6.4 两段锁协议的性质

事务遵守两段锁协议是可串行化调度的充分条件，不是必要条件
若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议

6.5 两段锁协议与一次封锁法的关系

一次封锁法遵守两段锁协议
但遵守两段锁协议的事务可能发生死锁

6.6 两阶段封锁协议存在的问题

问题	说明	解决办法
问题1：死锁	遵守2PL的事务仍可能相互等待形成死锁	事前：死锁预防；事后：死锁检测
问题2：级联回滚	T1回滚导致已读取T1未提交数据的T2也必须回滚（T2出现脏读）	见下文

6.7 处理级联回滚

级联回滚示例：

T1: Xlock x → W1(x,100) → Unlock x → Rollback (A1)
T2:                Slock x(等待) → R2(x,100) → Commit2 → 被迫回滚
→ T2读到脏数据(100)，T1回滚导致T2必须回滚

解决方案：

协议	规则	严格程度
严格两阶段封锁协议	遵守2PL + 排它锁必须在事务提交之后才能释放	较严格
强严格两阶段封锁协议	遵守2PL + 事务提交之前不允许释放任何锁	最严格

七、封锁的粒度（12.7，自学）

7.1 封锁粒度（Granularity）

定义：封锁对象的大小
封锁的对象：
- 逻辑单元：属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等
- 物理单元：页（数据页或索引页）、物理记录等

7.2 选择封锁粒度的原则

封锁粒度与系统的并发度和并发控制开销密切相关：

封锁粒度	并发度	系统开销
越大	越小	越小
越小	越高	越大

示例1：若封锁粒度是数据页 → 事务T1修改元组L1必须对含L1的整页加锁，T2要修改同页L2则被阻塞 → 并发度低

示例2：若封锁粒度是元组 → T1和T2可以同时对L1和L2加锁，无需互相等待 → 并发度高

示例3：事务T3需要读取整个表 → 元组粒度需对每个元组加锁（开销极大），关系粒度只需一次加锁（开销小）

7.3 多粒度封锁（Multiple Granularity Locking）

定义：在一个系统中同时支持多种封锁粒度供不同事务选择

选择策略（同时考虑开销和并发度）：

事务类型	推荐封锁单位
处理多个关系的大量元组	数据库
处理大量元组	关系
只处理少量元组	元组

多粒度树

以树形结构表示多级封锁粒度，根结点是最大数据粒度，叶结点是最小数据粒度。

三级粒度树：      数据库 → 关系(R1...Rn) → 元组
四级粒度树：      数据库 → 分区 → 数据块 → 数据记录

多粒度封锁协议

允许多粒度树中的每个结点被独立地加锁
对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁

显式封锁和隐式封锁

类型	定义
显式封锁	直接加到数据对象上的封锁
隐式封锁	该数据对象没有独立加锁，由于其上级结点加锁而使该数据对象加上了锁

显式封锁和隐式封锁效果相同，检查封锁冲突时都要检查。

本章小结

并发操作带来的数据不一致性：丢失修改、脏读、不可重复读、幻读
SQL标准的四种隔离级别（低→高）：读未提交 → 读已提交 → 可重复读 → 可串行化
基本封锁类型：排它锁（X锁/写锁）和共享锁（S锁/读锁）
三级封锁协议提供不同程度的一致性保证
封锁引起的额外问题：
- 活锁 → 用先来先服务（FCFS）解决
- 死锁 → 预防（一次封锁法/顺序封锁法）或诊断与解除（超时法/等待图法）
可串行性是并发事务正确调度的准则；冲突可串行化是更严格且实用的判断条件
两段锁协议（2PL）：可串行化调度的充分条件，DBMS普遍采用
- 2PL的问题：死锁 + 级联回滚
- 改进：严格2PL / 强严格2PL
封锁粒度的选择在并发度和系统开销之间权衡；多粒度封锁提供灵活性

不同的DBMS提供的封锁类型、封锁协议、达到的系统一致性级别不尽相同，但依据的基本原理和技术是共同的。

并发控制 ​

问题的产生 ​

多事务执行方式 ​

事务并发执行带来的问题 ​

一、并发控制概述（12.1） ​

1.1 并发控制机制的任务 ​

1.2 并发操作带来的数据不一致性 ​

1. 丢失修改（Lost Update）—— "写-写冲突" ​

2. 脏读（Dirty Read）—— "读-写冲突" ​

3. 不可重复读（Non-repeatable Read）—— "读-写冲突" ​

*4. 幻读（Phantom Row） ​

1.3 数据不一致性的本质 ​

1.4 并发控制的主要技术 ​

二、事务的隔离级别（12.2） ​

2.1 SQL标准定义的四种隔离级别 ​

2.2 隔离级别与数据不一致性的关系 ​

2.3 隔离级别选择原则 ​

2.4 MySQL实现说明 ​

三、封锁（12.3） ​

3.1 封锁的基本概念（12.3.1） ​

什么是封锁 ​

基本封锁类型 ​

锁的相容矩阵 ​

3.2 封锁协议（12.3.2 Locking Protocol） ​

三级封锁协议 ​

一级封锁协议 ​

二级封锁协议 ​

三级封锁协议 ​

封锁协议小结 ​

四、活锁和死锁（12.4） ​

4.1 活锁（Live Lock）（12.4.1） ​

4.2 死锁（Dead Lock）（12.4.2） ​

解决死锁的两类方法 ​

方法一：预防死锁 ​

(1) 一次封锁法 ​

(2) 顺序封锁法 ​

方法二：死锁的诊断与解除 ​

死锁的诊断 ​

解除死锁 ​

五、并发调度的可串行性（12.5） ​

5.1 基本概念 ​

5.2 可串行化调度（12.5.1） ​

判断可串行化的枚举法 ​

示例 ​

5.3 冲突可串行化调度（12.5.2） ​

六、两段锁协议（12.6，Two-Phase Locking，2PL） ​

6.1 基本概念 ​

6.2 两段锁协议定义 ​

6.3 "两段"的含义 ​

6.4 两段锁协议的性质 ​

6.5 两段锁协议与一次封锁法的关系 ​

6.6 两阶段封锁协议存在的问题 ​

6.7 处理级联回滚 ​

七、封锁的粒度（12.7，自学） ​

7.1 封锁粒度（Granularity） ​

7.2 选择封锁粒度的原则 ​

7.3 多粒度封锁（Multiple Granularity Locking） ​

多粒度树 ​

多粒度封锁协议 ​

显式封锁和隐式封锁 ​

本章小结 ​

并发控制

问题的产生

多事务执行方式

事务并发执行带来的问题

一、并发控制概述（12.1）

1.1 并发控制机制的任务

1.2 并发操作带来的数据不一致性

1. 丢失修改（Lost Update）—— "写-写冲突"

2. 脏读（Dirty Read）—— "读-写冲突"

3. 不可重复读（Non-repeatable Read）—— "读-写冲突"

*4. 幻读（Phantom Row）

1.3 数据不一致性的本质

1.4 并发控制的主要技术

二、事务的隔离级别（12.2）

2.1 SQL标准定义的四种隔离级别

2.2 隔离级别与数据不一致性的关系

2.3 隔离级别选择原则

2.4 MySQL实现说明

三、封锁（12.3）

3.1 封锁的基本概念（12.3.1）

什么是封锁

基本封锁类型

锁的相容矩阵

3.2 封锁协议（12.3.2 Locking Protocol）

三级封锁协议

一级封锁协议

二级封锁协议

三级封锁协议

封锁协议小结

四、活锁和死锁（12.4）

4.1 活锁（Live Lock）（12.4.1）

4.2 死锁（Dead Lock）（12.4.2）

解决死锁的两类方法

方法一：预防死锁

(1) 一次封锁法

(2) 顺序封锁法

方法二：死锁的诊断与解除

死锁的诊断

解除死锁

五、并发调度的可串行性（12.5）

5.1 基本概念

5.2 可串行化调度（12.5.1）

判断可串行化的枚举法

示例

5.3 冲突可串行化调度（12.5.2）

六、两段锁协议（12.6，Two-Phase Locking，2PL）

6.1 基本概念

6.2 两段锁协议定义

6.3 "两段"的含义

6.4 两段锁协议的性质

6.5 两段锁协议与一次封锁法的关系

6.6 两阶段封锁协议存在的问题

6.7 处理级联回滚

七、封锁的粒度（12.7，自学）

7.1 封锁粒度（Granularity）

7.2 选择封锁粒度的原则

7.3 多粒度封锁（Multiple Granularity Locking）

多粒度树

多粒度封锁协议

显式封锁和隐式封锁

本章小结