从源码分析 MySQL的多版本控制(MVCC)

什么是MVCC

MVCC，Multi-Version Concurrency Control，多版本并发控制。MVCC 是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问；在编程语言中实现事务内存。

MVCC怎么实现的

InnoDB中MVCC的实现依赖四个条件: 隐藏字段, 事务链表，read view, undo log.下面我们就这四个条件分析一下.

隐藏字段

根据MySQL官网关于InnoDB中包含的三个隐藏字段分别是DB_TRX_ID,DB_ROLL_PTR,DB_ROW_ID.

InnoDB是一个 多版本的存储引擎：它保存关于已更改行的旧版本的信息，以支持事务功能，如并发和 回滚。这些信息存储在一个称为回滚段的数据结构的表空间中 （在Oracle中的类似数据结构之后）。InnoDB 使用回滚段中的信息执行事务回滚所需的撤消操作。它还使用这些信息来构建一个行的早期版本以进行 一致的读取。

在内部，InnoDB将三个字段添加到数据库中存储的每一行。一个6字节的DB_TRX_ID字段表示插入或更新行的最后一个事务的事务标识符。另外，删除在内部被视为一个更新，其中行中的特殊位被设置为将其标记为已删除。每行还包含一个DB_ROLL_PTR称为滚动指针的7字节 字段。滚动指针指向写入回滚段的撤消日志记录。如果行已更新，则撤消日志记录包含在更新行之前重建行内容所需的信息。一个6字节的DB_ROW_ID字段包含一个行标识，随着新行的插入而单调递增。如果 InnoDB自动生成聚集索引，索引包含行ID值。否则，该 DB_ROW_ID列不会出现在任何索引中。

聚簇索引行结构

DB_TRX_ID(6字节): 在innoDB中, 会为每个事物分配一个事务ID. 而该字段表示的就是插入或更新该行的最后一个事务的事务标识符.

DB_ROLL_PTR(7字节): 这个字段称为回滚指针, 指向了回滚段的撤销日志. (undo log)

DB_ROW_ID(6字节):  这个字段包含了一个行ID. 该ID在插入新行时会单调增加. 这个字段是为了在表里没有主键ID的时候, 生成聚簇索引使用的.

事务链表

MySQL中的事务在开始到提交这段过程中，都会被保存到一个叫trx_sys的事务链表中，基本的链表结构如下：

trx_sys

事务链表中保存的都是还未提交的事务，事务一旦被提交，则会被从事务链表中摘除。

Read View

有了前面隐藏列和事务链表的基础，接下去就可以构造MySQL实现MVCC的关键——ReadView。

ReadView可以理解为一个数据结构，在事务开始的时候会根据上面的事务链表构造一个ReadView,初始化方法如下：

// readview 初始化
// m_low_limit_id = trx_sys->max_trx_id; 
// m_up_limit_id = !m_ids.empty() ? m_ids.front() : m_low_limit_id;
ReadView::ReadView()
    :
    m_low_limit_id(),
    m_up_limit_id(),
    m_creator_trx_id(),
    m_ids(),
    m_low_limit_no()
{
    ut_d(::memset(&m_view_list, 0x0, sizeof(m_view_list)));
}

​​trx_ids​​: 表示事务开启的时候, 其它未提交的活跃的事务ID. 这个集合中的事务对于当前事务来说, 一直都是不可见的.

​​low_limit_id​​: 表示在生成ReadView时当前系统中最大事务id.

​​up_limit_id​​: 表示未提交活跃事务Id(trx_ids)的最大值. 如果trx_ids为空, 则up_limit_id=low_limit_id.

readview

通过该ReadView，新的事务可以根据查询到的所有活跃事务记录的事务ID来匹配能够看见该记录，从而实现数据库的事务隔离，主要逻辑如下：

通过聚簇索引的行结构中DB_TRX_ID隐藏字段可以知道最近被哪个事务ID修改过。一个新的事务开始时会根据事务链表构造一个ReadView。当前事务根据ReadView中的数据去跟检索到的每一条数据去校验,看看当前事务是不是能看到这条数据

怎么来判断可见性呢？ 我们来通过源码一探究竟：

// 判断数据对应的聚簇索引中的事务id在这个readview中是否可见
bool changes_visible(
        trx_id_t        id, // 记录的id
    const table_name_t& name) const
MY_ATTRIBUTE((warn_unused_result))
{
    ut_ad(id > 0);
    // 如果当前记录id < 事务链表的最小值或者等于创建该readview的id就是它自己,那么是可见的
    if (id < m_up_limit_id || id == m_creator_trx_id) {
        return(true);
    }

    check_trx_id_sanity(id, name);
    // 如果该记录的事务id大于事务链表中的最大值,那么不可见
    if (id >= m_low_limit_id) {
        return(false);
        // 如果事务链表是空的,那也是可见的
    } else if (m_ids.empty()) {
        return(true);
    }

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

    //判断是否在ReadView中，如果在说明在创建ReadView时 此条记录还处于活跃状态则不应该查询到，否则说明创建ReadView是此条记录已经是不活跃状态则可以查询到
    return(!std::binary_search(p, p + m_ids.size(), id));
}

可见性判断逻辑总结：

1. 当检索到的数据的事务ID小于事务链表中的最小值(数据行的DB_TRX_ID < m_up_limit_id)表示这个数据在当前事务开启前就已经被其他事务修改过了,所以是可见的。
2. 当检索到的数据的事务ID表示的是当前事务自己修改的数据(数据行的DB_TRX_ID = m_creator_trx_id) 时，数据可见。
3. 当检索到的数据的事务ID大于事务链表中的最大值(数据行的DB_TRX_ID >= m_low_limit_id) 表示这个数据在当前事务开启后到下一次查询之间又被其他的事务修改过,那么就是不可见的。
4. 如果事务链表为空,那么也是可见的,也就是当前事务开始的时候,没有其他任意一个事务在执行。
5. 当检索到的数据的事务ID在事务链表中的最小值和最大值之间，从m_low_limit_id到m_up_limit_id进行遍历，取出DB_ROLL_PTR指针所指向的回滚段的事务ID，把它赋值给 trx_id_current ，然后从步骤1重新开始判断，这样总能最后找到一个可用的记录。

RC和RR隔离级别ReadView的实现方式

我们知道，RC隔离级别是能看到其他事务提交后的修改记录的，也就是不可重复读，但是RR隔离级别完美的避免了，但是它们都是使用的MVCC机制，那又为何有两种截然不同的结果呢？其实我们看一下他们创建ReadView的区别就知道了。

在RC事务隔离级别下,每次语句执行都关闭ReadView,然后重新创建一份ReadView。在RR下,事务开始后第一个读操作创建ReadView,一直到事务结束关闭。

上面的总结英文版为：With REPEATABLE READ isolation level, the snapshot is based on the time when the first read operation is performed. With READ COMMITTEDisolation level, the snapshot is reset to the time of each consistent read operation.

因为RC每次查询语句都创建一个新的ReadView，所以活跃的事务列表一直在变，也就导致如果事务B update提交了后事务A才进行查询，查询的结果就是最新的行，也就是不可重复读咯。而RR则一直用的事务开始时创建的ReadView。

Undo Log

Undo log是InnoDB MVCC事务特性的重要组成部分。当我们对记录做了变更操作时就会产生Undo记录，Undo记录默认被记录到系统表空间(ibdata)中，但从5.6开始，也可以使用独立的Undo 表空间。

Undo记录中存储的是老版本数据，当一个旧的事务需要读取数据时，为了能读取到老版本的数据，需要顺着undo链找到满足其可见性的记录。当版本链很长时，通常可以认为这是个比较耗时的操作。

Undo Log 格式

在InnoDB引擎中，undo log分为：

insert undo log：

insert undo log是指在insert操作中产生的undo log，因为insert操作的记录，只对事务本身可见，对其他事务不可见（这是事务隔离性的要求），故该undo log可以在事务提交后直接删除，不需要进行purge操作。

update undo log：

update undo log记录的是delete和update操作产生的undo log。该undo log可能需要提供MVCC机制，因此不能在事务提交时就进行删除，提交时放入undo log链表，等待purge线程进行最后的删除。下面是两种undo log的结构图。

undo_log

purge

对于一条delete语句 delete from t where a = 1，如果列a有聚集索引，则不会进行真正的删除，而只是在主键列等于1的记录delete flag设置为1，即记录还是存在在B+树中。而对于update操作，不是直接对记录进行更新，而是标识旧记录为删除状态，然后新产生一条记录。那这些旧版本标识位删除的记录何时真正的删除？怎么删除？

其实InnoDB是通过undo日志来进行旧版本的删除操作的，在InnoDB内部，这个操作被称之为purge操作，原来在srv_master_thread主线程中完成，后来进行优化，开辟了purge线程进行purge操作，并且可以设置purge线程的数量。purge操作每10s进行一次。

为了节省存储空间，InnoDB存储引擎的undo log设计是这样的：一个页上允许多个事务的undo log存在。虽然这不代表事务在全局过程中提交的顺序，但是后面的事务产生的undo log总在最后。此外，InnoDB存储引擎还有一个history列表，它根据事务提交的顺序，将undo log进行连接，如下面的一种情况：

purge

在执行purge过程中，InnoDB存储引擎首先从history list中找到第一个需要被清理的记录，这里为trx1，清理之后InnoDB存储引擎会在trx1所在的Undo page中继续寻找是否存在可以被清理的记录，这里会找到事务trx3，接着找到trx5，但是发现trx5被其他事务所引用而不能清理，故再去history list中取查找，发现最尾端的记录时trx2，接着找到trx2所在的Undo page，依次把trx6、trx4清理，由于Undo page2中所有的记录都被清理了，因此该Undo page可以进行重用。

InnoDB存储引擎这种先从history list中找undo log，然后再从Undo page中找undo log的设计模式是为了避免大量随机读操作，从而提高purge的效率。

总结

最早的数据库, 除了读读之间可以并发. 读写, 写读, 写写之间都要阻塞. InnoDB有了多版本控制, 除了写写之外, 其它三种操作都可以并发进行. 这样大幅度提高了InnoDB的并发度.

MVCC在Read Committed以及Repeatable Read两个隔离级别下工作,而InnoDB通过在undo log保存每条数据的多个版本, 这样就能够找回历史版本的数据. 并且每个事务读到的数据版本都是不一样的.

参考文档

​​https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_consistent_read​​

​​http://www.searchdoc.cn/rdbms/mysql/dev.mysql.com/doc/refman/5.7/en/innodb-multi-versioning.com.coder114.cn.html​​

​​https://zhuanlan.zhihu.com/p/40208895​​

​​http://mysql.taobao.org/monthly/2018/11/04/​​ ​

https://zhuanlan.zhihu.com/p/64576887