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 ， 从而实现了可重复读。 |
可以这样理解，再RR隔离级别下，事务开始后只在第一次创建后才会生成每次进行，不管中间有多少的操作语句，之后就不会再生成新的的ReadView了；
再RC隔离级别下，事务开始后，创建ReadView，不仅如此，之后的查询语句都会产生新的ReadView，这样就会出现不能读取重复数据的问题。
6、总结
（1）、实现了非阻塞的读操作（OLTP应用）,写操作也只锁定必要的行，是个行级锁； select不会加锁，读和写操作性能好，提高了数据库的并发处理能力；缺点：需要额外的存储空间；
（2）、innodb的mvcc是每次事务都有递增的版本号,通过在每行记录的后面添加隐藏字段,存储操作它事务的版本号，实现MVCC；（在底层的是使用事务id、回滚指针、undo log和可见性算法实现的）
（3）、undo log将各个版本的数据形成一个版本链，通过可见性比较规则来查询相应版本的数据；
（4）、通过保存数据在某个时间点的快照实现的，也就是一致性视图（read view）；
（5）、mvcc只在RR和RC两个隔离级别下工作;用户可以查看当前数据的前一个或者前几个历史版本。保证了ACID中的I-隔离性。