上节课介绍到，故障恢复算法由两个部分构成：
- 在事务执行过程中采取的行动来确保出现故障时能够恢复 (上节课)
- 在故障发生后的恢复机制，确保原子性、一致性和持久性 (本节课)
1 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
- Normal Commit & Abort Operations
- Fuzzy Checkpointing
- Recovery Algorithm
2 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 |
pageLSN 和 recLSN 对应一个 page 尚未落盘的最新 log 和最老 log。
在 buffer pool manager 中，每个 data page 都维护着 pageLSN，而 DBMS 本身需要追踪 flushedLSN。
事务修改某 page 中的数据时，要更新该 page 的 pageLSN，在将操作日志写进 WAL 后，DBMS 会更新 flushedLSN 为最新落盘的 log record 的 LSN。
在 page x 落盘前，DBMS 必须保证以下条件成立，表明该 page 的对应的 log 已落盘：
\[pageLSN_x ≤ flushedLSN \]
3 Normal Commit & Abort Operations
每个事务都会包含一些列的读和写操作，然后提交 (commit) 或中止 (abort)，本节我们来看下不存在故障时，事务的正常执行过程。
在讨论之前，我们需要约定 4 个假设，简化问题：
- 所有日志记录都能放进一个 page 中
- 写一个 page 到磁盘能保持原子性
- 没有 MVCC，使用严格的 2PL
- 使用 WAL 记录操作日志，buffer pool policy 为 Steal + No-Force
3.1 Transaction Commit
当事务提交时，DBMS 先写入一条 COMMIT 记录到 WAL ，然后将 COMMIT 及之前的日志落盘，当落盘完成后，flushedLSN 被修改为 COMMIT 记录的 LSN，同时 DBMS 将内存中 COMMIT 及其之前的日志清除。最后等事务涉及的脏数据页也落盘后，再写入一条 TXN-END 记录到 WAL 中，作为内部记录，对于执行提交的事务来说，COMMIT 与 TXN-END 之间没有别的操作。
3.2 Transaction Abort
要处理事务回滚，就必须从 WAL 中找出所有与该事务相关的日志及其执行顺序。由于在 DBMS 中执行的所有事务的操作记录都会写到 WAL 中，因此为了提高效率，同一个事务的每条日志中需要记录上一条记录的 LSN，即 prevLSN，一个特殊情况是：第一条 BEGIN 记录的 prevLSN 为空。
实际上中止事务是 ARIES undo 操作的一种特殊情况：回滚单个事务。
可以看到，T4 的每条日志都记录着 prevLSN，当 T4 要中止时，DBMS 先向 WAL 中写入一条 ABORT 记录，然后寻着 LSN 与 prevLSN 连接串成的链表，找到之前的操作，倒序回滚恢复旧值，为了防止在回滚过程中再次故障导致部分操作被执行多次，回滚操作也需要写入日志中，等待所有操作回滚完毕后，DBMS 再往 WAL 中写入 TXN-END 记录，意味着所有与这个事务有关的日志都已经写完，不会再出现相关信息。
那么，如何记录回滚操作呢？这就是我们马上要介绍的 CLR。
3.3 Compensation Log Records
CLR 描述了为 undo 先前更新记录的操作而采取的操作，它记录了原操作 log record 的所有字段 和 undoNext 指针 (指向下一个将要被 undo 的 LSN)，CLR 本身也是操作记录，因此它也需要像其它操作一样写进 WAL 中，但DBMS在通知 application 事务中止前，不会强制将它们落盘。
标签：事务,Crash,记录,LSN,DBMS,20,Lecture,日志,page From： https://www.cnblogs.com/angelia-wang/p/17335375.html