14. 恢复系统

1. Motivation (动机)

目的：计算机系统经常发生故障，数据库必须具备恢复机制，以保证事务的 Atomicity (原子性) 和 Durability (持久性)。
故障分类 (Failure Classification)：
1. 事务故障：逻辑错误（代码 Bug）或系统错误（如死锁被强制中断）。
2. 系统崩溃 (System Crash)：掉电、操作系统蓝屏。
  - 假设：遵循 Fail-stop Assumption（内存数据丢失，但磁盘数据未受损）。
3. 磁盘故障：物理损坏（磁头坏了），通常需 RAID 解决。
存储类型：
- Volatile (易失性)：内存 (Buffer)。崩溃即失。
- Nonvolatile (非易失性)：磁盘 (Disk)。崩溃后幸存。
- Stable Storage (稳定存储)：理论概念，通过冗余备份（RAID/镜像）模拟“永不丢失”。

2. Concept (核心概念)

2.1 数据访问 (Data Access)

区分物理传输和逻辑传输是理解恢复算法的前提。

Input(B) / Output(B)：负责 磁盘块内存 Buffer 之间的物理传输。
Read(X) / Write(X)：负责 事务工作区内存 Buffer 之间的逻辑传输。
★ 关键风险：Write(X) 仅仅是修改了内存中的 Buffer。如果此时系统崩溃，Buffer 还没来得及 Output 到磁盘，数据就会丢失。

2.2 基于日志的恢复 (Log-Based Recovery)

日志是记录数据库更新操作的序列，必须存放在 Stable Storage 上。

记录格式：<Ti, X, V1, V2>
- ：旧值 (Old Value) 用于 Undo。
- ：新值 (New Value) 用于 Redo。
★ WAL 协议 (Write-Ahead Logging)：
- 规则：在内存中的数据块被写回磁盘 (Output) 之前，该操作对应的日志记录必须先写到稳定存储中。
- 口诀：“日志先行，数据后行”。

2.3 检查点 (Checkpoints)

痛点：如果不做检查点，恢复时必须从头扫描整个日志，慢得无法接受。
操作：
1. 将内存中所有日志记录写入磁盘。
2. 将内存中所有 脏数据块 (Dirty Blocks) 强制写入磁盘。
3. 写入一条 <checkpoint L> 记录（L 是当前活跃事务列表）。
作用：恢复时仅需从最近的检查点开始向后扫描，不用管太久之前的日志。

3. Method: 恢复算法 (Recovery Algorithm)

恢复过程严格分为两个阶段：先 Redo (重做)，后 Undo (撤销)。

Phase 1: Redo Phase (重做阶段 - 从前往后)

目标：重建系统崩溃那一刻的内存状态，并确定哪些事务是“活”着的。

起点：找到日志中最近的一个 <checkpoint L>。
初始化：undo-list = L。
扫描过程 (Forward Scan)：
- 遇到更新记录 <Ti, X, V1, V2> 执行 Redo (写入 )。(重新执行一遍就是)
- 遇到 <Ti start> 将加入 undo-list。
- 遇到 <Ti commit> 或 <Ti abort> 将 从 undo-list 中移除（说明该事务已结束，不需要撤销）。
结果：扫描结束时，undo-list 中剩下的就是崩溃时还未完成的事务。

Phase 2: Undo Phase (撤销阶段 - 从后往前)

目标：回滚那些未完成的事务（即 undo-list 中的家伙）。

起点：日志末尾。
扫描过程 (Backward Scan)：
- 仅关注 undo-list 中的事务。
- 遇到更新记录 <Ti, X, V1, V2> 执行 Undo (写入 )，并写入 CLR (补偿日志记录)。
- 遇到 <Ti start> 写入 <Ti abort>，并将 从 undo-list 移除。
终点：当 undo-list 为空时，恢复结束。

4. Example (习题实战详解)

4.1 基础题 (Slide 42 模型)

日志：<T0...>, <T1...>, <T2...>, <checkpoint {T1, T2}>, <T3...>, Crash。

Redo 阶段：
- 从 Checkpoint 开始。初始 undo-list = {T1, T2}。
- 遇到 <T3 start>，undo-list 变为 {T1, T2, T3}。
- 假设 T3 后来 Commit 了，undo-list 变回 {T1, T2}。
Undo 阶段：
- 只撤销 T1 和 T2。

4.2 ★ 进阶压轴题 (Slide 43 实例详解)

场景：包含两次 Checkpoint，且有事务在崩溃前 Abort。

(1) 日志时间线重构 (Log Sequence)

<T1 start>, <T1, A...>
<T2 start>, <T2, B...>
<T3 start>
<T2, B...>
<checkpoint {T1, T2, T3}> (Checkpoint 1)
<T1 commit>
<T3, C...>
<T3, C...>
<checkpoint {T2, T3}> (Checkpoint 2) —— 恢复起点
<T4 start>
<T3 abort>
=== CRASH (系统崩溃) ===

(2) 恢复推演步骤

Step 1: Redo Phase (从 Checkpoint 2 往后扫)

起点：行号 9 <checkpoint {T2, T3}>。
初始化：undo-list = {T2, T3}。
扫描过程：
- 读到 <T4 start> (行 10)：新事务来了。undo-list = {T2, T3, T4}。
- 读到 <T3 abort> (行 11)：关键点！ T3 已经自我了断了。既然日志里有 abort，说明不用我们在 Undo 阶段去回滚它。
- 动作：将 T3 从列表移除。undo-list = {T2, T4}。
- (注：在此期间所有数据的 Update 操作，无论属于谁，都要 Redo 一遍以恢复内存状态)。
Redo 结束状态：undo-list = {T2, T4}。

Step 2: Undo Phase (从 Crash 处一直往前扫)

目标：只撤销 T2 和 T4。
扫描过程 (Backward)：
- 处理 T4：
  - 遇到 <T4 start> (行 10)。
  - T4 没有写操作，直接写入 <T4 abort>。
  - 移除 T4。undo-list = {T2}。
- 处理 T2 (需穿越 Checkpoint 2 继续回溯)：
  - 遇到 <T2, B...> (行 4)：执行 Undo，写 CLR。
  - 遇到 <T2, B...> (行 2)：执行 Undo，写 CLR。
  - 遇到 <T2 start>：写入 <T2 abort>。
  - 移除 T2。undo-list = {}。
结束：列表为空，恢复完成。

5. Summary (关键考点总结)

T1 为什么不管？
- T1 在 Checkpoint 2 之前已经 <T1 commit>。Redo 从 Checkpoint 2 开始，根本看不到 T1 的 commit 记录，也不需要管（因为 Checkpoint 保证了 T1 的数据当时已经落盘）。
T3 为什么不用 Undo？
- Redo 阶段看到了 <T3 abort>。既然它生前已经 Abort，系统状态已经回滚过了，Undo 阶段就把它放过。
Undo 会扫描多远？
- 虽然 Redo 从最近的 Checkpoint 开始，但 Undo 必须回溯到事务的 Start。比如 T2，Undo 一直追溯到了 Checkpoint 1 之前。

口诀：

Redo 从检查点起，见 Start 加名单，见 End 删名单。

Undo 从屁股往回，只杀名单里的，杀到 Start 为止。