CS186 笔记05

在数据库事务的 ACID 四大特性中，原子性 (Atomicity) 和 持久性 (Durability) 是由强大的恢复系统来保证的。想象一下数据库操作的“撤销”和“重做”能力，这就是原子性和持久性的核心体现。

• 原子性 (Atomicity): 事务要么全部完成，要么全部不发生。

  • 定义： 事务是一个不可分割的工作单元。它内部的所有操作必须作为一个单一的、不可中断的整体来执行。这意味着事务中的所有步骤要么全部成功提交到数据库，要么全部不留痕迹地被撤销，就好像这个事务从未执行过一样。
  • 为什么需要？ 试想一个银行转账的例子：从账户 A 扣款 100 元，然后给账户 B 增加 100 元。
    • 如果系统在“账户 A 扣款”成功后，但在“账户 B 增加”之前突然崩溃了，没有原子性，账户 A 少了钱，账户 B 却没收到，导致数据不一致（总金额变少了）。
    • 原子性确保了这种“半完成”的状态不会存在。如果事务未能完整执行，系统会确保它被完全撤销 (Undo)，账户 A 的钱会退回，就像转账从未发生一样，保证了数据的一致性。
  • 事务中止 (Abort) 的常见原因：
    • 用户或应用程序显式中止： 比如用户点击了“取消”按钮。
    • 违反数据一致性或完整性约束： 例如，试图插入一个重复的主键值，或违反外键约束。
    • 死锁 (Deadlock)： 两个或多个事务互相等待对方释放资源，系统检测到死锁后会选择一个事务作为“牺牲者”并中止它。
    • 系统崩溃： 在事务成功提交之前，数据库服务器或操作系统发生故障，导致事务未能完成。

• 持久性 (Durability): 提交的事务，其修改永久有效。

  • 定义： 一旦一个事务被数据库系统成功地标记为“提交 (Committed)”，那么它对数据库所做的所有修改都必须是永久性的。即使在提交之后，系统发生断电、软件崩溃或任何其他故障，这些修改也绝不能丢失。
  • 为什么需要？ 继续以上面支付的例子：如果用户已经收到了“支付成功”的确认消息，那么这笔交易的数据（例如订单状态、库存数量）必须被永久记录下来。
    • 如果没有持久性，系统提交事务后立即崩溃，而该事务所做的修改还在内存中没有写入磁盘，那么重启后这些修改就丢失了。
    • 持久性保证了即使发生故障，系统也能恢复到提交事务后的状态，确保了对用户的承诺不会落空。

挑战：简单的恢复方案为何行不通

为了实现原子性和持久性，我们需要一个精巧的系统设计。让我们先分析一个看似简单，但实际存在致命缺陷的方案，从而理解数据库恢复面临的真正挑战。

一个天真的方案：

1. 锁定与缓存 (Locking & Caching)： 当一个事务要修改数据库中的一个页面 (Page) 时，它会：

   • 首先锁定该页面，防止其他事务同时修改。
   • 将该页面从磁盘加载到内存的缓冲池 (Buffer Pool) 中。
   • 在内存中对页面进行修改，此时这个页面被称为“脏页” (Dirty Page)，因为它在内存中的版本与磁盘上的版本不一致。
   • 事务会“固定” (Pin) 住这个脏页，意思是阻止缓冲池管理器将这个脏页在事务提交前写回磁盘（因为它包含了未提交的数据）。

2. 提交 (Commit)： 当事务决定提交时：

   • 它会将自己修改过的所有“脏页”全部“强制” (Force) 写回磁盘。
   • 只有当所有这些脏页都成功写入磁盘后，事务才被正式宣布提交成功，并释放锁和固定。

3. 中止 (Abort)： 当事务决定中止时：

   • 由于所有的脏页都还被固定在内存中，未被写回磁盘，事务只需简单地在内存中丢弃这些修改。
   • 这些脏页会被标记为“干净”，并可以被缓冲池管理器自由替换，无需任何磁盘操作。

这个方案的致命缺陷：

1. 无法保证原子性： “提交时将所有脏页写回磁盘”这个步骤本身就不是一个原子操作！

   • 问题： 如果一个事务修改了多个页面 (P1, P2, P3)，并在提交时尝试将它们全部写回磁盘。假设 P1 成功写入，P2 正在写入时系统崩溃了，而 P3 还没来得及写入。
   • 后果： 重启后，P1 的修改已经生效，P2 和 P3 的修改可能部分生效或未生效。数据库就会处于一个不一致的“半完成”状态，违反了原子性。我们无法轻松地“撤销” P1 的修改，也无法“重做” P2 和 P3 的修改。

2. 性能与伸缩性极差：

   • 问题： 它要求所有未提交事务的脏页都必须保留在内存的缓冲池中。
   • 后果：
     • 缓冲池迅速耗尽： 如果一个“长事务”修改了大量数据（例如一个批处理事务处理了几百万条记录），或者在高峰期有大量的并发事务同时运行，缓冲池会迅速被未提交的脏页占满。
     • 系统停滞： 一旦缓冲池满了，新的数据页就无法加载进来，所有需要新页面的操作都会被阻塞，导致整个数据库系统几乎无法进行任何工作，完全没有伸缩性。
     • 提交延迟高： 事务提交时需要等待所有修改的页面都写入磁盘，这涉及大量的随机磁盘 I/O，提交时间会非常长，严重影响用户体验。

缓冲管理器策略：STEAL 与 FORCE

从上述失败方案中，我们引出两个核心的缓冲管理策略。它们的组合方式直接决定了数据库恢复系统的复杂度和性能。

• STEAL vs. NO-STEAL (关于未提交数据是否能被写回磁盘)

  • NO-STEAL (不偷): 不允许将一个未提交事务修改的脏页写回磁盘。这是我们之前天真方案采用的策略。

    • 优点: 实现原子性非常简单。因为未提交的数据绝不会出现在磁盘上，所以当一个事务中止 (Abort) 时，我们只需在内存中丢弃这些修改即可，无需在磁盘上执行任何 Undo 操作。磁盘永远是“干净”的。
    • 缺点: 性能和伸缩性差。缓冲池必须足够大，以容纳所有活跃事务所修改的脏页。一旦缓冲池满了，就无法加载新的页面，导致系统停滞。

  • STEAL (偷): 允许将未提交事务修改的脏页写回磁盘。

    • 优点: 缓冲池可以更自由、更高效地管理页面。当内存不足时，即使某个脏页包含未提交事务的修改，缓冲池管理器也可以选择将其写回磁盘（“偷走”该页的内存空间），从而释放内存供其他操作使用。这极大地提高了数据库的性能和伸缩性。
    • 缺点: 实现原子性变得复杂。如果一个包含未提交数据的脏页已经被“偷”到磁盘上（即写回了磁盘），但该事务最终却中止了。此时，磁盘上的数据就是错误的，我们必须有办法在磁盘上撤销 (Undo) 这些已经生效的修改。这就要求我们记录足够的Undo 日志信息。

• FORCE vs. NO-FORCE (关于已提交数据是否必须立即写回磁盘)

  • FORCE (强制): 在事务提交时，强制要求其修改的所有脏页都必须被写回磁盘。这也是天真方案采用的策略。

    • 优点: 实现持久性非常简单。一旦事务被通知为“已提交”，其所有修改都已安全地落盘，不会因崩溃而丢失。
    • 缺点: 性能极差。事务提交需要等待多次（可能是随机的）磁盘 I/O 完成。对于用户来说，这意味着提交操作的响应时间很长，严重影响并发性能。

  • NO-FORCE (不强制): 事务提交时，不要求其修改的脏页必须立即写回磁盘。

    • 优点: 事务提交非常快，只需完成必要的内存操作和日志操作即可立即响应用户。真正的磁盘 I/O（将脏页写回磁盘）可以在后台批量、异步地进行，这极大地提高了事务的吞吐量和并发性。
    • 缺点: 实现持久性变得复杂。如果一个事务已经成功提交，但它的脏页还仅仅在内存中，此时系统崩溃，这些已提交的修改就会丢失。这就要求我们记录足够的Redo 日志信息，以便在恢复时重做这些丢失的修改。

策略组合	原子性实现	持久性实现	性能
NO-STEAL/FORCE	简单	简单	最差
STEAL/NO-FORCE	复杂 (Undo)	复杂 (Redo)	最好

现代高性能数据库，例如 PostgreSQL、Oracle 等，几乎无一例外地采用 STEAL/NO-FORCE 策略。这种策略以最佳的性能和伸缩性为代价，换来了恢复系统的复杂性。而 ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) 正是一套完整、严谨、工业级的算法，专门用于在 STEAL/NO-FORCE 环境下实现可靠的崩溃恢复。

核心思想：预写日志 (Write-Ahead Logging, WAL)

WAL 是实现 STEAL/NO-FORCE 策略的基石，它的思想简单而强大，是数据库领域最重要的概念之一。

是什么 (What it is): 永远先写日志，再修改数据。预写日志 (WAL) 是一种协议或规则，它规定：在对数据库中的任何数据进行实际修改之前，必须先将描述该修改的日志记录 (Log Record) 安全地写入到稳定存储（通常是磁盘上的日志文件）中。

怎么做 (How it works): WAL 的两个黄金法则

WAL 协议由两个核心规则构成，它们分别保障了原子性和持久性：

1. Undo 法则 (保证原子性):

   • 规则： 在一个数据页 (Data Page) 被写回磁盘之前，与该页面上未提交事务的更新相对应的日志记录（特别是包含“旧值”的记录）必须先被强制刷盘到稳定存储。
   • 通俗解释： 如果我们允许把未提交的数据写到磁盘（STEAL策略），那么一旦这些数据被写出去了，我们将来又需要撤销它（因为事务中止了），我们必须确保在撤销之前，有记录可以告诉我们这个数据“修改前是什么样子”。这个“修改前是什么样子”的信息就记录在日志里。所以，日志必须比数据页更早地写入磁盘。
   • 举例： 事务 T1 修改了 Page A，还没有提交。由于缓冲池空间紧张，Page A 的脏数据被写回了磁盘 (STEAL)。为了能撤销 T1 对 Page A 的修改（如果 T1 最终中止），描述 T1 对 Page A 修改的日志记录（包含 Page A 的旧值）必须在此之前已经安全地写入了磁盘。

2. Redo 法则 (保证持久性):

   • 规则： 在一个事务被通知为“已提交”之前，与该事务相关的所有日志记录（特别是包含“新值”的记录）必须先被强制刷盘到稳定存储。
   • 通俗解释： 我们允许事务提交后，其修改的数据页可以不立即写回磁盘 (NO-FORCE)。这意味着当系统崩溃时，一些已经提交的事务的修改可能还只停留在内存中，尚未写入磁盘。为了保证这些已提交的修改不会丢失（持久性），我们必须确保这些修改的“操作记录”（日志）已经安全地落盘。这样，即使数据页丢失，我们也可以通过日志“重做”这些修改。
   • 举例： 事务 T2 修改了 Page B，并成功提交。虽然 Page B 的修改还在内存中没有写回磁盘 (NO-FORCE)，但是描述 T2 对 Page B 修改的日志记录已经安全地写入了磁盘。即使系统现在崩溃，重启后我们也能根据日志中的信息，把 T2 对 Page B 的修改重新应用到 Page B 上，保证持久性。

日志 (Log) 的物理特性: 日志文件通常是一个仅追加 (Append-only) 的文件。所有对日志的写入操作都是顺序 I/O。顺序 I/O 的速度比随机 I/O 快得多，因为磁头不需要频繁移动。ARIES 正是巧妙地利用这一点，将昂贵的随机写盘操作（修改数据页）转化为廉价的顺序写日志操作，从而获得巨大的性能提升。

ARIES 的关键数据结构

为了实现 WAL 协议和高效的恢复过程，ARIES 维护了几个核心的数据结构。

1. 日志记录 (Log Record)

日志文件 (Log File) 是一个由一系列有序的日志记录 (Log Records) 构成的序列。每一条日志记录都有一个唯一且单调递增的日志序列号 (Log Sequence Number, LSN)。LSN 是日志中的“地址”，也是 ARIES 各种操作的关键引用点。

通用日志记录字段:

• LSN: 本条日志记录的唯一标识符。它是一个不断增长的数字，代表了日志中的一个位置。它不仅是记录的 ID，更是“时间”的度量，LSN越大代表时间越晚。
• prevLSN: 指向同一个事务 (XID) 的上一条日志记录的 LSN。这个字段将属于同一个事务的所有日志记录串成一个以时间倒序的链表。这对于快速回滚一个事务（即从最新操作追溯到最早操作）至关重要。
• XID: 产生该日志记录的事务 ID。
• Type: 日志记录的类型（如 Update, Commit, Abort, CLR, Checkpoint 等）。

常见的日志记录类型详解:

• Update (更新记录):

  • 这是最常见的日志记录类型，每当一个事务修改了数据库中的数据时，就会写入一条 Update 记录。
  • 额外字段：
    • PageID: 被修改的数据页的唯一标识符。
    • Offset: 在 PageID 指定的页面内，具体修改发生的位置（字节偏移量）。
    • before-image: 修改发生前，受影响数据的旧值。这是进行 Undo 操作的必需信息。
    • after-image: 修改发生后，受影响数据的新值。这是进行 Redo 操作的必需信息。
  • 示例： 事务 T1 将 Page 10 的 Offset 20 处的值从 'A' 改为 'B'。
    • LSN: 100, prevLSN: 50 (T1的上一条记录), XID: T1, Type: Update, PageID: 10, Offset: 20, before-image: 'A', after-image: 'B'

• Commit / Abort (提交/中止记录):

  • 标记一个事务的最终状态。当事务决定提交或中止时写入。
  • 示例： LSN: 200, prevLSN: 180, XID: T1, Type: Commit

• CLR (Compensation Log Record, 补偿日志记录):

  • 这是 ARIES 最精妙的设计之一。当对一个 Update 操作执行 Undo 时（例如事务回滚或崩溃恢复的 Undo 阶段），ARIES 并不会简单地修改页面，而是会额外写入一条 CLR。
  • 本质： CLR 本身也是一种特殊的“更新”日志，它记录了“我刚刚执行了一个撤销操作”。它包含了执行撤销操作所需的 PageID、Offset 和新的值（也就是原 Update 记录的 before-image）。
  • 核心特性：CLR 永不被 Undo！ 这是防止在恢复期间（特别是 Undo 阶段发生二次崩溃时）对同一个操作进行重复、错误的撤销的关键。因为 CLR 记录的是一个“已经完成的撤销动作”，如果再次撤销它，就意味着你又把数据改回了原来的错误值。
  • 额外字段：
    • undoNextLSN: 指向下一个需要被撤销的日志记录的 LSN。这个 LSN 通常是原 Update 记录的 prevLSN。它指示了回滚链条的下一个目标。
  • 示例： 事务 T1 正在回滚。它遇到了 LSN 100 的 Update 记录（将 'A' 改为 'B'）。
    • LSN: 210, prevLSN: 200 (T1的上一条日志，可能是一个CLR), XID: T1, Type: CLR, PageID: 10, Offset: 20, after-image: 'A', undoNextLSN: 50 (即 LSN 100 的 prevLSN)
    • CLR 写入后，才在内存中真正把 Page 10 的值从 'B' 改回 'A'。

• Checkpoint (检查点记录):

  • 用于限制崩溃恢复时需要扫描的日志量。它记录了系统在某一时刻的活跃事务和脏页信息。

• End (结束记录):

  • 标记一个事务的生命周期（无论是提交还是中止）已完全结束，所有相关的清理工作（如释放锁，移除事务表项）都已完成。

2. 内存中的辅助表

ARIES 在内存中维护两个核心的动态表，用于在正常运行时和崩溃恢复时跟踪系统状态：

• 事务表 (Transaction Table):

  • 作用： 记录当前所有活跃事务的状态和最近的日志信息。

  • 内容： 每个活跃事务占一行，包含以下字段：

    • XID: 事务的唯一 ID。
    • Status: 事务的当前状态，常见的有 running (正在执行), committing (正在提交), aborting (正在中止)。
    • lastLSN: 该事务最近写入的日志记录的 LSN。这个字段是回溯事务日志链的关键入口。

  • 示例：

    XID	Status	lastLSN
    T1	running	150
    T2	committing	280

• 脏页表 (Dirty Page Table, DPT):

  • 作用： 记录缓冲池中所有当前是脏的 (dirty) 的数据页的信息。这些页面在内存中的版本比磁盘上的版本新。

  • 内容： 每个脏页占一行，包含以下字段：

    • PageID: 脏页的唯一 ID。
    • recLSN (Recovery LSN): 这是理解 ARIES 的一个非常关键的概念。它表示第一次导致该页面变“脏”的 Update 日志记录的 LSN。
      • 深刻含义： recLSN 标志着一个页面需要被 Redo 的“最早起点”。这意味着在 recLSN 之前的任何对该页的修改，都必然已经在崩溃前被安全地写入了磁盘。我们恢复时，只需要从 DPT 中最小的 recLSN 开始 Redo，无需扫描整个日志文件。

  • 示例：

    PageID	recLSN
    P10	120
    P25	180

    • 这表示 Page 10 在 LSN 120 处首次变脏，Page 25 在 LSN 180 处首次变脏。

3. 数据页上的 pageLSN

数据库中的每个数据页的头部，都会存储一个特殊的 pageLSN。

• pageLSN (Page Log Sequence Number): 记录了对该页面进行最近一次成功更新的日志记录的 LSN。
• WAL 的具体实现： WAL 的 Undo 法则可以更精确地描述为：在将页面 P 从内存缓冲池写入磁盘之前，必须确保 P.pageLSN (即该页上最新修改对应的日志 LSN) 所在的日志记录已经安全地刷入磁盘。换句话说，如果 P.pageLSN 是 LSN=100，那么在将 Page P 写盘之前，日志中 LSN 100 及之前的记录都必须已经落盘。

ARIES 的三大核心流程

ARIES 算法巧妙地将恢复过程分为三个阶段，并通过 WAL 和上述数据结构协同工作，实现了鲁棒性。

1. 正常执行流程

这是数据库系统在日常运行时事务如何与日志系统交互。

• 更新操作 (例如：UPDATE account SET balance = balance - 100 WHERE id = 'A')

  1. 加载并修改页面： 事务 T 要修改数据页 P（例如，Page 10）。首先，将 Page 10 加载到内存缓冲池，并对其中的数据进行修改。
  2. 生成日志记录： 构造一条 Update 日志记录。这条记录会包含：
     • 事务 T 的 XID。
     • 被修改的页面 P 的 PageID (Page 10)。
     • 修改的 Offset。
     • 修改前的旧值 (before-image)。
     • 修改后的新值 (after-image)。
  3. 更新事务表： 将事务 T 在内存中的事务表 (Transaction Table) 中对应的 lastLSN 更新为这条新生成的 Update 日志记录的 LSN。例如，如果新日志的 LSN 是 150，那么 T 的 lastLSN 就变成了 150。
  4. 更新页面 pageLSN： 将内存中 Page 10 的 pageLSN 更新为这条新 Update 日志记录的 LSN (即 150)。
  5. 更新脏页表 (DPT)： 如果 Page 10 之前不是脏页，现在它被修改了，所以它变成了脏页。将其加入到内存中的脏页表 (DPT) 中，并设置其 recLSN 为这条新 Update 日志记录的 LSN (即 150)。如果 Page 10 已经是在 DPT 中的脏页，那么只需更新其 pageLSN，recLSN 保持不变（因为 recLSN 记录的是“第一次”变脏的 LSN）。

• 事务提交 (Commit)

  1. 写入 Commit 记录： 事务 T 决定提交。首先，写入一条 Commit 日志记录到日志缓冲区。
  2. 强制刷盘 (Force Log)： 这是实现持久性的关键一步。系统会强制 (Force) 将该事务产生的所有日志记录（包括之前的 Update 记录，直到当前的 Commit 记录）从日志缓冲区刷写到磁盘上的日志文件。这严格遵循了 WAL 的 Redo 法则：在告诉用户事务已提交之前，所有相关日志必须落盘。
  3. 返回成功： 一旦所有相关日志刷盘成功，系统就可以安全地向用户返回“提交成功”。
  4. 写入 End 记录并清理： 最后，写入一条 End 日志记录，表示该事务的生命周期完全结束。然后，将该事务从内存中的事务表 (Transaction Table) 中移除。

• 事务中止 (Abort) - 显式回滚 (Rollback)

  • 这通常发生在应用程序显式调用回滚，或事务遇到错误时。
  1. 写入 Abort 记录： 写入一条 Abort 日志记录到日志缓冲区。
  2. 逆向回滚 (Backward Pass)： 系统通过事务表找到该事务的 lastLSN。然后，从 lastLSN 开始，沿着日志记录的 prevLSN 链表逆向回溯（从最新操作回溯到最早操作）。
  3. 处理每条日志记录：
     • 遇到 Update 记录：
       • 写入 CLR： 首先，构造并写入一条对应的 CLR (补偿日志记录) 到日志缓冲区。CLR 中会记录执行 Undo 操作所需的 PageID、Offset 和新的值（这个新值就是原 Update 记录的 before-image）。最重要的，CLR 的 undoNextLSN 字段会指向当前 Update 记录的 prevLSN。
       • 执行 Undo： 在内存中真正执行页面 P 的 Undo 修改，即根据 CLR 的信息将 PageID 的数据恢复到 before-image。同时，更新 Page P 的 pageLSN 为这条 CLR 的 LSN。
       • 继续回溯： 将 CLR 中记录的 undoNextLSN（也就是原 Update 记录的 prevLSN）加入到待处理的 LSN 集合中，继续回溯。
     • 遇到 CLR 记录：
       • 什么都不做： ARIES 的核心原则是 CLR 永不被 Undo。我们不需要对 CLR 本身执行任何操作。
       • 继续回溯： 直接读取 CLR 中记录的 undoNextLSN，并将其加入到待处理的 LSN 集合中，以继续沿着回滚链条回溯。
  4. 回滚完成： 当所有与该事务相关的日志记录都被处理完后（即 prevLSN 或 undoNextLSN 为空），为该事务写入一条 End 记录到日志缓冲区。最后，将日志缓冲区刷盘。将事务从事务表中移除。
  • 例子： 事务 T1 修改了 Page A (LSN 100)，然后修改了 Page B (LSN 120)。现在 T1 需要回滚。
    • 从 lastLSN 120 (修改 Page B) 开始。
    • 处理 LSN 120 (Update Page B)： 写入 CLR (LSN 125)，恢复 Page B。CLR 125 的 undoNextLSN 指向 LSN 100。
    • 处理 LSN 100 (Update Page A)： 写入 CLR (LSN 130)，恢复 Page A。CLR 130 的 undoNextLSN 指向 LSN 50 (Page A 的 prevLSN)。
    • 最终写入 End 记录。

2. 检查点 (Checkpointing)

为什么需要检查点？ 如果数据库系统从不进行检查点，那么在发生崩溃后，恢复过程可能需要从日志文件的最开始扫描直到日志末尾。对于一个长期运行的数据库系统，日志文件可能非常巨大，扫描整个日志文件将耗费巨大的时间和资源，导致恢复时间过长，无法接受。检查点就是为了限制恢复时需要扫描的日志量。

ARIES 的模糊检查点 (Fuzzy Checkpoint): ARIES 的检查点设计非常高效和“不打扰”。它在执行期间不会暂停所有事务的正常工作，因此被称为“模糊”检查点。

1. 写入 BEGIN_CHECKPOINT： 首先，向日志文件中写入一条特殊的 BEGIN_CHECKPOINT 日志记录。
2. 复制内存状态： 系统会暂时暂停一小段时间（非常短，通常只是为了获取一致性快照），将当前的内存事务表 (Transaction Table) 和脏页表 (Dirty Page Table, DPT) 的内容复制一份。
3. 写入 END_CHECKPOINT： 接下来，向日志文件中写入一条 END_CHECKPOINT 日志记录。这条记录中会包含刚才复制的事务表和 DPT 的完整内容。
4. 更新 Master Record： 将这条 END_CHECKPOINT 记录的 LSN 位置（或者 BEGIN_CHECKPOINT 的 LSN）安全地存储在数据库的一个固定位置，通常称为 Master Record 或元数据区。这个 Master Record 是系统重启时找到最近检查点的“锚点”。

在 BEGIN_CHECKPOINT 和 END_CHECKPOINT 记录之间，其他事务可以继续正常地执行读写操作。这意味着 END_CHECKPOINT 中记录的事务表和 DPT 状态，是检查点开始后某个时间点的一个快照，而不是精确到某一时刻的瞬间状态，但这对恢复来说已经足够了。这种“模糊”性使得检查点操作对正常事务的影响降到最低。

3. 崩溃恢复 (Crash Recovery)

这是 ARIES 算法的“大戏”。当数据库系统从崩溃中重启时，它会执行以下三个精心设计的阶段来确保数据库的一致性、原子性和持久性。

阶段一：分析 (Analysis) - “找出真相”

• 目标： 在尽可能短的时间内，确定崩溃瞬间的系统状态。具体来说，就是要回答两个问题：
  1. 哪些事务是“失败者” (Loser Transactions)，即崩溃时仍在活跃的、未完成的事务，需要被 Undo？
  2. 哪些页面是“脏”的 (Dirty Pages)，即在崩溃时内存版本比磁盘新的页面，可能需要被 Redo？
• 过程：
  1. 找到起点： 从数据库的 Master Record 中读取最近一次 END_CHECKPOINT 记录的 LSN。这就是恢复扫描日志的起点。
  2. 初始化内存表： 使用这个 END_CHECKPOINT 记录中保存的事务表和脏页表 (DPT) 的内容，来初始化内存中的事务表和 DPT。
  3. 向前扫描日志： 从这个 END_CHECKPOINT 的 LSN 开始，向前 (Forward) 扫描日志文件，直到日志的末尾 (EOJ - End Of Log)。
  4. 更新状态： 在扫描过程中，根据日志记录的类型动态更新内存中的事务表和 DPT：
     • 遇到 Update 或 CLR 记录：
       • 如果该记录的 XID 不在当前的事务表中，则将其加入事务表，状态设置为 running，lastLSN 设置为当前记录的 LSN。
       • 更新该 XID 在事务表中的 lastLSN 为当前记录的 LSN。
       • 如果该记录影响的 PageID (例如 Update 记录中的 PageID) 不在当前的脏页表 (DPT) 中，则将其加入 DPT，并设置其 recLSN 为当前日志记录的 LSN。
     • 遇到 Commit 或 Abort 记录： 将对应事务的 Status 更新为 committing 或 aborting。
     • 遇到 End 记录： 将对应事务从事务表中移除。
• 结束时：

  • 内存中事务表里所有状态不是 committing 或 aborting，或者说没有 End 记录的事务，都被标记为失败者 (Loser) 事务。这些事务在接下来的 Undo 阶段需要被回滚。

  • 我们得到了崩溃瞬间准确的脏页表 (DPT)，其中包含了所有在崩溃时内存中仍然是脏的页面，以及它们对应的 recLSN。

  • 示例： 假设日志中有 LSN 100(T1 update P1), 120(T2 update P2), 140(T1 update P3), 160(T2 commit)。检查点在 LSN 80。

    • 分析阶段从 LSN 80 扫描到日志末尾。
    • 初始事务表：空。初始 DPT：空。
    • 遇到 LSN 100(T1 update P1)：T1加入事务表(running, LSN 100)，P1加入DPT(recLSN 100)。
    • 遇到 LSN 120(T2 update P2)：T2加入事务表(running, LSN 120)，P2加入DPT(recLSN 120)。
    • 遇到 LSN 140(T1 update P3)：T1的lastLSN更新为140，P3加入DPT(recLSN 140)。
    • 遇到 LSN 160(T2 commit)：T2状态更新为committing。
    • 扫描到末尾，假设没有T2的End记录（系统崩溃在T2 commit后，End前）。
    • 结果： 事务表中有 T1 (running, LSN 140)，T2 (committing, LSN 160)。DPT 中有 P1(recLSN 100), P2(recLSN 120), P3(recLSN 140)。
    • 失败者事务： T1 (因为它没有提交/中止的标记)。T2虽然没End，但已经Commit了，它不是失败者。

阶段二：重做 (REDO) - “重复历史”

• 目标： 将数据库恢复到崩溃前的确切状态。这意味着要重做所有在日志中记录的更新操作，无论是已提交的事务的更新，还是未提交的（失败者）事务的更新。Redo 阶段会重新应用这些修改，使磁盘上的数据页与崩溃前内存中的最新状态保持一致。

• 过程：

  1. 找到 Redo 起点： 从脏页表 (DPT) 中找到所有 recLSN 值的最小值。这个最小 recLSN 成为 Redo 阶段开始扫描日志的起点 (RedoLSN)。
     • 原因： 任何比这个 RedoLSN 小的日志记录所对应的页面，一定在检查点之前就已经是干净的，或者它们的修改已经被写入磁盘。因此，我们只需要从这个点开始重做，避免了扫描不必要的历史日志。
  2. 向前扫描日志： 从这个 RedoLSN 开始，向前 (Forward) 扫描日志，直到日志的末尾。
  3. 判断并执行 Redo： 对于扫描到的每一条 Update 或 CLR 日志记录，执行以下三个检查：
     • 检查1：PageID 是否在 DPT 中？ (logRecord.PageID IN DPT)
       • 原因： 如果页面不是脏的，说明其在崩溃前已经写入磁盘，无需重做。
     • 检查2：logRecord.LSN 是否大于等于该页面在 DPT 中的 recLSN？ (logRecord.LSN >= DPT[PageID].recLSN)
       • 原因： 如果 logRecord.LSN 小于 recLSN，说明这个更新发生在页面第一次变脏之前，其影响的页面肯定已经落盘了（或者被检查点包含在内）。
     • 检查3：磁盘上该页的 pageLSN 是否小于该记录的 LSN？ (PageOnDisk.pageLSN < logRecord.LSN)
       • 原因： 这是防止重复 Redo 的关键！如果磁盘上的 pageLSN 已经等于或大于当前日志记录的 LSN，说明这个修改已经通过之前的写入（或者上一次恢复的 Redo 阶段）应用到磁盘上了，无需再次 Redo。
  4. 执行 Redo： 如果以上所有三个条件都满足，那么就说明这个修改需要在当前页面上被重做。系统会将日志记录中的 after-image 应用到内存中的页面上（如果有必要，会从磁盘加载该页面），并将该页面的 pageLSN 更新为当前日志记录的 LSN。同时，将该页面标记为脏。
  5. 刷新日志： 在 Redo 阶段结束时，将所有新的日志记录（可能包括崩溃后新生成的 End 记录等）刷盘。

• 特性： Redo 阶段是幂等 (Idempotent) 的。这意味着即使在 Redo 过程中再次发生崩溃，重启后再次执行 Redo 阶段也不会导致任何问题或错误。因为条件检查 (PageOnDisk.pageLSN < logRecord.LSN) 确保了只有尚未应用的修改才会被重做。

  • 例子（接分析阶段）： DPT 中有 P1(recLSN 100), P2(recLSN 120), P3(recLSN 140)。最小recLSN是100。
    • Redo 阶段从 LSN 100 开始扫描。
    • LSN 100 (T1 update P1):
      • P1 在 DPT 中？是。
      • 100 >= P1.recLSN(100)？是。
      • PageOnDisk.pageLSN < 100？(假设是) 是。
      • 执行 Redo： 将 P1 恢复到 LSN 100 记录的 after-image 状态，P1.pageLSN 更新为 100。
    • LSN 120 (T2 update P2):
      • P2 在 DPT 中？是。
      • 120 >= P2.recLSN(120)？是。
      • PageOnDisk.pageLSN < 120？(假设是) 是。
      • 执行 Redo： 将 P2 恢复到 LSN 120 记录的 after-image 状态，P2.pageLSN 更新为 120。
    • LSN 140 (T1 update P3):
      • P3 在 DPT 中？是。
      • 140 >= P3.recLSN(140)？是。
      • PageOnDisk.pageLSN < 140？(假设是) 是。
      • 执行 Redo： 将 P3 恢复到 LSN 140 记录的 after-image 状态，P3.pageLSN 更新为 140。
    • LSN 160 (T2 commit): 这是一个 Commit 记录，不涉及数据修改，跳过。
    • Redo 阶段结束。所有在崩溃前“丢失”的修改（包括已提交和未提交的）都被重新应用了。此时，数据库的逻辑状态与崩溃瞬间内存中的状态是完全一致的。

阶段三：撤销 (UNDO) - “回滚失败者”

• 目标： 撤销所有在分析阶段被确定为“失败者”的事务的所有影响，从而保证原子性。这个阶段会逆向地回滚这些事务，抹去它们在崩溃前留下的所有足迹。
• 过程：
  1. 确定回滚起点： 收集所有失败者事务在分析阶段得到的 lastLSN。将这些 lastLSN 放入一个临时的待处理集合 toUndo (通常是一个最大堆，以便每次取出最大的 LSN)。
  2. 向后回溯处理： 从 toUndo 集合中取出最大的 LSN (这意味着从最近的修改开始回滚)。
  3. 处理每条日志记录：
     • 如果这条日志是 Update 记录：
       • 写入 CLR： ARIES 不会直接在页面上 Undo，而是先写入一条对应的 CLR (补偿日志记录) 到日志缓冲区。这条 CLR 描述了撤销这个 Update 操作的动作。
       • 执行 Undo： 在内存中的数据页面上执行 Undo 操作（应用 before-image），并将页面的 pageLSN 更新为这条 CLR 的 LSN。
       • 更新 toUndo 集合： 将这条 Update 记录的 prevLSN (即该失败者事务的下一个需要被撤销的日志记录) 加入到 toUndo 集合中。
     • 如果这条日志是 CLR 记录：
       • 什么都不做： CLR 永不被 Undo！ 这是 ARIES 的核心。我们不需要对 CLR 本身执行任何操作，因为 CLR 代表的是一个已经完成的撤销动作。
       • 更新 toUndo 集合： 直接将这条 CLR 中记录的 undoNextLSN 加入到 toUndo 集合中。undoNextLSN 指示了该回滚链条的下一个目标。
  4. 事务结束： 当一个失败者事务的所有日志都被处理完后（即其 prevLSN 或 undoNextLSN 为空，并且该事务的 lastLSN 不再在 toUndo 集合中），为该事务写入一条 End 记录到日志缓冲区。
  5. 刷盘： 在 Undo 阶段的最后，将日志缓冲区中的所有 CLR 和 End 记录强制刷盘。

结果 ： 当 toUndo 集合为空时，Undo 阶段结束。所有失败者事务的修改都被彻底撤销了。

例子（接Redo阶段）：分析阶段我们得到失败者事务 T1，其 lastLSN 是 140。

toUndo 集合：{140}

取出 LSN 140 (T1 update P3):

• 写入 CLR (LSN 170)，undoNextLSN 指向 LSN 100 (T1 的 prevLSN)。
• 将 P3 恢复到 LSN 140 的 before-image 状态，P3.pageLSN 更新为 170。

toUndo 集合：{100}

取出 LSN 100 (T1 update P1):

• 写入 CLR (LSN 180)，undoNextLSN 指向 LSN 50 (T1 的 prevLSN，假设这是 T1 的第一条日志)。
• 将 P1 恢复到 LSN 100 的 before-image 状态，P1.pageLSN 更新为 180。

toUndo 集合：{50}

取出 LSN 50:

• 假设 LSN 50 是 T1 的第一条日志，处理后 prevLSN 为空，T1 的回滚链条结束。
• 写入 End 记录 (LSN 190) for T1。

toUndo 集合：{}

Undo 阶段结束。T1 的所有修改都被成功撤销。

恢复完成： 当 Undo 阶段结束后，数据库就回到了一个完全一致的状态：所有已提交事务的修改都已持久化（通过 Redo 保证），所有未完成事务的修改都已被彻底擦除（通过 Undo 保证）。系统现在可以安全地接受新的事务请求。