ARIES数据库恢复算法

Algorithms for Recovery and Isolation Exploiting Semantics(ARIES) 是一种针对非强制(no-force,即当事务提交时不强制立刻写入记录所在的磁盘对象)可窃用(steal,即缓存管理器可强制将任意page刷入磁盘)数据库的恢复算法。ARIES的发明者的描述是,ARIES是一种使用写前日志(WAL)的支持细粒度锁和部分回滚的事务恢复方法。 1. ARIES 三原则 先看看ARIES的三个原则: 写前日志(write-ahead logging,WAL):一个对象的任何修改需要先记录在log中,log在对对象的修改写入磁盘前必须写入到稳定的存储中 Redo时重复历史:崩溃重启时,ARIES分析崩溃前的行为,并把系统恢复到崩溃前的状态,然后undo崩溃时未完成的事务 Undo时记录修改:undo事务时所作的修改写入log,防止不断重启时重复这些操作 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_logfile0, ib_logfile1就是InnoDB的redo log file。 因为undo / redo log使数据库可以在事务当中恢复到事务前状态,所以说WAL可以保证原子性。 WAL不仅用在数据库中,在文件系统中类似的机制叫journaling,将来有机会可以写写Ceph的Filestore的journal机制。 3. 日志 每个log条目都按序列号(Log Sequence Number,LSN)顺序排列的。为获取写log必要的信息,我们需要两个数据结构: 脏页表(dirty page table, DPT) 事务表(transaction table, TT) 脏页表记录了所有被修改的胆识还未刷入磁盘的脏页和造成脏页的第一个序列号。事务表记录了所有正在进行的事务和它们写入的最后一条log的序列号。 我们以<LSN,事务ID,页ID,Redo,Undo,前一SN>的形式记录log。其中前一LSN指向这个事务产生的前一条log,当事务被取消,就可以用这一项从后往前遍历来回滚。 恢复和回滚未完成的事务时会写补偿log(Compensation Log Record, CLR)来记录被回滚的操作。CLR的一般形式是<LSN,事务ID,页ID,重做,前一SN>。 4. 恢复 恢复的三个阶段: 分析,从logfile里面计算所有需要的信息 Redo,将数据库恢复到崩溃现场,包括崩溃时还未提交的事务 Undo,将未提交的事务回滚,恢复一致性 4.1 分析 分析过程中,buffer中的脏页和崩溃时正在进行的事务将被从log中识别,DPT和TT恢复到崩溃时状态,具体过程如下。
Read more...