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.