ARIES 恢复算法 | Codeboy's Blog

形式陈述

固定恢复模型与持久状态

ARIES 在预写日志与steal/no-force 缓冲管理上，先分析事务和脏页，再重复历史，最后撤销未完成事务。本页把这套机制放在一个可逐步核验的单机模型中：[1]

稳定日志是完整记录组成的前缀，LSN 严格递增；崩溃丢失缓冲区和未稳定的日志尾部。
页值与 pageLSN 一起可靠写入，不发生不可检测的撕裂。redo 写入 after-image，undo 写回 before-image。
示例每页只有一个值；普通事务使用严格锁规则，不覆盖别的未结束事务对同一值的写入。恢复期间不接纳新事务。
COMMIT 记录稳定后才确认持久提交；END 表示清理完成。运行、已提交待清理、正在回滚分别记为 RUNNING、COMMITTING、ABORTING。
从一个已知正确的初始磁盘状态扫描完整日志；若使用模糊检查点，需要其另行保证的保守表重建接口。

这是单机教学状态机。原论文还处理 prepared/in-doubt 事务、细粒度锁、逻辑撤销和分布式提交；其事务表字段和终止记录约定不是本页状态名的逐字版本。处于 in-doubt 状态的事务不能未经提交协议决定就当成普通 loser。

页更新记录含事务、页、before/after-image 和 prevLSN；prevLSN 指向该事务上一条日志，不是上一条全局日志。每页的 pageLSN 记录当前页面包含的最后一条更新或 CLR 的 LSN。WAL 要求写页前稳定日志已覆盖其 pageLSN；恢复写页也遵守它。

Analysis：重建两张用途不同的表

事务表 TT 记录每个未 END 事务的状态与 lastLSN。脏页表 DPT 记录每页的 recLSN：它是可能尚未体现在稳定页中的更新的保守下界，不要求恰好等于最早缺失记录。[1, §§4.3–4.4、6.1]

在本页从干净基线完整扫描的模型中，TT 和 DPT 从空表开始。按 LSN 正序处理：

记录	TT 的变化	DPT 的变化
UPDATE	若首次出现，建 RUNNING；lastLSN 更新为本 LSN	页尚未在表中时，插入本 LSN
COMMIT	状态变 COMMITTING；更新 lastLSN	不变
ABORT	状态变 ABORTING；更新 lastLSN	不变
CLR	保持回滚状态；更新 lastLSN	页尚未在表中时，插入本 LSN
END	删除该事务	不变

CLR 属于一次回滚中的事务；本页不含回滚后恢复正常执行的 savepoint 分支。表中省略的字段均保持原值。由于完整扫描没有记录所有页刷新，DPT 不在这里推断删除或提升 recLSN；它可能比真实脏页集合大，仍是安全的。

扫描结束，COMMITTING 事务是 winner，可补写 END 并移出 TT。RUNNING 事务是 loser，将其改为 ABORTING；本页选择追加 ABORT 记录并更新 lastLSN。原已 ABORTING 的事务继续回滚，不重复追加 ABORT。TT 中没有 END 不意味着没有提交：必须查看状态。

Redo：三个过滤条件按顺序执行

若 DPT 为空，跳过 redo。否则从 $\min_p\operatorname{recLSN}(p)$ 起扫描稳定的历史日志。只考虑可重做的 UPDATE 和 CLR，对页记录 $(p,\ell)$ 顺序检查：

$p\notin\mathrm{DPT}$ ：跳过，不读页面。
$\ell<\operatorname{recLSN}(p)$ ：跳过，不读页面。
读入页后，若 $\operatorname{pageLSN}(p)\ge\ell$ ：跳过；否则应用 redo，并设置 pageLSN 为 $\ell$ 。

前两步利用保守下界排除不必读页的记录，第三步才看实际页面进度。同一页已被前面记录修改时，后续检查使用当前缓冲页，不重新读旧磁盘值。Redo 不生成新的更新日志。[1, §6.2、Figure 11] 原文还可在第三步跳过时提升恢复用 recLSN；本页保持较旧下界，只增加检查量。

Redo 包含 loser 更新与 CLR。它重建的是稳定日志前缀对应的历史状态，不是已经删除 loser 的最终状态，也不保证恢复崩溃前尚未稳定的内存尾部。

Undo：沿事务链倒退，并记录新的前进日志

将每个 loser 的 lastLSN 放入按 LSN 取最大值的待处理集合。读到记录 $r$ 后：[1, §§5.2、6.3]

若为普通可撤销 UPDATE，生成一条CLR，其 redo 描述本次补偿，prevLSN 取该事务当前 lastLSN，undoNextLSN 取 $r.\mathrm{prevLSN}$ 。在页锁存保护下完成日志追加、页面补偿及 pageLSN 更新，TT.lastLSN 改为新 CLR 的 LSN；下一目标为 undoNextLSN。
若为 CLR，不撤销它，直接把它的 undoNextLSN 作为下一目标。
若为本模型的 ABORT 等控制记录，不修改页，沿 prevLSN 继续。
下一目标为零时，追加 END，移出 TT；否则把该目标放回集合。

CLR 的追加不意味着立即强制刷盘。必须保证的是：含补偿的页面不能早于 CLR 稳定。Undo 不用 DPT 或 pageLSN 判定“这条原更新要不要撤销”；历史已在 redo 中重复，剩余工作由事务链与 CLR 指针决定。

对一次不再崩溃的恢复尝试，设起始稳定日志有 $N$ 条记录，事务表与脏页表访问及单条记录处理按常数成本计，则 analysis 与 redo 的记录处理工作为 $O(N)$ 。若 undo 实际访问 $U$ 条历史记录、开始时有 $T$ 个 loser，并且已有可按 LSN 常数时间定位记录的索引，用最大堆维护每个 loser 的下一目标需要 $O(U\log(T+1))$ 的队列工作；每条实际撤销的普通 UPDATE 生成一条 CLR。记恢复期间事务表与脏页表的最大条目数分别为 $T_{\mathrm{active}}$ 、 $P_{\mathrm{dirty}}$ ，两表与堆共需 $O(T_{\mathrm{active}}+P_{\mathrm{dirty}})$ 个元数据记录。页面缓冲、日志索引与记录载荷、编码位数及实际 I/O 另计；反复崩溃下不能由此得到统一的总工作量或时间上界。

直觉

TT 回答“哪些事务尚未收尾、下一步从哪里走”，DPT 回答“哪些页面可能欠了哪段历史”。两者都丢在崩溃中，依靠稳定日志重建；稳定页面的 pageLSN 则为某一页提供更精确的进度证据。

最容易混淆的是 CLR 的两个指针。prevLSN 保存真实发生过的事务日志链，必须接到刚刚追加过的 ABORT 或 CLR。undoNextLSN 保存剩余原始撤销工作，可能越过这些新日志和已经撤销的更新。恢复一边向日志末尾追加记录，一边沿原历史的 LSN 严格下降，并不矛盾。

第二次崩溃时CLR50已经稳定但P页仍是9，重启先重放CLR50恢复P等于5，再沿undoNextLSN到20撤销Q — ARIES：持久CLR与尚未写回的补偿页

例子与边界

原始五条日志与第一次 Analysis

初始稳定页为 $P=(0,0),Q=(0,0)$ ，有序对表示“页值、pageLSN”。完整日志如下，零指针表示事务链已到头：

LSN	事务	类型	页及变化	prevLSN
10	$T_1$	UPDATE	$P:0\to5$	0
20	$T_2$	UPDATE	$Q:0\to7$	0
30	$T_1$	COMMIT	无	10
35	$T_1$	END	无	30
40	$T_2$	UPDATE	$P:5\to9$	20

稳定日志已到 40，数据页尚未落盘，此时发生第一次崩溃 A。注意 $T_2$ 在 $T_1$ 提交后才写 $P$ ，符合上面的锁假设。

记 R 为 RUNNING，C 为 COMMITTING，A 为 ABORTING。第一次扫描的全部表状态为：

处理后	TT，按“状态／lastLSN”表示	DPT
初始	空	空
10	$T_1:\mathrm R/10$	$P:10$
20	$T_1:\mathrm R/10,\ T_2:\mathrm R/20$	$P:10,Q:20$
30	$T_1:\mathrm C/30,\ T_2:\mathrm R/20$	同上
35	$T_2:\mathrm R/20$	同上
40	$T_2:\mathrm R/40$	同上

$T_1$ 是已收尾 winner， $T_2$ 是 loser。追加 ABORT45，令其 prevLSN 为 40；TT 变为 $T_2:\mathrm A/45$ 。控制记录没有页面效果。

第一次 Redo 与第一次 Undo

Redo 起点为 10。10、20、40 的页均在 DPT 中且通过 recLSN 过滤；初始 pageLSN 都为零，因此依次重做：

处理记录	缓冲页 $P$	缓冲页 $Q$
10	$(5,10)$	$(0,0)$
20	$(5,10)$	$(7,20)$
40	$(9,40)$	$(7,20)$

30、35 是控制记录，无需 redo。这里明确重做了两个 loser 更新。现在选择把两页写盘：日志已稳定到 40，符合 WAL。稳定页成为 $P=(9,40),Q=(7,20)$ 。

Undo 首先读 45，沿 prevLSN 到 40。撤销 40 时追加

\mathrm{CLR50}:\quad P:=5,\quad \mathrm{prevLSN}=45,\quad \mathrm{undoNextLSN}=20.

缓冲页变为 $P=(5,50)$ ，TT.lastLSN 为 50。此刻选择将日志前缀强制刷到 50，不写回补偿页，然后发生第二次崩溃 B：

状态所在位置	B 时实际保留的内容
稳定日志	10、20、30、35、40、45、50
稳定页	$P=(9,40),Q=(7,20)$
丢失的缓冲页	$P=(5,50),Q=(7,20)$
丢失的恢复表	TT 与 DPT；下一撤销目标曾为 20

这是允许的 WAL 窗口。不能把“CLR 已存在”误当成“补偿后的页已经写盘”。

第二次重启的全部续接

从同一干净基线完整扫描稳定日志，前五行与第一次相同。45 将 $T_2$ 置为 ABORTING／45，50 将其 lastLSN 更新为 50。DPT 仍为 $P:10,Q:20$ ；它不知道先前两页曾被刷出，所以仍保守地保留较早下界。

第二次 redo 从 10 开始：

页记录	读取时 pageLSN	判断	页结果
10，写 $P=5$	40	$40\ge10$ ，跳过	$P=(9,40)$
20，写 $Q=7$	20	$20\ge20$ ，跳过	$Q=(7,20)$
40，写 $P=9$	40	$40\ge40$ ，跳过	$P=(9,40)$
50，补偿 $P=5$	40	$40<50$ ，重做 CLR	$P=(5,50)$

不能跳过 50：它的记录虽稳定，页面效果却丢失了。第二次 undo 从 lastLSN=50 开始，遇到 CLR 后直接转到 20；不沿 50 的 prevLSN=45 返回 40。撤销 20，追加

\mathrm{CLR60}:\quad Q:=0,\quad \mathrm{prevLSN}=50,\quad \mathrm{undoNextLSN}=0.

缓冲页变为 $Q=(0,60)$ 。下一目标为零，追加 END70，prevLSN=60，并删除 TT 条目。恢复后的逻辑状态为 $(P,Q)=(5,0)$ ：保留 $T_1$ 的提交，去掉 $T_2$ 的两次更新。

若要让本例终点也全部落在稳定页上，可再强制日志到 70，并写回 $P=(5,50),Q=(0,60)$ 。这是一项明确选择，不是 no-force 要求每次恢复结束都立即刷净全部页面。若只稳定了 CLR 而仍未写页，下次 redo 可以补齐；若 CLR 也未稳定，WAL 保证它对应的页面补偿尚未落盘，下次会重新完成相应撤销。

前两种过滤与不适用情形

上述主例从最早日志扫描，所以没有页被前两种过滤排除。以下是其他合法检查点状态中的独立判断，不是悄悄更改主例的 DPT：

DPT 证据	待检查记录	结果
$R$ 不在 DPT，保守性保证其相关历史已稳定	$R$ 的更新 12	不读页，按第一项跳过
$P$ 的 recLSN 为 40	$P$ 的更新 10	不读页，按第二项跳过
$P$ 的 recLSN 为 40	$P$ 的更新 40	仍须读 pageLSN，不能仅凭 DPT 重做

若扫描起点来自模糊检查点，必须把其快照与并发日志正确合并；用旧快照覆盖新 TT 状态，或把 recLSN 擅自抬高，都会破坏上述保守性。本文的完整轨迹刻意从已知基线扫描，因此不借用未经展示的检查点合并来得到数字。

介质整块丢失需要备份和 media recovery；无可靠 pageLSN 的撕裂页需要检测与修复层。外部邮件、支付调用和无法重复的业务动作也不是这里的物理页更新。事务隔离规则保证 before-image 撤销不会抹掉别人的合法后续写入；只实现三阶段而缺少这一前提，不足以恢复任意并发历史。

推论与应用

三个恢复不变量

Analysis 的保守性。 从干净基线出发，每页第一次更新进入 DPT，后续保留更早下界，所以任何尚未稳定的更新都不早于该页 recLSN。TT 对每条事务记录更新 lastLSN，COMMIT／ABORT 改变状态，END 删除条目；沿日志长度归纳，就得到稳定前缀末尾的事务状态。页刷新未被观测只会增加 redo 候选，不会漏掉缺失更新。

Redo 的逐页前缀。 页值与 pageLSN 同步写入、页内更新按日志顺序进行，稳定页因此对应该页历史中的某个前缀。扫描记录 $\ell$ 时，若 pageLSN 已达到 $\ell$ ，其效果或其后继历史已在页上，无须退回旧值；否则按序应用缺失 after-image 并设置 LSN。对每页记录数归纳，扫描结束时恰好得到稳定日志的页历史，包括所有稳定 CLR。幂等性来自版本检查，不能只凭“写同一个值”推广到任意增量操作。

Undo 的剩余链。 每个事务的待处理指针代表尚未撤销的历史。普通更新生成 CLR 后，下一指针是被撤销更新的前驱；持久 CLR 在任何重启中都将控制流越过同一更新。Redo 保证先兑现这个持久补偿，再继续剩余链。所有非零下一指针都严格小于当前被处理的历史 LSN，所以在最后一次崩溃后，有限日志的 undo 会结束；新追加的 CLR 不使下降度量反向增长。

若 CLR 没有持久化，崩溃后可能重新执行那次内存中的撤销；不能宣称任意多次崩溃下 CPU 工作绝不重复。准确保证是：WAL 将可见的页面补偿与稳定 CLR 对齐，稳定的撤销进度不再作为原更新重复撤销。上述条件和锁假设共同保证最终只保留 winner 效果。

日志诊断中的三个核对点

本例提供三项可以直接检查的证据：45→40 是真实事务前驱，50 的 prevLSN=45 与 undoNextLSN=20 分工不同，第二次 redo 的唯一必要页面动作是 CLR50。若恢复代码把这两个指针共用一个字段，或按“已提交”筛 redo，它就无法重现这条合法轨迹。

模糊检查点可缩短扫描，索引恢复可使用更复杂的逻辑补偿，恢复也可并行化；这些扩展都必须保留各自的日志顺序、持久化和剩余工作接口，不能由本页的单值页面证明直接推出。

参考资料

[1] C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh and Peter Schwarz, ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM TODS 17(1), 1992, pp. 94–162；§§4.1–4.4，pp. 113–115：日志、页面、TT、DPT；§5.2，p. 118：CLR 指针；§6.1–6.3，Figures 10–12，pp. 122–127：三阶段算法。原文 §5.3 的提交记录约定含分布式事务，本页明确使用单机简化。
Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1992, Ch. 11。

形式陈述 ​

固定恢复模型与持久状态 ​

Analysis：重建两张用途不同的表 ​

Redo：三个过滤条件按顺序执行 ​

Undo：沿事务链倒退，并记录新的前进日志 ​

原始五条日志与第一次 Analysis ​

第一次 Redo 与第一次 Undo ​

第二次重启的全部续接 ​

前两种过滤与不适用情形 ​

三个恢复不变量 ​

日志诊断中的三个核对点 ​

反向链接