InnoDB：Lock Manager-每日运维

承接 Skywalker：InnoDB：lock manager (1)，这一篇我们研究不同 SQL 对应的加锁方式

MySQL 的默认隔离级别是 Reaptable Read（可重复读），一般来讲 Reaptable Read 的定义是不需要阻止幻读的，但 MySQL 的实现上消除了幻读

幻读（Phantom）

A phantom read occurs when, in the course of a transaction, new rows are added or removed by another transaction to the records being read.

从概念上来讲，只要事务发现一个之前（事务开启后）未见过的数据行，就称作幻读。这里的 "发现" 很有意味，如果事务的执行结果被该数据行所影响，就称之为发现了该数据行

例如：两个事务 T1 / T2，串行执行时 T1 的执行结果，和并行执行时 T1 的执行结果并不相同；而且是由于幻读导致（T1 读到 T2 新插入的数据行）

a write in one transaction changes the result of a search query in another transaction, is called a phantom

从行为上来看，事务发现一个之前未见过的数据行，就是因为事务的 "search query" 的结果被另一个事务改变，则该事务就（可能）会出现幻读。注意，这里的 search query 很广泛，不单指 select 语句，比如 update ... where ...，where 子句也可以叫做 search query（因为也是要查询出来再做修改）。我们看一个存在幻读现象的例子（改变部门 A 的员工工资）：

create table t (id int, salary int, department varchar(32), primary key(id), key(deptment));
insert into t values (1,50,'A'),(2,10,'A'),(3,20,'B')

T1	T2
update t set salary=salary+20 where department='A'
	insert into t values (4,5,'A')
update t set salary=salary-10 where department='A'

事务 T1 首先把部门 A 员工工资都 +20，随后又都 -10。如果无法阻挡 T2 的 insert，那么 T1 的第二次 update 最终会导致 id=4 的员工工资为负数（-5）。究其原因是因为 T1 的第二次 update 读到了 T2 新产生的 id=4 的数据行（幻读）

注：在 Reaptable Read 隔离级别下，MySQL 采用 MVCC 的方式来处理只读语句（e.g. select ... from ...），无论该语句执行多少次均会看到相同的结果，因此不会出现幻读的现象

消除幻读

想要消除上面的例子中的幻读，一个朴素的想法就是锁住 department 的全部成员，延伸一下就是锁住 where 子句（或叫做 "谓词"）。

不同于 record lock，这种叫 predicate lock（谓词锁），试图锁住一个范围。当然，在申请 predicate lock 时需要检查是否和已有的 predicate lock 冲突，但不幸的是，这是一个 NP-complete 难题。

我们可以简化这个问题，即放大 lock 的范围。比如看这个 SQL：查找 1 班成绩在 80 和 90 分之间的学生

SELECT name FROM students WHERE class = 1 AND score > 80 AND score < 90 FOR UPDATE;

我们可以放大范围：锁住 1 班的全体学生，或者 80-90 分的所有班级的学生，根据 students 表的不同索引情况有不同的实现

students 有一个索引是 class，那么该查询会在 class 的索引上查找值为 1 的 record，找到后直接锁住该 record 即可
students 有一个索引是 score，那么该查询会锁住 score 这个索引上 80-90 的范围的所有 record（即使该范围没有 record）

在 InnoDB 实现的就是这种锁的策略，更正式的名字叫 next-key locking。具体的行为就是：

InnoDB 在索引的 B-Tree 叶子节点正/逆序遍历时，一般的对于访问到的 record 要申请 next-key lock。这个 next-key lock 锁住的范围是 (𝑟𝑒𝑐𝑜𝑟𝑑𝑝𝑟𝑒𝑣,𝑟𝑒𝑐𝑜𝑟𝑑]

下一节我们看看为什么这样的行为会使得事务锁住谓词条件的一个超集，从而保证 next-key locking 是正确的

三种不同范围的 Lock

InnoDB 在 next-key lock （LOCK_ORDINARY）的基础上又增加两种模式：LOCK_GAP / LOCK_REC_NOT_GAP。我们通常讲，对一个记录（例如下图的 B）申请某种类型的 lock 指的是：

LOCK_ORDINARY：锁住 B 和 A、B 之间的开区间 (𝐴,𝐵)，最终是 (𝐴,𝐵]
LOCK_GAP：只锁住 A、B 之间的开区间 (𝐴,𝐵)
LOCK_REC_NOT_GAP：只锁住 B

InnoDB：Lock Manager-1 三种 lock

从效果上讲，LOCK_ORDINARY = LOCK_GAP + LOCK_REC_NOT_GAP

三种不同范围 Lock 的兼容性

LOCK_GAP 只锁住一个区间、表示不希望其他任何事务在这个区间插入新的记录。因此如果两个 lock 都是 LOCK_GAP 类型，一般是不冲突的（即你不希望区间内插入新纪录，我也不希望区间内插入新纪录）

同时，LOCK_GAP 和 LOCK_REC_NOT_GAP 也是不冲突的，因此 LOCK_GAP 和 LOCK_ORDINARY 依然不冲突

那么 LOCK_GAP 和什么冲突呢？只和插入的操作冲突

lock_rec_insert_check_and_lock { // insert 操作依然需要申请 LOCK_GAP，我们举个例子 // create table t (id int, primary key(id)); // insert into t values (2)(4)(6)(8); // 那么对于 insert into t values (5); 会把 cursor 定位于第一个小于 5 // 的记录上（记录 6）。申请区间（4,6）的 LOCK_GAP，同时这个 lock 的 type_mode // 具有 LOCK_INSERT_INTENTION 标识。这样如果（4,6）区间存在其他的 LOCK_GAP // 或 LOCK_ORDINARY，则因为 LOCK_INSERT_INTENTION 标识而会产生冲突 const ulint type_mode = LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION;

const lock_t* wait_for = lock_rec_other_has_conflicting( type_mode, block, heap_no, trx); }

LOCK_ORDINARY 和 LOCK_REC_NOT_GAP 则没什么特殊之处。实现可见函数 lock_rec_has_to_wait

// 判断事务1正在申请的 lock 与一个已知的 lock2 是否冲突 lock_rec_has_to_wait( ulint type_mode, // 事务1申请的锁模式 lock_t* lock2) // 事务2持有的 lock { if (trx != lock2->trx && !lock_mode_compatible(static_cast LOCK_MODE_MASK & type_mode), lock_get_mode(lock2))) { // 兼容性矩阵返回"冲突"


      // 1. 如果事务1申请是 LOCK_GAP 而且不是在执行插入操作，则与其余 lock 不会冲突

      if ((lock_is_on_supremum || (type_mode & LOCK_GAP))

        && !(type_mode & LOCK_INSERT_INTENTION)) {

	return(FALSE);

      }
      // 2. 如果事务1不是在执行插入操作，而且 lock2 是 LOCK_GAP 则表示不冲突

      if (!(type_mode & LOCK_INSERT_INTENTION)

        && lock_rec_get_gap(lock2)) {

	return(FALSE);

      }
      // 3. 如果事务1申请的是 LOCK_GAP，lock2 是 LOCK_REC_NOT_GAP 则表示不冲突

      if ((type_mode & LOCK_GAP)

        && lock_rec_get_rec_not_gap(lock2)) {

        return(FALSE);

      }
      // 3. 如果事务2是插入操作，则不会与事务1冲突（事务2在先）

      if (lock_rec_get_insert_intention(lock2)) {

        return(FALSE);

      }
      // 其余情况表示冲突：比如事务1是插入操作，而且 lock2 是 LOCK_GAP

      return(TRUE);

  }

// 与持有 lock2 的事务是同一个事务，或者兼容性矩阵返回"兼容" return(FALSE); }

正确性论证

下文会通过一些例子来看到不同场景（不同的 SQL、不同的执行计划）下不同的加锁方式。但核心原则就是保证：

一个事务检索（search query）的结果不会被另一个事务改变

根据上面的原则，一个简单的实现就是对于一次范围检索，扫描到的每个 record （比如从 A 开始、至 M 结束）都申请 LOCK_ORDINARY。这样封锁住的区间范围是 (𝐴𝑝𝑟𝑒𝑣,𝑀]

假设检索的范围是 [𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑] （e.g where start < id）我们知道： 𝐴≥𝑠𝑡𝑎𝑟𝑡,𝑀≤𝑒𝑛𝑑 （这样的话扫描的 record 才能是 A ~ M），因而有：

(𝐴𝑝𝑟𝑒𝑣,𝑀]⊇[𝐴,𝑀]⊇[𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑]

可以看到这种方法封锁住的区间范围是充分大的。对于 (𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑],[𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑),(𝑠𝑡𝑎𝑟𝑡,𝑒𝑛𝑑) 类似的情况依然成立

InnoDB：Lock Manager-2 Next-key locking

InnoDB 的实现有一些优化，有的场景只需要 LOCK_REC_NOT_GAP / LOCK_GAP 就足够了，这样的话可以减小封锁的范围：

规则 1：如果一次检索时至多能有一个 record 被选中，使用 LOCK_REC_NOT_GAP
规则 2：等值查询时，当遍历到不满足条件的 record，使用 LOCK_GAP

除此之外的场景全部使用 LOCK_ORDINARY。规则 1 的话，如果至多能有一个 record 被选中时，则当锁住这个 record 后（LOCK_REC_NOT_GAP）其他任何事务都不会导致幻读的发生

规则 2 的话是说对于不符合要求的 record 则无需锁住记录本身。比如这个例子：

create table t (c1 int, c2 varchar(16), c3 int, primary key(c1), index(c2)); insert into t values (1,'A',1),(2,'A',2),(4,'C',3),(5,'D',4),(......) update t set c3=10 where c2='A';

InnoDB：Lock Manager-3 (C,4)申请的是 LOCK_GAP

update 语句会选择辅助索引 c2 扫描，（A,1）(A,2) 直至 (C,3) 停止。对于 (C,3) 则只需要申请 LOCK_GAP 而不锁住该记录本身

不锁住 (C,3) 的话，如果另一个事务把 (C,3) 更新为 (A,3) 是否会导致 where c2='A' 检索出的记录发生变化（多出一行）而导致幻读？无需担心，因为辅助索引的 update 是由 delete mark 和 insert 实现，insert (A,3) 会被上图中的 LOCK_GAP 阻塞

InnoDB：Lock Manager

幻读（Phantom）