MySQL InnoDB MVCC数据结构分析

1、概述

MVCC（Multiversion Concurrency Control）多版本并发控制，通过维护不同的版本号，提供一种很好的并发控制技术，这种技术能够使读写操作不冲突，提升并发性能。

MySQL InnoDB存储引擎，在更新某些数据时，并非使用新数据覆盖旧数据，而是标记旧数据是过时的，同时在其他地方新增一个数据版本。因此，同一份数据有多个版本存储，但只有一个是最新的。

根据事务的ACID特性：原子性，一致性，隔离性，持久性，MVCC主要解决的是隔离性问题。

特性	解释
Atomicity 原子性	事务的所有行为或者全部提交或者全部不做
Consistency 一致性	事务在完成时使得整个数据库仍保持一致性状态
Isolation 隔离性	并发的事务看不到彼此正在进行的更新操作
Durability 持久性	一个成功提交的事务对数据库的更新是永久的

并且InnoDB存储引擎采用Next-Key Loking的算法来避免幻读现象。在事务隔离界别Read Commited和Repeatable Read下，InnoDB存储引擎使用非锁定的一致性读。

2、隐藏列

在InnoDB表中会存有三个隐藏字段，这三个字段是mysql默认帮我们添加的。

在MySQL 5.7.29版本 dict文件夹下dict0dict.cc文件的实现源码中，从dict_table_add_system_columns()函数可以看到其内部实现：

分析：

从函数中可以看到当满足一定的条件时，若建表时没有指定主键，InnoDB会使用该ROW_ID创建一个聚簇索引，MySQL会自动生成一个隐藏的自增ID；事务的ID和回滚指针也被生成，用于记录修改（insert/update/delete）该记录的事务ID和指向这条记录的上一个版本。

当产生新的版本，旧的版本将被放到undo log中，并且当前记录的回滚指针指向上一个版本的地址。

当建表没有指定主键或新开一个事务对该行数据有修改操作时，会增加隐藏列，隐藏列的产生会调用一个函数，在dict文件夹下dict0dict.cc文件中的dict_table_add_system_columns()函数中，具体定义了这三个隐藏列：

隐藏字段名称	意义	大小
ROW_ID	隐藏的自增ID，当建表没有指定主键，InnoDB会使用该ROW_ID创建一个聚簇索引。	6 byte
DB_TRX_ID	最近修改（更新/删除/插入）该记录的事务ID。	7 byte
DB_ROLL_PTR	回滚指针，指向这条记录的上一个版本。	6 byte

MVCC 使用了三个字段来实现版本并发控制。分别为事务字段，回滚指针字段，是否删除字段。

对于删除标记位的解读：

字段名称	意义
DEL_BIT	判断该行记录是否已经被删除。

分析：

删除标记位是MVCC在进行删除操作时，对该条记录的删除位状态进行标记，当DEL_BIT为true时，表示已经删除，但未真删除，若需要回滚，可根据状态位进行逆向操作，insert回去，这样保证了在勿删等操作下对于数据的找回。

3、undo log &版本链

undo log被称为回滚日志，它是用于记录数据被修改前的信息。undo log主要记录的是数据的逻辑变化，为了在发生错误时回滚之前的操作，需要将之前的操作都记录下来，然后在发生错误时才可以回滚。

数据库事务未提交时，会将事务修改数据的镜像（即修改前的旧版本）存放到undo日志里，当事务回滚时，或者数据库奔溃时，可以利用undo日志，即旧版本数据，撤销未提交事务对数据库产生的影响。

每次写入数据或者修改数据之前都会把修改前的信息记录到undo log。

undo log 有什么作用？

　　undo log 记录事务修改之前版本的数据信息，因此假如由于系统错误或者rollback操作而回滚的话可以根据undo log的信息来进行回滚到没被修改前的状态。

　　undo log是用来回滚数据的，用于保障未提交事务不会对数据库的ACID特性产生影响。

undo log 工作步骤：

1).开始事务

2).记录数据行数据快照到undo log

3).更新数据（此时在缓存中操作）

4).将undo log写到磁盘

5).将数据写到磁盘

6).提交事务

结论：

(1)、每条数据变更(insert/update/delete)操作都伴随一条undo log的生成,并且回滚日志必须先于数据持久化到磁盘上

(2)、所谓的回滚就是根据回滚日志做逆向操作，比如delete的逆向操作为insert，insert的逆向操作为delete，update的逆向为update等。

在undo log中，当保存的版本多起来后，就会形成一条链表，这就是版本链，它表示当前最新记录数据与旧数据之间的关系。通过undo log与当前最新数据形成的版本链，可以找到任一版本的数据。如下图，模拟三个不同id的事务先后执行一些操作后，select1时形成的版本链。

在undo log 回滚日志中，事务在insert新记录产生的insert undo log，当事务提交之后可以直接丢弃；事务在进行 update 或者 delete 的时候产生的update undo log，在快照读的时候还是需要的，所以不能直接删除，只有当系统没有比这个log更早的read-view了的时候才能删除。

定期唤醒purge线程管理比现在最早的活动事务还早的undo log，遍历undo日志，构造索引记录，查找并删除。

功能：回收局促索引/二级索引上的删除项。不足：为了能够删除二级索引记录，undo中必须记录完整索引项

ps：所以长事务会产生很多老的视图导致undo log无法删除大量占用存储空间。

4、ReadView可见性

read view: 一致性视图，是MySQL秒级创建视图的必要条件，比如一个事务在进行简单的select 操作(快照读)的时候会创建一个 read view ，读取的只是当前事务的可见版本，不用加锁。

通过跟踪mysql源码，可以在判断该条记录可见性，总会涉及到一个非常重要的类ReadView，Read View是事务开启时当前所有事务的一个集合,这个类中存储了当前Read View中最大事务ID及最小事务ID。ReadView类保存在include文件夹下read0types.h头文件中，从源码中可以看到ReadView类中私有成员变量的定义信息：

…….

可以看到read0types.h头文件中ReadView类中定义的私有成员变量，下面对它各个字段进行解读：

ReadView类的成员变量	意义
trx_id_t m_low_limit_id	读取的内容应该看不到trx id> =此值的任何事务。相当于max_id。
trx_id_t m_up_limit_id	读取结果应查看所有严格 < 此值的trx id。相当于min_id。
trx_id_t m_creator_trx_id	创建当前视图的事务id。相当于alive_id。
ids_t m_ids	当前活跃事务(即未提交的事务)的数量。
node_t m_view_list	事务系统中的一致性视图链表
......	......

分析：

因为逆序排列，所以不要对于命名中的low和up字样有单纯字面上的理解！

m_low_limit_id意思，根据源码注释以及上下文的解读，此值的意义为能看到当前行版本的高水位标识,>= low_limit_id皆不能看见；

m_up_limit_id的意思为能看到当前行版本的低水位标识,< m_up_limit_id皆能看见；

在可见性的算法上，最核心的算法被封装成一个函数changesvisible()，它是判断可见性算法的核心，根据查询的ReadView即可判断可以看见哪个版本的数据。changesvisible()函数作为成员函数被封装在include文件夹下read0types.h头文件的ReadView类中，可见其重要性，它能够对不同隔离界别下的ReadView的判断。

分析：

从第一个if分支可以看到，如果ID小于Read View中最小的, 则这条记录是可以看到，即id<= m_up_limit_id。说明这条记录是在select这个事务开始之前就结束的；

从第二个if分支可以看到，如果比Read View中最大的还要大，则说明这条记录是在事务开始之后进行修改的，所以此条记录不应查看到；

从ifelse if分支中，判断是否在Read View中，如果在说明在创建Read View时此条记录还处于活跃状态则不应该查询到，否则说明创建Read View是此条记录已经是不活跃状态则可以查询到。

画出该程序的流程图，对于该函数对于可见性的算法一目了然。

对于不可见的记录都是通过row_vers_build_for_consistent_read()函数查询undo构建的老版本记录，直到记录可见。这个函数在row文件夹下row0sel.cc文件中可以看到，省略不重要的代码，可以看到这个循环只有在符合可见性的条件才会break，如果不符合就会回溯到上一个版本：

在MVCC类中，其实也会有一个链表，这个链表将每次生成的ReadView对象建立联系，形成一个ReadView链。

在include文件夹下read0read.h头文件中，对MVCC类进行了定义，并且在最后定义了一个ReadView链的成员变量，将生成的ReadView链接起来。

……

进一步查看链表的结构，可以看到链表中只有三个变量，分别链表中节点的个数、头指针和尾指针。

5、隔离性与可见性

不同的事务隔离级别，可见性的实现也不一样。但是在InnoDB存储引擎中，MVCC只能在RC或者RR隔离级别下使用。通过对不同隔离级别下的产生的ReadView研究，可以发现两种隔离级别下ReadView的产生是不同的。

隔离级别	可见性比较规则
Read Commited	事务内的每个查询语句都会重新创建Read View，这样就会产生不可重复读现象发生。
Repeatable Read	事务内开始时创建Read View ，在事务结束这段时间内每一次查询都不会重新重建Read View ，从而实现了可重复读。