mem.academic
4 min read

XIV. Concurrency Control

memset0
memset0
Jun 11, 2025

Lock-Based Protocols

  • 可串行化调度是并发控制的基础，而为了确保可串行化，需要通过锁来保护数据库对象．

  • 锁(lock) 是一种控制并发访问同一数据项的机制．

  • 两种 锁模式(lock mode)：

    • exclusive(X)：表示数据项可以读和写，用 lock-X 表示．

    • shared(S)：表示数据项只能读，用 lock-S 表示．

  • 锁兼容性矩阵(lock-compatiability matrix)：

    • 如果请求的锁和这个数据项上已有的锁兼容（可通过兼容性矩阵判断），则可以批准这个锁（让事务 持有(obtain) 这个锁）．

    • 如果一个锁没有被批准，就会产生一个请求事务，等到所有冲突的锁被 释放(release) 后，再批准该锁．

    • 对于这个锁兼容性矩阵来说，单个数据项上可以有任意多事务持有 S 锁，但是如果有一个事务持有 X 锁，其他事务就都不可以持有这个事务项的锁（无论是 S 或 X）．

  • 基于锁的协议(lock-based protocol)：是对所有事务在请求和释放锁时的一组规则．⇒\Rightarrow 限制了可能的调度集合．

The Two-Phase Locking Protocol

  • 二阶段锁协议(two-parse locking protocol, 2PL)：对于每个事务，分为两个阶段 (1) growing 阶段：每个事务可以请求锁，锁管理器可以 批准(grant) 或 拒绝(deny) 锁请求．(2) shrinking 阶段进允许 释放(release) / 降级(downgrade) 先前获取的锁，而不能获取新的锁．

    • 二阶段锁协议可以确保冲突可串行化调度．

    • 无法解决死锁的问题．

    • 不能避免级联回滚．

Example: 二阶段锁协议

  • 严格二阶段锁协议(strict two-phase locking protocol)：事务必须持有所有 互斥锁(exclusive lock) 直到事务提交/中止．

    • 可确保可恢复性：事务可以按照他们提交的顺序进行序列化（TBD：？）

    • 可以避免级联回滚．

  • 强二阶段锁协议(rigorous two-phase locking protocol)：事务必须持有所有锁直到事务提交/中止．

    • 可确保事务可以按照提交的顺序进行序列化．

  • 二阶段锁不是可串行化的必要条件．⇔\Leftrightarrow 存在一些冲突可串行化调度无法通过二阶段锁协议实现．

Two-Phase Locking with Lock Conversions

  • 带 锁转换(lock conversion) 的二阶段锁协议：(1) upgrade 阶段：可以申请 X 锁或 S 锁，可以把 S 锁升级为 X 锁．(2) downgrade 阶段：可以释放 X 锁或 S 锁，可以把 X 锁降级为 S 锁．

    • 锁转换同样可以确保冲突可串行化．

    • 按照我的理解，带锁转换的 2PL 和普通的 2PL 能处理的调度集合其实是相同的．

  • 带锁转换的二阶段锁协议可以让事务自动获取/释放锁，而不需要显示的锁定调用．当需要 read 时如果没有锁就自动申请 S 锁，当需要 write 时如果没有锁就自动申请 X 锁，如果已经持有 S 锁就升级成 X 锁；当事务提交/中止时自动释放所有锁．

  • 锁管理器(lock manager) 用于处理申请和释放锁的请求．

  • 锁管理器一般通过称为 锁表(lock table) 的数据结构进行维护，其是一个哈希表套队列．每个数据项有一个队列，用于维护等待获取该数据项的锁的事务．

Graph-Based Protocols

  • 图锁协议(graph-based protocol) 是二阶段锁协议的一个替代方案，如果偏序关系（就是说是路径，而不是说边） di→djd_{i} \rightarrow d_{j} 存在，那么同时访问 did_{i} 和 djd_{j} 的事务必须在访问 djd_{j} 之前访问 did_{i}．

    • 这个图是一个有向无环图，称为 数据库图(database graph)．

    • 使用图锁协议可以避免死锁的出现．

  • 树锁协议(tree-based protocol) 是图锁协议的一个简化版本．要求如下：

    • 只允许使用排他锁．

    • 每个事务的第一个锁可以加在任何数据项上，之后如果想要再锁别的数据项，必须已经锁定其父节点．

    • 数据项可以在任何时候释放锁．

    • 已经被事务锁定并解锁的数据项，不能再次被同一事务锁定．

  • 比较树锁协议与二阶段锁协议：

    • 优点：

      • 相比于二阶段锁协议可以更早解锁，并且可保证不会出现死锁．

    • 缺点：

      • 无法保证可恢复性或无级联回滚．

      • 事务可能需要锁定更多的数据项，并带来额外开销．

    • 二阶段锁协议无法所实现的调度可能通过树锁协议实现，反之亦然．

Example: 树协议下的可串行化调度

Deadlock Handling

  • 死锁(deadlock)：两个（或多个）事物的锁相互等待造成事务无法执行．

  • 饥荒(starvation)：包括但不限于：

    • 一个事务在等一个数据项的 X-lcok，而一群别的事务在等他释放．

    • 同一事务因为死锁问题被反复回滚．

Example: 死锁

  • 死锁处理(deadlock handling)：死锁处理分为两种：

    • deadlock prevention（预防）

    • deadlock detection and deadlock recovery（检测并修复）

Deadlock Prevention Strategies

  • 死锁预防(deadlock prevention)：用于确保系统永远不会进入死锁状态．

  • 下图是一些预防策略，后面还有三个预防策略．

  • 一开始就获得所有锁．

  • timeout-based schema：事务仅在指定时间内等待锁，超时后自动回滚．

    • 实现简单，但可能出现饥荒．

  • wait-die schema：（非抢占式）

    • 老事务等待新事务；新事务遇到老事务则回滚（自杀）．

  • wound-wait schema：（抢占式）

    • 老事务强制回滚新事务（创伤）；新事务等待老事务．

    • 可以避免饥荒．

Example: wait-die 与 wound-wait 策略对比

抄骗人纸的时候可以记一下这个例子，还挺深刻的．

Deadlock Detection & Recovery

  • 死锁检测(deadlock detection)：死锁可以通过 等待图(wait-for graph) 来描述并检测．当等待图中出现环时说明出现了死锁．

  • 死锁恢复(deadlock recovery)：检测到死锁之后，必须回滚某些事务以打破死锁．

    • 选择成本最小的事务进行回滚，但是如果总是选择同时事务作为牺牲品，则可能出现 饥荒(starvation)．应将回滚次数纳入考量以避免饥荒．

    • 系统还可以选择完全回滚（中止事务并重新启动他）还是部分回滚事务．

Multiple Granularity Locking

  • 锁的粒度：

    • 粗粒度(coarse granularity)：higher in tree：低锁开销，低并发度．

    • 细粒度(fine granularity)：lower in tree：高锁开销，高并发度．

  • 意向锁(intention lock)：意向锁允许 higher-level node 锁定在共享锁或排他锁上，从而避免对所有子节点进行检查（TBD：？）．

    • 意向锁的主要作用是用于支持行级锁与表级锁的并存

    • InnoDB 提供了行级锁，而在某些场景下，数据库系统仍需要对整张表加锁，例如 LOCK TABLES 或 ALTER TABLE 操作．在这些场景中，如果没有意向锁机制，系统需要扫描所有行级锁来判断是否可以安全地加表锁，这会严重影响性能

    • 通过提供表级的锁定信息，避免了系统去逐行检查是否可以加表锁．

  • 意向锁模式(intention lock mode)：

    • 意向共享锁(intention-shared, IS)：表示在树的较低层级仅使用共享锁进行显示锁定．

    • 意向排他锁(intention-exclusive, IX)：表示在树的较低层级使用共享锁或排他锁进行显示锁定．

    • 共享且意向排他锁(shared and intention exclusive, SIX)：以该节点为跟的子树以共享模式进行锁定，并且在较低层级使用排他模式进行显示锁定．（SIX = S + IX）

  • 在显示锁定某个节点之前，需要对其所有祖先节点设置意向锁．

  • 意向锁模式下的兼容性矩阵：

ISIXSSIXX
IStruetruetruetruefalse
IXtruetruefalsefalsefalse
Struefalsetruefalsefalse
SIXtruefalsefalsefalsefalse
Xfalsefalsefalsefalsefalse
Example: 意向锁模式下的多粒度锁

  • 多粒度锁机制(multiple granularity locking schema)：

    • （条件1）必须遵循锁兼容性矩阵．

    • （条件2）必须首先锁定树的根节点，并且可以以任何模式锁定．

    • （条件3）仅当 Q 的父节点目前被 TiT_{i} 以 IX 或 IS 模式加锁时，TiT_{i} 才能以 S 或 IS 模式锁定节点 Q．

    • （条件4）仅当 Q 的父节点目前被 TiT_{i} 以 IX 或 SIX 模式加锁时，TiT_{i} 才能以 X、SIX 或 IX 模式锁定节点 Q．

    • （条件5）TiT_{i} 只有在之前没有解锁过任何节点的情况下才能对节点加锁（即，多粒度锁机制中的事务是二阶段的）．

    • （条件6）TiT_{i} 只有在 Q 的子节点都没有被 TiT_{i} 加锁的情况下，才能解锁节点 Q．

  • 锁粒度升级(lock granularity esclation)：如果在某一特定级别有太多锁，则切换到更高级别的 S 锁或 X 锁．

Index Locking Protocol

  • 幻读(phantom read)：一个事务读取某个范围的数据时，另一个事务在该范围内插入/删除一以些数据，导致第一个事务再次读到了一些不存在（或读不到应该存在的数据）的数据．

  • 如果只使用 元组锁(tuple lock)，就可能出现幻读．

    • 除非对整个表枷锁，但这样会大大降低并发度，不可行．

  • 索引锁协议(index locking protocol) 可以避免出现幻读．

    • 每个关系必须至少有一个索引．

    • 事务只能在通过一个或多个索引在关系中找到元组后才能访问元组．

    • 执行 查找(lookup) 操作的事务 TiT_{i} 必须以 S 模式锁住其访问的所有索引叶节点．

      • 即使叶节点不包含任何满足索引查找条件的元组（例如，对于范围查询，叶节点中没有元组在这个范围内）．

    • 执行插入、更新或删除元组 tit_{i} 于关系 rr 的事务 TiT_{i}．

      • 必须更新关系 rr 锁拥有的所有索引．

      • 必须对所有受插入/更新/删除影响的索引的叶节点获取 X 锁．

    • 必须遵守两阶段锁协议的规则

Comments