Transaction failure#

事务失败分两种：

• Logical errors：事务因为自身内部条件不能继续执行
  • 例如输入错误、数据不存在、溢出、资源限制等
  • 违反完整性约束，例如插入重复主键、违反外键约束
• System errors：数据库系统因为某种错误条件终止一个活跃事务
  • 典型例子：deadlock
  • 事务被选为 deadlock victim 时，会被系统强制 rollback

这类失败通常只影响某个事务。恢复动作是 abort / rollback 该事务。

关键问题是：事务没有执行到 commit，但已经做了部分更新。根据 atomicity，这些部分更新必须全部撤销。撤销的依据就是 log 中记录的 old value。

System crash#

系统崩溃指 power failure、hardware failure、software failure 等导致系统停止运行。

采用 fail-stop assumption：

系统崩溃会丢失 volatile storage 中的内容，但不会破坏 nonvolatile storage 中已经写好的内容。

这个假设依赖数据库系统和硬件层的大量完整性检查。

可以把 system crash 想象成“突然掉电”：正在并发执行的事务中，有些还没完成，需要 undo；有些已经提交，但修改的数据可能还停留在 buffer，没有真正写到磁盘，需要 redo。因此系统重启后必须先进入 recovery 过程，不能直接对外服务。

Disk failure#

磁盘失败指 head crash 或类似故障破坏磁盘上的全部或部分数据。

特点：

• 非易失存储内容也可能丢失
• 假设破坏是可检测的
• 磁盘通常用 checksum 检测坏块或不完整写入

磁盘失败的朴素恢复思路是：先恢复最近一次 backup / dump，再把 backup 之后已经提交事务的日志重新做一遍。这个过程能恢复正确性，但会带来不可用时间，因此银行等关键系统通常还会配置 remote backup / hot-spare，实现异地热切换。

Volatile / Nonvolatile / Stable Storage#

Stable Storage 的近似实现#

基本方法：

• 每个 logical block 维护多个 physical copies
• 多个副本放在不同磁盘上
• 也可以放在 remote sites，防火灾、洪水等灾难
• 副本数量越多，单个磁盘或单个机房故障导致全部副本丢失的概率越低
• 副本最好放在独立故障域中：不同磁盘、不同机器、不同机房，甚至异地

一次 block transfer 可能有三种结果：

1. Successful completion：写入成功完成
2. Partial failure：写到一半失败，目标块内容错误
3. Total failure：还没真正更新目标块就失败，目标块保持旧值

假设每个 block 有两个副本，output 操作可以这样执行：

1
1. 先写第一个 physical block
2
2. 第一个副本写成功后，再写第二个 physical block
3
3. 第二个副本写成功后，才认为 output 完成

恢复时：

• 如果某个副本 checksum 错误，用另一个副本覆盖它
• 如果两个副本都没有 checksum 错误，但内容不同，用第一个副本覆盖第二个副本
• 为了避免恢复时比较所有块，可以在 nonvolatile RAM 或磁盘特殊区域记录正在写的块，只检查这些可能不一致的块

Data Access#

数据库永久存放在磁盘上，运行时只把部分 block 放入内存。

两类 block：

• Physical block：磁盘上的 block
• Buffer block：主存 buffer 中的 block

磁盘和内存之间的数据移动由两个操作完成：

1
input(B)   : 把磁盘上的 physical block B 读入主存
2
output(B)  : 把主存中的 buffer block B 写回磁盘

为了简化讨论，本章假设每个 data item 都完整存放在一个 block 内。

注意 input / output 是磁盘块和内存 buffer 之间的移动；事务内部的 read / write 是 buffer 和事务私有工作区之间的数据移动。恢复系统关心这两个层次的错位：一个事务可能已经 write(X) 修改了 buffer，但包含 X 的 block 还没有 output 到磁盘。

Transaction 的 private work-area#

每个事务 Ti 有自己的私有工作区，保存它访问和更新的数据项的本地副本。

• Ti 对数据项 X 的本地副本记作 xi
• read(X)：把 buffer block 中的 X 读入本地变量 xi
• write(X)：把本地变量 xi 写回 buffer block 中的 X

注意：

write(X) 只是把值写到内存 buffer，不一定马上执行 output(BX) 写回磁盘。

这句话是后面 redo / undo 的根源：

• 已提交事务的更新可能只在 buffer 里，crash 后丢失，所以要 redo
• 未提交事务的更新可能已经 output 到磁盘，所以要 undo
• commit 和 data page 写盘没有一一对应关系，真正的边界由 log 决定

事务规则：

• 第一次访问 X 前，必须执行 read(X)
• 后续可以直接访问本地副本 xi
• write(X) 可以在事务 commit 前任意时刻执行

Log Records#

为了保证失败后的原子性，在真正修改数据库前，系统先把修改信息写到 stable storage 中的 log。

Log 是一串 log records，用来记录数据库的更新活动。

常见 log record：

1
<Ti start>              事务 Ti 开始
2
<Ti, X, V1, V2>          Ti 把 X 从旧值 V1 改为新值 V2
3
<Ti commit>             Ti 提交
4
<Ti abort>              Ti 回滚完成

其中：

• V1：old value，用于 undo
• V2：new value，用于 redo

更新日志必须在对应数据库修改前写出。

日志通常是顺序追加的流水账文件。相比在磁盘上到处随机修改 data page，顺序写 log 的 I/O 代价更低，所以数据库愿意先把每次更新记入 log，再择机把脏页刷回磁盘。

Ti 是事务的唯一标识。实际系统中还会维护每个事务自己的日志链，例如每条日志记录指向同一事务的前一条日志记录，这样 rollback 时不需要从整个 log 末尾逐条搜索该事务的记录。

WAL#

Write-Ahead Logging（WAL，先写日志原则）：

在内存中的数据块被写回数据库前，与该数据块有关的 log records 必须先写到 stable storage。

更直观地说：

1
先写 log，再写 database page

原因：

• 如果数据库页已经写入磁盘，但 log 没写入，崩溃后无法 undo
• 如果 log 已经写入，但数据库页没写入，崩溃后可以 redo

WAL 是 log-based recovery 的核心约束。

WAL 可以分成两个约束理解：

1. data page 写盘前：该 page 相关的所有 update log 必须已经写到 stable storage
2. commit log 写盘前：该事务之前的所有 log records 必须已经写到 stable storage

因此，事务是否已经提交的唯一可靠标志是：<Ti commit> 已经进入 stable storage。commit log 只停在 log buffer 里时，系统 crash 后只能把它当成未提交事务处理。

Concurrency Control and Recovery#

并发事务共享：

• 一个 disk buffer
• 一个 log file

恢复算法通常要求：

如果事务 Ti 修改了某个 item，则在 Ti commit 或 abort 前，其他事务不能修改同一个 item。

否则会出现问题：

1
T1 updates A
2
T2 updates A and commits
3
T1 aborts

如果此时用 T1 的 old value 恢复 A，会把 T2 的已提交更新也覆盖掉。

解决方法：

• 对更新的数据项加 exclusive lock
• 持有到事务结束
• 也就是 strict 2PL

后面讲的 logical undo 可以放宽这个要求，支持 early lock release。

Immediate Modification 与 Deferred Modification#

Transaction Commit#

事务进入 commit 状态的判定标准：

当 <Ti commit> log record 被写到 stable storage 后，事务 Ti 才算真正 committed。

同时要求：

• Ti 的所有先前 log records 已经写到 stable storage
• Ti 修改过的数据页可以仍在 buffer 中，之后再写到磁盘

也就是说：

1
commit 只要求 commit log 稳定落盘
2
不要求所有 data pages 立刻落盘

这正是 no-force policy 的基础。

1
事务 commit 不等于数据页都写盘
2
事务 commit 只要求 commit log 及其之前日志稳定落盘

这也是 group commit 能成立的原因：多个事务的 commit log 可以在同一个 log block 中一起刷出，刷出后这些事务一起变成 committed。

1
Log                         Write              Output
2
<T0 start>
3
<T0, A, 1000, 950>
4
<T0, B, 2000, 2050>         A = 950
5
                            B = 2050
6
<T0 commit>
7
<T1 start>
8
<T1, C, 700, 600>           C = 600            BB, BC
9
<T1 commit>                                    BA

Undo 与 Redo#

对更新日志：

1
<Ti, X, V1, V2>

定义：

• undo：把 X 恢复为 old value V1
• redo：把 X 设置为 new value V2

1
<Ti, X, V1, V2>  ->  write X = V1

1
<Ti, X, V1>

1
<Ti abort>

1
<Ti, X, V1, V2>  ->  write X = V2

恢复时如何判断 Undo / Redo#

系统崩溃后，根据 log 判断事务状态。

事务 Ti 需要 undo：

1
log 中有 <Ti start>
2
但没有 <Ti commit>
3
也没有 <Ti abort>

事务 Ti 需要 redo：

1
log 中有 <Ti start>
2
并且有 <Ti commit> 或 <Ti abort>

这里 <Ti abort> 的事务也要 redo，原因是：

abort 本身也是由一系列补偿动作构成的。崩溃恢复时要 redo 这些补偿动作，保证事务已经被完整撤销。

所以判断事务状态时不要只看是否出现过 update log。正确顺序是：

1
有 commit log：该事务已经提交，redo
2
有 abort log：该事务已经完整回滚，redo 其补偿动作
3
只有 start / update，没有 commit / abort：crash 时未完成，undo

这也是为什么恢复算法先 redo repeating history，再 undo incomplete transactions。

Repeating History#

如果一个事务之前已经被 undo，并且 <Ti abort> 已经写入 log，之后系统又崩溃，那么 recovery 会 redo 这个事务的所有历史动作。

这包括：

• 原来的更新动作
• 后来的补偿日志动作

这种策略叫：

Repeating history（重复历史）

直觉：

1
先把数据库恢复到崩溃那一刻的状态
2
再撤销当时仍未完成的事务

虽然看起来浪费，但它让恢复逻辑非常统一。

假设三个崩溃时间点对应不同 log：

1
(a) T0 未提交时崩溃
2
    -> undo(T0)
3
    -> B 恢复为 2000，A 恢复为 1000
4
    -> 写 <T0, B, 2000>, <T0, A, 1000>, <T0 abort>
5

6
(b) T0 已提交，T1 未提交时崩溃
7
    -> redo(T0), undo(T1)
8
    -> A = 950, B = 2050, C 恢复为 700
9
    -> 写 <T1, C, 700>, <T1 abort>
10

11
(c) T0 和 T1 都已提交时崩溃
12
    -> redo(T0), redo(T1)
13
    -> A = 950, B = 2050, C = 600

Checkpointing#

如果每次 recovery 都从 log 开头扫描，会很慢：

1. 系统运行时间越长，log 越长
2. 很多早已写入磁盘的事务被重复 redo，浪费时间

所以系统周期性执行 checkpoint。

一个基本 checkpoint 操作：

1
1. 把当前内存中的所有 log records 写到 stable storage
2
2. 把所有 modified buffer blocks 写到 disk
3
3. 写一条 <checkpoint L> 到 stable storage

其中 L 是 checkpoint 时仍然 active 的事务列表。

基本 checkpoint 的问题：

执行 checkpoint 时需要暂停所有更新。

它的高代价主要来自两点：

• checkpoint 要强制刷出 log buffer，满足 WAL
• 还要集中刷出所有 modified buffer blocks，形成大量同步 I/O

因此基本 checkpoint 虽然让恢复更快，但正常运行时会造成明显停顿。

后面会用 fuzzy checkpointing 降低这个开销。

checkpoint 后的恢复范围#

恢复时：

1. 从 log 末尾向前找最近的 <checkpoint L>
2. 只有 L 中的事务，以及 checkpoint 后新开始的事务，可能需要 redo / undo
3. 对于 L 中事务，为了 undo，可能还要继续向前找到它们的 <Ti start>
4. 更早的 log 可以在安全时删除

checkpoint log 例子：

checkpoint 时活跃事务是 {T2, T4}。

恢复时只需要关注：

• checkpoint 列表里的 T2, T4
• checkpoint 后开始的新事务

T1 和 T3 已经在 checkpoint 前完成并落盘，不再需要考虑。

易错点：checkpoint 中的列表 L 只记录 checkpoint 时仍 active 的事务。L 中事务在 checkpoint 前的日志仍可能需要用于 undo，所以恢复时可能还要继续向前找到这些事务的 <Ti start>。

例子：

1
T1 在 checkpoint 前开始，在 checkpoint 后提交
2
T2 在 checkpoint 前开始，失败时仍未完成
3
T3 在 checkpoint 后开始并提交
4
T4 在 checkpoint 后开始，失败时仍未完成

恢复动作：

• T1 可以忽略：更新已经因 checkpoint 写入磁盘
• T2 和 T3 redo
• T4 undo

正常执行时的 Logging#

事务正常运行时：

1
事务开始：      写 <Ti start>
2
每次更新 Xj：   写 <Ti, Xj, V1, V2>
3
事务提交：      写 <Ti commit>

其中 update log 必须在数据库 item 被写入前写出。

正常执行时的 Transaction Rollback#

如果事务 Ti 在正常执行过程中需要 rollback：

1
1. 从 log 末尾开始向前扫描
2
2. 对每条属于 Ti 的 <Ti, Xj, V1, V2>：
3
   - 把 Xj 写回 V1
4
   - 写补偿日志 <Ti, Xj, V1>
5
3. 扫到 <Ti start> 后停止
6
4. 写 <Ti abort>

补偿日志是 redo-only 的：

• 它表示“撤销动作本身已经做过”
• 崩溃后 redo 它即可
• 不应该再 undo 它

系统崩溃后的 Recovery#

系统崩溃后的 recovery 分两个阶段：

1. Redo phase：重复历史
2. Undo phase：撤销未完成事务

1
1. 找到最后一条 <checkpoint L>
2
2. undo-list = L
3
3. 从该 checkpoint 开始向前扫描到 log 末尾：
4
   - 遇到 <Ti, Xj, V1, V2>：写 Xj = V2
5
   - 遇到补偿日志 <Ti, Xj, V>：写 Xj = V
6
   - 遇到 <Ti start>：把 Ti 加入 undo-list
7
   - 遇到 <Ti commit> 或 <Ti abort>：从 undo-list 删除 Ti

1
1. 从 log 末尾开始向前扫描
2
2. 遇到属于 undo-list 中事务 Ti 的 <Ti, Xj, V1, V2>：
3
   - 写 Xj = V1
4
   - 写补偿日志 <Ti, Xj, V1>
5
3. 遇到 undo-list 中事务 Ti 的 <Ti start>：
6
   - 写 <Ti abort>
7
   - 从 undo-list 删除 Ti
8
4. undo-list 为空时停止

1
<T1 start>
2
<T1, A, 100, 200>
3
<T2 start>
4
<T2, B, 100, 200>
5
<T3 start>
6
<T3, C, 100, 200>
7
<checkpoint (T1, T2, T3)>
8
<T3, C, 200, 300>
9
<T3 commit>
10
<T4 start>
11
<T4, C, 300, 400>
12
<checkpoint (T1, T2, T4)>
13
<T1 commit>
14
<T4, C, 300>
15
<T4 abort>
16
<T2, C, 300, 400>
17
<T2, C, 300>

1
redo phase: 重做 checkpoint 后的历史
2
undo phase: 撤销 T2，并写 <T2 abort>

Log Record Buffering#

实际系统不会每生成一条 log 就立刻写 stable storage。

做法：

• log records 先放在内存中的 log buffer
• 当 log buffer 满，或执行 log force 时，再写到 stable storage

Log force：强制把 log buffer 中必要的 log records 写到 stable storage。

事务 commit 时必须执行 log force：

1
<Ti commit> 以及 Ti 的所有先前 log records 必须落到 stable storage

Group Commit#

Group commit 把多个事务的 commit log 一次性写出。

好处：

• 多个 log records 共享一次 I/O
• 降低每个事务的 commit I/O 成本
• 高并发事务系统中非常重要

代价：

• 单个事务 commit 可能稍微等待
• 但高负载下整体吞吐量更高，平均延迟可能更低

WAL Rules with Log Buffering#

使用 log buffer 时必须满足三条规则：

1. log records 按创建顺序写到 stable storage
2. 事务 Ti 只有在 <Ti commit> 写到 stable storage 后，才进入 commit state
3. 内存中的 data block 写回数据库前，和该 block 有关的所有 log records 必须先写到 stable storage

第三条就是 WAL。

严格来说，WAL 至少要求 undo information 先写出；如果 undo 和 redo 分开记录，redo information 可以稍后写。

No-force 与 Steal#

1
steal + no-force

Latch#

如果一个含有未提交更新的 block 要写回磁盘，必须先保证 WAL。

输出一个 block 的步骤：

1
1. 获取该 block 的 exclusive latch
2
2. flush 与该 block 有关的 log records
3
3. output 该 block 到磁盘
4
4. 释放 latch

Latch（闩锁） 和事务锁不同：

• latch 是短期的内部锁
• 用来保护内存数据结构或 buffer block
• 不用于保证事务 serializability
• 可以很快释放，不遵循 2PL

OS Buffer 与 Dual Paging#

数据库 buffer 可以有两种实现方式。

1
OS 想淘汰数据库 buffer page 时，通知 DBMS
2
DBMS 先按 WAL 写 log，再把 page 写到 database file
3
然后释放内存给 OS

Fuzzy Checkpointing#

基本 checkpoint 会暂停更新，开销太大。

Fuzzy checkpointing 允许 checkpoint 过程中事务继续执行。

步骤：

1
1. 暂停所有事务更新
2
2. 写 <checkpoint L> 并 force log 到 stable storage
3
3. 记录当前 modified buffer blocks 列表 M
4
4. 允许事务继续执行
5
5. 把 M 中的 modified blocks 写到磁盘
6
   - 写出每个 block 前要满足 WAL
7
   - 写出时不能被更新
8
6. 在磁盘固定位置 last_checkpoint 存放该 checkpoint record 的指针

恢复时：

• 从 last_checkpoint 指向的 checkpoint record 开始扫描
• 如果系统在 checkpoint 中途崩溃，last_checkpoint 还没更新，恢复时仍使用前一个完整 checkpoint

这保证 fuzzy checkpoint 是安全的。

要点是 last_checkpoint 指针：

• 写出 <checkpoint L> 并不立刻说明这个 checkpoint 已经“算数”
• 只有 checkpoint 开始时记录下来的脏页都陆续写出后，系统才能把 last_checkpoint 指向它
• recovery 从 last_checkpoint 指向的 checkpoint 开始，而不一定从 log 中最后出现的 checkpoint 记录开始

因此 fuzzy checkpoint 的“模糊”体现在：checkpoint 记录先出现，脏页在后台慢慢写出，checkpoint 完成状态由额外指针确认。

Failure Detection#

Backup site 必须检测 primary site 是否失败。

难点：

1
primary site failure 和 communication link failure 要区分

做法：

• 多条通信链路
• heart-beat messages

如果 backup 收不到 heartbeat，需要判断是 primary 坏了还是网络断了。

Transfer of Control#

当 backup 接管时：

1
1. backup 使用自己的 database copy 和从 primary 收到的 log 执行 recovery
2
2. redo completed transactions
3
3. rollback incomplete transactions
4
4. backup 成为新的 primary

旧 primary 恢复后，如果要重新接管：

1
1. 旧 primary 从当前 primary 接收 redo logs
2
2. 应用所有更新
3
3. 追上当前状态后才能重新成为 primary

Hot-Spare#

为了减少 takeover delay，可以使用 Hot-Spare（热备份）。

特点：

• backup 持续处理 primary 发来的 redo log
• 本地持续应用更新
• primary 失败后，只需要 rollback incomplete transactions
• 接管速度非常快

Hot-spare 的本质是把 recovery 工作提前做：backup 不是等 primary 坏了才开始读 log，而是在日志到达时持续 redo。故障发生时剩下的主要工作是检测故障、回滚未完成事务、切换入口。

One-safe / Two-very-safe / Two-safe#

Remote backup 中有一个核心权衡：

commit 要不要等 backup 也收到 commit log？

1
primary 写入 commit log 后，事务立即 commit

1
commit log 同时写到 primary 和 backup 后，事务才 commit

1
如果 primary 和 backup 都 active：按 two-very-safe
2
如果只有 primary active：按 one-safe

为什么需要 Logical Undo#

高并发结构，例如 B+-tree，并发控制通常会提前释放底层锁。

例子：

• B+-tree insertion
• B+-tree deletion
• tuple insertion / deletion
• space allocation
• bank balance 上的 deposit / subtract 操作

问题：

一旦底层锁提前释放，其他事务可能已经修改同一数据结构。此时不能简单恢复 old value，否则会覆盖其他事务的正确更新。

因此需要 logical undo。

1
把数据项恢复为 old value

1
用一个反向操作撤销原操作

Redo 仍然使用 Physical Redo#

即使 undo 使用 logical undo，redo 通常仍然使用 physical redo。

原因：

崩溃恢复刚开始时，磁盘上的数据库状态可能缺少 operation consistency，可能只包含某个操作的一部分影响。此时执行 logical redo 很复杂。

所以：

• undo 可以 logical
• redo 仍然 physical

这不会影响 early lock release。

直觉：redo 要把系统带回 crash 发生时的历史状态，必须重演当时已经发生过的物理变化；undo 是把未完成事务的语义效果取消，所以可以用反向逻辑操作实现。

Operation Logging#

逻辑操作的日志记录方式：

1
1. 操作开始：
2
   <Ti, Oj, operation-begin>
3

4
2. 操作执行过程中：
5
   正常写 physical redo + physical undo log records
6

7
3. 操作完成：
8
   <Ti, Oj, operation-end, U>

其中：

• Oj 是操作实例的唯一标识
• U 是逻辑撤销所需的信息

向索引 I9 插入 (K5, RID7)：

1
<T1, O1, operation-begin>
2
...
3
<T1, X, 10, K5>
4
<T1, Y, 45, RID7>
5
<T1, O1, operation-end, (delete I9, K5, RID7)>

解释：

• 中间的 <T1, X, 10, K5>、<T1, Y, 45, RID7> 是 physical logs
• 如果操作没完成就 rollback，用 physical undo
• 如果操作完成后 rollback，用 operation-end 里的 (delete I9, K5, RID7) 做 logical undo

Rollback with Logical Undo#

事务 Ti rollback 时，逆序扫描 log。

1
<Ti, X, V1, V2>

1
X = V1
2
写 <Ti, X, V1>

1
<Ti, Oj, operation-end, U>

1
1. 用 U 执行 logical undo
2
2. logical undo 过程中产生的更新正常记录 log
3
3. 完成后写 <Ti, Oj, operation-abort>
4
4. 跳过该操作之前的所有 physical log，直到 <Ti, Oj, operation-begin>

1
跳过前面属于该操作的 log，直到 <Ti, Oj, operation-begin>

遇到 Ti start#

1
写 <Ti abort>
2
rollback 完成

---

Failure Recovery with Logical Undo#

整体仍然是两阶段：

1. Redo phase：从最后一个 checkpoint 后开始，物理重做所有更新，重复历史
2. Undo phase：对 undo-list 中未完成事务执行 rollback

区别在于 undo phase 处理 log 时，要按 logical undo 的规则：

• 完成的 operation 用 U logical undo
• 未完成的 operation 用 physical undo
• 已经有 operation-abort 的 operation 不再重复撤销

1
<T1 start>
2
<T1, O1, operation-begin>
3
...
4
<T1, X, 10, K5>
5
<T1, Y, 45, RID7>
6
<T1, O1, operation-end, (delete I9, K5, RID7)>
7
<T1, O2, operation-begin>
8
<T1, Z, 45, 70>
9

10
-- T1 Rollback begins here --
11

12
<T1, Z, 45>          -- 对未完成 O2 做 physical undo，redo-only log
13
<T1, Y, ..., ...>    -- 对已完成 O1 做 logical undo 时产生的正常 redo records
14
...
15
<T1, O1, operation-abort>
16
<T1 abort>

ARIES 的核心改进#

相比前面的简化算法，ARIES 的主要改进包括：

1. 使用 LSN（Log Sequence Number） 标识每条 log record
2. 在 page 中保存 PageLSN，判断哪些更新已经反映到该 page
3. 支持 physiological redo
4. 使用 Dirty Page Table 避免不必要的 redo
5. 使用低开销 fuzzy checkpointing，checkpoint 时不强制写出所有 dirty pages

Physiological Redo#

Physiological redo 的含义：

物理定位 page，但 page 内部的动作可以是逻辑操作。

例子：删除 page 中一条 record。

如果用纯 physical redo：

• 删除后可能需要移动很多 records 填补空洞
• 需要记录 page 中大量字节的 old/new values

如果用 physiological redo：

• log 只需记录“在这个 page 中删除某条 record”
• redo 时在指定 page 内执行删除动作

优点：

• log 更小
• 恢复效率更高

要求：

• page output 必须是 atomic 的
• incomplete page output 要能通过 checksum 检测
• 如果 page 半写，需要按 media failure 处理

LSN 与 PageLSN#

1
1. X-latch page
2
2. 写 log record
3
3. 更新 page
4
4. 把该 log record 的 LSN 写入 PageLSN
5
5. unlock page

1
必须先 S-latch page

1
如果 PageLSN >= 某 log record 的 LSN
2
说明该 log record 的影响已经在 page 上
3
redo 时跳过

CLR#

ARIES 使用 CLR（Compensation Log Record） 记录 recovery / rollback 期间执行的 undo 动作。

CLR 是 redo-only：

CLR 记录的动作永远不需要再 undo。

普通 log record 包含：

1
LSN, TransID, PrevLSN, RedoInfo, UndoInfo

CLR 包含：

1
LSN, TransID, UndoNextLSN, RedoInfo

其中：

• PrevLSN：同一事务上一条 log record 的 LSN
• UndoNextLSN：下一条需要被 undo 的更早 log record

UndoNextLSN 的作用：

如果 recovery 期间再次崩溃，重启后可以跳过已经 undo 过的 log records，避免重复 undo。

Dirty Page Table#

DirtyPageTable 记录 buffer 中已经被更新但磁盘版本未必最新的 pages。

每个 dirty page 记录：

• PageLSN
• RecLSN

其中：

RecLSN 是该 page 变 dirty 后第一条可能还没反映到磁盘的 log record 的 LSN。

设置方式：

1
当 page 第一次进入 DirtyPageTable 时，RecLSN = 当前 update log record 的 LSN

作用：

• recovery 时不必从更早的 log 开始 redo
• 对某个 page 来说，早于 RecLSN 的 log 一定不需要 redo

ARIES Checkpoint#

ARIES checkpoint record 包含：

• DirtyPageTable
• active transaction list
• 每个 active transaction 的 LastLSN

同时，磁盘固定位置保存：

1
last completed checkpoint log record 的 LSN

ARIES 的 checkpoint 特点：

checkpoint 时不强制写出 dirty pages。

dirty pages 在后台持续写出。

因此 ARIES checkpoint 开销很低，可以频繁执行。

这里和基本 checkpoint 的差别必须分清：

• 基本 checkpoint：checkpoint 时强制刷出 dirty pages
• ARIES checkpoint：只把 DirtyPageTable 和 active transaction list 写进 checkpoint log，dirty pages 后台持续写出

所以 ARIES 中 RedoLSN 可能早于 checkpoint log record 的 LSN，因为 checkpoint 时 dirty page 并没有被强制写盘。

ARIES Recovery#

ARIES recovery 分三遍：

1. Analysis pass
2. Redo pass
3. Undo pass

1
1. 从最后一个完整 checkpoint 开始
2
2. 读取 checkpoint 中的 DirtyPageTable
3
3. RedoLSN = DirtyPageTable 中所有 RecLSN 的最小值
4
   - 如果没有 dirty pages，则 RedoLSN = checkpoint record 的 LSN
5
4. undo-list = checkpoint 中的 active transaction list
6
5. 读取这些事务的 LastLSN
7
6. 从 checkpoint 向前扫描到 log 末尾：
8
   - 发现新事务 log，加入 undo-list
9
   - 发现 update log，若 page 不在 DirtyPageTable 中，加入并设置 RecLSN
10
   - 发现 transaction end log，删除该事务
11
   - 持续更新每个事务的 LastLSN

1
DirtyPageTable：哪些页的磁盘版本可能不是最新
2
Active transaction list / undo-list：哪些事务 crash 时还没结束

1
1. 如果 page 不在 DirtyPageTable 中：跳过
2
2. 如果 log record 的 LSN < page 的 RecLSN：跳过
3
3. 否则 fetch page
4
4. 如果 page.PageLSN < log record.LSN：redo
5
5. 否则跳过

1
repeating history

Undo pass#

Undo pass 对 analysis 得到的 undo-list 中事务做 rollback。

优化方式：

1
1. 每个事务维护 next LSN to undo
2
2. 初始值为该事务 LastLSN
3
3. 每次选择最大的 LSN 进行 undo
4
4. 如果是普通 log record：
5
   - 执行 undo
6
   - 写 CLR
7
   - next = PrevLSN
8
5. 如果是 CLR：
9
   - next = UndoNextLSN
10
   - 跳过中间已经 undo 过的 records
11
6. 所有事务都到达 start 后，写 end / abort，undo 完成

CLR 保证：

• rollback 过程中崩溃也没关系
• 重启后不会重复 undo 已经 undo 过的动作

ARIES 的其他特性#

Index redo 可以省略#

主存数据库恢复 relation 后，index 往往可以很快重建。

因此很多系统：

• 不为 index updates 做 redo logging
• 仍然需要 undo logging 支持事务 abort
• 这些 undo logs 可以只保存在内存中，不一定写入 stable log

只做 redo logging#

一些主存数据库通过以下方式减少 logging：

• 周期性 checkpoint
• 确保未提交数据不写入 disk
• 或使用多版本记录，避免 in-place updates

恢复时：

1
1. 加载 checkpoint
2
2. redo checkpoint 后的提交更新
3
3. 清理未提交版本

并行恢复#

主存数据库恢复时，整个数据库需要重新载入，恢复速度非常关键。

优化方式：

• 将数据分区
• log records 也按分区组织
• 多个 CPU cores 并行恢复不同分区

NVRAM 补充#

Non-volatile RAM / Storage Class Memory 支持类似 RAM 的随机访问，同时断电后不丢失内容。

对恢复的影响：

• 可以减少甚至避免 redo logging
• 仍可能需要 undo logging 处理事务 abort
• 需要考虑 NVRAM 上原子更新的问题