数据库恢复

1.简介

如今，数据库恢复最流行的算法是由IBM提出的ARIES。其思想主要包括三个部分：

• Write-Ahead Logging
• Repeating History During Redo
• Logging Changes During Undo

其中，undo操作同样也需要记录日记。这是为了保证在恢复的过程中若发生崩溃，则需要从恢复的崩溃中恢复。

2.Log Sequence Numbers

生成的日志都会被分配一个单调递增的数，用于唯一标识日志，称之为LSN。由于并发事务的存在，LSN不一定是连续的。

在系统、事务以及page中，会维护一些与LSN相关的metadata，如下表所示：

Name	Where	Definition
flushedLSN	Memory	最后一个写入到磁盘的LSN序号。
pageLSN	page	对于每个page来说，最后对该page作出修改的LSN。
recLSN	page	使page标志dirty变为真的日志LSN。
LastLSN	transaction	每个事务最后的产生LSN序号。
MasterRecord	Disk	最后一个Checkpoint的LSN。

其中，一个额外的保证是在一个page写入到磁盘前，需要保证$pageLsn<=flushedLSN$，即需要保证数据在落地到磁盘前，其相关的日志需要被记录。

3.Transaction Execution

每个事务其实就是由写和读组成的序列，由COMMIT或ABORT结尾。

在这里，为了简化事务的执行过程中日志的变化过程，作出以下假设：

• 1.所有日志能够放在一个page中
• 2.page写入磁盘的操作是原子的
• 3.单版本，由2PL作为并发协议
• 4.对于缓存池管理器，采用STEAL（允许未提交的事务将含有修改的page写入磁盘）+NO-FORCE（不要求事务将锁修改的所有dirty page都写入到磁盘）的策略。

在事务提交的时候，执行的流程为：

• 在日志中写入COMMIT标记。注意，这并不代表事务已经执行完并返回给用户COMMIT了，只是表示事务需要进行COMMIT的相关工作。
• 将COMMIT标记及之前的日志都写入到磁盘中。常见的优化方法是采用两个Buffer Pool轮转，当一个Buffer Pool正在写入内容到磁盘中时，使用另外一个Buffer Pool写入新的日志。
• 当写入到磁盘完成后，写入一个特殊标记TXN-END，然后告知外部该事务已经提交。

为了在ABORT时可以方便的回滚，每一个WAL日志需要维护一个preLSN，用于标记该事务的上一个LSN序号。在事务放弃的时候，执行的流程为：

• 在日志中写入ABORT标记，然后告知用户该事务已经ABORT了。这里不需要等待事务的日志都写入到磁盘后再告知用户。
• 通过preLSN获取该事务的相关日志，并利用日志中的Before Value对修改进行回滚。注意，该回滚操作也会产生日志。
• 回滚完毕后，写入一个特殊标记TXN-END。

1.为什么需要preLSN？对于一个事务来说，他的LSN并不是连续的，因为有可能存在其他的并发事务。preLSN减少了对WAL扫描的时间。

2.为什么ABORT不需要等到WAL写入磁盘后才告诉用户ABORT？COMMIT作出该保证的原因是因为崩溃时可以知道所有的修改，而在ABORT的时候若崩溃了，我不需要知道该事务作出的修改。

4.Fuzzy Checkpointing

ARIES是允许在事务不停止的情况下，制作Checkpoint并支持恢复数据库的算法。

Fuzzy Checkpoint是ARIES所使用的制作Checkpoint的手段，在开始和结束制作checkpoint的时候，需要添加两个特殊的日志：

• CHECKPOINT-BEGIN：表示checkpoint的起点。
• CHECKPOINT-END：表示checkpoint制作完毕，并包含CHECKPOINT-BEGIN前的ATT和DPT。

ATT表示的是Active Transaction Table，DPT表示的是Dirty Page Table。主要是用于记录有哪些没有运行完毕的事务以及有哪些在buffer pool是dirty的。

ATT需要包含以下信息：

• Transaction Id
• status，如running，commiting，undo
• lastLSN：最后创建的LSN

为何事务在结束时需要写入TXN-END？这表示的其实是在TXN-END之后，ATT中不可能会再看到该Transaction相关的信息了。

DPT则需要记录recLSN，即使page变为dirty的LSN。

Checkpoint的思想是，记录CHECKPOINT-BEGIN前的活跃事务与脏页的信息，并通过与扫描CHECKPOINT-BEGIN之后的信息归并总结，从而获得最新的活跃事务与脏页信息。

该思想其实与数据库的持久化思想相同。利用全量的数据库副本作为状态，再利用增量的追加日志作为该状态的偏移，从而得到最新的数据库状态。

5.ARIES Recovery

ARIES的恢复主要包括三个阶段：

• Analysis：从MasterRecord中得到最后一个Checkpoint的位置，然后进行顺序扫描，得到ATT与DPT的信息。
• Redo：从DPT中找到时间最小的LSN，以该LSN为起点，重复所有（包括ABORT）日志对应的操作。为什么ABORT的事务日志也要重复？这是因为在并发事务下，如果去除了ABORT事务的操作带来的影响，得到的结果不一定完全一致。
• Undo：模拟Undo ABORT事务。

5.1.Analysis

Analysis做的事情就是从Checkpoint到扫描到日志尾部，从而分析出最新的ATT和DPT内容。

具体来说，是从CHECKPOINT-BEGIN顺序扫描WAL到尾部，从而维护ATT和DPT。

ATT的维护方法为：

• 若发现了事务Tx的TXN-END，则将其从ATT中去掉。
• 否则，若发现所有其他关于事务Tx的日志，都将其加入ATT中。

DPT的维护方法为：对于UPDATE page的语句，如果P不在DPT中，则将其写入DPT，并将其LSN作为recLSN。

5.2.Redo

系统在Redo阶段首先找出DPT中所有PageRec LSN中最小的，作为redo的起始位置，因为再往前的日志记录对应的数据修改都已落盘，不会出现在DPT中。

随后系统从redo的起始位置开始，按顺序对后续更新日志记录（包括CLR）执行redo操作，除非遇到以下三种情况，都表示该LSN对应记录已经落盘，可以直接跳过，不需要执行redo：

• 更新的Page不在Dirty Page Table中
• Page在Dirty Page Table中但Rec LSN大于当前LSN
• 磁盘上的Page LSN大于当前的LSN

在redo时，系统不需要再记录日志，因为redo只是实现整个内存状态的重构，如果在redo时又出现了系统故障，则按照原来操作重新进行一遍即可。重复redo是没有风险的，因为前面三种情况已经规避了已经写入到磁盘的情况。

5.3.Undo

Undo阶段目的是撤销在系统故障时未完成的事务，即Redo阶段之后仍存在于ATT中的事务。

首先，找到ATT中lastLSN最大的事务，然后利用食物中LSN对应的日志及其preLSN所串连的日志对数据进行，直到preLSN为空。

---

参考与扩展

https://www.transwarp.cn/news/1712