第18章 并发控制
在多用户数据库系统中,多个事务可能同时请求对同一数据项进行读写。若不加以协调,就会破坏数据库的一致性。本章讨论保证事务可串行化调度的各类并发控制协议:从最基本的两阶段封锁(2PL),到时间戳排序、有效性检查、多版本机制、快照隔离,以及若干弱一致性级别与高级主题。
18.1 基于锁的协议
保证冲突可串行化最常用的方法是加锁。事务在读写数据项之前先申请锁,只有持有相应锁时才能进行操作;操作完成后按协议规则释放锁。
18.1.1 锁
数据项上的锁分为两种基本模式:
- 共享锁(S 锁):允许事务读取该数据项,但不能写。
- 排他锁(X 锁):允许事务读取和写入该数据项。
两种锁的相容性由相容矩阵给出。若事务 请求某模式的锁,而当前锁模式与之相容,则可以立即授予;否则必须等待。
| 已持有 \ 请求 | S | X |
|---|---|---|
| S | 相容 | 冲突 |
| X | 冲突 | 冲突 |
多个事务可以同时持有同一数据项的 S 锁,但 X 锁只能由一个事务独占。锁请求由锁管理器(lock manager) 统一处理,事务通过 lock-S(Q)、lock-X(Q)、unlock(Q) 三条基本原语与之交互。
一个使用 S/X 锁的调度示例:
T1: lock-S(A) read(A) unlock(A)
T2: lock-X(A) read(A) A:=A-50 write(A) unlock(A)
若 尚未 unlock(A), 的 lock-X(A) 将被阻塞,直到 释放该 S 锁——这即是并发控制在最低层次的体现。
18.1.2 锁的授予
当事务申请锁被阻塞时,锁管理器把请求放入该数据项的等待队列。授予锁时通常采取先来先服务策略并保证无饿死:若事务 等待 的锁,则不允许无休止地让后来的、相容的事务先获得锁而使 一直无法前进。
18.1.3 两阶段封锁协议
两阶段封锁(Two-Phase Locking, 2PL) 要求每个事务的执行分为两个阶段:
- 增长阶段:事务可以获得锁,但不能释放任何锁。
- 收缩阶段:事务可以释放锁,但不能再获得新锁。
基本 2PL 保证冲突可串行化,但不能防止级联回滚,也不能防止读脏数据。因此实际系统常用以下两种加强形式:
| 变体 | 关键约束 | 优点 | 缺点 |
|---|---|---|---|
| 严格 2PL(Strict 2PL) | 所有 X 锁必须保留到事务提交/中止后才释放 | 防止读脏数据;避免级联回滚 | 事务持锁时间较长,并发度略低 |
| 强 2PL(Rigorous 2PL) | 所有 S 锁与 X 锁都保留到事务结束 | 事务的可串行化次序即为其提交次序,便于恢复推理 | 并发度进一步降低 |
严格 2PL 与强 2PL 都保证可串行化,且几乎所有商用数据库都采用其中之一。
一个符合两阶段封锁的调度示例:
T1: lock-X(A); read(A); A:=A-50; write(A);
lock-X(B); read(B); B:=B+50; write(B);
commit; -- 提交时统一释放锁 (strict/rigorous 2PL)
其"增长阶段"是前两次 lock-X;进入 commit 后一次性释放全部锁。若允许在 commit 之前提前 unlock(A),则同样满足基本 2PL,但可能出现级联回滚。
18.1.4 封锁的实现
锁管理器一般用锁表实现:一张以数据项标识(如 页号+槽号,或行号)为键的散列表,每个表项挂一条链,链中每个节点代表一次锁请求,记录:
- 事务 ID;
- 请求模式(S / X / …);
- 状态(已授予 / 等待);
- 指向下一节点的指针。
事务请求锁时,锁管理器沿链检查前面所有已授予节点的模式,判断是否相容;若相容立即授予并挂入链尾,否则该节 点置为等待并阻塞事务。事务释放锁时,唤醒该链中因它而等待的事务。
18.1.5 基于图的协议
若能事先获得数据项之间的偏序关系(如层次结构或有向无环图),可用树形协议(tree protocol) 提高并发度:
- 事务对任一数据项 加锁之前,除根节点外都必须已锁定 的父节点。
- 数据项可以随时解锁,但一旦解锁后不能再次锁定。
树形协议不需要两阶段限制,故避免死锁,且可释放锁更早;缺点是可能锁定实际不访问的祖先节点,某些应用中并发度反而下降。
18.2 死锁处理
在基于锁的协议中, 若若干事务互相等待对方所持的锁,就形成死锁。处理死锁有两类策略:预防与检测。
18.2.1 死锁预防
常用的死锁预防方法有:
- 一次性封锁:事务开始前一次性申请所有需要的锁。简单可靠,但难以事先预知集合,且并发度低。
- 按序封锁:对所有数据项施加全序 ,事务只能按 递增顺序申请锁。
- 抢占方案:给每个事务分配唯一时间戳 ,值越小越"老"。
- 等待–死亡(wait-die):若 ( 老),则 等待;否则回滚 。老事务等,新事务死。
- 伤害–等待(wound-wait):若 ,则回滚 ("伤害");否则 等待。老事务抢占新事务。
两种方案都保证无死锁且无饿死(被回滚的事务重启时保留原 时间戳)。
18.2.2 死锁检测与恢复
不主动预防,而是周期性检测。系统维护等待图(Wait-For Graph):结点表示活跃事务,若 等待 所持的锁,则加一条 的有向边。系统中存在死锁当且仅当等待图存在环。
下面是一个存在环 的等待图示例:
检测到环后,需要选择一个牺牲者回滚。选择准则通常综合考虑:已消耗资源、已完成的工作量、后续还需的资源、涉及的数据项数量等,并采用部分回滚——只回滚到打破死锁所需的最早状态。为避免同一事务反复被选为牺牲者,通常在牺牲者回滚计数上加权,形成饿死避免。
18.3 多粒度
大多数事务只访问少量元组,若始终以关系或数据库为粒度加锁,将严重影响并发;而始终以元组为粒度加锁,则大范围扫描会产生大量锁请求。多粒度封锁允许事务在不同粒度上加锁:数据库 → 关系 → 页 → 元组构成一棵粒度树。
为在细粒度加锁前先在粗粒度声明意图,引入意向锁:
- IS(意向共享):在其子树中某处将加 S 锁。
- IX(意向排他):在其子树中某处将加 X 锁。
- SIX(共享意向排他):当前节点加 S 锁,其子树中另有节点将加 X 锁。
多粒度相容矩阵(行为已持有,列为新请求):
| 已持 \ 请求 | IS | IX | S | SIX | X |
|---|---|---|---|---|---|
| IS | 相容 | 相容 | 相容 | 相容 | 冲突 |
| IX | 相容 | 相容 | 冲突 | 冲突 | 冲突 |
| S | 相容 | 冲突 | 相容 | 冲突 | 冲突 |
| SIX | 相容 | 冲突 | 冲突 | 冲突 | 冲突 |
| X |