MySQL Bugs: #35821: Unexpected deadlock between concurrent INSERTs when unique key violation may occ

Bug #35821	Unexpected deadlock between concurrent INSERTs when unique key violation may occ
Submitted:	4 Apr 2008 3:54	Modified:	9 Mar 2009 17:47
Reporter:	Yasufumi Kinoshita	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Documentation	Severity:	S4 (Feature request)
Version:	5.0.56	OS:	Any
Assigned to:	Paul DuBois	CPU Architecture:	Any

Description:
In InnoDB, INSERT sets a S-lock on the record first when unique key violation may occur, and sets a X-lock next while inserting record.
So, some INSERTs on same key which have waited for commit of DELETE on the same key always cause deadlock.
This deadlock seems not to be related to the next-key locking or the isolation.

Why the S-locks are necessary in the following case?
There are no secondary indexes.
Is the case simple enough not to need the such S-locks?

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> delete from locktest where c='1';

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

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

TRX1> commit;

(Deadlock between TRX2 and TRX3 occurs.)

Suggested fix:
Not to set such a S-lock if unnecessary.
(row0ins.c: row_ins_duplicate_error_in_clust() )

Thank you for a problem report.

As current behaviour is documented at http://dev.mysql.com/doc/refman/5.0/en/innodb-locks-set.html, we can speak about new feature request here. 

Now, please, explain how INSERT in TRX2:

TRX2> insert into locktest values ('1');

(or in TRX3) can determine that s-lock is not needed?

This is not a new feature, but isn't documented at http://dev.mysql.com/doc/refman/5.0/en/innodb-locks-set.html

At this case, each INSERT sets lock on the same record twice.
The first is S-lock, the second is X-lock.
(innobase/row/row0ins.c: row_ins_duplicate_error_in_clust() sets the S-lock)

I think the valid result may be
TRX2: success to INSERT
TRX3: waiting for TRX2 end

But current behavior is
TRX2: deadlock
TRX3: success
or
TRX2: success
TRX3: deadlock

Even if the S-lock is needed, can we make the deadlock not occur?

Yasufumi,

the S-lock on the duplicate key value record is needed, because when InnoDB returns the 'Duplicate key error' to the user, the user gets information of the database state: there exists a duplicate key record. In two-phase locking, whatever information we return to the user, the corresponding data set must be locked. That is to guarantee serializability.

Why InnoDB only takes an SHARED lock on the duplicate key, because an X-lock would be overkill: normally, the duplicate key record will stay there. Why would we block readers from accessing it? We do not want to block them, that is why we set an S-lock.

The case where the duplicate key gets deleted, and there are TWO or more inserters waiting for to insert the duplicate value is not common. In theory, we could allow the first inserter to bypass the S-lock set by other inserters. But I doubt such optimization is worth the effort.

Regards,

Heikki

Heikki,

Thank you for your kind explanation.
I've understood. And I also think the optimization isn't so worth the effort..

However, I cannot force my customers to be conscious of the undocumented behavior.

Could the behavior be added to the manual?

Regards,

Yasufumi

I think additional clarification and example in the manual will be really useful.

Paul, I think the manual already mentions that InnoDB sets an S-lock on the duplicate record.

Thank you for your bug report. This issue has been addressed in the documentation. The updated documentation will appear on our website shortly, and will be included in the next release of the relevant products.

Added to http://dev.mysql.com/doc/refman/5.1/en/innodb-locks-set.html under description of INSERT INTO ... VALUES():

INSERT INTO ... VALUES (...) sets an exclusive lock on the inserted
row. This lock is not a next-key lock and does not prevent other
sessions from inserting into the gap before the inserted row. If a
duplicate-key error occurs, a shared lock on the duplicate index
record is set. 

This use of a shared lock can result in deadlock should there be
multiple sessions trying to insert the same row if another session 
already has an exclusive lock. This can occur if another session
deletes the row. Suppose that an InnoDB table t1 has the following
structure and contents:

CREATE TABLE t1 (i INT, PRIMARY KEY (i)) ENGINE = InnoDB;
INSERT INTO t1 VALUES(1);

Now suppose that three sessions perform the following operations in
order:    

Session 1: 

START TRANSACTION;
DELETE FROM t1 WHERE i = 1;

Session 2: 

START TRANSACTION;
INSERT INTO t1 VALUES(1);

Session 3: 

START TRANSACTION;
INSERT INTO t1 VALUES(1);

Session 1: 

COMMIT;

The first operation by session 1 acquires an exclusive lock for the 
row. The operations by sessions 2 and 3 both result in a
duplicate-key error and they both acquire a shared lock for the row. 
When session 1 commits, it releases the exclusive lock on the row. At
this point, sessions 2 and 3 deadlock: Neither can acquire an
exclusive lock for the row because of the shared lock held by the
other.

See also Bug#43210.