# Database Recovery

上节课介绍到，故障恢复算法由两个部分构成：

* 在事务执行过程中采取的行动来确保出现故障时能够恢复 (上节课)
* 在故障发生后的恢复机制，确保原子性、一致性和持久性 (本节课)

### ARIES

本节课介绍的是 Algorithms for Recovery and Isolation Exploiting Semantics (ARIES)，由 IBM Research 在 90 年代初为 DB2 DBMS 研发的基于 WAL 的故障恢复机制，尽管并非所有 DBMS 都严格按照 ARIES paper 实现故障恢复机制，但它们的思路基本一致。

ARIES 的核心思想可以总结为 3 点：

* Write-Ahead Logging (WAL)
  * 在数据落盘之前，所有写操作都必须记录在日志中并落盘
  * 必须使用 Steal + No-Force 缓存管理策略 (buffer pool policies)
* Repeating History During Redo
  * 当 DBMS 重启时，按照日志记录的内容重做数据，恢复到故障发生前的状态
* Logging Changes During Undo
  * 在 undo 过程中记录 undo 操作到日志中，确保在恢复期间再次出现故障时不会执行多次相同的 undo 操作

### Log Sequence Numbers

WAL 中的每条日志记录都需要包含一个全局唯一的 log sequence number (LSN)，一般 LSN 单调递增。DBMS 中的不同部分都需要记录相关的 LSN 信息，举例如下：

| Name         | Where            | Definition                     |
| ------------ | ---------------- | ------------------------------ |
| flushedLSN   | memory           | 最后落盘的那个 LSN                    |
| pageLSN      | buffer pool page | 与某 page data 相关的最新 LSN         |
| recLSN       | buffer pool page | 在上次落盘之后，与某 page data 相关的最老 LSN |
| lastLSN      | transaction      | 某事务最后一条日志的 LSN                 |
| MasterRecord | disk             | 最近一次 checkpoint 的 LSN          |

在 buffer pool manager 中，每个 data page 都维护着 pageLSN，而 DBMS 本身需要追踪 flushedLSN，那么在 page x 落盘前，DBMS 必须保证以下条件成立：

$$
pageLSN\_x \le flushedLSN
$$

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M97am2_3_BVde5RcxdD%2F-M97ipBdwkZhgTVBsW_i%2FScreen%20Shot%202020-06-06%20at%204.24.25%20PM.jpg?alt=media\&token=ef764239-fd24-41d6-85a8-85c78fa4325c)

当一个事务修改某 page 中的数据时，也需要更新该 page 的 pageLSN，在将操作日志写进 WAL 后，DBMS 会更新 flushedLSN 为最新写入的 LSN。

### Normal Execution

每个事务都会包含一些列的读和写操作，然后提交 (commit) 或中止 (abort)，本节我们来看下不存在故障时，事务的正常执行过程。在讨论之前，我们需要约定 4 个假设，简化问题：

* 所有日志记录都能放进一个 page 中
* 写一个 page 到磁盘能保持原子性
* 没有 MVCC，使用严格的 2PL
* 使用 WAL 记录操作日志，buffer pool policy 为 Steal + No-Force

#### Transaction Commit

当事务提交时，DBMS 先写入一条 COMMIT 记录到 WAL  ，然后将 COMMIT 及之前的日志落盘，当落盘完成后，flushedLSN 被修改为 COMMIT 记录的 LSN，同时 DBMS  将内存中 COMMIT 及其之前的日志清除。最后再写入一条 TXN-END 记录到 WAL 中，作为内部记录，对于执行提交的事务来说，COMMIT 与 TXN-END 之间没有别的操作。整个过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M97am2_3_BVde5RcxdD%2F-M97uVDFSs5dBRd8ONce%2FScreen%20Shot%202020-06-06%20at%205.15.28%20PM.jpg?alt=media\&token=73b86733-047b-45df-821a-e761fe8e6c7a)

#### Transaction Abort

要处理事务回滚，就必须从 WAL 中找出所有与该事务相关的日志及其执行顺序。由于在 DBMS 中执行的所有事务的操作记录都会写到 WAL 中，因此为了提高效率，同一个事务的每条日志中需要记录上一条记录的 LSN，即 prevLSN，一个特殊情况是：第一条 BEGIN 记录的 prevLSN 为空。

实际上中止事务是 ARIES undo 操作的一种特殊情况：回滚单个事务。过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M97xvcl9voXTIZHRbB1%2F-M97ymeDCvhcsipRVZCR%2FScreen%20Shot%202020-06-06%20at%205.34.09%20PM.jpg?alt=media\&token=102d8bb3-99e5-4bcd-a7eb-8eb2dbb55b07)

可以看到，T4 的每条日志都记录着 prevLSN，当 T4 要中止时，DBMS 先向 WAL 中写入一条 ABORT 记录，然后寻着 LSN 与 prevLSN 连接串成的链表，找到之前的操作，倒序回滚，为了防止在回滚过程中再次故障导致部分操作被执行多次，回滚操作也需要写入日志中，等待所有操作回滚完毕后，DBMS 再往 WAL 中写入 TXN-END 记录，意味着所有与这个事务有关的日志都已经写完，不会再出现相关信息。那么，如何记录回滚操作呢？这就是我们马上要介绍的 CLR：

#### Compensation Log Records

CLR 记录的是 undo 操作，它除了记录原操作相关的记录，还记录了 undoNext 指针，指向下一个将要被 undo 的 LSN，CLR 本身也是操作记录，因此它也需要像其它操作一样写进 WAL 中，举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M98-0-qPoaIh_gKYQOg%2F-M98HGVM06SzmgverNb8%2FScreen%20Shot%202020-06-06%20at%206.59.13%20PM.jpg?alt=media\&token=d1129325-7a00-48f3-96e7-2df2a93c1a3e)

值得注意的是：CLR 永远不需要被 undone。

### Non-fuzzy & fuzzy Checkpoints

#### Non-fuzzy Checkpoints

使用 Non-fuzzy 的方式做 checkpoints 时，DBMS 会暂停所有工作，保证落盘的是一个 consistent snapshot，整个过程包括：

* 停止任何新的事务
* 等待所有活跃事务执行完毕
* 将所有脏页落盘

显然这种方案很糟糕。

#### Slightly Better Checkpoints

Non-fuzzy 需要停止所有事务，并且等待所有活跃事务执行完毕，我们是否有可能改善这一点？一种做法是：checkpoint 开始后，暂停写事务，阻止写事务获取数据或索引的写锁 (write latch)，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M98-0-qPoaIh_gKYQOg%2F-M98KSCcXCs76z7RZAkz%2FScreen%20Shot%202020-06-06%20at%207.13.13%20PM.jpg?alt=media\&token=95178f9e-e1f3-4cb4-802c-90ba6fd0e268)

checkpoint 开始时，txn 已经获取了 page#3 的写锁，后者可以继续往 page#3 中写数据，但不能再获取其它 page  的写锁，此时 DBMS 只管扫描一遍 buffer pool 中的 pages，将所有脏页落盘。这时，部分 txn 写入的数据可能会被 checkpoint 进程一起捎带落盘，这时磁盘中的数据 snapshot 处于 inconsistent  的状态。

即便如此，只要我们在 checkpoint 的时候记录哪些活跃事务正在进行，哪些数据页是脏的，故障恢复时读取 WAL 就能知道存在哪些活跃事务的数据可能被部分写出，从而恢复 inconsistent 的数据。因此整个 checkpoint 过程需要两类信息：

* 活跃事务表：Active Transaction Table (ATT)
* 脏页表：Dirty Page Table (DPT)

活跃事务表中记录着活跃事务的事务 id、事务状态 (Running/Committing/Candidate for Undo) 以及 lastLSN (最新的日志记录 LSN)，当事务提交或中止后，相应的记录才会被删除；脏页表记录着 buffer pool 中所有包含未提交事务写入数据的页信息，其中还记录着每个脏页最近一次落盘的日志记录的 LSN，即 recLSN。一个完整的 WAL 举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M98-0-qPoaIh_gKYQOg%2F-M98NRN-6TSfyXAPXrah%2FScreen%20Shot%202020-06-06%20at%207.26.17%20PM.jpg?alt=media\&token=01c2e82c-19e6-41e6-80eb-763b1d14c591)

在第一个 checkpoint 处：活跃事务有 T2，脏页有 P11 和 P22；在第二个 checkpoint  处，活跃事务有 T3，脏页有 P11 和 P33。

这种方案尽管比 Non-fuzzy 好一些，不需要等待所有活跃事务执行完毕，但仍然需要在 checkpoint 期间暂停执行所有写事务。

#### Fuzzy Checkpoints

fuzzy checkpoint 允许任何活跃事务在它落盘的过程中执行。既然允许活跃事务执行，checkpoint 在 WAL 中的记录就不是孤零零的一条，而是一个区间，因此我们需要两类记录来标记这个区间：

* CHECKPOINT-BEGIN：checkpoint 的起点
* CHECKPOINT-END：checkpoint 的终点，同时包含 ATT 和 DPT 记录

当 checkpoint 成功完成时，CHECKPOINT-BEGIN 记录的 LSN 才被写入到数据库的 MasterRecord 中，任何在 checkpoint 之后才启动的事务不会被记录在 CHECKPOINT-END 的 ATT 中，举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M98P92rG4IJJTKiePCQ%2F-M98QXAvXge6jjS7MYXh%2FScreen%20Shot%202020-06-06%20at%207.39.43%20PM.jpg?alt=media\&token=6525ad8f-d13b-44d5-bff4-98641bd5f758)

显然实践中使用的是 fuzzy checkpoint，这也是接下来要介绍的 ARIES 的故障恢复算法的基础。

### ARIES - Recovery Phases

ARIES 故障恢复一共分三步：

* 分析 (analysis)：从 WAL 中读取最近一次 checkpoint，找到 buffer pool 中相应的脏页以及故障时的活跃事务
* 重做 (redo)：从正确的日志点开始重做所有操作，包括将要中止的事务
* 撤销 (undo)：将故障前未提交的事务的操作撤销

整体流程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M98RvhiFzm-uXsTLvUb%2F-M98v9nUJ0C6N0jkwkfb%2FScreen%20Shot%202020-06-06%20at%209.57.58%20PM.jpg?alt=media\&token=7c0e9df5-9188-4ebd-9eaf-fa4368bc0a33)

通过 MasterRecord 找到最后一个 BEGIN-CHECKPOINT 记录，然后分别进行 3 个阶段：

1. 分析：找到最后一个 checkpoint 之后哪些事务提交或中止了
2. 重做：找到 DPT 中最小的 recLSN，从那里开始重做所有操作
3. 撤销：WAL 最近的位置开始往回撤销所有未提交的事务操作

#### Analysis Phase

从最近的 BEGIN-CHECKPOINT 开始往近处扫描日志：

* 如果发现 TXN-END 记录，则从 ATT 中移除该事务
* 遇到其它日志记录时
  * 将事务放入 ATT 中，将 status 设置为 UNDO
  * 如果事务提交，将其状态修改为 COMMIT
  * 如果是数据更新记录，按需更新 DPT 以及 recLSN

当 Analysis Phase 结束时：

* ATT 告诉 DBMS 在发生故障时，哪些事务是活跃的
* DPT 告诉 DBMS 在发生故障时，哪些脏数据页可能尚未写入磁盘

#### Redo Phase

Redo Phase 的目的在于回放历史，重建崩溃那一瞬间的数据库状态，即重做所有更新操作 (包括后来发生中止事务的操作)，同时重做 CLRs。尽管 DBMS 可以通过一些手段避免不必要的读写，但本节课不讨论这些优化技术。

从 DPT 中找到最小的 recLSN，从那里开始重做更新记录和 CLR，除非遇到以下两种情况：

* 受影响的 page 不在 DPT 中
* 受影响的 page 在 DPT 中，但那条记录的 LSN 小于那个 page 的 recLSN

重做时，需要：

1. 重新执行日志中的操作
2. 将 pageLSN 修改成日志记录的 LSN
3. 不再新增操作日志，也不强制刷盘

在 Redo Phase 结束时，会为所有状态为 COMMIT 的事务写入 TXN-END 日志，同时将它们从 ATT 中移除。

#### Undo Phase

将所有 Analysis Phase 判定为 U (candidate for undo) 状态的事务的所有操作按执行顺序倒序撤销，并且为每个 undo 操作写一条 CLR。

#### Additional Crash Issues

> 如果 DBMS 在故障恢复的 Analysis Phase 崩溃怎么办？

无所谓，再执行一次故障恢复算法就好

> 如果 DBMS 在故障恢复的 Redo Phase 崩溃怎么办？

无所谓，再重做所有操作即可，操作是幂等的

> 在 Redo Phase DBMS 如何能够提高性能？

如果数据库不会再次故障，可以异步地将数据落盘 (这点没理解)

> 在 Undo Phase DBMS 如何能够提高性能？

1. Lazy Rollback：在新的事务访问数据页时才回滚数据
2. 在数据库的用户侧，避免运行长时间的事务

### Conclusion

ARIES 的核心观点回顾：

* WAL with Steal/No-Force
* Fuzzy Checkpoints
* Redo everything since the earliest dirty page
* Undo txns that never commit
* Write CLRs when undoing, to survive failures during restarts

### References

* ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, [*paper*](https://dl.acm.org/doi/10.1145/128765.128770)
* lecture [slides](https://15445.courses.cs.cmu.edu/fall2019/slides/21-recovery.pdf), [video](https://www.youtube.com/watch?v=4VGkRXVM5fk\&list=PLSE8ODhjZXjbohkNBWQs_otTrBTrjyohi\&index=22\&t=4113s)