崩溃恢复是数据库最被低估的核心能力。本文从 ACID 的持久性保证出发, 展开 WAL 协议的设计空间,深入 ARIES 恢复算法的三阶段流程, 用 C 代码实现一个最小 WAL 引擎,并讨论 InnoDB、PostgreSQL、SQLite 的实际做法以及 NVM 时代的新方向。
一、ACID 与持久性保证基础
关系数据库的正确性建立在 ACID 四大属性之上:
| 属性 | 含义 | 关键机制 |
|---|---|---|
| Atomicity | 事务要么全做、要么全不做 | Undo log / Shadow paging |
| Consistency | 事务执行前后满足所有约束 | 约束检查、触发器 |
| Isolation | 并发事务互不干扰 | 锁、MVCC、时间戳排序 |
| Durability | 一旦提交,永不丢失 | WAL + Force-at-commit |
其中持久性(Durability)是最”物理”的一条:它对抗的不是逻辑错误, 而是掉电、内核崩溃、磁盘损坏等硬件事件。
1.1 持久性的朴素实现
最简单的做法:每次写操作直接落盘。问题:随机写性能极差(HDD 一次 fsync 约 5-10ms),事务修改分散在磁盘各处,写到一半崩溃导致 torn page。
1.2 WAL 的核心洞察
WAL(Write-Ahead Logging)的核心思想极其简单:
在修改任何数据页之前,先把”我打算做什么修改”写到一个 顺序追加的日志文件里。
为什么这行得通?因为顺序写比随机写快一到两个数量级。 只要日志落盘了,即使数据页没有落盘,崩溃后也能从日志恢复。
1.3 持久性保证的两个层次
- 事务级持久性: 已提交事务的所有修改不会丢失。
- 崩溃一致性: 恢复后数据库处于一致状态,不会出现中间态。
WAL 同时解决了这两个问题:redo log 保证已提交事务可重放, undo log 保证未提交事务可回滚。
二、WAL 协议: 先写日志、提交强制
2.1 WAL 规则
WAL 协议可以归纳为两条不可违反的规则:
规则一: Log-Before-Data (先写日志)
在将任何脏页刷到磁盘之前,
该页面对应的所有日志记录必须已经持久化。
pageLSN <= flushedLSN => 允许刷页这条规则保证了:如果崩溃时某个页面已经落盘, 那么产生这个修改的日志一定也已经落盘,redo 时不会遗漏。
规则二: Force-at-Commit (提交强制)
在向客户端返回 COMMIT OK 之前,
该事务的所有日志记录(包括 COMMIT 记录)必须已经持久化。
commitLSN <= flushedLSN => 允许返回 OK这条规则保证了:只要客户端收到了提交确认, 即使下一瞬间崩溃,该事务也能通过 redo 恢复。
2.2 Group Commit 优化
每个事务单独 fsync 代价太高。Group Commit 的做法是: 积攒一批事务的日志,一次 fsync 写入,然后批量通知所有事务。
Timeline:
T1 writes log ──┐
T2 writes log ──┼── buffer fills / timeout ── fsync ── notify all
T3 writes log ──┘InnoDB 的 innodb_flush_log_at_trx_commit = 1
时, 每次提交都 fsync;设为 2 时,仅写到 OS 缓存,由后台线程每秒
fsync。
2.3 Steal / No-Steal 与 Force / No-Force
缓冲池管理策略可以用两个维度描述:
Force No-Force
(提交时刷所有脏页) (提交时不必刷脏页)
┌──────────────────────────────┬──────────────────────────────┐
│ No-Steal + Force │ No-Steal + No-Force │
│ 不需要 redo, 不需要 undo │ 需要 redo, 不需要 undo │
│ 简单但性能差 │ 事务大时内存不够 │
├──────────────────────────────┼──────────────────────────────┤
│ Steal + Force │ Steal + No-Force │
│ 不需要 redo, 需要 undo │ 需要 redo, 需要 undo │
│ 提交慢 │ ARIES 选择的策略 │
└──────────────────────────────┴──────────────────────────────┘Steal: 允许将未提交事务修改过的脏页刷到磁盘(为了腾出缓冲池空间)。 这就需要 undo 能力,因为崩溃后磁盘上可能存在未提交的修改。
No-Force: 提交时不强制刷数据页(只强制刷日志)。 这就需要 redo 能力,因为已提交的修改可能还在缓冲池中没有落盘。
ARIES 选择 Steal + No-Force,这是性能最好的组合, 代价是恢复逻辑最复杂——既要 redo 又要 undo。
2.4 LSN: 日志的全局时钟
LSN(Log Sequence Number)是 WAL
的核心概念,它是日志记录在日志文件中的
字节偏移量(或单调递增序号)。每个数据页头部维护一个
pageLSN, 表示”最后一次修改这个页面的日志记录的
LSN”。
LSN 的用途:判断页面是否需要
redo(pageLSN >= logRecord.LSN 则跳过);
判断日志是否已刷盘(对比 flushedLSN); 确定 redo
起始位置(RedoLSN = min(DPT.recLSN)); 通过
prevLSN 链回溯事务的所有操作。
三、ARIES 三阶段: Analysis、Redo、Undo
ARIES(Algorithm for Recovery and Isolation Exploiting Semantics) 由 IBM 的 C. Mohan 等人在 1992 年提出,是绝大多数关系数据库 崩溃恢复算法的理论基础。
3.1 整体流程
Checkpoint RedoLSN Crash
| | |
v v v
===|==================|=================================|=== LOG
|<-- Analysis ---->| |
|<---------- Redo --------------->|
|<----------------------- Undo ----------------------|三个阶段严格按顺序执行:
Analysis(分析): 从最近的 checkpoint 开始正向扫描日志, 重建 ATT(Active Transaction Table)和 DPT(Dirty Page Table), 确定 redo 的起始 LSN 和需要 undo 的事务集合。
Redo(重做): 从 RedoLSN 开始正向扫描日志, 对所有日志记录(包括未提交事务的)进行重做, 将数据库恢复到崩溃瞬间的精确状态。
Undo(撤销): 对所有在崩溃时仍处于活跃状态的事务进行回滚, 反向遍历它们的日志记录链,撤销每一个操作。
3.2 为什么要 redo 未提交事务的操作?
这是 ARIES 最反直觉的地方。由于 Steal 策略,未提交事务的脏页可能 已刷到磁盘。Redo 阶段的目标是恢复到崩溃瞬间的精确状态, 这样 undo 阶段才能正确撤销未提交的修改。
3.3 Repeating History
ARIES 的设计哲学: redo 阶段精确重放崩溃前的每一个操作,不做过滤。 redo 不需要知道事务的提交状态,只管机械重放。判断留给 undo。
四、日志记录格式: LSN、prevLSN、CLR
4.1 普通日志记录(Update Record)
┌───────┬──────────┬────────┬──────┬────────┬─────────────┬────────────┐
│ LSN │ prevLSN │ txnID │ type │ pageID │ before-img │ after-img │
└───────┴──────────┴────────┴──────┴────────┴─────────────┴────────────┘各字段含义:
| 字段 | 大小(典型) | 说明 |
|---|---|---|
| LSN | 8 bytes | 日志记录在日志文件中的位置 |
| prevLSN | 8 bytes | 同一事务的上一条日志记录的 LSN |
| txnID | 4-8 bytes | 事务标识符 |
| type | 1 byte | UPDATE / COMMIT / ABORT / CLR / BEGIN / CHECKPOINT |
| pageID | 4-8 bytes | 被修改的页面 |
| before-image | 变长 | 修改前的值(用于 undo) |
| after-image | 变长 | 修改后的值(用于 redo) |
4.2 prevLSN 链: 事务内的反向链表
每个事务的日志记录通过 prevLSN
形成一条反向链表:
T1: BEGIN(LSN=10) <-- UPDATE(LSN=30, prevLSN=10) <-- UPDATE(LSN=70, prevLSN=30)
^
lastLSN of T1undo 阶段从事务的 lastLSN 开始,沿
prevLSN 链逐条回溯。
这比正向扫描整个日志高效得多,因为只需要访问本事务的记录。
4.3 CLR (Compensation Log Record)
CLR 是 ARIES 最精妙的设计之一。当 undo 一条日志记录时, ARIES 会写一条 CLR 来记录这次撤销操作:
CLR 格式:
┌───────┬──────────┬────────┬──────┬────────┬────────────┬─────────────┐
│ LSN │ prevLSN │ txnID │ CLR │ pageID │ undo-data │ undoNextLSN │
└───────┴──────────┴────────┴──────┴────────┴────────────┴─────────────┘undoNextLSN 指向下一条需要被 undo 的日志记录
(即被撤销的那条记录的 prevLSN)。
为什么需要 CLR?考虑以下场景:
正常运行: T1: UPDATE(LSN=10) -> UPDATE(LSN=20) -> UPDATE(LSN=30)
第一次崩溃: undo T1, 撤销了 LSN=30, 写了 CLR(LSN=40, undoNextLSN=20)
第二次崩溃: undo 阶段看到 CLR(LSN=40), 跳到 undoNextLSN=20 继续 undo
不会重复撤销 LSN=30CLR 保证 undo 操作是幂等的——无论崩溃多少次, 每条原始日志记录最多被 undo 一次。CLR 本身在 redo 阶段会被重做, 但在 undo 阶段不会被撤销(CLR 是 redo-only 的)。
4.4 各类型日志记录汇总
BEGIN(txnID) -- 事务开始
UPDATE(txnID, pageID, -- 数据修改
before, after)
COMMIT(txnID) -- 事务提交
ABORT(txnID) -- 事务显式回滚
CLR(txnID, pageID, -- 补偿日志(undo 产生)
undo-data, undoNextLSN)
END(txnID) -- 事务完全结束(undo 完成或 commit 落盘)
CHECKPOINT(ATT, DPT) -- 检查点五、Checkpoint: 模糊检查点与 ATT/DPT
5.1 为什么需要 checkpoint
如果每次恢复都从日志开头扫描,恢复时间会随日志增长而线性增加。 Checkpoint 的作用是缩短 Analysis 和 Redo 的起始位置。
5.2 朴素 checkpoint 的问题
暂停所有事务,刷所有脏页,记录 ATT。问题:刷页可能花费数十秒, 期间数据库完全停止服务,对 OLTP 不可接受。
5.3 Fuzzy Checkpoint(模糊检查点)
ARIES 使用 fuzzy checkpoint,不刷任何脏页,只记录两张表:
ATT(Active Transaction Table):
┌────────┬────────┬──────────┬────────────┐
│ txnID │ status │ lastLSN │ firstLSN │
├────────┼────────┼──────────┼────────────┤
│ T1 │ active │ 1050 │ 1020 │
│ T3 │ active │ 1080 │ 1055 │
│ T5 │ commit │ 1090 │ 1060 │
└────────┴────────┴──────────┴────────────┘每一行代表一个在 checkpoint 时刻仍然活跃(或刚提交但还没 END)的事务。
DPT(Dirty Page Table):
┌────────┬──────────┐
│ pageID │ recLSN │
├────────┼──────────┤
│ P5 │ 1020 │
│ P8 │ 1055 │
│ P12 │ 1080 │
└────────┴──────────┘recLSN(recovery
LSN)是该页面第一次变脏时的日志 LSN, 给出了该页面最早可能需要
redo 的位置下界。
5.4 Checkpoint 写入流程
1. 写 BEGIN_CHECKPOINT 日志记录
2. 构建当前 ATT 和 DPT 的快照
3. 写 END_CHECKPOINT(ATT, DPT) 日志记录
4. 将 BEGIN_CHECKPOINT 的 LSN 写入 master record(固定位置)注意:步骤 2-3 期间数据库仍在运行,ATT/DPT 可能已变化。 Analysis 阶段会从这个近似状态开始,通过扫描后续日志来修正。
5.5 master record
数据库在磁盘固定位置维护 master record,记录最近 checkpoint 的 LSN。 恢复时先读 master record 找到 checkpoint,再开始 Analysis。
六、Recovery 流程详解
6.1 Analysis 阶段
从 checkpoint 记录的 ATT/DPT 开始,正向扫描日志到末尾:
function analysis(checkpoint_lsn):
ATT = checkpoint.ATT // 从 checkpoint 恢复
DPT = checkpoint.DPT
for each log_record from checkpoint_lsn to end_of_log:
if record.type == BEGIN:
ATT.add(record.txnID, status=active, lastLSN=record.LSN)
if record.type in {UPDATE, CLR}:
ATT[record.txnID].lastLSN = record.LSN
if record.pageID not in DPT:
DPT[record.pageID] = record.LSN // recLSN
if record.type == COMMIT:
ATT[record.txnID].status = committing
if record.type == END:
ATT.remove(record.txnID)
// Analysis 结束后:
// ATT 中剩余的事务 = 需要 undo 的 loser transactions
// RedoLSN = min(DPT[p].recLSN for all p in DPT)
RedoLSN = min(DPT.values())
return ATT, DPT, RedoLSN6.2 Redo 阶段
从 RedoLSN 开始正向扫描,对每条 UPDATE 或 CLR 记录:
function redo(RedoLSN, DPT):
for each log_record from RedoLSN to end_of_log:
if record.type not in {UPDATE, CLR}:
continue
if record.pageID not in DPT:
continue // 该页面在 checkpoint 后已经刷盘
if DPT[record.pageID].recLSN > record.LSN:
continue // 该页面的首次脏化在此记录之后
// 读取页面,检查 pageLSN
page = read_page(record.pageID)
if page.pageLSN >= record.LSN:
continue // 修改已经反映在页面上
// 实际 redo
apply_redo(page, record)
page.pageLSN = record.LSN
// 注意: 不立即刷盘,也不写新的日志记录三层过滤确保了 redo 的效率: 1. 页面不在 DPT 中 => 已刷盘,跳过; 2. DPT 中 recLSN 大于当前记录 LSN => 不可能需要 redo,跳过; 3. 页面的 pageLSN 大于等于当前记录 LSN => 已经应用,跳过。
6.3 Undo 阶段
对 ATT 中所有 status != committed 的事务进行回滚:
function undo(ATT):
// 收集所有需要 undo 的事务的 lastLSN
to_undo = max_heap()
for txn in ATT where txn.status != committed:
to_undo.push(txn.lastLSN)
while to_undo is not empty:
lsn = to_undo.pop() // 取最大的 LSN
record = read_log(lsn)
if record.type == CLR:
// CLR 不需要 undo,跳到 undoNextLSN
if record.undoNextLSN != NULL:
to_undo.push(record.undoNextLSN)
else:
write_end_record(record.txnID)
else:
// 普通 UPDATE: 执行 undo 并写 CLR
page = read_page(record.pageID)
apply_undo(page, record)
clr = write_CLR(
txnID = record.txnID,
pageID = record.pageID,
undo_data = record.before_image,
undoNextLSN = record.prevLSN
)
page.pageLSN = clr.LSN
if record.prevLSN != NULL:
to_undo.push(record.prevLSN)
else:
write_end_record(record.txnID)使用最大堆(从最新到最旧)可以利用缓冲池中已有的页面,减少随机 I/O。
6.4 完整恢复示例
假设日志如下,T1 已提交,T2 未提交:
LSN | prevLSN | txnID | type | pageID | before | after
-----|---------|-------|--------|--------|--------|------
100 | - | T1 | BEGIN | - | - | -
110 | - | T2 | BEGIN | - | - | -
120 | 100 | T1 | UPDATE | P1 | AAA | BBB
130 | 110 | T2 | UPDATE | P2 | CCC | DDD
140 | 120 | T1 | UPDATE | P3 | EEE | FFF
150 | 130 | T2 | UPDATE | P1 | BBB | GGG
160 | 140 | T1 | COMMIT | - | - | -
170 | 160 | T1 | END | - | - | -
*** CRASH ***Checkpoint 在 LSN=100 之前(假设空 ATT/DPT)。Analysis 扫描全部日志: - ATT = {T2: active, lastLSN=150},DPT = {P1: 120, P2: 130, P3: 140},RedoLSN = 120
Redo: 从 LSN=120 重做 120, 130, 140, 150。
Undo: T2 从 lastLSN=150 开始: 1. Undo 150: P1 GGG->BBB, CLR(180, undoNextLSN=110) 2. Undo 130: P2 DDD->CCC, CLR(190, undoNextLSN=-), END(T2)
最终: P1=BBB(T1保留), P2=CCC(T2撤销), P3=FFF(T1保留)。
七、CLR 深入: 防止重复 undo 的精妙设计
7.1 问题: 恢复过程中再次崩溃
考虑这样的场景:
原始日志: T1: UPDATE(10) -> UPDATE(20) -> UPDATE(30)
第一次崩溃后 undo:
CLR(40, undoNextLSN=20) // 撤销了 LSN=30
*** 第二次崩溃 ***如果没有 CLR,第二次恢复的 undo 阶段会: 1. 看到 LSN=30,再次 undo——但此时页面状态已经是 undo 后的状态, 再 undo 一次就错了! 2. 看到 LSN=20,正常 undo——但 LSN=30 的 undo 已经把数据搞乱了。
7.2 CLR 的解决方案
有了 CLR,第二次恢复的流程:
Redo 阶段: 重做 10, 20, 30, CLR(40)——恢复到第二次崩溃瞬间的状态。
Undo 阶段: T1 的 lastLSN = 40(CLR)。 1. 看到 CLR(40),不 undo,跳到 undoNextLSN=20; 2. Undo LSN=20,写 CLR(50, undoNextLSN=10); 3. Undo LSN=10,写 CLR(60, undoNextLSN=NULL); 4. 写 END(T1)。
7.3 CLR 的关键性质
- CLR 是 redo-only 的: redo 阶段会重做 CLR,但 undo 阶段不会撤销 CLR。
- CLR 的 undoNextLSN 跳过已撤销的记录: 形成一条”快速通道”。
- CLR 本身也遵循 WAL 规则: 写 CLR 之前,必须确保日志持久化。
- CLR 保证有界恢复: 无论崩溃多少次,每条原始 UPDATE 最多被 undo 一次。
7.4 CLR 链的可视化
prevLSN 链: 10 <-- 20 <-- 30
1st undo: CLR(40) ---undoNextLSN---> 20
2nd undo: CLR(50) ---undoNextLSN---> 10
3rd undo: CLR(60) ---undoNextLSN---> NULL => END(T1)每个 CLR 的 undoNextLSN 跳过被撤销的记录,后续恢复不会重复工作。
八、Physiological Logging: 物理与逻辑的混合
8.1 纯物理日志 vs 纯逻辑日志
纯物理日志: 记录字节偏移和前后值。优点是 redo/undo 简单; 缺点是日志量大,页面重组产生大量碎片记录。
Physical: page P5, offset 120, length 8, before=0xDEAD, after=0xBEEF纯逻辑日志: 记录高层操作。日志量小但 redo 可能非幂等, 需要完整执行上下文。
Logical: INSERT INTO users(id, name) VALUES(42, 'Alice')8.2 Physiological Logging
ARIES 采用折中方案:页面级物理 + 页内逻辑。
Physiological: page P5, INSERT tuple (42, 'Alice') at slot 3- 物理定位: 精确到页面(pageID),redo/undo 时只需要锁定该页面;
- 逻辑操作: 在页面内部用逻辑描述(如”在 slot 3 插入元组”), 不关心具体字节偏移,容忍页面内的重组。
8.3 为什么 physiological logging 有效
- redo 幂等: 通过 pageLSN 比较,同一操作不会被重做两次;
- 页面是原子单位: 一条日志只涉及一个页面,不存在跨页面不一致;
- 容忍重组: B+tree 节点分裂后 slot 编号可能变化,physiological log 可以适应;
- 日志量适中: 比纯物理日志小,比纯逻辑日志可控。
8.4 InnoDB 的 physiological logging
InnoDB redo log 既有物理级字节写入,也有逻辑级操作,全部绑定到具体页面:
MLOG_1BYTE // 写 1 字节到页面偏移
MLOG_2BYTES // 写 2 字节到页面偏移
MLOG_WRITE_STRING // 写变长字节串到页面偏移
MLOG_REC_INSERT // 在页面上插入一条记录(逻辑)
MLOG_REC_DELETE // 标记删除一条记录
MLOG_PAGE_REORGANIZE // 页面重组九、Mini WAL Engine: C 语言实现
下面是一个完整的 mini WAL 引擎,实现日志写入、checkpoint、 崩溃恢复(analysis + redo + undo)的核心逻辑。 使用内存模拟磁盘页面,日志存储在数组中。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
/* ---------- 常量定义 ---------- */
#define MAX_LOG_RECORDS 1024
#define MAX_PAGES 64
#define MAX_TRANSACTIONS 32
#define PAGE_VALUE_SIZE 32
#define NULL_LSN (-1)
/* ---------- 日志记录类型 ---------- */
typedef enum {
LOG_BEGIN,
LOG_UPDATE,
LOG_COMMIT,
LOG_ABORT,
LOG_CLR,
LOG_END,
LOG_CHECKPOINT
} LogType;
/* ---------- 日志记录 ---------- */
typedef struct {
int32_t lsn;
int32_t prev_lsn; /* 同一事务的上一条记录 */
int32_t txn_id;
LogType type;
int32_t page_id;
char before_img[PAGE_VALUE_SIZE];
char after_img[PAGE_VALUE_SIZE];
int32_t undo_next_lsn; /* CLR 专用 */
} LogRecord;
/* ---------- 数据页 ---------- */
typedef struct {
int32_t page_id;
int32_t page_lsn; /* 最后修改此页的 LSN */
char data[PAGE_VALUE_SIZE];
bool on_disk; /* 模拟是否已刷盘 */
} Page;
/* ---------- ATT 条目 ---------- */
typedef struct {
int32_t txn_id;
int32_t last_lsn;
bool active;
bool committed;
} ATTEntry;
/* ---------- DPT 条目 ---------- */
typedef struct {
int32_t page_id;
int32_t rec_lsn; /* 首次变脏时的 LSN */
bool valid;
} DPTEntry;
/* ---------- 全局状态 ---------- */
static LogRecord g_log[MAX_LOG_RECORDS];
static int g_log_count = 0;
static int g_next_lsn = 100;
static Page g_pages[MAX_PAGES];
static int g_page_count = 0;
static ATTEntry g_att[MAX_TRANSACTIONS];
static DPTEntry g_dpt[MAX_PAGES];
static int g_checkpoint_lsn = NULL_LSN;
/* ---------- 辅助函数 ---------- */
static Page *find_or_create_page(int page_id) {
for (int i = 0; i < g_page_count; i++) {
if (g_pages[i].page_id == page_id)
return &g_pages[i];
}
Page *p = &g_pages[g_page_count++];
p->page_id = page_id;
p->page_lsn = NULL_LSN;
p->on_disk = false;
memset(p->data, 0, PAGE_VALUE_SIZE);
return p;
}
static ATTEntry *find_att(int txn_id) {
for (int i = 0; i < MAX_TRANSACTIONS; i++) {
if (g_att[i].active && g_att[i].txn_id == txn_id)
return &g_att[i];
}
return NULL;
}
static ATTEntry *alloc_att(int txn_id) {
for (int i = 0; i < MAX_TRANSACTIONS; i++) {
if (!g_att[i].active) {
g_att[i].txn_id = txn_id;
g_att[i].last_lsn = NULL_LSN;
g_att[i].active = true;
g_att[i].committed = false;
return &g_att[i];
}
}
return NULL;
}
static DPTEntry *find_dpt(int page_id) {
for (int i = 0; i < MAX_PAGES; i++) {
if (g_dpt[i].valid && g_dpt[i].page_id == page_id)
return &g_dpt[i];
}
return NULL;
}
static void add_dpt(int page_id, int rec_lsn) {
if (find_dpt(page_id)) return;
for (int i = 0; i < MAX_PAGES; i++) {
if (!g_dpt[i].valid) {
g_dpt[i].page_id = page_id;
g_dpt[i].rec_lsn = rec_lsn;
g_dpt[i].valid = true;
return;
}
}
}
/* ---------- 日志写入 ---------- */
static int write_log(int txn_id, LogType type, int page_id,
const char *before, const char *after,
int undo_next) {
LogRecord *r = &g_log[g_log_count++];
r->lsn = g_next_lsn++;
r->txn_id = txn_id;
r->type = type;
r->page_id = page_id;
r->undo_next_lsn = undo_next;
ATTEntry *att = find_att(txn_id);
r->prev_lsn = att ? att->last_lsn : NULL_LSN;
if (before) strncpy(r->before_img, before, PAGE_VALUE_SIZE);
if (after) strncpy(r->after_img, after, PAGE_VALUE_SIZE);
if (att) att->last_lsn = r->lsn;
return r->lsn;
}
/* ---------- 事务操作接口 ---------- */
void txn_begin(int txn_id) {
alloc_att(txn_id);
write_log(txn_id, LOG_BEGIN, -1, NULL, NULL, NULL_LSN);
}
void txn_update(int txn_id, int page_id,
const char *old_val, const char *new_val) {
int lsn = write_log(txn_id, LOG_UPDATE, page_id,
old_val, new_val, NULL_LSN);
Page *p = find_or_create_page(page_id);
strncpy(p->data, new_val, PAGE_VALUE_SIZE);
p->page_lsn = lsn;
add_dpt(page_id, lsn);
}
void txn_commit(int txn_id) {
write_log(txn_id, LOG_COMMIT, -1, NULL, NULL, NULL_LSN);
ATTEntry *att = find_att(txn_id);
if (att) att->committed = true;
write_log(txn_id, LOG_END, -1, NULL, NULL, NULL_LSN);
if (att) att->active = false;
}
/* ---------- Checkpoint ---------- */
void do_checkpoint(void) {
g_checkpoint_lsn = g_next_lsn;
write_log(-1, LOG_CHECKPOINT, -1, NULL, NULL, NULL_LSN);
printf("[CHECKPOINT] at LSN %d\n", g_checkpoint_lsn);
}
/* ---------- 模拟崩溃: 只保留 on_disk=true 的页面数据 ---------- */
void simulate_crash(void) {
printf("[CRASH] simulating system failure\n");
for (int i = 0; i < g_page_count; i++) {
if (!g_pages[i].on_disk) {
memset(g_pages[i].data, 0, PAGE_VALUE_SIZE);
g_pages[i].page_lsn = NULL_LSN;
}
}
memset(g_att, 0, sizeof(g_att));
memset(g_dpt, 0, sizeof(g_dpt));
}
/* ---------- Recovery: Analysis ---------- */
static int recovery_analysis(void) {
printf("[ANALYSIS] scanning from checkpoint LSN %d\n",
g_checkpoint_lsn);
memset(g_att, 0, sizeof(g_att));
memset(g_dpt, 0, sizeof(g_dpt));
int start = 0;
for (int i = 0; i < g_log_count; i++) {
if (g_log[i].lsn == g_checkpoint_lsn) { start = i; break; }
}
for (int i = start; i < g_log_count; i++) {
LogRecord *r = &g_log[i];
if (r->type == LOG_CHECKPOINT) continue;
if (r->type == LOG_BEGIN) {
alloc_att(r->txn_id);
}
if (r->type == LOG_UPDATE || r->type == LOG_CLR) {
ATTEntry *att = find_att(r->txn_id);
if (att) att->last_lsn = r->lsn;
if (r->page_id >= 0) add_dpt(r->page_id, r->lsn);
}
if (r->type == LOG_COMMIT) {
ATTEntry *att = find_att(r->txn_id);
if (att) att->committed = true;
}
if (r->type == LOG_END) {
ATTEntry *att = find_att(r->txn_id);
if (att) att->active = false;
}
}
int redo_lsn = g_next_lsn;
for (int i = 0; i < MAX_PAGES; i++) {
if (g_dpt[i].valid && g_dpt[i].rec_lsn < redo_lsn)
redo_lsn = g_dpt[i].rec_lsn;
}
printf("[ANALYSIS] RedoLSN = %d\n", redo_lsn);
return redo_lsn;
}
/* ---------- Recovery: Redo ---------- */
static void recovery_redo(int redo_lsn) {
printf("[REDO] replaying from LSN %d\n", redo_lsn);
for (int i = 0; i < g_log_count; i++) {
LogRecord *r = &g_log[i];
if (r->lsn < redo_lsn) continue;
if (r->type != LOG_UPDATE && r->type != LOG_CLR) continue;
if (r->page_id < 0) continue;
DPTEntry *dpt = find_dpt(r->page_id);
if (!dpt) continue;
if (dpt->rec_lsn > r->lsn) continue;
Page *p = find_or_create_page(r->page_id);
if (p->page_lsn >= r->lsn) continue;
const char *img = (r->type == LOG_CLR)
? r->before_img : r->after_img;
strncpy(p->data, img, PAGE_VALUE_SIZE);
p->page_lsn = r->lsn;
printf(" REDO LSN=%d page=%d -> \"%s\"\n",
r->lsn, r->page_id, img);
}
}
/* ---------- Recovery: Undo ---------- */
static void recovery_undo(void) {
printf("[UNDO] rolling back loser transactions\n");
bool progress = true;
while (progress) {
progress = false;
int max_lsn = NULL_LSN;
ATTEntry *max_att = NULL;
for (int i = 0; i < MAX_TRANSACTIONS; i++) {
if (g_att[i].active && !g_att[i].committed
&& g_att[i].last_lsn > max_lsn) {
max_lsn = g_att[i].last_lsn;
max_att = &g_att[i];
}
}
if (!max_att || max_lsn == NULL_LSN) break;
progress = true;
LogRecord *r = NULL;
for (int i = 0; i < g_log_count; i++) {
if (g_log[i].lsn == max_lsn) { r = &g_log[i]; break; }
}
if (!r) { max_att->active = false; break; }
if (r->type == LOG_CLR) {
if (r->undo_next_lsn == NULL_LSN) {
max_att->active = false;
printf(" END txn=%d\n", max_att->txn_id);
} else {
max_att->last_lsn = r->undo_next_lsn;
}
} else if (r->type == LOG_UPDATE) {
Page *p = find_or_create_page(r->page_id);
strncpy(p->data, r->before_img, PAGE_VALUE_SIZE);
int clr_lsn = write_log(r->txn_id, LOG_CLR, r->page_id,
r->before_img, NULL, r->prev_lsn);
p->page_lsn = clr_lsn;
printf(" UNDO LSN=%d txn=%d page=%d -> \"%s\" (CLR=%d)\n",
r->lsn, r->txn_id, r->page_id, r->before_img, clr_lsn);
max_att->last_lsn = r->prev_lsn;
if (r->prev_lsn == NULL_LSN) {
max_att->active = false;
printf(" END txn=%d\n", max_att->txn_id);
}
} else if (r->type == LOG_BEGIN) {
max_att->active = false;
printf(" END txn=%d (reached BEGIN)\n", max_att->txn_id);
} else {
max_att->last_lsn = r->prev_lsn;
}
}
}
/* ---------- 完整恢复 ---------- */
void recover(void) {
printf("\n========== RECOVERY START ==========\n");
int redo_lsn = recovery_analysis();
recovery_redo(redo_lsn);
recovery_undo();
printf("========== RECOVERY COMPLETE ==========\n\n");
}
/* ---------- 打印页面状态 ---------- */
void print_pages(void) {
printf("--- Page State ---\n");
for (int i = 0; i < g_page_count; i++) {
printf(" Page %d: \"%s\" (pageLSN=%d)\n",
g_pages[i].page_id, g_pages[i].data,
g_pages[i].page_lsn);
}
}
/* ---------- 测试 ---------- */
int main(void) {
printf("=== Mini WAL Engine Demo ===\n\n");
/* T1: 已提交事务 */
txn_begin(1);
txn_update(1, 10, "old_A", "new_A");
txn_update(1, 20, "old_B", "new_B");
/* checkpoint */
do_checkpoint();
/* T2: 未提交事务 */
txn_begin(2);
txn_update(2, 30, "old_C", "new_C");
txn_update(2, 10, "new_A", "new_A2");
/* T1 提交 */
txn_commit(1);
printf("\nBefore crash:\n");
print_pages();
simulate_crash();
printf("\nAfter crash (before recovery):\n");
print_pages();
recover();
printf("After recovery:\n");
print_pages();
/* 预期: Page 10 = "new_A"(T1已提交的值, T2的修改被undo)
Page 20 = "new_B"(T1已提交)
Page 30 = "old_C"(T2被undo) */
return 0;
}编译运行:
gcc -Wall -Wextra -O2 -o mini_wal mini_wal.c && ./mini_wal预期输出(关键部分):
[CHECKPOINT] at LSN 103
[CRASH] simulating system failure
[ANALYSIS] RedoLSN = 105
[REDO] replaying from LSN 105
REDO LSN=105 page=30 -> "new_C"
REDO LSN=106 page=10 -> "new_A2"
[UNDO] rolling back loser transactions
UNDO LSN=106 txn=2 page=10 -> "new_A" (CLR=109)
UNDO LSN=105 txn=2 page=30 -> "old_C" (CLR=110)
END txn=2 (reached BEGIN)
After recovery:
Page 10: "new_A" (T2 undone, restored to T1's value)
Page 20: "" (T1 committed pre-checkpoint, page not in DPT)
Page 30: "old_C" (T2 undone)注意: 由于 T1 在 checkpoint 之前修改了 P10 和 P20,而
checkpoint 是 fuzzy 的(不刷脏页),模拟崩溃后 P20
数据丢失。在真实数据库中,
已刷盘的页面(on_disk=true)不会受崩溃影响。这里的
demo 为简化起见将所有未标记 on_disk
的页面清零。
十、实际数据库的恢复实现
10.1 InnoDB (MySQL)
InnoDB 的恢复机制高度符合 ARIES 模型:
Redo Log(重做日志): 循环写入
ib_logfile0、ib_logfile1 等文件。
每条记录是 physiological 的,绑定到 space_id + page_no。 使用
LSN(字节偏移量)作为全局时钟。 提交时 fsync redo
log(innodb_flush_log_at_trx_commit = 1)。
Undo Log(回滚日志): 存储在系统表空间或独立 undo tablespace 中。 保存修改前的行版本,undo log 本身的修改也写 redo log。 MVCC 读取也使用 undo log 构造历史版本。
Checkpoint: 后台线程持续刷脏页。Checkpoint LSN = 最旧脏页的 LSN。 写入 redo log 文件头部(相当于 master record)。 Sharp checkpoint 仅在关闭时使用。
-- 查看 InnoDB 恢复相关状态
SHOW ENGINE INNODB STATUS\G
-- 关键指标:
-- Log sequence number: 当前 LSN
-- Log flushed up to: 已刷盘的 LSN
-- Pages flushed up to: 脏页已刷盘到的 LSN
-- Last checkpoint at: 最近 checkpoint LSN恢复流程:
1. 读取 redo log 文件头, 获取 checkpoint LSN
2. 从 checkpoint LSN 开始扫描, 按页面分组并行 redo
3. 打开 undo tablespace, 构建回滚段
4. 后台异步 undo 未提交事务 (不阻塞新请求)10.2 PostgreSQL
PostgreSQL 的 WAL 机制与 ARIES 有显著差异:
WAL: 日志文件在 pg_wal/
目录下,每个 16MB。 记录格式为 XLogRecord 头部 + 数据体。
Full-page writes: checkpoint
后首次修改某页时,日志中包含整页副本(防止 torn page)。
CLOG(pg_xact): 独立文件记录每个事务状态,每事务占 2 bit。
恢复流程:
1. 从 pg_control 读取 checkpoint 位置
2. 从 checkpoint redo 位置正向扫描 WAL
3. 对每条记录调用对应 RM(Resource Manager)的 redo 函数
4. 不需要显式 undo 阶段:
- MVCC 天然处理未提交事务的可见性
- CLOG 标记未提交事务为 aborted
- 后续 VACUUM 清理 dead tuple关键差异: PostgreSQL 没有 ARIES 的 undo 阶段。MVCC 使得未提交的 行版本不会被其他事务看到,因此不需要在恢复时立即回滚。
10.3 SQLite
SQLite 提供两种日志模式:
Rollback Journal:
修改页面前将原始页面复制到 .db-journal 文件。
提交时删除 journal。崩溃恢复:若 journal
存在,将页面复制回主数据库。 这是 undo-only
模式。
WAL 模式: 修改写入 .db-wal
文件,读取时先查 WAL 再查主文件。 Checkpoint 将 WAL
合并回主数据库,支持并发读写。
-- 切换到 WAL 模式
PRAGMA journal_mode=WAL;
-- 手动触发 checkpoint
PRAGMA wal_checkpoint(TRUNCATE);10.4 对比总结
| 特性 | InnoDB | PostgreSQL | SQLite WAL |
|---|---|---|---|
| 日志类型 | Redo + Undo | WAL (redo-only) | WAL (redo-only) |
| Undo 机制 | Undo log | MVCC + CLOG | 无需(单写者) |
| Checkpoint | Fuzzy (后台) | Fuzzy (后台) | 手动或自动 |
| 并行恢复 | 支持 | 不支持 | N/A |
| Full-page write | Doublewrite buffer | 有 (FPW) | 无 |
| Torn page 防护 | Doublewrite | Full-page image | 无(原子扇区写) |
| 典型恢复时间 | 秒到分钟级 | 秒到分钟级 | 毫秒级 |
十一、现代演进: WBL 与 NVM 感知日志
11.1 传统 WAL 的瓶颈
在 NVM(Non-Volatile Memory,如 Intel Optane DCPMM)时代, 传统 WAL 面临新的挑战:
- NVM 的读写延迟接近 DRAM(约 100-300ns), 但 WAL 仍在做大量的序列化写入;
- 双重持久化问题: 数据既写了日志又写了数据页, 在 NVM 上这个开销变得显著;
- 日志的顺序写优势减弱: NVM 的随机写和顺序写延迟差距远小于 SSD/HDD。
11.2 Write-Behind Logging (WBL)
Joy Arulraj 等人在 2016 年提出了 WBL,核心思想颠倒了 WAL:
WAL: 先写日志, 后写数据 (Write-Ahead)
WBL: 先写数据, 后写日志 (Write-Behind)WBL 的工作方式: 1. 事务直接在 NVM 上原地修改数据; 2. 提交时不需要写 redo log; 3. 定期写 commit-mark 日志,记录已提交事务的边界; 4. 恢复时通过 group commit boundary 识别和撤销未提交修改。
优势: 去掉 redo log 开销,减少写放大,恢复时间更短。 局限: 依赖 NVM 字节可寻址和持久性,需保证写入原子性 (clflush + mfence),实际部署系统还很少。
11.3 其他 NVM 感知方案
| 方案 | 核心思路 |
|---|---|
| MARS | 保留 ARIES 框架,redo log 放 NVM,用 clflush+mfence 替代 fsync |
| SiloR | Epoch-based group commit,只记录 after-image,依赖 checkpoint 恢复 |
| HALO | 热数据 WBL + 冷数据 WAL,按数据温度自动切换日志策略 |
11.4 NVM 编程的关键原语
#include <immintrin.h>
static inline void nvm_persist(void *addr, size_t len) {
for (size_t i = 0; i < len; i += 64)
_mm_clflushopt((char *)addr + i);
_mm_sfence();
}Intel Optane DCPMM 保证 8 字节对齐写入的原子性, 因此日志记录 header 通常包含一个 8 字节的 valid 标记,最后写入。
十二、工程陷阱与个人观点
12.1 工程陷阱速查表
| 陷阱 | 后果 | 应对措施 |
|---|---|---|
| fsync 只刷文件不刷目录 | 重命名后崩溃,新文件名丢失 | 对父目录也调用 fsync |
| O_DIRECT 未对齐 | 写入失败或静默数据损坏 | 内存和偏移按 512B/4KB 对齐 |
| fdatasync vs fsync | fdatasync 不刷 metadata | 文件大小变化时用 fsync |
| 依赖 write() 原子性 | POSIX 不保证大写入原子 | pwrite + 手动 CRC 校验 |
| Torn page(页面撕裂) | 页面一半新一半旧 | Doublewrite/FPW/checksum |
| Redo log 写满 | 数据库卡住或崩溃 | 监控 log space,及时 checkpoint |
| Undo tablespace 膨胀 | 长事务导致空间暴涨 | 监控长事务,设置超时 |
| Group commit 延迟 | 低负载时提交延迟增加 | 自适应等待时间 |
| 文件系统 barrier 被禁用 | fsync 返回成功但数据没到盘 | 确认挂载选项 barrier=1 |
| SSD 写缓存掉电丢失 | fsync 骗了你 | 使用带超级电容的企业级 SSD |
| ext4 delayed allocation | fsync 后 rename 仍可能丢 | 使用 XFS 或 data=journal |
| 内核版本差异 | fsync 语义有 bug | 使用 Linux 4.13+ |
12.2 个人观点
1. WAL 是数据库工程中最不容出错的模块。 查询优化器写烂了,最多查询慢;WAL 写烂了,数据没了。
2. ARIES 的 Repeating History 是一个伟大的工程简化。 “为什么要 redo 未提交事务的操作”——正是这个看似浪费的决定, 让 redo 阶段变成了无脑的日志重放机,极大简化了实现和验证。
3. 不要自己实现 WAL,除非你在写数据库。 SQLite WAL 模式或 RocksDB 的 WAL 已经足够好。 自己实现 WAL 的坑远比你想象的多:fsync 语义、torn page、 文件系统 bug、磁盘固件欺骗。
4. NVM 会改变游戏规则,但不是今天。 WBL 论文很漂亮,但部署面临的问题远不止算法层面。 目前最务实的做法是把 redo log 放在 NVM 上,其他不变。
5. Checkpoint 策略决定了恢复时间的上界。 如果 checkpoint 间隔太长,崩溃后 redo 日志量就大,恢复时间就长。 生产环境建议监控 redo log 使用率,设置合理的 checkpoint 频率。
6. 理解 ARIES 能帮你理解整个数据库。 ARIES 与缓冲池管理、锁管理、MVCC 都有深度交互。 理解了 Steal/No-Force 就理解了脏页刷盘策略; 理解了 CLR 和 prevLSN 就理解了 InnoDB undo log 的复杂性。
参考资料
- C. Mohan et al., “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging”, ACM TODS, 1992.
- Ramakrishnan, Gehrke, “Database Management Systems”, Chapter 18: Crash Recovery.
- Joy Arulraj et al., “Write-Behind Logging”, VLDB 2017.
- MySQL Source Code:
storage/innobase/log/,storage/innobase/trx/. - PostgreSQL Documentation: “WAL Internals”, “Reliability and the Write-Ahead Log”.
- SQLite Documentation: “Write-Ahead Logging”.
- Andy Pavlo, CMU 15-445/645 Lecture Notes: “Database Recovery”.
- Goetz Graefe, “A Survey of B-Tree Logging and Recovery Techniques”, ACM CSUR 2012.
上一篇: 缓冲池管理算法 下一篇: LSM-tree Compaction 策略
相关阅读: - B+tree 与 LSM-tree - MVCC 实现变体全解