Bug #43210 Deadlock detected on concurrent insert into same table (InnoDB)
Submitted: 26 Feb 2009 7:08 Modified: 29 Apr 2009 19:47
Reporter: Royce Lithgo Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Documentation Severity:S2 (Serious)
Version:5.0.51a-community-log, 5.0.74 OS:Linux
Assigned to: Paul DuBois CPU Architecture:Any

[26 Feb 2009 7:08] Royce Lithgo
Description:
I have three transactions all inserting into the same table. If they insert in sequence and the first one issues rollback, the third one fails with deadlock error.

How to repeat:
My table DDL:

CREATE TABLE `ns_custom_app_transaction_lock` (
  `custom_app_id` int(11) NOT NULL default '0',
  `transaction_key` varchar(100) collate utf8_bin NOT NULL default '',
  PRIMARY KEY  (`custom_app_id`,`transaction_key`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin;

The following scenario results in Deadlock detection of Tran C. Why is this so?

Tran A:
start transaction;

Tran B:
start transaction;

Tran C:
start transaction;

Tran A:
insert into ns_custom_app_transaction_lock
values(1,'abc123');

Tran B:
insert into ns_custom_app_transaction_lock
values(1,'abc123');   
[ BLOCKED ]

Tran C:
insert into ns_custom_app_transaction_lock
values(1,'abc123');   
[ BLOCKED ]

Tran A:
rollback;

At this point Tran B unblocks, but Tran C fails with error:
1213 - Deadlock found when trying to get lock; try restarting transaction
[26 Feb 2009 7:59] Valeriy Kravchuk
Thank you for the problem report. Please, send the results of

show innodb status\G

after you get this error message about deadlock. You will see what rows where locked and the reason for a deadlock will be more clear.
[26 Feb 2009 8:16] Royce Lithgo
Here is the deadlock information from the innodb status.

------------------------
LATEST DETECTED DEADLOCK
------------------------
090226 16:09:39
*** (1) TRANSACTION:
TRANSACTION 0 1451023042, ACTIVE 7 sec, process no 1230, OS thread id 2003295136 inserting
mysql tables in use 1, locked 1
LOCK WAIT 4 lock struct(s), heap size 320
MySQL thread id 16406, query id 250348 localhost 127.0.0.1 nexweb update
insert into ns_custom_app_transaction_lock
values(1,'abc123')
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 1753133 n bits 72 index `PRIMARY` of table `dec12idb/ns_custom_app_transaction_lock` trx id 0 1451023042 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 0 1451023043, ACTIVE 3 sec, process no 1230, OS thread id 1997200288 inserting, thread declared inside InnoDB 1
mysql tables in use 1, locked 1
4 lock struct(s), heap size 320
MySQL thread id 18701, query id 250349 localhost 127.0.0.1 nexweb update
insert into ns_custom_app_transaction_lock
values(1,'abc123')
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 1753133 n bits 72 index `PRIMARY` of table `dec12idb/ns_custom_app_transaction_lock` trx id 0 1451023043 lock mode S
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 0 page no 1753133 n bits 72 index `PRIMARY` of table `dec12idb/ns_custom_app_transaction_lock` trx id 0 1451023043 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;;

*** WE ROLL BACK TRANSACTION (2)
[26 Feb 2009 9:33] Valeriy Kravchuk
I had repeated this easily on 5.0.74. I think the following happened:

Transaction B (the first one waiting) was actually waiting for S lock on the record inserted by transaction A. S lock was needed because transaction B had found a duplicate key. This is somehow documented at http://dev.mysql.com/doc/refman/5.0/en/innodb-locks-set.html:

"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."

When transaction A was rolled back, transaction B (it was first in queue) got its S lock. When transaction A was rolled back, transaction C, that was second in queue with its intention to insert, had NOT found any duplicate and proceed with a request for insert intention X lock. It was blocked, as transaction B already had S lock on the record.

But then transaction B, being able to proceed, requested insert intention lock on the record. This request became second in queue, so it was blocked. We got a deadlock, ant transaction holding more locks, B, not C (check it!) was rolled back because of a deadlock. That removed S lock, and transaction C proceed, and inserted the row successfully.

Bad thing is that transaction B was not able to immediately escalate S lock it got to X insert intention lock it needs, skipping any previous requests in queue, but this is how InnoDB is designed at the moment.

In any case, insert intention locked are NOT mentioned in documentation (http://dev.mysql.com/doc/refman/5.0/en/innodb-locks-set.html) at all, so this is a valid documentation request.
[20 Apr 2009 18:24] Paul DuBois
Here is the explanation for the deadlock.

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:

CREATE TABLE t1 (i INT, PRIMARY KEY (i)) ENGINE = InnoDB;

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

Session 1:

START TRANSACTION; 
INSERT INTO t1 VALUES(1);

Session 2: 

START TRANSACTION; 
INSERT INTO t1 VALUES(1);

Session 3: 

<programlisting>
START TRANSACTION;
INSERT INTO t1 VALUES(1);
</programlisting>

Session 1: 

ROLLBACK; 

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 rolls back, it releases its 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#35821.
[21 Apr 2009 1:10] Royce Lithgo
Thanks for that latest explanation, but the bit that I don't follow is how can a transaction get a shared lock on a row that is already exclusively locked by another transaction? Doesn't that defeat the purpose of 'exclusive'?

I would have thought that the 2nd and 3rd transactions that were seeking exclusive locks would have been placed into a locking queue until the exclusive lock is released. At which point the next transaction in the queue would get the exclusive lock. This way there's no deadlock. I take it innodb doesn't work this way?

How else to implement key based locking in innodb if this simple scenario causes dealocking? In the end we went with semaphores.
[21 Apr 2009 17:20] Paul DuBois
I should have indicated that the share locks are requested, and go into a queue until the first session ends. At that point, they come off the queue and are granted. The exclusive locks that sessions 2 and 3 then need to perform the insert deadlock because neither can be granted due to the shared lock held by the other session.
[21 Apr 2009 17:21] Paul DuBois
See also Heikki's comments at [7 Apr 2008 14:12] in Bug#35821.
[29 Apr 2009 19:47] Paul DuBois
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.

Documentation for insert intention locks:

Prior to inserting the row, a type of gap lock called an insertion
intention gap lock is set. This lock signals the intent to insert in
such a way that multiple transactions inserting into the same index
gap need not wait for each other if they are not inserting at the
same position within the gap. Suppose that there are index records
with values of 4 and 7. Separate transactions that attempt to insert
values of 5 and 6 each lock the gap between 4 and 7 with insert
intention locks prior to obtaining the exclusive lock on the inserted
row, but do not block each other because the rows are
non-conflicting. 

(To be added to the description for INSERT at:
http://dev.mysql.com/doc/refman/5.1/en/innodb-locks-set.html)
[6 Oct 2009 7:32] Sveta Smirnova
Bug #43591 was marked as duplicate of this one.
[13 Apr 2011 19:04] Andras Gyomrey
Hi,

What do you mean by semaphores? I just can't find a safely way to insert in a transaction. SELECT.. FOR UPDATE isn't working for this either.