Recovery System¶

Log-Based Recovery¶

Log 由一系列 Log Records 组成，维护在稳定存储中:

• 当事务 \(T_i\) 开始时，写入记录 <T_i, start>
• 在事务 \(T_i\) 执行 WRITE(X) 前，写入记录 <T_i, X, V_1, V_2>
  • 其中 V_1, V_2 分别是数据项 X 写入前后的值
• 当事务 \(T_i\) 结束时，写入记录 <T_i, commit>

Deffered Database Modification¶

Deffered Database Modification 将所有写操作都推迟到 Partial Commit 阶段，即事务执行过程中只记录 Log；事务 Commit 后再读 Log 并将需要写入的内容执行。

假定 DB Crash 时，存储在 Stable Storage 中的 Log 分别为如下三种情况：

• 【a】 不需要做 REDO 操作，因为没有任何数据被实际写入
• 【b】 需要 REDO(T_0)，因为 \(T_0\) 已经 COMMIT 了，但它的数据还没成功写入
• 【c】 需要 REDO(T_0), REDO(T_1)

Immediate Database Modification¶

Immediate Modification 允许事务在未提交之前就将更新写入 Buffer 或者 Disk 中，但是仍然需要注意 Log Record 的写入必须在数据项的写入之前。

由于将更新后的 Block 写回磁盘相对耗时，它们的实际写入时间可能出现在该事务 COMMIT 之后，例如：

在如上背景下，我们将数据库的恢复分为两个操作：

• 【Undo】 从事务 \(T_i\) 的最后一个记录开始，将对应数据项的值都恢复到 old values
  • 如果记录只包含 <T_i, start> 不包含 <T_i, commit>
  • Undo 时，也要记录对应的日志
• 【Redo】 从事务 \(T_i\) 的第一个记录开始，将对应数据项的值都设置为 new values
  • 如果记录既包含 <T_i, start> 又包含 <T_i, commit>

在数据库运行过程中，我们会设置 CheckPoints，以防止数据库恢复需要读取的 Log 太多。

在执行 Checkpointing 时：

• <1> 将主存中的所有 Log Record 都写入磁盘
• <2> 将所有被更新过了的 Buffer Blocks 都写入磁盘
• <3> 写入一条日志 <CheckPoint L> 到磁盘
  • L 是执行 CheckPoint 时还在活跃的事务列表

在执行恢复时，我们首先找到记录 <CheckPoint L>，只有 L 以及位于检查点之后开始的事务需要 Redo 和 Undo。

Recovery With Concurrent Transactions¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

undo_list = []
redo_list = []
log_ptr = the end of log
while (*log_ptr != <checkpoint L>):
    switch (log_ptr->type):
        case <T_i, commit>:
            redo_list.append(T_i)
        case <T_i, start>:
            if not T_i in redo_list:
                undo_list.append(T_i)
        case <T_i, abort>:
            undo_list.append(T_i)
for txn in L:
    if not T_i in redo_list:
        undo_list.append(T_i)

在得到两个列表后，先从后向前 Undo，再从 Checkpoint 向后 Redo。

Buffer Management¶

主存和 Stable Storage 交互的最小单位时 Block，而一个 Log Record 的大小远小于一个 Block，我们不可能每次都直接将单个 Log 写入磁盘。通常，Log 都缓存在主存中，只有如下情况才会输出到磁盘中：

• <1> Blocks of log records in buffer are full
• <2> Log Force operation is executed
  • checkpoint happens
  • 如果采用 Force Policy 恢复算法，一个事务 COMMIT 时也要将其所有 LOG 都强制写回

Database Buffer 可以在 Real Main Memory 或者 Virtual Memory 中执行，它们各有优劣：

Advanced Recovery Techniques*¶

对于 update log，我们为其包裹一层逻辑操作日志，其中 \(O_j\) 是该操作实例的 unique identifier：

1
2
3

<T_i, O_j, operation-begin>
<T_i, A, 100, 300>
<T_i, O_j, operation-end, (A, -200)>

在 operation-end 里包含了 Logical Undo Information，当 crash 发生，需要 undo 这个事务的时候，如果能够读取到这个日志，则使用 Logical Undo，忽略中间的物理日志；如果只能找到 operation-begin，但找不到对应 operation-end，则使用 Physical Undo。

Undo 时，书写的 Undo 日志格式为：

1

<T_i, O_j, operation-abort>

ARIES 算法¶

Data Structure¶

我们之前提到的恢复算法其实都是基于 ARIES 算法简化的，它们去除了 Optimization 部分。跟它们相比，ARIES 算法有如下特征：

• <1> 使用 Log Sequence Number(LSN) 来标志 Log Records
  • LSNs 以 Page 的形式存储
• <2> Physiological Redo
  • 是介于物理和逻辑 Redo 中的策略，它以物理的方式定位受影响的 Page，以逻辑的方式记录业内的操作
  • 相比于物理 Redo 需要记录整个 Page 的字节变化，Physiological Redo 只需要记录页内编号 + slot 操作，节省大量空间
  • Warning: 要求 Page 的写回是原子操作
• <3> 维护 Dirty Page Table 来避免不必要的 Redo 操作
• <4> 使用 Fuzzy Checkpoint，在检查点只记录脏页的相关信息，不要求脏页写回

我们在 Page 的首部中还需额外维护 PageLSN，用来存储最后一条影响该 Page 的日志的 LSN。在恢复阶段，LSN 值不超过 PageLSN 的日志记录不会在该页上执行，从而避免重复的 Redo。

一个普通的 Log Record 的格式如下：

1
2
3

+-----+---------+---------+----------+----------+
| LSN | TransID | PrevLSN | RedoInfo | UndoInfo |
+-----+---------+---------+----------+----------+

在之前的恢复算法中，Undo 阶段时我们需要为所有被 Undo 的日志写入对应的 Undo Log。在 ARIES 中，该日志称为 Compensation Log Record(CLR)，是一个 Read-Only 的日志记录，并且有一个特殊的字段 UndoNextLSN，用于指向下一个需要执行 Undo 操作的日志：

1
2
3

+-----+---------+-------------+----------+
| LSN | TransID | UndoNextLSN | RedoInfo |
+-----+---------+-------------+----------+

Dirty Page Table 记录仍在 Buffer 中、已经被更新过的 Page 的信息，包括：

• PageLSN
• RecLSN LSN 小于 RecLSN 的日志都已经生效且写回磁盘中了
  • 当一个 Page 被插入脏页表中时，设置 RecLSN = PageLSN（更新前一刻的）

只要一个 Dirty Page 被写入磁盘，则从脏页表中移除该页。

在 CheckPoint，记录当前 Dirty Page Table 和当前正在活跃的事务。对于每一个活跃事务，记录它们写入的最后一个 Log Record 的 LSN，记为 LastLSN。

脏页不必在 CheckPoint 写回，它们在后台持续写回，因此 CheckPoint 的消耗较小，可以相对更频繁的设置。

Recovery Algorithm¶

ARIES 的恢复算法分为三个阶段：分析阶段、Redo阶段、Undo阶段。

• <1> Analysis pass
  • 从最后一个 CheckPoint 开始
  • 读取 Dirty Page Table
    • 设置 RedoLSN = min RecLSN（脏页表中的最小 RecLSN），如果脏页表为空，则设置为 CheckPoint 的 LSN
    • 初始化 Undo List 为 CheckPoint 中记录的活跃事务
    • 读取 Undo List 中每一个事务的最后一条 Log 的 LSN
  • 从 CheckPoint 开始正向扫描
    • 如果发现了不在 Undo List 中的事务则加入 Undo List
    • 如果发现了 Update Log Record，如果其修改的 PageID 不在里面，则将其加入脏页表中，并设置其 RecLSN 为该日志的 LSN，用于 Redo
      • 无论在不在，都要修改脏页表的 PageID 部分
    • 如果发现了事务的 End Log，则将其从 Undo List 中移除
    • 扫描过程中记得记录每一个事务的最后一条日志的 LSN，用于 Undo
• <2> Redo pass
  • 从 RedoLSN 开始正向扫描 ，当发现更新记录的时候
    • 如果对应 Page 不在脏页表中。或者这一条记录的 LSN 小于页面的 RecLSN 就忽略这一条
    • 否则从磁盘中读取这一页，如果磁盘中得到的这一页的 PageLSN 小于该 Log，就 redo，否则就忽略这一条记录
• <3> Undo pass
  • 从分析阶段获得的每个事务最后一条日志的 LSN 开始，接下来每一步都选取这之中 LSN 最大的日志开始 Undo
  • 在 undo 一条记录之后
    • 对于普通的记录，将 NextLSN 设置为 PrevLSN
    • 对于CLR记录，将 NextLSN 设置为 UndoNextLSN
      • 这之间的日志将被跳过，不会执行 Undo