一、故障的分类 Failure Classification

1. 事务故障 Transaction Failure
   • Logical Errors：事务内部逻辑错误导致的事务故障，例如输入格式不正确、数据溢出等
   • System Errors：由于错误情况（如检测到死锁），数据库系统必须中止事务的执行
2. 系统崩溃 System Crash
   • 电源、硬件、软件等故障导致的系统崩溃
   • 假设非易失性存储不会因为系统崩溃而被破坏
3. 磁盘故障 Disk Failure
   • 磁盘出现故障，导致磁盘的部分或全部数据被破坏

二、基于日志的恢复 Log-Based Recovery

1. 日志 Log

• 日志由一系列日志记录（Log Record）组成
• 事务 $T_i$ 开始时，写入日志记录 <T_i Start>
• 事务 $T_i$ 执行 write(X) 操作时，写入日志记录 <T_i, X, V1, V2>，其中 X 表示写入的对象， V1 表示写入对象的旧值， V2 表示写入对象的新值
• 事务 $T_i$ 结束时，写入日志记录 <T_i Commit>

示例：

<T1 start>
<T1, A, 100, 200>
<T2 start>
<T2, B, 300, 400>
<T3 start>
<T1, C, 500, 600>
<T1 commit>
<T3, C, 600, 700>
<T3, C, 700, 800>
<T3 commit>
<T2, C, 800, 900>
<T2, B, 400, 500>

2. 延迟修改技术 Deferred Database Modification

• 假设事务是序列执行的

• 事务执行 write(X) 操作时，实时写入日志记录，但不立即更新数据库存储的实际值，而是将更新进行延迟（Defer），直到发生故障

• 当发生故障时，对于已结束并提交的事务，将该事务的更新应用到数据库（ redo(T_i) ）；对于发生故障的事务，不进行任何操作，因为这些事务并未应用到数据库

  示例：

  

3. 立即修改技术 Immediate Database Modification

1. 延迟修改技术仅在事务结束并提交后才能对数据库进行更新，而立即修改技术允许未结束的事务对数据库进行更新

   示例：

   • Output 表示向 Disk 输出的更新的块
   • 块的输出既可以在涉及的事务提交前进行，也可以在事务提交后进行
   • 块的输出和它们的更新顺序可能不同

   

2. 发生故障的恢复操作

   定义两种运算：

   • undo(T_i) ：将事务 $T_i$ 进行的所有更新进行回退（从 $T_i$ 的最后一条日志记录开始，倒序进行回退）
   • redo(T_i) ：将事务 $T_i$ 进行的所有更新进行应用（从 $T_i$ 的第一条日志记录开始，顺序进行更新）

   示例：

   

3. 检查点 Checkpoint

   • 若仅依赖重做/撤销日志（Redo/Undo Log）恢复，系统崩溃后需处理整个日志，导致时间成本高；通过设置检查点，定期保存和更新数据库状态，将恢复范围限制在最近一个检查点之后，从而大幅减少恢复时需处理的日志量
   • 检查点的执行流程
     • 将所有未写入磁盘的日志记录强制写入磁盘，无论对应的事务是否执行完成
     • 向日志写入一条检查点记录 <checkpoint L>，其中 L 为检查点时正在执行的事务列表
     • 检查点执行期间，暂停所有数据更新
   • 由检查点进行恢复
     • 定位检查点：从日志末尾反向扫描，找到最近的<checkpoint L>记录。
     • 确定恢复范围：仅对检查点 L 后的日志对应的事务进行 Redo 或 Undo 操作

   示例：