Why do these concurrent MySQL inserts deadlock?

Question

I am baffled by this deadlock:

------------------------
LATEST DETECTED DEADLOCK
------------------------
150511 18:42:43
*** (1) TRANSACTION:
TRANSACTION B8972CA4, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1248, 2 row lock(s), undo log entries 1
MySQL thread id 55103359, OS thread handle 0x7f6babefb700, query id 18803072369 db.example.com 127.0.0.1 application update
INSERT INTO users ( created_at, external_record_type, external_id, email ) VALUES ( '2015-05-11 18:42:43', 'person', '212999172', '[email protected]' )
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 18 page no 1103450 n bits 320 index `index_users_on_external_record_type_and_external_id` of table `users`.`users` trx id B8972CA4 lock_mode X locks gap before rec insert intention waiting
*** (2) TRANSACTION:
TRANSACTION B8972CA5, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
3 lock struct(s), heap size 1248, 2 row lock(s), undo log entries 1
MySQL thread id 55103302, OS thread handle 0x7f6bf2320700, query id 18803072370 db.example.com 127.0.0.1 application update
INSERT INTO users ( created_at, external_record_type, external_id, email ) VALUES ( '2015-05-11 18:42:43', 'person', '212999170', '[email protected]' )
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 18 page no 1103450 n bits 320 index `index_users_on_external_record_type_and_external_id` of table `users`.`users` trx id B8972CA5 lock_mode X locks gap before rec
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 18 page no 1103450 n bits 320 index `index_users_on_external_record_type_and_external_id` of table `users`.`users` trx id B8972CA5 lock_mode X locks gap before rec insert intention waiting
*** WE ROLL BACK TRANSACTION (2)

The schema:

CREATE TABLE users
(id int NOT NULL AUTO_INCREMENT,
 external_id varchar(255) NOT NULL,
 external_record_type varchar(255) NOT NULL,
 email varchar(255) NOT NULL,
 created_at datetime DEFAULT NULL,
 PRIMARY KEY(id),
 UNIQUE KEY index_users_on_external_record_type_and_external_id (external_record_type(8), external_id),
 KEY index_users_on_email (email))

I see that T1 and T2 both want the insert intention gap lock on the same gap, but I don't see why the transactions can't proceed sequentially. Moreover, I don't see why T2 acquires a non-insert-intention lock on the gap before trying for the insert-intention lock.

I'm using MySQL 5.5 of the Percona flavor.

Answer 1

I failed to understand the extent of the transactions.

Before I do the INSERT, I do a write-locking select on the external index value in both transactions. I would have expected T2 to block T1 at that point, but that is not the case, both transactions successfully acquire a lock on the gap. Neither transaction can promote its lock to insert intention; T1 will block when it tries, then T2 will deadlock when it tries, thereby letting T1 succeed.

The behavior I found, and continue to find surprising, is that write locks on index gap values aren't exclusive. While that's certainly a correct way to implement serializability, it carries an attendant risk of deadlock that you would forego if write locks on gap values were exclusive as they are for record values. I wonder if I continue to miss something fundamental.