Chapter 14 : Concurrency Control¶

约 4672 个字 12 张图片预计阅读时间 23 分钟

Lock-Based Protocols¶

一种确保隔离性的方法是要求被访问的数据项遵循一种相互排斥的规则：当某个事务访问数据项时，其他事务就不得修改这个数据项。实现这种要求的最常用的方法是仅允许对于数据项有锁（Lock）的事务访问该数据项。一般会提供多种锁模式，我们目前只关注这两种：

共享（Shared）：若事务 \(T_i\) 获得一个对于数据项 \(Q\) 的共享锁（Shared-Mode Lock）（记作 \(S\)），那么 \(T_i\) 可以读取 \(Q\)，但不能向 \(Q\) 写入
排他（Exclusive）：若事务 \(T_i\) 获得一个对于数据项 \(Q\) 的排他锁（Exclusive-Mode Lock）（记作 \(X\)），那么 \(T_i\) 可以读取并写入 \(Q\)

当事务访问数据项时，它会向并发控制管理器发起合适的请求（Request）；只有当并发控制管理器向事务授予（Grant）锁时，该事务才能继续后面的操作

这两种锁模式允许多个事务读取同一个数据项，但也给出了一次仅允许一个事务进行写访问的限制。我们可以用一个兼容性函数（Compatibility Function）来描述这一特征：假如有两个任意的锁模式 \(A,B\)，如果在数据项 \(Q\) 已经有锁模式 \(B\) 的情况下，事务 \(T_i\) 仍然能够被立即授予对于该数据项的锁模式 \(A\)，那么称模式 \(A\) 和模式 \(B\) 是兼容的（Compatible）。兼容性函数 comp(A, B) 可以用以下表格描述（值为 true 表明是兼容的）：

	\(S\)	\(X\)
\(S\)	True	False
\(X\)	False	False

可以看到，只有共享模式是相互兼容的，而一旦涉及到排他模式就是不兼容的

我们定义一些和锁相关的指令：

lock-S(Q)：向数据项 \(Q\) 发起共享锁请求
lock-X(Q)：向数据项 \(Q\) 发起排他锁请求
unlock(Q)：解锁数据项 \(Q\)
- 该指令不一定要放在事务的最后执行

要想访问数据项，事务 \(T_i\) 必须先锁住该数据项。如果该数据项已被其他事务锁住的话，并发控制管理器就不会向 \(T_i\) 授予锁，\(T_i\) 一直处于等待状态，直到所有不兼容的锁都被释放为止

The Two-Phase Locking Protocol¶

一种确保（冲突）可串行性的协议是两阶段锁协议（Two-Phase Locking Protocol），该协议要求每个事务分两个阶段发起加锁和解锁请求：

增长阶段（Growing Phase）：事务可能会获得锁，但不会释放任何锁
收缩阶段（Shrinking Phase）：事务可能会释放锁，但不会获得任何新的锁

在调度中，某个事务获取最后一个锁（在增长阶段的末尾）的节点被称为该事务的锁点（Lock Point)。调度中的事务可以按照锁点序排序，而这样的顺序正是可串行的顺序

该协议不保证不会出现死锁问题，而且可能会出现级联回滚（Cascading Rollback）的问题。为避免该问题发生，我们对原来的协议稍作修改，得到严格两阶段锁协议（Strict Two-Phase Locking Protocol）。该协议在原有协议的基础上，要求事务所有的排他锁必须被保留，直到该事务被提交为止。另一种变体是强严格两阶段锁协议（Rigorous Two-Phase Locking Protocol），它要求保留所有锁，直至事务被提交

为了提高并发程度，我们在基础的两阶段锁协议上增加一种锁转换（Lock Conversion）机制，它支持：

升级（Upgrade）：从共享锁到排他锁的转换，仅发生在增长阶段
降级（Downgrade）：从排他锁到共享锁的转换，仅发生在收缩阶段

需要注意的是，当数据项 \(Q\) 被其他事务以共享模式锁住时，尝试升级对 \(Q\) 的锁的事务会被要求强制等待

一种简单但被广泛使用的，用来在事务中自动生成合适的加锁和解锁指令的方案如下（基于读 / 写请求）：

当事务 \(T_i\) 发起 read(Q) 操作时，系统在该操作后发起 lock-S(Q) 指令
当事务 \(T_i\) 发起 write(Q) 操作时，系统检查 \(T_i\) 是否已经有 \(Q\) 上的共享锁：
- 如果有的话，系统在 write(Q) 之后发起 upgrade(Q) 指令
- 否则系统在 write(Q) 之后发起 lock-X(Q) 指令
在事务提交或中止后，该事务获得的所有锁都会被解锁

Implementation of Locking¶

锁管理器可被实现为一个独立进程，事务向其发送加锁和解锁请求
对于加锁请求，锁管理器通过发送锁授予消息进行响应（若发生死锁，则发送要求事务回滚的消息）
请求事务将等待直至收到响应
锁管理器维护一个称为锁表的数据结构，用于记录已授予的锁和待处理请求
锁表通常实现为内存中的哈希表，以被锁数据项的名称作为索引键，锁表的示意图如下：

锁表记录已授予的锁和等待请求，还会记录已授予或请求的锁类型
新请求会被添加到数据项的请求队列末尾，若与所有先前的锁兼容则被授予
解锁请求会删除对应请求，并检查后续请求是否可被授予
若事务中止，该事务所有等待中或已授予的请求将被删除
- 锁管理器可维护每个事务持有的锁列表以实现此机制

Deadlock Handling¶

假如存在一组等待事务 \(\{T_0,T_1,\cdots,T_n\}\)，使得 \(T_0\) 等待 \(T_1\) 加锁的数据，\(T_1\) 等待 \(T_2\) 加锁的数据，...，\(T_{n−1}\) 等待 \(T_n\) 加锁的数据，\(T_n\) 等待 \(T_0\) 加锁的数据。那么我们认为这些事务进入死锁（Deadlock）状态

下面介绍两种处理死锁问题的主要方法：

死锁阻止（Prevention）：确保系统不会进入死锁状态
死锁检测和恢复（Detection and Recovery）：允许系统进入死锁状态，但之后尝试从死锁状态恢复

如果死锁会带来相对较高的损失，那么可以采用死锁阻止；否则的话可以采用更加高效的死锁检测和恢复

Deadlock Prevention¶

死锁阻止协议确保系统永远不会进入死锁状态。一些预防策略包括：

要求每个事务在执行前锁定其所有数据项（预声明）
对所有数据项施加部分排序，并规定事务只能按照部分排序指定的顺序锁定数据项（基于图的协议）

基于超时的方案如下：

事务仅等待锁定的指定时间。超时后，事务回滚
因此不可能发生死锁
实现简单，但可能导致饥饿问题。此外，难以确定合适的超时间隔

类似死锁恢复，当事务的等待可能会导致死锁时，回滚该事务而不是继续等待

具体通过抢夺（Preemption）来实现：当事务 \(T_j\) 向已被 \(T_i\) 加锁的数据项请求锁时，通过回滚 \(T_i\)，将 \(T_i\) 的锁抢走，然后向 \(T_j\) 授予锁
为了控制抢占操作，我们需要为每个刚开始的事务赋予时间戳（Timestamp）（基于计数器或系统时钟）。系统仅用时间戳来决定事务是否需要等待或回滚。如果事务要回滚，那么在重启该事务时要保留旧的时间戳。下面给出两种使用时间戳的不同方案：
- 等待 - 死亡（Wait-Die）（非抢夺技术）：当事务 \(T_i\) 向已被 \(T_j\) 加锁的数据项请求锁时，仅当 \(T_i\) 的时间戳小于 \(T_j\)（\(T_i\) 比 \(T_j\) 更老）的时候，\(T_i\) 可以等待，否则需要回滚 \(T_i\)
- 受伤 - 等待（Wound-Wait）（抢夺技术）：当事务 \(T_i\) 向已被 \(T_j\) 加锁的数据项请求锁时，仅当 \(T_i\) 的时间戳大于 \(T_j\)（\(T_i\) 比 \(T_j\) 更新）的时候，\(T_i\) 可以等待，否则需要回滚 \(T_j\)（\(T_j\) 被 \(T_i\) “击伤”）
- 这两种方法的共同问题是会带来不必要的回滚

Deadlock Detection¶

死锁的情况可用一种称为等待图（Wait-For Graph）的有向图 \(G=(V,E)\) 表示，

其中顶点表示系统中的事务，边表示一个有序对 \(T_i\rightarrow T_j\)，表明事务 \(T_i\) 正在等待事务 \(T_j\) 释放其所需数据项的锁。
当事务 \(T_i\) 向正被 \(T_j\) 加锁的数据项发起加锁请求时，将 \(T_i\rightarrow T_j\) 插入到图中；当 \(T_j\) 不再持有该数据项的锁时，将这条边删掉。
当且仅当等待图中存在环时，系统中就出现了死锁。为了检测死锁，系统需要维护等待图，周期性地调用在图中搜索环的算法

下面两张等待图分别展示了无环和有环的情况：

Deadlock Recovery¶

检测到死锁时，必须回滚某些事务（作为牺牲者）以解除死锁。应选择回滚成本最低的事务作为牺牲者

回滚操作需确定回滚的范围：

完全回滚：中止事务并重新启动
更有效的方式：仅回滚到足以解除死锁的程度

若同一事务频繁被选为牺牲者，会导致“饿死”现象。为避免此问题，需将回滚次数纳入成本考量

Graph-Based Protocols¶

基于图的协议是两阶段锁定的替代方案
在数据项集合 \(D = \{d_1, d_2 ,\cdots, d_h\}\) 上定义一个偏序关系 \(\rightarrow\)
- 若存在 \(d_i\rightarrow d_j\)，则任何需要访问 \(d_i\) 和 \(d_j\) 的事务都必须先访问 \(d_i\) 再访问 \(d_j\)
- 这意味着集合 \(D\) 可视为有向无环图，称为数据库图

Tree Protocol¶

树协议是一种简单的图协议

仅允许排他锁
事务 \(T_i\) 的首个锁可施加于任意数据项上。此后，只有当数据项 \(Q\) 的父节点当前被 \(T_i\) 锁定时，\(T_i\) 才能对 \(Q\) 加锁
数据项可随时解锁
若某数据项已被 \(T_i\) 加锁并解锁，则 \(T_i\) 后续无法再次对其加锁

树形协议确保冲突可串行化且不会产生死锁，它的优点如下：

与两阶段锁定协议相比，树形锁定协议中的解锁操作可以更早进行
等待时间更短，并发性更高
协议无死锁
无需回滚操作

也有缺点如下：

该协议不能保证可恢复性或无级联回滚
- 需要引入提交依赖以确保可恢复性
事务可能需要锁定比实际需求更多的数据项
- 锁定开销增加，等待时间延长
- 可能导致并发性下降

在树形协议下可能出现的调度方案，在两阶段锁定协议下不可行，反之亦然

Multiple Granularity¶

允许数据项具有不同大小，并定义数据粒度的层次结构，其中较小粒度嵌套在较大粒度内
可通过树形结构图形化表示（但不要与树形锁定协议混淆）
当事务显式锁定树中的某个节点时，会隐式以相同模式锁定该节点的所有后代
锁定的粒度（在树中进行锁定的层级）：
- 细粒度（树中较低层级）：高并发性，高锁定开销
- 粗粒度（树中较高层级）：低锁定开销，低并发性

Example

我们有一棵树来表示层级：

这些层级从最顶层（最粗粒度）开始依次为：

数据库
区域
文件（表）
记录

Intention Lock Modes¶

除了共享锁（S）和排他锁（X）模式外，还存在三种多粒度锁模式：
- 意向共享锁（IS）：表示在树的较低层级显式加共享锁
- 意向排他锁（IX）：表示在较低层级显式加排他锁或共享锁
- 共享与意向排他锁（SIX）：该节点为根的子树被显式加共享锁，同时在较低层级显式加排他锁
意向锁允许高层级节点直接加S或X锁，而无需检查所有后代节点

算上一般的共享锁和排他锁，我们可以得到以下兼容函数：

在多粒度概念的基础上，我们可以得到多粒度锁协议（Multiple-Granularity Locking Protocol）。该协议利用上述 5 种锁来确保可串行性。它要求事务 \(T_i\) 在对某个节点 \(Q\) 加锁前必须遵循以下规则：

\(T_i\) 必须遵循上面给出的兼容函数
\(T_i\) 必须先对树的根节点加锁（可用任意锁模式）
仅当 \(T_i\) 已经对 \(Q\) 的父亲节点加上 IX 或 IS 锁时，\(T_i\) 可对 \(Q\) 加上 \(S\) 或 IS 锁
仅当 \(T_i\) 已经对 \(Q\) 的父亲节点加上 IX 或 SIX 锁时，\(T_i\) 可对 \(Q\) 加上 X, SIX 或 IX 锁
仅当 \(T_i\) 在先前没有解锁过时，\(T_i\) 才可以对节点加锁
仅当 \(T_i\) 没有对 \(Q\) 的任何孩子加锁时，\(T_i\) 才可以解锁 \(Q\)

可以看到，多粒度协议要求获取锁的顺序是自顶向下（Top-Down/Root-to-Leaf），而释放锁的顺序是自底向上（Bottom-Up/Leaf-to-Root）。并且死锁可能会发生

锁粒度升级：若某层级锁数量过多，则切换为更高粒度的 S 锁或 X 锁

Insert and Delete Operations¶

如果使用两阶段锁定：

删除操作只能在执行删除的事务对要删除的元组持有排他锁时进行
向数据库中插入新元组的事务将被授予该元组的 X 模式锁

插入和删除操作可能导致幻读现象

扫描关系的事务（例如查找 Perryridge 所有账户余额的总和）与在该关系中插入元组的事务（例如在 Perryridge 插入一个新账户）即使没有访问任何共同的元组，（概念上）也会发生冲突
如果仅使用元组锁，可能会导致不可串行化的调度。例如扫描事务看不到新账户，但读取了更新事务写入的其他元组
扫描关系的事务会读取描述该关系包含哪些元组的信息，而插入元组的事务则会更新这些信息
- 此类冲突应当被检测到，例如通过对该信息加锁来实现
一种解决方案：
- 为关系关联一个数据项，用于表示该关系包含的元组信息
- 扫描关系的事务需获取该数据项的共享锁
- 插入或删除元组的事务需获取该数据项的排他锁。（注：此数据项上的锁与单个元组上的锁互不冲突）
上述协议对插入/删除操作的并发支持度较低
索引锁定协议通过要求对特定索引桶加锁，能在防止幻读现象的同时提供更高的并发性

Index Locking Protocol¶

索引锁定协议：
- 每个关系必须至少有一个索引
- 事务只能通过关系上的一个或多个索引找到元组后才能访问它们
- 执行查找的事务 \(T_i\) 必须对所有访问的索引叶节点加 S 锁
  - 即使叶节点中不包含任何满足索引查找条件的元组（例如范围查询中，叶节点内没有元组落在该范围内）
- 对关系 \(r\) 中的元组 \(t_i\) 进行插入、更新或删除的事务 \(T_i\) 必须：
  - 更新 \(r\) 的所有索引
  - 并对受插入/更新/删除操作影响的所有索引叶节点加 X 锁
- 必须遵守两阶段锁定协议的规则
该协议可确保幻读现象不会发生

Multiversion Schemes¶

多版本机制通过保留数据项的旧版本来提高并发性
每次成功的写操作都会生成数据项的一个新版本
使用时间戳标记版本
当发出读操作 read(Q) 时，根据事务的时间戳选择 Q 的合适版本，并返回所选版本的值
只读事务永远无需等待，因为每次读操作都能立即获取到合适的版本

Multiversion Two-Phase Locking¶

区分只读事务与更新事务
- SET TRANSACTION READ ONLY;
- SET TRANSACTION READ WRITE;
更新事务
- 获取读锁和写锁
- 持有所有锁直至事务结束（遵循严格两阶段锁协议）
- 每次成功写入会为被修改数据项创建新版本
- 每个数据项版本具有唯一时间戳，其值来源于提交阶段递增的计数器 ts-counter
只读事务
- 启动前通过读取 ts-counter 当前值分配时间戳
- 当只读事务 \(T_i\) 执行 read(Q) 时，返回满足以下条件的版本内容：该版本时间戳是小于等于 \(TS(T_i)\) 的最大时间戳
当更新事务需要读取数据项时：
- 它会在该数据项上获取一个共享锁（S锁），并读取最新版本
当更新事务要写入一个数据项时：
- 它会先获取该数据项的 X 锁；然后创建该数据项的新版本，并将此版本的时间戳设置为 \(\infty\)
当事务Ti更新完成时，将执行提交处理：
- \(T_i\) 将其创建的数据版本时间戳设置为 ts-counter + 1
- \(T_i\) 将 ts-counter 的值递增 1
- 释放其持有的所有锁
当一个只读事务 \(T_i\) 发出读操作 read(Q) 时，返回的值是时间戳小于等于 \(TS(T_i)\) 的最大时间戳对应版本的内容
仅产生可序列化的调度

MVCC : Implementation Issues¶

创建多个版本会增加存储开销
- 额外的元组
- 每个元组中需要额外空间存储版本信息
过时版本应被垃圾回收
- 在所有时间戳小于等于系统中最老只读事务时间戳的版本中，保留最年轻的版本 \(Q_k\)，其余比 \(Q_k\) 更早的版本均可删除

Chapter 14 : Concurrency Control¶

Lock-Based Protocols¶

The Two-Phase Locking Protocol¶

Implementation of Locking¶

Deadlock Handling¶

Deadlock Prevention¶

Deadlock Detection¶

Deadlock Recovery¶

Graph-Based Protocols¶

Tree Protocol¶

Multiple Granularity¶

Intention Lock Modes¶

Insert and Delete Operations¶

Index Locking Protocol¶

Multiversion Schemes¶

Multiversion Schemes¶

Multiversion Two-Phase Locking¶

MVCC : Implementation Issues¶

评论