MySQL deadlock on concurrent INSERT ... ON DUPLICATE KEY UPDATE batches

We run an inventory service for a marketplace with around 40 suppliers. Each supplier pushes stock feeds, and Sidekiq jobs write the levels into a MySQL table, inventory_levels, keyed by SKU and warehouse. In the week before a big November sale, the error tracker started reporting this during afternoon peaks:

ActiveRecord::Deadlocked: Mysql2::Error: Deadlock found when trying to get lock; try restarting transaction
  app/jobs/import_stock_batch_job.rb:31:in `perform'

About 2.5% of import jobs failed with it at peak. Sidekiq retried them, so nothing was lost, but the retries landed minutes later. During that window, the storefront showed stale stock, and we oversold 37 units of a promoted item in one afternoon.

Reproducing it

Each feed is split into batches of 500 rows, and each batch is written with one multi-row upsert. Simplified, the statement looks like this:

INSERT INTO inventory_levels (sku_id, warehouse_id, qty, updated_at)
VALUES (88123, 4, 12, NOW()), (10477, 4, 0, NOW()), (55310, 4, 3, NOW()) -- ...500 rows
ON DUPLICATE KEY UPDATE qty = VALUES(qty), updated_at = VALUES(updated_at);

Two suppliers often stock the same SKUs in the same warehouse, and their feeds list rows in their own order. We reproduced the deadlock in staging with two MySQL sessions, each inside an explicit transaction, upserting the same two keys in opposite order. The second session's statement failed immediately with error 1213.

What we ruled out

• Long transactions. Each job's transaction lasted under 200 ms; there was no lock wait timeout (error 1205), only deadlocks.
• Foreign key checks. inventory_levels has foreign keys to skus and warehouses, which take shared locks on parent rows. The deadlock log showed only locks on the unique index of inventory_levels itself.
• A recent MySQL upgrade. We had moved from 8.0.36 to 8.0.40 a month earlier. Deadlocks were present before the upgrade too; traffic growth had simply made them visible.

Root cause

SHOW ENGINE INNODB STATUS showed the pattern clearly. Two transactions each held an exclusive next-key lock on one entry of the unique index uq_sku_warehouse and waited for a lock on the other's entry. One was also waiting for an insert intention lock on a gap the other had locked:

------------------------
LATEST DETECTED DEADLOCK
------------------------
2024-11-19 14:02:11 140235561371200
*** (1) TRANSACTION:
TRANSACTION 1849302, ACTIVE 0 sec inserting
mysql tables in use 1, locked 1
LOCK WAIT 5 lock struct(s), heap size 1128, 3 row lock(s), undo log entries 2
MySQL thread id 8812, OS thread handle 140235561371200, query id 9921733 198.51.100.14 inventory update
INSERT INTO inventory_levels (sku_id, warehouse_id, qty, updated_at) VALUES ...
*** (1) HOLDS THE LOCK(S):
RECORD LOCKS space id 412 page no 87 n bits 312 index uq_sku_warehouse of table `inv`.`inventory_levels` trx id 1849302 lock_mode X
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 412 page no 87 n bits 312 index uq_sku_warehouse of table `inv`.`inventory_levels` trx id 1849302 lock_mode X locks gap before rec insert intention waiting
*** (2) TRANSACTION:
TRANSACTION 1849305, ACTIVE 0 sec inserting
...
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 412 page no 87 n bits 312 index uq_sku_warehouse of table `inv`.`inventory_levels` trx id 1849305 lock_mode X waiting
*** WE ROLL BACK TRANSACTION (2)

Concurrent upsert batches with overlapping keys in different orders, plus gap locking around new keys, made lock cycles inevitable at higher concurrency.

What is happening under the hood

InnoDB locks index records, not rows in the abstract. Under the default REPEATABLE READ isolation level, it uses next-key locks: a lock on an index record plus the gap before it. The MySQL manual describes what INSERT ... ON DUPLICATE KEY UPDATE does when it hits an existing key: it places an exclusive lock instead of the shared lock a plain INSERT would take, and for a duplicate on a unique secondary index that is an exclusive next-key lock.

For keys that do not exist yet, InnoDB first takes an insert intention lock, a special gap lock. Insert intention locks do not conflict with each other, but they do wait for an existing gap or next-key lock held by another transaction on that gap.

A multi-row upsert acquires these locks one row at a time, in the order the rows appear. If transaction A processes keys (K1, K2) and transaction B processes (K2, K1), A holds K1 and wants K2 while B holds K2 and wants K1. InnoDB detects the cycle and rolls back the transaction that is cheaper to undo. Even with identical order, new keys landing in a gap that the other transaction has next-key locked can form a cycle.

Environment

Minimal reproduction

-- session A
START TRANSACTION;
INSERT INTO inventory_levels (sku_id, warehouse_id, qty) VALUES (1, 1, 5)
  ON DUPLICATE KEY UPDATE qty = VALUES(qty);

-- session B
START TRANSACTION;
INSERT INTO inventory_levels (sku_id, warehouse_id, qty) VALUES (2, 1, 7)
  ON DUPLICATE KEY UPDATE qty = VALUES(qty);
INSERT INTO inventory_levels (sku_id, warehouse_id, qty) VALUES (1, 1, 9)
  ON DUPLICATE KEY UPDATE qty = VALUES(qty);   -- waits for A

-- session A
INSERT INTO inventory_levels (sku_id, warehouse_id, qty) VALUES (2, 1, 3)
  ON DUPLICATE KEY UPDATE qty = VALUES(qty);   -- ERROR 1213 (40001): Deadlock found ...

Who is affected

Any InnoDB workload with concurrent multi-row upserts, or several upserts in one transaction, that touch overlapping unique keys. It is most common with unique secondary indexes, ingestion pipelines, counters and "last seen" tables. READ COMMITTED reduces gap locking but does not remove it: the manual notes that gap locks are still used for duplicate-key checking.

The fix

We applied three changes, in order of impact.

1. Consistent lock order. Every batch is now sorted by the unique key before it is written. Two transactions that touch the same keys acquire locks in the same order, so one simply waits for the other instead of forming a cycle:

 def perform(supplier_id, rows)
-  InventoryLevel.upsert_all(rows, record_timestamps: true)
+  sorted = rows.sort_by { |r| [r[:sku_id], r[:warehouse_id]] }
+  sorted.each_slice(100) do |slice|
+    with_deadlock_retry { InventoryLevel.upsert_all(slice, record_timestamps: true) }
+  end
 end

2. Smaller batches. Going from 500 to 100 rows per statement shortened how long each statement holds its locks and reduced the overlap between concurrent batches. Throughput stayed the same because round trips were not the bottleneck.

3. A bounded retry for the remaining cases. Deadlocks are a normal outcome under InnoDB and the manual recommends that applications retry. We retry only the failed statement, with jitter:

def with_deadlock_retry(attempts: 3)
  tries = 0
  begin
    yield
  rescue ActiveRecord::Deadlocked
    tries += 1
    raise if tries >= attempts
    sleep(rand * 0.05 * tries)
    retry
  end
end

We also replaced the deprecated VALUES(col) function in our hand-written upserts with the row alias syntax available since MySQL 8.0.19:

INSERT INTO inventory_levels (sku_id, warehouse_id, qty, updated_at)
VALUES (1, 1, 5, NOW()) AS new
ON DUPLICATE KEY UPDATE qty = new.qty, updated_at = new.updated_at;

Alternatives and trade-offs

1. Single writer per partition. Routing all writes for a warehouse to one Sidekiq queue with concurrency 1 removes contention entirely, at the cost of throughput per warehouse.
2. READ COMMITTED for the import connection. It disables most gap locking and reduced deadlocks further in our tests, but duplicate-key checks still lock gaps. We kept it as an option rather than a fix.
3. Update first, insert only misses. UPDATE ... WHERE (sku_id, warehouse_id) IN (...) followed by INSERT IGNORE for the rest takes fewer gap locks for existing keys, but needs two statements and has its own race window.

How to test the fix

We wrote a stress script that runs 20 threads, each upserting random overlapping subsets of 2,000 keys in random order, for two minutes:

bin/rails runner script/upsert_stress.rb --threads 20 --keys 2000 --seconds 120

before: batches=41210 deadlocks=1187 (2.9%)
after:  batches=40877 deadlocks=4 (0.01%), retried successfully=4

Confirming in production

We enabled innodb_print_all_deadlocks so that every deadlock is written to the error log, not only the latest one, and tracked the InnoDB deadlock counter:

SET GLOBAL innodb_monitor_enable = 'lock_deadlocks';
SELECT name, count FROM information_schema.INNODB_METRICS WHERE name = 'lock_deadlocks';

During the sale week, deadlocks dropped from about 900 per peak hour to between 0 and 6, and every one of those succeeded on the first retry. Sidekiq retries for the import job went to zero, and the median delay from feed receipt to storefront stock update fell from 4 minutes at peak to 9 seconds. There were no oversells caused by stale stock during the sale.

Regression guard

• The stress script runs nightly against a staging database and fails if the deadlock rate exceeds 0.1%.
• A shared UpsertBatch helper sorts by unique key, so new import jobs get ordering for free.
• An alert fires when lock_deadlocks grows faster than 50 per minute.

Security implications

None beyond availability and data correctness. Deadlocks do not expose data, but stale inventory led to overselling, and a retry loop without a limit could amplify load on the primary during an incident. Our retry is bounded to three attempts with jitter, and errors after that surface as normal job failures.

Prevention checklist

• Sort rows by the unique key before multi-row upserts or multi-statement transactions.
• Keep upsert batches small and transactions short.
• Treat error 1213 as retryable, with a bounded retry and jitter.
• Turn on innodb_print_all_deadlocks and monitor the deadlock counter.
• Load-test concurrent writers with overlapping keys before peak events.

References

• MySQL 8.0 Reference Manual, Locks Set by Different SQL Statements in InnoDB — https://dev.mysql.com/doc/refman/8.0/en/innodb-locks-set.html
• MySQL 8.0 Reference Manual, InnoDB Locking (next-key and insert intention locks) — https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html
• MySQL 8.0 Reference Manual, How to Minimize and Handle Deadlocks — https://dev.mysql.com/doc/refman/8.0/en/innodb-deadlocks-handling.html
• MySQL 8.0 Reference Manual, INSERT ... ON DUPLICATE KEY UPDATE Statement — https://dev.mysql.com/doc/refman/8.0/en/insert-on-duplicate.html
• Rails API, ActiveRecord::Persistence::ClassMethods#upsert_all — https://api.rubyonrails.org/classes/ActiveRecord/Persistence/ClassMethods.html#method-i-upsert_all