ARIES

经过前文的论述，本文着重介绍了Crash Recovery模块的功能和原理。虽然用记录redo log个undo log可以基本满足Atomicity和Durability，但是这种机制还是存在一些问题的：

Crash Recovery过程中需要扫描整个redo log，导致数据库恢复过程耗时太大。同时，redo log/undo log会越积越多，浪费磁盘空间，虽然可以用checkpoint来解决，但是checkpoint时刻会强制刷盘（刷日志和脏页）、禁写，导致数据库的写停顿。

Aries也是一种基于WAL（write ahead log）的Recovery算法，和一般的传统算法相比，Aries允许更细粒度的锁（比如B+索引中允许行级封锁而不是页级封锁）、更快的Recovery时间、支持物理逻辑日志（Physiological log）和Fuzzy checkpoints（不会停顿事务）等。Aries还拥有很多优点，当然，这也是以它的复杂性为代价的

Aries使用WAL预写日志来保证事务的Atomicity和Durability，WAL的刷新策略（steal/no-force）：

所有的日志记录必须在它对应的行数据页被写入磁盘之前写入稳定存储（保证Atomicity）。

所有的日志记录必须在其所属的事务提交（commit）之前写入稳定存储（保证Durability）。

image.png

需要额外添加的属性

image.png
image.png

除了上述这些 每个LOG 都会有自己的一个LSN，这个LSN 会更新PAGE LSN， 当TXN修改了一个这个PAGE的RECORD时。

那么当TXN 把所有的LOG刷到自盘的时候，会更新内存里的FLUSHED LSN 。

当事务提交的时候要做什么呢？

首先写一个COMMIT 的LOG 去WAL
然后所有到COMMIT的LOG之前TXN的所有LOG刷入磁盘
完成后，写一个TXN-END LOG。这个可以不用立刻被刷入磁盘。

image.png
image.png

当事务ABORT的时候要做什么呢？

为了解决ABORT的问题，我们需要在LOG的属性上再添加一个PREV LSN。
现在一个LOG 会有一个当前的LSN，还有记录前一个LSN。

image.png image.png

为了解决UNDO 到一半又CRASH的问题，我们还需要加一个CLR 的LOG

这个CLR主要记录了哪些LOG 已经被UNDO了，他会有一个UNDO NEXT的指针，表示下一个需要UNDO的是什么

image.png

至于为啥ATT 和 DPT是这个状态，小伙伴需要先看到后面理解了整个ARIES再回过头来理解

image.png

ABORT 的算法
写一个CLR LOG，就是回滚每个LOG的操作，成功了
当最后写一个TXN - END的LOG

CLR 如何防止ABORT到一半又CRASH

image.png

上述就是基本局面，我们可以看到T1已经TX END了。那么ATT里有的是T2 和 T3

随后在UNDO的时候又CRASH了

image.png

但是T3已经END了。而且T2的第一个UNDO操作也被CLR记录了。

image.png
最后我们就可以依据T2的CLR直接锁定要LSN为20的记录 就是下一个需要UNDO的操作。

那么UNDO时CRASH解决了，ARIES算法另2个阶段 REDO 和 ANYLASIS时CRASH怎么办?

image.png

为啥要FUZZY CHECKPOINT

为了解决记CHECK POINT时不用停顿和等待。引入了FUZZY CHECKPOINT

基于这个CHECKPOINT，我们需要加2个数据结构，一个是ATT，一个是DPT

ATT

image.png

DPT

image.png

DPT的REC LSN记录的是第一个引起该PAGE变脏的LOG的LSN。

image.png

所以CHECKPOINT-BEGIN 之后发生的操作都不会再CHECKPOINT-END里的TABLE体现。

有了上述知识，最后就开始讲ARIES算法了。

ARIES

image.png

LOG：

• LSN:Log Sequence Number，一个本地单调递增的序号，唯一的标识一条log record

• PreLSN: 属于同一个事务的log record，和面的log record会使用PreLSN指向前一条log record，组成逻辑上的单链表

• XID:事务的id

• Type: log record的类型，目前主要有Update、Commit、Abort、End (signifies end of commit or abort)、Compensation Log Records (CLRs)、CheckPoint(begin_checkpoint、end_checkpoint)。

• PageID:唯一的表示一个Page

• Length:Page的长度

• Offset: Page在磁盘的位置、偏移

• BeforeImage：修改前的值，等价于undo log

• AfterImage：修改后的值，等价于redo log

• undoNextLSN：只有CLR类型的log会使用这个字段，用于防止重复undo

Transaction Table：

• XID: 事务的id
• Statius：事务的状态，主要有running、commited、aborted
• LastLSN：该事务的最后一条log record序号

Dirty Page Table ：

• PageID:唯一的表示一个Page
• RecLSN：第一个导致该Page变脏（Dirty）的log record序号

Checkpoint：

Aries的checkpoint log record主要包含以下内容：

• Transaction Table：执行Checkpoint时刻对应的Transaction Table
• Dirty Page Table：执行Checkpoint时刻对应的Transaction Table

Aries的checkpoint和传统意义上的checkpoint不太一样。Aries使用fuzzy checkpoint，也就是在执行checkpoint的时刻，他并不要求将buffer中的脏页（Dirty Page）刷新到Disk，因此也就不会造成其它事务的停顿，提升性能明显。因此它就需要记录此时的Transaction Table和Dirty Page Table，以便在执行Recovery时可以获取当时的事务运行状态，并加速Recovery。因此，通常数据库中都会有一个后台任务周期性的对脏页进行flush，这样可以缩短Recovery的时间。

image

DB:

• **PageID: **唯一的表示一个Page
• pageLSN：该page上对应的最后一条被flush到stable storage上的log record序号

Matser record:

• LastCheckPoint: 指向了最近一次CheckPoint log record的序号

为了更直观的表达它们之间的关系，我特意按照它们的存储位置不同画了图4。

image

图4 Aries算法数据结构关系图

Aries Recovery算法

Aries的Recovery主要会分为三个阶段进行：

image.png

• Analysis阶段：该阶段会先使用最后一次的checkpoint（更确切的说是用end_checkpoint record log，可以通过master record找到）来恢复状态（就是恢复Transaction Table和Dirty Page Table）。从begin_checkpoint log record开始，正向（forward）扫描，如果遇到end log record，那么就把改log record对应的事务从Transaction Table中删除。对于其他类型的log record，就把该log record对应的事务加入到Transaction Table中，并把LastLSN设置为改log record的LSN，status设置为U（表示undo）,如果是commit log record，则把改为C（表示commit）。同时，如果这是一个update log record，并且该log record更新的Page没有在Dirty Page Table中，就把该Page加入到Dirty Page Table，并将RecLSN设置为该log record的LSN。在Analysis阶段结束时，Transaction Table中包含了在Crash发生那一刻所有正在运行（active）的事务。Dirty Page Table中包含了一些可能还没有被flush到磁盘的脏页（dirty page）。

• Redo阶段：
  

  image.png

该阶段会使用Analysis阶段产生的信息来重演历史（repeat History），以求可以将数据库恢复到Crash时的一致性状态。根据Analysis阶段恢复的Dirty Page Table信息，找出最小的recLSN，并从该recLSN对应的log record开始正向（forward）扫描，对每一个update和CLR类型的log record，重做（redo）该log record的动作（Action），即使这个事务之前已经abort了 。以下有两种情况会导致一个log record不会被redo，一是被该log record影响的Page不在Dirty Page Table中，二是被影响的Page对应的pageLSN（可以从磁盘读取）已经大于等于该log record的的LSN。三是如果此时该Page对应的RecLSN大于该log record的LSN，那么该log也不用执行redo操作。

image.png

每当成功将一个log record应用到磁盘上的Page后，就更新Page的pageLSN更新为这条log record的LSN。注意，这个阶段的redo操作仍然是不要求force flush磁盘的。在redo的最后阶段，会为status为C的事务写一个end log record，并将其从Transaction Table中删除。

• Undo阶段：
  image.png

经过Analysis和Redo阶段处理后，所有需要Undo的事务都被记录在了Transaction Table中（包括了Crash时正在运行或者回滚的事务，将此类事务称为loser）。假设ToUndo是一个集合，里面包含了此时Transaction Table中所有事务的lastLSN，接下来会将进入一个循环，该循环里，首先会从ToUndo里面取出最大的那个lastLSN（并将其从ToUndo中移除），如果这个LSN对应的log record是CLR并且undonextLSN==NULL，就为这个事务写一个end log record。否则，如果是一个CLR log record并且undonextLSN!=NULL，那么就将undonextLSN加入到ToUndo中。如果log record不是CLR，而是一个update，就对这个update执行undo操作，并写一个CLR log record，同时会将该update log record的prevLSN加入ToUndo中。至此，如果ToUndo不为空，就返回到循环的开始。直到ToUndo为空，循环结束。这路需要注意，CLR类似的log是绝不对不会重复执行Undo的，通过这种方式可以保证Undo只执行一次（幂等性保证），因此即使在undo过程中即使再次发生Crash，系统也可以正常Recovery。

整个过程如图5所示。

image

图5 Recovery的三个阶段

Aries 核心思想

• WAL（write ahead log）采用steal/no-force缓冲管理策略

• fuzzy checkpoints，不需要force flush dirty page，不会停顿事务，相当于持有checkpoint时事务状态的一个快照

• 可以从最早的dirty page进行redo任何log。对loser事务进行undo，Aries会有机制保持redo和undo的幂等性

• CLR的加入是为了防止在undo的过程中再次发生Crash，用来保证undo的幂等性

• 采用Physiological redo log和Logical undo log，支持嵌套的顶层动作。这里的Physical log表示Log记录的是Bit的变化，而Logical log记录的是触发变化的operation和arguments。它们之间的其他区别本文不再赘述。

Aries Example

图6为例，一共三个事务T1、T2、T3同时运行，W(PX)表示事务对页PX进行写操作（具体写入了什么值此处可以不用考虑）。CP表示checkpoint，图1中可以看到，在T1对P2执行了写操作之后，系统执行了一次CP。在T1的W(P3)和T2的W(P4)之间，有一次脏页的flush。最后，在T3执行完W(P5)之后，系统Crash。

image

图6 实例中的事务运行图

Crash时刻，Aries的数据结构的视图如图7所示。

image

图7 Crash时刻视图

假设系统稍后restart，会进入Aries的三个阶段。

Analysis阶段：

首先，根据存储在磁盘上的master record找到最近的checkpoint位置，此处就是LSN为3的log record。然后从LSN为4开始，forword扫描。（注意，此时的Transaction table和Dirty table是从checkpoint拿到的初始状态）

image

LSN为4的log是T1的update日志，将T1记录到Transaction table中。同时，由于该log是第一次更新P3，因此还需要将P3加入到Dirty table中。接下来扫描LSN为5的日志。该日志是T2的一个update记录，并且首次更新了P4。

image

对LSN为5的日志进行分析后，会将T2加入到Tansaction table中，并将P4加入到Dirty table中，如下图所示。接下来准备扫描LSN为6的日志，其原理和前面论述的一致。

image

为了加快描述，本文假设分析阶段完成（已经分析完了LSN为10的日志），此时的整个系统视图如下所示。Transantion table中只剩下T3是loser，Dirty page table中有P1、P2、P3、P4和P5脏页，并分别包含了它们的recLSN（第一个导致它们变dirty的LSN）。至此，Analysis阶段完成，接下来进入redo阶段。

image

REDO阶段：

该阶段，首先会从Dirty page table中找出最小的recLSN，也就是1开始进行forword扫描。首先会对LSN为1的log进行redo action操作。由于磁盘上，P1的PageLSN为1，因此这条log之前已经被flush过了，所以该条log不用执行redo操作。

image

接下来要redo LSN为2的log，同样，磁盘上P2的PageLSN为2，因此该条log也不需要执行redo操作。

image

接下来要redo LSN为4的log（提过LSN为3的checkpoint），同样，磁盘上P3的PageLSN为2，因此该条log也不需要执行redo操作。

image

接下来要redo LSN为5的log，同样，磁盘上P4的PageLSN为NULL，因此该条log需要执行redo操作。

image

跳过T1的end log，继续redo LSN为7的log，由于磁盘上P2的PageLSN为2，因此该条log需要执行redo，同时，执行完成之后需要将P2加入到Dirty page table中，并将其recLSN设置为7。

image

继续redo LSN为8的log，由于磁盘上P1的PageLSN为1，因此该条log需要执行redo，同时，执行完成之后需要将P1加入到Dirty page table中，并将其recLSN设置为8。

image

跳过LSN为9的end log，LSN为10的log是T3的update，其更新的P5此时对应的PageLSN为NULL，因此这条log需要执行redo。至此，最后一条log也redo完毕。接下来将进入undo 阶段。

image

Undo阶段：

经过Analysis和Redo阶段后，现在Transaction table里面还剩T3这个loser事务，对应的LastLSN为10，根据算法，设置toUndo={10}。

image

从toUndo中取出最大的那个LastLSN，也就是10， 开始对LSN为10的log执行undo，undo完成之后，还需要新写一个CLR log record（LSN为11），并将其undoNextLSN设置为7（也就是LSN为10的log对应的PreLSN）。最后再把该log的PreLSN加入到toUndo中，因此此时toUndo={7} 。然后进行下一次循环。

image

由于toUndo不为空，因此，依然从toUndo取出最大的LastLSN，为7， 对LSN为7的log进行undo操作，之后也会为其新写一个CLR log record。不同的是，由于LSN为7的log是事务T3的第一条log，因此它的PreLSN为NULL，因此它对应的undoNextLSN也为NULL。PreLSN为NULL，因此也就不需要再加入toUndo里了，而此时toUndo={} ,集合为空。循环结束。

image

对于CLR的undoNextLSN为NULL的情况 ，还会为其对应的事务写一个end log record，表示该事务已经结束。这样在下次revovery的时候就无需再次undo了。

image