MySQL的MVCC实现原理

背景

当数据库的读和写同时访问一行数据时，此时应该怎么返回？MySQL为了解决这一问题，同时也为了提高数据库并发能力，采用了MVCC(Mutil-Version Concurrency Control)多版本并发控制技术。数据库通过锁来实现隔离性，锁住一个资源后禁止其他所有的访问请求是最可靠的隔离性。但是我们知道，主流关系型数据库读写操作是可以同时进行(写写操作不能同时发生)。Mysql InnoDB引擎解决读写同时操作依赖于MVCC，那么它到底时如何实现呢？在了解MVCC之前，我们要先了解概念。

几个重要概念介绍

• 当前读&快照读

所谓当前读，即读取的记录是当前最新的记录，会对当前读取的数据进行加锁，防止其他事务修改数据，比如select for update
、select lock in share mode
，以及DML操作都是当前读。换言之当前读是一种悲观锁。而快照读，则是读取的数据有可能不是最新的数据，当前数据是可以被修改，比如不加锁(包括不加共享读锁)查询语句，所以是一种乐观锁。Mysql的快照读的前提是隔离级别不能是串行和读未提交，因为串行和读未提交下只有当前读。快照读的作用是为了解决读写冲突，提高数据库并发性能。

• 事务的ACID

数据库最重要的特性即为数据一致性(Consistency)，MySQL数据一致性是通过原子性(Atomicity)、持久性(Durability)、隔离性(Isolation)实现的，这四个特性合称为：ACID。

• 一致性

所谓的数据一致性是数据状态的一致。最经典的例子是银行转账，A用户转账给B用户100元，这件事情作为一个事务，要么都成功要么都失败，这样才能保障AB用户的金额是一致的。实现这一目标，MySQL是通过原子性、持久性和隔离性实现。

• 原子性

原子性是指所有操作要么都成功要么都失败，实现依赖组件是undo log。当事务对数据库进行修改时，InnoDB会生成对应的undo log。如果事务执行过程中失败或调用了rollback，导致事务需要回滚，便可以利用undo log中的信息将数据回滚到修改之前的样子。

undo log属于逻辑日志，记录的是sql执行相关的信息。当发生回滚时，InnoDB会根据undo log的内容做与之前相反的工作。对于每个insert，回滚时会执行delete；对于每个delete，回滚时会执行insert；对于每个update，回滚时会执行一个相反的update，把数据改回去。

注意：
看完原子性和一致性的介绍，或许有同学会懵逼，这tm不是一回事情吗？我再补充2点个人理解。
1、原子性是相对最小粒度操作而言的。比如一个DML语句，这个语句是不可分割且，就像原子是不可分割一样。(别说原子是可分割，里面还有原子核和电子。。。)
2、一致性是针对一个事务而言，比如前面说的转账就是一个事务(当然一个事务也可以只是一个DML语句，此时原子性和一致性，恰巧一致)，而这个事务涉及多个DML语句，要保证这多个语句都成功或者都失败，称为一致性。

• 持久性

持久性是指事务一旦被提交，数据库的改动是永久的，实现依赖组件是redo log。数据库读写瓶颈主要是磁盘IO，缓存技术是有效解决IO问题的方法，但是由于缓存则会有异常情况丢失数据的危险。所以在解决IO瓶颈和数据丢失的要求下，mysql引进了redo log。

当数据修改时，除了修改Buffer Pool中的数据，还会在redo log记录这次操作；当事务提交时，会调用fsync接口对redo log进行刷盘。如果MySQL宕机，重启时可以读取redo log中的数据，对数据库进行恢复。redo log采用的是WAL（Write-ahead logging，预写式日志），所有修改先写入日志，再更新到Buffer Pool，保证了数据不会因MySQL宕机而丢失，从而满足了持久性要求。

另外，查询场景的缓存技术，目前一般不建议使用，8.0版本官方默认已经关闭该功能。

• 隔离性

隔离性是指事务内部的操作与其他事务是隔离的，并发执行的各个事务之间不能互相干扰。写和写之间的隔离性的实现方式锁，写和读的隔离性是通过快照读实现的。

• 隔离级别

MySQL有4种隔离级别，分别是：
读未提交(RU)：别人改数据的事务尚未提交，我在我的事务中也能读到。
读已提交（RC）：别人改数据的事务已经提交，我在我的事务中才能读到。解决脏读。
可重复读（RR）：别人改数据的事务已经提交，我在我的事务中也不一定能看到(也就是同一个事务中，不管其他事务如何修改数据，在该事务种多次查询读取到的数据是一致)。解决不可重复读。
串行化（S）：我的事务尚未提交，别人就别想改数据。

四种隔离是为了解决脏读、不可重复和幻读的问题，脏读和不可重复读相对简单，这里只介绍幻读。

网上对幻读有很多错误的定义，比如：事务A 执行两次查询操作得到不同的数据集，即查询1 得到 10 条记录，查询2得到 11 条记录。这其实并不是幻读，这是不可重复读的一种。
其实这并不幻读，幻读是指某一次的查询操作得到的结果所表征的数据状态无法支撑后续的业务操作。更为具体一些：查询某记录是否存在，不存在，准备插入此记录，但执行insert
时发现此记录已存在，无法插入，此时就发生了幻读。

RR虽然没有解决幻读，那是因为RR情况下的，普通查询语句都是快照读，如果加上当前读(即加上X锁)则可以在RR模式下解决幻读。串行化即是在所有的语句都上X锁，解决了幻读问题。

• 锁

所谓锁，是操作数据库数据时，对在涉及到的数据行上加上标记，这些标记用于表示这部分数据当前是否允许其他事务去查询或者修改。

特性：
1、普通的查询语句不会产生锁，但是select for update
是X锁(排他锁)，select lock in share mode
是S锁(共享锁))
2、所有的DML都会产生X锁。
3、X锁不和其他所有锁相兼容，也就是某一行数据当前为X锁，则其他所有锁都只能等待其释放。
4、S锁和S锁互相兼容
5、InnoDB引擎的行级锁是通过index实现的，否则都是表级锁。
6、死锁必须是2个及以上事务的情况下才会发生。

MVCC实现原理

MVCC的是通过行记录的三个隐藏列、undo log和read view实现的，首先介绍inndod引擎的行数据存储的三个隐藏列。

三个隐藏列

inndodb的每一行记录除了用户创建的列外，会有三个隐藏列：DATA_TRX_ID
、DATA_ROLL_PTR
和DB_ROW_ID
。

• DATA_TRX_ID：记录最近更新这条记录的事务ID(6字节)，如果这行数据第一次事务操作，则该列为空（比如这行数据首次insert）。

• DATA_ROLL_PTR：指向该行undo log的指针，通过指针找到之前版本，通过链表形式组织(7字节)

• DB_ROW_ID：行标识，没有主键时主动生成(6字节)。如果有主键，则不会有该隐藏列。

如user表：

如上图，该表有主键MySQL不会增加一个DB_ROW_ID隐式主键。DB_TRX_ID是最后一次操作该记录的事务ID，而DB_ROLL_PTR是指向这行记录上一个版本的指针值，由于改记录上一个版本的数据存储在undo log中，故该值是指向undo log一个指针值。
注意：
如果这行数据是第一次被写入，不存在上一个事务的操作，所以DATA_TRX_ID和DATA_ROLL_PTR两列为空。

Undo log链路

undo log主要分为两种：

• insert undo log

代表事务在insert新记录时产生的undo log, 只在事务回滚时需要，并且在事务提交后可以被立即丢弃

• update undo log

事务在进行update或delete时产生的undo log， 不仅在事务回滚时需要，在快照读时也需要。所以不能随便删除，只有在快速读或事务回滚不涉及该日志时，对应的日志才会被purge线程统一清除

对MVCC有帮助的其实是update undo log
，一个update语句undo的链路指向过程如下。

第一步：先insert数据
插入user_id、name、主键ID三列数据。由于已经有了主键，此时引擎只会再对这一行记录增加两列，分别是最近更新这条记录的事务ID，即DATA_TRX_ID
。和该行上一个事务状态下数据的undo指针值，即DATA_ROLL_PTR
。由于这行数据是第一次被写入，不存在上一个事务的操作，所以DATA_TRX_ID和DATA_ROLL_PTR两列为空。

第二步：A事务更新name，将张三改为李四

链路如下：

第三步：B事务再更新name，将李四改为王五
a、事务B在改行数据上，加排他锁，其他事务等待。
b、再将目前数据拷贝到undo log，作为旧的记录保存下来。
c、在将【李四】改为【改为】，同时在DATA_TRX_ID列记录当前B事务的ID，并且DATA_ROLL_PTR列则指向上一步的undo log地址。
d、事务提交，释放锁。

这三步的链路如下：

到此我们可以看出，不同事务或者相同事务的对同一记录的修改，会导致该记录的undo log成为一条记录版本线性表，既链表，undo log的链首就是最新的旧记录，链尾就是最早的旧记录。

说明：
实际上undo log的信息，在事务进行提交或者回归后，事务对应数据的undo log是会purge线程清除掉，向图中的第一条insert undo log，其实在insert事务提交之后可能就被删除丢失了，不过这里为了演示，所以还放在这里。

Read view

当一个快照读语句发生时，数据库会产生一个Read View
，该视图是保存事务ID的list列表，记录的是本事务执行时，MySQL还有哪些进行中且未提交的事务，即当前系统中还有哪些活跃的读写事务ID列表
。每个事务开启时，都会被分配一个ID, 这个ID是递增的，所以最新的事务ID值越大。

Read View主要是用来做判断的, 即当我们某个事务执行快照读的时候，对该记录创建一个Read View读视图，把它比作条件用来判断当前事务能够看到哪个版本的数据，可能是当前最新的数据
，也有可能是该行记录的undo log里面的某个版本的数据
。

Read View几个属性

trx_id_list: 当前系统活跃(未提交)事务版本号集合。
low_limit_id: 创建当前read view 时“当前系统最大事务版本号+1”。
up_limit_id: 创建当前read view 时“系统正处于活跃事务最小版本号”
creator_trx_id: 创建当前read view的事务版本号；

注意，网上有很多文章说low_limit_id是最小版本号，up_limit_id是最大版本号，但是根据 源码的注释来看意思恰好是相反，节选源码如下：

struct read_view_struct{
  ulint    type;  /*!< VIEW_NORMAL, VIEW_HIGH_GRANULARITY */
  undo_no_t  undo_no;/*!< 0 or if type is
        VIEW_HIGH_GRANULARITY
        transaction undo_no when this high-granularity
        consistent read view was created */
  trx_id_t  low_limit_no;
        /*!< The view does not need to see the undo
        logs for transactions whose transaction number
        is strictly smaller (<) than this value: they
        can be removed in purge if not needed by other
        views */
  trx_id_t  low_limit_id;
        /*!< The read should not see any transaction
        with trx id >= this value. In other words,
        this is the "high water mark". */
  trx_id_t  up_limit_id;
        /*!< The read should see all trx ids which
        are strictly smaller (<) than this value.
        In other words,
        this is the "low water mark". */
  ulint    n_trx_ids;
        /*!< Number of cells in the trx_ids array */
  trx_id_t*  trx_ids;/*!< Additional trx ids which the read should
        not see: typically, these are the active
        transactions at the time when the read is
        serialized, except the reading transaction
        itself; the trx ids in this array are in a
        descending order. These trx_ids should be
        between the "low" and "high" water marks,
        that is, up_limit_id and low_limit_id. */
  trx_id_t  creator_trx_id;
        /*!< trx id of creating transaction, or
        0 used in purge */
  UT_LIST_NODE_T(read_view_t) view_list;
        /*!< List of read views in trx_sys */
};

快照读操作返回结果的判断是由以下规则决定的：

• DB_TRX_ID < up_limit_id
  此记录的最后一次修改在read_view创建之前，可见
   

• DB_TRX_ID > low_limit_id
  此记录的最后一次修改在read_view创建之后，不可见。需要用DB_ROLL_PTR查找undo log(此记录的上一次修改)，然后根据undo log的DB_TRX_ID再计算一次可见性。
   

• up_limit_id <= DB_TRX_ID <= low_limit_id
  需要进一步检查read_view中是否含有DB_TRX_ID
   

• DB_TRX_ID ∉ trx_id_list
  此记录的最后一次修改在read_view创建之前，可见。
   

• DB_TRX_ID ∈ trx_id_list
  此记录的最后一次修改在read_view创建时尚未保存，不可见。需要用DB_ROLL_PTR查找undo log(此记录的上一次修改)，然后根据undo log的DB_TRX_ID再从头计算一次可见性。

根据上面描述一句话总结，当这个事务的ID小于read view中最小的事务ID，或者这个事务的ID值在read view范围内又不在这个列表中，则可以读取最新数据，其他情况读取的都是历史版本数据
。
根据上述总结，可以画出以下流程途：

经过上述规则的判断，我们得到了这条记录相对read_view来说，可见的结果。此时，如果这条记录的delete_flag为true，说明这条记录已被删除，不返回。如果delete_flag为false，说明此记录可以安全返回给客户端

另外，对于Read view的生成时间不同，确定了事务是属于RR还是RC隔离级别。
RR是执行事务中的第一条查询语句的瞬间产生一个read view，后续所有的查询语句都是复用这个read view，所以能保证每次读取的一致性（可重复读的语义。而RC则每次读取，都会创建一个新的read view。这样就能读取到其他事务已经COMMIT的内容。所以对于InnoDB来说，RR虽然比RC隔离级别高，但是开销反而相对少。

总结

MVCC主要解决了读写(写读)冲突，提高了并发能力。实现方式是通过三个隐藏列、undo log链路和read view。同时Read view生成时间不同，决定了隔离级别是RR还是RC。

参考

《高性能MySQL》 第三版 电子工业出版社
《MySQL技术内幕 InnoDB存储引起》 第二版 机械工业出版社
http://mysql.taobao.org/monthly/2017/12/01/
https://github.com/twitter-forks/mysql/blob/master/storage/innobase/include/read0read.h#L124
https://dev.mysql.com/doc/refman/5.7/en/innodb-storage-engine.html