MySQL MVCC机制与Undo Log

MySQL的多版本并发控制（MVCC）是如何实现多版本的，真是冗余了一个完整的快照么？这个值得学习了解。

如果了解了的话，简单说，MVCC是利用了ReadView + Undo Log解决的。下边我们细看下：

事务隔离级别

当然多版本并发控制就是和事务隔离级别有关，MySQL/Innodb支持以下四个事务隔离级别：

• Read Uncommitted

  读未提交。当前事务可以读到其他事务未提交的数据。

• Read Commited

  读已提交。事务每次读，可以读到其他事务最新提交的数据。

• Repeatable Read

  可重复读。MySQL/Innodb 默认隔离级别。事务每次读，都可以保持和事务启动后第一次读到的数据一致性，即快照读（中间自己修改了自己感知）

• Serializable

  串行化。“写”会加“写锁”，“读”会加“读锁”。当出现读写锁冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行

Undo Log

Undo Log我们比较熟知的是作为回滚段，正是这个作用，也可以用它来回溯历史版本数据。

每一行数据都有多个版本，每个版本都有自己的row trx_id，并通过Undo Record（Undo Record是每一个回滚版本的数据结构）中的指针把每个事务变更的版本链接起来，形成历史链。每个版本并不是这一行的全部field，而是包含这次修改的field和主键等信息。

想想这个历史链最早能追溯到哪个版本呢？最早就是这个insert插入的版本了（也可能中间的无用版本已经被purge掉了）。除了insert版本，其他就都可以认为是更新版本了（delete也是先修改的标记位，不是立刻删除。因为其他事务可能还会可见这个数据）。因此Undo Record 可分插入和更新两种类型看：

Insert类型的Undo Record

值得说的是Table Id和 Key Fileds

• Table ID用来表示是哪张表的修改。

• Key Fields是记录的主键信息。其长度不定，因为对应表的主键可能由多个field组成，这里需要记录Record完整的主键信息，回滚的时候可以通过这个信息在索引中定位到对应的Record。

Insert类型的没有回滚指针，这行能回滚的最早的就是这个插入版本，它对应的回滚就是delete。

Update类型的Undo Record

显然Update类型的记录的信息要更多，除了Insert类型包含的，值得说的

• Transaction Id

  这个trx_id 记录的是本次更新的上一个事务id，这点要明确。因为本次事务id的更新已经体现在最新的record中了，这里记录的是上一个要回滚到的事务id

• RollPtr

  通过它来把历史版本的数据链起来，指向的是该记录的上一个版本的位置

• Update Fields

  记录的所有被修改的Field的编号，长度和历史值。 注意这里记录的是历史值，undo log存的diff的老数据，毕竟新版数据已经在record中了。

  因为每个undo record只有两次的diff数据，因此回溯某一个版本的完整数据时，要把最新的record记录和每一个途经版本的数据进行merge。

Undo Record 构造历史链路

同一个行记录被不同事务修改，会产生不同的历史版本，这些历史版本又通过Rollptr穿成一个链表，供MVCC使用。下边给一个图示加深理解：

Undo Record组织成 Undo Log

上边介绍的Undo Record 是某一行的历史链路的版本数据。而一个事务中，会操作多个行数据，这就需要把这些Undo Record组织起来，这些Undo Record首尾相连就组成了这个事务的Undo Log。图示：

Undo Log Header中记录了trx_id，trx_no 等：

• trx_id 产生这个Undo Log的事务的trx_id
• trx_no 是事务的提交顺序，用这个来判断是否能Purge，后边再介绍下。

Purge Undo Log

Purge Undo Log 即清除无用的undo log。历史版本undo record要占用磁盘空间，而一行记录更早的版本可能在现存的事务里根本不会再用了，这就要删除掉。

具体purge哪些版本的undo record，这里引出一个trx_no，简单对比下trx_no和trx_id：

• trx_id 在事务开启的时候，向Innodb 申请的严格递增的trx_id。
• trx_no 在每次事务 commit 阶段申请，体现了事务的 commit 顺序。

在 purge 阶段使用 oldest read-view 的 trx_no 来和 undo log 里记录的 trx_no 比较判断是否可以被安全的 purge.

如果Undo Log中的 trx_no 比 oldest ReadView 中的 trx_no 还要小，那么说明这个Undo Log已经不会再有事务使用了，表示可以purge删除了。

ReadView

有了上边介绍的Undo Log知识，也知道事务开启时所谓的快照并不是真正的冗余一份，而是每一个行依赖undo record形成的多个版本。

InnoDB里面每个事务有一个唯一的事务ID：trx_id，它是在事务启动时向InnoDB申请的，是递增的。每一行数据的历史链路包含多个事务产生的Undo Record，也就是每个Undo Record中有自己的trx_id。

InnoDB为了实现 MVCC机制，会在事务开启时创建一个 ReadView 视图，正是利用这个trx_id 来判断这些Record是否对当前事务可见。

ReadView 创建

列出几个关键字段：

• m_ids

  表示当前事务创建时，InnoDB中所有尚处在活跃中的 trx_id列表

• m_low_limit_id

  活跃事务列表中最大的 trx_id + 1

• m_up_limit_id

  活跃事务列表中最小的 trx_id

• m_low_limit_no

  即ReadView里的trx_no。正在 commit 的活跃事务中，选择最小的 trx->no （默认等于m_low_limit_id，活跃事务列表中最大的 trx_id + 1） 赋值给m_low_limit_no。

ReadView 结构

class ReadView {
  /* ... */
private:
  trx_id_t m_low_limit_id;      /* 大于等于这个 ID 的事务均不可见 */
  trx_id_t m_up_limit_id;       /* 小于这个 ID 的事务均可见 */
  trx_id_t m_creator_trx_id;    /* 创建该 Read View 的事务ID */
  trx_id_t m_low_limit_no;      /* 事务 Number, 小于该 Number 的 Undo Logs 均可以被 Purge */
  ids_t m_ids;                  /* 创建 Read View 时的活跃事务列表 */
}

ReadView 创建

void ReadView::prepare(trx_id_t id) {
  ut_ad(mutex_own(&trx_sys->mutex));

  /* id 即为创建该 Read View 的事务ID. */
  m_creator_trx_id = id;

  /* 将 m_low_limit_no, m_low_limit_id 和 m_up_limit_id 初始化为当前 trx_sys 最大的事务ID. */
  m_low_limit_no = m_low_limit_id = m_up_limit_id = trx_sys->max_trx_id;

  if (!trx_sys->rw_trx_ids.empty()) {
    /* 假如当前 trx_sys 的活跃事务列表不为空，则将其拷贝至 m_ids.
     * 并在这个过程中更新 m_up_limit_id = m_ids.front(),
     * 即将 m_up_limit_id 更新为当前活跃事务列表中 trx_id 最小的一个. */

    copy_trx_ids(trx_sys->rw_trx_ids);
  } else {
    /* 否则清空 Read View 的活跃事务列表. */
    m_ids.clear();
  }

  ut_ad(m_up_limit_id <= m_low_limit_id);

  if (UT_LIST_GET_LEN(trx_sys->serialisation_list) > 0) {
    const trx_t *trx;

    trx = UT_LIST_GET_FIRST(trx_sys->serialisation_list);

    /* serialisation_list 为当前 trx_sys 正在 commit 的活跃事务, 选择最小的 trx->no 赋值于 m_low_limit_no. */
    if (trx->no < m_low_limit_no) {
      m_low_limit_no = trx->no;
    }
  }

  ut_d(m_view_low_limit_no = m_low_limit_no);

  /* m_closed 设为 false. */
  m_closed = false;
}

可见性规则

所谓可见性判断，就是判断某一行数据的历史链路中，每个Undo Record的变更是否被当前事务可见。依赖的就是 Undo Record中的trx_id 和 ReadView。

代码逻辑如下：

bool changes_visible(trx_id_t id, const table_name_t &name) const
      MY_ATTRIBUTE((warn_unused_result)) {
    ut_ad(id > 0);

    /* 假如 trx_id 小于 Read View 限制的最小活跃事务ID m_up_limit_id 或者等于正在创建的事务ID
     * m_creator_trx_id 即满足事务的可见性. */
    if (id < m_up_limit_id || id == m_creator_trx_id) {
      /* 可见. */
      return (true);
    }

    /* 检查 trx_id 是否有效. */
    check_trx_id_sanity(id, name);

    if (id >= m_low_limit_id) {
      /* 假如 trx_id 大于等于最大活跃的事务ID m_low_limit_id, 即不可见. */
      return (false);
    } else if (m_ids.empty()) {
      /* 假如目前不存在活跃的事务，即可见. */
      return (true);
    }

    const ids_t::value_type *p = m_ids.data();

    /* 利用二分查找搜索活跃事务列表，找到就返回fasle，没找到就是true可见。
     * trx_id 在 m_up_limit_id 和 m_low_limit_id 之间
     * 如果 id 在 m_ids 数组中, 表明 ReadView 创建时候，事务处于活跃状态，因此记录不可见.
     * 如果该trx_id不在数组，它既大于最小的活跃事务id 又不在活跃事务里，说明是已经提交了，可见。*/
    return (!std::binary_search(p, p + m_ids.size(), id));
  }

1. 如果这个Undo Record中的trx_id 小于了 ReadView中最小活跃事务ID，或者就是当前事务本身的trx_id，那么可见。

2. 如果trx_id 大于等于最大活跃的事务ID，那么是不可见的。

3. 剩下的情况就是 trx_id 处在最小活跃和最大活跃id之间，在活跃事务Ids中二分查找：

   3.1. 如果找到，说明启动时这个trx_id 还在活跃中，不可见。

   3.2. 如果没找到，说明启动时，这个trx_id 已经提交了，不在活跃事务里。可见。

对于 3.2 的场景值得说下，即：

为什么 trx_id 在 最小和最大活跃trx_id之间，但还没在活跃事务中找到？

其实不难理解，因为trx_id 的申请时机是在事务启动时，且trx_id 递增。那么就可能存在，某一个时刻，后申请的事务先提交了，先申请的还有没提交的。

这就是为什么这个trx_id 大于最小活跃id，但还不在活跃事务里，因为它先提交了。

可见性图示

可重复读和读提交的 ReadView

• 可重复读隔离级别下，事务启动时创建一次 ReadView，之后的查询都共用这个ReadView
• 读提交隔离级别下，每一次查询执行前都会重新生成一个 ReadView

总结

MVCC是利用了ReadView + Undo Log解决的多版本数据：

• ReadView 记录了事务开启时，所有活跃事务的Id，为了可见性。
• Undo Log 记录了各个 Undo Record，每行数据的多个版本即Undo Record记录了变更信息，版本数据可回溯。

参考

• 庖丁解InnoDB之Undo LOG
• InnoDB undo log基础知识
• InnoDB 事务分析-MVCC

• MySQL
• 数据库