为什么这个简单的事务会与 MySQL 发生死锁？

我在以下过程中遇到间歇性死锁：

DELIMITER $$
CREATE PROCEDURE pr_set_user_password (IN user_id INT, IN algorithm INT, IN hash VARBINARY(256))
BEGIN
    DECLARE EXIT HANDLER FOR SQLEXCEPTION 
    BEGIN
        ROLLBACK;
        RESIGNAL;
    END;

    START TRANSACTION;
        UPDATE `UserPassword` SET `Active` = 0 WHERE `UserId` = user_id;
        INSERT INTO `UserPassword` (`UserId`, `Active`, `Algorithm`, `Hash`) VALUES (user_id, 1, algorithm, hash);
COMMIT;
END $$
DELIMITER ;

UserId该表在和Active( IX_UserPassword_UserId_Active)上有一个复合索引。

有人试图运行一个并行创建许多用户的负载测试，并且他们非常一致地遇到了死锁。查看日志，我发现当此 proc 使用相邻user_id值运行时会发生死锁。

我真的在寻找一个真正的解释为什么这会导致死锁。我有各种混合和相互冲突的答案，没有一个是有意义的，从因为一个事务有锁而另一个锁无法获取它（即使只有一个锁有问题）到这就是 MySQL 的工作方式，处理它。

请参阅下面的死锁示例：

------------------------
LATEST DETECTED DEADLOCK
------------------------
2016-08-26 00:21:52 2b30caecc700
*** (1) TRANSACTION:
TRANSACTION 71925393848, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 5 lock struct(s), heap size 1184, 3 row lock(s), undo log entries 1
MySQL thread id 4901, OS thread handle 0x2b30cc1d7700, query id 37117819 <server> update
INSERT INTO `UserPassword` (`UserId`, `Active`, `Algorithm`, `Hash`) VALUES ( NAME_CONST('user_id',72332427), 1,  NAME_CONST('algorithm',2),  NAME_CONST('hash',_binary'<data>' COLLATE 'binary'))
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 388 page no 117300 n bits 784 index `IX_UserPassword_UserId_Active` of table `users`.`UserPassword` trx id 71925393848 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 714 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 844fb48c; asc  O  ;;
 1: len 1; hex 81; asc  ;;
 2: len 4; hex 818106f9; asc     ;;

*** (2) TRANSACTION:
TRANSACTION 71925393846, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
6 lock struct(s), heap size 1184, 4 row lock(s), undo log entries 1
MySQL thread id 4909, OS thread handle 0x2b30caecc700, query id 37117815 <server> update
INSERT INTO `UserPassword` (`UserId`, `Active`, `Algorithm`, `Hash`) VALUES ( NAME_CONST('user_id',72332426), 1,  NAME_CONST('algorithm',2),  NAME_CONST('hash',_binary'<data>' COLLATE 'binary'))
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 388 page no 117300 n bits 784 index `IX_UserPassword_UserId_Active` of table `users`.`UserPassword` trx id 71925393846 lock_mode X locks gap before rec
Record lock, heap no 714 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 844fb48c; asc  O  ;;
 1: len 1; hex 81; asc  ;;
 2: len 4; hex 818106f9; asc     ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 388 page no 117300 n bits 784 index `IX_UserPassword_UserId_Active` of table `users`.`UserPassword` trx id 71925393846 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 714 PHYSICAL RECORD: n_fields 3; compact format; info bits 0
 0: len 4; hex 844fb48c; asc  O  ;;
 1: len 1; hex 81; asc  ;;
 2: len 4; hex 818106f9; asc     ;;

*** WE ROLL BACK TRANSACTION (1)