MYSQL INNODB replace into 死锁 及 next key lock 浅析

原创：全文带入了大量自我认知和理解，可能错误，因为水平有限，但是代表我努力分析过。



一、问题提出
问题是由姜大师提出的、问题如下：
表：
mysql> show create table c \G
*************************** 1. row ***************************
       Table: c
Create Table: CREATE TABLE `c` (
  `a` int(11) NOT NULL AUTO_INCREMENT,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  UNIQUE KEY `b` (`b`)
) ENGINE=InnoDB 
1 row in set (0.01 sec)
开启两个会话不断的执行
replace into c values(NULL,1);
会触发死锁。问死锁触发的原因。

我使用的环境：
MYSQL 5.7.14 debug版本、隔离级别RR、自动提交，很显然这里的c表中的可以select出来的记录始终是1条
只是a列不断的增大，但是这里实际存储空间确不止1条，因为从heap no来看二级索引中，heap no 已经到了
7，也就是有至少7(7-1)条记录,只是其他记录标记为del并且被purge线程放到了page free_list中。

二、准备工作和使用方法
1、稍微修改了源码关于锁的打印部分，我们知道每个事物下显示锁内存结构lock 
   struct会连接成一个链表，只要按照顺序打印出内存lock struct就打印出了
   所有关于这个事物显示锁全部信息和加锁顺序如下：



正常的版本只有

部分后面的都是我加上的，其实修改很简单，innodb其实自己写好了只是没有开启，我开启后加上了序号来表示顺序。
上面是一个 select * from c where  id2= 20 for update; b列为辅助索引的所有4 lock struct(s)，可以看到有了这些信息分析
不那么难了。
这里稍微分析一下
表结构为：
mysql> show create table c4;
+-------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table                                                                                                                                                  |
+-------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
| c4    | CREATE TABLE `c4` (
  `id1` int(11) NOT NULL,
  `id2` int(11) DEFAULT NULL,
  PRIMARY KEY (`id1`),
  KEY `id2` (`id2`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+-------+---------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
数据为：
mysql> select * from c4;
+-----+------+
| id1 | id2  |
+-----+------+
|   1 |    1 |
|  10 |   10 |
|  20 |   20 |
|  30 |   30 |
+-----+------+
4 rows in set (0.00 sec)
语句为：
 select * from c  where  id2= 20 for update;
RR模式
从锁结构链表来看，这个语句在辅助索引分别锁定了
id2:20 id1:20 LOCK_X|LOCK_ORDINARY 也就是NEXT KEY LOCK
同时锁定了
id2:30 id1:30 LOCK_X|LOCK_GAP也就是gap lock不包含这一列
那么画个图容易理解黄色部分为锁定部分：

是不是一目了然？如果是rc那么锁定的只有记录了两个黄色箭头
表示gap没有了就不在画图了
2、在死锁检测回滚前调用这个打印函数打印到err日志文件中，打印出全部的事物的显示内存lock struct如下，这里就
不给出了，后面会有replace触发死锁千事物锁结构的一个输出


3、使用MYSQL TRACE SQL语句得到大部分的函数调用来分析replace的过程

修改出现的问题：修改源码打印出所有lock struct 在线上显然是不能用的。因为打印出来后show engine innodb status 会非常
长，甚至引发其他问题，但是测试是可以，其次修改了打印死锁事物锁链表到日志后，每次只要遇到死锁信息可以打印
到日志，但是每次MYSQLD都会挂掉，但是不影响分析了。

三、预备知识(自我理解)
1、
Precise modes:
#define LOCK_ORDINARY 0 /*!< this flag denotes an ordinary
next-key lock in contrast to LOCK_GAP
or LOCK_REC_NOT_GAP */
默认是LOCK_ORDINARY及普通的next_key_lock,锁住行及以前的间隙
#define LOCK_GAP 512 /*!< when this bit is set, it means that the
lock holds only on the gap before the record;
for instance, an x-lock on the gap does not
give permission to modify the record on which
the bit is set; locks of this type are created
when records are removed from the index chain
of records */
间隙锁，锁住行以前的间隙，不锁住本行
#define LOCK_REC_NOT_GAP 1024 /*!< this bit means that the lock is only on
the index record and does NOT block inserts
to the gap before the index record; this is
used in the case when we retrieve a record
with a unique key, and is also used in
locking plain SELECTs (not part of UPDATE
or DELETE) when the user has set the READ
COMMITTED isolation level */
行锁，锁住行而不锁住任何间隙
#define LOCK_INSERT_INTENTION 2048 /*!< this bit is set when we place a waiting
gap type record lock request in order to let
an insert of an index record to wait until
there are no conflicting locks by other
transactions on the gap; note that this flag
remains set when the waiting lock is granted,
or if the lock is inherited record */
插入意向锁，如果插入的记录在某个已经锁定的间隙内为这个锁
2、参数innodb_autoinc_lock_mode的值为1，也许不能保证replace into的顺序。
3、infimum和supremum
   一个page中包含这两个伪列，页中所有的行未删除(删除未purge)的行都连接到这两个虚列之间，其中
   supremum伪列的锁始终为next_key_lock。
4、heap no
   此行在page中的heap no heap no存储在fixed_extrasize 中，heap no 为物理存储填充的序号，页的空闲空间挂载在page free链表中(头插法)可以重用，
   但是重用此heap no不变，如果一直是insert 则heap no 不断增加，并非按照KEY大小排序的逻辑链表顺序，而是物理填充顺序 
5、n bits
   和这个page相关的锁位图的大小如果我的表有9条数据 还包含2个infimum和supremum虚拟列 及 64+11 bits，及75bits但是必须被8整除为一个字节就是
   80 bits
6、隐含锁(Implicit lock)和显示锁(explict)
锁有隐含和显示之分。隐含锁通常发生在 insert 的时候对cluster index和second index 都加隐含锁，如果是UPDATE(DELETE)对cluster index加显示锁 辅助
索引加隐含锁。目的在于减少锁结构的内存开销，如果有事务需要和这个隐含锁而不兼容，这个事务需要帮助 insert或者update(delete)事物将隐含
锁变为显示锁，然后给自己加锁，通常insert主键检查会给自己加上S锁，REPLACE、delete、update通常会给自己加上X锁。

四、replace过程分析
通过replace的trace找到了这些步骤的大概调用：
首先我们假设
TRX1：replace 不提交
TRX2：replace 堵塞
TRX1：replace 提交
TRX2：replace 继续执行直到完成
这样做的目的在于通过trace找到TRX2在哪里等待，确实如我所愿我找到了。

1、检查是否冲突，插入主键 

2、检查是否冲突，插入辅助索引，这里实际上就是会话2被堵塞的地方，如下解释
(如果冲突回滚先前插入的主键内容)

我们可以隐隐约约看到row_ins_sec_index_entry_low和row_ins_clust_index_entry_low回检查是否有重复的行
    分别代表是二级索引和聚集索引的相关检查，因为就这个案例主键不可能出现重复值，而二级索引这个例子中肯定是
    重复的，索引row_ins_sec_index_entry_low触发了等待，其实我们知道这里的锁方式如下列子：
    
---lock strcut(2):(Add by gaopeng) In modify Version I force check all REC_LOCK/TAB_LOCK chain! for this Trx
RECORD LOCKS space id 406 page no 4 n bits 72 index b of table `test`.`c` trx id 177891 lock_mode X(LOCK_X) waiting(LOCK_WAIT)
Record lock, heap no 3 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 4; hex 80000001; asc     ;;
 1: len 4; hex 80000006; asc     ;;
 
LOCK_X|LOCK_ORDINARY|LOCK_WAIT：需要X的next_key lock处于等待状态他需要锁定(infimum,{1,6}]这个区间。
这也是死锁发生的关键一个环节。

3、这里涉及到了回滚操作，从下面的trace输出我们也能看到确实做了回滚
   实际上事物2会堵塞在这里，因为我做trace的时候他一直停在
   这里不动了。为此我还加上598行说明在这里wait了

4、这个重复key会传递给SERVER层次，并且貌似重新初始化了事物(只是从trace猜测)

5、接下就是真正删除插入主键

6、接下就是真正插入辅助索引

注意：上面只是看trace出来的过程，很多是根据函数调用进行的猜测。

五、死锁前事物锁信息打印分析
打印出死锁前事物的全部信息

这里涉及两个事物
1、TRANSACTION 182592
2、TRANSACTION 182588
事物182588先于182592执行。
在上一次事物结束后：
留下的数据为：
a=0X911 b=0X1
那么开始辅助索引上的逻辑链表 如下(这里只画单项链表)




死锁流程流程开始：
时刻N：
---  TRX:182588   lock strcut(2)
    supremum和 a=0X911 b= 0X1 均加LOCK_X|LOCK_ORDINARY
    为独占NEXT KEY LOCK，
    换句话说整个范围都加锁了，就这个列子replace期间不能
    插入任何数据，这点比较狠。
    如下图黄色部分都是这里加锁了：


时刻N+1：
--- TRX：182592  lock strcut(2)
检查辅助索引唯一性，这里在上面的trace中已经说明过了
等待发生，锁类型为  LOCK_X|LOCK_ORDINARY|LOCK_WAIT
同样为独占NEXT KEY LOCK处于WAIT范围是0X1 0X911如下图 红色箭头部分都
是要想加锁的其实就是0X1 0X911和infimum到0X1 0X911的范围：                                                                                                                                      

时刻N+2：
--- TRX:182588  
   这里涉及一个重点和lock strcut(5)
    (参数innodb_autoinc_lock_mode的值为1，也许不能 保证replace into的顺序有关)，
   显然这个时候如果 我要插入的新数据是 a=0X908 b= 0X1 ，只要小于 a=0X911 b= 0X1
    就会落到TRX182592锁定的范围那锁的类型为：
    LOCK_X|LOCK_GAP|LOCK_INSERT_INTENTION|LOCK_WAIT
    因为这个范围已经被其他事物TRX：182592锁定本事物WAIT
   插入意向GAP锁不能获得
    如下图绿色箭头就表示a=0X908 b=0X1需要插入到的位置，显然
   已经被TRX：182592锁定：                                                       

                        

这样一来 TRX:182588等待TRX：182592等待TRX:182588的流程就出来了，死锁触发。
从整个死锁的关键来看视乎innodb_autoinc_lock_mode能够保证并发事物获得自增值的
顺序就成了关键，如果能够保证顺序显然 a=0X908 b= 0X1 这样的记录不可能出现，因为0X911
后面应该是0X912，如果是a=0X912 b=0X1自然不会落到infimum到 a=0X911 b= 0X1之间不会被TRX182592堵塞
死锁也不会出现，所以这里死锁触发还是需要一定条件的。
如下图：

六、实验初次验证

我使用如下：
CREATE TABLE `c` (
  `a` int(11) NOT NULL ,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`a`),
  UNIQUE KEY `b` (`b`)
) ENGINE=InnoDB ;

这个存储过程增加奇数
DELIMITER //  
CREATE PROCEDURE test1()
begin 
  declare num int;
set num = 1; 
while num <= 100000000 do
  replace into c values(num,1);
  set num = num+2;
end while;
end //
这个存储过程增加偶数
CREATE PROCEDURE test2()
begin 
  declare num int;
set num = 2; 
while num <= 100000000 do
  replace into c values(num,1);
  set num = num+2;
end while;
end //
DELIMITER ;

TRX1：时间N
mysql> call test1();        

TRX2：时间N+0.5分钟
 mysql> call test2();继续执行

TRX1：（几乎同时） 时间N+0.5分钟
mysql> call test1();    
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

TRX2：
  mysql> call test2();继续执行

可以看到这两个存储过程不会产生同样的主键一个为奇数一个为偶数
然后让test1先跑一会，然后再跑test2()目的在于模拟上面主键自增
取值小于当前值的情况，果然基本是马上就出现死锁了。
例如某一时刻 test1() 中主键的值为1001
此时test2()才开始跑这个时候主键值为2
那么就模拟出来上面判断的0X911后事物取值为0X908的情况，只是这里不再是偶然事件，
而是必然，而原题中为偶然事件。
由于家里没有修改了源码的环境就先看show engine innodb status中
的死锁如下：

可以看到完全一致，证明问题判断正确。

七、疑问
1、
二级索引中heap no运行一段时间后如下：
00200010000e 80000001800008af
002000180054 8000000180000712
00200020000e 8000000180000014
00240028002a 8000000180000017
002000300070 80000001800008e0
00200038fff2 8000000180000911
00200040002a 800000018000001a
00200048002a 800000018000001b
00000050ff82 8000000180000912
002000580000 800000018000001d
00200060ff90 800000018000001e
00200068ffd6 800000018000090e
00200070ff58 80000001800008df
很显然这里只有8000000180000912 是当前数据，其他都标记为了del，按理说长度一样的数据进行删除插入，空间应该
会不断重用，为什么有时候重用不了呢？
2、在整个replace加锁流程中，我并没有完全搞懂，譬如182588的lock strcut(3)和lock strcut(1)分别是什么时候加
     的用于保护什么操作，这里只是从死锁现象进行了分析。

八、RC模式下我做了同样的测试得到如下的死锁前事物LOCK STRUCT链表和RR模式基本无异。不在分析给出即可。
mysql> show variables like '%tx_isolation%';
+---------------+----------------+
| Variable_name | Value          |
+---------------+----------------+
| tx_isolation  | READ-COMMITTED |
+---------------+----------------+
1 row in set (0.09 sec)


本文某些关键点参考了文章，最大的提示就是自增值不是有序的，这点以后要验证一下，但是实验也证明了这一点：
https://yq.aliyun.com/articles/41190


作者微信: