InnoDB的MVCC实现
# MVCC
LBCC是基于锁的并发控制，因为锁的粒度过大，会导致性能的下降，因此提出了比LBCC性能更优越的方法MVCC。MVCC是Multi-Version Concurremt Control的简称，意思是基于多版本的并发控制协议，通过版本号，避免同一数据在不同事务间的竞争，只存在于InnoDB引擎下。它主要是为了提高数据库的并发读写性能，不用加锁就能让多个事务并发读写。MVCC的实现依赖于：三个隐藏字段、Undo log和Read View，其核心思想就是：只能查找事务id小于等于当前事务ID的行；只能查找删除时间大于等于当前事务ID的行，或未删除的行。接下来让我们从源码级别来分析下MVCC。
# 隐藏列
MySQL中会为每一行记录生成隐藏列，接下来就让我们了解一下这几个隐藏列吧。
（1）DB_TRX_ID：事务ID，是根据事务产生时间顺序自动递增的，是独一无二的。如果某个事务执行过程中对该记录执行了增、删、改操作，那么InnoDB存储引擎就会记录下该条事务的id。（换句话说。如果一个事务在某个时刻执行了快照读，那这时候记录下的事务ID还是上一次执行了增删改操作的事务ID，而不是当前执行快照读的事务ID）。
（2）DB_ROLL_PTR：回滚指针，本质上就是一个指向记录对应的undo log的一个指针，大小为 7 个字节，InnoDB 便是通过这个指针找到之前版本的数据。该行记录上所有旧版本，在undo log中都通过链表的形式组织。
（3）DB_ROW_ID：行标识（隐藏单调自增 ID），如果表没有主键，InnoDB 会自动生成一个隐藏主键，大小为 6 字节。如果数据表没有设置主键，会以它产生聚簇索引。
（4）实际还有一个删除flag隐藏字段，既记录被更新或删除并不代表真的删除，而是删除flag变了。
# undo log
每当我们要对一条记录做改动时（这里的改动可以指INSERT、DELETE、UPDATE），都需要把回滚时所需的东西记录下来, 比如:
- Insert undo log ：插入一条记录时，至少要把这条记录的主键值记下来，之后回滚的时候只需要把这个主键值对应的记录删掉就好了。
- Delete undo log：删除一条记录时，至少要把这条记录中的内容都记下来，这样之后回滚时再把由这些内容组成的记录插入到表中就好了。
- Update undo log：修改一条记录时，至少要把修改这条记录前的旧值都记录下来，这样之后回滚时再把这条记录更新为旧值就好了。InnoDB把这些为了回滚而记录的这些东西称之为undo log。这里需要注意的一点是，由于查询操作（SELECT）并不会修改任何用户记录，所以在查询操作执行时，并不需要记录相应的undo log。
每次对记录进行改动都会记录一条undo日志，每条undo日志也都有一个DB_ROLL_PTR属性，可以将这些undo日志都连起来，串成一个链表，形成版本链。版本链的头节点就是当前记录最新的值。
实际上insert undo只在事务回滚时起作用，当事务提交后，该类型的undo日志就没用了，它占用的Undo Log Segment也会被系统回收。接着继续执行sql操作
★很多人以为undo log用于将数据库物理的恢复到执行语句或者事务之前的样子，其实并非如此，undo log是逻辑日志，只是将数据库逻辑的恢复到原来的样子。因为在多并发系统中，你把一个页中的数据物理的恢复到原来的样子，可能会影响其他的事务。 ”
# Read View
Read View遵循一个可见性算法，主要是将要被修改的数据的最新记录中的DB_TRX_ID（即当前事务ID）取出来，与系统当前其他活跃事务的ID去对比（由Read View维护），如果DB_TRX_ID跟Read View的属性做了某些比较，不符合可见性，那就通过DB_ROLL_PTR回滚指针去取出Undo Log中的DB_TRX_ID再比较，即遍历链表的DB_TRX_ID（从链首到链尾，即从最近的一次修改查起），直到找到满足特定条件的DB_TRX_ID, 那么这个DB_TRX_ID所在的旧记录就是当前事务能看见的最新老版本。
在可重复读隔离级别下，我们可以把每一次普通的select查询（不加for update语句）当作一次快照读，而快照便是进行select的那一刻，生成的当前数据库系统中所有未提交的事务id数组（数组里最小的id为min_id）和已经创建的最大事务****id（max_id）的集合，即我们所说的一致性视图readview。在进行快照读的过程中要根据一定的规则将版本链中每个版本的事务id与readview进行匹配查询我们需要的结果。
**快照读是不会看到别的事务插入的数据的。因此，幻读在“当前读”下才会出现。**快照读的实现是基于多版本并发控制，即MVCC，可以认为MVCC是行锁的一个变种，但它在很多情况下，避免了加锁操作，降低了开销；既然是基于多版本，即快照读可能读到的并不一定是数据的最新版本，而有可能是之前的历史版本。MVCC只在 READ COMMITTED 和 REPEATABLE READ两个隔离级别下工作，其他两个隔离级别不和MVCC不兼容。因为READ UNCOMMITTED总是读取最新的数据行，而不是符合当前事务版本的数据行，而SERIALIZABLE 则会对所有读取的行都加锁。**事务的快照时间点（即下文中说到的Read View的生成时间）是以第一个select来确认的。**所以即便事务先开始，但是select在后面的事务的update之类的语句后进行，那么它是可以获取前面的事务的对应的数据。
★ RC和RR隔离级别下的快照读和当前读：RC隔离级别下，快照读和当前读结果一样，都是读取已提交的最新；RR隔离级别下，当前读结果是其他事务已经提交的最新结果，快照读是读当前事务之前读到的结果。RR下创建快照读的时机决定了读到的版本。 ”
对于使用RC和RR隔离级别的事务来说，都必须保证读到已经提交了的事务修改过的记录，也就是说假如另一个事务已经修改了记录但是尚未提交，是不能直接读取最新版本的记录的。核心问题就是：**需要判断一下版本链中的哪个版本是当前事务可见的。**为此，InnoDB提出了一个Read View的概念。
Read View就是事务进行快照读（普通select查询）操作的时候生产的一致性读视图，在该事务执行的快照读的那一刻，会生成数据库系统当前的一个快照，它由执行查询时所有未提交的事务id数组（数组里最小的id为min_id）和已经创建的最大事务id（max_id）组成，查询的数据结果需要跟read view做对比从而得到快照结果。
快照规则
版本链比对规则：
如果落在绿色部分（trx_id<min_id），表示这个版本是已经提交的事务生成的，这个数据是可见的；
如果落在红色部分（trx_id>max_id），表示这个版本是由将来启动的事务生成的，是肯定不可见的；（代表DB_TRX_ID 所在的记录在Read View生成后才出现的，那对当前事务肯定不可见）
如果落在黄色部分（min_id<=trx_id<=max_id），那就包含两种情况：a.若row的trx_id在数组中，表示这个版本是由还没提交的事务生成的，不可见；如果是自己的事务，则是可见的；b.若row的trx_id不在数组中，表示这个版本是已经提交了的事务生成的，可见。（如果在，则代表我Read View生成时刻，你这个事务还在活跃，还没有Commit，你修改的数据，我当前事务也是看不见的；如果不在，则说明，你这个事务在Read View生成之前就已经Commit了，你修改的结果，我当前事务是能看见的）
# 实例说明
当我们执行到第7行的select的语句时，会生成readview[100,200],300,版本链如图所示：
此时我们查询到的数据为lilei300。我们首先要拿最新版本的数据trx_id=300来readview中匹配，落在黄色区间内，一看该数据已经提交了，所以是可见的。
继续往下执行，当执行到第10行的select语句时，因为trx_id=100并未提交，所以版本链依然为readview[100,200],300，版本链如图所示：
此时我们查询到的数据为lilei300。我们按上边操作，从最新版本依次往下匹配，我们首先要拿最新版本的数据trx_id=100来read view中匹配，落在黄色区间内，一看该数据在未提交的数组中，且不是自己的事务，所以是不可见的；然后我们选择前一个版本的数据，结果同上；继续向上找，当找到trx_id=300的数据时，会落在黄色区间，且是提交的，所以数据可见。
继续往下执行，当执行到第13行的select语句时，此时尽管trx_id=100已经提交了，因为是InnoDB的RR模式，所以readview不会更改，仍为readview[100,200],300,版本链如图所示：
此时我们查询到的数据为lilei300。原因同上边的步骤，不再赘述。
★当执行update语句时，都是先读后写的，而这个读，是当前读，只能读当前的值，跟readview查找时的快照读区分开。 ”
刚才演示的是InnoDB下的RR模式，接下来我们简单说一下RC模式，上文中提到的RC模式的数据读都是读最新的即当前读，所以readview是实时生成的，执行语句如图所示：
当我们执行到第13行的select的语句时，会生成readview[200],300，版本链还和之前一样，此时我们查询到的数据为lilei2。原因和上边讲的RR模式下的比对规则相同。
# RC,RR级别下的InnoDB快照读有什么不同？
正是Read View生成时机的不同，从而造成RC,RR级别下快照读的结果的不同
在RR级别下的某个事务的对某条记录的第一次快照读会创建一个快照及Read View, 将当前系统活跃的其他事务记录起来，此后在调用快照读的时候，还是使用的是同一个Read View，所以只要当前事务在其他事务提交更新之前使用过快照读，那么之后的快照读使用的都是同一个Read View，所以对之后的修改不可见；
即RR级别下，快照读生成Read View时，Read View会记录此时所有其他活动事务的快照，这些事务的修改对于当前事务都是不可见的。而早于Read View创建的事务所做的修改均是可见
而在RC级别下的，事务中，每次快照读都会新生成一个快照和Read View, 这就是我们在RC级别下的事务中可以看到别的事务提交的更新的原因
总之在RC隔离级别下，是每个快照读都会生成并获取最新的Read View；而在RR隔离级别下，则是同一个事务中的第一个快照读才会创建Read View, 之后的快照读获取的都是同一个Read View。
此处我们演示的是update的情况，对于删除的情况可以认为是update的特殊情况，会将版本链上最新的数据复制一份，然后将trx_id改成删除操作的trx_id，同时在该条记录的头信息（record header）里的（deleted_flag）标记位上写上true，来表示当前记录已经被删除，在查询时按照上边的规则查到对应的记录，如果delete_flag标记位为true，意味着记录已被删除，则不返回数据。
大家应该还关心一个问题，即undo log什么时候删除呢？系统会判断，没有比这个undo log更早的read view的时候，undo log会被删除。所以这里也就是为什么我们建议你尽量不要使用长事务的原因。长事务意味着系统里面会存在很老的事务视图。由于这些事务随时可能访问数据库里面的任何数据，所以这个事务提交之前，数据库里面它可能用到的回滚记录都必须保留，这就会导致大量占用存储空间。