数据库概论.陈立军.09.恢复控制(3)

Posted on In Views:
恢复控制、ARIES 算法

恢复控制

ARIES 算法

  • 相当复杂的算法
  • A Transaction Recovery Method Supporting Fine-Franularity Locking and Partial Rollbacks Using Write-Ahead Logging

日志类型

  • Redo Log 记录了提交更新操作所需要的信息
  • Undo Log 记录了回滚更新操作所需要的信息
  • 使用 Page-oriented 级的 Redo
    • Redo 物理级（页级）
  • 使用 Logical 级的 Undo
    • Undo 逻辑级
  • 实际数据库中日志是以页为单位记录的，而不是数据项级别的
    • 数据项 <事务, 修改前的值, 修改后的值>
    • 页级 <事务, 页面, 叶偏移, 修改前的值, 修改后的值>
  • CLR（Compensation Log Record）：补偿日志
    • 对于一条 undolog，这个 CLR 在 Page-oriented 级记录了如何更改一个页面来达到 Undo 的效果
    • 将逻辑级的 undo 操作转化成物理页级的操作

数据结构

  • LSN
    • 在增长的日志记录空间中的日志记录的第一个字节的地址
    • 这是一个单调递增的数值
  • Type
    • 表示一个记录是补偿日志（'compensation'）
    • 正常更新记录（'update'）
    • 一个提交协议相关记录（例如 'prepare'）
  • TransID
    • 事务的标记，如有，则写入到日志记录中
  • PrevLSN
    • 本事务的前一条日志记录的 LSN
    • 对该事务的第一条日志记录而言是0，因此不需要用一条日志记录显式地表示一条事务的开始
  • PageID
    • 只在 Update 和 compensation 类型的记录中出现，它记录本记录所更新页面的标记
  • Data
    • 这是描述欲更新的 redo 和/或 undo 数据
    • CLR 只包含 redo 信息，因为它们不能 undo
  • UndoNxtLSN
    • 只在 CLR 中出现，它指的是回滚阶段要处理的下一个本事务的日志记录，也即 UndoNxtLSN 是当前日志正在补偿的日志记录的 PrevLSN 的数值
  • 页面结构
    • 数据库的每个页都有 page_LSN 域
    • 它包含对该页面所做的最近更新日志记录的 LSN
    • redo 恢复的时候如果发现修改页的 LSN 比当前操作的 LSN 要大，则可以直接跳过（这个修改已经反映到页面上了）
    • 注意算法是以页为单位，以页为单位向磁盘上刷数据

事务表

  • 记录活跃事务的状态
  • TransID：事务的ID
  • State：事务的提交状态
  • LastLSN：事务所写的最后一条LSN
  • UndoNxtLSN：在回滚阶段下一个记录的LSN
    • 如果本事务的最近日志记录是一个可 undo 的非 CLR 记录，这个字段的值就会被设为 LastLSN
    • 如果最近日志记录是 CLR，该字段就设为此 CLR 的 UndoNxtLSN 的值

脏页表

  • 包含一个在数据库缓冲区中已更新页的列表，它为每一页保存其 PageID 和一个称为RecLSN 的字段
  • RecLSN 用于标识日志记录，也即引起该页变脏的第一个日志记录的 LSN
  • 当一页被插入到脏页表时，RecLSN 被设置成日志的当前末尾
  • 只要页被写入磁盘，该页就被从脏页表中移除

检查点日志记录

  • 包含脏页和活动事务的列表，同时记录每个事务的LastLSN

三个原理

  • 先写日志
    • 在将更新的数据库对象的修改写入磁盘之前，先将对应的日志记录写入稳存
  • 重做时重复历史
    • 在崩溃后进行重新启动时，重做崩溃前的所有操作，使系统恢复到崩溃时的状态，然后回滚崩溃时还在执行的事务已完成的操作
  • 恢复修改的记录数据
    • 在回滚某些事务时，如果出现对数据库的改变，则需要在日志中记录这些改变，保证在重复进行重新启动时不需要重复这些操作

三个过程

  • 分析过程
    • 决定哪些事务要undo，哪些页在崩溃时是脏的，以及 redo 应从哪个 LSN 开始
    • 丛最近的检查点开始
  • Redo 过程
    • 从分析过程决定的位置开始，执行 redo，重复历史，将数据库恢复到发生崩溃前的状态
  • Undo 过程
    • 回滚在发生崩溃时那些不完整的事务

分析过程

  • 找到最后完整检查点日志记录，从该记录读入脏页表
  • 从检查点继续向前扫描，每找到一个不在 undo-list 中的事务日志记录，就将其添加到 undo-list，每找到一个事务的 end 日志记录，就将其从 undo-list 中删除
  • 只要发现一个更新页的日志记录，如果该页不在脏页表上，就将它添加进脏页表，并设置该页的 RecLSN 为该日志记录的 LSN
  • 将要被 undo 的事务列表 undo-list 设置为检查点日志记录中的事务列表及其 LastLSN
  • 将 RedoLSN 设置为脏页表中页的 RecLSN 的最小值，如果没有脏页，就将其设置为检查点日志记录的 LSN

Redo 过程

  • 通过重演所有没有反映在磁盘页上的动作来重复历史
  • Redo 过程从 RedoLSN 开始向前扫描日志，该点之前的日志记录已经反映在磁盘数据库页上
  • 只要找到一个 update 日志记录，它就执行如下动作：
    • 如果该页不在脏页表中（说明更新已经写到磁盘上了），或者该 update 日志记录的 LSN 小于脏页表中该页的RecLSN，Redo过 程就跳过该日志记录
    • 否则从磁盘调出该页，如果其 PageLSN 小于该日志记录的 LSN，重做该日志记录，修改 PageLSN 为该日志的 LSN

Undo 过程

  • Undo 过程反向扫描日志，取消所有 undo-list 中的事务
  • 如果找到一个 CLR，它用 UndoNextLSN 字段跳过一个已经回滚了的事务日志。否则，它用事务日志的 PrevLSN 字段查找下一个要被撤消的事务日志
  • 每当一个 update 日志记录被用于撤消，Undo 过程产生一个包含 undo 执行动作的 CLR，并将 CLR 的 UndoNextLSN 设置为 update 日志记录的 PreLSN 值