MySQL Bugs: #99138: Gap locking behavior leads to unavoidable deadlocks

Bug #99138	Gap locking behavior leads to unavoidable deadlocks
Submitted:	1 Apr 2020 4:35	Modified:	14 Apr 2020 18:37
Reporter:	Nicholas Gaya	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S4 (Feature request)
Version:	8.0.19	OS:	Linux
Assigned to:		CPU Architecture:	x86

Description:
If two clients try to perform a SELECT ... FOR UPDATE or DELETE operation followed by INSERT on a table with an indexed column, deadlocks can easily occur when multiple clients acquire a gap lock for the same range and then try to insert into the gap.

The documentation has this note:

> Gap locks in InnoDB are “purely inhibitive”, which means that their only purpose is to prevent other transactions from inserting to the gap. Gap locks can co-exist. A gap lock taken by one transaction does not prevent another transaction from taking a gap lock on the same gap. There is no difference between shared and exclusive gap locks. They do not conflict with each other, and they perform the same function.

So, this is the "expected" behavior but from a user standpoint it's still a problem.  Is there really no way to prevent deadlocks in this situation without locking the entire table?

References:
* https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html

Related:
* https://bugs.mysql.com/bug.php?id=20134
* https://bugs.mysql.com/bug.php?id=25847

How to repeat:
Create an example table with an indexed column.

CREATE TABLE `User` (
  `id` int DEFAULT NULL,
  KEY `id` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci

Open an interactive database session in two terminals, T1 and T2.  Enter the following commands in T1:

mysql> START TRANSACTION;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT * FROM User WHERE id = 1 FOR UPDATE;
Empty set (0.00 sec)

Switch to T2 and enter the following commands:

mysql> START TRANSACTION;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT * FROM User WHERE id = 2 FOR UPDATE;
Empty set (0.00 sec)

mysql> INSERT INTO User (id) values (2);

The last command will hang.  Switch back to T1:

mysql> INSERT INTO User (id) values (1);
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

Deadlock information from innodb status:
------------------------
LATEST DETECTED DEADLOCK
------------------------
2020-04-01 00:41:43 0x7f9737cf1700
*** (1) TRANSACTION:
TRANSACTION 2066, ACTIVE 21 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 9, OS thread handle 140287793612544, query id 21 localhost root update
INSERT INTO User (id) VALUES (2)

*** (1) HOLDS THE LOCK(S):
RECORD LOCKS space id 2 page no 5 n bits 72 index id of table `db`.`User` trx id 2066 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
 0: len 8; hex 73757072656d756d; asc supremum;;

*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 2 page no 5 n bits 72 index id of table `db`.`User` trx id 2066 lock_mode X insert intention waiting
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
 0: len 8; hex 73757072656d756d; asc supremum;;

*** (2) TRANSACTION:
TRANSACTION 2065, ACTIVE 38 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 3 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 8, OS thread handle 140287793907456, query id 22 localhost root update
INSERT INTO User (id) VALUES (1)

*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 2 page no 5 n bits 72 index id of table `db`.`User` trx id 2065 lock_mode X
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
 0: len 8; hex 73757072656d756d; asc supremum;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 2 page no 5 n bits 72 index id of table `db`.`User` trx id 2065 lock_mode X insert intention waiting
Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0
 0: len 8; hex 73757072656d756d; asc supremum;;

MySQL distribution: Docker mysql 8.0.19 https://hub.docker.com/_/mysql

OS information: Linux 56def4f9635c 5.3.0-42-generic #34~18.04.1-Ubuntu SMP Fri Feb 28 13:42:26 UTC 2020 x86_64 GNU/Linux

Suggested fix:
Provide a way to acquire an exclusive gap lock in a transaction or otherwise prevent deadlocks in this scenario.

Hi Mr. Gava,

Thank you for your feature request.

However, I do not think that we can accommodate your request. The manner in which InnoDB storage engine works is based on the best solutions presented by numerous authors who have been building transactional processing for the ACID storage engines.

This is the way that InnoDB SE functions since 2001, without changes. This is the only way which ensures the integrity of each table.

Also, we can not force exclusivity on the gap locks, since that would lead to significant performance degradation.

Last, but not least, what you have designed is a classical case where a transactional engine creates a deadlock. If you get a deadlock error, that means that InnoDB SE functions properly and exactly as desired and as it is designed. All you have to do is to re-submit transactions in questions from your application.

So, in short, unfortunately, this feature request can not be implemented.

Hi Sinisa,

Thanks for your comment. Just because this is an old problem, doesn't mean it's impossible to fix. Looking through the bug tracker (see links at end) shows that this a common issue encountered by users so there is real value in finding a solution.

> Also, we can not force exclusivity on the gap locks, since that would lead to significant performance degradation.

What about giving the user the option to decide?  For example you could add a "LOCK EXCLUSIVE" keyword for "SELECT ... FOR UPDATE" queries to indicate that the user wishes to acquire an exclusive lock.

Examples:

* https://bugs.mysql.com/bug.php?id=14647
* https://bugs.mysql.com/bug.php?id=20134
* https://bugs.mysql.com/bug.php?id=25847
* https://bugs.mysql.com/bug.php?id=43211
* https://bugs.mysql.com/bug.php?id=48911
* https://bugs.mysql.com/bug.php?id=95230
* https://bugs.mysql.com/bug.php?id=96748

Hi Mr. Gaya,

I truly do not think that adding such a command is a good idea. We try to follow SQL standard as much as possible, and this does not comply with standards.

Another solution would be to add (yet) another global/session variable. However, this is not a good idea either. There are already too many of those, plus, your test case would also produce a deadlock with exclusive gap locks.

Can you clarify why there would be a deadlock in the example with exclusive gap locking?  I would expect the behavior to be:

* T1 acquires an exclusive gap lock and successfully inserts a row.
* T2 blocks on SELECT ... FOR UPDATE until T1 is complete, then proceeds with no issues.

Hi Mr. Gaya,

The reply is very simple.

Even with current non-exclusive gap locks, you managed to produce a classical deadlock. Test that you submitted produced a  deadlock with a record lock and a gap lock, which two concurrent threads issued in the opposite order. 

Hence, with exclusive gap locks, number of semaphore waits and deadlocks would have been much higher. That change would have produced a very high number of the regression bugs.

> Test that you submitted produced a  deadlock with a record lock and a gap lock, which two concurrent threads issued in the opposite order. 

This is incorrect.  Both transactions perform the same operations in the same order, with different id values.  Therefore no deadlock should occur with exclusive locking.

Deadlock still occurred. Hence ,with exclusive locking it would occur more frequently, in many different scenarios then yours.