数据库恢复系统
19.1 故障分类
数据库系统必须在多种故障下保持事务的原子性与持久性。本章聚焦以下故障类型:
- 事务故障(transaction failure):由事务自身引发。
- 逻辑错误:违反完整性、除零、找不到记录等,事务无法正常完成。
- 系统错误:死锁、超时导致数据库主动中止事务;重新提交通常可成功。
- 系统崩溃(system crash):硬件失效、OS 错误或电源中断,导致主存内容丢失 ,但非易失性存储器上的内容通常完好。恢复系统需据此撤销未完成事务、重做已提交事务的丢失更新。
- 磁盘故障(disk failure):磁头刮痕、坏道、控制器损坏,导致非易失性存储上部分内容丢失。需借助归档或远程副本恢复。
- 灾难性故障(catastrophic failure):机房失火、洪水、地震,甚至整个数据中心不可用。需要远程备份或异地多副本。
针对不同故障,恢复方案的复杂度与代价不同。绝大多数商用系统同时具备日志、检查点、备份与远程复制机制。
故障模型的一般假设:
- fail-stop 假设:节点要么正确工作要么彻底停机;不会产生错误结果并向外发送。多数恢复算法基于此假设。
- fail-recover 假设:节点停机后可能重启并恢复处理;日志需存于非易失介质。
- 拜占庭故障:节点可能返回任意错误值或恶意消息;数据库通常不考虑,由更上层的共识协议(如 PBFT、区块链)解决。
19.2 存储器
按对故障的鲁棒性,存储层次可分为三类:
- 易失性存储器(volatile):CPU 寄存器、主存。系统崩溃即丢失。
- 非易失性存储器(non-volatile):磁盘、SSD、闪存。系统崩溃后仍保留数据,但仍可能因介质故障丢失。
- 稳定存储器(stable storage):抽象概念,指信息永不丢失的存储器。物理上通过多副本近似实现。
19.2.1 稳定存储器的实现
在真实硬件之上通过冗余与协议近似稳定存储:
- 多副本:至少两个物理副本,位于不同磁盘(或不同机柜、不同机房)。
- 原子写入协议:先写入副本 A,等待其成功持久化后再写入副本 B;恢复时检查两副本一致性并修复。
- 写时校验:使用校验和检测坏块,若某副本损坏用另一副本修复(RAID 1/5/6 提供类似能力)。
19.2.2 数据访问
数据块(page)在两处存在:
- 磁盘块(disk block):非易失性存储上的物理块。
- 缓冲块(buffer block):主存中缓冲池的对应副本。
事务通过 把包含数据项 的块读入缓冲,通过 把缓冲块写回磁盘。事务对数据项的读/写实际操作缓冲块中的副本。这就意味着,事务已"提交"不代表其修改已到磁盘——恢复系统必须在此错位中保证 ACID。
19.3 恢复与原子性
19.3.1 日志记录
恢复的核心是日志(log)。日志是一个顺序追加的记录序列,写入稳定存储。基本更新日志格式:
含义:事务 对数据项 执行了写操作; 是修改前值(旧值 / before image), 是修改后值(新值 / after image)。此外 还有:
- :事务开始;
- :事务提交;
- :事务中止;
- :检查点日志, 为活跃事务集。
一个完整的日志片段示例(转账事务 :,: 上加息):
LSN 100 <T0, start>
LSN 101 <T0, A, 1000, 950>
LSN 102 <T0, B, 2000, 2050>
LSN 103 <T0, commit>
LSN 104 <T1, start>
LSN 105 <T1, C, 700, 707>
LSN 106 <checkpoint {T1}> -- T0 已完成, T1 尚活跃
LSN 107 <T1, commit>
若系统在 LSN 105 之后、LSN 107 之前崩溃,则恢复算法需要 undo (回退 C=700);若崩溃发生在 LSN 107 之后,则 都需要 redo。
关键规则——先写日志(Write-Ahead Logging, WAL):在把某个更新对应的数据块刷入磁盘前,必须先把该更新的日志记录(含旧值)刷入稳定存储;在事务提交返回前,其提交记录必须先刷入稳定存储。
19.3.2 数据库修改
按缓冲刷盘时机可分两类:
- 延迟修改(deferred modification):事务提交前不修改磁盘上的数据库,仅在日志中记录;提交后统一 redo。日志只需 after image。
- 立即修改(immediate modification):事务执行时即可将修改块刷入磁盘,故需要 before image 以便 undo。
现代系统几乎都采用立即修改,配合 WAL 与检查点。这一选择的组合可用一张对照表概括:
| 缓冲策略 | 提交前是否可刷脏页 (steal) | 提交时是否强制刷回 (force) | 是否需要 undo | 是否需要 redo |
|---|---|---|---|---|
| no-steal / force | 否 | 是 | 否 | 否 |
| no-steal / no-force | 否 | 否 | 否 | 是 |
| steal / force | 是 | 是 | 是 | 否 |
| steal / no-force | 是 | 否 | 是 | 是 |
商用 DBMS 几乎都是 steal / no-force:并发性能与主存利用率最好,但需要完整的 redo/undo 支持——这正是本章重点讨论的方案。
19.3.3 并发控制与恢复
恢复方案的正确性依赖于并发控制协议提供的性质。严格 2PL(写锁保留到事务结束)保证在事务中止时不需级联回滚,也便于 redo/undo 单事务。若使用弱协议,恢复必须处理级联回滚或采用逻辑撤销(见 19.8 节)。
19.3.4 事务提交
事务提交流程:
- 事务把所有更新写入日志缓冲;
- 将 追加到日志缓冲;
- 强制将日志缓冲刷入稳定存储(fsync);
- 提交成功返回给用户;
- 修改的数据块可以延后异步刷回磁盘。
第 3 步是持久性的关键:只要日志中出现 commit 记录,事务的效果必能通过 redo 恢复。
19.3.5 使用日志来重做和撤销事务
- redo():从头顺序扫描日志,遇到 的更新记录 ,将 置为 。redo 必须幂等:多次执行结果相同。
- undo():从尾向头扫描日志,遇到 的更新记录,将 置为 ,并写补偿日志 (redo-only 日志);扫描到 后写 。undo 也必须幂等。
19.3.6 检查点
若每次崩溃都扫描整个日志,代价随时间线性增长。检查点周期性地做以下事:
- 暂停所有更新(或采用模糊检查点,见 19.5.4);
- 将日志缓冲刷入稳定存储;
- 将所有脏缓冲块刷入磁盘;
- 写 到日志, 为当前活跃事务集。
恢复时只需从最近的 checkpoint 记录向前找到最早未完成事务的 ,从该点起扫描即可。
19.4 恢复算法
19.4.1 事务回滚
单个事务 主动中止或被系统回滚时:
scan log backwards from tail:
for each record r of T_i:
if r is <T_i, X, V1, V2>:
X := V1 // undo the write
append <T_i, X, V1> // compensation log record (CLR)
if r is <T_i, start>:
append <T_i, abort>
stop
19.4.2 系统崩溃后的恢复
崩溃后重启,恢复分两遍:
通俗理解:redo 把数据库"重放"回崩溃瞬间的状态(包括那些尚未提交事务留下的修改);然后 undo 再把未提交事务的痕迹擦除。这样即使崩溃时刻 X 的物理值不确定,恢复终态也是确定的:所有已提交事务效果保留,所有未提交事务效果全部消除。
- redo 阶段(正向):
- 从最近的检查点开始扫描日志;
- 对遇到的所有更新记录(包括 CLR)无条件 redo。之所以是"无条件",是因为幂等 redo 比判断更简单,也避免遗漏。
- 维护 undo-list:见到 加入,见到 或 移除。
- undo 阶段(反向):
- 从日志尾向头扫描;
- 对 undo-list 中的每个事务 ,遇到其更新记录时执行 undo,写 CLR;
- 遇到 时写 并把 从 undo-list 移除;
- undo-list 为空时结束。
19.4.3 提交处理的优化
- 组提交(group commit):把多个事务的 commit 记录累积后一次 fsync 刷盘,摊薄同步开销。
- 异步刷盘 + 顺序号:日志顺序写盘,事务只需等待其 commit LSN 之前的日志刷盘完成。
- 并行日志:多个日志流,事务按分区归属不同流。
19.5 缓冲区管理
19.5.1 日志记录缓冲
日志先写入内存缓冲,再批量刷盘。刷盘时机:
- 事务提交时(同步);
- 日志缓冲满时;
- 后台周期性刷盘。
任何数据块刷盘前,其对应日志必须先刷盘(WAL 规则)。这要求缓冲管理器维护每个数据块的最大更新 LSN,刷盘前将日志刷到该 LSN。
将 WAL 规则形式化:设数据页 的最大更新 LSN 为 ,日志已刷盘的最大 LSN 为 。刷盘 前必须满足 ;事务提交返回给应用前,其 commit 记录的 LSN 必须 。这两条不变式保证了:任何在磁盘上出现的更新,都能在日志中找到 undo 与 redo 所需的信息;任何被承诺"提交成功"的事务,其效果都能被 redo。
19.5.2 数据库缓冲
数据库缓冲池管理数据块。若采用 steal(可以在事务未提交时将脏页刷盘):需要 undo 支持。若采用 no-force(提交时不强制刷盘):需要 redo 支持。绝大多数系统选择 steal + no-force,代价是 redo 与 undo 均需完整支持。
19.5.3 操作系统在缓冲区管理中的作用
DBMS 通常不完全信任 OS 的页面缓存与 fsync 语义,倾向于:
- 使用 O_DIRECT 或 raw device 绕过 OS 缓冲;
- 显式管理缓冲池大小与替换策略;
- 显式使用 fsync/fdatasync 确保日志落盘。
19.5.4 模糊检查点
普通检查点需暂停事务以刷盘,代价高。模糊检查点(fuzzy checkpoint) 允许在检查点期间继续处理事务:
- 写 ;
- 记录当前活跃事务列表 、脏页列表;
- 异步地把脏页刷回磁盘;不阻塞新事务;
- 全部脏页刷完后,写 。
恢复时以最近成功完成的 end-checkpoint 为起点。ARIES 的检查点即模糊检查点。
19.6 非易失性存储器上数据丢失的故障
若磁盘介质损坏,日志与数据可能一并丢失。防御手段:
- RAID(镜像、纠删码)在单机层面提供冗余;
- 归档与转储(dump):周期性地把整个数据库或增量转储到磁带、异地存储;
- 日志归档:把归档转储之后产生的日志也备份到独立介质;
- 恢复:先从最近的归档转储恢复数据库,再重放归档日志追赶。
按转储方式可细分为:
- 完全转储:一次性拷贝整个数据库,简单但代价大;
- 增量转储:仅拷贝自上次转储以来变动的数据块;
- 在线转储:不停机进行,需与日志配合以保证一致性;
- 一致性检查点转储:暂停事务、写检 查点、然后转储;开销最大,但恢复最简单。
企业级系统一般采用"每周一次完全转储 + 每日增量 + 归档日志"的组合,配合 3-2-1 备份策略(3 份副本、2 种介质、1 份异地)。
19.7 使用远程备份系统的高可用性
将日志实时发送到地理上分离的备份站点,主站崩溃时快速切换。按备份站点的准备程度可分:
| 类型 | 备份状态 | 切换时间 | 数据一致性 | 成本 |
|---|---|---|---|---|
| 冷备份(Cold standby) | 备用机器不运行 DB 实例,只保留数据副本 | 分钟~小时 | 视复制粒度,可能丢较多数据 | 低 |
| 温备份(Warm standby) | 备用实例运行,持续接收并 redo 主站日志,但不服务读 | 秒~分钟 | 备份滞后主站一小段日志 | 中 |
| 热备份(Hot standby) | 备用实例已完成 redo 并处于就绪,可承担只读查询;主站宕机时立即接管 | 秒级或亚秒级 | 若采用同步复制则不丢数据 | 高 |
复制方式:
- 异步复制:主站不等备份确认即提交;性能好但可能丢失最后若干事务。
- 同步复制:主站提交前必须等备份写入日志;持久性最强,但延迟高。
- 半同步:主站等至少一个备份确认即可提交。
主备切换需处理脑裂:主站 短暂断网时若备份提升为主站,可能出现双主。常用仲裁(quorum)与栅栏(fencing)机制。
衡量高可用能力的两大指标:
- RPO(Recovery Point Objective):可容忍的数据丢失时长——异步复制的 RPO 通常为秒到分钟,同步复制可做到 RPO=0;
- RTO(Recovery Time Objective):可容忍的服务不可用时长——热备份可做到秒级,冷备份可能长达数小时。
现代云数据库普遍采用"同步复制到同 AZ + 异步复制到跨 Region"的组合,兼顾正常时的低延迟与灾难时的可恢复性。
19.8 锁的提前释放与逻辑撤销操作
若严格 2PL 持锁到事务结束的代价过高(尤其是索引维护),可以提前释放锁,但需要逻辑撤销。
19.8.1 逻辑操作
逻辑操作(如"在 B+ 树中插入键 ")的物理表现依赖当前树结构,简单 restore before image 无法正确回滚。定义与之匹配的逆操作(如"从 B+ 树删除键 "),逆操作作用于当前状态即可回滚。
19.8.2 逻辑撤销日志记录
一次逻辑操作开始时写 ;操作期间照常记录物理 redo 日志;操作结束时写 , 描述逆操作。
19.8.3 有逻辑撤销的事务回滚
回滚 时:
- 遇到 operation-end:调用逆操作 ,跳到对应 operation-begin 之前继续扫描(跨越整个逻辑操作);
- 遇到普通更新记录:物理 undo;
- 遇到 operation-begin 且未匹配 end:表示操作未完成,按物理 undo 回滚其中的物理更新。
19.8.4 逻辑撤销中的并发问题
由于锁提前释放,逻辑撤销时数据结构状态可能已被其他事务修改。逆操作必须能作用于任意合法状态——例如"从 B+ 树删除 "不管当前树多深、 位于哪个叶子都能正确执行。这要求索引结构提供满足此性质的操作接口。
19.9 ARIES
ARIES(Algorithm for Recovery and Isolation Exploiting Semantics) 是 IBM 提出的经典恢复算法,为几乎所有现代关系数据库采用其思想。核心特征:物理 redo + 逻辑 undo、模糊检查点、CLR、幂等 redo。
19.9.1 数据结构
- LSN(Log Sequence Number):日志记录的单调递增编号,同时用作日志位置指针。
- PageLSN:每个数据页头存储写入该页的最后一条日志记录的 LSN;用于 redo 时判断"该更新是否已经在页面上"。
- DPT(Dirty Page Table)脏页表:缓冲池中已被修改但未刷盘的页面。每项
(PageID, RecLSN),RecLSN是首次将该页设为脏的日志 LSN。 - TT(Transaction Table)事务表:所有活跃事务的状态。每项
(TransID, Status, LastLSN),LastLSN是该事务最新一条日志的 LSN。 - CLR(Compensation Log Record):undo 时生成的补偿日志,含
UndoNextLSN指向下一条待 undo 的日志——保证 undo 幂等,避免"回滚过程中崩溃再次回滚"重复工作。
DPT / TT 结构示意:
| 表 | 字段 | 含义 |
|---|---|---|
| DPT | PageID | 脏页页号 |
| DPT | RecLSN | 该页第一次变脏时对应的日志 LSN,redo 从此开始才可能影响该页 |
| TT | TransID | 事务 ID |
| TT | Status | 状态:U(Undo 中)/ P(准备中)/ C(活跃)等 |
| TT | LastLSN | 该事务的最新一条日志 LSN |
19.9.2 恢复算法
ARIES 恢复由三阶段组成:
- 分析阶段(Analysis):从最近 begin-checkpoint 向后扫描:
- 遇 update 记录:将对应事务加入 TT,若目标页不在 DPT 则加入并
RecLSN = 当前 LSN; - 遇 commit / abort 记录:更新 TT 中事务状态;
- 结束时,DPT 中最小 RecLSN 即
RedoLSN。
- 遇 update 记录:将对应事务加入 TT,若目标页不在 DPT 则加入并
- 重做阶段(Redo):从 RedoLSN 起顺序扫描:
- 对每条更新记录 :若目标页不在 DPT,或
r.LSN < DPT[page].RecLSN,跳过(不可能影响该页);否则读取该页,比较PageLSN,若PageLSN < r.LSN则重放该更新并将 PageLSN 更新为 r.LSN。 - 这一阶段包括对 CLR 的 redo,因此保证部分回滚已完成的工作不会丢失。
- 对每条更新记录 :若目标页不在 DPT,或
- 撤销阶段(Undo):对 TT 中处于 U 状态的事务(未提交):
- 用优先队列按 LastLSN 递减处理;
- 每次取出 LSN 最大的事务,对其日志记录:
- 若是更新记录:执行 undo,写 CLR(
UndoNextLSN = 该记录的 PrevLSN),事务的下一个待 undo LSN 更新为 PrevLSN; - 若是 CLR:跳到 CLR 的 UndoNextLSN 继续 undo(避免重复 undo);
- 若下一个待 undo LSN 为 null:写 ,从优先队列移除。
- 若是更新记录:执行 undo,写 CLR(
19.9.3 其他特性
- 模糊检查点:写 begin-checkpoint、dump DPT 与 TT、写 end-checkpoint;不阻塞事务。
- 嵌套 top action:对结构性操作(如 B+ 树分裂)单独记录,不因外层事务回滚而被撤销,用一条 CLR 引用其结束 LSN,跳过整段。
- 重启后即可开放:分析后即知崩溃时活跃事务,可选择在 undo 前先允许新事务并发。
一个 ARIES 恢复走查示例:
日志:
LSN 10 <T1, start>
LSN 20 <T1, P5, "abc", "abd"> -- 更新页面 P5
LSN 25 <begin-checkpoint>
LSN 30 <end-checkpoint DPT={P5:20} TT={T1:20}>
LSN 40 <T2, start>
LSN 50 <T2, P7, 100, 200>
LSN 55 <T1, commit>
-- 崩溃发生 --
分析阶段:从 LSN 25 起扫描,得 DPT = {P5:20, P7:50},TT = {T2:50}(T1 已 commit 被移出),RedoLSN = 20。
Redo:从 LSN 20 顺序 redo LSN 20、50,若目标页 PageLSN 已 ≥ 记录 LSN 则跳过。
Undo:TT 剩余 T2,从 LSN 50 逆向 undo,写 CLR,并写 <T2, abort>。
19.10 主存数据库的恢复
主存数据库中数据默认驻留主存,磁盘仅存日志与检查点。恢复的挑战与折中:
- 提交延迟:磁盘 fsync 成为瓶颈。使用组提交、并行日志、NVRAM/持久内存缓解。
- 检查点:由于主存中所有数据都是脏的,检查点等同于一次完整快照。采用 fork-based checkpoint(借助操作系统 COW)或增量脏页跟踪。
- 重启加载:崩溃后需要把整个数据库重新装入主存,恢复完成前系统不可用。可用并行加载、按需加载(需要时才装入具体块)等策略。
- 日志压缩:可通过删除已被后续覆盖的旧日志或使用逻辑日志减小体积。
近年来 Intel Optane 等持久内存(Persistent Memory, PMEM) 提供了字节寻址、非易失、纳秒级延迟的新层次,主存数据库可以直接在 PMEM 上写日志,甚至将数据结构(B+ 树、日志)持久化于 PMEM,从根本上改变恢复的代价模型。设计要点在于缓存行原子性(cache-line atomicity)与持久化屏障(clflushopt / sfence)的正确使用。
19.11 总结
- 数据库须应对事务故障、系统崩溃、介质故障与灾难。
- 日志 + WAL 是保证原子性与持久性的基础;提交必须刷日志。
- redo 恢复已提交事务,undo 撤销未提交事务;两者都必须幂等。
- 检查点(尤其是模糊检查点)限定恢复扫描范围。
- ARIES 结合物理 redo、逻辑 undo、CLR、DPT/TT,为工业界事实标准。
- 高可用性通过远程备份实现,按恢复速度分冷/温/热备份,同步与异步复制各有取舍。
- 逻辑撤销允许锁提前释放,是索引并发的关键。
- 主存数据库对日志与检查点提出新挑战,正推动持久内存等新硬件的应用。
关键不变式一览:
- WAL:数据页刷盘前,其对应日志必须已刷盘。
- 强制日志(Force-log-at-commit):事务提交返回前,其 commit 记录必须已刷盘。
- 幂等性:redo 与 undo 都可被安全地重复执行任意次。
- 单调 LSN:日志顺序追加,LSN 单调递增;页头 PageLSN 提供"该更新是否已作用于该页"的判断依据。
- CLR 的 UndoNextLSN:保证 undo 在再次崩溃后也能正确接续,不重复回滚。
只要这些不变式在所有正常与异常路径上都被满足,事务的 ACID 中的 A 与 D 就得以保证;C 由完整性约束保证,I 由并发控制协议保证。四者相辅相成,缺一不可。