ARIES -- A Transaction Recovery Method


ARIES: A Transaction Recovery Method Supporting Fine-Franularity Locking and Partial Rollbacks Using Write-Ahead Logging

引言

ARIES(Algorithm for Recovery and Isolation Exploiting Semantics,,这篇文章应该是WAL里面最有名的一篇了,发表在1992年,现在很多数据库WAL的设计上都有它的影子。后续的对它的改进和各种的变体也很多。另外,这篇论文长达69页。还有在这篇Paper注意Latch和Lock描述的不同的含义。ARIES有以下的几个特点: 1. 操作之前先在Log中持久化相关的数据,这些log都是只追加的,从来不会修改;2. ‘No-Force’ policy,由于有了Log,也就不需要立即就将更新之后的page持久化;3. ‘Steal’ policy,没有提交的事务更新的pages也能写入到磁盘上面(这个是为了支持”很大”的事务),因为有undo log,这也是可以恢复的;4. 使用LSN (Log Sequence Numbers)来保证标记log,page是基本的管理单位。这Paper中包含了大量的细节信息,对应实际去实现这样的一个系统非常有参考价值。

相关的数据接口

在一个log record中,存在一下的字段:

* LSN,唯一地表示一个log record,单调递增。在ARIES中,这个字段比不要实际保存到log记录中;
* Type,操作的类型,比如compensation,update,prepare等;
* TransID,一个事务的标示符,如果存在,则写入到log record中;
* PrevLSN,同一个事务中写入的上一条记录的LSN。一个事务可能写入多个log,它们并不一定是连续的,这个时候就需要这个字段。在非事务的log和一个事务的第一条的log中,这个字段被置为0。
* PageID,只存在与compensation、update类型的记录中,标示那一个数据page被修改。一般包含了table和page number两部分的信息;
* UndoNxtLSN,只在CLRs(compensation log record)的log中出现,表示了一个事务会滚过程中下一条将要被处理的log的LSN;
Data,数据部分。CLR类型只需要记录redo的信息,因为它们不会被undo。

ARIES的log可能包含了redo或者是undo的信息,也可能同时包含redo和undo的信息(redo-only, undo-only, redo-undo), Compensation Log Record (CLR)记录是redo的时候的记录,记录了redo的进度。另外在数据page上记录了一个page_LSN字段,表示应用在这个page上面修改操作的最新的LSN。ARIES对buffer pool的实现只有这一个强制的要求,这样就给了buffer pool实现很大的灵活性。 一个table叫做transaction table在重启恢复的时候会记录活跃事务的状态。在分析扫描的阶段(从最近的checkpoint开始)初始化。因为undo操作的时候会改变状态,所以这个表中一些记录就会更新。如果在恢复的时候写入了checkpoint,这个表也会记录这个checkpoint的信息。这个表在正常操作的时候也会被transaction manager记录事务的信息,存在下面的一些字段: TransID,事务的id;State,事务的提交状态,比如prepared(P),or unprepared(U);LastLSN,这个事务产生的最近的log的LSN;UndoNxtLSN,一个事务会滚过程中下一条将要被处理的log的LSN,此外,对于不可undo且不是CLR的操作等的log还要一些特殊的地方:

If the most recent log record written or seen for this transaction is an undoable non-CLR log record, then this field’s value will be set to LastLSN.
If that most recent log record is a CLR, then this field’s value is set to the UndoNxtLSN value from that CLR.

此外,dirty pages table是用来记录目前的脏的数据page的,在这个page被持久化之后,这个记录就会从中删除。这个table在数据库恢复的时候也会用到。这个table中的每个entry有两个字段:PageID 和 RecLSN,即recovery LSN。当一个nodirty的page要被更新的时候,下一个会写入的LSN,以及这个PageID会被记录到这个dirty pages table中。这个RecLSN代表来这Page从Log中哪一个位置开始被更新。也就是说,持久化保存的这个Page的版本应用Log到的位置。在Diry Page持久化之后,会将对应的数据从table中移除。这个table的内容会包含了一个checkpoint的记录中。在恢复的时候,这个table从最近的一个checkpoints的记录中恢复,在恢复的分析步骤中会被更新。RecLSN作为Redo开始的一个标记。这个table在MySQL中实现为一个list,并且会根据这个RecLSN排序。

正常处理流程

更新操作

正常的操作下,一个事务可能继续向前运行,也可能由于多种原因部分or全部回滚。在更新操作的时候,如果lock的粒度是一条记录,在锁住了这条记录之后,这条记录所在的data page也就会被固定在buffer pool之中,并被加上X模式的latch。在log写入完成之后,就会更新这个page的page-LSN字段,然后释放latch并解除在buffer pool中的固定。这个Page Latch在写日志的时候也必须一直持有,用来保证写入日志的顺序和应用在这个page上面的更新操作的顺序一致。加上Page Latch也是为了保障在读取和更新(insert, update)操作的时候这个page的一致性,这里读取的时候加的是S mode的latch,而更新则是X mode。这里操作的另外的几个点,

  • 在一个索引上面进行一些操作的时候,在这里data page的latch是不用获取的。而且在这里最多同时获取两个data page的latchs(这个与使用的B-tree的并发控制协议相关,可以参看相关的paper),这样也就意味着在两个不同的事务修改一个特定的data page和一个特定的index page的顺序可能是不同的。这里ARIES使用的是latch来保持物理上的一致性,这里不同于System R之类的使用的lock的方式。在后者中,一个data page上面的lock只有在一个RSS (data manager)调用的时候被释放,而一个RSS调用会处理相关的数据更新和相关的索引,这里有可能产生deadlock的问题。
  • 在ARIES中,一个事务可能会有多条的log。举一个例子,一个操作可能包含了一个undo-only的日志记录和一个redo-only的日志记录,这里要满足两个条件:1. Undo-only的日志必须在rodo-only日志之前写入,2. page_LSN保存的是redo-only日志的LSN。设置这两个条件的目的是保证在任何情况下系统都能正确恢复。
  • ……

为了支持灵活的rollback,ARIES使用了savepoint的机制。在一个事务的执行过程中,savepoint可以被创建,而且在一个save point创建之后,有执行了一部分的情况下,系统可以rollback到前面的savepoint的位置。并且在回滚到一个savepoint之后,事务可以向前继续执行。创建一个savepoint的时候,最好写入log的LSN被记录为SaveLSN,事务一开始记录的savepoint的时候这个值被记录为0。在回滚操作的时候,将log倒序undo来实现回滚。每一个log undo完成的时候,会写入一条CLR日志,用于处理在redo的时候又发生故障。回滚的时候CLR记录不会被undone,也会忽略redo-only的日志记录。 假设系统是使用一些两阶段提交的协议,一个prepare的记录会被记录下来,包含了update-type locks 的信息,比如IX、X和SIX等。将locks的信息保存到日志中保证了,如果系统在故障之后进行一个模糊的状态,这些lock可以重新被获取。在prepare记录被写入之后,读类型的lock就可以被释放了。Morething about rollback….

Checkpoints

Checkpoint是为了减少在recovery操作的时候需要处理的工作量的必要手段。ARIES中会周期性地创建checkpoint。Checkpint可以被异步地创建,通过写入一个begin-chkpt记录来初始化一个fuzzy checkpoint,一个end–chkpt 记录会包含如normal transaction table, the BP dirty-pages table以及any file mapping information for the objects (like tablespace, indexspace, etc.) that are “open” (i.e., for which BP dirty–pages table has entries)。构建好这个end–chkpt并将其持久化之后,begin-chkpt的LSN信息会被保存到一个master record中,这个master record的位置是已知的。如果在写入end–chkpt记录之前、写入begin-chkpt记录之后系统故障了,这个checkpint就被是为一个不完整的checkpoint。在begin-chkpt和end–chkpt之间,事务可能已经写入其它的日志记录,这里的事务处于一种in-doubt的状态,

If one or more transactions are likely to remain in the in-doubt state for a long time because of prolonged loss of contact with the commit coordinator, then it is a good idea to include in the end-chkpt record information about the update-type locks (e.g., X, IX and SIX) held by those transactions. This way, if a failure were to occur, then, during restart recovery, those locks could be reacquired without having to access the prepare records of those transactions.

重启处理流程

重启恢复操作的伪代码如下。操作的第一部步Analysis Pass,Analysis步骤的输入是Master Addr,输出是Transaction Table,包含了在系统故障or关闭的时候处理in-doubt状态、unprepared状态的事务;dirty pages table,包含了在系统故障or关闭的时候 可能为 dirty的pages;RedoLSN,标记了redo开始的位置。这些信息是通过扫描log来构建的。在一些系统中Analysis不是必须的,可以和后面操作的步骤结合到一起。

RESTART(Master_Addr);
Restart_Analysis(Master_Addr, Trans_Table, Dlrty_Pages, RedoLSN);
Restart_Redo(RedoLSN, Trans_Table, Dirty_Pages);
buffer pool Drity_Pages table := Dirty_Pages;
remove entrued from non-buffer-resident pages from the buffer pool Dirty_Pages table;
Resater_Undo(Trans_Table);
reacquire locks for prepared transactions;
checkpoints();
RESTURN
  • Analysis Pass接下来的操作时Redo Pass。Redo Pass的输入时RedoLSN,以及dirty pages table。Redo Pass冲RedoLSN处开始扫描log。遇到一个可以redo的日志记录之后,先查询对应的page是否在dirty pages table中,如果存在且log的LSN大于等于对应page的RecLSN,通过比较Page的LSN和这条日志的LSN来决定是否需要redo,在Page的LSN小于日志的LSN时满足条件。不是所有的Page都需要redo,可能在最后一个checkpoint之后,某个dirty page持久化了,但是相关的信息没有被添加到checkpoint中系统就故障了。第三步操作时Undo Pass,这一步中主要是回滚失败的事务。
  • 另外在恢复的过程中也使用了checkpoint机制,在Analysis Pass中,在这个步骤的末尾加上一个checkpoint。这样在恢复的过程中有发生故障的情况下可以节省一些工作,加快重新恢复的速度。在Redo Pass和Undo Pass中也有相关的应用。

Media恢复

TODO

Nested Top Actions

TODO

Recovery Paradigms

TODO

参考

  1. ARIES: A Transaction Recovery Method Supporting Fine-Franularity Locking and Partial Rollbacks Using Write-Ahead Logging, TODS 1992.