Bug #52020 InnoDB can still deadlock on just INSERT...ON DUPLICATE KEY
Submitted: 12 Mar 2010 21:49 Modified: 4 Jan 2012 21:39
Reporter: Harrison Fisk Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: InnoDB storage engine Severity:S3 (Non-critical)
Version:5.0, 5.1.46 OS:Any
Assigned to: Marko Mäkelä CPU Architecture:Any
Triage: Triaged: D2 (Serious) / R4 (High) / E4 (High)

[12 Mar 2010 21:49] Harrison Fisk
Description:
If you have conflicting INSERT...ON DUPLICATE KEY statements, it is possible for the statements to deadlock.

There seems to be some problem between when INSERT works and the UPDATE needs to be executed.

The order of operations appears to end up as:

Transaction 1: X lock on the gap before rec
Transaction 2: X lock insert intention on the gap before rec -- goes into queue
Transaction 1: X lock insert intention on the gap before rec -- goes into queue

This is related to Bug #21356 with another thread blocking you for a lock you already have, but is a different format.

How to repeat:
INSERT ... ON DUPLICATE KEY from many threads.  

Suggested fix:
Don't try to acquire the insert intention lock for INSERT...ON DUPLICATE KEY UPDATE.  

This statement was modified to acquire an X lock first in Bug #7975 and hence the insert intention lock is not required.
[13 Mar 2010 15:25] Valeriy Kravchuk
Multithreaded test case (no luck in repeating though)

Attachment: bug52020.c (text/x-csrc), 6.11 KiB.

[13 Mar 2010 15:27] Valeriy Kravchuk
I've tried to repeat with a test case uploaded, both aith 5.0.91 and 5.1.46, with up to 10 concurrent threads and 3-1000 distinct values for id and id2 columns of the table. Failed so far, maybe because of single core test box.
[17 Mar 2010 16:28] Mark Callaghan
This also occurs between an INSERT ON DUPLICATE KEY UPDATE and an UPDATE statement where the UPDATE statement gets stuck trying to upgrade lock to obtain 'insert intent' lock mode. It needed that for secondary index maintenance.
[17 Mar 2010 17:51] Sinisa Milivojevic
test script that also failed repeating the bug

Attachment: sinisa.test (application/octet-stream, text), 1.42 KiB.

[17 Mar 2010 18:03] Sinisa Milivojevic
New version with four threads ....

Attachment: sinisa4.test (application/octet-stream, text), 1.94 KiB.

[8 Apr 2010 9:43] Sveta Smirnova
Thank you for the report.

Which transaction isolation level do you use? Please provide your configuration file also.
[8 Apr 2010 18:56] Mark Callaghan
I use repeatable read
[21 Apr 2010 7:56] Shane Bester
think i repeated it now.. please , check if it looks correct.

Attachment: bug52020_5.4.3_deadlock_repeated.txt (text/plain), 2.52 KiB.

[21 Apr 2010 9:35] Shane Bester
think I repeated with 5.1.45 and insert .. on duplicate key update, see attached.

Attachment: bug52020_5.1.45_deadlock_repeated.txt (text/plain), 3.13 KiB.

[21 Apr 2010 15:01] Shane Bester
testcase to cause the above deadlock. often manually inspect 'show innodb status'  (it shows other deadlocks mostly :()

Attachment: bug52020_sbester.c (text/plain), 6.27 KiB.

[22 Apr 2010 14:53] Valeriy Kravchuk
Verified using last test case:

...
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.46-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> show innodb status\G
*************************** 1. row ***************************
  Type: InnoDB
  Name:
Status:
=====================================
100728 21:25:06 INNODB MONITOR OUTPUT
=====================================
Per second averages calculated from the last 54 seconds
----------
SEMAPHORES
----------
OS WAIT ARRAY INFO: reservation count 156, signal count 104
Mutex spin waits 0, rounds 4650, OS waits 22
RW-shared spins 70, OS waits 8; RW-excl spins 446, OS waits 126
------------------------
LATEST DETECTED DEADLOCK
------------------------
100728 21:24:59
*** (1) TRANSACTION:
TRANSACTION 0 987497, ACTIVE 1 sec, process no 6555, OS thread id 1118555056 inserting
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 320, 1 row lock(s), undo log entries 1
MySQL thread id 5, query id 723 localhost 127.0.0.1 root update
insert into `t1` set `a25`=-16582,`col605`=abs(21057) % 2,`col609`=abs(1480) on duplicate key update a25=values(a25),col609=values(col609),col605=values(col605)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 54 n bits 760 index `col605` of table `test`.`t1` trx id 0 987497 lock_mode X waiting
Record lock, heap no 509 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 80000001; asc     ;; 1: len 4; hex 7fff807e; asc    ~;; 2: len 4; hex 800024ef; asc   $ ;;

*** (2) TRANSACTION:
TRANSACTION 0 987493, ACTIVE 1 sec, process no 6555, OS thread id 1118153648 updating or deleting, thread declared inside InnoDB 1
mysql tables in use 1, locked 1
5 lock struct(s), heap size 1024, 355 row lock(s), undo log entries 2
MySQL thread id 3, query id 722 localhost 127.0.0.1 root update
insert into `t1` set `a25`=32406,`col605`=abs(10342) % 2,`col609`=abs(-9006) on duplicate key update a25=values(a25),col609=values(col609),col605=values(col605)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 54 n bits 760 index `col605` of table `test`.`t1` trx id 0 987493 lock_mode X
Record lock, heap no 509 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 80000001; asc     ;; 1: len 4; hex 7fff807e; asc    ~;; 2: len 4; hex 800024ef; asc   $ ;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 54 n bits 760 index `col605` of table `test`.`t1` trx id 0 987493 lock_mode X locks gap before rec insert intention waiting
Record lock, heap no 509 PHYSICAL RECORD: n_fields 3; compact format; info bits 32
 0: len 4; hex 80000001; asc     ;; 1: len 4; hex 7fff807e; asc    ~;; 2: len 4; hex 800024ef; asc   $ ;;

*** WE ROLL BACK TRANSACTION (1)
[27 Apr 2010 10:55] Marko Mäkelä
My attempt at patching this does not seem to make any significant difference to the test program bug52020_sbester.c of [21 Apr 17:01] Shane Bester.

=== modified file 'storage/innodb_plugin/lock/lock0lock.c'
--- storage/innodb_plugin/lock/lock0lock.c	2010-04-26 13:10:29 +0000
+++ storage/innodb_plugin/lock/lock0lock.c	2010-04-27 10:08:47 +0000
@@ -5067,7 +5067,8 @@ lock_rec_insert_check_and_lock(
 
 	if (lock_rec_other_has_conflicting(
 		    LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION,
-		    block, next_rec_heap_no, trx)) {
+		    block, next_rec_heap_no, trx)
+	    && !lock_rec_has_expl(LOCK_X, block, next_rec_heap_no, trx)) {
 
 		/* Note that we may get DB_SUCCESS also here! */
 		err = lock_rec_enqueue_waiting(LOCK_X | LOCK_GAP

With and without this patch, I counted around 15,000 DB_DEADLOCK returns from lock_rec_enqueue_waiting() during the 1-minute test run. Furthermore, I verified with debug printout that the lock_rec_other_has_conflicting() never holds in the test, that is, the added call to lock_rec_has_expl() is never executed.

Would this patch address the original problem? It avoids acquiring the insert intention lock if the transaction is already holding an X lock on the record and the preceding gap.
[29 Apr 2010 19:48] Harrison Fisk
I have done a variety of testing with this patch and without dealing with the testcase provided by Shane.  

The patch provided by Marko should indeed fix the original problem.

Shane's test case produces two categories of deadlocks:

1.  A single row deadlock:  This involves the insert intention lock and X lock on the same row.  This is fixed by the patch provided by Marko.

2.  Multiple row deadlocks:  This involves different rows being locked in different orders and are totally expected deadlocks.

When I run without the patch, I see both of these occurring.  When I add the patch, the first category does not happen any more, and only multiple row deadlocks are found.  Some may include the insert intention lock, but that is okay since it is on different rows.

So this patch should fix the problem for single row insert ... on duplicate key cases.  I would recommend it.
[30 Apr 2010 5:14] Shane Bester
Harrison, great you confirmed it.  It was tricky for me, since category 1 deadlock happened less than 1% of the time, and I had to be really fast to check it (or break in debugger for each deadlock :)
[18 May 2010 22:19] James Day
If you have a production emergency, don't be tempted to use the current patch, it's currently not safe and needs more work.

James Day, MySQL Senior Support Engineer, Oracle
[26 Jun 2010 21:17] Suhail Doshi
Is there any production patch or timeline?
[11 Aug 2010 7:06] Marko Mäkelä
InnoDB locking and multi-versioning is a complex area that would require major effort. The simple fix that I posted is broken. Fixing Bug #19762 would also take care of this issue.
[16 Nov 2010 14:40] Marko Mäkelä
Sorry, there has not been any progress on this area since the last update. I am hoping to start a complete review of the InnoDB locking rules some day.

There are two approaches to deadlock avoidance. One would be posting the lock requests in the same order in all threads, like MySQL does in open_and_lock_tables, and like InnoDB does for its internal mutexes and rw-locks (the latching order). This is difficult to achieve from the database user perspective, because there many sources of nondeterminism, such as gap locks and delete-marked records that could be swiped by the purge thread.

Another approach to deadlock avoidance is avoiding lock upgrades, or more coarse-grained locking. For example, instead of initially taking a shared lock and attempting to convert it to an exclusive lock later, we could acquire the exclusive lock upfront. That would reduce the chance of deadlocks at the price of reducing concurrency. The extreme case would be locking the entire table upfront, like MyISAM does.

I believe that if we fixed this special case by a small tweak instead of doing a complete overhaul of the locking, we would have to follow the idea of acquiring all necessary locks upfront.
[14 Sep 2011 8:20] Marko Mäkelä
In Bug#50413 there is an example posted [1 Dec 2010 20:57] by Sven Sandberg that shows why locks are necessary:

CREATE TABLE t1 (a INT UNIQUE KEY, b INT UNIQUE KEY, c INT) ENGINE = InnoDB;

--echo # Interleaved transactions
INSERT INTO t1 VALUES (1, 1, 1);
BEGIN;
INSERT INTO t1 VALUES (2, 1, 2) ON DUPLICATE KEY UPDATE c=VALUES(c);
  --connection other
  BEGIN;
  INSERT INTO t1 VALUES (2, 2, 3) ON DUPLICATE KEY UPDATE c=VALUES(c);
  COMMIT;
--connection default
INSERT INTO t1 VALUES (2, 3, 4) ON DUPLICATE KEY UPDATE c=VALUES(c);
COMMIT;
SELECT * FROM t1;

The above is currently not serializable, because the insert (2,1,2) fails to lock the record a=2 (or the gap after the only record a=1) because b=1 would violate the UNIQUE(b) constraint. If the insert (2,1,2) locked a=2, the insert (2,2,3) would block.

It should be noted that attempts to fix Bug#19762 (InnoDB should not lock a delete-marked record) may affect ON DUPLICATE KEY UPDATE for the better or the worse. If we try to purge delete-marked records quicker, so that they will not be locked unnecessarily, then the gap locks will become wider, because gap locks only extend to the following record, delete-marked or not. For example,

INSERT INTO t1 VALUES (1, 1, 1), (4, 4, 4);
DELETE FROM t1 WHERE a=4;
BEGIN;
# if purge has not completed, this should lock a=2 and a=3:
INSERT INTO t1 VALUES (2, 1, 2) ON DUPLICATE KEY UPDATE c=VALUES(c);
  --connection other
  BEGIN;
  # if a=4 has not been purged yet, this should succeed:
  INSERT INTO t1 VALUES (5, 5, 5);
  COMMIT;
--connection default
COMMIT;
[14 Oct 2011 17:45] Marko Mäkelä
Sorry, unless you can come up with a specific example and prove that relaxing the locking is safe in this case, we cannot do anything.
[9 Nov 2011 9:17] Marko Mäkelä
On a deeper look, it seems that this bug was introduced when innobase_query_is_update() was replaced in MySQL 5.1.

Can anyone confirm that this bug really exists in MySQL 5.0?
[9 Nov 2011 10:23] Marko Mäkelä
It looks like innobase_query_is_update() was implemented in 5.0.3 to fix MySQL Bug#7975. It was removed in MySQL 5.1 well before the GA release.
[10 Nov 2011 11:39] Marko Mäkelä
The patch that I just pushed adds a test case, innodb_replace.test.

You might use it as a base for creating scenarios that deadlock when you think that they should not.

I would love to hear if this bug really existed in 5.0 after 5.0.3.
[15 Nov 2011 7:00] Bugs System
No feedback was provided for this bug for over a month, so it is
being suspended automatically. If you are able to provide the
information that was originally requested, please do so and change
the status of the bug back to "Open".
[4 Jan 2012 21:39] John Russell
Added to MySQL 5.6.4, 5.1.61, and 5.5.20 changelog: 

Issuing INSERT...ON DUPLICATE KEY statements for InnoDB tables from 
concurrent threads could cause a deadlock, particularly with the 
INSERT...ON DUPLICATE KEY UPDATE form. The fix avoids deadlocks 
caused by the same row being accessed by more than one transaction. 
Deadlocks could still occur when multiple rows are inserted and 
updated simultaneously by different transactions in inconsistent 
order; those types of deadlocks require the standard error handling 
on the application side, of re-trying the transaction.
[24 Apr 2012 13:50] Michael Hase
For me these deadlocks still occur with mysql version 5.5.23 (binary from mysql.com) on a solaris box (8 cores) with testcase bug52020_sbester.c

The problen does not occur if innodb_thread_concurrency is set to 1, this is somehow expected. innodb_thread_concurrency >= 2 or the default 0 and the deadlocks are there.
[30 Aug 2012 19:35] Marko Mäkelä
INSERT...ON DUPLICATE KEY UPDATE is a problematic construct. The problem is that the INSERT code path inside InnoDB is not locking the record for the UPDATE code path. That bug is being tracked as Bug#50413. This one (actually a regression in MySQL 5.1) was fixed.
[5 Mar 2013 1:04] Ricardo Oliveira
this is still happening for mysql server v5.5.29, any fix in the roadmap?
[5 Mar 2013 9:43] Marko Mäkelä
This regression bug was fixed and closed. The remaining (not yet fixed) bug is being tracked in Bug#50413.
[6 Mar 2013 8:45] Ricardo Oliveira
well, you said above "The fix avoids deadlocks caused by the same row being accessed by more than one transaction." My deadlock is being created exactly this way, two queries accessing the same row in different threads with INSERT ON DUPLICATE UPDATE. So i dont understand how you can mark this as "fixed".
[6 Mar 2013 8:53] Ricardo Oliveira
Also , it seems Bug#50413 refers to a problem occurring during replication; im not using replication. Seems a confusing to point to that bug for this problem, which is very easy to replicate. Just run multiple threads trying to do a INSERT ON DUPLICATE KEY UPDATE with clashing keys and this error is going to happen eventually.
[20 Jan 2014 13:04] Marko Mäkelä
This Bug#52020 (accidental re-introduction of Bug#7975 in MySQL 5.1) affects tables that do not contain a secondary index.

There is another bug that affects tables with secondary indexes:

Bug#50413 insert on duplicate key update sometimes writes binlog position incorrectly

Despite the title, Bug#50413 can occur even if MySQL replication or binlog is not used. That bug has was fixed in MySQL 5.7.4. The fix is that when we encounter a duplicate key in the clustered index or in any unique secondary index during an INSERT, we will acquire gap locks in the not-yet-checked secondary indexes as well. In this way, the INSERT will already have acquired some locks for the ON DUPLICATE KEY UPDATE part, thus avoiding some potential deadlocks.

When there are multiple unique indexes, the execution of ON DUPLICATE KEY UPDATE can be ambiguous, which makes it tricky for statement-based replication.
[20 Jun 2017 18:38] shaurabh singh
Hi,
I am facing this same issue in version 5.7.18. Deadlock error when multiple threads execute INSERT..... ON DUPLICATE KEY UPDATE for bulk insert/update.
How can it be fixed?
[20 Jun 2017 18:40] shaurabh singh
Hi,
I am facing this same issue in version 5.7.18. Deadlock error when multiple threads execute INSERT..... ON DUPLICATE KEY UPDATE for bulk insert/update.
How it can be fixed?
[21 Jun 2017 4:47] shaurabh singh
The is happening when I have primary key on a column and a unique index on another column.
[22 Dec 2017 8:22] Nitin Sachdeva
INSERT ON DUPLICATE UPDATE deadlock issuw with next-key lock

Attachment: INSert_UPDATE_DEADLOCK.txt (text/plain), 2.47 KiB.

[22 Dec 2017 8:24] Nitin Sachdeva
I am facing the same issue when multiple threads are trying to insert in same table with primary key and unique index. Records are being inserted are different. Also It seems to be taking next-key lock here.