Why does this simple transaction deadlock with MySQL?

Question

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)

Answer 1

I'd say it's an illustration on how gap locks work -http://dev.mysql.com/doc/refman/5.7/en/innodb-locking.html#innodb-gap-locks .

Say you have adjacent user id , 1 and 2. When procedure executed simultaneously from 2 different sessions, each of them put a gap lock on two index-records (with user_id values 1 and 2 - maybe 0 ,4,5 as well ,but let's assume just 2 for simplicity sake), and each of them has to wait for another one to release the lock to perform an insert.

Gap locks in InnoDB are “purely inhibitive”, which means they only stop other transactions from inserting to the gap. They do not prevent different transactions from taking gap locks on the same gap. Thus, a gap X-lock has the same effect as a gap S-lock *."

To disable locks,

Gap locking can be disabled explicitly. This occurs if you change the transaction isolation level to READ COMMITTED or enable the innodb_locks_unsafe_for_binlog system variable (which is now deprecated). Under these circumstances, gap locking is disabled for searches and index scans and is used only for foreign-key constraint checking and duplicate-key checking.

Using READ COMMITTED sounds like a reasonable solution to me, assuming it doesn't break application logic.