目录
一、死锁是怎么被发现的？
二、innodb隔离级别、索引与锁
三、死锁成因
四、如何尽可能避免死锁
五、如何定位死锁成
前言
线上某服务时不时报出如下异常(大约一天二十多次)：“Deadlock found when trying to get lock;”。
Oh, My God! 是死锁问题。尽管报错不多，对性能目前看来也无太大影响，但还是需要解决，保不齐哪天成为性能瓶颈。 为了更系统的分析问题，本文将从死锁检测、索引隔离级别与锁的关系、死锁成因、问题定位这五个方面来展开讨论。
图1 应用日志
一、死锁是怎么被发现的？
1.1 死锁成因&解决办法
左图那两辆车造成死锁了吗？不是！右图四辆车造成死锁了吗？是！
图2 死锁描述
我们mysql用的存储引擎是innodb，从日志来看，innodb主动探知到死锁，并回滚了某一苦苦等待的事务。问题来了，innodb是怎么探知死锁的？
直观方法是在两个事务相互等待时，当一个等待时间超过设置的某一阀值时，对其中一个事务进行回滚，另一个事务就能继续执行。这种方法简单有效，在innodb中，参数innodblockwait_timeout用来设置超时时间。
仅用上述方法来检测死锁太过被动，innodb还提供了wait-for graph算法来主动进行死锁检测，每当加锁请求无法立即满足需要并进入等待时，wait-for graph算法都会被触发。
1.2 wait-for graph原理
我们怎么知道上图中四辆车是死锁的？他们相互等待对方的资源，而且形成环路！我们将每辆车看为一个节点，当节点1需要等待节点2的资源时，就生成一条有向边指向节点2，最后形成一个有向图。我们只要检测这个有向图是否出现环路即可，出现环路就是死锁！这就是wait-for graph算法。
图3 wait for graph
innodb将各个事务看为一个个节点，资源就是各个事务占用的锁，当事务1需要等待事务2的锁时，就生成一条有向边从1指向2，最后行成一个有向图。
二、innodb隔离级别、索引与锁
死锁检测是死锁发生时innodb给我们的救命稻草，我们需要它，但我们更需要的是避免死锁发生的能力，如何尽可能避免？这需要了解innodb中的锁。
1.2.1 锁与索引的关系
假设我们有一张消息表(msg)，里面有3个字段。假设id是主键，token是非唯一索引，message没有索引。
innodb对于主键使用了聚簇索引，这是一种数据存储方式，表数据是和主键一起存储，主键索引的叶结点存储行数据。对于普通索引，其叶子节点存储的是主键值。
图4 聚簇索引和二级索引 下面分析下索引和锁的关系。 1) deletefrommsgwhereid=2；
由于id是主键，因此直接锁住整行记录即可。
图5 2) deletefrommsgwheretoken=’cvs’;
由于token是二级索引，因此首先锁住二级索引(两行)，接着会锁住相应主键所对应的记录；
图6 3) deletefrommsgwheremessage=订单号是多少’；
message没有索引，所以走的是全表扫描过滤。这时表上的各个记录都将添加上X锁。
图7
1.2.2 锁与隔离级别的关系
大学数据库原理都学过，为了保证并发操作数据的正确性，数据库都会有事务隔离级别的概念：
1)未提交读(Read uncommitted)；
2)已提交读(Read committed(RC))；
3)可重复读(Repeatable read(RR))；
4)可串行化(Serializable)。
我们较常使用的是RC和RR。
提交读(RC)：只能读取到已经提交的数据。
可重复读(RR)：在同一个事务内的查询都是事务开始时刻一致的，InnoDB默认级别。
我们在1.2.1节谈论的其实是RC隔离级别下的锁，它可以防止不同事务版本的数据修改提交时造成数据冲突的情况，但当别的事务插入数据时可能会出现问题。
如下图所示，事务A在第一次查询时得到1条记录，在第二次执行相同查询时却得到两条记录。从事务A角度上看是见鬼了！这就是幻读，RC级别下尽管加了行锁，但还是避免不了幻读。
图8
innodb的RR隔离级别可以避免幻读发生，怎么实现？当然需要借助于锁了！
为了解决幻读问题，innodb引入了gap锁。
在事务A执行：update msg set message=‘订单’ where token=‘asd’;
innodb首先会和RC级别一样，给索引上的记录添加上X锁，此外，还在非唯一索引’asd’与相邻两个索引的区间加上锁。
这样，当事务B在执行insert into msg values (null,‘asd',’hello’); commit;时，会首先检查这个区间是否被锁上，如果被锁上，则不能立即执行，需要等待该gap锁被释放。这样就能避免幻读问题。
图9
推荐一篇好文，可以深入理解锁的原理：http://hedengcheng.com/?p=771#_Toc374698322
三、死锁成因
了解了innodb锁的基本原理后，下面分析下死锁的成因。如前面所说，死锁一般是事务相互等待对方资源，最后形成环路造成的。下面简单讲下造成相互等待最后形成环路的例子。
3.1不同表相同记录行锁冲突
这种情况很好理解，事务A和事务B操作两张表，但出现循环等待锁情况。
图10
3.2相同表记录行锁冲突
这种情况比较常见，之前遇到两个job在执行数据批量更新时，jobA处理的的id列表为[1,2,3,4]，而job处理的id列表为[8,9,10,4,2]，这样就造成了死锁。
图11
3.3不同索引锁冲突
这种情况比较隐晦，事务A在执行时，除了在二级索引加锁外，还会在聚簇索引上加锁，在聚簇索引上加锁的顺序是[1,4,2,3,5]，而事务B执行时，只在聚簇索引上加锁，加锁顺序是[1,2,3,4,5]，这样就造成了死锁的可能性。
图12
3.4 gap锁冲突
innodb在RR级别下，如下的情况也会产生死锁，比较隐晦。不清楚的同学可以自行根据上节的gap锁原理分析下。
图13
四、如何尽可能避免死锁
1)以固定的顺序访问表和行。比如对第2节两个job批量更新的情形，简单方法是对id列表先排序，后执行，这样就避免了交叉等待锁的情形；又比如对于3.1节的情形，将两个事务的sql顺序调整为一致，也能避免死锁。
2)大事务拆小。大事务更倾向于死锁，如果业务允许，将大事务拆小。
3)在同一个事务中，尽可能做到一次锁定所需要的所有资源，减少死锁概率。
4)降低隔离级别。如果业务允许，将隔离级别调低也是较好的选择，比如将隔离级别从RR调整为RC，可以避免掉很多因为gap锁造成的死锁。
5)为表添加合理的索引。可以看到如果不走索引将会为表的每一行记录添加上锁，死锁的概率大大增大。
五、如何定位死锁成因
下面以本文开头的死锁案例为例，讲下如何排查死锁成因。
1)通过应用业务日志定位到问题代码，找到相应的事务对应的sql；
因为死锁被检测到后会回滚，这些信息都会以异常反应在应用的业务日志中，通过这些日志我们可以定位到相应的代码，并把事务的sql给梳理出来。
start tran
1deleteHeartCheckDOByToken
2updateSessionUser
...
commit
此外，我们根据日志回滚的信息发现在检测出死锁时这个事务被回滚。
2)确定数据库隔离级别。
执行select @@global.tx_isolation，可以确定数据库的隔离级别，我们数据库的隔离级别是RC，这样可以很大概率排除gap锁造成死锁的嫌疑;
3)找DBA执行下show InnoDB STATUS看看最近死锁的日志。
这个步骤非常关键。通过DBA的帮忙，我们可以有更为详细的死锁信息。通过此详细日志一看就能发现，与之前事务相冲突的事务结构如下：
start tran
1updateSessionUser
2deleteHeartCheckDOByToken
...
commit
这不就是图10描述的死锁嘛！
转载自：小哈学JAVA公众号

一、Mysql 锁类型和加锁分析
1、锁类型介绍：
MySQL有三种锁的级别：页级、表级、行级。表级锁：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高,并发度最低。
行级锁：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低,并发度也最高。
页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般
算法：next KeyLocks锁，同时锁住记录(数据)，并且锁住记录前面的Gap
Gap锁，不锁记录，仅仅记录前面的Gap
Recordlock锁(锁数据，不锁Gap)
所以其实 Next-KeyLocks=Gap锁+ Recordlock锁
2、加锁分析：
二、死锁产生原因和示例
1、产生原因：
所谓死锁：是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用，它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。表级锁不会产生死锁.所以解决死锁主要还是针对于最常用的InnoDB。
死锁的关键在于：两个(或以上)的Session加锁的顺序不一致。
那么对应的解决死锁问题的关键就是：让不同的session加锁有次序
2、产生示例：
案例一
需求：将投资的钱拆成几份随机分配给借款人。
起初业务程序思路是这样的：
投资人投资后，将金额随机分为几份，然后随机从借款人表里面选几个，然后通过一条条select for update 去更新借款人表里面的余额等。
例如两个用户同时投资，A用户金额随机分为2份，分给借款人1，2
B用户金额随机分为2份，分给借款人2，1
由于加锁的顺序不一样，死锁当然很快就出现了。
对于这个问题的改进很简单，直接把所有分配到的借款人直接一次锁住就行了。
Select * from xxx where id in (xx,xx,xx) for update
在in里面的列表值mysql是会自动从小到大排序，加锁也是一条条从小到大加的锁例如(以下会话id为主键)：
Session1:
mysql> select * from t3 where id in (8,9) for update;
+----+--------+------+---------------------+
| id | course | name | ctime               |
+----+--------+------+---------------------+
|  8 | WA     | f    | 2016-03-02 11:36:30 |
|  9 | JX     | f    | 2016-03-01 11:36:30 |
+----+--------+------+---------------------+
rows in set (0.04 sec)
Session2:
select * from t3 where id in (10,8,5) for update;
锁等待中……
其实这个时候id=10这条记录没有被锁住的，但id=5的记录已经被锁住了，锁的等待在id=8的这里
不信请看
Session3:
mysql> select * from t3 where id=5 for update;
锁等待中
Session4:
mysql> select * from t3 where id=10 for update;
+----+--------+------+---------------------+
| id | course | name | ctime               |
+----+--------+------+---------------------+
| 10 | JB     | g    | 2016-03-10 11:45:05 |
+----+--------+------+---------------------+
row in set (0.00 sec)
在其它session中id=5是加不了锁的，但是id=10是可以加上锁的。
案例二
在开发中，经常会做这类的判断需求：根据字段值查询(有索引)，如果不存在，则插入；否则更新。以id为主键为例，目前还没有id=22的行
Session1:
select * from t3 where id=22 for update;
Empty set (0.00 sec)
session2:
select * from t3 where id=23  for update;
Empty set (0.00 sec)
Session1:
insert into t3 values(22,'ac','a',now());
锁等待中……
Session2:
insert into t3 values(23,'bc','b',now());
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
当对存在的行进行锁的时候(主键)，mysql就只有行锁。
当对未存在的行进行锁的时候(即使条件为主键)，mysql是会锁住一段范围(有gap锁)
锁住的范围为：
(无穷小或小于表中锁住id的最大值，无穷大或大于表中锁住id的最小值)
如：如果表中目前有已有的id为(11 ， 12)
那么就锁住(12，无穷大)
如果表中目前已有的id为(11 ， 30)
那么就锁住(11，30)
对于这种死锁的解决办法是：
insert into t3(xx,xx) on duplicate key update `xx`='XX';
用mysql特有的语法来解决此问题。因为insert语句对于主键来说，插入的行不管有没有存在，都会只有行锁
案例三mysql> select * from t3 where id=9 for update;
+----+--------+------+---------------------+
| id | course | name | ctime               |
+----+--------+------+---------------------+
|  9 | JX     | f    | 2016-03-01 11:36:30 |
+----+--------+------+---------------------+
row in set (0.00 sec)
Session2:
mysql> select * from t3 where id<20 for update;
锁等待中
Session1:
mysql> insert into t3 values(7,'ae','a',now());
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
这个跟案例一其它是差不多的情况，只是session1不按常理出牌了，
Session2在等待Session1的id=9的锁，session2又持了1到8的锁(注意9到19的范围并没有被session2锁住)，最后，session1在插入新行时又得等待session2,故死锁发生了。
这种一般是在业务需求中基本不会出现，因为你锁住了id=9，却又想插入id=7的行，这就有点跳了，当然肯定也有解决的方法，那就是重理业务需求，避免这样的写法。
案例四
一般的情况，两个session分别通过一个sql持有一把锁，然后互相访问对方加锁的数据产生死锁。
案例五
两个单条的sql语句涉及到的加锁数据相同，但是加锁顺序不同，导致了死锁。
案例六
死锁场景如下：
表结构：CREATE TABLE dltask (
id bigint unsigned NOT NULL AUTO_INCREMENT COMMENT ‘auto id’,
a varchar(30) NOT NULL COMMENT ‘uniq.a’,
b varchar(30) NOT NULL COMMENT ‘uniq.b’,
c varchar(30) NOT NULL COMMENT ‘uniq.c’,
x varchar(30) NOT NULL COMMENT ‘data’,
PRIMARY KEY (id),
UNIQUE KEY uniq_a_b_c (a, b, c)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT=’deadlock test’;
a，b，c三列，组合成一个唯一索引，主键索引为id列。
事务隔离级别：
RR (Repeatable Read)
每个事务只有一条SQL：
delete from dltask where a=? and b=? and c=?;
SQL的执行计划：
死锁日志：
众所周知，InnoDB上删除一条记录，并不是真正意义上的物理删除，而是将记录标识为删除状态。(注：这些标识为删除状态的记录，后续会由后台的Purge操作进行回收，物理删除。但是，删除状态的记录会在索引中存放一段时间。) 在RR隔离级别下，唯一索引上满足查询条件，但是却是删除记录，如何加锁？InnoDB在此处的处理策略与前两种策略均不相同，或者说是前两种策略的组合：对于满足条件的删除记录，InnoDB会在记录上加next key lock X(对记录本身加X锁，同时锁住记录前的GAP，防止新的满足条件的记录插入。) Unique查询，三种情况，对应三种加锁策略，总结如下：
此处，我们看到了next key锁，是否很眼熟？对了，前面死锁中事务1，事务2处于等待状态的锁，均为next key锁。明白了这三个加锁策略，其实构造一定的并发场景，死锁的原因已经呼之欲出。但是，还有一个前提策略需要介绍，那就是InnoDB内部采用的死锁预防策略。找到满足条件的记录，并且记录有效，则对记录加X锁，No Gap锁(lock_mode X locks rec but not gap)；
找到满足条件的记录，但是记录无效(标识为删除的记录)，则对记录加next key锁(同时锁住记录本身，以及记录之前的Gap：lock_mode X);
未找到满足条件的记录，则对第一个不满足条件的记录加Gap锁，保证没有满足条件的记录插入(locks gap before rec)；
死锁预防策略
InnoDB引擎内部(或者说是所有的数据库内部)，有多种锁类型：事务锁(行锁、表锁)，Mutex(保护内部的共享变量操作)、RWLock(又称之为Latch，保护内部的页面读取与修改)。
InnoDB每个页面为16K，读取一个页面时，需要对页面加S锁，更新一个页面时，需要对页面加上X锁。任何情况下，操作一个页面，都会对页面加锁，页面锁加上之后，页面内存储的索引记录才不会被并发修改。
因此，为了修改一条记录，InnoDB内部如何处理：根据给定的查询条件，找到对应的记录所在页面；
对页面加上X锁(RWLock)，然后在页面内寻找满足条件的记录；
在持有页面锁的情况下，对满足条件的记录加事务锁(行锁：根据记录是否满足查询条件，记录是否已经被删除，分别对应于上面提到的3种加锁策略之一)；
死锁预防策略：相对于事务锁，页面锁是一个短期持有的锁，而事务锁(行锁、表锁)是长期持有的锁。因此，为了防止页面锁与事务锁之间产生死锁。InnoDB做了死锁预防的策略：持有事务锁(行锁、表锁)，可以等待获取页面锁；但反之，持有页面锁，不能等待持有事务锁。
根据死锁预防策略，在持有页面锁，加行锁的时候，如果行锁需要等待。则释放页面锁，然后等待行锁。此时，行锁获取没有任何锁保护，因此加上行锁之后，记录可能已经被并发修改。因此，此时要重新加回页面锁，重新判断记录的状态，重新在页面锁的保护下，对记录加锁。如果此时记录未被并发修改，那么第二次加锁能够很快完成，因为已经持有了相同模式的锁。但是，如果记录已经被并发修改，那么，就有可能导致本文前面提到的死锁问题。
以上的InnoDB死锁预防处理逻辑，对应的函数，是row0sel.c::row_search_for_mysql()。感兴趣的朋友，可以跟踪调试下这个函数的处理流程，很复杂，但是集中了InnoDB的精髓。
剖析死锁的成因
做了这么多铺垫，有了Delete操作的3种加锁逻辑、InnoDB的死锁预防策略等准备知识之后，再回过头来分析本文最初提到的死锁问题，就会手到拈来，事半而功倍。
首先，假设dltask中只有一条记录：(1, ‘a’, ‘b’, ‘c’, ‘data’)。三个并发事务，同时执行以下的这条SQL：
delete from dltask where a=’a’ and b=’b’ and c=’c’;
并且产生了以下的并发执行逻辑，就会产生死锁：
上面分析的这个并发流程，完整展现了死锁日志中的死锁产生的原因。其实，根据事务1步骤6，与事务0步骤3/4之间的顺序不同，死锁日志中还有可能产生另外一种情况，那就是事务1等待的锁模式为记录上的X锁 + No Gap锁(lock_mode X locks rec but not gap waiting)。这第二种情况，也是”润洁”同学给出的死锁用例中，使用MySQL 5.6.15版本测试出来的死锁产生的原因。
此类死锁，产生的几个前提：Delete操作，针对的是唯一索引上的等值查询的删除；(范围下的删除，也会产生死锁，但是死锁的场景，跟本文分析的场景，有所不同)
至少有3个(或以上)的并发删除操作；
并发删除操作，有可能删除到同一条记录，并且保证删除的记录一定存在；
事务的隔离级别设置为Repeatable Read，同时未设置innodb_locks_unsafe_for_binlog参数(此参数默认为FALSE)；(Read Committed隔离级别，由于不会加Gap锁，不会有next key，因此也不会产生死锁)
使用的是InnoDB存储引擎；(废话！MyISAM引擎根本就没有行锁)
最后
感谢大家看到这里，文章有不足，欢迎大家指出；如果你觉得写得不错，那就给我一个赞吧。
也欢迎大家关注我的公众号：程序员麦冬，麦冬每天都会分享java相关技术文章或行业资讯，欢迎大家关注和转发文章！

本文主要从共享锁(S锁)和独占锁(X锁)出发，详细说明两种锁的加锁机制，以及死锁如何产生。
问题:
什么是共享锁，什么是独占锁？
死锁怎么发生的？
发生死锁了，Mysql 如何处理的？
共享锁和独占锁
上一篇文章中我们已经讲解了共享锁和独占锁的基本概念，我这边再详细将一下。
共享锁 Shared Locks (S 锁)  从名字就可以看出来它允许共享，共享的意思是当你给某个事物加上锁后，其他人还可以为它加上(仅限)共享锁。
独占锁 Exclusive Locks (X 锁)， 如果想要修改某个事物，必须先加上X锁，但是如果该事物已经错在了S锁或者X锁就必须等已经存在的锁释放了才能再加上去。
S锁
X锁
S锁
兼容
不兼容
X锁
不兼容
不兼容
了解了S锁和X锁，那么我们来看看什么是死锁吧。
让我们来复现下死锁的过程，以便更好理解。建议可以根据自己理解来复现死锁过程，并分析原因加深理解。不然变成：
眼睛： 我会了。
脑子： 不，你不会。
准备工作
CREATE TABLE `student` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`age` int(11) NOT NULL,
`addresss` varchar(255) NOT NULL DEFAULT '',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
INSERT student VALUES (1,'张一',12,'ssss'),(2,'张二',12,'ssss'),(3,'张三',12,'ssss'),(4,'张四',12,'ssss'),(5,'张五',12,'ssss');
复制代码
准备工作完成，建立表，并插入5条数据。
模拟死锁第一步
新建一个数据库连接并执行：
###事务A
begin;
select * from student where id in (1,2) lock in share mode;
复制代码
步骤一 事务A 得到了id 为1，2的S锁。
再新建一个数据库连接并执行：
###事务B
begin;
select * from student where id in (1,3) lock in share mode;
复制代码
步骤二 这时事务B 得到了id为1，3的S锁
然后我们在事务B 中尝试获取数据id = 2 的X锁
事务B
update student set age  =100 where id = 2
复制代码
步骤三， 由于id为2 被事务A加了S锁，所以事务B 被阻塞。
最后我们在事务A中尝试获取数据id = 3 的X锁
事务A
update student set age  =100 where id = 3
#执行结果：1213 - Deadlock found when trying to get lock; try restarting transaction, Time: 0.005000s
复制代码
步骤四，由于id为3 被事务B加了S锁，所以事务A被阻塞。 当然其实执行的时候被跳出死锁警告。事务A回滚撤销了。
到此，我们模拟了整个死锁过程，由于B 为了获得X锁需要等A执行完成，而A后续反而为了获得X锁需要等B执行完成。所以造成了死锁。
死锁的原因
从上面的例子中我们可以看到死锁的原因是相互寻求各自手上的资源(即锁)导致的。
但是其中有个重要的特性需要说明就是二阶段锁协议。
二阶段锁协议很简单：
需要查询或者修改时才加锁。
事务提交的时候才释放锁。
上面例子中步骤三，B之所以会被阻塞，是因为事务A虽然读取数据结束了，但是事务还没结束，所以导致读取是加的锁没有释放。
也是由于二阶段锁协议的原因，所以我们应该尽可能避免长事务。因为`事务执行时间越长，加锁的时间越长，发生死锁的概率越大```
死锁如何处理
mysql 可以设置两种处理方式：
第一种就是上面例子锁展示的，发生死锁时，自动回滚其中一个事务，解除死锁。 可以通过innodb_deadlock_detect 参数设置为on 开启。默认情况下就是on 状态。
设置超时时间，也就是发生死锁时先等待一段时间后，再退出。可以设置innodb_lock_wait_timeout 设置超时时间。
一般情况下，我们会用第一种方式。
留个问题
现实场景中有哪些容易发生死锁的场景呢？其中最常见的一个例子是减库存了。
扣减库存我们一般有以下步骤
查看现有库存是否充足
库存充足则减去库存。 不足则返回扣除失败。
假设流程的sql语句如下
# 查询剩余库存
select last_number from stock where  id = 1000 lock in share mode;
#库存足够 --减去库存
update stock set last_number = last_number - 1 where id = 1000;
复制代码
那么问题是：
当并发比较高的时候，上面这个业务功能会不会发生死锁，分析下发生死锁的原因？
为什么要用lock in share mode 加锁，不加锁行不行？ 高并发下，如果不加锁会发生什么问题？
怎么修改才能不发生死锁，又能避免其他问题？
问题答案下篇文章回答。有收获，请关注下吧。

41.   map 在什么情况下会发生死锁；stl 中的 map 是怎么实现的？（有要参加淘宝面试的朋友注意，淘宝喜欢问 STL 方面的问题）
      如果面试官的本意是指map调用allocator死锁，理论上是可能的，allocator会调用libc的malloc等函数，malloc是线程安全的，但不是异步信号安全的，如果当前代码malloc在执行中，需要执行信号处理函数，而信号处理函数内部再次调用malloc，此时极有可能死锁！不过这弯子让太大了，而且和map的关系比较牵强，是脑筋急转弯吧，不算技术问题。。

    红黑树实现的，红黑树是一种自平衡二叉查找树。