【数据库系统原理】第33篇：ARIES恢复算法：工业级数据库的经典恢复范式

目录一、ARIES的诞生背景与核心哲学二、ARIES的三大基石数据结构三、检查点为恢复提供起点锚定四、分析阶段重建故障时刻的系统状态五、Redo阶段忠实地重复历史六、Undo阶段逆向逻辑回滚与补偿日志七、嵌套回滚与保存点支持八、ARIES的完备性论证九、结语工业级恢复的标准范式一、ARIES的诞生背景与核心哲学在前两篇文章中我们分别建立了故障分类与恢复框架以及WAL协议中物理日志、逻辑日志与缓冲策略的工程实现基础。这套理论在1980年代逐渐成熟但各家数据库系统的恢复实现仍然各自为战——对Steal/No-Force策略下如何高效而正确地执行恢复缺乏统一的方法论。ARIES正是在这一背景下诞生的。1989年至1992年间IBM Almaden研究中心的C. Mohan、Don Haderle、Bruce Lindsay等人在一系列论文中提出了ARIES——Algorithm for Recovery and Isolation Exploiting Semantics利用语义进行恢复与隔离的算法。ARIES不仅是一套恢复算法更是一套完整的事务恢复方法论。它将此前分散的恢复技术——WAL日志、物理逻辑日志、补偿日志、检查点、嵌套回滚——整合进一个统一的理论框架并提供了严密的正确性证明。ARIES的核心哲学可以用一句话概括恢复应该是历史的忠实重建而非对故障时刻状态的猜测性修补。这一哲学在三个核心设计原则中得以体现。其一Redo阶段必须重复所有已提交事务的所有修改不论这些修改在崩溃前是否已经写入磁盘——即“重复历史”。其二Undo阶段必须按操作执行的逆序逐条撤销未提交事务的修改并在Undo过程中写补偿日志以确保可中断性。其三整个恢复过程是可重入的——恢复在执行中途再次崩溃后重启后可以继续执行恢复而不必从头开始。这套哲学在1990年代迅速成为关系数据库工业界的标准范式。MySQL InnoDB、PostgreSQL、Oracle、IBM Db2的恢复机制虽然在具体实现上各有差异但其核心架构都建立在ARIES的原理之上。二、ARIES的三大基石数据结构在展开ARIES的三阶段恢复流程之前必须先理解支撑整个算法的三大基石数据结构。它们在正常运行期间由系统持续维护在崩溃后成为恢复流程的信息源。日志记录是ARIES最基础的数据结构。每条日志记录包含日志序列号LSN一个单调递增的64位整数精确标识日志记录在日志文件中的物理位置和逻辑顺序事务ID类型标识插入、删除、更新、补偿日志记录、提交、回滚等页面ID——该操作涉及的数据页标识前像与后像或逻辑操作的语义描述以及指向前一条日志记录的指针形成每条日志记录指向前一条的链表结构支持Undo阶段沿链回溯。事务表是内存中的数据结构在正常运行期间维护所有活跃事务的状态。每个活跃事务在事务表中有一条记录包含事务状态运行中、已提交、已回滚事务的最后一条日志记录的LSN以及事务的回滚状态信息。检查点时事务表的快照被写入日志供分析阶段重建故障时刻的活跃事务集合。脏页表同样是内存中的数据结构维护缓冲池中所有脏页的信息。每个脏页有一条记录包含页面ID和该页面第一次被修改时所对应的日志记录的LSN——即FirstLSN。FirstLSN是Redo阶段的起始边界对于任意一个脏页所有LSN小于其FirstLSN的日志修改必定已经写入磁盘而LSN大于等于其FirstLSN的日志修改可能尚未写入磁盘。检查点时脏页表同样被写入日志。LSN在这三套数据结构中扮演着统一的坐标轴角色。日志记录的LSN标识了日志中的位置事务表记录中存储的是该事务最后一条日志的LSN脏页表记录中存储的是该页最早的未刷盘修改的LSN。三套数据通过LSN实现了精确的对齐。三、检查点为恢复提供起点锚定检查点是数据库系统在正常运行期间间歇性执行的操作其目的是在日志中锚定一个已知的系统状态使得崩溃后的恢复不必从日志的起始开始扫描。ARIES采用了一种轻量级的检查点策略。检查点发生时系统执行以下操作将当前事务表的内容所有活跃事务及其状态写入日志将当前脏页表的内容所有脏页的页面ID和FirstLSN写入日志将检查点记录的LSN写入数据库的启动元数据区域。检查点本身不执行任何数据刷盘操作——不强制将脏页写入磁盘不阻塞正在运行的事务不要求缓冲池刷新。这种轻量特性是ARIES检查点的重要工程优势检查点可以在系统运行时频繁执行甚至每分钟一次而不对正常事务处理产生明显的性能冲击。检查点在恢复中的作用是为分析阶段提供起点。恢复管理器从检查点记录的LSN位置开始扫描日志利用检查点中保存的事务表和脏页表快照重建故障发生时刻的系统状态。检查点越新恢复需要扫描的日志范围越小恢复时间越短。四、分析阶段重建故障时刻的系统状态分析阶段是ARIES恢复流程的第一步。它从最后一次检查点开始沿着日志向前向更新的方向扫描直到日志末尾。分析阶段的输出是崩溃时刻的精确活跃事务列表以及崩溃时刻的精确脏页表包含哪些页面可能未将最新的已提交修改写入磁盘。分析阶段的具体流程如下。将事务表和脏页表初始化为检查点中保存的快照。从检查点的LSN开始逐条扫描日志记录。对于每条日志记录如果是事务开始或事务操作记录若该事务不在当前事务表中则加入并更新该事务的最后LSN。如果是事务提交或回滚记录从事务表中移除该事务。如果是页面修改记录若该页面不在当前脏页表中则加入并记录该日志记录的LSN作为该页的FirstLSN若已存在则更新为更早的LSN。扫描完成后事务表中剩余的正是崩溃时刻所有活跃未提交且未回滚的事务——这些事务的修改必须在后续的Undo阶段被撤销。脏页表中记录的是所有在检查点后曾被修改的页面及其最早未确认落盘的LSN——这些页面必须在后续的Redo阶段被重做。分析阶段的精妙之处在于它将“重建系统状态”这一抽象任务转化为机械的日志扫描和两套数据结构的增量更新。不需要复杂的全局一致性检查不需要猜测哪些页面可能已经落盘——只需忠实地从检查点快照出发逐步应用日志中记录的事件更新事务表和脏页表扫描结束时的状态就是崩溃时刻状态的精确近似。五、Redo阶段忠实地重复历史Redo阶段是ARIES区别于此前恢复算法的最核心创新之一。传统恢复算法往往试图在Redo阶段“选择性”地重做——只重做那些“可能未写入磁盘”的已提交修改。选择性Redo要求系统精确知道哪些页面在崩溃时已经落盘这在Steal/No-Force策略下是不现实的。ARIES的Redo阶段采用了截然不同的策略重复历史——将所有可能未落盘的修改全部重做不论它们属于已提交事务还是未提交事务。Redo的起始点不是从检查点开始而是从脏页表中所有脏页的最小FirstLSN开始——这是最早的可能未落盘修改的位置。从这个起始点向前扫描日志对于每条涉及页面修改的日志记录执行以下判断如果该页面不在当前脏页表中说明该页的修改已经在崩溃前落盘跳过该条Redo如果该页面在脏页表中但该日志记录的LSN小于该页的FirstLSN说明该条修改已经落盘跳过该条Redo如果该页面在脏页表中且日志LSN大于等于该页的FirstLSN执行Redo——在页面上重新应用该条日志记录描述的修改。判断是否需要Redo的快捷方法是比较日志记录的LSN与磁盘上数据页中存储的LSN。ARIES要求每个数据页在页头存储最近一次修改该页的日志记录的LSN称为pageLSN。如果在日志扫描中遇到的日志记录的LSN小于等于磁盘上该页的pageLSN说明该条修改已经反映在磁盘页面上Redo可以跳过。这一判据比脏页表的FirstLSN判断更为精确。Redo阶段完成时数据库的磁盘状态被恢复到崩溃发生前最后一个已提交修改写入后的状态——不论这些修改属于已提交事务还是未提交事务。此时磁盘上的数据包含了所有事务包括未提交事务在崩溃前的修改。未提交事务的修改将在Undo阶段中被清除。六、Undo阶段逆向逻辑回滚与补偿日志Undo阶段处理分析阶段识别出的所有活跃事务——即崩溃时尚未提交或回滚的事务。Undo按以下顺序执行从日志末尾向起始方向逆向扫描。对于每条日志记录如果它属于活跃事务集合中的某个事务则执行Undo——根据日志记录中的前像或逻辑操作描述将数据恢复到修改前的状态。ARIES的Undo操作具有两个关键特性。其一Undo操作本身必须生成日志记录——补偿日志记录。当一条修改被Undo时系统写入一条补偿日志记录描述Undo操作对数据页的实际修改即写入的前像值。补偿日志记录的LSN被记录在待Undo事务的事务表条目中作为该事务的新“最后LSN”。如果Undo过程中系统再次崩溃重启后的分析阶段会扫描到这些补偿日志记录恢复流程能够从上次中断的位置继续Undo而不是从零开始。其二Undo是逻辑性的而非物理性的。对于插入操作的Undo系统执行逻辑删除对于删除操作的Undo系统执行逻辑插入。逻辑Undo使得ARIES能够正确处理B树索引的分裂和合并——这些操作的逆向操作无法简单地用物理前像/后像来描述而是需要执行对应的逆向逻辑操作。逻辑Undo也为嵌套回滚和部分回滚提供了支持。Undo阶段继续逆向扫描日志逐条Undo活跃事务的操作直到所有活跃事务的修改都被撤销完毕。在Undo过程中每个活跃事务的最后一个Undo完成后系统为该事务写入一条“事务回滚完成”日志记录。当所有活跃事务都处理完毕后Undo阶段结束。分析-Redo-Undo三阶段完成后数据库进入一致状态——所有已提交事务的修改持久化在磁盘上所有未提交事务的修改被完全清除。系统可以开始接受新的事务连接。七、嵌套回滚与保存点支持ARIES对事务回滚的处理体现了其设计精细度的另一维度。传统恢复算法通常将回滚视为一个简单的撤销过程——逐条Undo事务的所有操作完成后事务消失。ARIES将回滚本身视为一个“逆向操作流”赋予其与正向操作同等的日志保障。当一个事务在执行过程中被显式要求回滚如应用层ROLLBACK或系统要求回滚如死锁牺牲者ARIES并不立即执行所有Undo操作并等待其完成。相反它引入了一个嵌套回滚概念回滚操作被分解为一系列小的逆向步骤每个步骤产生补偿日志记录逐步消除正向操作的影响。如果在回滚过程中再次发生故障补偿日志记录保障了回滚的可重续性。保存点机制是嵌套回滚的自然延伸。事务可以在执行过程中设置保存点标记一个逻辑上的中间点。当需要部分回滚时事务可以回滚到某个保存点——仅撤销该保存点之后的操作保留保存点之前的操作效果。ARIES的Undo逻辑天然支持部分回滚从当前事务的最后一条日志记录开始沿日志链逆向Undo直到遇到目标保存点的日志记录为止。八、ARIES的完备性论证ARIES之所以成为工业标准不仅在于它提供了可工作的恢复方案更在于它对正确性进行了严密的形式化论证。ARIES的正确性建立在以下不变量的严格维护之上。日志先行原则保证在任何时刻如果数据页的某个修改已经写入磁盘则描述该修改的日志记录必定已经先于它写入磁盘。脏页表的FirstLSN不变量保证对于任意脏页所有LSN小于其FirstLSN的日志修改必定已经写入磁盘。事务表的状态传递保证分析阶段从检查点事务表出发沿日志正确传递事务状态变更得到的崩溃时刻活跃事务集合是精确的。补偿日志的可重续性保证Undo过程在任何中断后可以继续从断点执行而不产生重复Undo或遗漏Undo。这些不变量并非各自独立而是环环相扣。如果日志先行原则被违反脏页表的FirstLSN推断就可能错误。如果分析阶段的事务状态传递有误Undo阶段可能遗漏活跃事务。ARIES的整体正确性正是建立在这一环环相扣的不变量系统之上。九、结语工业级恢复的标准范式ARIES的意义超越了任何单一数据库产品的恢复实现。它定义了“数据库系统应当如何进行崩溃恢复”的方法论标准。在ARIES之前恢复机制的实现众说纷纭、良莠不齐。在ARIES之后恢复机制的研究和实践有了统一的参照框架——即使某个数据库系统并未严格遵循ARIES的每一个细节其设计者也几乎必然以ARIES的原则为参照来论证自身方案的合理性。下一篇我们将探讨两种与ARIES互补的恢复优化技术——检查点技术的变体与影子分页机制。检查点如何在ARIES的轻量检查点基础之上进一步缩短恢复时间影子分页如何通过原子化的指针切换来实现一种完全不同原理的事务原子性保证。这两种技术与ARIES一起构成了数据库恢复工程的完整工具箱。