表锁相关结构：
table->locks：数据字典table保存这个表上的所有表锁信息
trx->lock.table_locks：每个事务trx保存该事务所加的所有表锁信息
trx->lock.trx_locks：每个事务trx保存该事务所有的锁信息（包括行锁）
表锁类型：
IS IX S X AI
AI：Auto-Increment Lock 也是表级的，语句结束后释放而不事事务结束后释放
http://dev.mysql.com/doc/refman/5.5/en/innodb-auto-increment-handling.html
lock_table 加锁流程
1 先从 trx->lock.table_locks 查找该事务是否已加对该表加锁，如果所加的锁比要加的锁strong,则返回成功。其它情况进入2
2 从 table->locks中查找该表是否被其他事务加锁。如果没有加锁进入3，如果已加锁进入4
3 新建表锁，返回加锁成功
4 此时需判断欲加的锁是否与已加的锁兼容。如果兼容进入5，否则进入6
5 新建表锁，返回加锁成功
6 新建表锁，加入等待队列，其中会穿插死锁检测流程。
新建表锁会将新建的锁放入table->locks，trx->lock.table_locks，trx->lock.trx_locks中。
?
附锁兼容矩阵和锁
/* LOCK
COMPATIBILITY MATRIX
*
IS IX S X AI
*
IS + + + - +
*
IX + + - - +
*
S + - + - -
*
X - - - - -
*
AI + + - - -
锁强度比较矩阵
/* STRONGER-OR-EQUAL RELATION (mode1=row, mode2=column)
* IS IX S
X AI
*
IS + - - - -
*
IX + + - - -
*
S + - + - -
*
X + + + + +
*
AI - - - - +
*
See lock_mode_stronger_or_eq().
*/
记录锁
记录锁的存储单位为页，一个事务在一个页上的所有同类型锁存储为一个lock,lock中通过bitmap来表示那些记录已加锁
行锁类型：行锁类型由基本类型和精确类型组成
行锁基本类型：
LOCK_S,LOCK_X
行锁精确类型：
LOCK_ORDINARY(NK)：next-key lock 既锁记录也锁记录前的gap
LOCK_GAP(GAP)：不锁记录，只锁记录前的gap
LOCK_REC_NOT_GAP(NG):只锁记录，不锁记录前的gap
LOCK_INSERT_INTENTION(I)：insert时，若insert位置已有gap锁，则需加LOCK_INSERT_INTENTION锁
相关结构：
trx->lock.trx_locks：每个事务trx保存该事务所有的锁信息（表锁和行锁）
lock_sys->rec_hash：保存所有事务的行锁信息
给记录加S锁之前必会给表加IS锁
给记录加X锁之前必会给表加IX锁
lock_rec_lock流程
分为两个阶段快加锁和慢加锁阶段，设记录所在的页为p
1 快加锁阶段：
1.1 在 lock_sys->rec_hash中查找P的所有锁，如果没有锁，则新建锁返回成功；否则进入1.2
1.2 如果查找到只有一个锁，且该所在的事务是当前事务，锁类型也相同，则进入1.3，否则，进入第二阶段快加锁阶段
1.3 如将该记录已加锁，则返回加锁成功。否则进入1.4
1.4 将该记录在lock的bitmap的位置为已加锁。返回成功。
2 慢加锁阶段
2.1 在lock_sys->rec_hash中遍历查找当前事务对此记录所加的锁，如果已有锁比欲加的锁strong(见lock_rec_has_expl)，则进入2.2，否则进入2.3。
2.2. 如果已有锁状态为wait，则当前事务进入等待。否则直接返回加锁成功。
2.3 在lock_sys->rec_hash中遍历查找对此记录所加的锁 ，如果所在的事务是其他事务且锁不兼容则进入等待，否则进入2.4
2.4 如是隐式加锁，则返回成功，否则进入2.5
2.5 如果当前记录已有锁等待（？），或当前事务没有同类型的锁设置bitmap位，则新建锁返回成功（见lock_rec_add_to_queue） ，否则进入2.6
2.6 在当前事务同类型的锁上设置bitmap位，返回成功
可见慢加锁阶段可能会两次遍历lock_sys->rec_hash的哈希桶。
行锁的兼容和锁比较没有表锁那么简单，是由于引入行锁精确类型导致的。
兼容性有以下原则
1 Gap type locks without LOCK_INSERT_INTENTION flag do not need to wait for anything. This is because different users can have conflicting lock types on gaps
2 Record lock (LOCK_ORDINARY or LOCK_REC_NOT_GAP does not need to wait for a gap type lock
3 Lock on gap does not need to wait for a LOCK_REC_NOT_GAP type lock
4 No lock request needs to wait for an insertintention lock to be removed.
可以推出以下锁兼容矩阵
GAP I NG NK
GAP + + + +
I +
NG + +
NK + +
对于锁强度比较可以参考lock_rec_has_expl，对于SUPREMUM记录的处理比较特殊。
锁强度矩阵（strong or equ)
GAP I NG NK
GAP - -
I -
NG - -
NK -
而对于SUPREMUM记录NG和G是+。
关于 lock的bitmap，当记录发生移动和page发生分裂和合并时都需要维护bitmap信息，参见lock_rec_move lock_update_merge_right
死锁检测
死锁检测发生在锁等待时，参见lock_deadlock_check_and_resolve。表锁和记录锁的检测逻辑是一样的。
采用等待图法，事务是图的节点，事务与该事务所等待的锁所在的事务的连线构成线，如果发现图中存在回路，则表示系统中出现了死锁。innodb采用图的深度优先的非递归算法实现的。非递归采用栈来记录节点的访问轨迹。lock->trx->lock.deadlock_mark和 ctx->mark_start来判断节点是否已访问过。
死锁检测有三种结果：
1 检查过程中搜索节点过深（>200)或访问的节点数过多（>1000000),或栈节点数超过srv_max_n_threads（？），则停止搜索，实际上就是认为产生了死锁。而不是采用超时的方法。此时将欲加的锁的事务做为牺牲者。
2 检测到死锁，这是需要选择牺牲者。在当前事务和等待的锁事务中选择，原则是牺牲undo和持有锁较少的事务。（trx_weight_ge）
作为牺牲者的事务会回滚，从而释放锁持有的锁，从而断开了环路，解决了死锁。
锁的释放
事务提交和回滚是会释放锁
另为自增锁在语句结束时释放lock_unlock_table_autoinc