跳到主要内容

第18章 并发控制

在多用户数据库系统中,多个事务可能同时请求对同一数据项进行读写。若不加以协调,就会破坏数据库的一致性。本章讨论保证事务可串行化调度的各类并发控制协议:从最基本的两阶段封锁(2PL),到时间戳排序、有效性检查、多版本机制、快照隔离,以及若干弱一致性级别与高级主题。


18.1 基于锁的协议​

保证冲突可串行化最常用的方法是加锁。事务在读写数据项之前先申请锁,只有持有相应锁时才能进行操作;操作完成后按协议规则释放锁。

18.1.1 锁​

数据项上的锁分为两种基本模式:

  • 共享锁(S 锁):允许事务读取该数据项,但不能写。
  • 排他锁(X 锁):允许事务读取和写入该数据项。

两种锁的相容性由相容矩阵给出。若事务 TiT_i 请求某模式的锁,而当前锁模式与之相容,则可以立即授予;否则必须等待。

已持有 \ 请求SX
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)

若 T1T_1 尚未 unlock(A),T2T_2 的 lock-X(A) 将被阻塞,直到 T1T_1 释放该 S 锁——这即是并发控制在最低层次的体现。

18.1.2 锁的授予​

当事务申请锁被阻塞时,锁管理器把请求放入该数据项的等待队列。授予锁时通常采取先来先服务策略并保证无饿死:若事务 TiT_i 等待 QQ 的锁,则不允许无休止地让后来的、相容的事务先获得锁而使 TiT_i 一直无法前进。

18.1.3 两阶段封锁协议​

两阶段封锁(Two-Phase Locking, 2PL) 要求每个事务的执行分为两个阶段:

  1. 增长阶段:事务可以获得锁,但不能释放任何锁。
  2. 收缩阶段:事务可以释放锁,但不能再获得新锁。

基本 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) 提高并发度:

  • 事务对任一数据项 QQ 加锁之前,除根节点外都必须已锁定 QQ 的父节点。
  • 数据项可以随时解锁,但一旦解锁后不能再次锁定。

树形协议不需要两阶段限制,故避免死锁,且可释放锁更早;缺点是可能锁定实际不访问的祖先节点,某些应用中并发度反而下降。


18.2 死锁处理​

在基于锁的协议中,若若干事务互相等待对方所持的锁,就形成死锁。处理死锁有两类策略:预防与检测。

18.2.1 死锁预防​

常用的死锁预防方法有:

  • 一次性封锁:事务开始前一次性申请所有需要的锁。简单可靠,但难以事先预知集合,且并发度低。
  • 按序封锁:对所有数据项施加全序 ≺\prec,事务只能按 ≺\prec 递增顺序申请锁。
  • 抢占方案:给每个事务分配唯一时间戳 TS(T)\text{TS}(T),值越小越"老"。
    • 等待–死亡(wait-die):若 TS(Ti)<TS(Tj)\text{TS}(T_i) < \text{TS}(T_j)(TiT_i 老),则 TiT_i 等待;否则回滚 TiT_i。老事务等,新事务死。
    • 伤害–等待(wound-wait):若 TS(Ti)<TS(Tj)\text{TS}(T_i) < \text{TS}(T_j),则回滚 TjT_j("伤害");否则 TiT_i 等待。老事务抢占新事务。

两种方案都保证无死锁且无饿死(被回滚的事务重启时保留原时间戳)。

18.2.2 死锁检测与恢复​

不主动预防,而是周期性检测。系统维护等待图(Wait-For Graph):结点表示活跃事务,若 TiT_i 等待 TjT_j 所持的锁,则加一条 Ti→TjT_i \to T_j 的有向边。系统中存在死锁当且仅当等待图存在环。

下面是一个存在环 T1→T2→T3→T1T_1 \to T_2 \to T_3 \to T_1 的等待图示例:

检测到环后,需要选择一个牺牲者回滚。选择准则通常综合考虑:已消耗资源、已完成的工作量、后续还需的资源、涉及的数据项数量等,并采用部分回滚——只回滚到打破死锁所需的最早状态。为避免同一事务反复被选为牺牲者,通常在牺牲者回滚计数上加权,形成饿死避免。


18.3 多粒度​

大多数事务只访问少量元组,若始终以关系或数据库为粒度加锁,将严重影响并发;而始终以元组为粒度加锁,则大范围扫描会产生大量锁请求。多粒度封锁允许事务在不同粒度上加锁:数据库 → 关系 → 页 → 元组构成一棵粒度树。

为在细粒度加锁前先在粗粒度声明意图,引入意向锁:

  • IS(意向共享):在其子树中某处将加 S 锁。
  • IX(意向排他):在其子树中某处将加 X 锁。
  • SIX(共享意向排他):当前节点加 S 锁,其子树中另有节点将加 X 锁。

多粒度相容矩阵(行为已持有,列为新请求):

已持 \ 请求ISIXSSIXX
IS相容相容相容相容冲突
IX相容相容冲突冲突冲突
S相容冲突相容冲突冲突
SIX相容冲突冲突冲突冲突
X冲突冲突冲突冲突冲突

加锁规则:事务在节点 QQ 上申请某锁之前,必须在 QQ 的所有祖先上按上表约束获得相应意向锁;解锁则从叶子向根方向进行。


18.4 插入操作、删除操作与谓词读​

18.4.1 删除​

删除操作与写操作一样,需要 X 锁;被删除的元组被物理保留到事务提交之后,以便回滚。

18.4.2 插入​

插入需要对新元组加 X 锁,但新元组在插入前对其他事务并不可见,故需要通过对索引页或存储页加锁的方式对新元组的位置进行保护,以避免"读者看漏"。

18.4.3 谓词读和幻象现象​

幻象读(phantom read):事务 T1T_1 用谓词 PP 扫描表两次,两次读之间事务 T2T_2 插入了满足 PP 的新元组并提交,导致 T1T_1 两次读到的结果不一致——即使 T1T_1 已对首次读到的所有元组加了 S 锁。

解决办法:

  • 谓词锁:对谓词 PP 而非具体元组加锁,功能上正确但实现代价高。
  • 索引封锁 / 键范围锁(key-range locking):在 B+ 树等有序索引上,对包含谓词范围的索引区间加锁,插入前须先检查并等待相应区间锁。多数商用系统采用此法。

18.5 基于时间戳的协议​

18.5.1 时间戳​

在事务开始时赋予唯一时间戳 TS(Ti)\text{TS}(T_i),可用系统时钟或递增计数器。协议要求最终形成的可串行化次序满足:TS(Ti)<TS(Tj)⇒Ti\text{TS}(T_i) < \text{TS}(T_j) \Rightarrow T_i 在 TjT_j 之前。

每个数据项 QQ 维护两个时间戳:

  • W-TS(Q)\text{W-TS}(Q):成功执行 write(Q)\text{write}(Q) 的事务中最大的 TS;
  • R-TS(Q)\text{R-TS}(Q):成功执行 read(Q)\text{read}(Q) 的事务中最大的 TS。

18.5.2 时间戳排序协议​

对读写操作按下面伪码判决:

读操作 read(Q) 由 T_i 执行:
if TS(T_i) < W-TS(Q):
// 读一个"未来"事务已经写过的旧值,冲突
abort(T_i); restart with new TS
else:
execute read(Q)
R-TS(Q) := max(R-TS(Q), TS(T_i))

写操作 write(Q) 由 T_i 执行:
if TS(T_i) < R-TS(Q):
// 某更晚事务已经读走了 Q,本次写已过期
abort(T_i); restart
else if TS(T_i) < W-TS(Q):
// 某更晚事务已写过 Q,本次写被覆盖,可忽略(见 Thomas 写规则)
abort(T_i); restart // 严格 TSO
else:
execute write(Q)
W-TS(Q) := TS(T_i)

时间戳排序协议保证冲突可串行化,且无死锁(不使用锁);缺点是可能产生级联回滚,需额外机制(如提交依赖)避免读脏数据。

一个典型的时间戳判决示例:设 TS(T1)=10\text{TS}(T_1) = 10, TS(T2)=15\text{TS}(T_2) = 15,初始 W-TS(Q)=5\text{W-TS}(Q) = 5, R-TS(Q)=5\text{R-TS}(Q) = 5。

时刻操作判决副作用
1T2T_2: read(Q)15 ≥ W-TS(Q)=5,允许R-TS(Q) := 15
2T1T_1: write(Q)TS(T_1)=10 < R-TS(Q)=15,回滚 T1T_1无
3T2T_2: write(Q)15 ≥ R-TS(Q)=15 且 15 ≥ W-TS(Q)=5,允许W-TS(Q) := 15

可见协议在读写次序不符合时间戳所隐含的串行化次序时果断回滚。

18.5.3 Thomas 写规则​

在上述"TS(Ti)<W-TS(Q)\text{TS}(T_i) < \text{W-TS}(Q)"分支中,TiT_i 想要写入的值必然被 W-TS(Q)\text{W-TS}(Q) 对应的更晚事务的写覆盖。因此该写实际是"过期写",可安全忽略而非回滚 TiT_i。这就是 Thomas 写规则(Thomas's Write Rule),它在保证视图可串行化的同时提高了并发度,但生成的调度并不总是冲突可串行化的。


18.6 基于有效性检查的协议​

又称乐观并发控制(OCC)。事务运行分三个阶段:

  1. 读阶段:事务从数据库读值,写入私有本地副本,不影响数据库。
  2. 有效性检查阶段:分配 TS(Ti)=\text{TS}(T_i) = 校验时刻。检查是否与所有较早提交的事务 TkT_k 冲突:
    • 要么 TkT_k 已在 TiT_i 开始前提交;
    • 要么 TkT_k 的写集与 TiT_i 的读集不相交,且 TkT_k 已在 TiT_i 进入写阶段前完成写。
  3. 写阶段:若校验通过,把本地副本刷入数据库;否则回滚 TiT_i。

OCC 在冲突稀少时性能优越;在热点数据上频繁冲突则会造成大量回滚,反而不如封锁协议。


18.7 多版本机制​

多版本并发控制(MVCC) 通过保留数据项的多个历史版本,让读操作访问适当版本,从而避免读写互相阻塞。

18.7.1 多版本时间戳排序​

数据项 QQ 保存版本序列 ⟨Qk⟩\langle Q_k \rangle,每个版本 QkQ_k 有 content\text{content}、W-TS(Qk)\text{W-TS}(Q_k)、R-TS(Qk)\text{R-TS}(Q_k)。

  • TiT_i 执行 read(Q)\text{read}(Q):选出 W-TS(Qk)≤TS(Ti)\text{W-TS}(Q_k) \le \text{TS}(T_i) 中 W-TS 最大的版本 QkQ_k,读其值并更新 R-TS(Qk)\text{R-TS}(Q_k)。读永不阻塞、永不回滚。
  • TiT_i 执行 write(Q)\text{write}(Q):找出满足 W-TS(Qk)≤TS(Ti)\text{W-TS}(Q_k) \le \text{TS}(T_i) 的最新版本 QkQ_k;若 TS(Ti)<R-TS(Qk)\text{TS}(T_i) < \text{R-TS}(Q_k) 则回滚 TiT_i;否则创建新版本 Qk+1Q_{k+1},W-TS(Qk+1)=R-TS(Qk+1)=TS(Ti)\text{W-TS}(Q_{k+1}) = \text{R-TS}(Q_{k+1}) = \text{TS}(T_i)。

版本链示意:

TS=25 的读取者会读 Q2Q_2(值 120),TS=40 的读取者会读 Q3Q_3(值 150)。

18.7.2 多版本两阶段封锁​

将 MVCC 与 2PL 结合:

  • 事务分为只读与更新两类。只读事务在开始时获得时间戳,之后按 TS\text{TS} 读取相应版本,不加任何锁。
  • 更新事务遵循严格 2PL,读写都加锁;提交时按提交次序生成 TS,写入新版本。

这样读永不阻塞写、写不阻塞读,但更新事务之间仍按 2PL 相互串行化。


18.8 快照隔离​

快照隔离(Snapshot Isolation, SI) 是 MVCC 的一种实用形式,被 Oracle、PostgreSQL、SQL Server 等广泛采用。

18.8.1 快照隔离中的多版本​

事务 TiT_i 开始时拍摄数据库的一个逻辑快照 SiS_i:整个事务期间的所有读都基于 SiS_i,看不到在 TiT_i 之后开始或提交的事务所做的修改。写操作先写入 TiT_i 的私有版本,直到提交时才对其他事务可见。

18.8.2 更新事务的有效性检查步骤​

提交时进行冲突检查,防止两个并发事务同时写同一数据项(丢失更新)。有两种典型方案:

  • 先提交者获胜(First-committer-wins):TiT_i 提交时,检查是否存在同时活跃且已在 TiT_i 开始之后提交、写集与 TiT_i 写集相交的事务;若有,TiT_i 中止。
  • 先更新者获胜(First-updater-wins):写数据项时立即尝试获得该项的排他资源(如内部锁);若已被其他并发事务持有,则等待或中止。

18.8.3 串行化问题和解决方案​

SI 不等价于可串行化,典型异常是写偏斜(write skew):

假设银行规定"两个账户 A、B 余额之和 ≥0\ge 0"。初始 A=100,B=100A = 100, B = 100。

  • T1T_1:读 A、B(合计 200),若合法则更新 A:=−100A := -100。
  • T2T_2:读 A、B(合计 200),若合法则更新 B:=−100B := -100。

在 SI 下,T1T_1 与 T2T_2 各自基于开始时的快照,看到 A+B=200A+B = 200,都判断合法。两者写集不相交(T1T_1 写 A,T2T_2 写 B),提交检查通过。最终数据库 A=−100,B=−100A = -100, B = -100,A+B=−200<0A + B = -200 < 0,一致性被破坏。

任何串行执行顺序都不会导致这种结果,故 SI 不是可串行化的。

补救方案:

  • 可串行化快照隔离(SSI):跟踪读–写反依赖,若形成危险环则中止其一(PostgreSQL 9.1+)。
  • 显式加锁(SELECT … FOR UPDATE / FOR SHARE):在关键读处显式加锁,强制读–写冲突显式化。
  • 在应用层加约束或校验。

18.9 实践中的弱一致性级别​

许多应用为了提高并发度,愿意接受比可串行化弱的一致性。SQL 标准定义了四个隔离级别,本节讨论几种在实践中常见的弱级别及其取舍。

18.9.1 二级一致性​

Degree-2 consistency(游标读一致性):事务在读某数据项时获得 S 锁,读完立即释放;写锁按 2PL 到事务结束才释放。避免读脏数据,但不可重复读、幻象仍可能发生,对应 SQL 的 READ COMMITTED。

18.9.2 游标稳定性​

Cursor Stability 是二级一致性的扩展:只在游标当前指向的元组上持有 S 锁,游标移到下一元组时才释放前一元组的 S 锁。适合按行遍历更新的场景。

18.9.3 跨用户交互的并发控制​

对长交互(如网页表单编辑、订票系统),事务不能长时间持锁。常见做法:

  • 乐观离线锁 / 版本号法:读取时记录版本号,提交时若版本号未变则更新,否则冲突提示用户重试。
  • 业务级悲观锁:显式加一条"某用户正在编辑"的记录,配合超时释放。

这些通常在应用层实现,而非数据库并发控制协议直接支持。


18.10 并发控制的高级主题​

18.10.1 在线索引创建​

在生产库中创建索引不能长时间锁表。在线索引创建分阶段:

  1. 建立索引结构快照,扫描数据填充索引;
  2. 记录构建期间的更新到辅助日志;
  3. 应用辅助日志追赶;
  4. 短暂加锁切换到新索引。

18.10.2 索引结构中的并发​

B+ 树的并发控制不必满足可串行化——只要保证结构正确与查找结果正确即可。常用crabbing 协议:

  • 查找:自根向下逐层加 S 锁;子节点加锁成功后,若判断子节点"安全"则释放父锁。
  • 插入/删除:加 X 锁,若节点不会发生分裂/合并则释放祖先锁。

由此可显著提高 B+ 树并发度。

18.10.3 主存数据库中的并发控制​

对主存数据库,磁盘 I/O 不再是瓶颈,锁获取与释放的 CPU 开销反而突出。常见优化:

  • 分区并串行执行:H-Store/VoltDB 将数据按分区划分,每分区单线程串行执行事务,无锁。
  • 乐观并发 + MVCC:Hekaton、HyPer 等。
  • 无锁数据结构与 CAS。

18.10.4 长事务​

长事务(如设计事务、CAD/CASE 事务)可能持续数小时甚至数天。整套 2PL 会导致严重阻塞。解决方案包括:

  • 嵌套事务模型:将长事务分解为若干子事务,允许部分回滚。
  • 补偿事务(Sagas):每个子事务对应一个显式补偿动作,失败时按逆序执行补偿。
  • 签入/签出(check-in/check-out):将数据签出到私有工作区,长时间修改后再签入。

18.10.5 利用操作的并发控制​

若能利用操作的交换律,可以放宽冲突判定。例如 increment(x, k) 之间可交换(xx 加 k1k_1 再加 k2k_2 与加 k2k_2 再加 k1k_1 结果相同),可以并发执行而不必串行化,这被称为语义并发控制或升级锁模式(如 U 锁、增量锁)。

18.10.6 实时事务系统​

在实时数据库(航电、电信计费)中,事务有截止期限。并发控制需要与调度联动:

  • 优先级继承:低优先级事务持锁被高优先级事务等待时临时提升;
  • 优先级抢占 / 优先级取消:允许高优先级抢占低优先级持锁;
  • 时间戳分配偏向高优先级事务。

18.11 总结​

  • 锁是最主流的并发控制手段。两阶段封锁(尤其是严格 / 强 2PL)保证可串行化。
  • 死锁可用预防(一次性、按序、wait-die / wound-wait)或检测–回滚(等待图找环)处理。
  • 多粒度封锁通过 IS/IX/S/SIX/X 等意向锁在不同粒度间平衡并发度与开销。
  • 时间戳排序是完全无锁的替代方案;Thomas 写规则可安全跳过过期写。
  • 乐观并发控制在冲突稀少时高效,冲突频繁时代价高。
  • MVCC让读不阻塞写、写不阻塞读,快照隔离是其广泛使用的近似串行化实现,但存在写偏斜等异常。
  • 实际系统提供多种弱一致性级别(READ COMMITTED、REPEATABLE READ、SI 等)以在正确性与性能之间折中。
  • 高级主题包括索引结构并发、主存数据库、长事务、实时事务等,需要针对性协议。

各协议特性对比:

协议是否用锁是否死锁是否级联回滚冲突可串行化主要开销
基本 2PL是可能可能是锁管理
严格 / 强 2PL是可能否是锁持有时间长
时间戳排序否否可能是频繁回滚
Thomas 写规则否否可能视图可串行频繁回滚
乐观并发(OCC)否否提交时检查是冲突多时回滚
MVCC + 2PL部分可能否是版本维护
快照隔离否否否否(有异常)版本维护、写偏斜检测
SSI否否否是反依赖跟踪

核心洞察:并发控制的所有协议都在做同一件事——限制或重排事务对数据项的访问次序,使最终结果等价于某种串行执行。协议之间的差别,是在"何时限制"(提前加锁 vs. 提交时校验)与"如何限制"(同步等待 vs. 直接回滚)上的取舍。