背景
事务的原子性是如何保证的？面试中不少被问到吧，这里涉及到事务以及数据的可恢复性，而数据可恢复性的基础技术就是日志，本文将讨论三种日志：undo、redo 和 undo/redo log。
日志：一种安全的方式记录数据变更的历史
说明
- 存储介质：内存和磁盘（仅讨论本文涉及到的），认为内存是易失的，磁盘是非易失的
- 事务：包含多个操作，具体 ACID 属性，所有操作要么全部成功（指数据持久化到磁盘中）, 要么完全失败（原子性）
-
<START T>：一条日志，表示开始事务 T -
<COMMIT T>：一条日志，表示提交 T -
<T,X,v>：一条日志，表示在事务 T 中，对 X 进行了修改，X 的旧值或新值为 v -
<T,X,v,w>：一条日志，表示在事务 T 中，对 X 进行了修改，X 的旧值为 v，新值为 w -
<ABORT T>：一条日志，表示事务 T 未成功
增加持久化操作部分，一个事务的操作可分为如下几个步骤：
| 步骤 | 操作 |
|---|---|
| 1 | 更新数据 A |
| 2 | 更新数据 B |
| 3 | 持久化 A |
| 4 | 持久化 B |
数据从磁盘中的读取暂不考虑
后续将以上述步骤来介绍几种日志。
undo log
记录变更前的数据（旧值）。
规则：
- U1：数据在持久化前，日志必须先落盘
- U2：所有数据落盘后，提交事务，并将 commit 日志落盘
日志两次落盘
采用 undo log 后，事务的执行步骤将变为：
| 步骤 | 操作 | 日志 |
|---|---|---|
| 1 | 开始事务 T | <START T> |
| 2 | 更新数据 A | <T,A,a> |
| 3 | 更新数据 B | <T,B,b> |
| 4 | 持久化 日志 | |
| 5 | 持久化 A | |
| 6 | 持久化 B | |
| 7 | 提交事务 T | <COMMIT T> |
| 8 | 持久化 日志 |
a，b 分别为 A 和 B 的旧值
数据恢复
根据日志<COMMIT T>，将事务分为已提交和未提交事务，分别处理：
- 已提交事务：按规则 U2，数据已全部落盘，故无需处理
- 未提交事务：从尾部（时间顺序）开始扫描日志，寻找未提交的事务（无
<COMMIT T>或<ABORT T>），按<T,X,v>将 X 的值设为v，修改完成之后写入一条日志<ABORT T>
可靠性保证
通过假设系统在不同步骤中奔溃，来验证该机制的可靠性：
- 在步骤 8 以后：所有数据和日志均已落盘，可靠
- 在步骤 5-8 之间：部分数据可能已落盘，根据规则 U1，落盘数据的日志肯定已落盘，因此按
<T,X,v>日志进行恢复即可 - 在步骤 5 之前：数据都在内存态，直接写入
<ABORT T>日志即可
redo log
记录变更后的数据（新值）。
规则：
- R1：数据在持久化前，日志必须先落盘，包括事务的 commit 日志
与 undo log 的区别：无需等待数据落盘即可提交事务
采用 redo log 后，事务的执行步骤将变为：
| 步骤 | 操作 | 日志 |
|---|---|---|
| 1 | 开始事务 T | <START T> |
| 2 | 更新数据 A | <T,A,a> |
| 3 | 更新数据 B | <T,B,b> |
| 4 | 提交事务 T | <COMMIT T> |
| 5 | 持久化 日志 | |
| 6 | 持久化 A | |
| 7 | 持久化 B |
a，b 分别为 A 和 B 的新值
数据恢复
按规则 R1，可以知道如果没有<COMMIT T>日志，事务 T 对数据库的所有变更都未落盘。
从首部扫描日志，按事务提交情况处理：
- 已提交事务：按
<T,X,v>日志写入新值 - 未提交事务：无需处理，写入
<ABORT T>日志
可靠性保证
通过假设系统在不同步骤中奔溃，来验证该机制的可靠性：
- 在步骤 5 以后：日志已落盘，数据可能未全部落盘，因此按
<T,X,v>日志写入新值，即可恢复 - 在步骤 1-5 之间：数据未落盘，直接标记事务未成功（
<ABORT T>）
undo/redo log
记录变更后的数据（新值）
规则：
- UR1：数据在持久化前，日志必须先落盘（undo 和 redo 规则的公共部分）
不关心事务提交和数据持久化的顺序
采用 redo log 后，事务的执行步骤将变为：
| 步骤 | 操作 | 日志 |
|---|---|---|
| 1 | 开始事务 T | <START T> |
| 2 | 更新数据 A | <T,A,a0,a1> |
| 3 | 更新数据 B | <T,B,b0,b1> |
| 4 | 持久化 日志 | |
| 5 | 持久化 A | |
| 6 | 提交事务 T | <COMMIT T> |
| 7 | 持久化 B |
a0，b0 分别为 A 和 B 的旧值，a1，b0 分别为 A 和 B 的新值
步骤 5，6，7 顺序可调换
数据恢复
- 从前往后：按 redo log 处理已提交事务
- 从后往前：按 undo log 处理未提交事务
可靠性保证
按 undo log 和 redo log 的逻辑来保证。
总结
| 日志类型 | 落盘时机 | 数据恢复 |
|---|---|---|
| undo log | 日志落盘2次，数据落盘前和事务提交后 | 对未提交事务，按日志恢复 |
| redo log | 事务提交后日志落盘，数据再落盘 | 对已提交事务，按日志恢复 |
| undo/redo log | 日志先于数据落盘，不管事务是否提交 | undo+redo |
问题：在上述的日志恢复过程中，都需要扫描整个日志文件，来执行恢复操作，这其中包括很多无效的日志读取操作，如何避免呢？
参考
- 《数据库系统实现》第六章 系统故障对策
