事务

概念

事务是构成单一逻辑工作单元的操作集合
事务是访问并可能更新各种数据项的一个程序执行单元
事务由事务开始（begin transaction）与事务结束（end transaction）之间执行的全体操作组成
事务管理主要处理的两个主要问题
- 各类故障恢复，如硬件故障，系统崩溃等
- 多个事务的并发执行

ACID

事务是访问并可能更新各种数据项的一个程序执行单元

为保证数据的完整性，数据库系统必须保证:

原子性（ Atomicity ）：事务的所有操作在数据库中要么全部反映出来，要么完全不反映
一致性（ Consistency ）：事务隔离执行时（即在没有其他事务并发执行的情况下）保持数据库的一致性
隔离性（ Isolation ）：尽管多个事务可能并发执行，但是每个事务都感觉不到系统中有其他事务在并发的执行
- 对于任何一对事务 $T_i$ 和 $T_j$ ，在 $T_i$ 看来，$T_j$ 或者在 $T_i$ 开始之前已经完成执行，或者在 $T_i$ 完成之后开始执行
持久性（ Durability ）：一个事务成功完成后，它对数据库的改变是永久的，即使系统出现故障时也是如此

原子性和持久性

活动的：初始状态，事务执行时处于这个状态
部分提交的：最后一条语句执行后
失败的：发现正常的执行不能继续后
中止的：事务回滚并且数据库已恢复到事务开始执行前的状态后
- 重新开始事务：只有没有任何内部逻辑错误的时候才能执行
- 杀死事务
已提交的：成功完成执行的事务
- 撤销已提交事务所造成影响的唯一方法是执行一个补偿事务

![[images/Pasted image 20260110190828.png]]

隔离性

事务处理系统通常允许多个事务并发地执行。优点是：

提高吞吐量和资源利用率
减少等待时间：短事务不必等在长事务后面，减少平均响应时间

并发控制机制：实现事务隔离性的机制

控制并发执行的事务之间的相互作用，来避免他们破坏数据库的一致性

调度

指令执行顺序，指定并发执行事务的指令执行的时间顺序

一组事务的一个调度必须包含这一组事务的全部指令
必须保持指令在各个事务中出现的顺序
一个事务成功执行后，会有一条指令作为最后的声明
- 事务默认提交指令 COMMIT 为其最后一条指令
一个事务没有成功完成时，会用一条中止指令 abort 来作为最后的声明

SQL 中的事务定义

SQL 标准规定事务的开始是隐式的

事务的结束用下列 SQL 语句之一来表示：

COMMIT：提交当前事务并开始一个新的事务
ROLLBACK：回滚当前事务

在几乎所有的数据库系统中，默认每个 SQL 语句如果成功执行，也立即隐式提交事务

可串行化

假设：每个事务都能保持数据库的一致性

事务的串行执行是可以保持一致性的
如果一个调度等价于一个串行调度，那么这个调度就是可串行化的

按照调度的形式分为：

冲突可串行化
视图可串行化

冲突可串行化

冲突的指令

两条连续指令 $l_i$ 与 $l_j$ 分别属于事务 $T_i$ 与 $T_j$ ，当且仅当数据项 $Q$ 被 $l_i$ 和 $l_j$ 同时访问，并且至少有一个指令执行了 write(Q) 操作时才会发生冲突

$l_i$	$l_j$	冲突情况
read(Q)	read(Q)	不冲突
read(Q)	write(Q)	冲突
write(Q)	read(Q)	冲突
write(Q)	write(Q)	冲突

冲突可串行化

$l_i$ 和 $l_j$ 之间的冲突迫使它们之间有一个逻辑时间顺序

一个调度中，如果 $l_i$ 和 $l_j$ 在时间上连续并且不发生冲突，则可以交换这两条指令的顺序
如果调度 $S$ 可以通过一系列非冲突指令交换转换成 $S’$ ，称 $S$ 和 $S’$ 是冲突等价的
若一个调度 $S$ 与一个可串行调度冲突等价，则称调度 $S$ 是冲突可串行化的

![[images/Pasted image 20260110201614.png]]

左侧调度可以转换为右侧调度，右侧调度为串行调度，$T_2$ 在 $T_1$ 之后执行，因此该调度是冲突可串行化的

可恢复性

可恢复调度：如果 $T_j$ 读取了由 $T_i$ 所写的数据项，则 $T_i$ 需要先于 $T_j$ 提交

![[images/Pasted image 20260110201826.png]]

如果 $T_9$ 调度在 read 之后直接提交，则无法恢复
如果 $T_8$ 要中止，则 $T_9$ 会读到不一致的数据 A，数据库必须保证调度可恢复

级联回滚

级联回滚：因单个事务故障导致一系列事务回滚

![[images/Pasted image 20260110202003.png]]

如果 $T_{10}$ 失败，则 $T_{11}$ 和 $T_{12}$ 必须回滚

无级联调度

无级联调度：对于每对事务 $T_i$ 和 $T_j$ ，如果 $T_j$ 读取了先前由 $T_i$ 所写的数据项，则 $T_i$ 必须在 $T_j$ 这一读取操作前提交

不会发生级联回滚
无级联调度是可恢复的

并发控制

数据库必须提供一种机制来保证所有调度（目标）是

冲突可串行化
可恢复性，最好是无级联

一个策略是一个时间只允许一个事务，即产生一个串行调度，但是并发性能差

目标：建立一个能够保证串行化的并发控制协议

并发问题

并发级别

级别		描述
可串行化	Serializable	保证可串行化的执行
可重复读	Repeatable Read	只允许读取已提交数据，一个事务对相同数据的重复读取要返回相同的值（其他事务不得更改该数据），MySQL 默认
读已提交	Read Committed	只允许读取已提交数据，但不要求可重复读
读未提交	Read Uncommitted	允许读取未提交数据

以上所有隔离性级别都不允许脏写（但是可以脏读）：即如果一个数据项已经被另外一个尚未提交或中止的事务写入，则不允许对该数据项执行写操作

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

基于锁的协议

锁是用来控制对数据项的并发访问的一种机制

给数据加锁有两种方式：

共享锁(S)：对数据项只能读。使用 lock-S 指令
排他锁(X)：对数据项可写又可读。使用 lock-X 指令

unlock 指令释放锁

申请锁请求发送给并发控制管理器。只有在并发控制管理器授予所需锁后，事务才能继续其操作

锁相容性矩阵

表示为 comp(A, B)

![[images/Pasted image 20260110202939.png]]

指令之间的冲突对应于锁类型之间的不相容性

如果被请求锁与数据项上已有的锁相容，那么事务可以被授予该锁
- 一个数据项可以同时有多个共享锁
- 如果一个事务在某个数据项上拥有排他锁，那么其他事务不能再在这个数据项上加任何锁
如果一个锁不能被授予，那么请求该锁的事务必须等待，直到该数据项上的其他不相容锁全部释放，然后再被授予锁

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

在最后一次访问数据后，立即释放锁

上述锁无法有效地保证可串行化，需制定合理的封锁协议：一组规定事务何时对数据项进行加锁、解锁的规则。封锁协议限制了可能的调度数目

基于锁协议的隐患

死锁 Deadlock

![[images/Pasted image 20260110203204.png]]

lock-S(B) 导致 $T_4$ 等待 $T_3$ 释放锁
lock-S(A) 导致 $T_3$ 等待 $T_4$ 释放锁

造成死锁，必须回滚并释放锁

饿死 Starved

一个事务 $T_1$ 等待在一个数据项上加上排他锁，而同时存在一个事务序列 ${T_2\dots T_n}$，被授予在该数据项上加上了共享锁；$T_1$ 有可能被饿死

避免事务饿死的授权加锁方式：当事务 $T_i$ 申请对数据项 Q 加 M 型锁时，并发控制管理器授权加锁的条件须满足：

不存在在数据项 Q 上持有与 M 型锁冲突的锁的其他事务
不存在等待对数据项 Q 加锁且先于 $T_i$ 申请加锁的事务

封锁协议

先于

令 ${T_0, T_1,\dots, T_n}$ 是参与调度 $S$ 的一个事务集，如果存在数据项 Q，使得 $T_i$ 在 Q 上持有 A 型锁。后来，$T_j$ 在 Q 上持有 B 型锁，且 $comp(A, B) = false$，则称 $T_i$ 先于 $T_j$，记为 $T_i \rightarrow T_j$

如果 $T_i \rightarrow T_j$，这一优先意味着在任何等价的串行调度中， $T_i$ 必须出现在 $T_j$ 之前
如果调度 $S$ 是那些遵从封锁协议规则的事务集的可能调度之一，称调度 $S$ 在给定的封锁协议下是合法的
- 一个封锁协议当且仅当其所有合法的调度为冲突可串行化时，称它保证冲突可串行性
- 即对于任何合法的调度，其关联的事务优先关系是无循环的

两阶段封锁协议

这是一个能够保证冲突可串行化调度的协议

阶段一：增长阶段
- 事务可以获得锁
- 事务不能释放锁
阶段二：缩减阶段
- 事务不能获得新锁
- 事务可以释放锁

封锁点：在调度中该事务获得其最后加锁的位置（增长阶段结束点）

特点

两阶段封锁协议保证可串行化
- 事务可以按照封锁点来排序
两阶段封锁不能保证不发生死锁
两阶段封锁下很有可能发生级联回滚
- 为了避免这个问题，将该协议修改为严格两阶段封锁协议

严格两阶段封锁协议

严格两阶段封锁协议要求未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据

强两阶段封锁协议

更加严格：要求事务提交之前不得释放任何锁

事务可以按其提交（commit）的顺序串行化

多粒度

将多个数据项聚成一组，作为同步单元，无需单独对单个数据项进行加锁

多粒度：允许各种大小的数据项，并定义数据粒度的层次结构，可以图形化的表示为树

如果一个事务显式地对树中的某个节点加了锁，那么它也给所有同一模式下的该节点的子节点隐式地加了锁

锁的粒度：

细粒度 (树的低层): 高并发性，锁开销多
粗粒度 (树的高层): 低并发性，锁开销少

![[images/Pasted image 20260112100918.png]]

如事务 $T_i$ 需判定某个节点（如 rb1）是否可以加锁，必须从根结点进行遍历至该节点（开销大）

意向锁

除了排他锁及共享锁类型，多粒度下还有其他三种锁类型：

共享型意向锁(IS)：将在树的较低层进行显式封锁，但只能加共享锁
排他型意向锁(IX)：将在树的较低层进行显式封锁，可以加排他锁或共享锁
共享排他型意向锁(SIX)：= S + IX 以该节点为根的子树显式地加了共享锁，并且将在树的更低层显式地加排他锁

意向锁允许较高层的节点被加上共享锁或排他锁，而无需从树根遍历到子孙节点来检验锁的相容性，提升锁相容检验的效率

相容性矩阵

![[images/Pasted image 20260112101045.png]]

多粒度封锁模式

事务 $T_i$ 按如下规则对数据项 Q 加锁：

必须遵从锁类型相容函数
必须首先封锁树的根结点，并且可以加任意类型的锁
仅当事务 $T_i$ 当前对 Q 的父结点具有 IX 或 IS 锁时，对结点 Q 可加 S 或 IS 锁
仅当事务 $T_i$ 当前对 Q 的父结点具有 IX 时，对结点 Q 可加 X、 SIX 或 IX 锁
仅当 $T_i$ 未曾对任何结点解锁时，$T_i$ 可对结点加锁（满足两阶段封锁）
仅当 $T_i$ 当前不持有 Q 的子结点的锁时，$T_i$ 可对结点 Q 解锁

加锁按自顶向下的顺序，锁的释放按自底向上的顺序

基于时间戳的协议

时间戳

对于系统中每个事务 $T_i$，把一个唯一的固定时间戳和它联系起来，此时间戳记为 $TS (T_i)$；该时间戳是在事务 $T_i$ 开始执行前由数据库系统赋予的

若事务 $T_i$ 已被赋予时间戳 $TS(T_i)$，并且有一新事务 $T_j$ 进入系统，则 $TS(T_i) < TS(T_j)$

使用系统时钟/逻辑计数器作为时间戳

每个数据项 Q 需要与两个时间戳值相关联：

W-timestamp(Q)表示成功执行 write(Q)的所有事务的最大时间戳
R-timestamp(Q)表示成功执行 read(Q)的所有事务的最大时间戳

时间戳排序协议

时间戳排序协议保证任何有冲突的 read 或 write 操作按时间戳顺序执行

假设事务 $T_i$ 发出指令 read(Q)

若 $TS(T_i ) < \text{W-timestamp(Q)}$，则 $T_i$ 需要读入的 Q 值已被覆盖
- read 操作被拒绝
- $T_i$ 回滚
若 $TS(T_i )\geq \text{W-timestamp(Q)}$
- 执行 read 操作
- R-timestamp(Q)被设置为 $\max(\text{R-timestamp(Q)}, TS(T_i ))$

基于有效性检查的协议

有效性检查协议（适用于大部分只读事务的情况）要求每个事务 $T_i$ 在其生命周期中按两个或三个阶段执行

读阶段: 事务 $T_i$ 的所有 write 操作都是对局部临时变量进行的
有效性检查阶段: 事务 $T_i$ 进行有效性测试，判断是否可以执行 write 操作而不违反可串行性
写阶段: 如果 $T_i$ 已通过有效性检查，则保存任何写操作结果的临时局部变量值被复制到数据库中。只读事务不进入此阶段

每个事务必须按照以上顺序经历这些阶段。然而，并发执行的事务的三个阶段可以是交叉执行的

每个事务 $T_i$ 都有三个不同的时间戳

Start(Ti): 事务 Ti 开始执行的时间
Validation(Ti ): 事务 Ti 完成读阶段并开始其有效性检查的时间
Finish(Ti ): 事务 Ti 完成写阶段的时间

恢复系统

故障类型

事务故障
- 逻辑错误：由于某些内部条件而
- 无法继续正常执行
- 系统错误：系统进入一种不良状态（如死锁），结果事务无法继续正常执行
系统崩溃
- 硬件故障，或者是数据库软件或操作系统的漏洞，导致易失性存储器内容丢失，并使得事务处理停止
磁盘故障
- 由于磁头损坏或故障造成磁盘块上的内容丢失
- 毁坏是可探测的：磁盘驱动器用校验和来检测故障

恢复机制

保证数据库一致性以及事务的原子性的算法称为恢复算法

在正常事务处理时采取措施，保证有足够的信息可用于故障恢复
故障发生后采取措施，将数据库内容恢复到某个保证数据库一致性、事务原子性及持久性的状态

存储器类型

易失性存储器（volatile storage）：易失性存储器中的信息在系统崩溃时通常无法保存下来。例子有主存和高速缓冲存储器
非易失性存储器（nonvolatile storage）：非易失性存储器中的信息在系统崩溃时可以保存下来。这类存储器的例子有磁盘和磁带（但仍有可能丢失数据）
稳定存储器（stable storage）：稳定存储器中的信息永不丢失

数据访问

物理块是位于磁盘上的块
缓冲块是临时位于主存的块

磁盘和主存间的块移动是由下面两个操作引发的

input(B)传送物理块 B 至主存
output(B)传送缓冲块 B 至磁盘，并替换磁盘上相应的物理块

![[images/Pasted image 20260112093623.png]]

每个事务 $T_i$ 有一个私有工作区，用于保存 $T_i$ 所访问及更新的所有数据项的拷贝

必须在第一次访问 X 之前执行read(X)
write(X)可以在事务被提交前的任意时刻执行

恢复与原子性

为保证原子性，必须在修改数据库本身之前，首先向稳定存储器输出信息，描述要做的修改

目的：确保由中止事务所做的修改不会持久保存于数据库中，即回滚该中止事务

基于日志的恢复机制

日志是日志记录的序列。它记录数据库中的所有更新活动
日志保存于稳定存储器中

指令	日志形式
事务开始	`<Ti start>`
write(X)	`<Ti, X, V_old, V_new>`
提交事务	`<Ti, commit>`
事务中止	`<Ti, abort>`

使用日志的两种方法：

立即的数据库修改（事务提交前已修改）
延迟的数据库修改（事务提交后还未修改）

数据库修改

立即修改模式允许在事务提交前，将未提交的事务更新至缓冲区或磁盘
延迟修改模式直到事务提交时都没有更新到缓冲区/磁盘
- 简化了恢复
- 但是多了存储本地副本的开销

日志记录的更新必须在数据项被 write（数据库修改）之前完成

事务提交

当事务将其关于提交的日志记录输出到稳定存储器时，该事务被认为已提交

之前的所有日志记录必须都已经输出

事务提交时，由该事务执行的 write 操作结果可能仍在缓冲区，随后被输出

并发控制和恢复

在并发事务中，所有事务共享一个磁盘缓冲区和日志

一个缓冲块中的数据项可以来自多个事务的更新

假设如果一个事务 $T_i$ 修改了一个数据项，那么在 $T_i$ 提交前，其他事务不能修改同一个数据项（即不允许脏写）

未提交事务的更新不能被其他事务所见
可以通过在被更新数据项上获取排他锁，并持有该锁直到事务提交位置来保证 (严格两阶段封锁)

不同事务的日志记录在日志中穿插（interspersed）存储

Undo 和 Redo

对日志记录 <Ti, X, V1, V2> 的 Undo 操作将旧值 V1 写入 X
对日志记录 <Ti, X, V1, V2> 的 Redo 操作将新值 V2 写入 X

undo(Ti) 将事务 $T_i$ 所更新的所有数据项的值恢复成旧值，回到 $T_i$ 的最后一条日志记录

每次数据项 X 被恢复成旧值，日志记录会被写入
当事务的 undo 操作完成时，日志记录被写入

redo(Ti) 将事务 $T_i$ 所更新的所有数据项的值置为新值，从 $T_i$ 的第一条日志记录开始执行

这个情况下没有任何日志记录

从故障中恢复

当日志是以下状态时，事务$T_i$ 需要进行 undo 操作

有日志 <Ti start>
没有日志 <Ti commit> 和 <Ti abort>

当日志是以下状态时，事务 $T_i$ 需要进行 redo 操作

有日志 <Ti start>
有日志 <Ti commit> 和 <Ti abort>

如果事务 $T_i$ 之前执行了 undo 操作，被写入到日志，接着故障发生。为了从故障中恢复，$T_i$ 要执行 redo 操作

这样的 redo 操作重新执行了原先的所有操作，包括重新存储旧值
称为重复历史
看起来很浪费，但是最大程度地简化了恢复

检查点

对于日志中的所有事务做 redo/undo

如果系统已经运行了很长一段时间，那么处理整个日志很费时间
那些已经将输出更新到数据库的事务没必要 redo

流线型恢复过程周期性地执行检查点：

将当前位于主存的所有日志记录输出到稳定存储器上
将所有修改了的缓冲块输出到磁盘上
将一个日志记录 <checkpoint L> 输出到稳定存储器

执行检查点时，所有数据更新都停止

恢复时，仅考虑在检查点前最近开始的事务 $T_i$ ，及在 $T_i$ 后开始的事务

从日志末尾反向扫描，找到最近的 <checkpoint L> 记录
只有在 L未提交/中止的事务或者在检查点后开始的事务需要 redo 或 undo
检查点之前的已提交或者中止的事务已经将其更新输出到了稳定存储器

undo 操作可能需要一些早期的日志

继续从日志末尾反向扫描直到找到在 L 的每个事务 $T_i$ 的记录 <Ti start>

![[images/Pasted image 20260112095622.png]]

在 system failure 之前 commit 的进行 redo
在 system failure 发生时没有 commit 的进行 undo