Concurrent conditional inserts, prevent duplicates

Question

I'd like to guard against concurrent conflicting inserts given a certain condition. I'm building a system that allows users to select an available time slot and reserve it but prevent two users from reserving the same slot. The condition involves a couple of constraints, but for simplicity sake lets assume the following:

CREATE TABLE reservations (
  id INT AUTO_INCREMENT PRIMARY KEY,
  val VARCHAR(255) NOT NULL
);

where val remains unique (in reality the "uniqueness" involves datetime range checks and more).

Optimistic locking

I had assumed that the following would suffice:

INSERT INTO reservations (val) SELECT :val FROM reservations
    WHERE 0 = (SELECT COUNT(*) FROM reservations WHERE val=:val) LIMIT 1

But this causes two problems in some of the concurrency tests I've performed (MariaDB using Go):

• It happens that one insert is successful, but the others return Error 1467 (HY000): Failed to read auto-increment value from storage engine upon INSERT
• Sometimes it inserts the same value twice! There doesn't seem to be a lock between the SELECT and the INSERT, and neither is the entire statement atomic. Neither if I add FOR UPDATE to the inner SELECT

Optimistic insert

The other option I figured is the following:

SELECT COUNT(*) FROM reservations WHERE val=:val
-- application: check count=0 beforehand to prevent inserting a row and updating AUTO_INCREMENT unnecessarily

INSERT INTO reservations (val) VALUES (:val)
-- application: store last insert ID

SELECT COUNT(*) FROM reservations WHERE val=:val
-- application: check count=1 afterwards to detect conflicts

-- only if 1<count:
DELETE FROM reservations WHERE id=:last_insert_id

The following considerations I believe to apply on concurrent use:

• We can exclude the first SELECT from consideration since it doesn't guarantee anything, it just prevents 99% of the bad inserts beforehand
• I believe the simple INSERT, SELECT and DELETE statements to be atomic in the sense that they happen "in an instant" without possibly interleaving with other statements (eg. a SELECT at the same time of an INSERT either selects nothing or the inserted value, nothing "in between")
• We could insert the same value twice, and then both are deleted (worst case)
• We could insert the same value twice, but only delete one of the rows
• A transaction would defeat the purpose of the different selects with the repeatable reads isolation for example
• We now have two selects instead of one, which is not optimal
• We could combine the SELECT and DELETE into one: DELETE FROM reservations WHERE id=:last_insert_id AND 1 != (SELECT COUNT(*) FROM reservations WHERE val=:val) but I'm not sure if this could cause a problem

Putting a uniqueness constraint on the table would be preferable but not easy/feasible with the conditions I need. See also Concurrency with Select-conditional Insert/Update/Delete - PostgreSQL for some considerations why locking rows (with FOR UPDATE) is insufficient, you'd need to lock the entire table to prevent race conditions.

Any thoughts or opinions are highly appreciated!

Answer 1

I thought this would be a common scenario, but alas I couldn't find resources on this, and everyone seems to discourage READ UNCOMMITTED. My conclusions and solution:

• We simply insert a row and then check if constraints failed, otherwise for the reverse anything may happen between a SELECT and the INSERT. We could still put an extra SELECT before (and outside) of the transaction, just to reject common and non-concurrent conflicts to avoid the transaction dance. That may be better for performance and would prevent unnecessary primary key increments caused by AUTO_INCREMENT on INSERTs
• We need to use a transaction for two reason: so that the inserted row is not visible to other unrelated queries; and so that in any case of failure (lost connection, client crash) the INSERT is automatically rolled back
• Due to using a transaction, we need to read the UNCOMMITTED data from the INSERTs from other transactions in-process, not doing dirty reads would open the possibility of multiple insertions

-- OPTIONAL to exclude common case:
SELECT COUNT(*) FROM reservations WHERE val=:val;


BEGIN TRANSACTION;
SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;

INSERT INTO reservations (val) VALUES (:val);

SELECT COUNT(*) FROM reservations WHERE val=:val;

-- IF 1 < COUNT:
ROLLBACK;
-- ELSE
COMMIT;
-- END

I have tested this using two concurrent transactions step-by-step, as well as a test with 20 concurrent transactions. This will either insert ONE row or NONE at all. Since transactions at the exact same time are generally rare, the worst case where none of the transactions succeed is acceptable (but not perfect). Each transaction takes about 2ms – 10ms, increasing for each concurrent transaction, suggesting some kind of locking (perhaps for the AUTO_INCREMENT or for the atomic INSERTs/SELECTs).