ARIES 恢复算法 | Codeboy's Blog

形式陈述

ARIES 在预写日志和 steal/no-force 缓冲管理上运行。更新日志通常含 LSN、事务 ID、prevLSN、页 ID、redo/undo 信息；每个数据页记录 pageLSN。重启按三阶段执行。

Analysis 从最后一个完整检查点附近向前扫描，重建 Transaction Table（事务状态、lastLSN）与 Dirty Page Table（DPT）。DPT 的 recLSN(p) 是页 $p$ 自上次可能干净以来最早的更新 LSN，给出该页需要检查 redo 的下界；扫描结束仍活跃的事务是 loser。

Redo 从所有 DPT 条目最小的 recLSN 开始，按日志正序“重复历史”，包括后来将被撤销的 loser 更新。对页记录 LSN $\ell$ ，若页不在 DPT、 $\ell<\operatorname{recLSN}(p)$ ，或磁盘

\operatorname{pageLSN}(p)\ge\ell,

则可跳过；否则重做并把 pageLSN 推到 $\ell$ 。该检查让重复重启保持幂等。

Undo 按 LSN 逆序遍历 loser 的日志链，撤销可撤销更新，并为每次撤销写补偿日志记录。CLR 的 undoNextLSN 指向下一项待撤销工作；事务完全回滚后写 END。三阶段次序先重建精确崩溃现场，再只移除未完成事务。

提交记录已稳定但尚无 END 的事务是 winner：Analysis 可补写 END，却不能把它当 loser。已经写 ABORT、但回滚未完成的事务仍需继续 Undo。事务状态与最后 LSN 共同决定路径，不能只用“有没有 END”二分提交与中止。

直觉

ARIES 不试图猜磁盘上哪些页“应该已经写过”。Analysis 先列出不确定范围，Redo 用日志和 pageLSN 把所有相关页推到崩溃瞬间，Undo 再沿每个 loser 的私人足迹倒退。先把现场复原，才能让部分回滚、恢复中再次崩溃和并发页刷写共享一套规则。

DPT 是保守过滤器，不是数据库内容副本。页在表中表示“可能缺少从 recLSN 开始的某些更新”；最终是否重做仍由磁盘 pageLSN 判断。Transaction Table 同样记录恢复状态，不等于所有已提交事务的永久目录。

Redo 从全局最小 recLSN 顺序扫描，看似会重读无关记录，却保留日志顺序和顺序 I/O；逐页 pageLSN 检查再精确跳过。为每页随机追日志可能减少扫描字节，却会破坏简单的重复历史接口并增加索引维护。

例子与边界

假设开始时 $P=Q=0$ ，日志为：

text

10: T1 UPDATE P 0->5
20: T2 UPDATE Q 0->7
30: T1 COMMIT
35: T1 END
40: T2 UPDATE P 5->9
CRASH

若这些数据页尚未落盘，Analysis 得到 DPT： $P\mapsto10,Q\mapsto20$ ，并认定 $T_2$ 是 loser。Redo 从 10 开始，依次把 $P$ 变为 5、 $Q$ 变为 7、再把 $P$ 变为 9；它没有因为 $T_2$ 未提交就跳过 20 与 40。

Undo 随后先撤销 LSN 40，使 $P$ 回到 $T_1$ 已提交的 5，再撤销 LSN 20，使 $Q$ 回到 0，并分别记录 CLR。最终状态为 $(P,Q)=(5,0)$ 。若某页磁盘 pageLSN 已经是 40，相应 redo 会跳过，逻辑结果不变。

这个例子假定日志页和数据页没有不可检测的撕裂，且更新的 redo/undo 语义正确。介质整块丢失需要备份与 media recovery；事务间逻辑约束、锁重新取得和外部消息也不由 restart 三阶段自动恢复。

若在撤销 LSN 40、写出 CLR 后再次崩溃，下一轮 Redo 会重放该 CLR，Undo 再沿 undoNextLSN 继续到 20。这个窗口正是 ARIES 不把恢复当成一次必然成功的离线脚本的原因。

推论与应用

ARIES 的“repeat history”常被误写成“只重做 winner”。后者无法重建 loser 后续 undo 所依赖的页面形态，也难以解释恢复中断后的 pageLSN。正确边界是：Redo 重现所有需要的历史，Undo 再按事务状态筛掉 loser。

模糊检查点缩短 Analysis 起点，却不要求停机或刷净脏页；CLR 让 Undo 的进展自身也受 WAL 保护。两者不是附加优化口号，而是算法能在高并发与重复崩溃中保持正确的状态接口。

参考资料

C. Mohan et al., “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging,” ACM Transactions on Database Systems 17(1), 1992, pp. 94–162。
Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1992, Ch. 11。
Goetz Graefe, “A Survey of B-Tree Logging and Recovery Techniques,” ACM Transactions on Database Systems 37(1), 2012, Article 1。

形式陈述 ​

反向链接

形式陈述