声明：本文配图和样本数据均来自《数据库系统概念》官网，再次对原作者表示感谢。
1 概述
1.1 数据库是如何访问数据的？
数据库系统常驻于非易失性存储器（主要是磁盘），在任何时间都只有部分内容在主存中。数据库分成称为块（block）的定长存储单位。块是磁盘数据传送的单位，可能包含多个数据项。事务由磁盘向主存输入信息，然后再将信息输出回磁盘。输入和输出操作都以块为单位。位于磁盘上的块为物理块，临时位于主存中的块称为缓冲块。内存中用于临时存放块的区域叫做磁盘缓冲区。
下面这张图描述了事务操作数据时的大致过程：
一般地，事务都有自己的私有工作区（事务初始化时创建），用于保存事务访问及更新的所有数据项的拷贝，在事务提交或者终止时删除。事务通过在其私有工作区和系统缓冲区之间传送数据（read(X)和write(X)），与数据库系统进行交互。
read(X)和write(X)操作都可能需要将块从磁盘传送到主存，但是它们都没有特别指明需要将块从主存传送回磁盘，也就意味着write(x)和output(B)并没有直接的对应关系，而是异步的，因为缓冲块B可能包含其它正在被访问的数据项。实际上，缓冲区的块写回磁盘一般发生于：1.缓冲区溢出需要交换内存空间；2.数据库系统希望将磁盘块B的变化反映到磁盘上。
事务对数据的完整更新操作应该包含3个部分：
- 在工作区完成对数据的计算处理。
- 调用write(X)将新数据更新到系统缓冲区。 --只要完成了这一步，就可以说事务修改了数据库。
- 数据据系统执行output(B)操作将缓冲块写回磁盘。
如果数据库系统在write(X)完成后和output(B)完成之前发生故障，事务已经提交的修改就会丢失。实际上，更大概率的事件是在事务提交之前就遇到了系统故障，而此时事务的部分更新已经写回磁盘，部分更新没有完成，破坏了磁盘数据的一致性。
因此，需要设计一些机制来保证数据据系统即使发生崩溃，事务的原子性也能得到保证，从而保证数据的一致性。
2 故障恢复的基础
在系统重启后，想要做一些恢复动作来保持原子性，就必须在修改数据库之前，先写入一些信息来记录后面的修改，这种工作也叫作预埋。使用最为广泛的记录数据库修改的结构就是日志，日志是日志记录的序列，它记录数据库中的所有更新活动。
2.1 日志记录
每次事务执行写操作时，必须在数据库修改前建立该次写操作的日志记录并把它加到日志中，而日志必须存放在稳定存储器中。这里需要注意的是，数据据系统所在的磁盘属于非易失性存储，也容易发生各种物理故障，比如磁头和扇区损坏。而日志所在的存储需要更高的稳定性，稳定存储器中的信息永远不会丢失（接近100%可靠），一般就是采用RAID技术来尽可能保证磁盘单点故障不会损坏到数据。
日志记录的结构：<
, 
, V_old, V_new>
它记录了某个事务在某个数据项上的修改，并保存了修改前的旧值和修改后的新值。通常是数据项在磁盘上的位置，包括数据项所驻留的块的块标识和块内偏移量。
日志中还包括一些事务状态的记录：
- <, ,start> 事务开始
- <, commit> 事务提交 ，这是事务的最后一个日志记录，当这条记录输出到稳定性存储后，就可以说这个事务提交了，这时所有更早的日志记录都已经输出到稳定性存储中，即使发生崩溃，事务所做的更新也可以重做（redo）。如果系统发生在<, commit>输出到稳定性存储之前，事务将会回滚（undo）。
- <, abort> 事务中止
需要强调的是，日志记录输出到稳定存储器也是异步的，和数据更新一样仍然会先写入系统缓冲块，再在合适的时候写入到稳定存储器。
2.2 事务的redo和undo
redo将事务更新过的所有数据项的值都设置成新值。
通过redo来执行更新的顺序是非常重要的。当从系统中恢复时，如果对一个特定数据项的多个更新的执行顺序不同于它们原来的执行顺序，那么该数据的最终状态很可能将是一个错误的值。对于恢复算法，一般都是对日志进行扫描，在扫描过程中每遇到一个redo日志就执行redo动作，而不是针对每个事务单独做redo，这样可以提高恢复的效率。
undo将事务更新过的所有数据项的值都恢复成旧值。
对于事物的undo操作完成后，它写一个<, abort>日志记录，表示撤销完成了。
发生系统崩溃后，系统查询日志以确定为保证原子性需要对哪些事务进行重做（redo），对哪些事务进行撤销（undo）。
- 如果日志包括<, ,start>，但没有<, commit> 和<, abort>，执行undo。
- 如果日志包括<, ,start>，以及<, commit> 或者<, abort>，执行redo。如果有<, abort>，说明事务中止完成，为什么还要执行redo？<, ,abort>日志记录是事务回滚时写入的，日志中一定也包含了回滚时写入的只读日志记录<, , V>，所以发现<, ,abort>时重做是对事务的修改做了撤销，这里确实是冗余操作，但是简化了恢复算法。
2.3 检查点checkpoint
如果每次系统崩溃后的恢复工作都需要扫描整个日志来完成，会导致：
- 搜索过程太耗时。
- 对于大部分事务，已经完成缓冲块到磁盘块的输出操作，不存在破坏原子性的问题，对它们重做会使恢复过程加长。
实际上，需要重做或者撤销的事务，只是那些在系统崩溃时正处于活跃状态的事务（包括未提交的和正在回滚的事务）。因此引入checkpoint来降低恢复的开销。
检查点的执行过程：
- 将当前位于主存的所有日志记录输出到稳定存储器。
- 将所有修改的缓冲块输出到磁盘。
- 将一个日志记录<checkpoint L>输出到稳定存储器，和日志记录存放在一起，L是执行检查点时正活跃的事务的列表。
在检查点执行过程中，不允许事务执行任何更新动作，如往缓冲块写入数据或写日志记录。
在系统崩溃发生后，系统检查日志找到最后一条<checkpoint L>记录（从尾部反向搜索）后，只需要对L中的事务执行redo或者undo。因为只需要从最后的checkpoint位置处开始执行恢复，效率会提高很多。同时，做完checkpoint后，之前的日志记录也就不再需要了，数据据系统可以在需要更多空间时清除这些日志记录。
3 恢复算法
3.1 常规的事务回滚
对于常规的事务回滚（非系统崩溃导致，比如检测到死锁），过程如下：
-
从后往前扫描日志，对于发现的每一个形如<, , V_old, V_new>的日志记录（对应于数据更新操作）：a. 值V_old被写入数据项中。b. 往日志中写一个特殊的只读日志记录<, , V_old>（补偿日志记录）。
- 一旦发现了<, ,start>日志记录，就停止从后往前的扫描，并往日志中写一个<, ,abort>日志记录。
3.2 系统崩溃后的恢复
系统崩溃后的恢复分为两个阶段：
1.重做阶段，图中箭头向下的Redo Pass。
2.撤销阶段，图中的Undo pass。
3.2.1 重做阶段
从最后一个checkpoint开始正向扫描日志来重做所有事务的更新，包括在系统崩溃前已经回滚的事务的日志记录。
- 将要回滚的事务的列表undo-list初始设定为<checkpoint L>日志记录中的L列表。
- 一旦遇到形如<, , V_old, V_new>或者<, , V>的日志记录，就重做这个操作。因为<, , V>是事务回滚时写入的，所以这里的重做就是把V值写入数据项。
- 一旦发现形如<, ,start>的日志记录，表示事务在最后的checkpoint执行完以后开始的，就把这个事务加到undo-list中。
- 一旦发现形如<, ,abort>或者<, ,commit>的日志记录，表示事务在最后的checkpoint执行完以后完成了，就把该事务从undo-list中去掉。
在redo阶段的末尾，undo-list包括在系统崩溃之前尚未完成的所有事务：没有提交的事务或者没有完成回滚的事务。
3.2.2 撤销阶段
从尾端开始反向扫描日志回滚undo-list中的事务：
- 一旦发现属于undo-list中事务的日志记录，就执行undo操作，就如同前面事务失败时的常规回滚操作。
- 发现undo-list中事务的<, ,start>日志记录，就往日志写入一个<, ,abort>日志记录，表示该事务撤销完成，并把该事务从undo-list中移除。
- 一旦undo-list变为空表，表示系统已经找到了开始时位于undo-list中所有事务的<, ,start>日志记录，撤销阶段结束。
当恢复过程的撤销阶段结束后，就可以重新开始正常的事务处理了。
3.3 日志记录的约束
恢复机制的高效实现需要尽可能减少向数据库和稳定存储器写出的数目。前面提到过，日志记录在开始可以保存在内存的日志缓冲区中，但是系统崩溃也会导致这些日志信息丢失，必须对恢复算法添加一些约束以保证事务的原子性：
- 在<, ,commit>日志记录输出到稳定存储后，事务进入提交状态。
- 在<, ,commit>日志记录输出到稳定存储器之前，与该事务相关的所有日志记录必须已经输出到稳定存储器中。对于一个事务，<, ,commit>永远是该事务在日志中的最后一条记录。
- 在内存中的一个数据块输出到（磁盘中）数据库之前，与该块中的数据相关的所有日志记录必须已经输出到稳定存储器中，也称为先写日志（Write-Ahead Logging, WAL）规则。
注：上面介绍的只是最简单的故障恢复，实际数据库中的故障恢复算法要复杂的多。