Mysql – Why does this simple transaction deadlock with MySQL

I'm encountering intermittent deadlocks in the following proc:

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 ;

This table has a composite index on UserId and Active (IX_UserPassword_UserId_Active).

Someone tried to run a load test that created many users in parallel, and they encountered the deadlock very consistently. Looking at the logs, I see that the deadlock occurs when this proc runs with adjacent user_id values.

I'm really looking for a real explanation of why this results in a deadlock. I've had various mixed and conflicting answers, none of which make sense, ranging from because one transaction has the lock and the other lock can't acquire it (even though there's only one lock in question) to that's just how MySQL works, deal with it.

See an example of the deadlock below:

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