Contention and double booking

Contention is many requests racing to claim the same scarce thing: the last berth on a train, a hotel room for one night, the final unit in a flash sale, a username, a driver, the money in a wallet. Double booking is the bug when two of them both win. The fix is one idea applied at growing scale: make the check and the claim one indivisible step, decided by one authority, and decide in advance what the losers see.

Picture it first: the key on the hook

A small hotel has a whiteboard listing free rooms and a hook board with one key per room. Two clerks serve two guests who both want room 204 tonight.

Working from the whiteboard, both clerks see “204: free”, both say yes, and later someone finds two names against one room. Looking and writing were separate acts.

Working from the hook board, the first clerk to lift the key has the room; the second finds an empty hook and apologises. Checking and claiming are one motion, and a key cannot be in two hands.

Two more habits complete the picture. For a guest stepping out to the cash machine, the key goes in an envelope marked “held for Mr Rao until 3:10 pm”; after 3:10 anyone may take it. On a festival night, the manager hands out numbered tokens at the door so only a few guests reach the desk at once.

Map it back: the whiteboard is a read followed by a separate write; the hook is an atomic conditional write; the envelope is a hold with an expiry; the tokens are a waiting room.

Spotting the pattern

Reach for this playbook on any of these cues:

• A scarce unit with many takers. “The last seat”, “limited stock”, “one room per night”, “one driver per ride”, “each username once”, “highest bid wins”.
• An explicit never. “Must never oversell”, “no double booking”, “balance can never go negative”. The claim must then be strongly consistent, refusing rather than guessing during a partition (the CP side of CAP).
• A timed rush. Tatkal booking opening at 10 am, a Big Billion Days-style deal, an auction’s last seconds: thousands of requests per second on one row.
• A slow step in the middle. The user picks seats, then pays with a UPI collect request or a card OTP. Minutes between “I want it” and “it’s mine” call for a hold.
• Money leaving an account. Wallet debits and ledger postings are double-spend problems in disguise.

Know when it does not apply. Like counts, view counts and the “only 3 left!” badge can be approximate: use cheap counters and accept a little error (see scaling writes). Unlimited goods such as e-books have nothing to fight over. Contention means many writers on the same row; writes spread over millions of rows are a throughput problem instead.

The core bug: check, then act

Here is the code almost everyone writes first:

-- Step 1: look
SELECT status FROM seats WHERE show_id = 42 AND seat_id = 'C7';  -- 'free'
-- Step 2: the application decides, then writes
UPDATE seats SET status = 'booked', user_id = :me
 WHERE show_id = 42 AND seat_id = 'C7';

Between the two statements is a gap (a round trip, some code, perhaps a garbage-collection pause), and any other request can read the same “free” inside it.

Wrapping both in a transaction does not help at PostgreSQL’s default level, READ COMMITTED. Each statement sees data committed before that statement began, so both buyers’ SELECTs see “free”. The second UPDATE waits for the first buyer’s row lock, then re-checks its WHERE clause against the new row. The clause only says seat_id = 'C7', which still matches, so it overwrites the first buyer. Both were told “booked”; the row names only the second. That is the classic lost update.

A stricter level is only a partial fix. PostgreSQL’s REPEATABLE READ aborts the second updater with “could not serialize access due to concurrent update”. But if each booking is a new row in a bookings table, the two transactions write different rows, nothing conflicts, and snapshot isolation commits both: write skew. See transaction isolation levels and concurrency control.

The fix is to move the check into the write, so the database decides:

UPDATE seats SET status = 'held', user_id = :me
 WHERE show_id = 42 AND seat_id = 'C7' AND status = 'free';
-- 1 row updated: you have it.  0 rows: someone beat you to it.

When the second buyer’s UPDATE re-checks this clause after the first commits, status = 'free' is false, it updates zero rows, and you show a clean “sorry, just taken”.

Every rung that follows keeps that property (one authority decides, atomically) as the decision gets bigger, slower or hotter. Figure 2 maps the rungs on two axes.

Start at rung 1 and climb only when you can name the number that forces you.

Rung 1: let the database decide

How it works. Express the whole rule as one statement that either succeeds or changes nothing, then check the result.

• A conditional update for a specific item, as above. Check the affected-row count; zero rows is not an error.
• A conditional decrement for interchangeable stock: UPDATE stock SET qty = qty - 1 WHERE sku = :sku AND qty > 0, with CHECK (qty >= 0) as a backstop.
• A unique constraint when the claim is a new row: UNIQUE (show_id, seat_id) on tickets, or a unique index on lower(username). Insert with ON CONFLICT DO NOTHING; nothing inserted means “taken”.
• An exclusion constraint for ranges, which uniqueness cannot express. PostgreSQL can reject overlapping stays in one room; the btree_gist extension supplies the = on a plain column:

CREATE EXTENSION btree_gist;
CREATE TABLE room_stays (
  room_id int,
  stay    daterange,
  EXCLUDE USING gist (room_id WITH =, stay WITH &&)
);
-- Two overlapping inserts for room 204: one commits, the other
-- fails with "conflicting key value violates exclusion constraint".

A hotel that sells room types rather than specific rooms keeps one row per type per night, and updates every night of the stay in one statement: SET reserved = reserved + 1 WHERE … AND night >= :in AND night < :out AND reserved < total. If a three-night stay updates only two rows, a night is full: roll back. See database constraints.

Outside SQL, a DynamoDB UpdateItem with a condition expression such as qty > :zero applies or fails as a whole; Redis SET key value NX writes only if absent.

What you gain: one round trip, no locks in your code, no retries, correct under READ COMMITTED. What you pay: the rule must fit in one statement, and writers to a hot row still queue on its lock until they commit.

Where it breaks. That queue caps each row. If a claim holds the row lock for about 5 ms, statement plus commit (illustrative), one row admits at most 1,000 ÷ 5 = 200 claims per second, however many app servers you add. Plenty for a hotel room-night; far too little for one flash-sale counter. You also outgrow this rung when the decision needs several rows and application logic.

Say it: “The claim is a conditional write. One row changed means you got it; zero means someone beat you.”

Rung 2: lock the rows first

When the decision needs several reads and some code (“two adjacent seats, stranding no single seat”, or “move ₹500 from wallet A to B”), lock first, then decide:

BEGIN;
SELECT seat_id, status FROM seats
 WHERE show_id = 42 AND seat_id IN ('C7', 'C8')
 ORDER BY seat_id
 FOR UPDATE;           -- anyone else claiming C7 or C8 now waits
-- application checks both are free and the gap rule holds
UPDATE seats SET status = 'held', user_id = :me
 WHERE show_id = 42 AND seat_id IN ('C7', 'C8');
COMMIT;

Three details separate a solid version from a flaky one:

• Lock in one global order. If one transaction locks C7 then C8 while another locks C8 then C7, each waits for the other. PostgreSQL detects the deadlock and aborts one; its docs advise taking locks on multiple objects in a consistent order. Sort by seat or account ID.
• Skip instead of queueing when any unit will do. For “any free lower berth in coach S4”, … LIMIT 1 FOR UPDATE SKIP LOCKED lets each buyer pass over rows others have locked, so a hundred buyers grab a hundred different berths instead of queueing on one. PostgreSQL warns this view is inconsistent: right for picking work, wrong for reporting. NOWAIT errors at once instead.
• Keep the lock short. Never call a payment provider or wait for a user while holding it. A blocked PostgreSQL lock request waits indefinitely, so set lock_timeout.

What you gain: simple reasoning, and no wasted work. What you pay: waiting, deadlock handling, and a connection tied up by every waiter. See optimistic vs pessimistic locking.

Where it breaks. Throughput on a hot row is 1 ÷ lock hold time, and you control the hold time: 5 ms gives 200 claims per second. Put a 2-second payment call inside the transaction and the ceiling falls to 0.5 per second; with 200 requests arriving per second, about 200 × 2 = 400 transactions are waiting within two seconds, more than most connection pools hold, and the backlog keeps growing. The whole service stalls.

Say it: “When the rule spans rows, I lock them in ID order and keep the transaction to milliseconds.”

Rungs 3 and 4: detect conflicts, then retry

Locking assumes conflicts are likely, so everyone waits. These two rungs assume they are rare: everyone proceeds, and the loser is caught at write or commit time.

Optimistic concurrency control

Give each row a version column. Read the row and its version, do your work, then write only if nothing changed:

UPDATE seats SET status = 'held', user_id = :me, version = version + 1
 WHERE show_id = 42 AND seat_id = 'C7' AND version = 7;
-- 0 rows: someone changed it after you read it. Re-read and decide again.

DynamoDB’s Java mapper does exactly this with a version attribute, turning each save into a conditional write that fails with ConditionalCheckFailedException on a mismatch; HTTP has the same shape with ETag and If-Match. One caveat from the DynamoDB docs: multi-Region global tables settle concurrent writes by last-writer-wins, so version checks do not hold across Regions. Route each item’s claims to one Region.

What you gain: no locks held while a user thinks. What you pay: bounded, jittered retry loops, and wasted work for every loser.

Where it breaks. If writes hit a row at rate r per second and your read-to-write window lasts w seconds, the chance another write lands inside your window is about 1 − e^(−r·w): roughly 5% at r·w = 0.05, 39% at 0.5, 99% at 5. At 2 writes per second and a 25 ms window, optimistic control is nearly free; at 2,000 per second (r·w = 50), almost every attempt fails.

Worse, the losers come back. If k buyers race on one stock counter in lockstep, each round has one winner, so serving all of them takes k + (k − 1) + … + 1 = k(k + 1) ÷ 2 writes: 55 for 10 buyers, 5,050 for 100. A queue needs 10 and 100.

Backing off with jitter spreads retries out but does not remove the wasted work. Use optimistic control while r·w stays well below 0.1.

SERIALIZABLE isolation

PostgreSQL’s SERIALIZABLE level (serializable snapshot isolation) lets you write naive check-then-insert code and stay safe. It tracks read/write dependencies between concurrent transactions with predicate locks that never block, and when a group of transactions could not have run in any one-at-a-time order, aborts one with SQLSTATE 40001. The double insert into bookings that slipped past REPEATABLE READ is caught. See serializable isolation.

What you gain: correctness by default for invariants awkward to encode by hand, such as “guests across overlapping bookings never exceed capacity”. What you pay: every transaction must be retryable from the start, and nothing it reads is trustworthy until it commits. Only transactions that also run at SERIALIZABLE are protected, and false positives happen: PostgreSQL warns that a sequential scan takes a relation-level predicate lock and raises the failure rate, so index your predicates.

Where it breaks. Under contention it behaves like optimistic control, retries piling up, and it stops at the edge of one database.

Say it: “Conflicts are rare here, so I use a version check with three jittered retries. If r times w nears 1, I switch to a conditional write or a queue.”

Rung 5: hold, pay, confirm

Payment is the slow step: a UPI collect request or a card OTP can take minutes, and the user may walk away. No row lock should last that long, so split the claim into three short steps:

1. Hold: a conditional write that records who holds the item and until when.
2. Pay: outside any database transaction, with an idempotency key.
3. Confirm: a conditional write that succeeds only if the hold is still yours.

-- hold: the seat is free, or its previous hold has run out
UPDATE seats SET status = 'held', user_id = :me,
       held_until = now() + interval '10 minutes'
 WHERE show_id = 42 AND seat_id = 'C7'
   AND (status = 'free' OR (status = 'held' AND held_until < now()));

-- confirm, after the payment succeeds
UPDATE seats SET status = 'booked', booking_id = :b
 WHERE show_id = 42 AND seat_id = 'C7' AND status = 'held' AND user_id = :me;

The important choice is lazy expiry: an expired hold counts as free in the next claim’s WHERE clause, at the moment someone wants the seat. A sweeper still runs every minute or so to reset rows and publish “seat freed” events, but correctness never depends on its timing; rely on it alone and a stalled job makes seats look sold when they are not. For counted stock, either store holds as rows and compute available = total − sold − unexpired holds, or decrement on hold and give units back on expiry. A late give-back undersells; it never oversells.

Confirm checks ownership, not the clock: if your hold ran out but nobody else claimed the seat, your late payment still books it. The expiry is a business trade: too short and honest buyers lose seats mid-OTP; too long and abandoned holds lock up stock during the rush.

Booking and payment usually live in different services, so the steps form a saga with compensating actions: release the hold, refund the charge. If a payment succeeds after someone else took the seat, confirm updates zero rows and the saga refunds automatically. Idempotency keys on payment and confirm stop a double tap or client retry from charging or booking twice. See multi-step workflows, two-phase commit vs sagas and idempotency.

What you gain: no long locks, and a fair, visible timer. What you pay: expiry rules, a compensation path and refunds. Where it breaks: when one hot item gets more hold attempts than its row can process. That is rung 7.

Say it: “A hold is a conditional write with an expiry the next claim checks lazily; pay outside the transaction, confirm idempotently, refund if the hold was lost.”

Rung 6: distributed locks need fencing

Sometimes the thing you protect is not a row you can write conditionally: a supplier’s inventory API with no compare-and-set, a file in object storage, a job that must run on exactly one worker. Then you reach for a lock service.

The usual single-instance Redis recipe is SET lock:seat:42:C7 <random-token> NX PX 30000: set only if absent, expire after 30 seconds so a crashed holder cannot block everyone, and release only if the value is still your token (a short Lua script, or DELEX … IFEQ on Redis 8.4+). Redis’s docs flag the catch with replicas: replication is asynchronous, so if the primary dies after granting a lock but before copying it, the promoted replica can grant it again.

The deeper problem applies to every lease. Martin Kleppmann’s 2016 critique of the multi-node Redlock algorithm walks through it: client 1 takes the lock, then pauses (a garbage-collection stall, a delayed packet) past the expiry; client 2 takes the lock and writes; client 1 wakes and writes too. Checking the expiry just before writing does not help, because the pause can strike right after the check. The fix is a fencing token: a number that grows with every grant and travels with every write, so the resource rejects any token lower than one it has already seen. Redlock does not produce one; a ZooKeeper zxid or an etcd revision can serve.

Rule of thumb: a resource that can check a fencing token can usually do a conditional write, so you never needed the lock. Use locks freely for efficiency (avoiding duplicate work), and for correctness only with fencing. More in distributed locking and Redis.

What you gain: mutual exclusion across systems that share no database. What you pay: another dependency, lease tuning, and safety only as good as the fence. Where it breaks: the first time a pause outlasts the lease on an unfenced resource.

Say it: “A paused client can outlive its lease, so I’d pass a fencing token the resource checks, or better, use a conditional write.”

Rung 7: extreme contention

The tatkal rush and the flash sale break every earlier rung for one reason: too many claims for one item, most of which must fail anyway. Suppose (illustratively) 100,000 people tap “book” in the first minute for 500 berths: 100,000 ÷ 60 ≈ 1,667 claims per second against one row’s 200-per-second ceiling. The backlog grows by about 1,467 a second, so after a minute some 88,000 requests are stuck behind one row lock, and 99.5% of them were never going to get a berth. Four tactics, usually combined:

Admit only what you can serve. A virtual waiting room in front of the booking flow gives each arrival a signed, timestamped place in line and lets people through at a set rate. Cloudflare’s Waiting Room, for example, is configured by “total active users” and “new users per minute”, admits in FIFO order by cookie, and refreshes queued browsers every 20 seconds. Fairness matters: Shopify’s first checkout throttle had customers poll at random, a lottery in which some waited 40 minutes during a 40-minute sale, until they ordered admission by first-arrival time. See backpressure and load shedding.

Fail the doomed requests cheaply. Keep an approximate stock counter in Redis and DECR it, or run a short Lua script that also enforces one unit per customer; Redis runs each script atomically. Below zero means sold out: reply at once, without touching the database. Redis is a gate, not the record: a failover can lose recent decrements, so the database’s conditional write stays the final check, and a reconciler compares the two.

Serialise claims per item. Publish each admitted claim to a Kafka topic keyed by item. Every claim for one item lands in one partition and is read in order by one allocator, so there are no locks and no retries: it checks stock in memory and writes results in batches. At an illustrative 50 µs per claim, one partition handles 1 ÷ 0.00005 = 20,000 claims per second. You pay with asynchrony (the user sees “you’re in line” and gets the result by polling or a WebSocket) and a pause while a failed consumer’s partition moves. See per-key queues.

Split the inventory. Spread 10,000 units across 20 bucket rows of 500 and send each claim to a random bucket: 20 × 200 = 4,000 claims per second. The price: a bucket can empty while others still have stock, so a loser tries another, and “sold out” means every bucket is empty.

One claim’s journey: (1) join the line; (2) get admitted at the rate the back end can serve; (3) the API decrements the Redis gate and answers “sold out” at once if stock is gone; (4) otherwise it publishes the claim, keyed by item; (5) one allocator per partition takes claims in order; (6) it batch-writes results to the record of truth; (7) a reconciler keeps the Redis counter honest.

Say it: “Most of these requests must fail, so I fail them early: waiting room, Redis gate, then one ordered lane per item.”

Choosing a rung

Estimate two numbers per contended item: peak claims per second, and how long one claim holds the item. Compare the first with 1 ÷ hold time to see whether one row keeps up; the shape of the rule says how far up the map you are.

Which classic problems use it

Common mistakes

• A mutex in application code. It protects one process; with 20 pods behind a load balancer, it protects nothing.
• Calling the payment provider inside the transaction. The lock is held for seconds and connection pools drain (rung 2’s arithmetic).
• A cache as the source of truth for stock. Reading “3 left” from Redis or a replica, then writing without a condition, oversells. So does a Redis counter with no database check behind it.
• Lease locks without fencing. A pause longer than the lease gives you two holders. Expiry is a liveness feature, not a safety one.
• Ignoring the affected-row count. A conditional UPDATE that matches nothing still returns success. Not checking it is check-then-act with extra steps.
• Unbounded retries without jitter. Immediate retries collide again. Cap attempts and add random backoff.

Cheat sheet

How to say it in the interview

“The risk is two buyers both getting seat C7. I won’t read availability and then write; the claim is one conditional update, set held where status is free, and zero rows means ‘taken’. Payment takes minutes, so the hold carries an expiry that the next claim checks lazily, and confirm is another conditional update with an idempotency key; if payment lands after the hold was lost, we refund. One hot row tops out near one over the lock time, about 200 claims a second at 5 ms, so for a big on-sale I add a FIFO waiting room, a Redis counter that turns away sold-out requests cheaply, and a partition per event so one allocator takes its claims in order. The database stays the record of truth.”

Why not SELECT … FOR UPDATE everywhere? It is safe, but every claimant waits and holds a connection. For a one-row rule, a conditional update gives the same safety in one round trip. Lock rows only when the decision spans several, always in ID order.

Optimistic or pessimistic? Estimate r·w: writes per second on the row times your read-to-write window. Well below 0.1, optimistic wins. Near 1 or above, retries dominate: use a conditional write, a lock or a queue.

Can I use a Redis lock instead of the database? For efficiency, yes. For correctness, only with a fencing token the resource checks, because a paused client can outlive its lease and a failover can lose the lock. If the resource is your own database, a conditional write is simpler and already fenced.

What does the losing user see? A fast, specific answer: “just taken, here are the nearest free seats”, a countdown while holding, and an automatic refund if payment lands after the hold was lost. In a flash sale, an honest queue position and an early “sold out”.

Where to go next

• Optimistic vs pessimistic locking: both philosophies in depth.
• Lost update problem: the anomaly behind check-then-act.
• Serializable isolation: what SSI catches, and what it costs.
• Database constraints: the cheapest referees.
• Distributed locking: leases, consensus-backed locks and fencing tokens.
• Multi-step workflows: sagas and compensation for hold, pay and confirm.
• Per-key queues: single-writer lanes and their failure modes.
• Design Ticketmaster and design a flash sale: this playbook applied end to end.

References and further reading

1. PostgreSQL documentation: Explicit lockingpostgresql.orgRow-level lock modes, automatic deadlock detection, locking in a consistent order, and why long-open transactions are a bad idea.
2. PostgreSQL documentation: SELECT, the locking clausepostgresql.orgFOR UPDATE with NOWAIT and SKIP LOCKED, and the warning that skipping locked rows gives an inconsistent view suited to queue-like tables.
3. PostgreSQL documentation: Transaction isolationpostgresql.orgHow READ COMMITTED re-checks the WHERE clause after waiting, the REPEATABLE READ concurrent-update error, and SSI’s 40001 failures and tuning advice.
4. PostgreSQL documentation: Range types, constraints on rangespostgresql.orgThe EXCLUDE USING GIST pattern, with btree_gist, that rejects overlapping room reservations.
5. Amazon DynamoDB Developer Guide: Optimistic locking with version numberdocs.aws.amazon.comVersion checks as conditional writes, ConditionalCheckFailedException, and the last-writer-wins caveat for global tables.
6. Redis documentation: Distributed locks with Redisredis.ioSET with NX and PX, token-checked release, and how asynchronous replication can hand the same lock to two clients.
7. How to do distributed locking (Kleppmann, 2016)martin.kleppmann.comLocks for efficiency versus correctness, process pauses that outlive a lease, and fencing tokens.
8. Cloudflare Waiting Room: Aboutdevelopers.cloudflare.comFIFO admission by cookie, total-active-users and new-users-per-minute thresholds, and 20-second refreshes for queued visitors.
9. Surviving flashes of high-write traffic using scriptable load balancers, Part I (Shopify Engineering)shopify.engineeringA flash sale that took down a database shard, the checkout throttle that followed, and how random polling turned the queue into a lottery.
10. Apache Kafka: Introductionkafka.apache.orgEvents with the same key land in the same partition and are read in exactly the order they were written.