4.undo-log.md

5.3 undo 日志

日志就是记录事务相关操作的文件，每个改变数据库的操作都会生成日志记录，在系统故障发生之后，可以通过日志将数据库恢复到一致性状态。本节主要介绍回滚日志（undo log），它通过撤销未提交的事务来恢复数据库的一致性状态。

日志记录

日志由多个日志记录组成，每条日志记录对应一个重要操作，比如更新数据、删除数据、提交事务等，这些操作往往会改变数据库的一致性状态。日志空间最初在内存中由缓冲区管理器分配，日志记录则由日志管理器负责创建，缓存中的日志记录会尽快被写到持久性的存储介质中。

记录事务操作的几种日志记录类型如下：

1. [START T]：表示事务 T 开始。

2. [COMMIT T]：表示事务 T 已经完成。[COMMIT] 记录不能保证数据已经更新到磁盘上，如果需要应由日志管理器控制事务的逻辑。

3. [ABORT T]：表示事务 T 无法完成，需要终止。如果事务终止，那么它所做的任何更改都不能写到磁盘上，如果已经写到磁盘就必须消除这些影响。

4. [T, X, v]：undo 日志的一条更新记录，表示事务 T 改变了元素 X，它的原值是 v。更新记录在数据库对内存执行 WRITE 操作时产生，不需要记录数据库元素的新值。

事实上日志记录的类型还有很多，涉及的操作也不限于插入、更新、删除等基础操作，为了便于说明，在本节中只考虑对已有数据的更新操作。

undo 日志规则

为了保证数据能从系统故障中顺利恢复，undo 日志必须遵循以下两条规则：

R1：只有当形如 [T, X, v] 的日志记录写到磁盘后，事务 T 才能够改变数据库元素 X 的值。

R2：如果事务提交了，只有当事务 T 改变的所有数据库元素的值写到磁盘之后，[COMMIT T] 日志记录才能被写入（而且应该尽快）。

规则 R1 比较好理解，如果数据库元素已经发生改变但是没有记录下来，那么系统恢复时就无法知道数据库是否处于不一致的状态，也不知道数据库元素原来的值是什么，恢复流程也无法进行下去。R2 是由 undo 日志的性质决定的，如果 [COMMIT T]记录已经写入日志，那么磁盘上的数据一定全部更新了，不用撤销事务相关操作。但如果没有 [COMMIT T]记录，哪怕事务实际已经完成，也要撤销事务的所有操作，以保证数据库的一致性。

为了尽快将日志记录写到磁盘上，需要一条“刷写日志”命令来告诉缓冲区管理器将所有未持久化的日志写入磁盘。在后面的示例中，将这一命令记作“FLUSH LOG”。

【例 5.2】考虑上节例 5.1 中的事务，并将 undo 日志应用到其中，最终事务 T 的操作以及日志刷写操作流程如表 5-2 所示。

表 5-2

步骤	操作	t	A（内存）	B（内存）	A（磁盘）	B（磁盘）	日志
1							[START T]
2	READ(A, t)	15	15		15	15
3	t := t-10	5	15		15	15
4	WRITE(A, t)	5	5		15	15	[T, A, 15]
5	READ(B, t)	15	5	15	15	15
6	t := t+10	25	5	15	15	15
7	WRITE(B, t)	25	5	25	15	15	[T, B, 15]
8	FLUSH LOG
9	OUTPUT(A)	25	5	25	5	15
10	OUTPUT(B)	25	5	25	5	25
11							[COMMIT T]
12	FLUSH LOG

1. 事务的第 1 步，将 [START T] 记录写到日志中，标志着事务的开始。

2. 第 4 步，将 A 的新值写入缓冲区，并生成一条日志项 [T, A, 15] 记录 A 的旧值。

3. 第 8 步，将日志刷写到磁盘中，只有反映 A 和 B 发生变化的日志记录完成持久化，对 A 和 B 的修改才能落盘。

4. 第 11 步，创建 [COMMIT T] 日志记录，这一步必须在 A 和 B 的新值写到磁盘之后才能进行。

5. 第 12 步，刷写日志，整个事务彻底完成，这一步需要尽快，但不一定会立刻进行，中间还可能有其他事务的操作。

如果 [COMMIT T] 记录没有及时写到磁盘，在较长一段时间内查看日志都会认为事务 T 还未提交，这时候如果系统发生故障则可能需要撤销早已完成的事务。由于事务 T 可能和其他事务并行执行，如果其中一个事务刷写日志，那么事务 T 的日志记录可能比预期更早地出现在磁盘上。这对于反映数据原值的日志记录而言并没有影响，但对于 COMMIT 操作，必须等到 OUTPUT 全部完成之后才创建 [COMMIT T] 记录。

使用 undo 日志恢复数据

当有了前面的 undo 日志之后，就足以应对一般的系统故障了。现在假设系统故障发生了，事务 T 的部分更改已经应用到磁盘上，部分缓冲区中的更改却丢失了，此时数据库就可能处于不一致的状态。

首先考虑一种简单的方案：不管日志文件有多大，都要遍历整个日志。

恢复管理器首先将事务分成已提交事务和未提交事务，如果存在日志记录 [COMMIT T]，根据规则 R1 可知，事务 T 所做的更改已经全部写到磁盘，事务 T 不会影响数据库的一致性状态。

如果在日志记录中发现了 [START T] 记录，但是并未发现 [COMMIT T] 记录，那么事务 T 所做的更改可能只持久化了一部分，数据库就会处于不一致状态，这时必须撤销事务 T 所做的更改。当然也有可能，事务 T 更新的数据都写到了磁盘上，只是日志记录没有及时刷写下去，但是除了读到 [COMMIT T] 记录之外，无法判断事务是否已经提交，所以仍然只能撤销事务 T。

根据规则 R1，如果事务 T 修改磁盘上的元素 X，那么日志中必然存在 [T, X, v] 记录，系统恢复时依据该记录对数据库元素 X 写入旧值 v，无需考虑 X 是否真的被事务 T 修改了。

现在开始恢复数据，恢复管理器必须从尾部开始扫描日志，记住所有存在 [COMMIT T] 或 [ABORT T] 记录的事务 T，对于每一条 [T, X, v] 记录，有以下两种情况：

1. 如果事务 T 存在 COMMIT 记录，则无须做其他操作。

2. 如果事务 T 未完成（没有 COMMIT 记录）或者已终止（存在 ABORT 记录），那么需要将数据库中 X 的值修改为 v，以防系统故障前 X 的值就已经被修改。

扫描完所有日志并做了上述工作后，恢复管理器需要为未完成且未终止的每个事务 T 写入一条日志记录 [ABORT T]，然后刷写日志。在下次故障发生后，这些具有 ABORT 记录的事务仍然需要回滚，因为无法判断它们是因为系统故障终止还是因为事务本身的问题终止。

【例 5.3】考虑表 5-2 中的事务流程，系统可能随时发生故障，这里说明几种具有代表性的情况：

1. 故障发生在第 12 步之后：[COMMIT T]记录已经写到磁盘，进行恢复时判断事务 T 已经提交，与 T 相关的日志记录都将被忽略。

2. 故障发生在第 11 步和第 12 步之间：如果 COMMIT 记录已经刷写到磁盘（可能是其他事务执行的 FLUSH 命令），那么和情况 1 一样不需要做任何更改。如果 COMMIT 记录没有写到磁盘，那么恢复管理器认为 T 未完成，对于遇到的 [T, B, 15]、[T, A, 15] 记录，它会将 A 和 B 的值都重置为 15，最后还会写一条 [ABORT T] 记录到日志中。

3. 故障发生在第 10 步和第 11 步之间：COMMIT 一定没有写入，因此事务 T 未完成，会像情况 2 一样撤销。

4. 故障发生在第 8 步和第 10 步之间：由于 COMMIT 记录没有写入，事务 T 也会被撤销，虽然 A 和 B 的更新可能并未到达磁盘，仍然需要确保它们恢复到旧值。

5. 故障发生在第 8 步之前：现在日志是否到达磁盘并不确定，但是规则 R1 保证了日志先于数据到达磁盘，所以只要把遇到的修改记录全部撤销，就能恢复到事务 T 开始前的状态。

极端情况下，可能会在恢复数据的过程中再次发生系统故障，由于 undo 日志保存的是元素的旧值，所以无论执行多少次系统都能恢复到开始的状态，也就是说恢复步骤是幂等的。

检查点机制

使用 undo 日志恢复数据中说明了系统在恢复时需要检查整个 undo 日志。而一旦事务的 COMMIT 记录被写到磁盘上，该事务相关的记录就不再需要了。那么可以在 COMMIT 日志写入时把之前的日志全都删掉吗？答案是否定的，因为通常有多个事务同时执行，如果一个事务删掉 [COMMIT T] 以及之前的记录，另一些活跃事务在这之前的记录就可能会丢失。

解决上述问题一个简单的办法就是周期性地对日志做检查点，在一个检查点中可以：

1. 停止接受新的事务。

2. 等到所有活跃事务写入 COMMIT 或 ABORT 记录。

3. 将日志刷写到磁盘。

4. 写入日志记录 [CKPT] 并再次刷写日志。

5. 重新开始接受新的事务。

现在可以确保检查点之前执行的事务已经全部完成并提交，系统恢复时这些事务都不用撤销，所以检查点之前的日志都可以删除。此时从后往前扫描日志，未完成事务都是在检查点记录写入之后才能开始，所以它们的记录只可能出现在 [CKPT] 记录之后，当看到 [CKPT] 记录时，就知道已经扫描了所有未完成事务，之前的记录无需扫描。

【例 5.4】考虑一个事务并发执行的例子，假设某一时间日志内容为：

[START T1]

[T1, A, 10]

[START T2]

[T2, B, 20]

这时决定做一个检查点，由于存在活跃的事务 T1 和 T2，需要等到它们结束，并且从现在开始不再接受新的事务。检查点完成后日志可能的情况如表 5-3 所示。

表 5-3

[START T1]
[T1, A, 10]
[START T2]
[T2, B, 20]
[T2, C, 30]
[T1, E, 40]
[COMMIT T2]
[COMMIT T1]
[CKPT]
[START T3]
[T3, M, 50]

假设这时发生系统故障，从尾部开始扫描日志，可以判断 T3 是一个未完成事务，需要撤销。当看到[CKPT]记录时，就知道之前的事务已经提交，没必要再检查之前的日志记录，数据库已经恢复到一致性状态。

动态检查点

检查点机制 中描述的检查点技术已经足以解决系统故障后的数据恢复问题，但它存在一个问题：在进行检查点时数据库无法执行新的事务，如果当前活跃事务耗时较长，在用户看来系统似乎停止工作了。“动态检查点”的技术可以避免这一问题，它在系统进行检查点时允许新事务进入。

动态检查点的主要步骤如下：

1. 写入日志记录 [START CKPT(T1, ..., Tk)] 并刷写日志，其中 T1 到 Tk 是当前所有活跃事务。

2. 等待所有活跃事务提交或终止，期间允许其他新的事务执行。

3. 当 T1 到 Tk 全部完成时，写入记录 [END CKPT] 并刷写日志。

采用这种方式，在系统故障恢复时考虑两种情况（从后往前扫描日志记录）：

1. 如果先遇到 [END CKPT] 记录，那么所有未完成的事务都是在 START CKPT 记录之后开始的。因此只需要向前扫描直到 START CKPT 记录，之前的事务都已经完成，日志记录可以全部删掉。

2. 如果先遇到 [START CKPT(T1, ..., Tk)] 记录，那么故障发生在检查点过程中，除了 START CKPT 记录之后开始的事务，其他未完成事务都在 T1, ...,Tk 之中，所以只需要扫描到这些事务中最早的事务的 START 记录即可，之前的事务在检查点开始时就已经完成，不用再检查。

一旦 [END CKPT] 记录写到了磁盘，上一个 START CKPT 记录之前的日志内容可以全部删除。

【例 5.5】考虑例 5.4 中的情况，日志一开始状态如下：

[START T1]

[T1, A, 10]

[START T2]

[T2, B, 20]

现在开始做一个动态检查点，此时 T1 和 T2 是活跃的事务，将其写入日志记录：

[START CKPT(T1, T2)]

然后假设另一个事务 T3 开始了，后续日志的整体内容可能如表 5-4 所示。

表 5-4

[START T1]
[T1, A, 10]
[START T2]
[T2, B, 20]
[START CKPT(T1, T2)]
[T2, C, 30]
[START T3]
[T1, D, 40]
[COMMIT T1]
[T3, E, 50]
[COMMIT T2]
[END CKPT]
[T3, F, 60]

假设这时发生了系统故障，从尾部开始扫描日志，T3 由于是未完成的事务所以必须被撤销，由 [T3, F, 60] 记录可知需要将 F 的值恢复为原值 60。当发现 [END CKPT] 记录时，就知道所有未完成的事务都在前一个 START CKPT 后开始。继续扫描，发现 T1 和 T2 都已经提交，由 [T3, E, 50] 记录可知需要将 E 的值恢复为 50，最后扫描到 [START CKPT(T1, T2)]，至此就完成了数据库恢复。

现在假设故障发生在检查点过程中，故障后的日志内容如表 5-5 所示。

表 5-5

[START T1]
[T1, A, 10]
[START T2]
[T2, B, 20]
[START CKPT(T1, T2)]
[T2, C, 30]
[START T3]
[T1, D, 40]
[COMMIT T1]
[T3, E, 50]

从后往前扫描，可以确定 T3 和 T2 是未完成事务，当发现 [START CKPT(T1, T2)] 记录时，就知道其它可能未完成的事务为 T1，而已经扫描到了 [COMMIT T1]，并且也看到了 [START T3]，因而只需要继续扫描直到看到 [START T2] 记录，就完成了数据恢复。