并发算法 #03：MVCC（多版本并发控制）

MVCC（Multi-Version Concurrency Control，多版本并发控制）通过保留数据的历史版本，实现"读不阻塞写、写不阻塞读"，是 MySQL InnoDB、PostgreSQL、Oracle 等主流数据库实现高并发事务隔离的核心机制。

相关文章：CAS 与 ABA 问题 · AQS（AbstractQueuedSynchronizer） · 无锁队列（Michael-Scott Queue）

目录

核心思想

传统悲观锁的问题：读加共享锁，写加排他锁，读写互斥，高并发下吞吐量差。

MVCC 的解法：不修改原行，而是写新版本。

写操作：
  不覆盖原有数据，而是创建一个新版本
  把旧版本保存在 Undo Log 中
  通过指针把各版本串成链表（版本链）

读操作（快照读）：
  根据事务开始时的"快照"（ReadView）
  沿版本链找第一个"对我可见"的版本
  整个过程不加任何锁

结果：
  读者看到的是某个时刻的一致性快照
  写者可以同时修改，互不阻塞

InnoDB 隐藏字段

InnoDB 的每一行数据，除了用户定义的列，还有以下隐藏字段：

行记录结构（简化）：
┌─────────────────────────────────────────────────────┐
│  col1  │  col2  │ ... │ DB_ROW_ID │ DB_TRX_ID │ DB_ROLL_PTR │
└─────────────────────────────────────────────────────┘

DB_ROW_ID   (6 bytes)：
  若表没有主键，InnoDB 自动生成的行 ID
  有主键时该字段不存在

DB_TRX_ID   (6 bytes)：
  最后一次修改本行的事务 ID（单调递增）
  事务 ID 越大，说明事务越新

DB_ROLL_PTR (7 bytes)：
  回滚指针（rollback pointer）
  指向 Undo Log 中本行的上一个版本
  通过该指针串成版本链

事务 ID 的分配

规则：
  只读事务（没有修改操作）：不分配事务 ID（值为 0）
  读写事务（有 INSERT/UPDATE/DELETE）：在第一次修改时分配一个全局单调递增 ID

分配来源：
  InnoDB 全局维护 max_trx_id 计数器
  每次分配后递增：new_trx_id = max_trx_id; max_trx_id++
  该计数器持久化到系统表空间（崩溃恢复时不重置）

Undo Log 版本链

数据结构

版本链节点（Undo Log Record）：
  trx_id    : 本版本由哪个事务写入
  roll_ptr  : 指向更旧一个版本的指针（NULL 表示最旧版本）
  col_values: 本版本各列的值（UPDATE 时只存被修改的列）
  type      : INSERT_UNDO 或 UPDATE_UNDO

版本链示意（最新版本在表的数据页中，旧版本在 Undo Log 中）：

  当前行（数据页）              Undo Log
  ┌─────────────────┐          ┌──────────────────┐
  │ val="C"         │          │ val="B"          │
  │ DB_TRX_ID=300   │ ──→      │ DB_TRX_ID=200    │ ──→
  │ DB_ROLL_PTR=ptr1│          │ DB_ROLL_PTR=ptr2 │
  └─────────────────┘          └──────────────────┘
                                        │
                                        ↓
                               ┌──────────────────┐
                               │ val="A"          │
                               │ DB_TRX_ID=100    │
                               │ DB_ROLL_PTR=NULL │
                               └──────────────────┘

UPDATE 时版本链的变化

初始：行 R，val="A"，DB_TRX_ID=100，DB_ROLL_PTR=NULL

事务 200 执行 UPDATE R SET val="B"：
  Step 1：将当前行（val="A", trx=100）复制到 Undo Log，生成旧版本记录 V1
  Step 2：修改当前行：val="B"，DB_TRX_ID=200，DB_ROLL_PTR 指向 V1

事务 300 执行 UPDATE R SET val="C"：
  Step 1：将当前行（val="B", trx=200）复制到 Undo Log，生成旧版本记录 V2
  Step 2：修改当前行：val="C"，DB_TRX_ID=300，DB_ROLL_PTR 指向 V2
  V2.DB_ROLL_PTR 指向 V1（V1 已在 Undo Log 中）

最终版本链（新→旧）：
  [val=C, trx=300] → [val=B, trx=200] → [val=A, trx=100] → NULL

ReadView 结构

ReadView 是事务执行快照读时创建的"一致性视图"，记录了创建时刻所有活跃（未提交）事务的 ID 集合。

ReadView 字段定义：

  m_ids        : List<trx_id>
                 创建 ReadView 时，所有活跃（已启动但未提交）的读写事务 ID 列表
                 （不包括只读事务，因为只读事务没有 trx_id）

  min_trx_id   : trx_id = min(m_ids)
                 m_ids 中的最小值
                 若 m_ids 为空，则 min_trx_id = max_trx_id
                 含义：小于此值的事务一定已提交

  max_trx_id   : trx_id = 当前 max_trx_id（分配给下一个事务的 ID）
                 注意：这是"下一个将要分配的 ID"，不是 m_ids 中的最大值
                 含义：大于等于此值的事务一定在 ReadView 创建之后才启动

  creator_trx_id: trx_id = 创建本 ReadView 的事务的 trx_id
                 只读事务的 creator_trx_id = 0
                 含义：自己修改的数据，自己应该能看到

ReadView 示例

假设系统当前状态：
  已提交事务：100, 101, 102
  活跃事务：103（未提交），105（未提交）
  max_trx_id（下一个待分配）= 107
  当前事务（要做快照读的）= 104（已提交，不在活跃列表）

创建的 ReadView：
  m_ids          = [103, 105]
  min_trx_id     = 103
  max_trx_id     = 107
  creator_trx_id = 104

可见性判断

对版本链中的每个版本 V（V.trx_id 为写入该版本的事务 ID），判断 ReadView rv 是否能看到该版本：

function is_visible(V, rv) -> bool:

  // 情况1：自己写的，自己能看
  if V.trx_id == rv.creator_trx_id:
      return true

  // 情况2：版本的事务 ID < min_trx_id
  //        说明写该版本的事务在 ReadView 创建之前就已提交
  //        → 可见
  if V.trx_id < rv.min_trx_id:
      return true

  // 情况3：版本的事务 ID >= max_trx_id
  //        说明写该版本的事务在 ReadView 创建之后才启动
  //        → 不可见（未来的事务）
  if V.trx_id >= rv.max_trx_id:
      return false

  // 情况4：min_trx_id <= V.trx_id < max_trx_id
  //        需要检查该事务是否在活跃列表中
  if V.trx_id in rv.m_ids:
      // 该事务创建 ReadView 时尚未提交 → 不可见
      return false
  else:
      // 该事务创建 ReadView 时已提交（介于 min 和 max 之间，但不在活跃列表）
      return true

执行追踪

ReadView：m_ids=[103,105], min=103, max=107, creator=104

版本链：[val=C, trx=106] → [val=B, trx=105] → [val=A, trx=102]

判断 V1（trx=106）：
  106 != 104            → 不走情况1
  106 < 103 ?  否       → 不走情况2
  106 >= 107 ? 否       → 不走情况3
  106 in [103,105] ? 否 → 走情况4的 else → return true ✅
  结果：V1 可见，返回 val=C

（若 V1 不可见，则继续看 V2...）

判断 V2（trx=105）：
  105 != 104            → 不走情况1
  105 < 103 ?  否       → 不走情况2
  105 >= 107 ? 否       → 不走情况3
  105 in [103,105] ? 是 → return false ✗

判断 V3（trx=102）：
  102 != 104            → 不走情况1
  102 < 103 ?  是       → return true ✅
  结果：V3 可见，返回 val=A

版本链遍历

// 快照读：找版本链中第一个对 ReadView 可见的版本
function find_visible_version(row, rv) -> row_data | NULL:

  // 从当前行（最新版本）开始
  current_version = row   // row 在数据页中，含 DB_TRX_ID 和 DB_ROLL_PTR

  while current_version != NULL:
      if is_visible(current_version, rv):
          return current_version   // 找到了，返回该版本的列数据

      // 沿回滚指针走到上一个版本
      current_version = follow_roll_ptr(current_version.DB_ROLL_PTR)
      // follow_roll_ptr：根据 DB_ROLL_PTR 从 Undo Log 中读取上一版本记录

  // 版本链全部遍历完，没有可见版本
  // 说明该行对当前事务不可见（可能是在 ReadView 创建后才插入的）
  return NULL

INSERT 的特殊处理

INSERT 生成的 Undo Log 类型为 INSERT_UNDO：
  该类型的 Undo Log 在事务提交后立即可以被 purge 删除
  （因为 INSERT 之前没有旧版本，不需要给任何快照读用）

UPDATE/DELETE 生成的 Undo Log 类型为 UPDATE_UNDO：
  必须等到所有使用该版本的 ReadView 都销毁后才能 purge

RC vs RR 差异

两种隔离级别下，MVCC 的数据结构完全相同，唯一区别是 ReadView 的创建时机：

RC（Read Committed，读已提交）：
  每次 SELECT 都创建一个新的 ReadView
  → 每次读都能看到最新的已提交数据
  → 同一事务内两次 SELECT 可能看到不同结果（不可重复读）

RR（Repeatable Read，可重复读，InnoDB 默认）：
  事务第一次执行快照读时创建 ReadView，之后复用同一个 ReadView
  → 同一事务内每次 SELECT 看到的是同一个快照
  → 解决了不可重复读问题

执行追踪：RC vs RR

事务 A（隔离级别 RC 或 RR）：
  t1: BEGIN
  t2: SELECT val FROM t WHERE id=1   ← 首次快照读，两者都在此创建 ReadView

事务 B：
  t3: BEGIN
  t4: UPDATE t SET val="X" WHERE id=1
  t5: COMMIT                         ← 事务 B 提交

事务 A（继续）：
  t6: SELECT val FROM t WHERE id=1

RC 下 t6 的结果：
  t6 时创建新 ReadView，B 已提交 → 能看到 val="X" → 返回 "X"（不可重复读）

RR 下 t6 的结果：
  t6 时复用 t2 创建的 ReadView，B 的 trx_id 不在 m_ids 中但 >= max_trx_id
  （因为 B 在 t2 创建 ReadView 之后才修改）→ 不可见 → 返回旧值（可重复读）

快照读 vs 当前读

快照读（Snapshot Read）：
  普通 SELECT 语句
  使用 MVCC，读取历史版本，不加锁
  示例：SELECT * FROM orders WHERE user_id=1

当前读（Current Read）：
  读取行的最新提交版本，并加锁
  必须等待其他事务释放锁后才能读
  会阻塞，直到拿到锁

  触发当前读的语句：
    SELECT ... FOR UPDATE         （加排他锁 X）
    SELECT ... LOCK IN SHARE MODE （加共享锁 S，MySQL 8.0+ 改为 FOR SHARE）
    INSERT INTO ...
    UPDATE ...
    DELETE ...

为什么 DML 要用当前读：
  UPDATE/DELETE 必须基于最新数据修改，否则可能覆盖其他事务的更新
  快照读可能读到旧版本，如果以旧版本为基础写入，会丢失其他事务的修改

当前读与 Next-Key Lock

SELECT * FROM t WHERE id > 10 FOR UPDATE

InnoDB 当前读不仅锁定满足条件的行，还会加 Next-Key Lock（行锁+间隙锁）
  行锁：锁定 id>10 的现有行
  间隙锁（Gap Lock）：锁定 id>10 的间隙，防止其他事务在此范围 INSERT
  → 解决幻读（Phantom Read）

注意：RR 隔离级别下，快照读不会产生幻读（看的是快照）
      但当前读在没有 Gap Lock 时会产生幻读

Purge 线程

清理条件

Purge 线程负责清理不再需要的 Undo Log 记录。

可以清理一个 Undo Log 版本 V 的条件：
  所有活跃的 ReadView 中，min_trx_id > V.trx_id

  也就是说：没有任何活跃事务需要读取 V 这个版本

Purge 线程的工作流程：
  loop:
    purge_trx_id = min(所有活跃 ReadView 的 min_trx_id)
                 = 系统中最老的活跃快照所能看到的最旧事务 ID

    遍历 UPDATE_UNDO 日志：
      for each undo_record in undo_log:
          if undo_record.trx_id < purge_trx_id:
              删除该 undo_record
              更新版本链（将指向该版本的 DB_ROLL_PTR 改为 NULL 或下一有效版本）

    INSERT_UNDO：事务提交后立即可清理，不受 purge_trx_id 限制

    sleep(innodb_purge_batch_size 控制的时间)

清理示例

版本链：[val=C, trx=300] → [val=B, trx=200] → [val=A, trx=100]

系统中所有活跃 ReadView 的 min_trx_id 最小值 = 250

Purge 线程：
  purge_trx_id = 250
  检查 trx=100 的版本 A：100 < 250 → 可删除 ✅
  检查 trx=200 的版本 B：200 < 250 → 可删除 ✅
  检查 trx=300 的版本 C：300 >= 250 → 保留 ✗

清理后版本链：[val=C, trx=300] → NULL

异常场景

场景1：长事务导致 Undo Log 积压

问题描述：
  事务 T 在 t0 时刻开始，持有 ReadView（min_trx_id=1000）
  T 一直不提交（比如忘记 COMMIT，或者程序 bug 挂起）
  在此期间，大量写操作产生版本：trx=1001, 1002, ..., 5000

  Purge 线程：purge_trx_id = min(活跃 ReadView 的 min) = 1000
  所有 trx >= 1000 的版本全部无法清理 → Undo Log 急速膨胀

表现：
  ibdata1 / undo tablespace 文件不断增大
  磁盘可能被撑满
  每次快照读需要遍历更长的版本链，性能下降

监控方式：
  SHOW ENGINE INNODB STATUS\G    ← 查看 History list length（积压条数）
  SELECT * FROM information_schema.INNODB_TRX\G  ← 找长事务

解决：
  SET innodb_max_undo_log_size 控制 Undo Tablespace 大小
  监控长事务，超过阈值自动 KILL
  pt-kill（Percona Toolkit）自动杀死超时事务

场景2：快照读与幻读

问题描述：
  RR 隔离级别下，快照读不会产生幻读（看的是事务开始时的快照）
  但混合使用快照读和当前读时，可能出现幻读：

  t1: BEGIN                               事务 A
  t2: SELECT * FROM t WHERE age>18        快照读，看到 0 行（无数据）
                                          事务 B: INSERT INTO t VALUES(25); COMMIT
  t3: SELECT * FROM t WHERE age>18 FOR UPDATE  当前读，看到 1 行！← 幻读

原因：
  t3 的当前读读取最新提交数据，而不是快照
  尽管 t2 和 t3 在同一事务中，当前读"穿透"了快照

解决：
  始终使用快照读（不用 FOR UPDATE）
  或在第一次读时就加 FOR UPDATE，阻止其他事务 INSERT
  或使用 SERIALIZABLE 隔离级别（所有读都变成当前读，自动加 Next-Key Lock）

场景3：写偏斜（Write Skew）

问题描述（RR 隔离级别下仍存在）：

  业务约束：同一班次中，至少有一名医生在岗
  初始状态：医生 Alice 在岗=true，医生 Bob 在岗=true

  事务 A（Alice 请假）：
    t1: SELECT COUNT(*) FROM doctors WHERE on_duty=true   ← 快照读，看到 2
    t2: 判断 2 > 1，可以请假
    t3: UPDATE doctors SET on_duty=false WHERE id=alice

  事务 B（Bob 请假，与 A 并发）：
    t1: SELECT COUNT(*) FROM doctors WHERE on_duty=true   ← 快照读，也看到 2
    t2: 判断 2 > 1，可以请假
    t3: UPDATE doctors SET on_duty=false WHERE id=bob

  两个事务都提交后：Alice 在岗=false，Bob 在岗=false → 无人在岗！违反约束

原因：
  MVCC 快照读让两个事务都看到了"2人在岗"的旧快照
  各自修改不同的行，没有冲突，都能提交
  但整体状态违反了约束

解决：
  SELECT ... FOR UPDATE（当前读），两个事务会互斥
  或应用层加分布式锁
  或 SERIALIZABLE 隔离级别

场景4：DELETE 后的版本链

问题：DELETE 是否真的删除数据？

不是。DELETE 在 InnoDB 中是"标记删除"：
  在当前行（或新版本）上设置 delete_mark = 1
  并创建一条 DELETE_UNDO 记录加入版本链

  快照读逻辑：
    如果读到的版本 V.delete_mark == 1：
      该版本对快照读不可见（视为不存在）
      继续往旧版本找

  物理删除（purge）：
    等到所有 ReadView 都不再需要该版本时
    Purge 线程才真正从磁盘删除该行

场景5：RC 下并发 UPDATE 的"丢失更新"

RC 隔离级别下：

  初始：balance=100

  事务 A（快照读）：
    SELECT balance → 看到 100（快照）

  事务 B：
    UPDATE account SET balance=balance-50 → balance=50；COMMIT

  事务 A（当前读 / UPDATE）：
    UPDATE account SET balance=balance-30
    InnoDB 的 UPDATE 使用当前读：读到最新值 50
    执行后：balance=20 ✅

  InnoDB 实际上会在 UPDATE 时自动使用当前读
  避免了基于旧快照的丢失更新
  但显式的 SELECT + 应用层计算 + UPDATE 模式仍有丢失更新风险
  → 应使用 UPDATE account SET balance=balance-30（原子操作）
     或 SELECT ... FOR UPDATE

参考资料

• MySQL 官方文档：InnoDB Multi-Versioning
• MySQL 官方文档：InnoDB Transaction Model
• 《MySQL 技术内幕：InnoDB 存储引擎》第 6 章，姜承尧著
• 《高性能 MySQL》第 1 章，Baron Schwartz 等著
• Jeremy Cole: InnoDB internals: InnoDB File Formats and Source Code Structure