故障分类和存储器

[1] 故障分类

1. 事务故障: 逻辑错误(内部条件, 非法输入、找不到数据、溢出、超出资源限制); 系统错误(死锁等导致事务无法继续执行)
2. 系统崩溃: 硬件故障或数据库软件呢、操作系统漏洞, 导致易失性存储器内容丢失, 但是非易失性存储器完好无损
3. 磁盘故障: (破坏非易失性存储器内容), 可以从三级介质的归档备份恢复

[2] 存储结构

• 易失性存储器(主存, cache): 计算机崩溃时丢失
• 非易失性存储器(磁盘, 闪存, 光盘, 磁带): 磁盘崩溃时丢失
• 稳定性存储器: 永不丢失, 可以复制非易失性存储器介质并采用独立故障模式

[3] 稳定存储器
必须支持在线访问的稳定存储器与磁盘镜像或者其他形式的提供冗余数据存储的RAID接近
对于离线或归档的情况, 稳定性存储器可以由存储在物理安全位置的数据的多个磁盘备份构成

数据访问

[1] 磁盘中的某些错误可以由存储在每个块中的校验和检测
恢复过程中比较每一对相应块开销太大——解决方案: 使用少量非易失性RAM, 跟踪正在进行的对应块的写操作; 恢复时只比较正在写的块

[2] 物理块: 磁盘上的块; 缓冲快: 临时位于主存的块

[3] input: 物理块B到主存
事务T的私有工作区用于保存T当问及更新的所有数据项X的拷贝, 在事务初始化时由系统创建, 事务提交或中止时由系统删除
T通过在其工作区和系统缓冲区之间传送数据, 与数据库系统交互

1. read将X值赋给局部变量x, 如果X所在块B不在主存中, 需要input(B)
2. write将局部变量x值赋给缓冲区块中数据项X, 如果X所在块B不再驻村中, 需要input(B)

[4] output: 缓冲块B到磁盘, 替换磁盘相应物理块
强制输出: 缓冲区管理器需要内存空间; 数据库系统希望将B的变化反映到磁盘
output(B)不需要在write后立即执行, 因为B可能包含其他仍在被访问的数据项

恢复与原子性

[1] 更新日志记录有如下字段: 事务标识、数据项标识(数据项在磁盘位置, 数据项驻留块的块标识和块内偏移量)、旧值、新值

[2] 事务修改数据项的步骤

1. 事务在主存中自己私有的部分执行某些计算
2. 事务修改主存磁盘缓冲区中包含该数据项的数据块
3. 系统执行output操作后数据库块写到磁盘中

[3] 延迟修改: 事务直到提交都没有修改数据库, 事务执行的所有write延迟到事务提交时执行
开销: 事务需要创建(更新过的所有数据项的)本地拷贝; 如果一个事务读他更新过的数据项, 必须从本地拷贝中读
日志记录不需要包含已更新的数据项的旧值

立即修改: 数据库修改在事务仍然活跃时发生

[4] 事务回滚: 从后往前扫描日志
利用旧值字段可以撤销已经输出到数据库中的修改, 作为撤销的一部分, 要使用redo-only日志要记录执行的更新(redo-only日志不包含更新的数据项的旧值)
undo操作之后需要写一个abort日志记录

[5] 系统发生崩溃之后:

1. 重做阶段: 正向扫描日志重放所有事务的更新, 如果日志包括 [start] 以及 [commit或者abort], 需要redo (abort: 如果日志包括abort, 意味着有redo-only日志, 需要对T的修改进行撤销) redo将将T更新过的数据项的值设置成新值
   • 如果找到redo-only或者正常日志记录, 则redo这个操作
   • 如果遇到start, 把T加入undo-list
   • 如果遇到abort或者commit, 把T从undo-list中去掉
2. 撤销阶段: 反向扫描日志进行回滚
   如果日志包括start记录, 但不包括commit或abort, 需要undo
   • 遇到undo-list中的事务记, 则undo, 并向日志中写redo-only记录
   • 如果遇到start, 往日志中写一个abort, 并把T从undo-list中去掉
   • undo-list变为空表, 撤销阶段结束

检查点

[1] 检查点

1. 当前位于主存的所有日志记录输出到稳定存储器
2. 所有修改的缓冲块输出到磁盘
3. 将一个日志记录checkpoint L输出到稳定存储器, L为检查点时正活跃的事务列表

[2] 模糊检查点: 允许检查点记录写入日志后, 修改过的缓冲块写到磁盘前开始做更新
如果系统在所有页面写完前崩溃, 磁盘上的检查点可能不完全——解决方案: 将最后一个完全检查点记录在磁盘上的固定位置last_checkpoint, 写入checkpoint时不更新该信息, 在写checkpoint记录前创建所有修改过的缓冲区块的列表, 只有在该列表中的所有缓冲块都输出到磁盘上以后, last_checkpoint信息才更新

缓冲区管理

[1] 日志缓冲区

1. 日志记录commit输出到稳定存储器后, 事务进入提交状态
2. 日志记录commit输出到稳定存储器前, 事务有关的所有日志记录必须输出到稳定存储器
3. 主存中的数据块输出到数据库前, 所有鱼数据块中数据有关日志记录必须输出到稳定存储器

[2] 写前日志WAL: undo信息已经输出到稳定存储器中, 而redo信息允许以后再写
WAL的刷新策略如下(窃取/非强制):
所有的日志记录必须在它对应的行数据页被写入磁盘之前写入稳定存储(保证原子性)
所有的日志记录必须在其所属的事务提交之前写入稳定存储(保证持久性)

[3] 数据库缓冲

[4] 闩锁封锁方法(非两阶段)
当一个块要输出时:

1. 获取排他锁, 确保没有任何事物正在进行写操作
2. 日志记录输出到稳定存储器
3. 块输出到磁盘
4. 块输出完成后, 释放排他锁

保证检查点进行过程中缓冲块不更新, 而且没有新的日志记录产生

1. 要求在检查点操作开始之前必须获得所有缓冲块的排他锁以及对日志的排他锁
2. 检查点操作完成后释放锁

[5] 不断在缓冲块间循环, 将修改过的缓冲块输出到磁盘。好处:
缓冲区中的脏块数目减少, 检查点过程中需要输出的块数目减少
需要从缓冲区逐出一个块时, 不脏的块可以逐出, 输入马上可以进行, 不必等待输出完成

[6] 管理数据库缓冲区

• 数据库系统保留部分主存作为缓冲区, 不让操作系统管理——缺点: 限制主存使用灵活性, 所有应用都不能利用所有可用内存
• 操作系统的虚拟内存中实现缓冲区, 让操作系统决定哪个缓冲块在什么时候强制输出到磁盘——缺点: 应该由数据库系统强制输出缓冲块, 否则会导致额外的数据到磁盘的输出

[7] 主存储器中包括: 日志缓冲区、数据库缓冲区、系统缓冲区
系统缓冲区由系统目标码页面和事务的局部工作区域

非易失性存储器数据丢失的故障

[1] 归档转储: 周期性将数据库内容转储到稳定存储器, 要求不能有事务处于活跃状态
恢复时可以利用最近一次转储将数据库复原到磁盘, 然后根据日志, 重做最近一次转储后所做的动作, 不必执行任何undo操作

[2] SQL转储: 将SQL的DDL和insert语句写到文件中, 可以重执行来重新创建数据库
用于将数据库已知道数据库另一个实例或数据库软件另一个版本, 因为物理位置或布局可能不同

逻辑undo操作

[1] 恢复技术支持高并发封锁技术: 用于B+树并发控制的封锁技术, 允许提前释放通过插入或删除操作获得的低级别的锁(允许别的事务其他的这类操作可以执行)
低级别的锁被释放后, 不能进行物理undo, 进行逻辑undo(如: 用删除对插入做undo)
事务保持高级别的锁确保并发的事务不会执行这样的动作, 可能导致一个操作的逻辑undo不可能

[2] 回滚过程: 从后往前扫描日志

1. 物理日志按之前处理
2. 遇到operation-end, 通过使用undo信息U回滚, 并将执行的更新记入日志(原因: 如果逻辑undo发生崩溃, 恢复时必须完成逻辑undo, 因此会使用物理undo信息撤销早先的undo部分的影响, 然后再执行逻辑undo), 回滚最后产生operation-abort记录
   随着反向扫描继续进行, 跳过T的所有日志记录直到遇到operation-begin (保证操作完成后物理日志中的旧值不会用来进行回滚)
3. 遇到operation-abort, 跳过前面所有记录直到operation-begin
   说明回滚 事务事先已经部分回滚, 因为逻辑操作不是幂等(操作执行一次和执行多次结果相同), 因此逻辑undo不能多次进行。如果前面事务部分回滚, 日志记录必须跳过, 防止同一操作多次回滚
4. 遇到start, 回滚完成, 添加abort记录

ARIES

提供更大并发性, 削减日志开销, 最小化恢复时间
基于历史, 允许逻辑undo操作
不断清洗页, 从而不需要在检查点清洗所有页

数据结构

[1] 日志顺序号(LSN)由一个文件号以及在该文件中的偏移量组成——减少恢复所花时间

[2] 每一页维护一个页日志顺序号(PageLSN), 每当一个更新操作发生在某页上时, 该操作将其日志记录的LSN存储在该页的PageLSN域中
在恢复的撤销阶段, LSN值小于或等于PageLSN值的日志记录将不在该页上执行, 因为它的动作已经在该页上了

[3] 每个日志记录包含同一事务的前一日志记录的LSN, 放在PrevLSN中, 使得一个事务可以由后向前提取, 而不必读整个日志
事务回滚中会产生一些特殊的redo-only的日志, 称为补偿日志记录(CLR)

[4] CLR中额外的称为undoNextLSN的字段, 记录下一个需要undo的日志的LSN (用于防止重复undo, 保证undo的幂等性)

[5] 脏页表: 包含一个在数据库缓冲区中已经更新的页的列表, 为每一页保存其PageLSN和一个称为RecLSN的字段
RecLSN用于标识已经实施于该页的磁盘上的版本的日志记录。当某页首次被放入脏页表中, 它的RecLSN值被设置为日志的当前末尾

[5] 模糊检查点日志记录: 包含脏页表和活动事务的列表

恢复算法

[1] 分析阶段: 决定哪些事务要撤销, 哪些页在崩溃时是脏的, 以及重做阶段应从哪个LSN开始
找到最后的完整检查日志记录，将该记录读入脏页表。将redoLSN设为脏页表中页的RecLSN的最小值
将undo-list初始设置为检查点日志记录中的事务列表, 从检查点正向扫描, 发现新的begin, 就加入; 发现end, 就删去
也记录undo-list每一个事务的最后一个记录, 在undo阶段使用
一旦有更新页的记录不在脏页表, 也加入脏页表

[2] redo阶段: 从分析阶段决定的位置开始, 执行重做, 将DB恢复到发生崩溃前的状态
找到一个更新日志记录: 如果该页不在脏页表中, 或者该更新日志记录的LSN小于脏页表中该页的RecLSN, 跳过
否则从磁盘中调出该页, 如果其PageLSN小于该日志记录的LSN, 就重做

[3] undo阶段: 这一阶段回滚在发生崩溃时那些不完全的事务
对日志进行一遍反向扫描, 对undo-list中的所有事务进行撤销
用分析阶段所记录的每一个事务的最后一个LSN来快速定位
每找到一个更新日志记录, 就用它来执行一个undo
产生一个包含undo的CLR, 并将该CLR的UndoNextLSN设置为该更新日志记录的PrevLSN
如果遇到一个CLR, 它的UndoNextLSN已经指明需要Undo的LSN, 且应该已经回滚

示例 & 图片来源: 图解数据库Aries事务Recovery算法

远程备份系统

主站点发生故障, 远程站点执行一定恢复动作, 然后接管事务处理
[1] 故障检测: 主站点和备份站点之间维持多条具有独立故障模式的通信线路, 防止通信线路故障使远程站点误以为主站点已发生故障

[2] 控制权移交: 原主站点从原备份站点收到redo日志, 应用到本地赶上更新, 之后主站点可以作为远程备份站点工作
如果控制权必须回传, 原备份站点可以假装发生故障, 主站点重新接管

[3] 恢复时间: 备份站点周期性处理redo日志并设计检查点
热备份: 备份站点不断处理redo记录并在本地更新

[4] 提交时间: 只有日志记录到达备份站点才能宣称事务已提交, 从而保证提交事务更新是持久的

• 一方保险: 事务提交日志写入主站点的稳定存储器, 事务就提交
• 两方强保险: 事务提交日志写入主站点和备份占地啊你稳定存储器, 事务就提交 (如果主站点或者备份站点的一个停工, 事务处理就无法进行)
• 两方保险: 如果只有主站点活跃, 事务日志记录只需要写入主站点稳定存储器