MySQL Bugs: #52020: InnoDB can still deadlock on just INSERT...ON DUPLICATE KEY

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

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.

Multithreaded test case (no luck in repeating though)

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

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.

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.

test script that also failed repeating the bug

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

New version with four threads ....

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

Thank you for the report.

Which transaction isolation level do you use? Please provide your configuration file also.

I use repeatable read

think i repeated it now.. please , check if it looks correct.

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

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.

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.

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)

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.

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 :)

Is there any production patch or timeline?

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.

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.

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;

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.

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?

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.

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.

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

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.

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.

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.

this is still happening for mysql server v5.5.29, any fix in the roadmap?

This regression bug was fixed and closed. The remaining (not yet fixed) bug is being tracked in Bug#50413.

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

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.

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.

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?

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?

The is happening when I have primary key on a column and a unique index on another column.

INSERT ON DUPLICATE UPDATE deadlock issuw with next-key lock

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

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.