Chapter 17 Transactions¶

1 Overview¶

事务（transaction）是一个访问并可能更新多个数据项的程序执行单元。数据库系统必须保证事务执行不会破坏数据完整性，即使系统发生故障，或多个事务并发执行。

示例：账户 A 向账户 B 转账 $50

read(A)
A := A - 50
write(A)
read(B)
B := B + 50
write(B)

事务处理主要面对两个问题：

故障（Failures）：硬件故障、系统崩溃、软件错误等可能让事务只执行了一部分。
并发执行（Concurrent execution）：多个事务同时运行时，可能互相看到中间结果或覆盖彼此更新。

2 Transaction Requirements¶

Why Atomicity?

若事务在 write(A) 之后、write(B) 之前失败，账户 A 已减少 $50，但账户 B 尚未增加 $50，数据库会进入不一致状态。

原子性（Atomicity）：事务的所有操作要么全部反映到数据库中，要么一个都不反映。系统必须保证部分执行事务的更新不会留在数据库里。
持久性（Durability）：事务一旦成功完成并通知用户，其更新就必须永久保留，即使之后发生软件或硬件故障也不能丢失。
一致性（Consistency）：事务在逻辑正确的前提下，把数据库从一个一致状态转换到另一个一致状态。

示例

在转账例子中，一致性要求是：

\[ A + B \text{ 的总和保持不变} \]

更一般地，一致性要求包括：

显式声明的完整性约束，如主键、外键、check 约束等。
隐式完整性约束，如所有账户余额总和减去贷款总额应等于现金库存等业务规则。

事务开始执行时必须看到一个一致数据库。事务执行期间，数据库可能暂时处于不一致状态；若事务逻辑正确，并且事务成功完成，则数据库最终必须重新回到一致状态。错误的事务逻辑本身也可能导致不一致，这不是并发控制或恢复机制能自动修复的问题。

隔离性（Isolation）：并发事务不能看到其他事务尚未完成的中间结果。

示例

若在转账事务的 write(A) 和 write(B) 之间，另一个事务 T2 读取 A、B 并打印 A+B，则 T2 会看到少了 $50 的中间状态。

T1: read(A)
T1: A := A - 50
T1: write(A)

T2: read(A), read(B), print(A+B)

T1: read(B)
T1: B := B + 50
T1: write(B)

最简单的隔离方式是让事务一个接一个串行执行（serially），但这会损失并发带来的吞吐量和响应时间优势。因此 DBMS 需要并发控制机制，在允许并发的同时控制事务间交互。

总结：ACID Properties

性质	含义
Atomicity	事务的所有操作要么全部成功，要么全部不生效
Consistency	若事务逻辑正确，事务单独执行时会保持数据库一致性
Isolation	并发执行时，每个事务看起来都像在与其他事务串行执行
Durability	事务提交后，其更新在系统故障后仍然保留

注：对任意两个事务 $T_i$ 和 $T_j$，隔离性要求在 $T_i$ 看来，要么 $T_j$ 在 $T_i$ 开始之前已经结束，要么 $T_j$ 在 $T_i$ 结束之后才开始。

3 Transaction State¶

状态	含义
Active	初始状态，事务正在执行
Partially committed	最后一条语句已经执行完成，但提交尚未最终完成
Failed	系统发现事务不能继续正常执行
Aborted	事务已经回滚，数据库恢复到事务开始前的状态
Committed	事务成功完成，更新已经提交

事务进入 aborted 状态后有两种处理方式：

重启事务（Restart the transaction）：如果失败不是事务内部逻辑错误导致的，可以重新启动事务。
终止事务（Kill the transaction）：如果事务本身逻辑错误或无法继续执行，则终止事务。

partially committed 不等于已经持久提交，事务执行完最后一条语句后，系统仍可能在写日志、刷新缓冲区等提交过程中失败。

4 Concurrent Executions¶

引入

允许多个事务并发运行有两个主要好处：

提高处理器和磁盘利用率：一个事务等待磁盘 I/O 时，另一个事务可以使用 CPU。
降低平均响应时间：短事务不必一直等待长事务结束。

并发控制方案（concurrency-control schemes）的目标是实现隔离性，即控制并发事务之间的交互，防止它们破坏数据库一致性。

调度（schedule）描述多个并发事务中各条指令的时间顺序，一个合法调度必须满足：

包含参与事务的所有指令。
保持每个单独事务内部指令的原有顺序。
成功完成的事务以 commit 作为最后一步，默认事务成功执行完后会执行 commit。
未成功完成的事务以 abort 作为最后一步。

示例

设 $T_1$ 表示从 A 向 B 转账 $50，$T_2$ 表示从 A 向 B 转移 A 当前余额的 10%，则：

Schedule 1：串行调度，$T_1$ 后执行 $T_2$

Schedule 2：串行调度，$T_2$ 后执行 $T_1$"

Schedule 3：非串行但等价于 Schedule 1

。

Schedule 4：破坏一致性的并发调度

5 Conflict Serializability¶

引入：可串行性（Serializability）

假设每个事务单独执行时都会保持数据库一致性，则一组事务的任意串行执行也会保持数据库一致性。

一个可能并发的调度若与某个串行调度等价，则称为可串行化（serializable）。不同的等价定义会得到不同的可串行化概念：

冲突可串行化（conflict serializability）
视图可串行化（view serializability）

为了分析调度，通常忽略事务中的普通计算，只保留数据库读写指令（read(Q) 和 write(Q)）。

事务可以在读写之间对本地缓冲区中的值进行任意计算，但简化调度中只关心读写操作的先后顺序。

设 $l_i$ 和 $l_j$ 分别是事务 $T_i$ 和 $T_j$ 的两条指令。若它们访问同一个数据项 $Q$，且至少有一条是写操作，则称 $l_i$ 和 $l_j$ 冲突（conflict）。

冲突会强制两个事务之间存在逻辑时间顺序。如果两条相邻指令不冲突，交换它们不会改变调度结果。

若调度 $S$ 可以通过一系列非冲突相邻指令交换变成调度 $S'$，则称 $S$ 与 $S'$ 冲突等价（conflict equivalent）。

若调度 $S$ 与某个串行调度冲突等价，则 $S$ 是冲突可串行化（conflict serializable）的。

Schedule 3 是冲突可串行化的

Schedule 3 可以通过交换非冲突指令，转换成一个 $T_1$ 在前、$T_2$ 在后的串行调度。

不可冲突串行化的例子

该调度无法通过交换非冲突指令变成 <T_3,T_4> 或 <T_4,T_3> 中的任意一个串行调度。

优先图（precedence graph）用于判断一个调度是否冲突可串行化。

给定事务集合 $T_1,T_2,\ldots,T_n$，构造有向图：

顶点是事务。
若 $T_i$ 和 $T_j$ 的某两条指令冲突，并且 $T_i$ 先访问发生冲突的数据项，则加入边 $T_i \to T_j$。
边可以用发生冲突的数据项标注。

调度冲突可串行化当且仅当其优先图无环。若优先图无环，可以对该图做拓扑排序，得到一个与调度冲突等价的串行顺序。

朴素环检测算法时间复杂度为 $O(n^2)$，其中 $n$ 是顶点数；更好的算法可达到 $O(n+e)$，其中 $e$ 是边数。

无环优先图的串行化顺序

若图无环，则所有满足图中偏序约束的拓扑序都可以作为合法的串行化顺序。

6 Recoverability¶

若事务 $T_j$ 读取了事务 $T_i$ 之前写过的数据项，则在可恢复调度（recoverable schedule）中，$T_i$ 的 commit 必须出现在 $T_j$ 的 commit 之前。换言之，读取了别人未提交结果的事务，不能先于被读取事务提交。

不可恢复调度

若 $T_9$ 在 read(A) 后立即提交，而 $T_8$ 随后中止，则 $T_9$ 已经读取并可能向用户展示了一个不一致状态。DBMS 必须避免这种调度。

级联回滚（cascading rollback）：一个事务失败后，所有读取了它未提交结果的事务也必须回滚，并可能继续触发更多回滚。

示例

若 $T_{10}$ 失败，则读取了它结果的 $T_{11}$ 必须回滚，读取了 $T_{11}$ 结果的 $T_{12}$ 也必须回滚。级联回滚可能撤销大量已完成工作。

无级联调度（cascadeless schedule）：若 $T_j$ 读取了 $T_i$ 写过的数据项，则 $T_i$ 的 commit 必须出现在 $T_j$ 的 read 之前。换言之，事务只能读取已经提交的数据。
- 无级联调度一定是可恢复调度，可恢复调度不一定无级联。
- 实际系统通常希望限制调度至少可恢复，并尽量无级联。

并发控制（Concurrency Control）

数据库必须提供机制，保证所有可能出现的调度满足：

冲突可串行化（Conflict serializable）：并发执行效果等价于某个串行执行。
可恢复（Recoverable）：事务失败时能正确恢复。
最好是无级联（Preferably cascadeless）：最好避免级联回滚。

一次只允许一个事务执行可以生成串行调度，但并发度太低。并发控制协议需要在允许的并发量和额外开销之间做权衡。

等调度已经执行完再检查是否可串行化通常已经太晚，可串行化测试的价值在于帮助理解和证明并发控制协议为什么正确。

并发控制的目标是设计协议，使所有由协议允许的调度都满足所需的可串行化和可恢复性要求。

7 Levels of Consistency in SQL¶

Weak Levels of Consistency

有些应用可以接受较弱的一致性级别，即允许某些不可串行化的调度，典型场景包括：

只读事务只想得到近似总余额。
查询优化器使用的数据库统计信息可以近似。

这类事务不一定需要相对于其他事务可串行化。弱一致性本质上是用准确性换取性能。

二级一致性（degree-two consistency）

S 锁可以在任意时刻释放。
事务可以在任意时刻继续获取锁。
X 锁必须持有到事务结束。

该级别不保证可串行化，程序员必须保证不会出现错误数据库状态。

游标稳定性（cursor stability）

读操作对每个元组加锁。
读取该元组后立即释放读锁。
X 锁仍持有到事务结束。

该级别可以避免某些脏读问题，但不能保证可串行化。

SQL 标准定义了多个隔离级别。隔离级别越弱，系统通常能提供越高并发，但允许的异常越多。

隔离级别	描述
Serializable	SQL 标准的默认隔离级别，效果应等价于串行执行
Repeatable read	只能读取已提交记录，重复读取同一记录应返回相同值，但不一定防止幻影读问题
Read committed	只能读取已提交记录，但连续两次读取同一记录可能得到不同的已提交值
Read uncommitted	允许读取未提交记录

上述级别都不允许脏写（dirty write），即一个事务覆盖另一个尚未提交事务写过的数据。

默认隔离级别

SQL 标准中的默认级别与具体数据库系统的默认实现不一定相同。很多实际系统默认不使用 serializable，例如 Oracle 和 PostgreSQL 默认使用的一致性级别是快照隔离（snapshot isolation），需要显式设置更强隔离级别。

Transaction Definition in SQL

SQL 的数据操纵语言必须能指定一组操作属于同一个事务。

在 SQL 中：

事务通常隐式开始。
commit work 提交当前事务，并开始新事务。
rollback work 中止当前事务，并撤销其更新。

很多数据库系统默认启用自动提交（auto-commit），每条 SQL 语句成功执行后都会隐式提交。可以通过数据库指令或客户端 API 关闭自动提交，例如 JDBC 中：

connection.setAutoCommit(false);