MVCC

核心思想

多版本并发控制（Multi version concurrency control MVCC）技术的核心思想是：

（1）当事务Ti执行一个读操作，并发控制器选择一个版本进行读取，这个版本的获取，依赖于事务Ti所能读取的数据的上下文，这个上下文（有个通常名称，叫做事务的快照，快照要和多版本相配合）是事务Ti在数据库系统里的当前并发执行的诸多事务的状态的一份拷贝，其中的信息能够帮助判断获取到的元祖是否对本事务是读取的。

（2）多版本并发控制不是一个可独立使用的事务并发控制技术，而是需要基于其他并发技术，如基于时间戳的称为“多版本时间戳排序机制”，基于两阶段封锁协议的称为“多版本两阶段封锁协议”。

多版本两阶段锁协议

innodb用的是多版本两阶段锁协议，所以我们就介绍一下这个。

首先，每个数据项X，其多版本体现在：X有一个版本序列<X1,X2,….,Xn>，其中，每个版本Xi包括一个时间戳，多数数据库中，这个时间戳对应的是唯一的一个事务标识，叫做事务号。事务号通常是一个递增的数字。

其次，事务分为两种类型，一种是只读事务，另外一种是更新事务。这意味着需要事先知道事务的读写请求，进而告知事务管理器，事务管理器才能区分事务的类型然后根据类型做出一定的优化（多数多版本两阶段封锁协议的事务管理器都采取了一定措施为只读事务做了优化）。

只读事务开始获得事务号，根据事务号读取事务号对应的数据项的版本，只读事务在整个生命周期内只使用这个版本的数据。

更新事务的操作可以细分为：

1：更新事务中的读操作：如果能获取该数据项的共享锁，读取该数据项的最新版本的值

2：更新事务中的写操作：

• 如果能获得该数据项的排它锁，则为该数据项创建一个版本。刚创建的时候新版本的时间戳为无穷大，致使其他并发事务不能读取到此尚未提交的数据项的版本。事务提交，此版本上的时间戳+1，表示此后其他事务可以读取此版本的数据。
• 不能获得排它锁时，表明有其他事务准备或已经写了数据但没有结束即锁没有被释放，本更新事务只能等待。

在上图中，我们提到的读操作，对应这SQL语句的SELECT操作，这样的操作在快照隔离技术中，可以做到读不加锁，但是，“读”操作的另外一层含义，是“获取”，即某SQL语句需要先获取到数据，然后才能操作数据。

在MVCC并发控制方法中，“读”操作可以细分为两种情况

• 快照读：读取的是元组的可见版本（可见的含义是获取在快照允许的事务范围内的版本，这样的版本可能是历史版本），不用加锁，如InnoDB使用UNDO日志帮助获取快照范围内的历史版本以支持简单的SELECT查询操作。
• 当前读：读取的是记录的最新版本，被当前读返回的元组会加上锁，保证其他事务不会再并发修改这条元组。如Innodb中把UPDATE，INSERT，DELETE操作视为特殊操作，这样的操作需要读取数据，属于当前读。

DML和DQL既然都要操作数据，所以都要“读取”数据，但是DQL（普通查询语句，不是指带有FOR UPDATE等显式加锁的语句）只是读取数据显示而已，但DML读出后却要进行写操作所以不只是读，目的不同，自然应该施加的锁是不同的。

所以从这个角度上看，快照读根本不用加锁，当前读一定要加锁，所以根本不必区分快照读和当前读这两种读，只要简单认为快照读基于多版本所以不用加锁，DML属于写操作，自然要加锁处理。

工作机制

每开启一个事务，我们都会从数据库中获得一个事务 ID（也就是事务版本号），这个事务 ID 是自增长的，通过 ID 大小，我们就可以判断事务的时间顺序。

InnoDB 的叶子段存储了数据页，数据页中保存了行记录，而在行记录中有一些重要的隐藏字段：

• DATA_TRX_ID：6字节长，表示上一个执行插入或更新操作的事务
• DATA_ROLL_PTR：7字节长，表示旧版本的数据位于回滚段中的位置，指向的是一个旧版本，只有元组被更新，才有会新版本产生，旧版本被置于回滚段，因此一致性无锁读操作按照“read view”快照需要读取旧版本时，只能根据事务ID回到回滚段中寻找旧版本
• DATA_ROW_ID：6字节长，表示执行插入操作后生成的单调自增长的行的ID标识，如果存在聚集索引，索引项则包括的是这个DB_ROW_ID值

InnoDB 将行记录快照保存在了 Undo Log 里，我们可以在回滚段中找到它们，如下图所示：

从图中能看到回滚指针将数据行的所有快照记录都通过链表的结构串联了起来，每个快照的记录都保存了当时的 db_trx_id，也是那个时间点操作这个数据的事务 ID。这样如果我们想要找历史快照，就可以通过遍历回滚指针的方式进行查找。

事务隔离级别与快照的关系

• 隔离级别大于等于可重复读：事务块的所有的SELECT操作都要使用同一个快照，此快照是在第一个SELECT操作时建立的
• 隔离级别小于等于已提交读：事务块内的所有的SELECT操作分别创建属于自己的快照，因此每次读都不同，后面的SELECT操作的读就可以读到本次读之前已经提交的数据

快照的基本数据结构

• m_up_limit_id ：左边界
• m_low_limit_id   右边界
• m_createor_trx_id：正在创建事务的事务id
• m_ids：快照创建时，处于活动即尚未完成的读写事务的集合

一个快照，有左右边界，左边界是最小值，右边界是最大值。

举一个例子：新建一个快照，假设当前事务的事务ID为6，这时候读写事务链上活动的事务有{3,5,6,10},不包括只读事务，那么调用方法创建快照成功后，上面四个属性的值分别是：

• m_ids的值是{3,5,10}（6因为是当前事务的ID，不记录进去）
• m_up_limit_id的值是3，
• m_low_limit__id是10，
• m_createor_trx_id是6

可见性判断

当一个记录被读取，需要通过可见性原则进行判断，以确认记录是否可以被上层的操作看到，如果不应该被看到，则不可见。

• 如果记录trx_id小于m_up_limit_id或者等于m_creator_trx_id，表明快照创建的时候该事务已经提交，记录可见。
• 如果记录的trx_id大于等于m_low_limit_id，表明事务是在快照创建后开启的，其修改，插入的记录不可见。
• 当trx_id在m_up_limit_id和m_low_limit_id之间的时候，如果trx_id在m_ids数组中，表明快照创建时候，事务处于活跃状态，因此记录不可见。

多版本生成

对于一个逻辑上的多版本生成过程，其方式如下：

• 最老的版本，一定是插入操作暂存到UNDO日志的版本(对于聚集索引，不是记录的所有字段读暂存到回滚段，而是主键信息被暂存)
• 更新操作，把旧值存入UNDO日志。同一个日志反复被更新，则每次读存入一个旧值(前像)到UNDO日志内，如此就会有多个版本，版本之间使用DATA_POLL_PTR来进行关联，由此所有版本构成一个链表，链头是索引上的记录，链尾是首次插入时生成的UNDO信息。
• 删除操作，在UNDO日志中保存删除标志

多版本查找

对于聚集索引，可以根据DATA_ROLL_PTR就可以从回滚段中找出前一个版本的记录，并知道此记录是更新操作还是插入操作生成的，如果是插入操作生成的，则意味着此版本是最原始的版本，即使不可见也没有必要在继续回溯查找旧版本了。

但是查找的过程与隔离级别紧密相关：

• 如果是未提交读隔离级别，根本不去找旧版本，在索引上读到的记录就被直接使用
• 如果不是未提交隔离级别，则需要进入UNDO回滚段中根据DATA_POLL_PTR进行查找，还要判断是否可见，如果可见，则返回，如果不可见，则一直根据DATA_POLL_PTR进行查找

参考资料：

《数据库处理的艺术 事务管理与并发控制》

 《高性能MySQL》

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

https://cloud.tencent.com/developer/article/1744079

https://dev.mysql.com/doc/refman/8.0/en/set-transaction.html#set-transaction-isolation-level