Recovery

数据库系统构建在许多的硬件跟软件上，他们也会有自身的稳定性跟可靠性等问题。数据库系统、底层的软件跟硬件的组件，同样也有可能会失效。数据库的开发人员需要去考虑这些失效的场景来确保数据需要按照所承诺的一般被写入磁盘。

Write-ahead log 预写日志 (缩写为 WAL，也被广泛称为 commit log 提交日志) 是一种只允许添加的基于磁盘的数据结构，他被用来从奔溃或事务中恢复数据库。页缓存允许页内容的更改缓存到内存中。在缓存的内容被写到磁盘之前，唯一的数据操作记录副本会被保存在基于磁盘的 WAL 中。许多的数据库都使用了 append-only write-ahead log 只进行附加的预写日志，比如 PostgreSQL 跟 MySQL。

预写日志的主要功能可以总结如下：

允许页缓存缓冲更新的操作，直到能在较大的上下文中确保数据库的持久化语义
持久化所有的操作到磁盘，直到缓存中被这些操作影响的页被安全的同步到磁盘。每个对数据库状态造成修改的操作都需要在这些操作关联的页被修改前记录到磁盘的日志中。
在奔溃后所丢失的内存中的修改，能够通过操作日志进行重建

除了这些功能之外，预写日志在事务的处理中也扮演者非常重要的角色，不得不夸张的说 WAL 有多么的重要，他被用来保证就算在崩溃的情形中，数据也最终肯定会被记录到持久化存储中，未被提交的数据也能够从日志中进行重建，让数据库能够回复到奔溃之前的状态。在本节中，我们会经常引用 ARIES (Algorithm for Recovery and Isolation Exploiting Semantics 基于语义的恢复与隔离算法)，一种先进并被广泛应用的算法。

PostgreSQL Versus fsync()

PostgreSQL 使用 checkpoints 检查点来确保更新后的索引跟数据文件的全部信息，跟日志中的具体的记录能够保持一致。刷新所有的脏页的操作是由定期执行的检查点操作来完成的。同步脏页的的内容到磁盘则是通过内核的 fsync() 调用来实现，他支持将在脏页同步到磁盘，并将内核中的页的 dirty 脏标记清除。就像你所期望的， fsync 在刷新数据页到磁盘出错时会返回错误信息。

在 Linux 跟一些其他的操作系统中， fsync 就算在产生错误未能成功的刷新页时也会清除其脏页标志。另外，错误只会被提交到当时所打开的文件描述符上，所以 fsync 不会返回任何在该描述符打开之前所产生的错误。

因为检查点并不会保存任何时间点中所有打开文件的信息，因此可能会丢失一些错误的提醒。因为脏页标志被清除了，检查点会假定数据已经被成功的记录到了磁盘，但事实上，他可能还未被成功写入。

在某些潜在的恢复失败中，这些行为的组合可能会成功数据丢失或者数据库出错时的来源。这些操作很难被检查出来，因此有一些产生的状态可能是没办法恢复的。有时触发这些行为的操作可能是不平凡的，当使用在一个 Recovery 恢复机制中，我们需要始终关注并思考、每种可能的错误场景。

Log Semantics

Write-ahead log 预写日志只能执行添加操作并且已经写入到日志的内容是不可变的，因此对日志的写入都是顺序性的。 WAL 是一个不可变的、只添加的数据结构，因为写入部分只会在日志的尾部添加日志，因此读取部分可以安全的访问最新写入之前的内容。

WAL 由日志记录组成，每条记录都有唯一的、单调递增的 log sequence number 日志顺序号 (LSN)，一般来说 LSN 会用一个内部的计数器或者是时间戳来表示。因为日志记录并不一定会填满整个磁盘块，他们的内容会被缓存在 log buffer 日志缓冲然后被 force 强制刷到磁盘。这个强制的操作会在缓冲被填满时发生，也可以由事务管理器或页缓存触发。所有的日志记录会按照 LSN 的顺序写到磁盘。

除了单独的操作记录，WAL 也会保存用来指示事务完成的记录。一个事务在其提交日志被强制写入磁盘时才能视为已提交。

为了确保系统能够在进行回滚或从奔溃恢复过程的错误中恢复到正确状态，有些系统会在日志中保存 compensation log records 补偿日志记录 CLR 。

WAL 通常通过接口与主要的存储结构连接，这接口允许在达到检查点时对日志进行 trimming 裁减。日志对数据库如何保持其正确性来说是最重要的一部分，也是非常困难的一部分：在日志裁减跟已经写入主存储结构之间的任何细微的不一致都可能会导致数据丢失。

检查点用来让日志模块知道，在该检查点之前的所有日志都已经被成功的持久化了，因此这部分日志已经不再是必须的，这能够显著的减少数据库启动时需要做的工作量。负责处理强制将脏页刷到磁盘的操作一般称为 sync checkpoint 同步检查点，因为他会完全同步主存储结构。

将全部的内容同步刷回磁盘是不现实的，因为还需要暂停所有正在执行的操作直到完成该检查点，所以大部分的数据库都是实现了 fuzzy checkpoints 模糊检查点，在这种方式里，last_checkpoint 指针会被存储到日志的头部信息中，用来表示最后成功执行的检查点。一个模糊检查点用一条特殊的 begin_checkpoing 日志来表示他的起点，并用一条 end_checkpoint 日志来表示其完结，其中就包含了跟这个检查点相关的脏页及其内容等信息。在这个记录关联的所有页被成功写入之前，这个检查点都是处于 incomplete 未完成的状态。然后页会以异步的方式刷到磁盘，一旦刷新成功就会使用 begin_checkpoint 记录的 LSN 来更新 last_checkpoint，如果这时程序崩溃，则恢复处理程序下次会继续从这个位置开始执行。

Operation Versus Data Log

有一些数据库系统，比如 System R 使用了 shadow paging : 一种 copy-on-write 写时复制技术用来确保数据的持久性以及事务的原子性。新的内容被存储到新的未发布的 shadow 页中，之后通过反转指针来从旧页找到保存了新内容的页。

任何状态的改变都可以通过 before-image 操作前的镜像跟 after-image 或者是关联的 redo 跟 undo 操作来表示。在 before-image 上执行 redo 操作将会产生 after-image，类似的，在 after-image 上执行 undo 操作将会产生 before-image。

我们可以使用物理日志 (保存了完整的页面信息或者是字节内容的变化) 或逻辑日志 (记录了需要在当前状态上执行的操作) 来将数据记录或页从一个状态转移到另一个，并且是同时支持双向的转换。因此跟踪页的状态，来确认哪些物理或逻辑日志能够在他上面应用是非常重要的。

物理日志记录了之前跟之后的镜像，因此需要将操作的整个页都记录到日志中。逻辑日志则说明了需要再页是哪个应用哪些操作，比如 "为 Key Y 插入一条数据记录 X"，以及跟他关联的 undo 操作如 “删除跟 Key Y 关联的数据。

在实践中，大部分的数据库同时结合了这两种方式，使用逻辑日志去实现 undo (为了并行跟性能)，使用物理日志去实现 redo (为了减少恢复的时间)。

Steal and Force Policies

为了确认何时能够将内存中的变更刷新到磁盘，数据库系统定义了 steal/no-steal 跟 force/no-force 策略。这些策略主要是应用在页缓存上，但他们更适合在 Recovery 的上下文中讨论，因为 Recovery 会组合使用他们，因此他们对 Recovery 会造成重大的影响。

允许将未提交事务中的页修改刷新到磁盘的的方式称为 steal 策略， no-steal 策略则不允许将未提交的日志内容刷新到磁盘。steal 窃取一个脏页在这里意味着将该页内存中的的内容刷新到磁盘中，然后从磁盘中读取其他的页到原本脏页所在的位置。

force 策略要求事务中修改的所有页都需要在事务提交之前刷新到磁盘中，这也就是说 no-force 策略允许事务在其相关的脏页还没刷新到磁盘前就提交。force 强制提交一个脏页在这里意味着必须在提交前刷新数据到磁盘。

因为 Steal 跟 Force 策略对事务的 redo 跟 undo 都有关联，所以理解他们非常重要。Undo 为已提交事务的强制更新页执行回滚操作，Redo 则将已提交事务的操作应用到磁盘中。

使用 no-steal 策略允许在实现 Recovery 时只使用 Redo 记录：旧的副本会被包含在磁盘中的页里，修改的信息则保存在日志里。使用 no-force 时我们可以推迟多个页的更新来实现缓冲的效果。由于此时需要将页的内容缓存在内存中，所以我们可能需要更大的页缓存。

在使用 force 策略时，奔溃恢复无需为已提交的事务付出额外的工作，因为这些事务的页的修改已经都被写入磁盘了。使用这种方式的主要缺点是事务的提交会因为更多的 I/O 而导致需要更长的时间。

一般来说，在事务提交之前，我们需要收集足够的信息来回滚他的结果。如果事务中的任意一个页被刷到磁盘，我们需要在日志中保存他的 undo 信息，直到他能够成功提交或者是回滚。另一方面，我们需要在日志中保存 redo 记录直到日志提交。在上面两种场景中，事务都只能够在他的 undo 跟 redo 记录都写到日志文件后才能提交。

ARIES

ARIES 是一个 steal/no-force 的恢复算法。他使用物理的 redo 来提高恢复时的性能 (因为可以快速的装载变更信息) ，使用逻辑的 undo 来提高常见操作的并发性 (因为逻辑的 undo 操作可以独立的应用到页上)。他还使用了 WAL 记录来实现恢复时的 repeating history 重复历史，在执行未提交的事务的 undo 之前重新构建数据库，并在执行 undo 的时候创建响应的补偿日志。

当数据库系统在崩溃后重启时，恢复操作由下面三步实现

analysis 分析步骤确认页缓存中的脏页以及在崩溃时处于执行中状态的事务。脏页的信息用来确定 redo 步骤的起始点。执行中的事务列表则被用在 undo 步骤中回滚未完成的事务。
redo 步骤则重新执行奔溃之前的历史操作直到数据库恢复到崩溃前的状态。这个步骤也会执行那些已经提交但还未将数据完全写入持久化存储中的事务。
undo 步骤回滚所有未完成的事务并将数据库修复到最后的一致状态。所有的操作都是按与记录时相反的顺序来执行。为了防止在恢复期间数据库再次奔溃，事务的 undo 操作也会被记录到日志中，用来防止重复执行回滚。

ARIES 使用 LSN 来作为日志的标识符，通过执行事务时的 dirty page table 脏页表来跟踪页的修改，使用物理的 redo、逻辑的 undo 跟 fuzzy checkpointing 模糊检查点。尽管该系统的论文早在 1992 年就发布了，但现今的许多概念、方法跟示例仍然跟他有许多的关系。