存储算法 #07：WAL（Write-Ahead Log）

WAL（Write-Ahead Log）通过"先写日志再改数据"保证崩溃后数据可恢复，是 InnoDB、PostgreSQL、etcd、RocksDB 等几乎所有持久化存储系统的核心机制。

章节	说明
核心思想	顺序写日志 vs 随机写数据页
WAL 记录结构	LSN、事务ID、前后镜像、checksum
写入流程	从事务提交到数据落盘的完整步骤
崩溃恢复：ARIES 三阶段	Analysis → Redo → Undo
Checkpoint 机制	缩短恢复范围，定期刷脏页
执行追踪	T1 提交、T2 崩溃的完整 Redo/Undo 过程
Group Commit 优化	批量 fsync 大幅提升写吞吐
异常场景	WAL 写满、fsync 失败、torn write、LSN 不一致
各系统实现对比	InnoDB / PostgreSQL / etcd / RocksDB

核心思想

问题背景：数据库需要在系统崩溃（断电、进程 crash）后保证已提交事务的数据不丢失（Durability）。

朴素方案：事务提交时直接将数据页刷盘
  问题：数据页是随机写（每个页在磁盘不同位置）
        100 个 4KB 数据页 → 100 次随机 I/O
        机械磁盘随机 I/O：约 100 IOPS（10ms/次）
        → 1 秒只能提交约 10 个事务，极低吞吐

WAL 方案：
  日志是顺序追加（Append-Only），一次顺序写 = 磁盘最优模式
  机械磁盘顺序写：约 100 MB/s
  → 先把操作记录到日志（顺序写，快），再异步刷数据页（批量，均摊随机 I/O）
  → 崩溃后从日志重放恢复

核心原则：
  1. 日志必须先于数据页落盘（Write-Ahead）
  2. 事务提交 = WAL 落盘（而非数据页落盘）
  3. 数据页可以延迟异步刷盘

wal structure

WAL 记录结构

每条 WAL 记录（WAL Record）包含以下字段：

WAL Record {
    lsn         uint64    // Log Sequence Number，单调递增，标识日志位置（字节偏移量）
    txn_id      uint64    // 事务 ID
    op_type     enum      // INSERT / UPDATE / DELETE / BEGIN / COMMIT / ABORT / CHECKPOINT
    page_id     uint64    // 被修改的数据页 ID（BEGIN/COMMIT/ABORT 无此字段）
    prev_lsn    uint64    // 同一事务上一条 WAL 记录的 LSN（构成链表，用于 Undo）
    before_img  bytes     // 前镜像（undo 数据：修改前的旧值）
    after_img   bytes     // 后镜像（redo 数据：修改后的新值）
    checksum    uint32    // CRC32 校验，检测 torn write（部分写）
    length      uint32    // 记录总长度（用于反向扫描）
}

LSN 的关键作用：
  - 每个数据页头部记录 page_lsn（该页最后一次被修改时对应的 WAL LSN）
  - Redo 时：WAL record.lsn ≤ page.page_lsn → 跳过（已经反映）
  - Redo 时：WAL record.lsn > page.page_lsn → 重放（需要应用）

写入流程

函数 WriteTransaction(txn, operations):
    // 阶段1：写 WAL
    for each op in operations:
        record = buildWALRecord(
            lsn       = nextLSN(),          // 全局单调递增计数器
            txn_id    = txn.id,
            op_type   = op.type,
            page_id   = op.pageId,
            prev_lsn  = txn.lastLSN,        // 链接同一事务的前一条记录
            before_img= op.oldValue,
            after_img = op.newValue,
            checksum  = crc32(record)
        )
        appendToWALBuffer(record)           // 写入内存 WAL Buffer（未落盘）
        txn.lastLSN = record.lsn

    // 写 COMMIT 记录
    commitRecord = buildWALRecord(op_type=COMMIT, txn_id=txn.id, ...)
    appendToWALBuffer(commitRecord)

    // 阶段2：WAL 落盘（关键！事务提交的唯一条件）
    fsync(WALBuffer → WALFile)              // 确保日志物理写入磁盘
    txn.commitLSN = commitRecord.lsn        // 提交 LSN 已持久化

    // 阶段3：修改内存 Buffer Pool（此时事务已经"提交"）
    for each op in operations:
        page = bufferPool.getPage(op.pageId)
        applyChange(page, op.newValue)
        page.pageLSN = op.walRecord.lsn     // 更新页面 LSN
        markDirty(page)                     // 标记为脏页，等待异步刷盘

    // 阶段4：数据页异步刷盘（后台线程，不阻塞提交）
    // 后台 PageFlusher 线程：
    //   选取最老的脏页批量刷盘
    //   刷盘前无需等 WAL（WAL 已经落盘，保证 Write-Ahead 原则）

    return SUCCESS

崩溃恢复：ARIES 三阶段

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）是数据库崩溃恢复的标准算法。

阶段1：Analysis（分析）

函数 Analysis(WALFile):
    // 从最后一个 Checkpoint 开始扫描
    checkpoint = findLastCheckpoint(WALFile)
    scanStart = checkpoint.lsn

    dirtyPageTable = {}   // 脏页表：page_id → recLSN（最早使该页变脏的 LSN）
    txnTable = {}         // 活跃事务表：txn_id → {status, lastLSN}

    // 恢复 checkpoint 时记录的状态
    for each entry in checkpoint.dirtyPages:
        dirtyPageTable[entry.pageId] = entry.recLSN
    for each entry in checkpoint.activeTxns:
        txnTable[entry.txnId] = {status: ACTIVE, lastLSN: entry.lastLSN}

    // 从 checkpoint 向前扫描到 WAL 末尾
    for each record in WALFile.scanForward(from=scanStart):
        txn = txnTable.getOrCreate(record.txn_id)
        txn.lastLSN = record.lsn

        if record.op_type == COMMIT:
            txn.status = COMMITTED
        elif record.op_type == ABORT:
            txn.status = ABORTED
        elif record.op_type in [INSERT, UPDATE, DELETE]:
            txn.status = ACTIVE
            if record.page_id not in dirtyPageTable:
                dirtyPageTable[record.page_id] = record.lsn   // 首次变脏的 LSN

    // 分析结果：
    //   redoLSN = min(dirtyPageTable.values)  // Redo 从最早脏页 LSN 开始
    //   undoList = {txn | txn.status == ACTIVE}  // 需要回滚的未提交事务
    return (dirtyPageTable, txnTable, redoLSN)

阶段2：Redo（重做）

函数 Redo(WALFile, dirtyPageTable, redoLSN):
    // 从 redoLSN 向前扫描，重放所有操作（包括后来回滚的事务！）
    for each record in WALFile.scanForward(from=redoLSN):
        if record.op_type not in [INSERT, UPDATE, DELETE]:
            continue                        // 跳过非数据修改记录

        page = bufferPool.getPage(record.page_id)

        // 判断是否需要重做
        if record.page_id in dirtyPageTable:
            recLSN = dirtyPageTable[record.page_id]
            if record.lsn < recLSN:
                continue                    // 该记录早于脏页首次记录，跳过
        if page.pageLSN >= record.lsn:
            continue                        // 该页已经反映此操作，跳过

        // 需要重做：应用后镜像
        applyChange(page, record.after_img)
        page.pageLSN = record.lsn
        markDirty(page)

阶段3：Undo（回滚）

函数 Undo(WALFile, txnTable):
    // 对所有 ACTIVE 事务（崩溃时未提交）进行回滚
    undoList = [txn for txn in txnTable if txn.status == ACTIVE]

    // 按 LSN 从大到小处理（最新的操作先撤销）
    while undoList is not empty:
        // 找到 lastLSN 最大的事务
        txn = undoList.maxByLastLSN()
        record = WALFile.getRecord(txn.lastLSN)

        if record.op_type in [INSERT, UPDATE, DELETE]:
            // 生成 CLR（Compensation Log Record）并追加到 WAL
            clr = buildCLR(
                txn_id    = txn.id,
                page_id   = record.page_id,
                undoNextLSN = record.prev_lsn,  // 下一个需要 Undo 的 LSN
                after_img = record.before_img    // 用前镜像恢复旧值
            )
            appendAndFlush(clr)

            // 应用前镜像（撤销该操作）
            page = bufferPool.getPage(record.page_id)
            applyChange(page, record.before_img)
            page.pageLSN = clr.lsn

        // 移动到该事务的上一条记录
        txn.lastLSN = record.prev_lsn
        if txn.lastLSN == NULL:
            undoList.remove(txn)                // 该事务所有操作已回滚完毕

Checkpoint 机制

问题：没有 Checkpoint，每次崩溃都要从头扫描整个 WAL（可能 GB 级别）

Checkpoint 流程（Fuzzy Checkpoint，不阻塞正常事务）：
    1. 记录当前时刻的 dirtyPageTable 和 activeTxnTable 到 WAL
    2. 将 Checkpoint 记录的 LSN 写入 checkpoint.lsn 文件
    3. 后台异步将 dirtyPageTable 中的脏页刷盘
    4. 脏页刷盘完成后，更新 checkpoint.lsn（提高恢复起始点）

效果：
    崩溃恢复只需从 checkpoint.lsn 开始扫描
    而不是从 WAL 起点扫描

WAL 空间回收：
    LSN ≤ checkpoint.lsn 的 WAL 段文件可以安全删除/复用
    （因为这些操作已确认写入数据页）

关键参数（InnoDB 示例）：
    innodb_log_file_size = 512MB   // 单个 redo log 文件大小
    innodb_flush_log_at_trx_commit:
        0 = 每秒刷一次（最快，可能丢 1 秒数据）
        1 = 每次提交 fsync（最安全，默认）
        2 = 每次提交写 OS buffer，每秒 fsync（折中）

执行追踪

场景：事务 T1（写 X=5）已提交，事务 T2（写 Y=10）未提交时系统崩溃。

崩溃前 WAL 内容：

LSN  | TXN | OP      | PAGE | BEFORE | AFTER
-----|-----|---------|------|--------|------
100  | T1  | BEGIN   |  -   |   -    |   -
110  | T1  | UPDATE  | P_X  |  X=0   |  X=5
120  | T1  | COMMIT  |  -   |   -    |   -
130  | T2  | BEGIN   |  -   |   -    |   -
140  | T2  | UPDATE  | P_Y  |  Y=0   |  Y=10
[CRASH 发生，T2 的 COMMIT 未写入]

磁盘上数据页状态（崩溃时）：
  P_X.pageLSN = 110（T1 的修改已刷盘，X=5）
  P_Y.pageLSN = 0   （T2 的修改未刷盘，Y=0）

=== Analysis 阶段 ===
扫描 WAL，得到：
  txnTable = {T1: COMMITTED, T2: ACTIVE}
  dirtyPageTable = {P_X: recLSN=110, P_Y: recLSN=140}
  redoLSN = min(110, 140) = 110

=== Redo 阶段（从 LSN=110 开始）===
处理 LSN=110（T1 UPDATE P_X X=5）：
  P_X.pageLSN = 110 = record.lsn → 跳过（P_X 已反映此操作）
处理 LSN=140（T2 UPDATE P_Y Y=10）：
  P_Y.pageLSN = 0 < 140 → 需要重做
  → 应用 after_img：P_Y.Y = 10，P_Y.pageLSN = 140
  [注意：Redo 阶段对所有事务都重做，包括未提交的 T2]

Redo 后内存状态：
  P_X: X=5（pageLSN=110）
  P_Y: Y=10（pageLSN=140）← 重做了 T2 的修改

=== Undo 阶段 ===
undoList = [T2]（T2 状态为 ACTIVE，需回滚）

T2 的 lastLSN = 140
  → 取 LSN=140 的记录（T2 UPDATE P_Y Y→10）
  → 生成 CLR：LSN=150，txn=T2，page=P_Y，after_img=Y=0（前镜像）
  → 应用前镜像：P_Y.Y = 0，P_Y.pageLSN = 150
  → T2.lastLSN = record.prev_lsn = 130（T2 BEGIN 的 LSN）
  → 取 LSN=130（T2 BEGIN），无需撤销
  → T2 回滚完成，从 undoList 移除

最终恢复结果：
  P_X: X=5 ✅（T1 已提交，数据正确）
  P_Y: Y=0 ✅（T2 未提交，回滚到初始值）

Group Commit 优化

问题：每次 fsync 需要约 1-10ms（磁盘寻道 + 旋转延迟）
     每个事务独立 fsync → 吞吐受限于 fsync 延迟

Group Commit 思想：
  多个并发事务将各自的 WAL record 追加到同一个 WAL Buffer
  由一个线程代表整个 group 执行一次 fsync
  fsync 完成后通知 group 内所有事务"提交成功"

InnoDB Group Commit 实现（三阶段 mutex）：

阶段1：FLUSH stage
  各事务将 WAL 写入 log buffer
  第一个到达的事务成为 leader，其余进入等待队列

阶段2：SYNC stage
  leader 代表整个 group 执行 fsync
  group 内积累的事务越多，每个事务的 fsync 均摊成本越低

阶段3：COMMIT stage
  leader 按顺序提交 group 内所有事务（释放锁、更新 binlog 位点）

效果对比：
  单独 fsync：1000 TPS（每个事务 1ms fsync 延迟）
  Group Commit：50000+ TPS（50 个事务共享 1 次 fsync）

伪代码：
    函数 GroupCommit(txn):
        // 加入 flush 队列
        flushQueue.enqueue(txn)
        
        if isLeader(txn):
            // 等待一批事务积累（或超时）
            group = waitForGroup(timeout=1ms)
            // 执行一次 fsync 覆盖整个 group 的 WAL
            fsync(WALFile, upToLSN=group.maxLSN)
            // 通知 group 内所有事务
            for each t in group:
                t.notifyCommitted()
        else:
            waitForNotification()   // 等待 leader 完成

异常场景

1. WAL 文件写满

InnoDB（redo log）：固定大小循环覆盖
  ib_logfile0 + ib_logfile1 共 1GB（可配置）
  write_pos 追着 checkpoint_lsn 跑
  当 write_pos 追上 checkpoint_lsn → 停止所有写事务，强制 checkpoint（刷脏页）

  [ 0 .... checkpoint_lsn .... write_pos .... 1GB ]
    ↑可覆盖区域↑              ↑不可覆盖↑

PostgreSQL（WAL）：新增 Segment 文件
  WAL 目录下按序新增 pg_wal/000000010000000000000001 等文件
  pg_archivemode 开启后归档旧 segment，释放空间
  无大小上限，但磁盘满时系统暂停

2. fsync 失败

场景：fsync 系统调用返回错误（磁盘故障、文件系统错误）

风险：
  WAL 未落盘但代码继续执行 → 内存中数据页被修改
  系统崩溃后 WAL 不完整 → 无法恢复已提交事务 → 数据丢失

正确处理：
  fsync 返回非零错误码 → 立即 PANIC（数据库宕机）
  拒绝继续提交任何事务
  等待人工干预后从备份恢复

  PostgreSQL 曾因 Linux 内核 bug（fsync 忽略了已写入 page cache 的脏页）
  在特定场景下出现数据损坏，2018 年引发社区大讨论，最终修复内核行为。

3. Torn Write（部分写）

场景：WAL 记录跨越两个磁盘块（512B 或 4KB），写入中途断电
     → 磁盘上只有前半段，后半段为旧数据

检测：每条 WAL 记录末尾含 checksum（CRC32）
     恢复时计算 checksum 不一致 → 该记录不完整，停止 Redo

处理：
  找到最后一条 checksum 正确的 WAL 记录
  截断之后的内容（PostgreSQL 直接截断，InnoDB 停在最后完整记录）
  事务提交需要 COMMIT 记录完整写入，COMMIT 前的 torn write → 该事务自动回滚

InnoDB Double Write Buffer 解决数据页 torn write：
  刷数据页前先整体写入 doublewrite buffer（顺序写，原子覆盖）
  再写入实际数据页位置
  崩溃后检测到数据页不完整 → 从 doublewrite buffer 恢复

4. WAL 与数据页 LSN 不一致

场景：Redo 阶段，WAL 说某页 pageLSN 应为 500，但磁盘上该页 pageLSN = 300

分析：
  300 < 500 → 数据页落后于 WAL（正常，需要 Redo）
  直接应用 WAL 后镜像，更新 pageLSN = 500 ✅

异常情况：
  磁盘上页 pageLSN = 800 > WAL 中对应记录 LSN 500
  说明该页曾被修改（LSN=800），但对应的 WAL 未刷盘就崩溃了
  → 违反了 Write-Ahead 原则（通常是 bug 或硬件错误）
  → 数据库应该 PANIC，不能继续恢复

各系统实现对比

系统	WAL 形式	大小限制	循环方式	特点
InnoDB	redo log	固定（默认 2×512MB）	循环覆盖	只记录物理修改（after_img），恢复最快
PostgreSQL	WAL segment	无上限	新增段文件	物理 + 逻辑混合，支持 PITR（时间点恢复）
etcd	Raft WAL	无上限	快照后截断	WAL = Raft log，条目 = KV 操作
RocksDB	WAL + MemTable	无上限	MemTable flush 后截断	WAL 写入后进 MemTable，flush 后 WAL 可删
SQLite	WAL mode	文件大小	checkpoint 后清零	单文件 WAL，读写并发友好

InnoDB redo log 循环覆盖示意：

ib_logfile0 [LSN 1000..............5000]
ib_logfile1 [LSN 5000..............9000]
                                    ↑
                               write_pos（当前写入位置）
            ↑
       checkpoint_lsn（已刷盘的最高 LSN，此前可覆盖）

当 write_pos 绕回追上 checkpoint_lsn 时：
  停止新事务 → 触发强制 checkpoint → 推进 checkpoint_lsn → 继续写入

RocksDB WAL + MemTable 流程：

写入路径：
  1. 追加到 WAL（磁盘顺序写）
  2. 写入 MemTable（内存跳表）
  3. 返回成功

后台：
  MemTable 达到阈值 → flush 为 SSTable（L0）
  对应的 WAL 段可以删除（数据已在 SSTable 持久化）

参考资料

Mohan, C. et al. (1992). ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS.

PostgreSQL 官方文档：WAL Reliability

MySQL 官方文档：InnoDB Redo Log

RocksDB Wiki：Write Ahead Log

《Database Internals》Alex Petrov，Chapter 7: Log-Structured Storage