CMU15-445 数据库系统播客：数据库恢复机制 ARIES – LSN、模糊检查点与 ARIES 三阶段协议

在数据库系统的世界里，无论硬件多可靠，软件多健壮，意外崩溃（Crash）都是一个我们必须面对的现实。电源故障、操作系统 Bug、硬件失灵……任何一个都可能让数据库瞬间“宕机”。当系统重启时，我们最关心的问题莫过于：我的数据还好吗？事务是成功了还是失败了？数据库是否还处于一个一致的状态？

为了回答这些问题，并确保数据的 原子性（Atomicity） 、 持久性（Durability） 和 一致性（Consistency） ，数据库工程师们设计了复杂的崩溃恢复（Crash Recovery）机制。而在众多恢复算法中， ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) 无疑是现代关系型数据库的基石和事实上的工业标准。

今天，就让我们一起深入探索 ARIES 的奥秘，看看它是如何通过一套精妙的机制，让数据库在崩溃后能够安全、高效地“起死回生”。

一切的前提：高并发的缓冲池策略

在深入 ARIES 协议之前，我们必须先理解它所服务的数据库环境。现代数据库为了追求高性能，广泛采用 缓冲池（Buffer Pool） 来缓存磁盘上的数据页。为了最大化并发和减少 I/O 瓶颈，ARIES 协议被设计为在以下两种缓冲池策略下工作：

STEAL ：允许将 尚未提交 的事务所修改的“脏页”（Dirty Pages）写入磁盘。这避免了缓冲池被巨大的事务占满，提升了内存利用效率。NO-FORCE ：事务提交时， 不强制 要求将该事务所修改的所有脏页立即刷回磁盘。只需要确保相关的日志记录被持久化即可。这极大地降低了提交操作的延迟，提升了系统的吞吐量。

STEAL + NO-FORCE 的组合性能极佳，但它也给恢复带来了挑战：

STEAL 的存在意味着磁盘上可能包含未提交事务的数据。如果系统崩溃，这些数据必须被撤销（Undo）。NO-FORCE 的存在意味着磁盘上的数据可能落后于已提交事务的状态。如果系统崩溃，这些已提交的修改必须被重做（Redo）。

ARIES 的核心使命，正是在这个高性能但复杂的环境下，提供一个可靠的恢复方案，同时处理好 Undo 和 Redo 的问题。

ARIES 的三大核心思想

ARIES 的设计哲学可以概括为三个核心原则，它们共同构成了整个恢复协议的基石：

预写式日志（Write-Ahead Logging - WAL）

这是数据库恢复的“黄金法则”。任何对数据页的修改，都必须 先 将描述该修改的日志记录（Log Record）写入稳定的存储（如磁盘）， 然后 才能将修改后的数据页写入磁盘。这个顺序至关重要，它确保了我们总是有足够的信息来恢复数据。日志是所有真相的来源。

重做时重复历史（Repeating History During Redo）

在恢复的重做（Redo）阶段，ARIES 会严格按照日志的记录，从一个已知的正确状态（检查点）开始，重新执行所有记录在案的操作，将数据库恢复到 崩溃发生前的确切状态 。这包括所有已提交事务的修改，也包括那些最终需要被回滚的未提交事务的修改。这个阶段的目标是“回到现场”，而不是“清理现场”。

撤销时记录更改（Logging Changes During Undo）

在恢复的撤销（Undo）阶段，当系统回滚一个未提交的事务时，这个 撤销操作本身也会被记录为一种特殊的日志记录 ——补偿日志记录（Compensation Log Records, CLRs）。这确保了撤销操作的持久性和幂等性。即使在撤销过程中再次发生崩溃，系统重启后也能知道哪些操作已经被撤销过，从而避免重复撤销，保证恢复过程的正确性。

ARIES 的“语言”：日志与 LSN

为了精确地追踪和管理数据库中的每一次变更，ARIES 引入了一套关键的数据结构和概念。

日志序列号（Log Sequence Number - LSN）

每个日志记录都被赋予一个 全局唯一且单调递增的 LSN 。LSN 不仅仅是日志的编号，它像一个时间戳，贯穿于整个系统中，用于协调数据页、事务和日志之间的状态。

以下是几个至关重要的 LSN：

pageLSN ：记录在每个数据页的头部，代表 对此页的最后一次修改所对应的日志记录的 LSN 。flushedLSN ：一个内存中的变量，表示已成功持久化到磁盘的 最后一个日志记录的 LSN 。WAL 协议的核心约束可以表示为：在将一个数据页写入磁盘前，必须保证该页的 pageLSN ≤ flushedLSN。recLSN （Recovery LSN）：记录在脏页表（DPT）中，表示某个脏页 首次被修改 时所对应的日志记录的 LSN。它标记了重做操作需要关注的“最早起点”。lastLSN ：记录在事务表中，表示该事务产生的 最新一条日志记录的 LSN 。MasterRecord LSN ：一个持久化在磁盘上的特殊位置，指向 最近一次成功完成的检查点（Checkpoint）的起始 LSN ，是恢复流程的入口点。事务的生命周期日志

事务提交（Commit）

当用户执行 COMMIT 时，系统会写入一条 COMMIT 日志记录，并 同步地（synchronously） 将其连同之前该事务的所有日志一起刷入磁盘。只有当刷盘成功后，系统才会向用户确认事务已提交。随后，系统会再写入一条 TXN-END 日志记录，标记该事务的彻底终结。

事务撤销（Abort）与补偿日志记录（CLR）

当一个事务需要被撤销时，ARIES 使用日志记录中的 prevLSN 字段来高效地回溯。prevLSN 指向由同一个事务生成的上一条日志记录，从而将一个事务的所有修改串成一个反向链表。

更关键的是，每当 ARIES 撤销一个更新操作时，它会生成一条 CLR (Compensation Log Record) 并写入日志。CLR 描述了“为了撤销 LSN 为 X 的操作，我做了 Y”。

为什么 CLR 至关重要？ 想象一下在撤销过程中系统再次崩溃。重启后，恢复过程会进入 Redo 阶段，它会重放所有日志，包括这些 CLR。通过重放 CLR，系统能将已经完成的撤销操作恢复，然后从中断处继续撤销，而不会错误地去撤销一个已经被撤销过的原始操作。 CLR 自身是不需要被撤销的 ，这巧妙地避免了无限循环的撤销问题。

检查点（Checkpointing）：为快速恢复铺路

如果每次恢复都需要从头扫描所有日志，那将是一场灾难。 检查点（Checkpointing） 的目的就是定期创建一个“快照”，以限定恢复时需要处理的日志范围。

早期的检查点机制是阻塞式的，它会暂停所有事务处理，这严重影响了系统可用性。ARIES 采用了一种更优雅的方案—— 模糊检查点（Fuzzy Checkpoint） 。

模糊检查点 不会暂停系统 ，它在允许事务正常运行的同时，悄悄地完成以下工作：

写入一条 CHECKPOINT-BEGIN 日志记录。扫描缓冲池，记录下当前 活动事务表（Active Transaction Table - ATT） 和 脏页表（Dirty Page Table - DPT） 的快照。

a.ATT ：包含检查点开始时所有尚未完成的事务及其状态（如 Running, Committing）。

b.DPT ：包含缓冲池中所有脏页的 ID 及其 recLSN。

将 ATT 和 DPT 的快照信息写入一条 CHECKPOINT-END 日志记录。将 CHECKPOINT-BEGIN 的 LSN 更新到 MasterRecord 中。

通过这个快照，恢复系统就不再需要从日志的“创世纪”开始扫描，而只需从最近的检查点开始，大大缩短了恢复时间。

王者归来：ARIES 的三阶段恢复协议

当数据库从崩溃中重启，ARIES 将严格按照以下三个阶段执行恢复，确保数据最终的正确性。

阶段一：分析（Analysis）

目标 ：确定崩溃时数据库的状态——哪些事务是“失败者”（需要回滚），哪些页是“脏”的（可能需要重做）。

过程 ：

从 MasterRecord 指向的最后一个检查点开始， 向前 扫描日志，直至日志末尾。根据日志内容，动态地重建 ATT 和 DPT 。如果日志记录属于一个新事务，则将其加入 ATT。如果日志记录是 COMMIT 或 TXN-END，则更新或移除 ATT 中的对应事务。如果日志记录是一个更新操作，且其影响的页不在 DPT 中，则将该页加入 DPT。

结果 ：分析阶段结束后，我们得到一个精确的 ATT（包含所有在崩溃时仍活跃的事务）和 DPT（包含所有在崩溃时可能仍在内存中且未刷盘的脏页）。

阶段二：重做（Redo）

目标 ：重复历史，将数据库恢复到崩溃前的确切物理状态。

过程 ：

从分析阶段得到的 DPT 中最小的 recLSN 开始， 向前 扫描日志。这是个重要的优化，因为任何在此之前的修改肯定已经被包含在检查点之前的某个时间点刷盘了。对于每一条更新日志记录或 CLR，检查它所影响的数据页。如果页面的 pageLSN小于 当前日志记录的 LSN，意味着这个修改尚未在页面上体现，因此 执行重做操作 （即重新应用修改），并更新页面的 pageLSN。否则，跳过。此阶段 不会 生成新的日志记录。

结果 ：重做阶段完成后，数据库的状态与崩溃瞬间完全一致。所有已提交的修改都被应用，所有未提交的修改也暂时被应用。

阶段三：撤销（Undo）

目标 ：清理现场，将所有在分析阶段被确定为“失败者”的事务（即 ATT 中未提交的事务）的所有修改进行回滚。

过程 ：

从 ATT 中 identified 的“失败者”事务集合（Loser Transactions）开始。以 LSN 降序 （即从后往前）的方向，利用 prevLSN 链表，撤销这些事务的每一个操作。对于每一次撤销操作，都生成一条对应的 CLR 日志记录 ，并写入日志。当一个“失败者”事务的所有修改都被撤销后，为其写入一条 TXN-END 日志记录。

结果 ：撤销阶段完成后，所有未提交事务的影响被彻底消除。数据库达到了一致且持久的状态，可以安全地开放给新的事务。

总结

ARIES 协议通过预写式日志、重复历史的重做、记录日志的撤销，以及高效的模糊检查点机制，完美地解决了高性能 STEAL/NO-FORCE 策略下的崩溃恢复难题。它的三个恢复阶段——分析、重做、撤销——分工明确，逻辑严谨，确保了无论在何时发生崩溃，数据库都能被恢复到一个正确的状态。

尽管 ARIES 的细节非常复杂，但理解其核心思想，对于我们深入认识现代数据库的健壮性与可靠性至关重要。正是因为有像 ARIES 这样强大的“守护者”，我们才能放心地将数据托付给数据库系统。