近日在线上系统的使用过程中发现一个死锁问题，场景如下：

存在一批string，可重复性，乱序
并发将此批string插入同一张表，表中该字段有二级唯一索引，主键为自增id
需要防重，防重采用insert ignore语句结合唯一索引进行防重
并发线程池批次为数千，并发量为5
数据库为mysql，innodb引擎

发生死锁，死锁日志如下：

*************************** 1. row ***************************
  Type: InnoDB
  Name: 
Status: 
=====================================
160118 15:43:52 INNODB MONITOR OUTPUT
=====================================
Per second averages calculated from the last 60 seconds
-----------------
BACKGROUND THREAD
-----------------
srv_master_thread loops: 8828234 1_second, 8828233 sleeps, 870289 10_second, 132572 background, 132569 flush
srv_master_thread log flush and writes: 8833888
----------
SEMAPHORES
----------
OS WAIT ARRAY INFO: reservation count 1455871, signal count 1762722
Mutex spin waits 4496319, rounds 19049903, OS waits 466437
RW-shared spins 1034217, rounds 27237845, OS waits 877524
RW-excl spins 511562, rounds 4307928, OS waits 107605
Spin rounds per wait: 4.24 mutex, 26.34 RW-shared, 8.42 RW-excl
------------------------
LATEST DETECTED DEADLOCK
------------------------
160114 20:12:17
*** (1) TRANSACTION:
TRANSACTION 53D484B6, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 11 lock struct(s), heap size 3112, 24 row lock(s), undo log entries 143
MySQL thread id 2972572, OS thread handle 0x7f45609d5700, query id 1469111789 172.22.108.1 admin_rw update
insert ignore into data_info(
        data,
        id,
        created_date )
        values
            ( '156321690_p', 13, now())
         , 
            ( '156512811_p', 13, now())
         , 
            ( '156529371_p', 13, now())
         , 
            ( '156988901_p', 13, now())
         , 
            ( '157280438_p', 13, now())
         , 
            ( '157663173_p', 13, now())
         , 
            ( '1578435-748742', 13, now())
         , 
            ( '15801111', 13, now())
         , 
            ( '158102438_p', 13, now())
         , 
            ( '158108127_p', 13, now())
         , 
            ( '158194111_p', 13, now())
         ,
            ( '158218753_p', 13, now())
         , 
            ( '158243936a', 13, now())
         , 
            ( '158277715_p', 13, now())
         , 
            ( '158516632_p'
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 4 page no 125769 n bits 400 index `unique_index` of table `db1`.`data_info` trx id 53D484B6 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 267 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 18; hex 333732e6bb91e58ebfe5b2b3e4bc9ae88bb9; asc 372               ;;
 2: len 8; hex 8000000000d0b8d0; asc         ;;
*** (2) TRANSACTION:
TRANSACTION 53D484B0, ACTIVE 0 sec inserting, thread declared inside InnoDB 213
mysql tables in use 1, locked 1
13 lock struct(s), heap size 3112, 20 row lock(s), undo log entries 1895
MySQL thread id 2972504, OS thread handle 0x7f47cc1fd700, query id 1469111770 172.22.108.1 admin_rw update
insert ignore into data_info(
        userpin,
        id,
        created_date )
        values
            ( '2185363-8112782', 13, now())
         , 
            ( '220074-12104', 13, now())
         , 
            ( '22317872-263437', 13, now())
         , 
            ( '22432677a', 13, now())
         , 
            ( '243_m', 13, now())
         , 
            ( '2486026_m', 13, now())
         , 
            ( '24q', 13, now())
         , 
            ( '2482839-58590', 13, now())
         , 
            ( '250357-87215', 13, now())
         , 
            ( '2537348-53461', 13, now())
         , 
            ( '2652844-357754', 13, now())
         , 
            ( '27106373_m', 13, now())
         , 
            ( '27923390_m', 13, now())
         , 
            ( '27554-68485737', 13, now())
         , 
            ( '2911506-437245'
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 4 page no 125769 n bits 336 index `unique_index` of table `db1`.`data_info` trx id 53D484B0 lock mode S
Record lock, heap no 265 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 16; hex 3336303434393037342d313431393333; asc 360449074-141933;;
 2: len 8; hex 8000000000d0b8ce; asc         ;;
Record lock, heap no 267 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 18; hex 333732e6bb91e58ebfe5b2b3e4bc9ae88bb9; asc 372               ;;
 2: len 8; hex 8000000000d0b8d0; asc         ;;
Record lock, heap no 296 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 16; hex 3530313738343438312d343835343539; asc 501784481-485459;;
 2: len 8; hex 8000000000d0b8ed; asc         ;;
Record lock, heap no 314 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 9; hex 36363662616e616e61; asc 666banana;;
 2: len 8; hex 8000000000d0b8ff; asc         ;;
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 4 page no 125781 n bits 496 index `unique_index` of table `db1`.`data_info` trx id 53D484B0 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 242 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 8000000d; asc     ;;
 1: len 13; hex 31383238353135313135385f70; asc 18285151158_p;;
 2: len 8; hex 8000000000d0c0b0; asc         ;;
*** WE ROLL BACK TRANSACTION (1)

基本分析

根据日志所述:

事务1在执行的过程中需要获取锁：gap before rec insert intention
事务2需要获取的锁：gap before rec insert intention

根据观察进行问题重现时发现一个事实，而根据每个事务执行的SQL，每个事务中欲获取的锁对应的记录并不在其相应的插入值列表中，而每个事务却要获取一个与其相关的GAP INSERT INTENTION LOCK（插入意向间隔锁）。
还有一个有趣的事实，每个事务准备获取的间隔锁涉及的记录在另一个事务中SQL中的存在两天重复数据并相邻排序（例如，123,aaa,aaa,232），根据undo entry分析，涉及的双方记录都已经进行插入。（MYSQL批量插入在底层同样拆分为单个操作进行，这里由于使用insert ignore语句，因此重复的记录并不会引发报错）

查证

下文中有关的实验使用的表信息

CREATE TABLE `t_1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(20) DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `name_index` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

根据mysql的官方对于这块的解释，insert在唯一索引下会对欲插入的记录索引与上一个索引加插入意向间隔锁，在多个事务对有交叉的间隔中加间隔锁不会发生互相等待，除非多个事务欲插入的记录均为同一个记录，例如，当前数据表table(name varchar)中存在记录a,m, 当前索引表中同样是2个记录(a,m)。参考

表情况	事务1	事务2	备注
a,m			当前索引[a,m]
a,m	insert e		OK 持有意向锁(a,e] 当前索引[a,e,m]
a,m		insert e	OK 持有意向锁(a,c]，意向锁之间不冲突当前索引[a,c,e,m]
a,m	insert c		wait 插入同一条记录与索引c冲突，等待

以上处理事务均为手动提交模式（start transaction）.同时印证，在事务未提交之前，SQL操作也会在底层上修改索引记录。

进一步查证

随后进一步查找资料求解释，终于在一篇文章当中有提及，参考，其中关于insert的加锁中有些阐述：

INSERT的加锁：

插入之前，对插入的间隙加插入意向GAP锁；
插入意向GAP锁表明将向某个间隙插入记录，如果该间隙已被加上了GAP Lock或Next-Key Lock，则加锁失败。
不同事务加的插入意向GAP锁互相兼容，否则就无法并发insert了。

插入成功后，对插入的这条记录加X Record Lock；

如果违反唯一性约束导致插入失败，则对记录加S Next-Key Lock。这一点在并发插入时可能导致死锁。

根据3与1的综合判断，基本得出结论，产生死锁的两个事务分别获得了一个区间的间隔锁，并在数据的插入过程中违反了唯一性约束（重复数据），导致区间被加上了next-key锁，之后分别向对方请求区间锁导致循环等待。关于next-key锁的介绍可以参见

此处后来分析有疑问，测试中发现貌似真正导致后一个事务加不上插入意向锁的原因是因为第一个事务违反唯一索引冲突后对该记录加了S行锁导致事务2加意向GAP锁时候冲突，因为区间锁是左开右闭(x1,x2],而如果在一个事务中再次执行一个插入（比如初始a,m,插入g之后插入e），此时a,e之间无法插入元素的原因是事务1对a,e之间加了S级GAP锁,可以通过如下SQL查询锁的信息

USE information_schema;
--锁等待和持有锁的相互关系
SELECT * FROM INNODB_LOCK_WAITS\G;
--锁等待的原因
SELECT * FROM INNODB_LOCKS\G;

由于线上情景涉及数据较多，现在以最简单方式进行重现：

仍然使用之间提到的测试表t_1：
现有数据：

开启mysql会话控制台，启动两个事务，事务1与事务2：

事务1中进行：

1	insert ignore into t_1(name) values('e'),('e');

由于采用insert ignore批量插入，且发生了违反唯一索引的情况，故插入一行记录，由于有ignore关键字，重复的索引自行忽略，语句没有报错，
但是，mysql仍然对第二个’e’进行了尝试，以至于产生了duplicates 1,根据上文分析，此时事务1对于区间(a,e]拥有next-key锁。其他事务无法立即对此区域内的任何记录进行插入。如图所示：

可以看到，事务2执行：

1	insert ignore into t_1(name) values('b');

由于等待事务1而无法立即插入，在不干预的情况下最终timeout.

此时只有单向等待，事务2等待事务1，事务1并没有等待事务2，因此尚未构成死锁。接下来，构造一个环境让事务1等待事务2.

事务2执行：

1	insert ignore into t_1(name) values('g'),('g');

同样，事务2插入成功一行，同时产生了一个duplicate.此时事务2拥有区间(e,g]的next-key锁。

最后一步:
事务1执行:

1	insert ignore into t_1(name) values('f');

事务2执行:

1	insert ignore into t_1(name) values('b');

事务1想要插入的 f 属于事务2持有next-key锁的区间(e,g]，事务1等待事务2；
事务2想要插入的 b 属于事务1持有next-key锁的区间(a,e]，事务2等待事务1。
循环等待，立即死锁，最后mysql回滚了事务2，执行了事务1。此时两个事务均未提交.

根据SHOW ENGINE INNODB STATUS查看此次试验的死锁日志:

------------------------
LATEST DETECTED DEADLOCK
------------------------
2016-01-21 21:51:49 5c94
*** (1) TRANSACTION:
TRANSACTION 52392, ACTIVE 959 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 1184, 3 row lock(s), undo log entries 2
MySQL thread id 11, OS thread handle 0x60d0, query id 681 localhost ::1 root update
insert ignore into t_1(name) values('f')
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 36 page no 4 n bits 80 index `name_index` of table `test`.`t_1` trx id 52392 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 1; hex 67; asc g;;
 1: len 4; hex 0000001d; asc     ;;
*** (2) TRANSACTION:
TRANSACTION 52393, ACTIVE 509 sec inserting, thread declared inside InnoDB 5000
mysql tables in use 1, locked 1
4 lock struct(s), heap size 1184, 3 row lock(s), undo log entries 2
MySQL thread id 12, OS thread handle 0x5c94, query id 682 localhost ::1 root update
insert ignore into t_1(name) values('b')
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 36 page no 4 n bits 80 index `name_index` of table `test`.`t_1` trx id 52393 lock mode S
Record lock, heap no 4 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 1; hex 67; asc g;;
 1: len 4; hex 0000001d; asc     ;;
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 36 page no 4 n bits 80 index `name_index` of table `test`.`t_1` trx id 52393 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 3 PHYSICAL RECORD: n_fields 2; compact format; info bits 0
 0: len 1; hex 65; asc e;;
 1: len 4; hex 0000001a; asc     ;;
*** WE ROLL BACK TRANSACTION (2)

回顾一下

此次死锁的几个条件：

使用了insert ignore ，dao层检测到重复的唯一索引没有及时中断，导致事务持有了区间next-key锁。
欲插入的数据没有进行预处理，去重与排序
（1）去重不会发生duplicate，从而不会导致事务持有某个区间的next-key锁，
（2）排序之后事务之间请求的区间不会交叉，从另一方面规避了相互等待区间next-key锁
并发对同一张表进行insert操作（线程数>=2）
1,2,3最根本的原因是内因3，去除1可以防止但会影响功能，2只能某种程度规避问题并不能解决，因为当前数据库中的数据不确定。

迭代器模式

提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示。
本示例实现了二叉树的前中后序遍历的迭代器

public interface CommonIterator<E> {
    E first();
    E next();
    Boolean isDone();
}
public interface Tree {
    CommonIterator createFrontIndexIterator();
    CommonIterator createMiddleIndexIterator();
    CommonIterator createBackIndexIterIterator();
}
public class Node implements Tree{
    public Node left;
    public Node right;
    public String name;
    public Node(Node left, Node right, String name) {
        this.left = left;
        this.right = right;
        this.name = name;
    }
    public Node(String name) {
        this.name = name;
    }
    public CommonIterator<Node> createFrontIndexIterator(){
        return  new FrontIndexIter(this);
    }
    public CommonIterator<Node> createMiddleIndexIterator(){
        return  new MiddleIndexIter(this);
    }
    public CommonIterator<Node> createBackIndexIterIterator(){
        return  new BackIndexIter(this);
    }
}
public class FrontIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public FrontIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        stack.push(cursor);
    }
    @Override
    public Node first() {
        return root;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top=stack.pop();
        cursor = top.right;
        if (cursor!=null){
            stack.push(cursor);
        }
        cursor = top.left;
        if (cursor!=null){
            stack.push(cursor);
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class MiddleIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public MiddleIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
    }
    @Override
    public Node first() {
        Node res = root;
        while ((res = res.left) != null) {
        }
        return res;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top = stack.peek();
        stack.pop();
        cursor = top.right;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class BackIndexIter implements CommonIterator<Node> {
    private final Node root;
    private Node cursor = null;
    private Boolean isDone = false;
    private Stack<Node> stack;
    public BackIndexIter(Node root) {
        this.root = root;
        stack = new Stack<>();
        cursor = root;
        while (cursor != null) {
            stack.push(cursor);
            cursor = cursor.left;
        }
    }
    @Override
    public Node first() {
        Node res = root;
        while ((res = res.left) != null) {
        }
        return res;
    }
    @Override
    public Node next() {
        if (stack.isEmpty()) {
            isDone = true;
            return null;
        }
        Node top = stack.peek();
        stack.pop();
        if (!stack.isEmpty()) {
            cursor = stack.peek();
            if ((cursor = cursor.right) != null && cursor != top) {
                while (cursor != null) {
                    stack.push(cursor);
                    cursor = cursor.left;
                }
            }
        }
        return top;
    }
    @Override
    public Boolean isDone() {
        return isDone;
    }
}
public class App {
    public static void main(String[] args) {
        Node one = new Node(
                new Node(new Node(new Node("8"),null,"3"), new Node(new Node("6"), new Node("7"), "4"), "2"),
                new Node(new Node("9"),null,"5"), "1");
        CommonIterator<Node> iter = one.createFrontIndexIterator();
        Node d;
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//1 2 3 8 4 6 7 5 9
        }
        System.out.println();
        iter = one.createMiddleIndexIterator();
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//8 3 2 6 4 7 1 9 5
        }
        System.out.println();
        iter = one.createBackIndexIterIterator();
        while (!iter.isDone() && (d = iter.next()) != null) {
            System.out.print(d.name+" ");//8 3 6 7 4 2 9 5 1
        }
    }
}

Peter I/O

Mediator(中介者)

中介者模式

一个关于insert ignore死锁问题的记录

基本分析

查证

进一步查证

回顾一下

Iterator(迭代器)

迭代器模式