ARIES数据库恢复算法


Algorithms for Recovery and Isolation Exploiting Semantics(ARIES) 是一种针对非强制(no-force,即当事务提交时不强制立刻写入记录所在的磁盘对象)可窃用(steal,即缓存管理器可强制将任意page刷入磁盘)数据库的恢复算法。ARIES的发明者的描述是,ARIES是一种使用写前日志(WAL)的支持细粒度锁和部分回滚的事务恢复方法。

1. ARIES 三原则

先看看ARIES的三个原则:

2. WAL

为什么要no-force?为什么不直接去修改磁盘上存储的对应的对象,而是先去写WAL呢?我们先看看WAL这个更大的概念。

WAL是一种提供ACID中的原子性和持久性的机制。ACID忘掉的可以点链接复习一下,题外话,以前觉得原子性/atomicity的叫法令人摸不着头脑,这个词和atom(原子)同源自古希腊语一个表示“不可再分”的哲学概念的词,所以原子性就表示一个事务的一系列操作是不可分的一个整体。

WAL除了可以保证原子性,也能提升写性能。因为数据库文件分散在磁盘中,一般场景下update将造成许多随机I/O,造成性能极差,但以追加形式写log文件则是顺序I/O,比随机I/O性能高很多。

Log的形式分为undo(回滚)和redo(重做)两种。Undo log记录事务修改前状态,根据undo log可以将该log造成的更改撤销;Redo log记录事务修改后状态,根据redo log,可以将该log造成的更改重做。一般同时使用两种log,MySQL InnoDB使用的是redo log,磁盘中的ib_logfile0ib_logfile1就是InnoDB的redo log file。

因为undo / redo log使数据库可以在事务当中恢复到事务前状态,所以说WAL可以保证原子性。

WAL不仅用在数据库中,在文件系统中类似的机制叫journaling,将来有机会可以写写Ceph的Filestore的journal机制。

3. 日志

每个log条目都按序列号(Log Sequence Number,LSN)顺序排列的。为获取写log必要的信息,我们需要两个数据结构:

脏页表记录了所有被修改的胆识还未刷入磁盘的脏页和造成脏页的第一个序列号。事务表记录了所有正在进行的事务和它们写入的最后一条log的序列号。

我们以<LSN,事务ID,页ID,Redo,Undo,前一SN>的形式记录log。其中前一LSN指向这个事务产生的前一条log,当事务被取消,就可以用这一项从后往前遍历来回滚。

恢复和回滚未完成的事务时会写补偿log(Compensation Log Record, CLR)来记录被回滚的操作。CLR的一般形式是<LSN,事务ID,页ID,重做,前一SN>

4. 恢复

恢复的三个阶段:

  1. 分析,从logfile里面计算所有需要的信息
  2. Redo,将数据库恢复到崩溃现场,包括崩溃时还未提交的事务
  3. Undo,将未提交的事务回滚,恢复一致性

4.1 分析

分析过程中,buffer中的脏页和崩溃时正在进行的事务将被从log中识别,DPT和TT恢复到崩溃时状态,具体过程如下。

我们从头或者从checkpoint遍历logfile,把找到的Begin Transaction的记录加入TT,若遇到对应的End Log记录则证明该事务已完成,再从TT删除。每个事务产生的最后一条log的LSN也会被记录。

遍历同时,我们将找到的DPT中没有的脏页插入DPT。但是这些“脏页“可能并非未刷入数据库文件,我们并没有去进行校验。

4.2 重做

目的是将已完成的事务刷入磁盘。

首先我们从DPT中得出一个脏页的最小LSN(下记为minLSN),即最早令该页变脏的log。从该log开始重做直到崩溃状态。

遍历log时,检查每条记录是否该记录修改的页P在DPT中,若不在,则证明数据库该数据已经落盘,我们不必再关心了。如果P存在于DPT中,需要检查是否minLSN小于log中的SN(下记为recLSN),

4.3 回滚

回滚阶段log被从后往前遍历,未完成的事务将被回滚,具体的操作如下。

对TT中的每一项,使用log中的前一LSN项从后往前遍历。对每条记录执行回滚操作,即Undo项,然后在log中写一个CLR。如果遇到Begin Transaction log,为该事务写一条End Log

写CLR是为了恢复从恢复阶段的崩溃,因为恢复的时间比较长,所以这种情况并非少见,恢复从恢复阶段的崩溃时,CLR在分析阶段会被读取,然后在重做阶段被重做。

5. 检查点

回顾恢复的分析阶段,我们需要从头读取logfile来将DPT和TT恢复到崩溃时状态,为了防止总是需要从头读取,我们定时将DPT和TT写入logfile,形成一个检查点(checkpoint)。这样我们就可以只从检查点开始恢复DPT和TT。

建立检查点需要一定时间,为了在这段时间里需要采取一定措施维持一致性。静态检查点完全不允许写入。模糊检查点建立两条log记录,开始时记录一条Fuzzy Log Starts Here,到数据准备完毕,中间还可以正常写入log。InnoDB中fuzzy checkpoint的实现方式是分小批将脏页落盘。

References