Chapter 18 Concurrency Control¶

1 Lock-Based Protocols¶

锁（lock）是控制多个事务并发访问同一数据项的机制。

锁模式	含义	请求指令
Shared lock, S-lock	共享锁，只允许读数据项	`lock-S`
Exclusive lock, X-lock	排他锁，允许读和写数据项	`lock-X`

事务向并发控制管理器请求锁。若请求能被授予，事务继续执行；若请求与已有锁不兼容，事务必须等待。

锁兼容矩阵（Lock-compatibility matrix）

当前持有锁	申请 S 锁（读锁）	申请 X 锁（写锁）
持有 S 锁	true（兼容）	false（不兼容）
持有 X 锁	false（不兼容）	false（不兼容）

任意多个事务可以同时持有同一数据项的共享锁。
若任一事务已经持有某数据项的排他锁，则其他事务不能再持有该数据项上的任何锁。
若锁不能立即授予，请求事务会等待，直到所有不兼容锁被释放。

仅仅在读写前后加锁并不一定保证可串行化

以事务 \(T_2\) 读取 A+B 为例：

lock-S(A)
read(A)
unlock(A)
lock-S(B)
read(B)
unlock(B)
display(A+B)

若 A 与 B 在两次读取之间被其他事务更新，则打印出的总和可能错误。

锁协议（locking protocol）是一组所有事务都必须遵守的加锁、解锁规则。锁协议通过限制可能出现的调度集合来保证正确性。

2 Two-Phase Locking¶

两阶段锁协议（two-phase locking, 2PL）：保证冲突可串行化，将每个事务的锁行为分为两个阶段。

阶段	允许操作	禁止操作
扩展阶段（Growing Phase）	获取锁	释放锁
收缩阶段（Shrinking Phase）	释放锁	获取锁

事务一旦释放了某个锁，就进入 shrinking phase，之后不能再获得任何新锁。

锁点（lock point）：事务获得最后一个锁的时刻，2PL 允许按照事务的锁点对事务串行化。
带锁转换的两阶段锁协议：保证可串行化，但需要程序员或系统正确插入锁操作。

阶段	允许操作
First phase	获得 `S` 锁、获得 `X` 锁、将 `S` 锁升级为 `X` 锁（只能在 growing phase 发生）
Second phase	释放 `S` 锁、释放 `X` 锁、将 `X` 锁降级为 `S` 锁（只能在 shrinking phase 发生）

普通 2PL 可能发生级联回滚，因为某事务可能读取了另一个尚未提交事务写出的数据，因此需要改进的协议：

严格两阶段锁协议（Strict two-phase locking）：事务必须持有所有 X 锁直到 commit 或 abort，从而避免读取未提交写入导致的级联回滚。
强两阶段锁协议（Rigorous two-phase locking）：事务必须持有所有锁，包括 S 锁和 X 锁，直到 commit 或 abort，事务可以按照提交顺序串行化。

系统可以自动为普通 read / write 指令获取锁（Automatic acquisition of locks），而不要求事务显式调用 lock-S 或 lock-X。

示例

read(D) 的处理逻辑

if Ti already has a lock on D:
    read(D)
else:
    wait until no other transaction has lock-X on D
    grant Ti a lock-S on D
    read(D)

write(D) 的处理逻辑

if Ti already has lock-X on D:
    write(D)
else:
    wait until no other transaction has any lock on D
    if Ti has lock-S on D:
        upgrade lock on D to lock-X
    else:
        grant Ti a lock-X on D
    write(D)

所有锁在事务 commit 或 abort 后释放。

3 Deadlocks¶

死锁（deadlock）是指存在一组事务，其中每个事务都在等待该组中另一个事务释放资源。

示例

\(T_3\) 等待 \(T_4\) 释放 A，同时 \(T_4\) 等待 \(T_3\) 释放 B，二者都无法继续执行。

发生死锁时，必须回滚其中某些事务并释放其锁，才能打破等待环。

两阶段锁协议保证冲突可串行化，但不能保证没有死锁，大多数锁协议都存在死锁的可能性，死锁发生时有可能引发级联回滚。

饥饿（starvation）

一个事务一直等待某数据项的 X 锁，但不断有其他事务请求并获得该数据项的 S 锁。
同一个事务在死锁处理中反复被选为牺牲者并回滚。

4 Implementation of Locking¶

锁管理器（lock manager）可以实现为独立进程或模块。事务向锁管理器发送加锁和解锁请求，锁管理器返回锁授予（lock grant）消息、等待通知和在死锁等情况下要求事务回滚的消息。

请求事务在收到答复前必须等待。

锁管理器维护一个锁表（lock table），记录已授予锁和等待请求。锁表通常是内存哈希表，以被加锁数据项的名称作为键。

新请求会追加到该数据项请求队列末尾。若它与所有更早的已授予锁兼容，则可以授予。
解锁请求会删除对应锁，并检查后续等待请求是否现在可以授予。
若事务中止，则该事务所有等待或已授予请求都要从锁表中删除。

5 Deadlock Handling¶

死锁处理的三类思路

Deadlock prevention：通过协议设计保证系统永不进入死锁状态。
Deadlock detection：允许死锁发生，周期性检测等待图中的环。
Deadlock recovery：检测到死锁后选择事务回滚，打破死锁。

5. 1 Deadlock Prevention¶

常见预防方法包括：

预声明（predeclaration）：事务开始前一次性锁定所有需要的数据项。
数据项偏序（partial ordering）：为所有数据项规定偏序，事务必须按该顺序申请锁。

这两种方法都能避免等待环，但可能降低并发度或要求事务提前知道所有访问对象。

策略	类型	规则
Wait-die	非抢占式	老事务可以等待年轻事务；年轻事务不能等待老事务，必须回滚
Wound-wait	抢占式	老事务请求年轻事务持有的数据项时，强制年轻事务回滚；年轻事务可以等待老事务

以上两种策略只用时间戳进行死锁预防，时间戳越小，事务越老。被回滚的事务重启时保留原始时间戳，因此老事务会逐渐获得优先权，避免饥饿。

基于超时的方案（Timeout-Based Schemes）：事务只能等待锁一段固定时间，若超时仍未获得锁，则事务回滚并重启。
- 优点：实现简单，不会长期保留死锁。
- 缺点：可能误杀没有死锁的事务，超时时间很难选择，仍可能发生饥饿。

5. 2 Deadlock Detection¶

死锁检测通常基于等待图（wait-for graph），记为 \(G=(V,E)\)：

\(V\) 是系统中的事务集合。
若 \(T_i\) 正在等待 \(T_j\) 释放某个数据项，则加入有向边 \(T_i \to T_j\)。
当 \(T_i\) 请求一个由 \(T_j\) 持有的数据项时加入边。
当 \(T_j\) 不再持有 \(T_i\) 需要的数据项时删除边。

系统处于死锁状态当且仅当等待图中存在环。系统需要周期性运行环检测算法。

5. 3 Deadlock Recovery¶

检测到死锁后，需要选择一个或多个事务作为牺牲者（victim）并回滚以打破等待环，选择牺牲者时通常考虑最小代价。

完全回滚（Total rollback）：完全中止事务，然后重新启动。
部分回滚（Partial rollback）：只回滚到足以打破死锁的点。

若总是选择同一个事务作为牺牲者会发生饥饿，将事务已被回滚次数纳入代价函数可以降低这种风险。

6 Multiple Granularity¶

多粒度锁（multiple granularity locking）允许数据项具有不同大小，并用层次树表示包含关系。

当事务显式锁定树中某个节点时，会隐式锁定该节点的所有后代，锁模式相同。

粒度	位置	并发度	加锁开销
细粒度（fine granularity）	树的低层，如记录	高	高
粗粒度（coarse granularity）	树的高层，如文件、关系、数据库	低	低

示例：database、area、file、record

仅有 S 和 X 锁时，若事务想锁定某个高层节点，系统必须检查所有后代是否已有冲突锁，代价很高。

意向锁（intention locks）用于在高层节点上标记后代中将会加锁，除 S、X 外，多粒度锁引入三种模式：

锁模式	含义
IS	intention-shared，表示事务将在更低层节点上显式加共享锁
IX	intention-exclusive，表示事务将在更低层节点上显式加共享锁或排他锁
SIX	当前节点以共享模式锁定，同时将在更低层节点上显式加排他锁

SIX 可理解为 S + IX：读整个子树，但只更新子树中的部分后代节点。

Compatibility Matrix with Intention Lock Modes

	申请 IS 锁	申请 IX 锁	申请 S 锁	申请 SIX 锁	申请 X 锁
持有 IS 锁	true	true	true	true	false
持有 IX 锁	true	true	false	false	false
持有 S 锁	true	false	true	false	false
持有 SIX 锁	true	false	false	false	false
持有 X 锁	false	false	false	false	false

事务 \(T_i\) 对节点 \(Q\) 加锁时必须遵守以下规则：

必须满足锁兼容矩阵。
必须先锁定树根，根可以用任意模式加锁。
只有当 \(T_i\) 已以 IX 或 IS 模式锁定 \(Q\) 的父节点时，才能以 S 或 IS 模式锁定 \(Q\)。
只有当 \(T_i\) 已以 IX 或 SIX 模式锁定 \(Q\) 的父节点时，才能以 X、SIX 或 IX 模式锁定 \(Q\)。
\(T_i\) 只有在此前没有解锁任何节点时，才能继续加锁，即仍需满足两阶段锁协议。
\(T_i\) 只有在自己没有锁定 \(Q\) 的任何子节点时，才能解锁 \(Q\)。

因此，锁按根到叶方向获得，按叶到根方向释放。

若某一层持有的锁数量太多，系统可以进行锁升级（lock escalation），即释放大量细粒度锁，改为在更高层节点上获取 S 或 X 锁，以减少锁管理开销。

7 Insert and Delete Operations¶

在使用两阶段锁协议时：

删除元组前，事务必须对被删除元组持有 X 锁。
插入新元组后，事务获得该新元组上的 X 锁。

但仅对已有元组加锁不能完全解决插入、删除带来的问题，因为会出现幻影读现象（phantom phenomenon）。

示例

考虑两个事务：

\(T_1\) 扫描关系，统计 Perryridge 分行所有账户余额之和。
\(T_2\) 向该关系插入一个新的 Perryridge 账户。

即使 \(T_1\) 和 \(T_2\) 没有访问任何共同的已有元组，它们在逻辑上仍冲突，因为 \(T_1\) 读取的是关系中有哪些元组满足条件这一信息，而 \(T_2\) 修改了这项信息。

若只使用元组锁，可能出现不可串行化调度，即扫描事务没有看到新账户，却读取到了插入事务写过的其他元组。

一种直接方案是给关系关联一个特殊数据项，用来表示该关系包含哪些元组。

扫描关系的事务对该数据项加 S 锁。
插入或删除元组的事务对该数据项加 X 锁。
该数据项上的锁不与单个元组上的锁冲突。

该方案能检测冲突，但会显著降低插入和删除的并发度，索引锁协议（Index Locking Protocol）可以在防止幻影读的同时提供更高并发。

索引锁协议

每个关系至少有一个索引。
事务只能通过一个或多个索引找到并访问元组。
执行查找的事务必须对访问到的所有索引叶节点加 S 锁。
即使叶节点中没有满足查找条件的元组，范围查询访问到的叶节点仍要加锁。
插入、更新或删除元组时，事务必须更新该关系上的所有索引。
插入、更新或删除影响到的索引叶节点必须加 X 锁。
所有锁操作仍必须遵守两阶段锁协议。

该协议能保证幻影读现象不会发生。

如果为了防止幻影读而锁住整个索引叶节点，插入频繁时并发度会很差，下一键锁（Next-Key Locking）是更细的索引锁方案。

下一键锁

对一次索引查找：

锁定所有满足查找条件的键值，或范围查询中的所有键值。
额外锁定索引中的下一个键值（next key）。
查询使用 S 锁。
插入、删除、更新使用 X 锁。

这样可以保证范围查询与并发插入、删除、更新发生冲突，无论哪个事务先执行。

8 Concurrency in Index Structures¶

索引结构与普通数据项不同，其作用只是帮助定位数据，访问频率非常高，如果对索引节点也严格使用普通两阶段锁，尤其是 B+ 树内部节点，会严重降低并发度。

因此，很多索引并发协议（index concurrency protocols）允许内部节点上的锁提前释放，不完全遵守两阶段锁。只要索引结构保持正确，并发访问索引本身不必可串行化。

对 B+ 树来说，内部节点读到的精确键值并不重要，只要搜索最终能到达正确叶节点即可。

Crabbing（螃蟹锁）

搜索、插入、删除时：

先以共享模式锁定根节点。
锁定所需子节点后，释放父节点。
插入或删除时，将叶节点锁升级为排他模式。
若分裂或合并需要修改父节点，则以排他模式锁定父节点。

该协议可能产生过多死锁，例如向下搜索的事务与向上更新父节点的事务互相等待。搜索操作可以中止并重启，因为它本身不改变事务语义。

更好的协议包括 B-link tree 协议，直觉是尽量在获得子节点锁前释放父节点锁，并处理释放与重新获取之间可能发生的结构变化。

9 Transactions across User Interaction¶

许多应用需要让事务逻辑跨越用户交互，例如用户查看余额、等待输入、再提交修改。

这类场景通常不适合在数据库中长时间持有锁：

用户思考时间不可控，长时间持锁会阻塞其他事务。
每个用户长时间占用一个数据库连接也会浪费资源。

一种常见方案是在应用层使用乐观并发控制和版本号：

每个元组包含版本号。

读取元组时，应用同时记录数据值和版本号。

select r.balance, r.version into :A, :version
from r
where acctId = 23;

写回时检查当前版本号是否仍等于读取时的版本号。

update r
set r.balance = r.balance + :deposit,
    r.version = r.version + 1
where acctId = 23
and r.version = :version;

若更新影响行数为 0，说明该元组在用户交互期间已被其他事务修改，应用应重新读取并让用户重试。

这种方式等价于一种不验证完整读集的乐观并发控制。Hibernate ORM 等系统内部会使用类似机制，应用也可以手动实现。版本号还可用于支持快照隔离中的 first-committer-wins 检查，但与完整快照隔离不同，这种方式不能保证所有读取都来自同一个快照。