Chapter 13 : Transactions¶

约 3691 个字 20 行代码 15 张图片预计阅读时间 19 分钟

Transaction Concept¶

事务（Transaction）：一个访问或更新各种数据项的程序执行单元

对于事务我们主要需要考虑两个问题：

处理各种情况的错误（例如硬件错误和系统崩溃）
处理并发事务的执行（例如多个用户同时访问同一个数据项）

事务的四大性质——ACID，分别对应着：

原子性（Atomicity）：事务中的所有语句要么全部能作用在数据上，要么没有一条是发挥作用的
- 所以事务是不可分割的单元
- 如果执行事务的过程中发生任何故障，任何因该事务而发生的数据库改变必须被撤销
一致性（Consistency）：被隔离的事务执行保留了数据库的一致性
隔离性（Isolation）：即便多个事务兵法执行，系统也能保证：对于每一对事务 $T_i,T_j$，看起来就好像 $T_j$ 先于 $T_i$ 开始前完成，或者 $T_j$ 在 $T_i$ 完成后开始。因此某个事务不会关心，也不会干扰和它并发执行的其他事务
- 隔离性的要求可能会显著降低系统的性能
持久性（Durability）：事务成功结束后，对数据库的改变应该持续存在，即便发生了系统故障

A Simple Transaction Model¶

事务通过以下两种操作实现对数据的访问：
- read(X)：将数据项 X 从数据库传输到位于主存缓存中的变量（也称为 X），该变量属于执行读操作的事务
- write(X)：将执行写操作的事务对应的主存缓存中的变量 X 写到数据库的数据项 X 中

Example

我们假设有事务 Ti 为从账户 A 中转账 $50 至账户 B，那么该事务的定义为：

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

我们从 ACID 这 4 个角度来分析事务：

一致性：
- 该性质要求 A 和 B 账户金额之和在执行事务的过程中保持不变
- 该性质应由应用程序员负责维护，可以用完整性约束的自动测试来实现
原子性：
- 不一致状态（Inconsistent State）：不再真实反映数据库中应该被捕获的状态的系统状态。我们必须确保这样的一致性对数据库系统是不可见的。
- 为确保原子性，数据库系统会追踪任何数据的过去值，并记录在日志（Log）中。如果事务没能完成执行，数据库系统就能从日志中恢复过去值，这样就好像事务从来没有执行过。
持久性：
- 要保证持久性，需要做到：
  - 由事务实现的更新在事务结束前被写到硬盘上
  - 由事务实现的关于更新的信息也要被写到硬盘上，并且这个信息应该足以使数据库在遇到故障重启后能够重构更新
- 还是由数据库的恢复系统负责维护持久性
隔离性：
- 并发执行多个事务可能会导致这些事务操作的交错，这是我们不想看到的
- 一种解决方法是干脆让这些事务串行执行，但这样的话相比并发执行性能太拉垮了，所以实际的解决方案还是确保并发执行，但能够确保并发执行事务的结果和等价的按照时间顺序执行事务的结果是一样的

Transaction State¶

在一个简单的抽象事务模型中，一个事务必须处在以下状态中的其中一个：

活跃（Active）：初始状态，当事务正在执行时会保持该状态
部分提交（Partially Committed）：当最后一条语句被执行完后
失败（Failed）：当发现无法正常继续执行时
中止（Aborted）：当事务已被回滚，且数据库将状态恢复至该事务执行前的状态
提交（Committed）：事务成功结束执行后

基于上述状态，我们可以得到以下关于事务的状态图：

系统中允许多个事务并发执行，其优势包括：

提升处理器和磁盘利用率，从而提高事务吞吐量，例如：一个事务占用 CPU 的同时，另一个事务可进行磁盘读写
缩短事务的平均响应时间：短事务无需在长事务后等待

并发执行中也会出现一些异常情况：

丢失修改（Lost Update）：两个事务对同一数据项进行修改，第二个事务的修改覆盖了第一个事务的修改
- 我们可以通过加锁的方式来解决这个问题

读脏数据（Dirty Read）：一个事务读到了另一个事务未提交的数据

不可重复读（Nonrepeatable Read）：一个事务读到了另一个事务已提交的数据

幻读（Phantom Read）：一个事务读到了另一个事务已提交的数据，且该数据在该事务执行的过程中发生了变化

Schedules¶

调度（Schedules）：一组指定并发事务指令执行时序顺序的指令序列

一个事务集的调度必须包含这些事务的所有指令，且必须保持每个独立事务中指令的原有顺序
成功完成执行的事务将以提交指令作为最后一条语句，默认情况下，事务假定其最后一步执行提交指令
未能成功完成执行的事务将以中止指令作为最后一条语句

Example

假设我们有两个事务 T1 和 T2，它们的定义如下：

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

T2: read(A);
    temp := A * 0.1;
    A := A - temp;
    write(A);
    read(B);
    B := B + temp;
    write(B);

假如先让 T1 执行，后让 T2 执行，对应的执行序列如下：

颠倒两个事务的执行顺序后，对应的执行序列如下：

下面是和第一个执行序列等价的并行调度：

但是我们对并行调度进行一定调整，就不和第一个执行序列等价了：

Serializability¶

我们假设每个事务都能保持数据库的一致性，因此，事务集的串行执行能保持数据库的一致性。我们定义一个（可能是并发的）调度是可串行化的（Serializable），当且仅当它等价于某个串行调度。

我们有两种不同的调度等价形式：

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

Conflict Serializability¶

假设有一个调度 S，它有两条连续的指令 I , J，分别对应事务 Ti , Tj（i != j）。如果 I , J 引用不同的数据项，那么可以交换这两条指令，不会影响调度结果；但如果 I , J 引用相同数据项 Q 的话，那么两者的顺序就比较重要了——考虑 4 种情况：

I = read(Q), J = read(Q)：I, J的顺序不重要，谁先读谁后读不要紧
I = read(Q), J = write(Q)：若 I 先于 J，则 Ti 读取的不是 Tj 写下的值；若 J 先于 I，则 Ti 读取的 j 就是 Tj 写下的值，因此有必要考虑两者的顺序
I = write(Q), J = read(Q)：类似前一种情况
I = write(Q), J = write(Q)：虽然两条指令的顺序不会影响各自的事务，但会影响到下一次 read(Q) 的结果

直观而言，若操作 I 与 J 之间存在冲突，则会在两者之间形成（逻辑上的）时序约束，若 I 与 J 在调度中连续执行且无冲突，即使调换两者的执行顺序，最终结果仍将保持不变

如果调度 S 可通过交换一系列没有发生冲突的指令得到调度 S'，那么我们认为S , S'是冲突等价的（Conflict Equivalent）。特别地，如果调度 S 冲突等价于一个串行调度，那么称 S 是冲突可串行的（Conflict Serializable）

我们有一种简单而高效的用于确定调度的冲突可串行性的方法：我们为调度 S 绘制优先图（Precedence Graph）$G=(V,E)$，其中 $V$ 为顶点集（顶点代表事务），$E$ 为边集。而每条边 $T_i\rightarrow T_j$ 表示以下三种条件中的任意一条：

$T_i$ 在 $T_j$ 执行 read(Q) 前执行 write(Q)
$T_i$ 在 $T_j$ 执行 write(Q) 前执行 read(Q)
$T_i$ 在 $T_j$ 执行 write(Q) 前执行 write(Q)

如果 $T_i\rightarrow T_j$ 存在于优先图中，那么在任何和 S 等价的串行调度 S' 中，$T_i$ 必须出现在 $T_j$ 前面

Example

我们还是选取上面的例子，对于第一个调度和第二个调度，它们的优先图如下所示：

而第四个调度的优先图如下所示：

如果像上面的例子当中那样出现环（Cycle）的话，说明该调度不是冲突可串行的

事务的可串行性顺序（Serializability Order）是和优先图的偏序（Partial Order）一致的线性顺序。寻找该顺序的过程称为拓扑排序（Topological Sort）。下面同时展示了三张图，其中上面那张表示的是优先图，下面两张表示的是可能的 2 种拓扑排序：

View Serializability¶

设 $S$ 和 $S'$ 是两个具有相同事务集合的调度。若对每个数据项 $Q$ 均满足以下三个条件，则称 $S$ 和 $S'$ 是视图等价（View Serializable）的：

若在调度 $S$ 中事务 $T_i$ 读取 $Q$ 的初始值，则在调度 $S'$ 中事务 $T_i$ 也必须读取 $Q$ 的初始值；
若在调度 $S$ 中事务 $T_i$ 执行 read(Q) 操作且该值由事务 $T_j$ 写入（若有），则在调度 $S'$ 中事务 $T_i$ 也必须读取由同一事务 $T_j$ 的 write(Q) 操作产生的 $Q$ 值；
在调度 $S$ 中执行最终 write(Q) 操作的事务（若有），在调度 $S'$ 中也必须执行最终的 write(Q) 操作

我们定义一个调度 $S$ 是视图可串行化的，当且仅当它与某个串行调度视图等价

所有冲突可串行化的调度同时也是视图可串行化的，以下是一个视图可串行化但非冲突可串行化的调度示例：

上面的串行调度和 T27-T28-T29 是等价的

Recoverable Schedules¶

我们定义可恢复的调度（Recoverable Schedule）为：对于每一对事务 $T_i,T_j$，$T_j$ 读取先前由 $T_i$ 写入的数据，$T_i$ 的提交发生在 $T_j$ 的提交之前

Example

考虑以下调度：

由于事务 $T_6$ 没有包含 commit 或 abort 操作，因此我们称这样的调度为部分调度（Partial Schedule）

假如 $T_6$ 在提交发生前故障，由于 $T_7$ 依赖于（Dependent）$T_6$（$T_7$ 读取 $T_6$ 的写入值），所以此时 $T_7$ 必须中止。然而 $T_7$ 已经被提交了，无法中止，所以我们遇到了无法正确从 $T_6$ 故障中恢复的情况。像这样的调度称为不可恢复的调度（Unrecoverable Schedule）

Cascading Rollbacks¶

即便调度是可恢复的，要想正确地从故障中恢复事务 $T_i$，我们可能需要回滚多个事务，这种情况发生于有其他事务读取被 $T_i$ 写入的数据的时候。像这种单个事务故障导致一系列事务回滚的现象被称为级联回滚（Cascading Rollback）。比如对于下面的调度，如果 $T_8$ 发生故障，就需要级联回滚了：

我们不希望遇到级联回滚，因为这会带来很大的撤销工作量。我们称没有级联回滚发生的调度为无级联调度（Cascadeless Schedule），具体定义为：对于每一对事务 $T_i,T_j$，$T_j$ 读取 $T_i$ 先前写入的数据项，而 $T_i$ 的提交先于 $T_j$ 这一读操作。所以显然，所有无级联调度都是可恢复的

Concurrency Control & Serializability¶

数据库必须提供一种机制，确保所有可能的调度方案要么满足冲突可串行化或视图可串行化，同时保证可恢复性，并尽可能实现无级联回滚
在调度执行后才进行可串行化测试为时已晚
我们的目标是开发能够确保可串行化的并发控制协议，这些协议允许并发调度，但必须确保调度满足冲突/视图可串行化要求，且具备可恢复性和无级联特性
并发控制协议通常不会实时检查前驱图的生成过程，而是通过制定规则来避免非可串行化调度的产生
不同并发控制协议在允许的并发程度与系统开销之间各有权衡
可串行化测试有助于我们理解并发控制协议的正确性原理

Weak Levels of Consistency¶

某些应用程序可以接受较弱的（弱）一致性级别，允许非可串行化的调度
- 例如：一个只读事务想要获取所有账户的大致总余额
- 例如：用于查询优化的数据库统计信息可以是近似值
- 此类事务无需与其他事务保持可串行化
牺牲准确性以换取性能

Transaction Isolation Levels¶

SQL 标准提供了以下隔离等级（Isolation Level）：

可串行（Serializable）：通常能确保可串行化执行，但有些数据库系统在实现这个隔离等级时，会允许一些不可串行化的执行
可重复读取（Repeatable Read）：仅允许读取已提交的数据，并且要求某个事务对同一数据的两次读取之间，不允许其他事务对其更新
读取提交（Read Committed）：仅允许读取已提交的数据，但不要求可重复读取
读取未提交（Read Uncommitted）：允许读取未提交的数据；它是最低级的隔离等级

Concurrency Control Protocols¶

在这里只是一个简单的概要，具体的实现和细节在下一章会详细介绍

基于锁的协议
- 锁定整个数据库 vs 锁定数据项
- 锁的持有时长
- 共享锁与排他锁
基于时间戳的协议
- 事务时间戳分配（例如在事务开始时）
- 数据项存储两个时间戳：
  - 读时间戳
  - 写时间戳
- 时间戳用于检测乱序访问
基于验证的协议
- 乐观并发控制
- 事务间冲突率低
- 每个事务必须经历三个阶段：读阶段 $\rightarrow$ 验证阶段 $\rightarrow$ 写阶段

Chapter 13 : Transactions¶

Transaction Concept¶

A Simple Transaction Model¶

Transaction State¶

Schedules¶

Serializability¶

Conflict Serializability¶

View Serializability¶

Recoverable Schedules¶

Cascading Rollbacks¶

Concurrency Control & Serializability¶

Weak Levels of Consistency¶

Transaction Isolation Levels¶

Concurrency Control Protocols¶

评论