并发控制

实现事务隔离的机制，称之为并发控制

所谓并发控制，就是保证并发执行的事务在某一隔离级别上的正确执行的机制

针对并发执行的事务，对可能破坏数据正确性的冲突事务，可能选择下面两种处理方式：

1、Delay：延迟某个事务的执行到合法的时刻
2、Abort：直接放弃事务的提交，并回滚该事务可能造成的影响

image.png

多版本并发控制

对应上述每种乐观程度，都可以有多版本的实现方式，多版本的优势在于，可以让读写事务与只读事务互不干扰，因而获得更好的并行度，也正是由于这一点成为几乎所有主流数据库的选择。为了实现多版本的并发控制，需要给每个事务在开始时分配一个唯一标识TID，并对数据库对象增加以下信息

• txd-id，创建该版本的事务TID
• begin-ts及end-ts分别记录该版本创建和过期时的事务TID

• pointer: 指向该对象其他版本的链表

  
  
  image.png

其基本的实现思路是，每次对数据库对象的写操作都生成一个新的版本，用自己的TID标记新版本begin-ts及上一个版本的end-ts，并将自己加入链表。读操作对比自己的TID与数据版本的begin-ts，end-ts，找到其可见最新的版本进行访问。

InnoDB的MVCC
多版本控制（Multiversion Concurrency Control）: 指的是一种提高并发的技术。引入MVCC之后，只有写写之间相互阻塞，读写可以并行，这样大幅度提高了InnoDB的并发度。在内部实现中，InnoDB通过undo log保存每条数据的多个版本，并且能够找回数据历史版本提供给用户读，每个事务读到的数据版本可能是不一样的。在同一个事务中，用户只能看到该事务创建快照之前已经提交的修改和该事务本身做的修改。

MVCC在 Read Committed 和 Repeatable Read两个隔离级别下工作
MySQL的InnoDB存储引擎默认事务隔离级别是RR(可重复读)，是通过 "行级锁+MVCC"一起实现的，快照读不加锁，写加锁
MVCC的实现依赖：隐藏字段、Read View、Undo log
当用户读取一行记录时，若该记录已经被其他事务占用，当前事务可以通过undo读取之前的行版本信息，以此实现非锁定读取

隐藏字段

• DB_TRX_ID(6字节)：表示最近一次对本记录行作修改（insert | update）的事务ID。InnoDB将delete作为update操作，会更新行删除标志为deleted，并非真正删除
• DB_ROLL_PTR(7字节)：回滚指针，指向当前记录行的undo log信息
• DB_ROW_ID(6字节)：随着新行插入而单调递增的行ID。当表没有主键或唯一非空索引时，innodb就会使用这个行ID自动产生聚簇索引。如果表有主键或唯一非空索引，聚簇索引就不会包含这个行ID了。这个DB_ROW_ID跟MVCC关系不大。

Read View

Read View 决定了记录是否对本事务可见。包含以下:

• low_limit_id
  下一个将被分配的事务ID，high water mark，大于等于low_limit_id的事务对于view都是不可见的
• up_limit_id
  活跃事务列表trx_ids中最小的事务ID，low water mark，小于up_limit_id的事务对于view一定是可见的
• trx_ids
  Read View创建时其他未提交的活跃读写事务ID列表。后续即使这些活跃事务修改了记录行的值，对于当前事务也是不可见的。不包括当前事务和已提交的事务
• low_limit_no
  trx_no小于low_limit_no的undo log对于view是可以purge的
• creator_trx_id
  当前创建事务的ID

Undo log

Undo log中存储的是老版本数据，当一个事务需要读取记录行时，如果当前记录行不可见，可以顺着undo log链找到满足其可见性条件的记录行版本。

大多数对数据的变更操作包括 insert/update/delete，在InnoDB里，undo log分为如下两类：

• insert undo log
  事务对insert新记录时产生的undo log, 只在事务回滚时需要, 并且在事务提交后就立即丢弃。
• update undo log
  事务对记录进行delete和update操作时产生的undo log，不仅在事务回滚时需要，快照读也需要，只有当数据库所使用的快照中不涉及该日志记录，对应的回滚日志才会被purge线程删除。
  undo log会产生redo log，也就是undo log的产生会伴随着redo log的产生，这是因为undo log也需要持久性的保护

可见性比较算法
RR隔离级别下，创建一个新事务后，执行第一个select语句的时候，innodb会创建一个Read View，Read View 中会保存系统当前其他活跃事务id列表（即trx_ids）。当用户在这个事务中要读取某个记录行的时候，innodb会将该记录行的DB_TRX_ID(记为trx_id)与该Read View中的一些变量进行比较，判断是否满足可见性条件。

1、如果 trx_id < up_limit_id(低水位), 那么表明“最新修改该行的事务”在“当前事务”创建快照之前就提交了，所以该记录行的值对当前事务是可见的。跳到步骤5。
2、如果 trx_id >= low_limit_id(高水位), 那么表明“最新修改该行的事务”在“当前事务”创建快照之后才修改该行，所以该记录行的值对当前事务不可见。跳到步骤4。
3、如果 up_limit_id <= trx_id < low_limit_id, 表明“最新修改该行的事务”在“当前事务”创建快照的时候可能处于“活动状态”或者“已提交状态”；所以就要对活跃事务列表trx_ids进行查找（源码中是用的二分查找，因为是有序的）：
3.1、如果在活跃事务列表trx_ids中能找到 id 为 trx_id 的事务，表明可能是下面两种情况。这些情况下，这个记录行的值对当前事务都是不可见的，跳到步骤4
3.1.1 在“当前事务”创建快照前，“该记录行的值”被“id为trx_id的事务”修改了，但没有提交
3.1.2 在“当前事务”创建快照后，“该记录行的值”被“id为trx_id的事务”修改了（不管有无提交）
3.2 在活跃事务列表中找不到，则表明“id为trx_id的事务”在修改“该记录行的值”后，在“当前事务”创建快照前就已经提交了，所以记录行对当前事务可见，跳到步骤5。
4、在该记录行的 DB_ROLL_PTR 指针所指向的undo log回滚段中，取出最新的的旧事务号DB_TRX_ID, 将它赋给trx_id，然后跳到步骤1重新开始判断。
5、将该可见行的值返回。

innodb中的Repeatable Read级别, 只有事务在begin之后，执行第一条select（读操作）时, 才会创建一个快照(read view)，将当前系统中活跃的其他事务记录起来；并且事务之后都是使用的这个快照，不会重新创建，直到事务结束。

在innodb中的Read Committed级别, 事务在begin之后，执行每条select（读操作）语句时，快照会被重置，即会重新创建一个快照(read view)。

image.png

这样，对于当前事务的启动瞬间来说，一个数据版本的 row trx_id，有以下几种可能：

• 如果落在绿色部分，表示这个版本是已提交的事务或者是当前事务自己生成的，这个数据是可见的；
• 如果落在红色部分，表示这个版本是由将来启动的事务生成的，是肯定不可见的；
• 如果落在黄色部分，那就包括两种情况
  1、 若 row trx_id 在数组中，表示这个版本是由还没提交的事务生成的，不可见；
  2、若 row trx_id 不在数组中，表示这个版本是已经提交了的事务生成的，可见。

一个数据版本，对于一个事务视图来说，除了自己的更新总是可见以外，有三种情况：

• 版本未提交，不可见；
• 版本已提交，但是是在视图创建后提交的，不可见；
• 版本已提交，而且是在视图创建前提交的，可见。

当前读和快照读

• 快照读(snapshot read)：

• 普通的 select 语句(不包括 select ... lock in share mode, select ... for update)

• 当前读(current read) ：

• select ... lock in share mode，select ... for update，insert，update，delete 语句（这些语句获取的是数据库中的最新数据 14.7.2.4 Locking Reads）

二级索引

InnoDB多版本并发控制(MVCC)对次级索引的处理与对聚集索引的处理不同。聚集索引中的记录将就地更新，其隐藏的系统列指向撤消日志条目，可以从中重建记录的早期版本。与聚集索引记录不同，辅助索引记录不包含隐藏的系统列，也不会就地更新。

更新二级索引列时，将对旧的二级索引记录进行删除标记，插入新记录，并最终清除带有删除标记的记录。当二级索引记录被删除标记或二级索引页被更新的事务更新时，InnoDB将在聚集索引中查找数据库记录。在聚集索引中，检查记录的DB_TRX_ID，如果在启动读取事务之后修改了记录，则从undo log中检索记录的正确版本。

如果将二级索引记录标记为删除或通过较新的事务更新了二级索引页，则不使用覆盖索引技术。 InnoDB而不是从索引结构中返回值，而是在聚集索引中查找记录。

但是，如果启用了索引条件下推(ICP)优化，并且只能使用索引中的字段来评估WHERE条件的某些部分，则 MySQL 服务器仍会将WHERE条件的这一部分下推到使用索引对其进行评估的存储引擎。如果找不到匹配的记录，则避免聚集索引查找。如果找到匹配的记录，即使在删除标记的 Logging，InnoDB也会在聚集索引中查找记录。

总结

当用户读取一行记录时，若该记录已经被其他活跃事务占用，当前事务可以通过undo log读取之前的行版本信息，以此实现非锁定读取。

Percolator的数据行可见性判断与传统的MVCC有所不同，这导致它读取数据行可能需要等待，从而损失了并发性能。要知道MVCC最重要的优点就是读操作不阻塞，以确保读的性能。

传统DBMS的MVCC中，一个事务T1的快照记录的是它‘拍’这个快照时刻活跃事务的集合，通常以这样的方式表示：{ts-min, ts-max}, [ative-t0, active-t1... Active-tN]，这里ts-min表示比ts-min小的事务全部已经提交（所以T1必然可以看到它们的改动）， ts-max表示比ts-max大的一定还没有启动（所以T1必然无法看到它们的改动）， active-ti数组中是活跃的事务id列表，这些事务的改动T1也是看不到的。如果一个事务T2.id在此快照中（ 即T2.id在数组中或者T2.id > ts-max），那么T1看不到T2生成的行版本，否则T1可以看到T2生成的行版本。

而percolator事务模型中，按说其MVCC可见性判断应该是给定事务T1,T2，在没遇到锁的时候，Get 操作，当且仅当 T2.start-ts > T1.commit-ts，T2才能看到T1的改动。遇到 lock 的处理要分情况： 如果 lock 的是晚于 Get 的，Get 操作仍然可以读取快照。 如果 Get 是晚于 lock 的，那么 Get 就必须等待，而不能读已提交的最新的。因为不确定这个 lock 最后会 commit 或是 rollback。假设读取最新的版本，后来事务 commit 了，那就是写了没读到。

之所以需要在每个行提交时刻写入commit-ts，还是因为percolator事务没有全局的事务管理器，每个客户端存储着自己的事务状态。所以系统无法获知此刻有哪些活跃的事务，也就无法为事务创建快照，只能在行中写入提交时间戳，才能做MVCC读。

(以上内容节选自 赵伟：Google Percolator 事务模型的利弊分析)

MVCC有什么问题?

实现 MVCC 最核心的一点就是在事务提交时检测冲突，如果两个事务发生了冲突，可以对其中一个事务进行 rollback 然后抛出异常，或者在 rollback 后在数据库内部重新执行事务。 MySQL直接进行覆盖，不解决冲突