Bug #36045 Unexpected deadlock between concurrent REPLACEs
Submitted: 14 Apr 2008 4:40 Modified: 13 May 2010 16:12
Reporter: Yasufumi Kinoshita Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S4 (Feature request)
Version:5.0.56 OS:Any
Assigned to: Assigned Account CPU Architecture:Any
Triage: Triaged: D5 (Feature request)

[14 Apr 2008 4:40] Yasufumi Kinoshita
Description:
Using InnoDB, a rollback of the one of concurrent REPLACEs causes a deadlock of the others when the record didn't exist before.
(innodb_locks_unsafe_for_binlog=false)

lock_rec_inherit_to_gap() seems to create strange situation.
(All of the related transactions have X-lock of the same gap-lock at the same time...)
But, the arbitrators seem not to be conscious of the situation.
(e.g. lock_rec_other_has_conflicting(), lock_rec_has_to_wait_in_queue(), lock_table_has_to_wait_in_queue(), lock_deadlock_recursive())

How to repeat:
Preparations:

create table locktest (c char(1) primary key) engine=InnoDB;
insert into locktest values ('1');

Operations:

TRX1> set autocommit=0;
TRX1> replace into locktest values ('1');

TRX2> set autocommit=0;
TRX2> replace into locktest values ('1');
(Waiting)

TRX3> set autocommit=0;
TRX3> replace into locktest values ('1');
(Waiting)

TRX1> rollback;

(Deadlock between TRX2 and TRX3 occurs.)

<*Transitions of the locks at the rollback>

- Before rollback
    record  : 1-X 2-X(Wait) 3-X(Wait)
    supremum:

- at lock_rec_inherit_to_gap()
    record  : 1-X 2-X(Wait) 3-X(Wait)
    supremum: 1-X(Gap) 2-X(Gap) 3-X(Gap)

- at lock_rec_reset_and_release_wait()
    record  : 1-X(reset)
    supremum: 1-X(Gap) 2-X(Gap) 3-X(Gap)

TRX2&3 wake up.

(*TRX1&2&3 have X-lock at the same time...)

- end of TRX1's rollback
    record  :
    supremum: 2-X(Gap) 3-X(Gap)

- TRX2&3 want insert intentional X-lock
    record  :
    supremum: 2-X(Gap) 3-X(Gap) 2-X(Gap:Wait) 3-X(Gap:Wait)

Deadlock!!

Suggested fix:
A lock has not to wait if the lock as following exists ahead.
 (   the owner is the same transaction
  && isn't LOCK_WAIT
  && is same lock modes. ([S|X] [GAP|not GAP] etc..)
  && doesn't has to wait for other locks
 )
[14 Apr 2008 4:42] Yasufumi Kinoshita
Sorry,, I've mistook...

How to repeat:

Preparations:

create table locktest (c char(1) primary key) engine=InnoDB;

Operations:

TRX1> set autocommit=0;
TRX1> replace into locktest values ('1');

TRX2> set autocommit=0;
TRX2> replace into locktest values ('1');
(Waiting)

TRX3> set autocommit=0;
TRX3> replace into locktest values ('1');
(Waiting)

TRX1> rollback;

(Deadlock between TRX2 and TRX3 occurs.)
[24 Apr 2008 11:04] Susanne Ebrecht
Verified as described with 5.1 bk tree.

ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
[24 Jun 2008 16:38] Heikki Tuuri
Hmm... the problem here is how do we know that TRX 2 IS allowed to re-insert record (1) which disappeared in the rollback of TRX 1. When record (1) is removed, the 'gap' (== the 'supremum' record on the page) inherits the waiting X-lock requests on (1).

"
Suggested fix:
A lock has not to wait if the lock as following exists ahead.
 (   the owner is the same transaction
  && isn't LOCK_WAIT
  && is same lock modes. ([S|X] [GAP|not GAP] etc..)
  && doesn't has to wait for other locks
 )
"

The suggested fix above might not work for the following reason:

In InnoDB, two transactions are allowed to have conflicting locks on a 'gap'. For example, TRX 2 and TRX 3 have both an X-lock on the 'supremum'. TRX 2 cannot do the insert of (1) because that would conflict with the gap lock of TRX 3. And vice versa. That is the deadlock.

Another way to avoid the deadlock here would be to change the lock 'inheritance' rules of a gap. If a record is removed from the index, is it really necessary that the gap inherits the waiting lock requests on the record in some form?

I am marking this as a feature request: how to relax InnoDB's gap locking without destroying the serializability of DML on the level REPEATABLE READ?