Chapter 19 Recovery System¶

Recovery with Early Lock Release ARIES Recovery Algorithm Remote Backup Systems

1 Overview¶

恢复系统（recovery system）的目标是在事务失败、系统崩溃或存储介质故障后，把数据库恢复到满足 atomicity、consistency、durability 的状态。

故障类型	含义
Logical error	事务内部条件导致不能继续执行，如非法输入、完整性约束违反等
System error	数据库系统因错误条件主动终止事务，如死锁
System crash	电源、硬件或软件故障导致系统崩溃
Disk failure	磁头损坏或类似磁盘故障破坏全部或部分磁盘内容

Fail-stop assumption

假设非易失性存储（nonvolatile storage）内容在系统崩溃后没有被破坏。

数据库系统通常通过 checksums 等完整性检查防止磁盘数据静默损坏。对磁盘故障，假设破坏是可检测的，磁盘驱动器可以用 checksums 检测失败。

Main Points of Recovery

以事务 $T_i$ 从账户 A 向账户 B 转账 $50 为例：

更新 A：A := A - 50
更新 B：B := B + 50

若数据库只写出了其中一个更新就发生故障，数据库会不一致；若事务已经提交但更新没有写出到数据库，又会丢失已提交更新。因此恢复算法包含两类工作：

正常执行期间的动作：记录足够的信息，使之后可以从故障中恢复。
故障之后的动作：根据记录的信息恢复数据库内容，保证原子性、一致性和持久性。

2 Storage Structure¶

存储类型	survive system crashes or not	示例
Volatile storage	否	main memory、cache memory
Nonvolatile storage	是，但介质本身仍可能失败	disk、tape、flash memory、battery-backed RAM
Stable storage	理想上可跨所有故障保留	实际系统用多个非易失介质副本近似实现

Stable-Storage Implementation

稳定存储通常为每个块维护多个副本，副本可以放在不同磁盘甚至远程站点，以抵抗火灾、洪水等灾难。

块传输可能有三种结果：

结果	含义
Successful completion	目标块被正确写入
Partial failure	目标块被写坏，包含错误信息
Total failure	目标块完全没有被更新

若每个块有两个物理副本，一种简单输出方案是：

先把信息写到第一个物理块。
第一个写入成功后，再写同样的信息到第二个物理块。
第二个写入成功后，整个 output 操作才算完成。

若故障发生在输出过程中，两个副本可能不一致。恢复时要找出可能不一致的块：

昂贵方案：比较每个磁盘块的两个副本。
更好的方案：在非易失性存储中记录正在进行的磁盘写操作，恢复时只检查这些可能不一致的块。

若某个副本校验和错误，用另一个副本覆盖它。

若两个副本校验和都正确但内容不同，则用第一个副本覆盖第二个副本、硬件 RAID 系统会使用类似思想。

概念	含义
Physical block	磁盘上的块
System buffer block	主存中临时保存的块
`input(B)`	将磁盘物理块 `B` 读入主存
`output(B)`	将缓冲块 `B` 写回磁盘，替换对应物理块

为简化讨论，假设每个数据项都完整存放在一个块中。

每个事务 $T_i$ 有自己的私有工作区（private work-area），用于保存它访问和更新的数据项的本地副本。

$T_i$ 对数据项 X 的本地副本记为 $x_i$，包含 X 的块记为 $B_X$。

操作	含义
`read(X)`	把系统缓冲区中数据项 `X` 的值赋给本地变量 $x_i$
`write(X)`	把本地变量 $x_i$ 的值写入缓冲块中的数据项 `X`

事务第一次访问 X 前必须执行 read(X)，后续访问可以使用本地副本。

write(X) 可以在事务提交前任意时刻执行，但 output(B_X) 不必紧跟 write(X)，系统可以在合适时机再把缓冲块写回磁盘。

3 Log-Based Recovery¶

日志（log）保存在稳定存储上，是一串日志记录（log records），记录数据库更新活动。基于日志的恢复思想是：在修改数据库本身之前，先把描述修改的信息写到稳定存储。

Example of Data Access

日志记录	含义
`<Ti start>`	事务 $T_i$ 开始
`<Ti, X, V1, V2>`	$T_i$ 将 `X` 从旧值 `V1` 更新为新值 `V2`
`<Ti commit>`	$T_i$ 完成最后一条语句并提交
`<Ti abort>`	$T_i$ 已完成回滚

方式	含义
Immediate database modification	$·$ 允许未提交事务的更新在提交前写入缓冲区或磁盘 $·$ 更新块可以在事务提交前或提交后输出到磁盘，输出顺序也可以不同于事务写入顺序 $·$ 更新日志记录必须先于对应数据库数据项写出 $·$ 数据页输出到磁盘前，与该页相关的日志记录必须先输出到稳定存储
Deferred database modification	$·$ 到事务提交时才把更新写入缓冲区或磁盘 $·$ 简化了部分恢复逻辑，但需要保存本地副本，开销更大

Immediate Database Modification Example

Transaction Commit

事务的 commit 日志记录输出到稳定存储时，事务才称为已经提交。此时：

该事务之前的所有日志记录都必须已经输出到稳定存储。
该事务执行过的写操作仍可能只在缓冲区中，之后才写入磁盘。

Concurrency Control and Recovery

并发事务共享同一个磁盘缓冲区和同一个日志。一个缓冲块中的不同数据项可能由一个或多个事务更新，多个事务的日志记录也会交错出现。

为保证 undo 可行，若事务 $T_i$ 修改了某个数据项，在 $T_i$ 提交或中止前，其他事务不能修改同一个数据项。否则若 $T_1$ 修改 A，随后 $T_2$ 修改 A 并提交，最后 $T_1$ 中止，就很难恢复 A 的正确状态。

这一点通常通过严格两阶段锁协议实现：对更新项获取排他锁，并持有到事务结束。

4 Log and Database Buffering¶

4. 1 Log Record Buffering¶

日志记录通常先缓存在主存中，而不是每条都立刻输出到稳定存储。日志缓冲区在以下情况输出：

日志缓冲块满。
执行 log force 操作。

事务提交时需要 log force，把该事务的所有日志记录（包括 commit 记录）强制输出到稳定存储。这样多个日志记录可以合并成一次输出，降低 I/O 成本。

若日志记录被缓冲，必须遵守：

日志记录按创建顺序输出到稳定存储。
只有 <Ti commit> 已输出到稳定存储，$T_i$ 才能进入 committed 状态。
主存中的数据块输出到数据库前，该块相关的日志记录必须已输出到稳定存储，即 WAL。

Write-Ahead Logging, WAL

预写日志规则（write-ahead logging, WAL）要求在主存中的数据块写入数据库之前，与该块中数据相关的日志记录必须先写入稳定存储。严格说，WAL 至少要求用于 undo 的信息先于数据块输出。

4. 2 Database Buffering¶

数据库在主存中维护数据块缓冲区。若缓冲区满，需要淘汰某个块；若被淘汰块已被修改，则必须写回磁盘。

策略	含义	恢复需求
No-force	事务提交时，不要求把更新块立即写回磁盘	已提交更新可能未落盘，因此需要 redo
Steal	含有未提交更新的块可以在事务提交前写回磁盘	未提交更新可能已落盘，因此需要 undo

脏页（dirty pages）可以由后台线程或进程周期性输出。

4. 3 Latches¶

若含有未提交更新的块要输出到磁盘，必须先把该更新的 undo 日志信息写到稳定存储。

同时，块输出期间不能有更新正在进行，可以用短期锁存器（latch）保证：

写数据项前，事务获取包含该数据项的块上的排他 latch。
写入完成后即可释放 latch。
输出块到磁盘时，先获取块上的排他 latch。
执行 log flush。
将块输出到磁盘。
释放 latch。

Latch 与 Lock

latch 是短时间持有的内部同步机制，用来保护缓冲页的物理一致性。

事务锁用于并发控制，通常持有到协议允许释放为止。

4. 4 Buffer Management¶

数据库缓冲区可以实现为数据库预留的一块真实主存区域，也可以实现为虚拟内存中的区域。

预留真实主存的缺点是内存分区提前固定，缺少灵活性，操作系统知道当前内存需求，却不能动态调整数据库缓冲区和其他应用之间的划分。

实际系统通常用虚拟内存实现数据库缓冲，但会带来 dual paging problem：操作系统淘汰已修改的缓冲页时，会把它写到 swap space。数据库之后要把该缓冲页写回数据库文件时，可能还要先从 swap space 读回，再写到数据库磁盘，这会产生额外 I/O。

理想情况下，操作系统淘汰数据库缓冲页时应把控制交给数据库：若该页已修改，数据库先遵守 WAL 将日志写出，再把页写到数据库文件，然后释放该页。但常见操作系统并不支持这种协作。

5 Redo and Undo Operations¶

对日志记录 <Ti, X, V1, V2>：

操作	效果
redo	将 `X` 写成新值 `V2`
undo	将 `X` 恢复为旧值 `V1`

对整个事务：

redo(Ti)：从 $T_i$ 的第一条更新日志开始向前扫描，把 $T_i$ 更新过的所有数据项设置为新值，此过程不再额外写日志。
undo(Ti)：从 $T_i$ 的最后一条更新日志开始向后扫描，把 $T_i$ 更新过的所有数据项恢复为旧值。

undo 事务时，每恢复一个数据项 X 的旧值 V，就写出一个特殊的 redo-only 日志记录 <Ti, X, V>，也称 compensation log record。事务 undo 完成后，写出 <Ti abort>，表示回滚已经完成。

redo 和 undo 的使用场景

正常运行期间事务因逻辑错误不能完成时，需要 undo 该事务。
系统故障恢复期间，需要 redo 和 undo。
如果恢复过程中再次故障，之前写出的 redo-only / compensation 记录可以让恢复过程继续正确执行。

若日志中包含 <Ti start>，且包含 <Ti commit> 或 <Ti abort>，则需要 redo $T_i$。
若日志中只包含 <Ti start>，不包含 <Ti commit> 和 <Ti abort>，则需要 undo $T_i$。

为什么已经 abort 的事务仍要 redo？

若日志中已有 <Ti abort>，说明 $T_i$ 的 undo 已经完成，undo 期间写出的 redo-only 记录也在日志中。

因此 redo $T_i$ 会重复原先的历史：先重做原更新，再重做那些把数据恢复为旧值的 redo-only 记录，最终效果仍是 $T_i$ 被撤销。这种思想称为 repeating history，可以简化恢复算法。

Immediate Modification Recovery Example

设事务 $T_0$ 把 A 从 1000 改为 950、把 B 从 2000 改为 2050，事务 $T_1$ 把 C 从 700 改为 600。

情形	恢复动作
$T_0$ 未提交	`undo(T0)`，把 `B` 恢复为 `2000`、`A` 恢复为 `1000`，并写出 `<T0, B, 2000>`、`<T0, A, 1000>`、`<T0 abort>`
$T_0$ 已提交，$T_1$ 未提交	`redo(T0)` 并 `undo(T1)`，把 `A`、`B` 设为 `950`、`2050`，把 `C` 恢复为 `700`，并写出 `<T1, C, 700>`、`<T1 abort>`
$T_0$ 与 $T_1$ 都已提交	`redo(T0)` 并 `redo(T1)`，把 `A`、`B`、`C` 分别设为 `950`、`2050`、`600`

该例还说明包含 C 的块 $B_C$ 可以在 $T_1$ 提交前输出，包含 A 的块 $B_A$ 也可以在 $T_0$ 提交后才输出。

6 Checkpoints¶

如果恢复时处理整个日志，系统运行越久恢复越慢，而且可能重复 redo 那些更新已经写到数据库的事务，因此需要周期性 checkpoint。

6. 1 Basic Checkpointing¶

普通 checkpoint 会暂时停止所有更新，并执行：

将当前主存中的所有日志记录输出到稳定存储。
将所有已修改缓冲块输出到磁盘。
在稳定存储日志中写入 <checkpoint L>，其中 L 是 checkpoint 时仍活跃的事务列表。

恢复时：

从日志末尾向后扫描，找到最近的 <checkpoint L>。
只有 L 中的事务和 checkpoint 之后开始的事务需要 redo 或 undo。
checkpoint 前已经提交或中止的事务，其更新已经输出到稳定存储，不需要恢复处理。
但 undo 可能仍需要更早日志，因此还要继续向后扫描，直到对 L 中每个事务 $T_i$ 都找到 <Ti start>。
早于这些最早 <Ti start> 的日志部分恢复时不再需要，可以在需要时删除。

Example of Checkpoints

若 T1 在 checkpoint 前已经完成，T2、T3 需要 redo，T4 故障时仍未完成，则：

T1 可以忽略，因为 checkpoint 已经把它的更新输出到磁盘。
T2 和 T3 redo。
T4 undo。

6. 2 Recovery Algorithm¶

阶段	作用
Redo phase	重放所有相关事务的更新，不区分 committed、aborted 或 incomplete
Undo phase	撤销所有未完成事务

Redo phase

找到最后一个 <checkpoint L>，将 undo-list 初始化为 L。
从该 checkpoint 向前扫描到日志末尾。
1. 遇到 <Ti, Xj, V1, V2>，把 Xj 写成 V2。
2. 遇到 <Ti start>，把 $T_i$ 加入 undo-list。
3. 遇到 <Ti commit> 或 <Ti abort>，把 $T_i$ 从 undo-list 删除。

Undo phase

从日志末尾向后扫描。
若遇到 <Ti, Xj, V1, V2> 且 $T_i$ 在 undo-list 中：
- 把 Xj 写回旧值 V1。
- 写出 <Ti, Xj, V1>。
若遇到 <Ti start> 且 $T_i$ 在 undo-list 中：
- 写出 <Ti abort>。
- 将 $T_i$ 从 undo-list 删除。
undo-list 为空时停止。
undo phase 完成后，系统可以恢复正常事务处理。

Example of Recovery

6. 3 Fuzzy Checkpointing¶

普通 checkpoint 会长时间暂停正常更新。模糊检查点（fuzzy checkpointing）允许 checkpoint 期间继续更新：

暂时停止所有事务更新。
写入 <checkpoint L> 日志记录，并 force log 到稳定存储。
记录当前已修改缓冲块列表 M。
允许事务继续执行。
将列表 M 中的已修改缓冲块输出到磁盘。
- 块输出期间不能被更新。
- 必须遵守 WAL，即该块相关日志先于块输出。
在磁盘固定位置 last_checkpoint 中保存指向该 checkpoint 记录的指针。

恢复时从 last_checkpoint 指向的 checkpoint 记录开始扫描。该位置之前的日志记录，其更新已经反映到磁盘数据库中，不需要 redo。

若系统在 checkpoint 过程中崩溃，只要 last_checkpoint 尚未更新，就会继续使用上一个完整 checkpoint，因此可以安全处理 incomplete checkpoint。

6. 4 Failure with Loss of Nonvolatile Storage¶

前面的恢复算法假设非易失性存储没有丢失。若磁盘内容可能丢失，需要类似 checkpoint 的 dump 技术：

周期性把整个数据库内容 dump 到稳定存储。
dump 期间不允许有活跃事务，需要先执行类似 checkpoint 的过程。
将主存中的所有日志记录输出到稳定存储。
将所有缓冲块输出到磁盘。
把数据库内容复制到稳定存储。
在稳定存储日志中写入 <dump>。

磁盘故障恢复时：

从最近的 dump 恢复数据库。
查阅日志，redo 所有 dump 之后提交的事务。

该方法可以扩展为允许 dump 期间仍有事务活跃，称为 fuzzy dump 或 online dump，思想类似 fuzzy checkpointing。

7 Recovery with Early Lock Release and Logical Undo¶

某些高并发并发控制技术会提前释放锁，例如 B+ 树并发控制。为了支持这类技术，恢复系统需要 logical undo，并且恢复过程通常基于 repeating history，恢复时执行与正常处理完全相同的动作。

7. 1 Logical Undo Logging¶

B+ 树插入、删除等操作会提前释放锁，不能简单通过恢复旧值完成 undo。原因是锁释放后，其他事务可能已经更新了同一 B+ 树结构，物理地写回旧值可能破坏后续更新。

因此：

插入操作的 undo 通常是执行对应删除操作。
删除操作的 undo 通常是执行对应插入操作。
undo 日志记录中需要包含要执行的 undo operation。

这种日志称为 logical undo logging，与记录旧值的 physical undo logging 相对。被这样记录的操作称为 logical operations。

Logical undo examples

为撤销 tuple insert，执行 tuple delete。
对空间分配信息提前释放锁时，用逻辑操作撤销空间分配。
为撤销 deposit，可以执行 subtract deposited amount，这允许提前释放账户余额上的某些锁。

7. 2 Physical Redo¶

即使某些操作使用 logical undo，redo 信息仍然物理记录，即记录每次写入的新值。

原因是恢复开始时，磁盘上的数据库状态可能不是 operation consistent，逻辑 redo 很复杂。

物理 redo 与 early lock release 不冲突。

7. 3 Operation Logging¶

操作开始时，写入 <Ti, Oj, operation-begin>，其中 Oj 是该操作实例的唯一标识。
操作执行期间，照常写入带有 physical redo 和 physical undo 信息的日志记录。
操作完成时，写入 <Ti, Oj, operation-end, U>，其中 U 包含执行 logical undo 所需的信息。

向索引 I9 插入 (K5, RID7)

插入步骤本身用 physical redo 记录；若要撤销完整插入操作，则用 delete I9, K5, RID7 作为 logical undo。

若 crash 或 rollback 发生在操作完成前：找不到 operation-end 记录，使用物理 undo 信息撤销该操作。
若 crash 或 rollback 发生在操作完成后：找得到 operation-end 记录，用 U 执行 logical undo，该操作内部的 physical undo 信息被忽略。

无论哪种情况，故障后的 redo 仍使用 physical redo 信息。

7. 4 Transaction Rollback with Logical Undo¶

回滚事务 $T_i$ 时，从日志末尾向后扫描：

若遇到普通更新记录 <Ti, X, V1, V2>：
- 执行物理 undo，把 X 写回 V1。
- 写出 <Ti, X, V1>。
若遇到 <Ti, Oj, operation-end, U>：
- 用 U 执行该操作的 logical rollback。
- rollback 期间产生的更新像正常操作一样写日志。
- 操作 rollback 结束时，不写 operation-end，而写 <Ti, Oj, operation-abort>。
- 跳过此前属于该操作的日志记录，直到 <Ti, Oj, operation-begin>。
若遇到 redo-only 记录，忽略。
若遇到 <Ti, Oj, operation-abort>：
- 跳过此前属于该操作的日志记录，直到 <Ti, Oj, operation-begin>。
遇到 <Ti start> 时停止扫描，并写出 <Ti abort>。

为什么要跳过 operation-abort 前的日志

operation-abort 说明该操作已经被逻辑撤销。若恢复或回滚时再次扫描到该操作内部日志并重复撤销，会造成重复 undo。

redo-only 记录和 operation-abort 情形通常只会在数据库正执行事务回滚时又发生 crash 的情况下出现。

Transaction rollback during normal operation

Failure Recovery with Logical Undo

完整操作与未完成操作同时存在

若 crash 发生在 <T1, O1, operation-abort> 之后，恢复时必须跳过 O1 内部日志，避免再次撤销 O1。

7. 5 Recovery Algorithm with Logical Undo¶

带 logical undo 的恢复算法与前面的算法基本相同，区别在于 undo 阶段按 logical rollback 规则处理操作日志。

Redo phase

从最后一个 <checkpoint L> 向前扫描到日志末尾。
通过 physical redo 重复所有事务的所有更新，即 repeat history。
扫描期间维护 undo-list：
- 初始为 L。
- 遇到 <Ti start>，把 $T_i$ 加入 undo-list。
- 遇到 <Ti commit> 或 <Ti abort>，把 $T_i$ 从 undo-list 删除。

redo phase 结束后，数据库回到 crash 时的状态，已提交、已中止和尚未完成事务的动作都被重放。此时 undo-list 中只剩未完成事务，即既没有 commit 也没有 abort 的事务。

Undo phase

从日志末尾向后扫描。
对 undo-list 中事务的日志记录，按前述 logical undo rollback 规则处理。
所有待撤销事务共享一次向后扫描。
对 undo-list 中某个事务 $T_i$，若扫描到 <Ti start>，写出 <Ti abort>。
当 undo-list 中所有事务的 <Ti start> 都被找到时停止。

该阶段撤销所有未完成事务的影响，恢复完成。

8 ARIES Recovery Algorithm¶

ARIES 全称 Algorithm for Recovery and Isolation Exploiting Semantics，是经典的工业级恢复算法。前面介绍的恢复算法可看作 ARIES 的简化版本。

ARIES 的主要优化包括：

使用 log sequence number, LSN 标识日志记录。
在页中保存 LSN，判断哪些更新已经反映到数据库页。
使用 physiological redo。
使用 dirty page table 避免不必要的 redo。
使用 fuzzy checkpointing，只记录脏页信息，不要求 checkpoint 时写出脏页。

8. 1 Physiological Redo¶

Physiological redo 物理标识受影响的页，但页内动作可以是逻辑的。

它可以降低日志开销。例如删除一条记录后，页内其他记录可能移动以填补空洞：

physical redo 可能要记录页面中大部分内容的旧值和新值。
physiological redo 只需记录“删除该记录”这一页内动作。

physiological redo 要求页输出到磁盘时具有原子性。硬件 RAID 或部分磁盘系统较容易支持这一点；若页输出不完整，可通过 checksum 检测，但需要额外恢复处理，通常视为 media failure。

8. 2 ARIES Data Structures¶

结构	含义
LSN	每条日志记录的递增编号，常用日志文件起始位置的偏移量表示，便于快速访问
PageLSN	数据页中保存的 LSN，表示该页已经反映到哪条日志记录
Log record	包含事务、前一日志记录、redo / undo 信息等
DirtyPageTable	记录缓冲区中被更新过、磁盘版本可能落后的页

LSN 必须单调递增，也可以扩展到多个日志文件。

8. 3 PageLSN¶

每个页包含一个 PageLSN，表示该页已经反映的最后一条日志记录的 LSN。

更新页时：

对页加 X-latch。
写日志记录。
更新该页。
将该日志记录的 LSN 写入 PageLSN。
释放页 latch。

将页刷新到磁盘前，需要先对页加 S-latch，保证磁盘上的页状态是 operation consistent。这是支持 physiological redo 的前提。

恢复时，PageLSN 用于避免重复 redo，从而保证 redo 的幂等性（idempotence）。

8. 4 Log Record and CLR¶

普通 ARIES 日志记录包含同一事务前一条日志记录的 LSN，即 PrevLSN。日志记录中的 LSN 本身可以是隐式的。

普通更新日志记录可抽象为：

ARIES 使用一种特殊的 redo-only 日志记录，称为 compensation log record, CLR，记录恢复过程中已经执行的 undo 动作。CLR 永远不需要再被 undo。

CLR 包含 UndoNextLSN，指向该事务下一条还需要 undo 的更早日志记录：

UndoNextLSN 的作用是跳过已经被撤销过的日志记录，避免重复 undo。

8. 5 DirtyPageTable¶

DirtyPageTable 记录缓冲区中已经被更新的页。对每个这样的页，记录：

页的 PageLSN。
RecLSN：一个 LSN，表示该 LSN 之前的日志记录已经应用到磁盘上的页版本。

当某页第一次进入 DirtyPageTable 时，RecLSN 设置为当前日志末尾，即该页即将被更新前的位置。DirtyPageTable 会写入 checkpoint，用来减少恢复时需要 redo 的工作量。

8. 6 Checkpoint Log¶

ARIES 的 checkpoint 日志记录包含：

DirtyPageTable。
活跃事务列表。
对每个活跃事务，记录 LastLSN，即该事务最后一条日志记录的 LSN。

磁盘固定位置保存最后一个完整 checkpoint 日志记录的 LSN。checkpoint 时不要求写出脏页；脏页可以在后台持续刷新。因此 ARIES checkpoint 开销很低，可以频繁执行。

8. 7 ARIES Three Passes¶

ARIES 恢复包含三趟：

阶段	作用
Analysis pass	确定哪些事务需要 undo，哪些页 crash 时是 dirty，redo 从哪个 LSN 开始
Redo pass	从 `RedoLSN` 开始 repeat history，重做还没有反映到磁盘页的动作
Undo pass	回滚所有未完成事务

Analysis 决定 redo 的起点；undo 可能需要回退到最早未完成事务的开始处。

8. 8 Analysis Pass¶

初始化
- 从最后一个完整 checkpoint 读取初始脏页表（DPT）和活跃事务列表（undo-list）
- 计算 RedoLSN = min(所有脏页的 RecLSN)，无脏页时 RedoLSN 等于 checkpoint 自身的 LSN
向日志末尾扫描
- 遇到新事务的日志：加入 undo-list，同步记录该事务的 lastLSN
- 遇到页面更新记录：
  - 页面已在 DPT 中：RecLSN 保持不变，PageLSN 更新为当前日志 LSN
  - 页面不在 DPT 中：新增该页，RecLSN = PageLSN = 当前日志 LSN
- 遇到事务结束（commit/abort）记录：将该事务从 undo-list 中移除
输出产物
- RedoLSN：Redo 阶段的起始扫描位置
- 最终脏页表：用于 Redo 阶段跳过无需重做的页面
- 最终 undo-list：所有需要回滚的失败事务

8. 9 Redo Pass¶

Redo pass 从 RedoLSN 向前扫描，重复历史。每遇到一条更新日志记录：

若该页不在 DirtyPageTable 中，跳过该日志记录。
若该日志记录的 LSN 小于该页在 DirtyPageTable 中的 RecLSN，跳过该日志记录。
否则从磁盘取该页。
若磁盘页的 PageLSN 小于该日志记录的 LSN，则 redo 该日志记录。
若 PageLSN >= LSN，说明该日志记录的效果已经在磁盘页中，跳过。

第 1、2 个测试可以避免无意义地从磁盘读取页面；第 4 个测试避免重复 redo。

8. 10 Undo Actions¶

当 ARIES 对一条更新日志记录执行 undo 时：

生成一个 CLR，记录本次 undo 动作。
CLR 的 redo 信息记录 undo 后的效果。
CLR 的 UndoNextLSN 设置为被 undo 的更新日志记录中的 PrevLSN。

CLR 在图示中常写作原记录编号加撇号，例如记录 4 的 CLR 写作 4'。箭头表示 UndoNextLSN。

ARIES 支持部分回滚（partial rollback），例如处理死锁时只回滚到足以释放所需锁的位置。部分回滚后可以继续向前执行，之后也可以再次部分回滚或最终完全回滚。

8. 11 Undo Pass¶

初始化：以 Analysis Pass 得到的每个待撤销事务的最后一条日志 LSN 作为该事务的初始待撤销 LSN。
倒序跳转处理：每一步选择所有待撤销 LSN 中最大的一个，直接跳转至该记录执行撤销，跳过中间无需重复处理的日志。
指针更新规则：
- 普通更新日志：撤销完成后，该事务下一条待撤销 LSN = 当前记录的 PrevLSN
- CLR 补偿日志：下一条待撤销 LSN = 当前 CLR 的 UndoNextLSN
日志落盘：每执行一次撤销动作，就写入一条对应的 CLR，事务全部操作撤销完毕后，写入事务 Abort 记录。

Recovery Actions in ARIES

Other ARIES Features

Recovery independence：页可以独立恢复。例如部分磁盘页损坏时，可以从备份恢复这些页，同时其他页仍可使用。
Savepoints：事务可以记录 savepoint，并回滚到某个 savepoint。复杂事务和死锁处理都可能使用 savepoint，只回滚到足以释放锁的位置。
Fine-grained locking：允许索引并发算法使用 tuple-level locking，这需要 logical undo，而不是简单 physical undo。
Redo prefetch：DirtyPageTable 可用于 redo 期间预取页面。
Out-of-order redo：某页正在从磁盘读取时，可以推迟该页上的 redo，继续处理其他日志记录；页面读入后再执行对应 redo。

9 Remote Backup Systems¶

远程备份系统（remote backup systems）通过在 primary site 被破坏后仍允许事务处理继续进行，提供高可用性。

9. 1 Failure Detection and Transfer of Control¶

备份站点必须检测 primary site 是否失败。为区分 primary failure 与通信链路 failure，系统通常在 primary 和 remote backup 之间维护多条通信链路，并发送 heart-beat messages。

控制权转移过程：

backup site 确认 primary site 失败。
backup 使用自己的数据库副本和已经从 primary 接收到的日志记录执行恢复。
已完成事务 redo，未完成事务 rollback。
backup 接管处理并成为新的 primary。
若旧 primary 恢复并要重新接管，必须先从旧 backup 接收 redo logs，并在本地应用所有更新。

9. 2 Time to Recover and Hot Spare¶

为了减少接管延迟，backup site 可以周期性处理收到的 redo log records，相当于不断从之前的数据库状态做恢复；之后执行 checkpoint，并删除更早日志。

Hot-spare configuration 可以实现很快接管：

backup 持续处理收到的 redo log records，并在本地应用更新。
检测到 primary failure 后，backup 只需回滚未完成事务，就可以开始处理新事务。

远程备份的替代方案是使用带复制数据的分布式数据库。远程备份通常更快、更便宜，但对某些故障的容忍度较低。

9. 3 Commit Durability Levels¶

为了保证更新持久性，可以延迟事务提交，直到更新也记录到 backup。若希望减少提交延迟，可以接受较低级别的持久性。

策略	提交条件	优点	风险或代价
One-safe	commit log record 写到 primary 后即可提交	提交延迟低	更新可能尚未到达 backup，backup 接管后可能丢失已提交事务
Two-very-safe	commit log record 写到 primary 和 backup 后才提交	避免 one-safe 的丢失事务问题	可用性下降，任一站点失败都可能导致事务不能提交
Two-safe	primary 和 backup 都 active 时按 two-very-safe；若只有 primary active，则写到 primary 后提交	比 two-very-safe 可用性更好，同时避免 one-safe 在 backup active 时的丢失事务问题	backup 不可用期间退化为 primary-only 提交

操作	含义
`read(X)`	把系统缓冲区中数据项 `X` 的值赋给本地变量 \(x_i\)
`write(X)`	把本地变量 \(x_i\) 的值写入缓冲块中的数据项 `X`

日志记录	含义
`<Ti start>`	事务 \(T_i\) 开始
`<Ti, X, V1, V2>`	\(T_i\) 将 `X` 从旧值 `V1` 更新为新值 `V2`
`<Ti commit>`	\(T_i\) 完成最后一条语句并提交
`<Ti abort>`	\(T_i\) 已完成回滚

方式	含义
Immediate database modification	\(·\) 允许未提交事务的更新在提交前写入缓冲区或磁盘 \(·\) 更新块可以在事务提交前或提交后输出到磁盘，输出顺序也可以不同于事务写入顺序 \(·\) 更新日志记录必须先于对应数据库数据项写出 \(·\) 数据页输出到磁盘前，与该页相关的日志记录必须先输出到稳定存储
Deferred database modification	\(·\) 到事务提交时才把更新写入缓冲区或磁盘 \(·\) 简化了部分恢复逻辑，但需要保存本地副本，开销更大

情形	恢复动作
\(T_0\) 未提交	`undo(T0)`，把 `B` 恢复为 `2000`、`A` 恢复为 `1000`，并写出 `<T0, B, 2000>`、`<T0, A, 1000>`、`<T0 abort>`
\(T_0\) 已提交，\(T_1\) 未提交	`redo(T0)` 并 `undo(T1)`，把 `A`、`B` 设为 `950`、`2050`，把 `C` 恢复为 `700`，并写出 `<T1, C, 700>`、`<T1 abort>`
\(T_0\) 与 \(T_1\) 都已提交	`redo(T0)` 并 `redo(T1)`，把 `A`、`B`、`C` 分别设为 `950`、`2050`、`600`