Completely avoid deadlocks with concurrent transactions inserting identical data in MySQL

Question

I have two concurrent transactions inserting identical but differently ordered data into a table with unique keys, thus causing frequent deadlocks. How can I avoid these deadlocks in this setup? I'm using MySQL

Example:

CREATE TABLE cache (
    id int auto_increment primary key,
    k int unique not null,
    v int not null
);

with the first transaction inserting entry 1 before 2

START TRANSACTION;
INSERT INTO cache (k, v) VALUES (1, 1);
INSERT INTO cache (k, v) VALUES (2, 2);
COMMIT;

and the second concurrent transaction inserting data the other way around

START TRANSACTION;
INSERT INTO cache (k, v) VALUES (2, 2);
INSERT INTO cache (k, v) VALUES (1, 1);
COMMIT;

Some more context: The table in question acts as a cache table. The values are computed in our application and will be used for subsequent sorting and filtering. The application knows which cache entries are relevant to its current task. In our current implementation, we first do a database query to check which of these cache entries are still missing, compute and insert them, and then do a query on the (now complete) cache table.

Answer 1

If you can't control the order of inserts, the only way to completely avoid deadlocks is to make sure your transactions occur serially, not concurrently, using some type of gating mechanism like an external lock, a sempahore, or a critical section in your code.

This does have implications for throughput. If transactions are happening rapidly, you could create a bottleneck such that the transactions are queued, waiting for other transactions to finish. If your transactions are short enough that they complete as rapidly as the requests come in, that'll be okay. But if they are coming in too fast, the throughput might not be able to keep up.

In MySQL, you can use statements like LOCK TABLES ... or DO GET_LOCK(...); to implement a kind of global gatekeeper to force transactions to run serially. I encourage you to read about those statements in the MySQL manual.

An alternative, instead of preventing deadlocks, is to respond to deadlocks when they happen. That is, allow concurrent transactions, and write code to check for deadlock errors and if one occurs, then start your transaction over (MySQL has killed the transaction if you receive the error), and try again.