ARIES Recovery 算法

该算法在1992的时候被提出，几乎所有db都用ARIES来做recovery，或着是它的变种，可见其地位。ARIES的核心思想如下。

• Write-Ahead Logging

  在内存中的所有修改，都要以log的形式在data之前刷到磁盘

• Redo

  重启的时候，对所有已提交的事务做redo

• undo

  重启的时候，对所有未提交的事务做undo

ARIES的前提是该数据库是STEAL + NO-FORSE。否则事情就简单了，不需要用ARIES这么复杂。

• STEAl

  允许未提交的事务将dirty data刷到磁盘

• NO-FORSE

  在事务提交之前，不强制将所有dirty data刷到磁盘

可见最简单的实现当然是NO-STEAL + FORSE，也就不需要redo和undo了，但是性能低。而且当机器的内存不足以支撑事务所需要的大小时，也不可行。

Write-Ahead Logging

如之前所说，为了解决断电以后的一致性问题。在内存中的所有修改，都要以log的形式在data之前刷到磁盘。在事务开始之前写一个 record到log。在事务提交后，写一个 record到log，注意需要保证该事务的所有log在结果返回给应用之前flush到磁盘。若事务中间abort的话，则写一个 record到log。有如下三种log。

• undo log: record中保存旧值，db是STEAL才需要undo。或者用来做abort之后的撤销。
• redo log: record中保存新值，db是NO-FORSE才需要redo
• undo-redo log (ARIES属于这一种)

最简单的一条log的记录为。当然现实比这复杂多了。

Log Sequence Number

为了更方便的追踪，现在每一条log record都会有一个对应的全局逻辑序号LSN。整个DB各个地方都会用到。

• flushedLSN，存在memory。表示磁盘上最新的log record的LSN。
• pageLSN，内嵌在page里。代表最新的对这个page update的log LSN。（每次对page update都要更新）
• recLSN ， 也是内嵌在page里。与pageLSN相反，代表最旧的对这个page update的log LSN。（只更新一次）
• lastLSN，存在memory，每个事务都会维护。该事务最新的一个操作记录的LSN。
• MasterRecord，存在disk。指向最新的一个checkpoint。

只有当flushLSN >= pageLSN时，相关的page才能刷到磁盘。表示对这个page所做的所有log都已经落盘了。

Transaction Operation

• txn start

  1. 写一条 记录

• txn commit

  1. 写一条 记录
  2. 将log刷到磁盘
  3. 写一条 记录。代表这个事务已经正式完成了。但page是否已经刷到磁盘是确定。看到 记录即可以对该事务做undo。

• txn abort

  1. 写一条 记录。
  2. 反向扫描log，对该事务做undo。可以用prevLSN加速。注意的是对每次更新都需要在log里写一条CLR。防止在undo的db崩溃。
  3. 结束后写一条 记录

  Compensation Log Record(CLR)的格式与普通log一样，除了多加一条undo_next_lsn。

下面是一次abort的示意图。

Checkpoint

WAL有一个显著的问题，随着系统运行时间越长，log会变得越来越长，导致每次crash之后，dbms需要对整个log进行恢复操作。所以dbms定期会做checkpoint，将当前在内存中的数据全部刷到磁盘，则下次恢复只需从最新的checkpoint开始即可。

Blocking Checkpoint

最Basic的版本，也是性能最差的版本

• 停止接受开启新的事务。并等待还在运行中的事务结束。
• flush所有log和dirty page
• 写一条 记录到log

Fuzzy Checkpoint

ARIES中使用的版本。允许接受新的事务，并且不需要等待还在运行中的事务结束。

为了达到这两个目的，需要维护两张表来保证。

• Active Transaction Table (ATT)

  1. txn_id: 当前正在运行的事务
  2. status：事务的状态（Running，Committing，Undo candidate）
  3. lastLSN: 事务最新一次update的LSN

  ARIES需要对ATT做undo

• Dirty Page Table (DPT)

  1. 所有未提交事务的dirty page。
  2. page中包含一个recLSN：第一次让该page变dirty的LSN

  ARIES需要对DPT做redo

Fuzzy Checkpoint有两条log record需要添加。

2. ：需要包含ATT和DPT。ARIES需要根据这两个信息做恢复。

ARIES

ARIES总共做如下三个步骤

1. Analysis

   从最新一个checkpoint开始，从前往后读，确定ATT和DPT。

   • 根据MasterRecord找到最新的一个Checkpoint
   • 如果发现TXN-END，将该事务从ATT中删去。（该事务的所有log都刷到磁盘，不需要undo该事务）
   • 将其他record中事务加到ATT
   • 如果是update record。若当前page不在DPT，则加到DPT中，并将recLSN设为LSN（只更新这一次）。

2. Redo

   从某个指定位置（DPT中最小的recLSN）开始，从前往后扫描，对已提交的事务（NO-FORSE， DPT）进行redo。

   • 从DPT找到一个最小的recLSN。（最远的一条记录使DPT中某个page dirty）
   • 从该位置往前扫描，对每条update record或者CLR，进行redo，除非满足下面其中一个条件可跳过：
     1. 该page不在DPT中。
     2. 该page在DPT中，但是这条update record的LSN比该page的recLSN大。（说明使该page变dirty的record还没出现，在recLSN之前的数据都已经落盘了）
     3. 该page的pageLSN大于当前record的LSN。（该page是从disk中读上来的，说明pageLSN之前的操作都已经落盘了，不需要在redo）

3. Undo

   从后往前扫描，对未提交的事务（STEAL, ATT）进行undo

   • 将所有ATT中标志状态为U的事务做undo
   • 从后往前扫描，每次更新也需要写CLR。