跳到主要内容

数据库恢复系统

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):主存中缓冲池的对应副本。

事务通过 input(A)\text{input}(A) 把包含数据项 AA 的块读入缓冲,通过 output(A)\text{output}(A) 把缓冲块写回磁盘。事务对数据项的读/写实际操作缓冲块中的副本。这就意味着,事务已"提交"不代表其修改已到磁盘——恢复系统必须在此错位中保证 ACID。


19.3 恢复与原子性​

19.3.1 日志记录​

恢复的核心是日志(log)。日志是一个顺序追加的记录序列,写入稳定存储。基本更新日志格式:

⟨Ti,X,V1,V2⟩\langle T_i, X, V_1, V_2 \rangle

含义:事务 TiT_i 对数据项 XX 执行了写操作;V1V_1 是修改前值(旧值 / before image),V2V_2 是修改后值(新值 / after image)。此外还有:

  • ⟨Ti, start⟩\langle T_i,\ \text{start} \rangle:事务开始;
  • ⟨Ti, commit⟩\langle T_i,\ \text{commit} \rangle:事务提交;
  • ⟨Ti, abort⟩\langle T_i,\ \text{abort} \rangle:事务中止;
  • ⟨checkpoint L⟩\langle \text{checkpoint}\ L \rangle:检查点日志,LL 为活跃事务集。

一个完整的日志片段示例(转账事务 T0T_0:A→BA \to B,T1T_1:CC 上加息):

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 T1T_1(回退 C=700);若崩溃发生在 LSN 107 之后,则 T0,T1T_0, T_1 都需要 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 事务提交​

事务提交流程:

  1. 事务把所有更新写入日志缓冲;
  2. 将 ⟨Ti, commit⟩\langle T_i,\ \text{commit} \rangle 追加到日志缓冲;
  3. 强制将日志缓冲刷入稳定存储(fsync);
  4. 提交成功返回给用户;
  5. 修改的数据块可以延后异步刷回磁盘。

第 3 步是持久性的关键:只要日志中出现 commit 记录,事务的效果必能通过 redo 恢复。

19.3.5 使用日志来重做和撤销事务​

  • redo(TiT_i):从头顺序扫描日志,遇到 TiT_i 的更新记录 ⟨Ti,X,V1,V2⟩\langle T_i, X, V_1, V_2 \rangle,将 XX 置为 V2V_2。redo 必须幂等:多次执行结果相同。
  • undo(TiT_i):从尾向头扫描日志,遇到 TiT_i 的更新记录,将 XX 置为 V1V_1,并写补偿日志 ⟨Ti,X,V1⟩\langle T_i, X, V_1 \rangle(redo-only 日志);扫描到 ⟨Ti, start⟩\langle T_i,\ \text{start} \rangle 后写 ⟨Ti, abort⟩\langle T_i,\ \text{abort} \rangle。undo 也必须幂等。

19.3.6 检查点​

若每次崩溃都扫描整个日志,代价随时间线性增长。检查点周期性地做以下事:

  1. 暂停所有更新(或采用模糊检查点,见 19.5.4);
  2. 将日志缓冲刷入稳定存储;
  3. 将所有脏缓冲块刷入磁盘;
  4. 写 ⟨checkpoint L⟩\langle \text{checkpoint}\ L \rangle 到日志,LL 为当前活跃事务集。

恢复时只需从最近的 checkpoint 记录向前找到最早未完成事务的 ⟨Ti, start⟩\langle T_i,\ \text{start} \rangle,从该点起扫描即可。


19.4 恢复算法​

19.4.1 事务回滚​

单个事务 TiT_i 主动中止或被系统回滚时:

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 的物理值不确定,恢复终态也是确定的:所有已提交事务效果保留,所有未提交事务效果全部消除。

  1. redo 阶段(正向):
    • 从最近的检查点开始扫描日志;
    • 对遇到的所有更新记录(包括 CLR)无条件 redo。之所以是"无条件",是因为幂等 redo 比判断更简单,也避免遗漏。
    • 维护 undo-list:见到 ⟨Ti, start⟩\langle T_i,\ \text{start} \rangle 加入,见到 ⟨Ti, commit⟩\langle T_i,\ \text{commit} \rangle 或 ⟨Ti, abort⟩\langle T_i,\ \text{abort} \rangle 移除。
  2. undo 阶段(反向):
    • 从日志尾向头扫描;
    • 对 undo-list 中的每个事务 TiT_i,遇到其更新记录时执行 undo,写 CLR;
    • 遇到 ⟨Ti, start⟩\langle T_i,\ \text{start} \rangle 时写 ⟨Ti, abort⟩\langle T_i,\ \text{abort} \rangle 并把 TiT_i 从 undo-list 移除;
    • undo-list 为空时结束。

19.4.3 提交处理的优化​

  • 组提交(group commit):把多个事务的 commit 记录累积后一次 fsync 刷盘,摊薄同步开销。
  • 异步刷盘 + 顺序号:日志顺序写盘,事务只需等待其 commit LSN 之前的日志刷盘完成。
  • 并行日志:多个日志流,事务按分区归属不同流。

19.5 缓冲区管理​

19.5.1 日志记录缓冲​

日志先写入内存缓冲,再批量刷盘。刷盘时机:

  • 事务提交时(同步);
  • 日志缓冲满时;
  • 后台周期性刷盘。

任何数据块刷盘前,其对应日志必须先刷盘(WAL 规则)。这要求缓冲管理器维护每个数据块的最大更新 LSN,刷盘前将日志刷到该 LSN。

将 WAL 规则形式化:设数据页 pp 的最大更新 LSN 为 PageLSN(p)\text{PageLSN}(p),日志已刷盘的最大 LSN 为 FlushedLSN\text{FlushedLSN}。刷盘 pp 前必须满足 FlushedLSN≥PageLSN(p)\text{FlushedLSN} \ge \text{PageLSN}(p);事务提交返回给应用前,其 commit 记录的 LSN 必须 ≤FlushedLSN\le \text{FlushedLSN}。这两条不变式保证了:任何在磁盘上出现的更新,都能在日志中找到 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) 允许在检查点期间继续处理事务:

  1. 写 ⟨begin-checkpoint⟩\langle \text{begin-checkpoint} \rangle;
  2. 记录当前活跃事务列表 LL、脏页列表;
  3. 异步地把脏页刷回磁盘;不阻塞新事务;
  4. 全部脏页刷完后,写 ⟨end-checkpoint L⟩\langle \text{end-checkpoint}\ L \rangle。

恢复时以最近成功完成的 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+ 树中插入键 kk")的物理表现依赖当前树结构,简单 restore before image 无法正确回滚。定义与之匹配的逆操作(如"从 B+ 树删除键 kk"),逆操作作用于当前状态即可回滚。

19.8.2 逻辑撤销日志记录​

一次逻辑操作开始时写 ⟨Ti, Oj, operation-begin⟩\langle T_i,\ O_j,\ \text{operation-begin} \rangle;操作期间照常记录物理 redo 日志;操作结束时写 ⟨Ti, Oj, operation-end, U⟩\langle T_i,\ O_j,\ \text{operation-end},\ U \rangle,UU 描述逆操作。

19.8.3 有逻辑撤销的事务回滚​

回滚 TiT_i 时:

  • 遇到 operation-end:调用逆操作 UU,跳到对应 operation-begin 之前继续扫描(跨越整个逻辑操作);
  • 遇到普通更新记录:物理 undo;
  • 遇到 operation-begin 且未匹配 end:表示操作未完成,按物理 undo 回滚其中的物理更新。

19.8.4 逻辑撤销中的并发问题​

由于锁提前释放,逻辑撤销时数据结构状态可能已被其他事务修改。逆操作必须能作用于任意合法状态——例如"从 B+ 树删除 kk"不管当前树多深、kk 位于哪个叶子都能正确执行。这要求索引结构提供满足此性质的操作接口。


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 结构示意:

表字段含义
DPTPageID脏页页号
DPTRecLSN该页第一次变脏时对应的日志 LSN,redo 从此开始才可能影响该页
TTTransID事务 ID
TTStatus状态:U(Undo 中)/ P(准备中)/ C(活跃)等
TTLastLSN该事务的最新一条日志 LSN

19.9.2 恢复算法​

ARIES 恢复由三阶段组成:

  • 分析阶段(Analysis):从最近 begin-checkpoint 向后扫描:
    • 遇 update 记录:将对应事务加入 TT,若目标页不在 DPT 则加入并 RecLSN = 当前 LSN;
    • 遇 commit / abort 记录:更新 TT 中事务状态;
    • 结束时,DPT 中最小 RecLSN 即 RedoLSN。
  • 重做阶段(Redo):从 RedoLSN 起顺序扫描:
    • 对每条更新记录 rr:若目标页不在 DPT,或 r.LSN < DPT[page].RecLSN,跳过(不可能影响该页);否则读取该页,比较 PageLSN,若 PageLSN < r.LSN 则重放该更新并将 PageLSN 更新为 r.LSN。
    • 这一阶段包括对 CLR 的 redo,因此保证部分回滚已完成的工作不会丢失。
  • 撤销阶段(Undo):对 TT 中处于 U 状态的事务(未提交):
    • 用优先队列按 LastLSN 递减处理;
    • 每次取出 LSN 最大的事务,对其日志记录:
      • 若是更新记录:执行 undo,写 CLR(UndoNextLSN = 该记录的 PrevLSN),事务的下一个待 undo LSN 更新为 PrevLSN;
      • 若是 CLR:跳到 CLR 的 UndoNextLSN 继续 undo(避免重复 undo);
      • 若下一个待 undo LSN 为 null:写 ⟨Ti, abort⟩\langle T_i,\ \text{abort} \rangle,从优先队列移除。

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 由并发控制协议保证。四者相辅相成,缺一不可。