Por que esse impasse de transação simples com o MySQL?

Estou encontrando deadlocks intermitentes no seguinte procedimento:

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 ;

Esta tabela possui um índice composto em UserIde Active( IX_UserPassword_UserId_Active).

Alguém tentou executar um teste de carga que criou muitos usuários em paralelo e encontrou o impasse de forma muito consistente. Olhando os logs, vejo que o impasse ocorre quando esta proc roda com user_idvalores adjacentes.

Estou realmente procurando uma explicação real de por que isso resulta em um impasse. Eu tive várias respostas confusas e conflitantes, nenhuma das quais faz sentido, variando de porque uma transação tem o bloqueio e o outro bloqueio não pode adquiri-lo (mesmo que haja apenas um bloqueio em questão) para que seja assim que o MySQL funciona, lidar com isso .

Veja um exemplo de impasse abaixo:

------------------------
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)