前言

• 前言
• 为什么要有事务隔离级别？
• 并发控制
  • 从数据结构来看
  • 从手段来看
• 锁（主要指行级别的并发访问控制）
  • 工作原理
  • 具体细节
  • 死锁
• MVCC 为数据提供多个副本
  • 实现细节
• 可重复读——可以读到什么数据
  • 可重复读——更新逻辑
  • mvcc 实现
• 其它
  • 基于 B+Tree 和 Lock 方式的并发控制
  • 调度器

计算机科学中有一种思想：如果一个问题太难了解决不了，那就放宽假设，弱化需求。比如实现数据库事务的“隔离性”会导致性能很差，只能在实验室环境使用，无法用在现实世界，于是人们提出“弱隔离性”，罗列出“读提交”，“可重复读”之类的“弱隔离级别”，越弱的问题越好解决；比如想实现“对业务透明”的分布式事务比较难，要付出很多代价，于是人们就提出放弃“对业务透明”，于是就有了 TCC 和 Saga；……

可能你对隔离性还有点陌生，其实在编程的过程中，我们通常会利用锁进行并发控制，确保临界区的资源不会出现多个线程同时进行读写的情况，这其实就对应了事务的最高隔离级别：可串行化，它能保证多个并发事务的执行结果和一个一个串行执行是一样的。为什么应用程序中可以提供可串行化的隔离级别，而数据库却不能呢？根本原因就是应用程序对临界区大多是内存操作，而数据库要保证持久性（即 ACID 中的 Durability），需要把临界区的数据持久化到磁盘，可是磁盘操作比内存操作要慢好几个数量级，一次随机访问内存、 SSD 磁盘和 SATA 磁盘，对应的操作时间分别为几十纳秒、几十微秒和几十毫秒，这会导致临界区持有的时间变长，对临界区资源的竞争将会变得异常激烈，数据库的性能则会大大降低。所以，数据库的研究者就对事务定义了隔离级别这个概念，也就是在高性能与正确性之间提供了一个缓冲地带，相当于明确地告诉使用者，我们提供了正确性差一点但是性能好一点的模式，以及正确性好一点但是性能差一点的模式，使用者可以按照自己的业务场景来选择。

为什么要有事务隔离级别？

浅谈对数据库隔离级别的理解”隔离性”实质上就是指对数据操作的并发控制。

为什么需要并发控制？它解决了什么问题？在数据库中，如果对于同一数据项的所有事务操作都被串行化地执行，那么执行过程与结果是没有问题的。如果存在并发操作，即多个事务的生命周期(时间区间)之间存在交集，就可能产生操作上的冲突和依赖，进而引发异常现象。操作顺序类型可以分为 读-读、读-写、写-读、写-写 4种类型，其中后三种包含写的操作序列是有冲突的，它们可能会引发执行结果的异常（其实就是与串行执行结果不一样），或者叫异常现象(Anomaly)，比如脏读等。PS：因为数据不是写入就算，而是commit 才算数，所以对另一个事务来说，“眼见不一定为实”，看见X=10，结果可能因为事务执行失败X后来不是10了。PS：一系列操作时不可能一瞬间执行完，所以我们在执行多个操作时，要控制他们的中间状态对外的可见性。

并发控制就是要解决这些异常，但是并发控制需要达到什么程度呢？因为并发控制程度高对应着并发执行效率低，数据库用户并非时刻都需要最强的并发控制方式，这是一致性与并发度的权衡，隔离级别就是这一权衡的控制参数。从数据库开发者的角度来看，需要解决并发操作时的异常现象是根本需求，而隔离级别是把这些无穷多的现象级需求进行了分类、抽象、归纳，将规避异常现象之需求转化为了满足有限种类隔离级别之需求。即数据库开发者只需要实现定义好的几种隔离级别，就可以为数据库系统提供规避某些(可能是无穷多)异常现象的功能。如果一个事务系统在运行时能够规避某些问题集，那么该系统的事务将具有某种相应的隔离级别，即隔离级别抽象出待规避的最小异常现象集合。至于DBMS的某种隔离级别的实现，是否还可能规避对应级别的最小问题集以外的异常序列，并不做限制。

|针对不带加锁行为的普通 SELECT 语句|解决脏读Dirty Read|解决不可重复读Unrepeatable Read|解决幻读Phantom Problem| |—|—|—|—| |读未提交Read Uncommitted|❌|❌|❌| |读已提交Read Committed|✅|❌|❌| |可重复读Repeatable Read|✅| ✅|✅| |串行化Serialization|✅| ✅|✅| 备注：innodb 在可重复读级别下，通过MVCC机制额外解决了幻读Phantom Problem 的问题。

数据库事务隔离发展历史事务隔离是事务并发产生的直接需求，最直观的、保证正确性的隔离方式，显然是让并发的事务依次执行，或是看起来像是依次执行。但在真实的场景中，有时并不需要如此高的正确性保证，因此希望牺牲一些正确性来提高整体性能。通过区别不同强度的隔离级别使得使用者可以在正确性和性能上自由权衡。随着数据库产品数量以及使用场景的膨胀，带来了各种隔离级别选择的混乱，数据库的众多设计者和使用者亟需一个对隔离级别划分的共识，这就是标准出现的意义。

如何标准化、形式化地描述并发读写的(异常)现象？1992年ANSI首先尝试指定统一的隔离级别标准，其定义了不同级别的异象(phenomenas)， 并依据能避免多少异象来划分隔离标准。几年后，微软的研究员们在A Critique of ANSI SQL Isolation Levels一文中对ANSI的标准进行了批判，改造了异象的定义，本质是基于锁的定义，但太过严格的隔离性定义，阻止了Optimize或Multi-version的实现方式中的一些正常的情况。Adya在Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions中给出了基于序列化图得定义，思路为先定义冲突关系；并以冲突关系为有向边形成序列化图；再以图中的环类型定义不同的异象；最后通过阻止不同的异象来定义隔离级别。写写冲突ww；先写后读冲突wr；先读后写冲突rw。PS：总之挺麻烦一件事。

并发控制

从数据结构来看

MySQL 是怎么做并发控制的？ 经典，从代码层级给出了mysql 各层级加锁过程。 按照近些年流行的概念来讲，MySQL 是一个典型的存储计算分离的架构，MySQL Server 作为计算层，Storage Engine 作为存储层。所以并发访问的控制也需要在计算层和存储层分别进行处理。从数据访问的角度，用户视角下，MySQL 的数据分为：表、行、列。MySQL 内部视角下则包括了：表、表空间（在 MySQL 8.0 中，默认情况下一个表独占一个表空间）、索引、B+tree、页、行、列等。MySQL 中的并发访问控制也是基于 MySQL 内部的数据结构来进行设计的，具体包括：

1. 表级别的并发访问控制，包括 Server 层和 Engine 层上的表；表锁主要保护的是表结构，在 MySQL 8.0 版本中，表结构的保护都是由 MDL 锁完成；非 InnoDB 表（CSV 表）还会依赖 Server 层的表锁进行并发控制，InnoDB 表不需要 Server 层加表锁；
2. 页级别的并发访问控制，包括 Index 和 Page 上的并发访问；主要是为了保护 B+tree 的安全性。
   1. InnoDB 引擎通过 B+tree 来保存数据，B+tree 中的每一个节点都是一个数据页（Page），页也是 InnoDB 中数据读写的最小单元，InnoDB 中默认的页大小为 16KB。
   2. 页级别的并发访问控制发生在 B+tree 的遍历过程，也就是 B+tree 的加锁过程；加锁的对象包括了 index 和 page；加锁的类型包括了 S，SX 和 X，其中 S 锁和 SX 锁不互斥；查询过程只加 S 锁；修改过程，根据修改的类型加锁过程有所区别。如果是页内的数据修改，走乐观更新的逻辑，只有被修改的叶子节点加 X 锁；如果是悲观更新的逻辑，index 和根节点要加 SX 锁，索引可能被修改的节点都要加 X 锁；
3. 行级别的并发访问控制；行锁主要是为了保护行记录的一致性。
   1. 行锁并不只是行记录上的锁，行锁的类型包括了：记录锁（Rec Lock）、间隙锁（Gap Lock）、下键锁（Next-Key Lock）和插入意向锁（Insert Intention Lock）；PS：不仅是保护行记录本身的安全读写，必要时还要阻断行记录前后的插入，所以锁类型搞了这么多。
   2. 行锁依赖于索引，非索引条件查询将退化为表锁，可能增加锁竞争，影响并发性能。
   3. 行锁是按需创建的，如果是第一次插入，默认不加锁（隐式锁），只有出现冲突时才会升级为显式锁；
   4. 记录锁（Rec Lock）上只有 S 锁和 S 锁兼容；间隙锁（Gap Lock）上 S 锁和 X 锁可以兼容，X 锁和 X 锁也可以兼容；下键锁（Next-Key Lock）就是记录锁和间隙锁的组合，处理的时候也是分开的；插入意向锁（Insert Intention Lock）的产生一定是因为有其他事务持有个待插入间隙的间隙锁；
   5. 所有锁的释放都是在事务提交时，所以为了减少死锁的产生，建议事务尽快提交；

B+tree 的加锁过程

1. 假设现在需要访问的数据是 ID = 400 的行，那么 B+tree 上的访问路径如下图所示。B+tree 的加锁过程其实也是按照上述访问路径进行的。具体的步骤如下：
   1. 加 index 上的 S 锁；
   2. 加根节点上的 S 锁；
   3. 加非叶子节点上的 S 锁；
   4. 加叶子节点上的 S 锁；
   5. 释放 index 和所有非叶子节点上的 S 锁；
      
2. 如果是页上的乐观更新（或者是页内的插入），那么 B+tree 上加锁的过程如下图所示：
   1. 加 index 上的 S 锁；
   2. 加根节点上的 S 锁；
   3. 加非叶子节点上的 S 锁；
   4. 加叶子节点上的 X 锁；
   5. 释放 index 和所有非叶子节点上的 S 锁； 可以看到，如果是页内的修改，其实加锁的逻辑和读过程的加锁类似很像，只是最后在叶子节点上加锁的类型不一样。
3. 如果更新的数据无法在页内完成，或者说修改动作会造成 B+tree 结构的变化（SMO, Structure Modify Operation），又应该如何进行加锁？InnDB 在执行数据更新操作时，会首先尝试使用乐观更新（MODIFY LEAF），如果乐观更新失败，那么会 进入到悲观更新（MODIFY TREE）的逻辑，悲观更新的加锁过程如下图所示：
   1. 加 index 上的 SX 锁；（5.7 版本引入了 SX 锁，SX 锁和 S 锁不互斥，所以此时还可以读）
   2. 根节点不加锁
   3. 非叶子节点上不加锁，但是会搜索所有经过的节点；
   4. 判断可能修改的非叶子节点加 X 锁，根节点加 SX 锁；
   5. 叶子节点，包括前后叶子节点加 X 锁； 在后续 B+tree 遍历的过程中，只是先收集索引经过的节点，并没有直接上锁。只有到了要修改的叶子节点时，才会去判断哪些非叶子节点也可能会修改，从而加上 X 锁。所以在整个 SMO 期间，除了可能会被修改的叶子节点和非叶子节点加的是 X 锁之外，其他的节点都没有加锁（index 和根节点是 SX 锁），非修改节点上的读操作可以正常进行。但是一棵 B+tree 上同时只能有一个 SMO 操作。

从手段来看

浅析数据库并发控制实现事务隔离的机制，称之为并发控制。并行执行的事务可以满足某一隔离性级别的正确性要求。要满足正确性要求就一定需要对事务的操作做冲突检测，对有冲突的事务进行延后或者丢弃。并发控制机制 根据检测冲突的时机不同可以简单分成三类：

1. 基于Lock：最悲观的实现，需要在操作开始前，甚至是事务开始前，对要访问的数据库对象加锁，对冲突操作Delay；
2. 基于Timestamp：乐观的实现，每个事务在开始时获得全局递增的时间戳，期望按照开始时的时间戳依次执行，在操作真正写数据的时候检查冲突并选择Delay或者Abort；
3. 基于Validation：更乐观的实现，仅在Commit前进行Validate，对冲突的事务Abort

三种策略的立足点其实是对冲突的乐观程度，越乐观，也就是认为冲突发生越少，就越倾向于推迟冲突的检测。直观的也可以看出，越晚的冲突检测越有可能获得高的并发。但当冲突真正出现时，由于前面的操作可能都需要一笔勾销，因此在冲突较多的场景下，太乐观反而得不偿失。

相同的乐观程度下，还存在多版本的实现。所谓多版本，就是在每次需要对数据库对象修改时，生成新的数据版本，每个对象的多个版本共存。读请求可以直接访问对应版本的数据，从而避免读写事务和只读事务的相互阻塞。当然多版本也会带来对不同版本的维护成本，如需要垃圾回收机制来释放不被任何事物可见的版本。

并发控制机制并不与具体的隔离级别绑定。无论是乐观悲观的选择，多版本的实现，读写锁，两阶段锁等各种并发控制的机制，归根接地都是在确定的隔离级别上尽可能的提高系统吞吐，可以说隔离级别选择决定上限，而并发控制实现决定下限。

锁（主要指行级别的并发访问控制）

锁的类型

1. 锁，锁表、锁行； 读写锁、互斥锁。
2. 谓词锁，它的加锁对象不属于特定的对象（例如表中的一行），它属于所有符合某些搜索条件的对象。
   1. 比如间隙锁（Next-Key Locking）就是关于谓词锁的简化以及性能更好的一个实现。互斥锁是行锁，只会锁定一行特定的记录，而间隙锁则是锁定两行记录之间的空隙，防止其他事务在此间隙中插入新的记录（一种在记录前面添加的锁，该锁阻止新记录插入到当前记录的前面，直到当前记录的间隙锁释放后新记录才能正常插入），仅在可重复读隔离级别下生效。间隙锁虽然解决了幻读问题，但因每次都会锁住一段间隙，大大降低了数据库整体的并发度，且因间隙锁和间隙锁之间不互斥，不同事务可以同时对同一间隙加上 Gap Locks，这也往往是各种死锁产生的源头。
   2. Next-Key Locks 是 (Shard/Exclusive Locks + Gap Locks) 的结合，当 session A 给某行记录 R 添加了互斥型的 Next-Key Locks 后， 相当于拥有了记录 R 的 X 锁和记录 R 的 Gap Locks，在可重复读隔离级别下，update 和 delete 操作默认都会给记录添加 Next-Key Locks。
   3. 插入意向锁 (Insert Intention Locks) 作用于新记录的 INSERT 流程中，配合着间隙锁使用的。由 INSERT 操作在行数据插入之前获取在插入一条记录前，需要先定位到该记录在 B+ 树中的存储位置，然后判断待插入位置的下一条记录上是否添加了 Gap Locks，如果下一条记录上存在 Gap Locks，那么插入操作就需要阻塞等待，直到拥有 Gap Locks 的那个事务提交（间隙锁释放后插入意向锁也会释放）。同时执行插入操作等待的事务也会在内存中生成一个锁结构，表明有事务想在某个间隙中插入新记录，但目前处于阻塞状态，生成的锁结构就是插入意向锁。
3. 表级意向锁。针对细粒度资源加锁之前，需要遵循自外向内的顺序，事先申请好更粗粒度资源的意向锁。比如在对表中一行记录加锁之前，需要先申请数据库级别意向锁、表级别意向锁、页级别意向锁，前置操作都处理成功后，最后再对具体的行记录加行锁。在 innodb 的具体实现中，针对意向锁的设计比较简练，就将其设定在表级的粒度，分为共享和独占式两种占有模式。所有申请行锁的操作都需要实现申请到相同占有模式下的表级意向锁. 比如针对一行记录加 X Lock，则需要先申请得到该行所在的表级 IX Lock。表级意向锁事实上不会阻塞表锁之外的任何流程。

工作原理

浅析数据库并发控制基于Lock实现的Scheduler需要在事务访问数据前加上必要的锁保护，为了提高并发，会根据实际访问情况分配不同模式的锁，常见的有读写锁，更新锁等。最简单地，需要长期持有锁到事务结束，为了尽可能的在保证正确性的基础上提高并行度，数据库中常用的加锁方式称为两阶段锁（2PL），Growing阶段可以申请加锁，Shrinking阶段只能释放，即在第一次释放锁之后不能再有任何加锁请求。需要注意的是2PL并不能解决死锁的问题，因此还需要有死锁检测及处理的机制，通常是选择死锁的事务进行Abort。PS：跟分布式事务有点一样

Scheduler对冲突的判断还需要配合Lock Table，如下图所示是一个可能得Lock Table信息示意，每一个被访问的数据库对象都会在Lock Table中有对应的表项，其中记录了当前最高的持有锁的模式、是否有事务在Delay、以及持有或等待对应锁的事务链表；同时对链表中的每个事务记录其事务ID，请求锁的模式以及是否已经持有该锁。Scheduler会在加锁请求到来时，通过查找Lock Table判断能否加锁或是Delay，如果Delay需要插入到链表中。对应的当事务Commit或Abort后需要对其持有的锁进行释放，并按照不同的策略唤醒等待队列中Delay的事务。PS：java 是将锁信息附着在对象header 上，但feel 是一样的

MYSQL 中锁的各种模式与类型

insert 插入流程

具体细节

InnoDB 事务锁源码分析InnoDB 中的lock是事务中对访问/修改的record加的锁，它一般是在事务提交或回滚时释放。latch是在BTree上定位record的时候对Btree pages加的锁，它一般是在对page中对应record加上lock并且完成访问/修改后就释放，latch的锁区间比lock小很多。在具体的实现中，一个大的transaction会被拆成若干小的mini transaction（mtr），如下图所示：有一个transaction，依次做了insert，select…for update及update操作，这3个操作分别对应3个mtr，每个mtr完成：

1. 在btree查找目标record，加相关page latch；
2. 加目标record lock，修改对应record
3. 释放page latch

为什么latch的锁区间比lock小很多？是为了并发，事务中的每一个操作，在步骤二完成之后，相应的record已经加上了lock保护起来，确保其他并发事务无法修改，所以这时候没必要还占着record所在的page latch，否则其他事务 访问/修改 相同page的不同record时，这本来是可以并行做的事情，在这里会被page latch会被卡住。

RR支持可重复读，也就是在一个事务中，多次执行相同的SELECT…FOR UPDATE应该看到相同的结果集（除本事务修改外），这个就要求SELECT的区间里不能有其他事务插入新的record，所以SELECT除了对满足条件的record加lock之外，对相应区间也要加lock来保护起来。在InnoDB的实现中，并没有一个一下锁住某个指定区间的锁，而是把一个大的区间锁拆分放在区间中已有的多个record上来完成。所以引入了Gap lock和Next-key lock的概念，它们加再一个具体的record上

1. Gap lock 保护这个record与其前一个record之间的开区间。
2. Next-key lock 保护包含这个record与其前一个record之间的左开右闭区间。 它们都是为了保护这个区间不能被别的事务插入新的record，实现RR。

万字解析 mysql innodb 锁机制实现原理间隙锁 Gap Lock 指的是针对行记录之间的间隙范围上锁，其存在本质上为了规避幻读问题（Phantom Problem），因此间隙锁是不涉及所谓共享或者排它的概念的，它的目标很明确，就是拦截间隙范围内即将到来的 insert 行为，除此之外它不会阻塞其它任何的流程。间隙锁是专为拦截间隙中的 insert 行为而生，因此其生效的前提依赖于 insert 行为的配合。 具体来说就是，执行 insert 操作时，会定位到拟插入记录所属的范围，然后检查右边界第一条记录的索引（间隙锁和行锁类似，也是依附于索引而存在），判断是否存在间隙锁标识。 例如，间隙锁的范围是index ∈ (3,4) ，那么间隙锁标识信息会依附于索引 index = 4 而存在。

死锁

所谓死锁 Dead Lock，指的是在两个以上事务的执行过程中，针对锁资源形成循环依赖关系，最终造成互相等待的现象。在 innodb 中，针对死锁问题制定了两种对策：

1. 超时 timeout 机制：产生死锁的直接导火索就是等锁行为，那么最简单粗暴的方式就是遇到长时间等待直接回滚. 具体来说就是给阻塞等锁行为设置一个时间阈值，一旦超时就直接回滚。
2. 等待图 wait-for graph 机制：这是一种主动探测死锁的方式。针对事务的等锁依赖关系构造出一条链表，如果链表形成环状，则代表存在死锁问题。此时 innodb 会选择事务进行回滚，进而破坏等锁链表回路。在回滚事务时，会选择对权重最小的事务作为目标，此处提到的权重值指的是事务涉及修改和锁住的行记录数量。

死锁一般是下面情况导致

循环依赖不同锁，但加锁顺序不一致

线程1   lock(l1x)  lock(l2x)
线程2   lock(l2x)  lock(l1x)

线程1   lock(l1s)  lock(l2x)
线程2   lock(l2s)  lock(l1x)

线程1   lock(l1s)  lock(l2x)
线程2   lock(l2x)  lock(l1x)

线程1   lock(l1x)  lock(l2x)
线程2   lock(l2s)  lock(l1x)

对同一个锁先共享后互斥
线程1   lock(ls)  lock(lx)
线程2   lock(ls)  lock(lx)

具体到mysql 则情况更为复杂，共享锁、排它锁、意向锁的兼容矩阵 ||X|IX|S|IS| |—|—|—|—|—| |X|冲突|冲突|冲突|冲突| |IX|冲突|兼容|冲突|兼容| |S|冲突|冲突|兼容|兼容| |IS|冲突|兼容|兼容|兼容|

避免死锁的办法：对不同的锁，加锁要顺序一致。对同一个锁，要避免先读后写。减少事务的粒度（行锁是在需要的时候才加上的，但并不是不需要了就立刻释放，而是要等到事务结束时才释放）。

查看当前数据库的死锁情况 SHOW ENGINE INNODB STATUS;

查看一条sql 会加那些锁

mysql> begin; # 开启事务，注意一定要在事务里操作，否则sql 执行完了，啥也看不到。
mysql> sql1;
mysql> SELECT * FROM performance_schema.data_locks; # 查看有哪些事务申请了哪些锁
...
mysql> commit;

其它细节：同一个sql 不同的隔离级别可能会加不同的锁；发生死锁后，innodb 会选择回滚undo 量最小的事务。

当出现死锁时，如果开启了 performance_schema，可以通过查询 performance_schema 下的 data_locks 表查看所等待关系，然后手动进行处理；如果实在不想分析锁等待的关系，可以把 data_locks 表中所有涉及的连接全部 kill；如有真的出现了死锁，在 MySQL 的错误日志中会打印出锁等待关系，可以通过锁等待关系进行分析，优化业务侧的写入逻辑；

MVCC 为数据提供多个副本

1. 每个事务拥有唯一的事务ID（transaction id）。
2. 更新操作会在undo log中保存旧版本数据，并标记新数据的事务ID。
3. 查询时根据事务的视图（由已提交的最大事务ID界定）决定可见版本，从而实现不同隔离级别的逻辑。

实现细节

万字解析 mysql innodb 锁机制实现原理针对读已提交和可重复读的事务隔离级别，innodb 采用多版本并发控制 Multi-Version Concurrent Control（简称 MVCC）作为应对策略. MVCC 在实现上可以拆分为【版本链结构实现】和【版本选择策略】两个部分：

1. 版本链结构：每当事务修改一行记录时，会基于写时复制（Copy-On-Write）策略生成一份副本，并通过指针指向上一个版本的数据记录。如此一来，依据修改的先后顺序，各行记录会形成一条链表状的数据结构。
   1. 在 innodb 的行记录中，会包含如下三个隐藏列：row_id；transaction_id；roll_pointer（回滚指针）。于是，版本链的拓扑结构就很清楚了，一次修改行为会生成一个记录的一个版本，会通过 transaction_id 标识其由哪个事务修改生成. 这样的一个版本就是链表中的一个节点，节点之间通过回滚指针 roll_pointer 串联形成单向链表.
   2. 在版本链中，一个版本根据其从属的事务是否已经成功提交，分为正式数据和草稿数据两类. 需要意识到，由于有行 X Lock 的存在，因此同一时刻至多只能有一个事务对一行数据记录进行修改.此外值得一提的是，innodb 中，为了支持事务回滚操作启用了 undo log 机制，因此天然就形成对应的版本链机制，在 MVCC 实现中可以直接进行复用，不存在额外的成本开销。只不过为了保证 MVCC 中数据视图的一致性，针对 undo log 中老版本数据的回收时机（purge）需要适当延后，保证直到不存在更小的活跃事务 id 存在时才能进行回收。
2. 版本选择策略：针对普通 SELECT 语句的查询行为，本质上就是遍历版本链，然后挑选合适的版本数据，以此保证查询视角的一致性。

innodb 会提供一个查询视图 Read View，其中包含如下几部分信息：

1. trx_list：当前处于活跃状态的事务 ID 列表（活跃的意思就是未提交，用于遍历版本链时判断该版本数据是正式版本还是草稿副本）
2. up_limit_id：trx_list 中的最小活跃事务 ID（undo log 版本链中，对于事务 id < up_limit_id 的老版本数据可以进行回收）
3. low_limit_id：分配给下一个事务的 id. 保证全局唯一且递增 基于以上，在可重复读和读已提交两个事务隔离级别中，在执行普通 SELECT 语句时都会获取 Read View，并针对行记录的版本链进行遍历，并遵循如下规则：
4. 如果遇到某个版本的事务 id 等于当前事务 id，直接选取该版本（同一个事务修改的内容，哪怕是草稿态也要读取到）
5. 遍历找到首个事务 id 不在 trx_list 的事务（代表该版本是已提交的最新版数据）作为选取的版本 而可重复读和读已提交的区别就在于：
6. 【读已提交】会在每次执行 SELECT 查询时，实时获取最新的 Read View 视图。
7. 【可重复读】只在事务开启时获取一次 Read View，并在整个生命周期进行复用. 同时针对上述第 2）条，还需要保证选取版本的事务 id < low_limit_id。 这样就能屏蔽事务开启后其它并发事务的一切修改和提交行为，进而保证当前事务视角的一致性。

《MySQL实战45讲》一个事务要更新一行，如果刚好有另外一个事务拥有这一行的行锁，它又不能这么超然了，会被锁住，进入等待状态。问题是，既然进入了等待状态，那么等到这个事务自己获取到行锁要更新数据的时候，它读到的值又是什么呢？

1. begin/start transaction 命令并不是一个事务的起点，在执行到它们之后的第一个操作 InnoDB 表的语句，事务才真正启动。如果你想要马上启动一个事务，可以使用 start transaction with consistent snapshot 这个命令。
2. 在 MySQL 里，有两个“视图”的概念
   1. 一个是 view。它是一个用查询语句定义的虚拟表，创建视图的语法是 create view … ，而它的查询方法与表一样。
   2. 另一个是 InnoDB 在实现 MVCC 时用到的一致性读视图，即 consistent read view，用于支持 RC（Read Committed，读提交）和 RR（Repeatable Read，可重复读）隔离级别的实现。它没有物理结构，作用是事务执行期间用来定义“我能看到什么数据”。
3. 在可重复读隔离级别下，事务在启动的时候就“拍了个快照”。注意，这个快照是基于整库的。如果一个库有 100G，那么我启动一个事务，MySQL 就要拷贝 100G 的数据出来，这个过程得多慢啊。实际上，我们并不需要拷贝出这 100G 的数据。
4. InnoDB 里面每个事务有一个唯一的事务 ID，叫作 transaction id。它是在事务开始的时候向 InnoDB 的事务系统申请的，是按申请顺序严格递增的。数据表中的一行记录，其实可能有多个版本 (row)，每个版本有自己的 row trx_id（trx_id 即操作 row 的事务id）。一行记录的 多个版本并不是物理上真实存在的，而是每次需要的时候根据当前版本和 undo log 计算出来的

可重复读——可以读到什么数据

按照可重复读的定义，一个事务启动的时候，能够看到所有已经提交的事务结果。但是之后，这个事务执行期间，其他事务的更新对它不可见。在实现上， InnoDB 为每个事务构造了一个数组，用来保存这个事务启动瞬间，当前正在“活跃”的所有事务 ID。“活跃”指的就是，启动了但还没提交。数组里面事务 ID 的最小值记为低水位，当前系统里面已经创建过的事务 ID 的最大值加 1 记为高水位。

数据版本的可见性规则，就是基于数据的 row trx_id 和这个高低水位/事务视图（每个事务的高低水位都不同）对比结果得到的。对于当前事务的启动瞬间来说，一个数据版本的 row trx_id，有以下几种可能：

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

有了这个声明后，系统里面随后发生的更新，是不是就跟这个事务看到的内容无关了呢？因为之后的更新，生成的版本一定属于上面的 2 或者 3(a) 的情况，而对它来说，这些新的数据版本是不存在的，所以这个事务的快照，就是“静态”的了。InnoDB 利用了“所有数据都有多个版本”的这个特性，实现了“秒级创建快照”的能力（PS：有点copy on write的feel）。一个数据版本，对于一个事务视图来说，除了自己的更新总是可见以外，有三种情况：

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

可重复读——更新逻辑

当事务要去更新数据的时候，就不能再在历史版本上更新了，否则其它事务的更新就丢失了。update 更新数据都是先读后写的，而这个读，只能读当前的值，称为“当前读”（current read）：必须要读最新版本，而且必须加锁。当前读的规则，就是要能读到所有已经提交的记录的最新值。

如果当前记录的行锁被其他事务占用的话，就需要进入锁等待。根据两阶段锁协议，其他事务提交才会释放锁，因此可以读到其他事务提交后的row。

除了 update 语句外，select 语句如果加锁，也是当前读

# 加读锁
mysql> select k from t where id=1 lock in share mode;
# 加写锁
mysql> select k from t where id=1 for update;

mvcc 实现

postgresql、mysql、tidb对 mvcc 有着不同的实现方案。

TiKV 事务模型概览，Google Spanner 开源实现MVCC层暴露给上层的接口行为定义：

MVCCGet(key, version), 返回某 key 小于等于 version 的最大版本的值
MVCCScan(startKey, endKey, limit, version), 返回 [startKey, endKey) 区间内的 key 小于等于 version 的最大版本的键和值，上限 limit 个
MVCCPut(key, value, version) 插入某个键值对，如果 version 已经存在，则覆盖它。上层事务系统有责任维护自增version来避免read-modify-write
MVCCDelete(key, version) 删除某个特定版本的键值对, 这个需要与上层的事务删除接口区分，只有 GC 模块可以调用这个接口

其它

基于 B+Tree 和 Lock 方式的并发控制

B+树数据库加锁历史如何选择Lock/Timestamp/Validation 归根结底是由用户的使用场景决定的，在不能对用户场景做太多假设的通用数据库中，毫无疑问，基于Lock的方式显得更为合适。除此之外，由于MVCC的广泛应用消除了读写之间的冲突，使得Lock带来的并发影响大大降低，也使得基于Lock的并发控制仍然是主流。

对数据库的数据加锁这件事情，本身是跟数据的组织方式是密不可分的，数据组织方式可能给加锁带来限制，同时利用组织方式的特性，可能也能改造和优化加锁过程。如何在B+Tree数据库上，基于Lock的方式，来实现高并发、高效的数据库并发控制？B+Tree加锁的发展历史（不是很专业，就不介绍那么细了）

1. 2PL，由于B+Tree的从根向下的搜索模式，事务需要持有从根节点到叶子节点路径上所有的锁。而两阶段锁(2PL)又要求所有这些锁都持有到事务Commit。更糟糕的是，任何插入和删除操作都有可能导致树节点的分裂或合并（Structure Modification Operations, SMO），因此，对根结点需要加写锁WL，也就是说任何时刻只允许一个包含Insert或Delete操作的事务进行。
2. Tree Protocol。略。2PL和Tree Protocol中面临的最大问题其实在于：节点的SMO时需要持有其父节点的写锁。之所以这样，是由于需要处理父节点中的对应key及指针，节点的分裂或合并，跟其父节点的修改是一个完整的过程，不允许任何其他事务看到这个过程的中间状态。
3. Blink Tree。巧妙的提出对所有节点增加右向指针，指向其Sibling节点，这是个非常漂亮的解决方案，因为他其实是提供了一种新的节点访问路径，让上述这种SMO的中间状态，变成一种合法的状态，从而避免了SMO过程持有父节点的写锁。
4. ARIES/KVL 峰回路转。上面讲到的传统的加锁策略，认为Btree的节点是加锁的最小单位，而所做的努力一直是在降低单个事务需要同时持有的锁的节点数，能不能更进一步提升Btree的并发能力呢？ARIES/KVL首先明确的区分了B+Tree的物理内容和逻辑内容，逻辑内容就是存储在B+Tree上的那些数据记录，而B+Tree自己本身的结构属于物理内容，物理内容其实事务是不关心的，那么节点分裂、合并这些操作其实只是改变了B+Tree的物理内容而不是逻辑内容。因此，ARIES/KVL就将这些从Lock的保护中抽离出来，也就是Lock在Record上加锁，对物理结构则通过Latch来保护其在多线程下的安全。这里最本质的区别是Latch不需要在整个事务生命周期持有，而是只在临界区代码的前后。可以看作是分层事务的一种实现。
   1. Latch保护物理结构。Latch才是我们在多线程编程中熟悉的，保护临界区访问的锁。通过Latch来保护B+Tree物理结构其实也属于多线程编程的范畴，上述传统的B+Tree加锁方式的优化，也可以直接无缝转化过来。只是将Lock换成的Latch，其作用对象也从事务之间变成线程之间。
   2. Lock保护逻辑结构。有了这种清晰的区分，事务的并发控制就变得清晰很多，不再需考虑树本身的结构变化。假设事务T1要查询、修改、删除或插入一个Record X，而Record X所在的Page为q，那么加Lock过程就变成这样：

       Search（X）and Hold Latch(q);
       SLock(X) or WLock(X);
       // Fetch, Insert or Delete
       Unlatch(q);
       ....
       T Commit and Unlock(X)
      

5. Key Range Locking，前面这套结合Latch和Lock方案，已经可以很好的支持对单条Record的增删改查。但很多数据库访问并不是针对某一条记录的，而是基于条件的。比如查询满足某个条件的所有Record，这个时候就会出现《数据库事务隔离发展历史》中提到的幻读的问题，也就是在事务的生命周期中，由于新的满足条件的Record被其他事务插入或删除，导致该事务前后两次条件查询的结果不同。这其实是要求，条件查询的事务和插入/删除满足这个条件Record的事务之间，有相互通信或冲突发现的机制，最直接的想法是对所有可能的，还不存在的Key也加锁，在大多数情况下，由于Key范围的无限，这都是不可接受的。传统的解决幻读的方案是谓词锁(Predicate Lock)，也就是直接对查询条件加锁，每次插入删除需要判断是否与现有的判断条件冲突，但通用数据库中，条件千变万化，判断条件冲突这件事情开销极大。也正是因此，谓词锁并没有成为主流。在B+Tree上，由于其Key有序的特点，通常会采用Key Range Locking，也就是对Key加锁，来保护其旁边的区间Range。其中最常见的一种实现是Next Key Locking。
6. Instant Locking，上述加锁过程中，Insert需要对要插入位置的Next Key加Lock，如果已经是最大则需要对正无穷加Lock，并持有整个事务生命周期。在高频率顺序插入的场景，这个Next Key Lock就会成为明显的瓶颈。Instant Locking的方案很好地解决了这个问题。顾名思义，Instant Locking只在瞬间持有这把Next Key Locking，其加锁是为了判断有没有这个Range冲突的读操作，但获得锁后并不持有，而是直接放锁。乍一看，这样违背了2PL的限制，使得其他事务可能在这个过程获得这把锁。通过巧妙的利用Btree操作的特性，以及Latch及Lock的配合，可以相对完美的解决这个问题，如下是引入Instant Locking后的Insert加Next Key Lock的流程：

    Search（M，Y）and Hold Latch(q);
   
    XLock(Y);
    Unlock(Y)
   
    XLock(M);
   
    Insert M into q
   
    Unlatch(q);
    ....
   
    T Commit and Unlock(M)
   

   可以看出，Y上Lock的获取和释放，和插入新的Record两件事情是在Page q的Latch保护下进行的，因此这个中间过程是不会有其他事务进来的，等Latch释放的时候，新的Record其实已经插入，这个X到Y的区间已经被划分成了，X到M以及M到Y，新的事务只需要对自己关心的Range加锁即可。分析这个过程，可以提前放锁的根本原因是：Insert的New Record在其他事务对这个Range加锁的时候已经可见。Delete就没有这么幸运了，因为Delete之后这个Key就不可见了，因此Delete的持有的Next Key Locking似乎不能采用Instant Locking，这个时候Ghost Record就派上用场了。

7. Ghost Records，Ghost Record的思路，其实跟之前讲到拆分物理内容和逻辑内容是一脉相承的，Ghost Record给每个记录增加了一位Ghost Bit位，正常记录为0，当需要删除某个Record的时候，直接将其Ghost Bit修改为1即可，正常的查询会检查Ghost Bit，如果发现是1则跳过。但是Ghost Record是可以跟正常的Record一样作为Key Range Lock的加锁对象的。可以看出这相当于把删除操作变成了更新操作，因此删除事务不再需要持有Next Key Lock。除此之外，由于回滚的也变成了修改Ghost Bit，不存在新的空间申请需要，因此避免了事务回滚的失败。Ghost Record的策略也成为大多数B+Tree数据库的必选实现方式。当然，这些Ghost Record最终还是需要删除的，其删除操作通常会放到后台异步进行，由于Ghost Record对用户请求是不可见的，因此这个删除过程只是对物理结构的改变，也不需要加Lock。但Record的删除会导致其左右的两个Lock Range合并，因此这个过程除了需要Page的Latch之外，还需要获得Lock系统中Lock的Latch，在Lock的Latch保护下对Lock Range合并。
8. 后续的研究多围绕权衡Lock粒度、新的Lock Mode及缩短Lock持有时间等方向继续前进。事务在操作数据库时，会先对要访问的元素加对应的Lock，为了更高的并发， Lock通常有不同的Mode，如常见的读锁SL，写锁WL，不同Mode的锁相互直接的兼容性可以用兼容性表来表示。

从实现的角度对几种隔离级别进行理解从上锁的强弱考虑，我们有互斥锁（Mutex Lock，又称写锁）和共享锁（Shared Lock，又称读锁）；从上锁的长短来考虑，我们有长时锁（Long Period Lock，事务开始获取锁，到事务结束时释放）和短时锁（Short Period Lock，访问数据时获取，用完旋即释放）；从上锁的粗细来考虑，我们有对象锁（Row Lock，锁一行）和谓词锁（Predicate Lock，锁一个范围）。说到数据范围，由于数据库在存储层实现时都是基于 KV 模型，如 B+ 树中 Page 和 LSM-Tree 中的 Block 都是一组 KV 条目。对应到关系型数据库中，如果按行存储，则单条 KV 的 Key 通常是主键， Value 通常是一行数据。因此，之后事务修改数据的范围都可以理解为：

1. 单个对象。可以理解为一个 KV 条目。
2. 一组对象。如 where x > 5 谓词语句，会确定一个 KV 范围子集。 性能最好的隔离级别就是不上任何锁，但会存在脏读（Dirty Read，一个事务读到另一个事务未提交的更改）和脏写（Dirty Write，一个事务覆盖了另外一个事务未提交的更改）的问题。为了避免脏写，可以给要更改的对象加长时写锁，但读数据时并不加锁，此时的隔离级别称为读未提交（RU，Read Uncommitted）。但此时仍然会有脏读，为了避免脏读，可以对要读取的对象加短时读锁，此时的隔离级别是是读已提交（RC，Read Committed）。但由于加的是短时读锁，一个事务先后两次读 x，而在中间空挡，另一个修改 x 的事务提交，则会出现两次读取不一致的问题，此种问题称为不可重复读。为了解决此问题，需要在读取数据的时候也加长时读锁。解决了不可重复读的隔离级别称为可重复读（RR，Repeatable Read）。到可重复读级别，都是针对单条数据上锁。在此隔离级别下，如果一个事务两次进行范围查询，比如说执行两次 select count(x) where x > 5；另一个事务在两次查询中间插入了一条 x = 6，这两次读到的结果并不一样，这种现象称为幻读（Phantom Read）。为了解决幻读问题，需要针对范围查询语句加长时谓词读锁。解决了幻读的隔离级别，我们称为可串行化（Serializability）。

从更抽象角度来说，每个事务在执行过程中都要去摸（touch）一个数据子集，针对该数据子集可能会读，可能会写；如果两个并发的事务，摸到的数据子集并不相交，则不用加锁，可以放心并发。如果数据子集有相交之处，为了维持事务执行过程中的因果关系（也可以理解为依赖关系，如多次读取数据一致，依赖某个读取内容进行决策后修改，依赖的内容不能为其他事务所修改，不然做出的决策就有问题），从而维持事务并发执行后的一致性（从数据库层面看是要维持外键约束等不变性；从用户层面看是符合业务直觉，不能出现类似 1+1=3 的结果）。但这没有覆盖到到另一个常见的隔离级别——快照隔离（Snapshot Isolation），因为它引出了另一种实现族——MVCC。由于属于不同的实现，快照隔离和可重复读在隔离级别的光谱上属于一个偏序关系，不能说谁强于谁。

调度器

需要指出的是并发控制由数据库的调度器负责，事务本身并不感知。如下图所示，Scheduler将多个事务的读写请求，排列为合法的序列，使之依次执行：

数据库通常会有一个调度模块来负责资源的加锁放锁，以及对应事务的等待或丢弃。所有的锁的持有和等待信息会记录在一张Lock Table中，调度模块结合当前的Lock Table中的状况和锁模式的兼容表来作出决策。比如：事务T3已经持有了元素A的写锁WL，导致事务T1和T2无法获得读锁SL，从而在队列中等待，直到T3结束释放WL后，调度模块再依次唤醒等待的事务。

这个过程中，对可能破坏数据正确性的冲突事务，调度器可能选择下面两种处理方式：

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