存储算法 #09：Redo 与 Undo Log

Redo Log 记录"做了什么"（物理变更）用于崩溃后重做已提交事务，Undo Log 记录"如何撤销"（逻辑旧值）用于回滚未提交事务与 MVCC 历史版本，两者共同实现 InnoDB、PostgreSQL 等数据库的 ACID 保障。

相关文章：WAL（Write-Ahead Log） · Bitcask

目录

图解

本质区别

为什么需要两种日志？

单靠一种日志无法同时满足"已提交的不丢"和"未提交的可撤销"两个需求：

• 已提交事务：数据页可能还在 Buffer Pool 中未落盘，崩溃后需要 Redo Log 重放物理变更，把"应该在磁盘上"的状态补回来。
• 未提交事务：操作已经写入 Buffer Pool（甚至可能刷盘），崩溃后或显式 ROLLBACK 时需要 Undo Log 将数据恢复到事务开始前的状态。
• MVCC：并发读写时，读事务需要看到事务开始时刻的"快照"，Undo Log 的版本链提供历史版本，无需加读锁。

Redo Log 数据结构

问题背景

磁盘 I/O 以页（通常 16KB）为单位，若每次事务提交都同步刷整个数据页，性能极差。Redo Log 以追加顺序写代替随机写数据页，只在提交时 fsync 日志文件即可保证持久性（WAL 原则）。

记录格式（物理日志）

RedoLogRecord {
    lsn        uint64   // Log Sequence Number，全局单调递增，标识日志位置
    trx_id     uint64   // 产生此记录的事务 ID
    space_id   uint32   // 表空间 ID
    page_no    uint32   // 页号（space_id + page_no 唯一确定一个数据页）
    offset     uint16   // 页内字节偏移
    length     uint16   // 新值长度（字节）
    new_value  []byte   // 新值（物理字节，与页格式绑定）
    checksum   uint32   // CRC32，防止日志本身损坏
}

关键字段说明

• LSN（Log Sequence Number）：全局单调递增的字节偏移量，表示"已写入日志的总字节数"。每个数据页头部也保存一个 page_lsn，表示"页面最后一次被修改时对应的 LSN"。崩溃恢复时，若 page_lsn >= redo_record.lsn，说明该变更已经刷盘，可跳过重做。
• Checkpoint LSN：系统定期将"已刷盘的最小 LSN"写入日志文件头，恢复时只需从 Checkpoint LSN 开始重放，而非从日志起点。

日志缓冲区（Log Buffer）

事务执行期间，Redo Log 先写入内存中的 log_buffer，提交时才调用 fsync 刷入磁盘。innodb_flush_log_at_trx_commit 控制刷盘策略：

Undo Log 数据结构

问题背景

事务回滚时需要将行数据恢复到修改前的状态。MVCC 读时需要沿版本链找到对应快照版本。Undo Log 以链表形式组织同一行的历史版本。

记录格式（逻辑日志）

UndoLogRecord {
    trx_id       uint64          // 产生此记录的事务 ID
    op_type      enum {          // 操作类型
                   INSERT,       //   INSERT undo：只需删除该行
                   UPDATE,       //   UPDATE undo：需恢复旧值
                   DELETE_MARK   //   DELETE undo：需清除删除标记
                 }
    table_id     uint64          // 表 ID
    primary_key  []byte          // 主键值（定位行）
    old_value    map[col][]byte  // 旧值（仅 UPDATE/DELETE_MARK 有效）
    roll_pointer uint64          // 指向该行上一个 Undo Log 记录的指针（版本链）
    next_undo    uint64          // 同一事务内下一条 Undo Log 的指针
}

版本链（MVCC 核心）

每行数据头部隐藏列：

Row {
    // ... 用户列 ...
    DB_TRX_ID     uint64   // 最后修改此行的事务 ID
    DB_ROLL_PTR   uint64   // 指向最新 Undo Log 记录（版本链头）
}

版本链示意（行 X 被连续修改）：

当前行 (trx=T3, val=8)
    ↓ DB_ROLL_PTR
UndoLog (trx=T3, old_val=5, roll_ptr→)
    ↓
UndoLog (trx=T1, old_val=1, roll_ptr→)
    ↓
nil（最初插入版本）

读事务根据自身快照版本（Read View）决定读哪个版本：若当前行 DB_TRX_ID 对读事务不可见，则沿版本链往下找，直到找到可见版本。

事务提交流程

伪代码（WAL 两阶段提交）

function ExecuteTransaction(ops):
    trx = BeginTransaction()
    undo_records = []

    // Phase 1: 执行操作，同步写 Undo Log，缓冲 Redo Log
    for op in ops:
        // 1a. 先写 Undo Log 到 undo tablespace（可立即 fsync 或延迟）
        undo_rec = BuildUndoRecord(trx.id, op.type, op.old_value, op.primary_key)
        WriteUndoLog(undo_rec)          // 持久化，以便回滚
        undo_records.append(undo_rec)

        // 1b. 在 Buffer Pool 中执行修改
        page = BufferPool.FetchPage(op.space_id, op.page_no)
        page.Apply(op)                  // 内存修改，页变为 Dirty

        // 1c. 将物理变更写入 Log Buffer（内存）
        redo_rec = BuildRedoRecord(trx.id, op.space_id, op.page_no,
                                   op.offset, op.new_value)
        LogBuffer.Append(redo_rec)      // 尚未 fsync

    // Phase 2: 提交
    // 2a. 关键：fsync Redo Log（WAL 原则，日志落盘才算提交）
    LogBuffer.Flush()                   // write() 到 OS 缓冲
    LogFile.Fsync()                     // 强制刷入磁盘

    // 2b. 写提交记录（commit marker），LSN 单调递增
    commit_lsn = LogBuffer.AppendCommitMarker(trx.id)
    LogFile.Fsync()

    // 2c. 标记事务已提交（内存状态）
    trx.status = COMMITTED

    // 2d. 数据页异步刷盘（由后台 checkpoint 线程负责）
    // BufferPool.AsyncFlushDirtyPages()  ← 不在事务提交临界路径上

    return SUCCESS


function Rollback(trx, undo_records):
    // 逆序回放 Undo Log
    for undo_rec in reversed(undo_records):
        if undo_rec.op_type == INSERT:
            DeleteRow(undo_rec.table_id, undo_rec.primary_key)
        elif undo_rec.op_type == UPDATE:
            RestoreRow(undo_rec.table_id, undo_rec.primary_key, undo_rec.old_value)
        elif undo_rec.op_type == DELETE_MARK:
            ClearDeleteMark(undo_rec.table_id, undo_rec.primary_key)
    trx.status = ABORTED

关键约束

1. Undo Log 必须在 Redo Log 之前或同时持久化：若先写 Redo 未写 Undo 就崩溃，恢复后无法回滚未提交事务。InnoDB 将 Undo Log 的修改也记录在 Redo Log 中（Undo 页的变更也是 Redo 保护的），保证一致性。
2. 数据页刷盘顺序任意：只要 Redo Log 已 fsync，数据页何时刷盘都可以，崩溃后可从 Redo Log 重建。
3. Undo Log 的清理（Purge）：事务提交后，Undo Log 不能立即删除，因为其他读事务可能还需要通过版本链访问历史版本。Purge 线程定期检查，当某条 Undo Log 已被所有活跃读事务的快照"越过"后才删除。

崩溃恢复：ARIES 三阶段

算法概述

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）是现代数据库崩溃恢复的标准算法，分三个阶段：

function CrashRecovery():
    // ========== Phase 1: Analysis（分析阶段）==========
    // 从最近 Checkpoint 开始扫描日志，重建崩溃时的系统状态
    checkpoint = ReadCheckpointFromLogHeader()
    dirty_page_table = checkpoint.dirty_pages   // 崩溃时 Buffer Pool 中的脏页
    active_trx_table = checkpoint.active_trxs  // 崩溃时活跃事务列表

    scan_lsn = checkpoint.lsn
    while scan_lsn < end_of_log:
        rec = ReadLogRecord(scan_lsn)
        if rec.type == UPDATE:
            if rec.page_id not in dirty_page_table:
                dirty_page_table[rec.page_id] = rec.lsn   // 记录页首次变脏的 LSN
            active_trx_table[rec.trx_id] = rec.lsn        // 更新事务最新 LSN
        elif rec.type == COMMIT:
            active_trx_table[rec.trx_id].status = COMMITTED
        elif rec.type == ABORT:
            active_trx_table[rec.trx_id].status = ABORTED
        scan_lsn = rec.next_lsn

    // ========== Phase 2: Redo（重做阶段）==========
    // 从 dirty_page_table 中最小 LSN 开始，重放所有日志（含未提交事务）
    // 目标：将 Buffer Pool 恢复到崩溃时的精确状态
    redo_start_lsn = min(dirty_page_table.values())

    for rec in LogRecords(from=redo_start_lsn, to=end_of_log):
        if rec.type != UPDATE:
            continue
        page = DiskIO.ReadPage(rec.space_id, rec.page_no)
        if page.page_lsn >= rec.lsn:
            continue    // 此变更已经刷盘，跳过（幂等性保证）
        page.Apply(rec.new_value, rec.offset, rec.length)
        page.page_lsn = rec.lsn
        BufferPool.Pin(page)

    // ========== Phase 3: Undo（撤销阶段）==========
    // 回滚所有在崩溃时未提交的事务（active_trx_table 中 status != COMMITTED）
    loser_trxs = [t for t in active_trx_table if t.status != COMMITTED]

    for trx in loser_trxs:
        // 逆序回放该事务的 Undo Log
        undo_rec = GetUndoLogHead(trx.id)   // 从事务最新 Undo 记录开始
        while undo_rec != nil:
            ApplyUndo(undo_rec)             // 物理恢复旧值
            WriteCompensationLogRecord(undo_rec)  // CLR：写补偿日志，防止 Undo 过程中再次崩溃
            undo_rec = undo_rec.prev        // 沿版本链向前
        MarkTransactionAborted(trx.id)

CLR（Compensation Log Record）

Undo 阶段写入的补偿日志，记录"已经撤销了哪些操作"。若 Undo 过程中再次崩溃，恢复时通过 CLR 知道哪些 Undo 步骤已完成，避免重复撤销。CLR 有一个 UndoNextLSN 字段，直接指向下一个需要撤销的日志记录，跳过已处理的部分。

执行追踪

场景设置

初始状态：行 X = 1，行 Y = 2

T1: UPDATE X = 5   （正常提交）
T2: UPDATE Y = 8   （崩溃时尚未提交）

执行过程（时序）

时刻  事件
────────────────────────────────────────────────────────────────
t1    T1 开始
t2    T1: 写 UndoLog-1 {trx=T1, type=UPDATE, pk=X, old=1}
t3    T1: Buffer Pool X.val = 5（内存修改）
t4    T1: 写 LogBuffer  RedoLog-1 {lsn=100, trx=T1, page=PX, off=8, new=5}
t5    T2 开始
t6    T2: 写 UndoLog-2 {trx=T2, type=UPDATE, pk=Y, old=2}
t7    T2: Buffer Pool Y.val = 8（内存修改）
t8    T2: 写 LogBuffer  RedoLog-2 {lsn=200, trx=T2, page=PY, off=8, new=8}
t9    T1 提交：LogFile.Fsync()，写 CommitMarker {lsn=300, trx=T1}
t10   T1 提交成功，trx_table[T1] = COMMITTED
t11   💥 数据库崩溃（T2 未提交，PX/PY 均未刷盘）

崩溃恢复过程

Phase 1: Analysis

从 Checkpoint（假设 lsn=50）扫描到日志末尾：
  lsn=100: UPDATE → dirty_page_table[PX]=100, active_trx[T1]=100
  lsn=200: UPDATE → dirty_page_table[PY]=200, active_trx[T2]=200
  lsn=300: COMMIT → active_trx[T1].status = COMMITTED

结果：
  dirty_page_table = {PX: 100, PY: 200}
  active_trx = {T1: COMMITTED, T2: ACTIVE}  ← T2 是 loser

Phase 2: Redo（从 lsn=100 开始）

处理 RedoLog-1 {lsn=100, page=PX, off=8, new=5}:
  读磁盘 PX，page_lsn=0 < 100 → 重做：PX.val[off=8] = 5，page_lsn = 100 ✓

处理 RedoLog-2 {lsn=200, page=PY, off=8, new=8}:
  读磁盘 PY，page_lsn=0 < 200 → 重做：PY.val[off=8] = 8，page_lsn = 200 ✓

（注意：T2 的操作也被 Redo，目的是先恢复崩溃时的精确内存状态）

Phase 3: Undo（T2 是 loser）

读 UndoLog-2 {trx=T2, type=UPDATE, pk=Y, old=2}:
  恢复 PY.val = 2（写入 Buffer Pool）
  写 CLR {lsn=400, undoes=200, undo_next=nil}
  PY.page_lsn = 400

标记 T2 ABORTED，写 AbortMarker {lsn=500, trx=T2}

最终状态

行 X = 5  ✓（T1 已提交，Redo 恢复）
行 Y = 2  ✓（T2 未提交，Undo 回滚）

InnoDB 具体实现

Redo Log 文件

$DATADIR/
├── ib_logfile0     // Redo Log 文件 0，固定大小（默认 48MB）
└── ib_logfile1     // Redo Log 文件 1，固定大小

写入方式：循环写（ring buffer）
  write_pos → 当前写入位置
  checkpoint_pos → 已刷盘数据页对应的最小 LSN 位置

可用空间 = checkpoint_pos - write_pos（取模）
当 write_pos 追上 checkpoint_pos 时：写入阻塞，强制 checkpoint

Undo Log 存储

MySQL 5.6 之前：存储在系统表空间（ibdata1），无法收缩
MySQL 5.6+    ：可配置独立 undo tablespace（undo001, undo002...）
MySQL 8.0+    ：默认 2 个独立 undo tablespace，支持在线 truncate

Undo Log 内部组织：
  Rollback Segment（回滚段，默认 128 个）
    └── Undo Log Segment（每个事务分配一个）
          └── Undo Page（16KB，与数据页相同大小）
                └── Undo Log Records（链表）

Checkpoint 机制

Sharp Checkpoint（全量刷盘）：
  数据库关闭时，将所有脏页刷盘，更新 checkpoint_lsn = max_lsn

Fuzzy Checkpoint（增量）：
  后台线程（Master Thread / Page Cleaner Thread）定期刷部分脏页
  checkpoint_lsn = min(dirty_page_table.lsn_values)
  将 checkpoint_lsn 写入 ib_logfile0 头部

恢复时只需从 checkpoint_lsn 开始重放，缩短恢复时间

Purge 线程

Purge Thread 工作流程：
  1. 维护全局 min_active_trx_id（所有活跃事务中最小的事务ID）
  2. 扫描 Undo Log Segment
  3. 对于 trx_id < min_active_trx_id 的 Undo Log 记录：
     - INSERT 类型：直接删除（无需历史版本）
     - UPDATE/DELETE 类型：若无读事务需要，则删除
  4. 释放 Undo Page，归还 Rollback Segment

配置参数：
  innodb_purge_threads = 4        // 并发 Purge 线程数
  innodb_max_purge_lag = 0        // Purge 积压阈值（0=不限制）
  innodb_max_purge_lag_delay = 0  // 积压时写操作延迟上限（微秒）

异常场景

场景 1：Redo Log 写满（写入阻塞）

触发条件：write_pos 追上 checkpoint_pos，环形日志无可用空间。

处理流程：

检测到 write_pos ≈ checkpoint_pos：
  1. 暂停所有新的写事务（write stall）
  2. 强制触发 Checkpoint：
     a. Page Cleaner 线程将脏页刷盘（急迫模式）
     b. 更新 checkpoint_lsn = min(dirty_page_table.lsn)
     c. 写 checkpoint_lsn 到日志文件头
  3. checkpoint_pos 前移，释放日志空间
  4. 恢复写入

预防：增大 innodb_log_file_size（8.0.30+ 为 innodb_redo_log_capacity），减少长事务，监控 Innodb_log_waits。

场景 2：长事务导致 Undo Log 链过长

触发条件：一个事务长时间运行，产生大量 Undo Log，同时阻塞 Purge 线程回收历史版本。

危害：

问题链：
  长事务 T_long（trx_id=100）未提交
    → min_active_trx_id = 100
    → 所有 trx_id >= 100 的 Undo Log 不能被 Purge
    → Undo tablespace 持续膨胀（可达数十 GB）
    → MVCC 读需要遍历超长版本链，查询变慢
    → 极端情况：Undo tablespace 写满，数据库挂起

检测与应对：

-- 查看长事务
SELECT * FROM information_schema.INNODB_TRX
WHERE TIME_TO_SEC(TIMEDIFF(NOW(), trx_started)) > 60
ORDER BY trx_started;

-- 查看 Undo Log 积压
SHOW ENGINE INNODB STATUS;  -- 查看 History list length

场景 3：Redo Log 的 LSN 幂等性校验

场景：数据页已经成功刷盘（page_lsn = 500），但崩溃后 Redo Log 中仍存在 lsn=500 的记录。

处理：

Redo Phase 处理 RedoLog {lsn=500, page=P, ...}:
  读磁盘页 P，获取 page.page_lsn = 500
  判断：page.page_lsn (500) >= rec.lsn (500) → 跳过，不重做

原则：重做操作是幂等的，重复执行不会导致数据损坏，
     但通过 page_lsn 校验可以跳过已完成的操作，提升恢复速度。

场景 4：Double Write Buffer 防止部分页写（Torn Write）

问题：Redo Log 是物理日志，依赖数据页是完整的。若数据页（16KB）在刷盘过程中崩溃，只写入了部分（OS 的 4KB 页），页面损坏，Redo Log 无法应用（因为逻辑偏移量在损坏页上无意义）。

解决：

Double Write Buffer 写入流程：
  1. 将脏页先批量写入 ibdata1 中的 doublewrite buffer 区域（顺序写，2MB）
  2. fsync doublewrite buffer
  3. 再将脏页写入各自真实位置（随机写）
  4. 崩溃恢复时：若数据页损坏，从 doublewrite buffer 恢复完整页，再应用 Redo Log

代价：每个数据页写入两次，写放大约 1.1x（因为步骤1是顺序写，性能较好）

参考资料

1. ARIES 论文：Mohan et al., "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging", ACM TODS 1992.
2. InnoDB 内部实现：MySQL 8.0 Reference Manual - InnoDB Redo Log
3. InnoDB Undo Log：MySQL 8.0 Reference Manual - InnoDB Undo Logs
4. CMU 15-445 课件：Lecture 20 - Database Logging, Lecture 21 - ARIES（Andy Pavlo, Carnegie Mellon University）
5. 《MySQL技术内幕：InnoDB存储引擎》（第2版），姜承尧，机械工业出版社，第7章「事务」
6. PostgreSQL WAL 内部结构：PostgreSQL Internals - WAL Reliability