数据库笔记1：Transaction

引言

在实际场景中，数据库并不是完全可靠的。数据库可能在执行某些操作时崩了，导致一系列操作戛然而止。但有很多操作是必须一起执行的，比如银行转账，不能只执行从A账户扣钱，但不继续执行向B账户里加钱，这样会破坏数据一致性。

为了保证数据库在出现故障时，仍能保证数据的正确，我们引入了“事务”。

事务

A transaction is a unit of program execution that accesses and possibly updates various data items.

总的来说，事务（transaction）是一种机制，用来确保多个操作（如读取和写入数据）要么全部成功，要么全部失败，从而保持数据的一致性和完整性。事务中的所有操作作为一个整体，要么全部完成（提交），要么全部撤销（回滚），因此保证了数据在任何情况下都是一致的。

ACID性质

在数据库系统中，Transaction需要保持一下四个性质（ACID properties）：

原子性（Atomicity）：事务中的操作，要么全部执行，要么全部没执行。
一致性（Consistency）
隔离性（Isolation）
永久性（Durability）：事务成功完成后，即使系统出现故障，它对数据库所做的更改也会持久存在。

通俗地讲，一致性是指，在仅当前事务执行时（没有事务并发执行），数据库中的某些不变量要保持一致。比如银行转账时两个账户的余额之和要保持不变。（英文释义：If a transaction is run atomically in isolation starting from a consistent database, the database must again be consistent at the end of the transaction. ）

但是，像银行转账，先从A账户扣钱，再向B账户里转钱，必然有处于不一致状态的时候。执行一个事务时也是如此。我们必须保证：不一致状态是不可见的。这也是为什么要保证原子性——要么全做完，要么回退到全部没做，不能位于中间不一致状态。

原子性一般这样实现：数据库会记录一个事务对任何数据进行写操作前的旧值。这些信息被写入一个称为日志（log）的文件中。如果事务没有完成其执行，数据库系统会从日志中恢复旧值，使其看起来像事务从未执行过一样。而且日志记录需要发生在事务开始修改数据库之前（log records need to be written to stable storage before any changes are made to the database on disk.）

诚然，事务序列运行（serially）是更容易实现的，但多个事务的并发运行能显著地提升性能，就像“一个人干活 Vs 一群人同时干活”：

提升吞吐量和资源利用
减少事务等待时间

但是，如果多个事务并发执行，它们的操作可能以某种不理想的方式交错进行，导致数据库处于不一致的状态。这就需要隔离性（保证隔离性才能实现并行控制）。

隔离性是指，多个事务可能并发执行，数据库要保证：

对于任意两个事务 T_i 和 T_j 来说，T_i 看起来 要么是 T_j 在 T_i 开始之前就已经完成了执行，要么是 T_j 在 T_i 完成之后才开始执行。

从而实现，每个事务都不知道系统中同时执行的其他事务。

事务状态

为了跟准确地描述一个事务执行了多少，我们引入事务状态。

Active：初始状态，事务在执行过程中处于该状态。
Partially committed：在执行了最后一个语句之后，事务进入该状态。
Failed：在发现正常执行无法继续后，事务进入该状态。
Aborted：在事务被回滚（roll back）且数据库恢复到事务开始之前的状态后，事务进入中止状态。
Committed：在当前事务成功完成执行后，事务进入该状态。

特别地，我们需要小心：可观察的外部写操作（比如写入用户的屏幕，一旦发生，就不能撤销）。大多数系统允许这种写操作仅在事务进入Committed状态后才进行。

调度

调度（Schedule）是指一系列指令，并指定并发事务的指令在系统中执行的时间顺序。

且一个调度要满足：

对于一组事务的调度必须包含这些事务中的所有指令。
必须保持各个事务中指令的相对顺序（
成功完成执行的事务，其最后一个语句将是commit指令。
未成功完成执行的事务，其最后一个语句将是abort指令。

举一个例子：T1事务是从A转账50元到B，T2事务是A转账10%到B。下图的调度1是一个序列化的（serial）调度。

可序列化

等价（equivalent）有很多种，因此对应的可序列化（Serializable）也有多种。这里我们指的都是冲突等价和冲突可序列化。

如果一个调度是等价于一个序列调度，则称为可序列化的（serializable）。所谓等价，通俗地讲，则是两个调度的最终结果相同。之后我们会给出严格定义。

下图中，调度3与调度1等价，是可序列化的调度。

我们只关心read和write两类操作，特别是它们执行的先后顺序，忽略其他类型的操作。大多数时候出问题都是因为：最新值还未写入数据库，而另一事务已经提前读取或写入了数据。但需要指出的是：可能存在两个调度，它们产生相同的结果，但它们不是冲突等价的（相当于是“充分条件，但不必要”）。

我们考虑调度 S 中的两个连续的指令 I 、 J 。

如果 I 、 J 分别作用于不同的数据，那么它们的先后顺序不影响数据结果，怎么样都可以，不冲突。

如果 I 、 J 分别作用于同一个数据 Q ，那么有4种可能情况：

I = read(Q), J = read(Q)
I = read(Q), J = write(Q)
I = write(Q), J = read(Q)
I = write(Q), J = write(Q)

I 、 J 同时读取一个数据并不在意顺序，不冲突。但是 I 、 J 只要有至少一个是write操作，就会冲突（conflict），需要考虑其执行顺序。

从而我们可以严格的定义等价：

如果一个调度 S 可以通过一系列非冲突指令的交换转换为另一个调度 S’，我们称 S 和 S’ 是冲突等价（Conflict Equivalent）的。

可恢复性

Transaction T_j is dependent on T_i means that T_j has read data written by T_i .

到目前为止，我们都在假定事务不会失败的情况下讨论，但实际情况是事务失败总会发生。为了保证原子性，我们就必须撤销该事务的所有操作。但如果T_i 失败了，且 T_j 依赖于 T_i ，那么我们需要也将 T_j 撤销。

例如下图中，调度9中的T₇使用了T₆写入的A值，如果T₆结果出问题，则T₇结果也有问题。所以，T₇依赖于T₆ 。

可恢复调度（recoverable schedule）应当满足：

如果一个事务 T_j 读取了之前由事务 T_i 写入的数据项，那么事务 T_i 将在事务 T_j 提交之前提交。

可恢复性确保了：如果一个事务要用其他事务的数据项，则一定用的是最终数据，而不是过程中的数据。这样避免了一个数据出错导致一系列数据出错（级联效应）。

无级联的

像上面所所的，一个事务的失败可能触发一系列事务的回滚。这种情况称为级联回滚（cascading rollback）。这样的情况会大大降低数据库的性能。

所以我们希望调度是无级联的（cascadeless），亦即：

任意一对事务 T_i 和 T_j ，如果一个事务 T_j 读取了之前由事务 T_i 写入的数据项，那么事务 T_i 将在事务 T_j 提交之前提交。

不难发现，无级联则可恢复。