周刊（第16期）：图解ARIES论文（下）

引言：ARIES(Algorithm for Recovery and Isolation Exploiting Semantics的简称）是论文《ARIES: A Transaction Recovery Method Supporting Fine-Franularity Locking and Partial Rollbacks Using Write-Ahead Logging》中提到的一种存储引擎中数据恢复的算法。这篇论文可以说是存储引擎数据恢复领域必读的一篇论文，这两期的周刊就是对这篇论文的图解，这是其中的下篇。

图解ARIES论文（下）

前情回顾

在周刊（第15期）：图解ARIES论文（上）中，讨论了存储引擎面临的问题，如果存储引擎宕机重启，将要进行以下两个操作：

• 撤销（Undo）：未完成或者由于各种原因发生回滚（rollback）、中断（abort）的事务，其修改需要被撤销，即回滚为事务之前的旧值。
• 重做（Redo）：已经提交的事务，其修改操作的效果需要体现为新值。

为了这两个操作，存储引擎就需要回答这两个问题：

• “是否允许未提交事务的修改在持久化存储上生效”（Whether the DBMS allows an uncommitted txn to overwrite the most recent committed value of an object in non-volatile storage），被称为Steal policy。
• 一个事务在提交之前是否需要将所有修改同步到持久化存储上（Whether the DBMS requires that all updates made by a txn are reflected on non-volatile storage before the txn is allowed to commit.），称为force policy。

两个问题合并起来一共有四种组合：

最常见的组合策略实现有以下两种：

• shadow paging（影子页面）：采用no-steal+force策略。

• WAL：采用steal+no-force策略。

两者的优缺点：

• steal+no-force策略：运行时效率高，即读写数据的效率高，但是数据恢复的效率低。以WAL为例，运行时写入WAL日志即可，而写WAL是append操作而不是随机写操作，速度会更快；但是恢复时需要重放（replay）WAL日志。
• no-steal+force策略：运行时效率低，但是数据恢复的效率高。

目前更常见的做法是WAL。在WAL这个策略中，任意时刻都满足以下条件：

全量数据 = 数据库文件数据 + WAL中已提交但还未转入数据库文件的数据

即可以认为，WAL中的已提交但还未转入数据库文件的数据是增量的数据。

另外，为了避免WAL文件无限增大，还引入了checkpoint流程，但是就目前来看在checkpoint时，需要终止写事务，这导致了写操作的卡顿。

前情回顾完毕，本篇正式开始介绍ARIES论文的思想，ARIES在此基础上提供了更高效的事务回滚、checkpoint算法的实现。

为了能够回滚事务，以及在checkpoint操作时不阻塞写事务，ARIES算法引入了一种重要的变量LSN（Log Sequence Number），下面几乎所有的相关算法、数据结构都跟这个变量有关系，从写事务开始说起。

写事务流程

扩展WAL格式

回忆一下上一节中wal日志的格式，有以下三类：

• 事务开始时，写入一条BEGIN表示写事务开始。
• 记录事务的修改操作：对于写事务中的每一条修改操作，都要记下以下四个数据：
  • 事务ID，这样在同一时间进行多个写事务时，可以知道对应的是哪个事务。
  • 修改的键值。
  • 修改之前的值，用于撤销事务时使用。
  • 修改之后的值，用于重做事务时使用。
• 事务提交时，写入一条COMMIT表示事务结束。
• 做checkpoint时，写入一条CHECKPOINT表示在这个点做了checkpoint操作。

ARIES算法要求扩展wal日志的格式：

• 每条日志需要带上一个全局唯一且单调递增的LSN序列号（Log Sequence Number），用于区分每一条日志。
• 同时，除了上面三类日志以外，还需要在事务提交成功之后，再写一条TXN-END的日志表示事务的结束。

总结起来，到目前为止，ARIES算法中日志有如下几类，其格式如下：

• 事务开始：LSN:<事务编号,BEGIN>。
• 事务的修改操作：LSN:<事务编号,修改的键值,修改之前的值,修改之后的值>。
• 事务提交操作：LSN:<事务编号,COMMIT>。
• 事务提交成功：LSN:<事务编号,TXN-END>。
• checkpoint操作：LSN:checkpoint。

有了LSN之后，各类数据就需要记录相关的LSN以便记录当前的进度：

几类记录LSN的数据

以下图来展开解释这几个值的使用。

例子

在上图中：

• 在LSN=07的位置，做了一次checkpoint，这意味着：
  • 在07之前的所有wal的内容，都同步到了数据库文件中，于是数据库文件中的A=3，这是07日志之前最后一次成功提交的事务对A的修改值。
  • 因为LSN=07做了一次checkpoint，所以MasterRecord=07，如果这时候发生宕机，那么重启恢复的时候，数据库将不会扫描在07这个LSN之前的wal日志，因为根据MasterRecord=07意味着这之前的日志都已经落盘从wal转存到数据库文件中了。
• 内存中的flushLSN=11，这是因为最后一条落盘的WAL日志序列号为11。
• 这个例子中仅有一个页面，为了讨论问题的方便，假设这个例子中的所有修改都在同一个页面中：
  • 右下角表示磁盘上在数据库文件中的页面，它始终反映的是最后一次checkpoint的修改，因此有： pageLSN=06和A=3。
  • 左下角表示该页面的内存中的修改，也被称为”脏页面“，内存中的脏页面一定反映的是当前最新的对该页面的修改，因此pageLSN=15和A=12、B=10。

以上几点都比较明确了，来看一个疑难问题：假如内存中有一个页面，如何判断这个页面是否能被释放？

这取决于这个页面的pageLSN与flushLSN之间的关系，因为pageLSN表示最后一次更新该页面时的LSN，因此唯有当将所有满足pageLSN<=flushLSN的日志都从内存落到磁盘时，这个页面才能被释放。

在上图中，对脏页面而言，pageLSN=15 > flushLSN=11，说明脏页面中仍然有日志还未落盘，也就是LSN=12到15这几条日志还在内存里，所以这时候不能释放这个脏页面。

来看何时才能安全释放这个脏页，如下图所示：

上图中，将LSN=12到15这几条日志从内存中落盘到磁盘上，这时候flushLSN修改成15，而内存中脏页面的pageLSN=15，这表示内存中脏页的修改都以日志形式落盘，于是这个脏页可以被安全释放了。

上面的流程里，还需要特别注意几点：

• 内存中的脏页不能直接落盘为磁盘上数据库文件中的页面，一定是经过这样的流程：
  • 对页面的修改日志先写入到内存中的WAL日志中。
  • 内存中的WAL日志落到磁盘上的WAL日志。
  • 对磁盘上的WAL日志进行checkpoint，在这个流程里依次回放WAL的操作，将修改落盘到数据库文件的页面里。

中断事务流程

事务中断时，就需要回滚这个事务前面的修改，为了记录一个事务都依次进行了哪些修改，需要在每一条记录上加入一个prevLSN字段表示在同一个事务中上一个日志的LSN，之所以加上prevLSN字段，是因为同一个事务的写日志，物理上不见得就是连续的，prevLSN在这里扮演了逻辑指针的作用。

有了prevLSN字段之后，继续扩展前面的日志格式：

• 事务开始：LSN|prevLSN:<事务编号,BEGIN>。
• 事务的修改操作：LSN|prevLSN:<事务编号,修改的键值,修改之前的值,修改之后的值>。
• 事务提交操作：LSN|prevLSN:<事务编号,COMMIT>。
• 事务提交成功：LSN|prevLSN:<事务编号,TXN-END>。

可以看到，有了prevLSN这个字段以后，可以将同一个事务的修改按照逆序串联起来，于是就可以根据这个逆序使用保存的undo值来回滚事务之前的修改。

只有这样还不够，因为还有可能在中断事务回滚的过程中也发生了宕机，这时候需要记录下来回滚进行到哪里了。记录回滚进度的日志被称为CLR（Compensation Log Record，补偿日志记录）日志，CLR日志和事务的修改操作日志格式大体相同，但是还需要新增一个UndoNext字段，表示回滚操作中下一个需要回滚的日志，显然有如下的关系：

假如CLR(A)是针对WAL(B)的回滚操作，那么CLR(A).UndoNext = WAL(B).prevLSN

于是在前面扩展之后的日志格式继续进行扩展新增CLR类型的日志：

• 事务开始：LSN|prevLSN:<事务编号,BEGIN>。
• 事务的修改操作：LSN|prevLSN:<事务编号,修改的键值,修改之前的值,修改之后的值>。
• CLR日志：LSN|prevLSN:<事务编号,修改的键值,撤销之前的值,撤销之后的值,下一个需要撤掉操作的LSN>。
• 事务提交操作：LSN|prevLSN:<事务编号,COMMIT>。
• 事务提交成功：LSN|prevLSN:<事务编号,TXN-END>。

以一个例子来说明情况：

在上面的表格中：

• 事务T1：
  • LSN=001：开始事务。
  • LSN=002：修改键值A=40，修改之前的值为30。
  • LSN=011：中断事务T1。
  • LSN=26：由于前面开始中断事务T1的操作，于是从中断的那条日志开始进行回滚操作。中断日志的LSN为011，其prevLSN=002，于是新增一条CLR日志：
    • 该CLR日志的prevLSN为11，即中断开始的日志LSN。
    • 将回滚操作前后（即LSN=002的这条日志）的值记录下来。
    • 将回滚操作的prevLSN记录为这条CLR日志的UndoNext。
    • 继续这个流程，直到回滚完毕这个事务的所有操作（即一直回滚到prevLSN=nil的日志）。
  • 最后，在回滚操作结束之后，同样也需要一条Txn-End日志来标记事务回滚结束。

有了CLR日志之后，因为知道了事务中哪些操作已经被回滚过了，这样就不会在程序宕机重启时重复执行了，另外CLR日志本身并不需要回滚操作。

fuzzy checkpoint流程

问题

上一篇讲解checkpoint流程时，有一个重要的问题：即一旦开始checkpoint，则当前所有事务，要么没有开始，要么全都已经结束，即此时不允许存在还未结束的事务。

这带来几个问题：

• checkpoint运行时，不允许同时并发有其它的写事务。
• 由于上面这一点，一旦checkpoint要花费很长的时间，会导致系统在这段时间内都无法进行写操作。

于是，首先想到的策略，是将事务运行时的状态加入到checkpoint流程中，这样就允许同时并发有写事务操作了。

带状态的checkpoint

为了在checkpoint过程中保存事务运行时的状态，引入了以下两个数据结构。

• Active Transaction Table（简称ATT，活跃事务表）：用于保存同时在运行的事务信息，表里存储的每个事务信息包括如下字段：
  • txnId：事务ID。
  • status：事务当前状态，包括Running（R，在运行）、Commit（C，在提交）、Candidate for Undo（U，准备撤销事务）。
  • lastLSN：该事务最后的日志LSN。
• Dirty Page Table（简称DPT，脏页表），这个表中存储的每个脏页信息，有recLSN：第一条修改这个页变成脏页的日志LSN。

**注意：这两个表的内容，要做为checkpoint记录的一部分，写入WAL日志中。 **

有了这些状态信息之后，一个重大的改进是：

• 之前一次checkpoint要求把这之前的所有WAL落盘到数据库文件中，所以不能在checkpoint时同时存在有写事务。
• 有了这些状态信息之后，不再要求将checkpoint之前的所有WAL落盘，对于还在进行的事务，只要将其信息保存到ATT以及DPT中即可，这些在进行事务的修改这一次checkpoint可以不进行落盘。

仍然以一个例子来说明这个流程。

如上图中：

• 事务T1：修改了页面P1，之后提交。
• 事务T2：修改了页面P2，还未提交之前就开始了checkpoint操作。
• 第一次checkpoint操作：在开始checkpoint时，系统中事务T2还在进行，P2为脏页面，于是ATT={T2}，以及DPT={P2}，于是这一次checkpoint操作，仅把已提交的事务T1的修改同步到了数据库文件上，即A=120。
• 继续到第二次checkpoint时，这时候事务T2已经完成，而事务T3还在进行，于是这一次checkpoint时，ATT={T3}，以及DPT={P3}，这样会把第一次checkpoint到第二次checkpoint之间的操作落盘，如何落盘呢？这时候会遍历这中间的WAL日志，来修改ATT和DPT这两个表，流程如下：
  • 第二次checkpoint开始的时候，ATT={T2}，以及DPT={P2}，这是上一次checkpoint记录下来的值。
  • 遍历两次checkpoint中间的所有WAL：
    • 完成的事务：从ATT表删除，同时从DPT中删除被该事务修改的页面。这个例子中，事务T2就是这样一个位于两次checkpoint之间且完成的事务，于是ATT={T2}修改为ATT={}，DPT={P2}修改为DPT={}
    • 开始的事务：将事务ID加入ATT表，当前被修改的页面编号加入DPT表中。在这个例子中，事务T3就是这样一个在第二次checkpoint时还在进行的事务，于是修改ATT={}为ATT={T3}，以及DPT={}为DPT={P3}。

可以看到，引入了ATT和DPT表之后，checkpoint操作带了状态， 这样就不要求checkpoint要等到所有事务都完成（比如这里的T2和T3）才能开始，因为记录了在进行的事务的状态。

但是这个改进还并未解决checkpoint时停止所有写事务的问题。原因在于，目前的checkpoint机制，是一个STW（Stop The World）的设计，一旦触发无法中断，下面的fuzzy checkpoint算法就针对这一点做了改进。

fuzzy checkpoint

fuzzy checkpoint算法主要有以下的重点：

• 对比之前的checkpoint流程，fuzzy checkpoint算法有两条相关的日志：
  • checkpoint-begin：标记着checkpoint操作的开始，在这次checkpoint操作成功之后，这条日志的LSN将保存到MasterRecord记录中。
  • checkpoint-end：标记着checkpoint操作的结束。
• ATT和DPT表：任何在checkpoint-begin之前开始但还未完成的事务ID以及脏页面会加入到这两个表中，但是任何在checkpoint-begin之后的不做记录。另外，对这两个表的内容是记录在checkpoint-end日志中的。

还是以一个例子来说明这个算法的流程：

• 事务T1：修改了页面P1，之后提交。
• 事务T2：修改了页面P2，还未提交之前就开始了checkpoint操作。
• 第一次checkpoint操作：在开始checkpoint时，系统中事务T2还在进行，P2为脏页面，于是ATT={T2}，以及DPT={P2}，于是这一次checkpoint-end日志，仅把已提交的事务T1的修改同步到了数据库文件上，即A=120。注意，事务T3在checkpoint-begin操作之后，所以并不会加入到这两个表中。
• 结束了第一次checkpoint操作之后，MasterRecord修改为checkpoint-begin操作的LSN。
• 继续到第二次checkpoint时，这时候事务T2已经完成，而事务T3还在进行，于是这一次checkpoint时，ATT={T3}，以及DPT={P3}，这样会把第一次checkpoint到第二次checkpoint之间的操作落盘，如何落盘呢？这时候会遍历这中间的WAL日志，来修改ATT和DPT这两个表，流程与上面大体一样，就不做解释了。

fuzzy-checkpoint操作之所以名为fuzzy（模糊），意思就是并不知道checkpoint操作何时结束，只知道何时开始，只需要在checkpoint-end结束的时候，把checkpoint-begin时计算的ATT，DPT内容一起写入即可。

可以看到，这个算法既不要求开始时所有写事务都结束，也不要求进行时停止所有写事务，极大提升了并发性能。

数据恢复流程

以上，已经完整的介绍了ARIES算法的核心，最后来谈谈数据恢复的流程。

数据恢复分为以下三个步骤：

• 数据分析阶段
• 重做。
• 撤销。

下面来逐个讲解这三个阶段的工作。

数据分析阶段

找到最近的一次checkpoint日志，分析出在这之后成功和失败的事务，从这条日志之后开始构建ATT，DPT表内容：

• MasterRecord中保存了最近一次成功的checkpoint-begin的LSN，从这条日志之后开始扫描。
• 扫描过程中，针对不同类型的WAL处理如下：
  • 修改：将对应事务的ID加入ATT表中，设置状态为Undo，意为需要撤销这个事务的操作。同时，这个修改操作修改到的页面编号，如果不在DPT表，就需要加入到DPT表中，同时设置这个页面的recLSN为这个操作的LSN。
  • 事务提交：对应事务的ID加入ATT表中，同时修改状态为Commit，意为需要这个事务的状态为提交。
  • CLR、checkpoint-end日志：忽略，这几类日志并不影响ATT和DPT表的构建。

在数据分析阶段完毕之后：

• ATT表：保存了在崩溃时所有还在活跃的事务以及其状态（需要撤销或者已经提交）。
• DPT表：保存了在崩溃时所有的脏页面编号。

有了这些信息，就能进行重做和撤销操作。

Redo（重做）阶段

第一步扫描完毕之后，DPT表中存储了所有崩溃时的脏页面编号，同时每个脏页面也有一条recLSN记录，存储的是这个页面被修改时的最小LSN编号，从这些编号中选出编号最小的那条日志，从这条日志开始做重放操作，但并不是所有日志都需要重放，满足以下条件的就不需要重放：

• 修改操作，同时这个修改操作修改的页面编号不在DPT表中，或者：
• 虽然页面编号在DPT表中，但是这条记录的LSN小于DPT中记录的该页面的recLSN，这说明这个修改的效果已经在checkpoint操作中体现，不需要重放了。

Undo（撤销）阶段

对于所有在ATT表中，且状态为Undo状态的事务，从后往前进行回滚操作（ATT表中每个事务保存了lastLSN，可以用这个字段快速定位这个事务的最后一个日志LSN），每回滚一条日志还需要补上对应的CLR日志。

例子

仍然以一个例子来说明数据恢复流程：

上图中：

• MasterRecord保存的是LSN为1的checkpoint操作，于是从这条日志开始逐条解析WAL日志，构建ATT和DPT表。
• 在这个checkpoint流程中，T1和T2事务还在活跃，分析结果如下：
  • ATT表（表中每个元素的格式为(事务编号，状态(U:Undo,C:cOMMIT),lastLSN)）：
    • 事务T1：因为事务T1最后提交了，因此值为（T1,C,4），表示T1的状态为已提交，且lastLSN=4。
    • 事务T2：事务T2没有提交，因此值为（T2,U,7），表示T1的状态为已提交，且lastLSN=7。
  • DPT表（表中每个元素的格式为(页面编号,recLSN)）：
    • (P1,4)：表示页面P1在LSN=4处修改。
    • (P2,6)：页面P2有两个地方被修改（6、7），但是只需要保存第一处就好了。
• 有了ATT和DPT数据之后，可以开始重做和撤销流程了：
  • 重做：这个例子中不存在不需要重做的日志，不再阐述。
  • 撤销：可以看到事务T2没有完成，因此需要撤销这个事务的操作，并且补上对应的CLR日志。由于ATT表中，保存的T2事务的lastLSN为7，因此从这条日志开始进行撤销。

数据恢复完成之后，补齐了CLR日志如下图所示：

总结

• ARIES算法在每条WAL日志中引入LSN，有了这个变量之后：

  • 可以把同一个事务的多个操作，在逻辑上串联起来。
  • 可以知道每个页面的最后一次修改。
  • 可以知道数据库文件的最后一次checkpoint操作。

  简而言之，LSN引入之后，给后面处理撤销操作、checkpoint、恢复操作都提供了基石。

• CLR日志是针对撤销（Undo）操作的日志。

• checkpoint操作引入ATT和DPT表用于保存状态，解决了两个问题：

  • 不再要求在checkpoint开始时要完成所有写事务。
  • 写事务和checkpoint可以并发进行。

参考资料

ARIES论文非常长，初看很难看，实际我到现在为止也不能说通读过一遍。更多的都是参考了CMU 15-445/645 :: Intro to Database Systems (Fall 2021)这门课程的讲解，这门课专门用了两节课讲解相关的内容，其实就是这系列博客的上下两篇的内容：

• Lecture #19: Logging Protocols + Schemes
  • Slide
  • Video
• Lecture #20: Crash Recovery Algorithms
  • Silde
  • Video

如果觉得上面的slide和video还是看不懂（我就没有全看懂），B站上有人用中文讲解了一遍：

• 19-数据库日志 [中文讲解] CMU-15445 数据库内核_哔哩哔哩_bilibili
• 20-数据库恢复 [中文讲解] CMU-15445 数据库内核_哔哩哔哩_bilibili

最后，网上还找到了演示ARIES算法原理的前端页面，可以自己一步一步实验理解：

ARIES