MySQL Bugs: #114446: A deadlock example cause by lock inherit

Bug #114446	A deadlock example cause by lock inherit
Submitted:	21 Mar 14:30	Modified:	21 Mar 16:42
Reporter:	Zongzhi Chen (OCA)	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S3 (Non-critical)
Version:	8.0.*	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	deadlock, innodb

Description:
In our user environment, we find deadlock cause by this example.

However, in this case, sometimes session 2 and session 3 lead to dead lock and sometimes it won't.

```mysql
create table t(a int AUTO_INCREMENT, b int, PRIMARY KEY (a));
insert into t(a, b) values(10, 8);
insert into t(a, b) values(5, 8); 

session 1: begin; delete from t where a=5;
session 2: insert into t(a, b) values (5, 8) on duplicate key update b = 11;
session 3: insert into t(a, b) values (5, 8) on duplicate key update b = 11;

session 1: commit;

# Then sometimes session 2 and session 3 lead to dead lock and sometimes it won't.
```

I find the root cause is lock inherit cause the deadlock.

In session 1 get the record 5 X, REC_NOT_GAP lock.

Then session 2 waiting in the record 5 X, REC_NOT_GAP lock.

And session 3 waiting in the record 5 X, REC_NOT_GAP lock.

```mysql
+-----------+------------+-----------+---------------+-------------+-----------+
| thread_id | index_name | lock_type | lock_mode     | LOCK_STATUS | lock_data |
+-----------+------------+-----------+---------------+-------------+-----------+
|       148 | PRIMARY    | RECORD    | X,REC_NOT_GAP | WAITING     | 5         |
|       150 | PRIMARY    | RECORD    | X,REC_NOT_GAP | WAITING     | 5         |
|       146 | PRIMARY    | RECORD    | X,REC_NOT_GAP | GRANTED     | 5         |
+-----------+------------+-----------+---------------+-------------+-----------+
```

Then when session 1 execute commit, there is two scenario:

Whether the record 5 was purged after session 1 commit and before session 2 and session 3 was executing.

If the record was not purged, the record 5 won't be physical deleted, then only one session, session2 or session 3 will get the 5 X, REC_NOT_GAP lock, then the session 2 and session 3 doing the insert one by one.

This scenario will not cause deadlock.

If the record was purged, the record 5 was physical deleted, then the waiting records will inherit to next record. Then session 2 and session 3 will wait for record 10, X GAP lock. Then session 2 and session 3 will both get the record 10, X GAP lock. Then they will doing the insert work, both sessions hold the X GAP lock and waiting other's X,GAP,INSERT_INTENTION lock. Then deadlock happend.

Get the lock information by adding a breakpoint before deadlock check.

```mysql
+-----------+------------+-----------+------------------------+--------------+-----------+
| thread_id | index_name | lock_type | lock_mode              | LOCK_STATUS  | lock_data |
+-----------+------------+-----------+------------------------+--------------+-----------+
|       148 | PRIMARY    | RECORD    | X,GAP                  | GRANTED      | 10        |
|       148 | PRIMARY    | RECORD    | X,GAP,INSERT_INTENTION | WAITING      | 10        |
|       150 | PRIMARY    | RECORD    | X,GAP                  | GRANTED      | 10        |
|       150 | PRIMARY    | RECORD    | X,GAP,INSERT_INTENTION | WAITING      | 10        |
+-----------+------------+-----------+------------------------+--------------+-----------+
```

The default behaviour of lock inherit is Let the next record's GAP lock inherit the record's REC_NOT_GAP lock.

However, in this case, the X REC_NOT_GAP lock is conflict with X REC_NOT_GAP lock, after the inherit, X REC_NOT_GAP lock inherit to next record's X GAP lock. The X GAP lock won't conflict with X GAP lock. Then two sessions both get the X GAP lock, then the deadlock happened.

I suggest in X REC_NOT_GAP lock inherit case, let the next record inherit the NEXT-KEY lock, then in this case NEXT_KEY lock conflict with NEXT_KEY lock, the deadlock won't happened.

How to repeat:
```mysql
create table t(a int AUTO_INCREMENT, b int, PRIMARY KEY (a));
insert into t(a, b) values(10, 8);
insert into t(a, b) values(5, 8); 

session 1: begin; delete from t where a=5;
session 2: insert into t(a, b) values (5, 8) on duplicate key update b = 11;
session 3: insert into t(a, b) values (5, 8) on duplicate key update b = 11;

session 1: commit;

# Then sometimes session 2 and session 3 lead to dead lock and sometimes it won't.
```

running this example

Suggested fix:
I suggest in X REC_NOT_GAP lock inherit case, let the next record inherit the NEXT-KEY lock, then in this case NEXT_KEY lock conflict with NEXT_KEY lock, the deadlock won't happened.

Hi Mr. Chen,

Thank you for your bug report.

However, deadlocks are not bugs. Detecting and acting on deadlocks are a proof that InnoDB storage engine is working perfectly, according the transaction processing standards.

Also, we do not see how we can change lock type. Locks with gaps, locks with no gaps, insert intention locks, next-key locks and others are performed exactly as the standard prescribes them. Changing the manner of granting locks and inheritance of the locks, will definitely lead to the breaking of both MVCC and ACID standards. It would lead to a far greater number of bugs and some hard problems in the production.

Once again, discovering deadlocks is a feature and not a bug.

Ok, get it. Discovering deadlocks is a feature and not a bug.

I want discuss the topic is lock inherit may change the lock behavior.
Such as in this case before the lock inherit the two X,REC_NOT_GAP locks is conflict, after lock inherit the two X,GAP locks is not conflict.

The lock inherit should take into account this case, it should review the inherit strategy, should next record lock inherit from previous X,REC_NOT_GAP be X, NEXT_KEY or X, GAP?

Hi,

We would just like to inform you that your idea would bring some improvements in some areas, but many other problems in other areas. Due to the vast complexity of the transaction code , there would be a number of regression bugs.

However, we would like to inform you that we have some ideas of our own, which will reduce some semaphore waits and deadlocks. However, those will be implemented in the future and in a very slow and careful manner.

We already changed the standard, by removing lock waits and deadlocks due to the escalation of the locks.

Hence, this is a slow, but ongoing process. Your idea will not be forgotten and may form a part of some new WorkLog entry.

No matter how much I try, a deadlock does not occur. Is it correct that I can physically delete a record while a transaction is open?

Hi,

Yes, you can delete a row within a transaction, or in another concurrent transaction. The results will depend on the isolation level that you are using, as explained here:

 https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html