Interview patterns · Design 7

Contention and double booking

How to stop two users taking the same seat, room or last item: pessimistic and optimistic locking, conditional writes, holds with a TTL, per-key queues and fenced locks.

AdvancedInterview priority: High40 min
On this page
  1. The problem: two people, one seat
  2. Signals that you are facing it
  3. The toolbox
  4. Worked example: a flash sale of 5,000 phones
  5. When not to use these tools
  6. Which case studies use it
  7. In the interview
  8. Quiz

The problem: two people, one seat

A concert has 20,000 seats, and at 10:00 a million fans try to buy them. The booking code does the obvious thing:

seat = db.query("SELECT holder FROM seats WHERE id = %s", (seat_id,))
if seat.holder is None:
    db.execute("UPDATE seats SET holder = %s WHERE id = %s", (user_id, seat_id))
    return "booked"
return "taken"

Alice and Bob click seat 12A within the same millisecond. Both SELECTs run before either UPDATE, both see holder = NULL, both write, and both are told "booked". The second write silently overwrites the first. This is a race condition (the result depends on the timing of concurrent operations), and this shape, read, decide, then write, is the most common one in system design.

Read-then-write lets two users book the same seat

Contention is many requests competing for the same piece of data. Low contention (two people rarely want the same hotel room) and high contention (a million people want 20,000 seats in the first minute) call for different tools.

Signals that you are facing it

  • Limited inventory: seats, rooms, appointments, stock, coupons, usernames.
  • "Exactly once" or "no more than N": one driver per ride, one winner per auction, balance never negative.
  • Spikes on the same item: ticket on-sales, flash sales, limited drops.
  • Multi-step flows that hold something: pick a seat, then pay within 10 minutes.

Say early: "Two users can race for the same seat, so the check and the write must be one atomic step, and I'll hold seats with a timeout during payment."

The toolbox

Pessimistic locking

Lock the row before reading it, so no one else can change it until you commit. In SQL, SELECT ... FOR UPDATE inside a transaction:

BEGIN;
SELECT holder FROM seats WHERE id = '12A' FOR UPDATE;   -- Bob's transaction waits here
UPDATE seats SET holder = 'alice' WHERE id = '12A';
COMMIT;                                                 -- now Bob reads 'alice'

Catch: other transactions wait while the lock is held, so throughput on one row is limited by how long you hold it (5 ms per transaction means at most about 200 a second on that row). Never hold a database lock across a network call or while a user decides. Locking several rows in different orders causes deadlocks (two transactions each waiting for the other), which the database breaks by aborting one.

Optimistic locking

Don't lock; detect conflicts at write time. Each row has a version number. Read it, then write only if it hasn't changed:

UPDATE seats SET holder = 'alice', version = version + 1
WHERE id = '12A' AND version = 7;     -- 1 row: success. 0 rows: someone else won; reread and retry

Catch: under heavy contention most attempts fail and retry, wasting work. It shines when conflicts are rare (editing a profile, updating a document's settings).

Conditional writes

Often you don't need a version at all: put the business rule into the write's condition, and let the database apply it atomically.

A conditional write lets the database pick one winner

StoreAtomic conditional write
SQLUPDATE seats SET holder = ? WHERE id = ? AND holder IS NULL, then check the affected row count
SQLINSERT INTO bookings (event_id, seat_id, user_id) with a UNIQUE (event_id, seat_id) constraint; the second insert fails
SQL, countersUPDATE items SET stock = stock - 1 WHERE id = ? AND stock > 0
DynamoDBPutItem / UpdateItem with a ConditionExpression such as attribute_not_exists(holder)
RedisSET seat:12A alice NX (only if not set); DECR with a check, or a Lua script for multi-step logic

This is usually the best default: one round trip, no lock held between steps, and the database is the referee. A unique constraint is the strongest version, because it holds no matter which code path writes.

One caution on isolation levels: Postgres and MySQL default to isolation levels (read committed and repeatable read) that do not stop the read-then-write race in the opening code. The SERIALIZABLE level does, by aborting one of the transactions, which then must retry. A conditional write or FOR UPDATE is more explicit.

Holds with a TTL

Buying a ticket takes minutes: pick seats, enter details, pay. You can't lock a row that long, but you must stop someone else buying the seat meanwhile. Use a reservation: a short-lived hold.

-- take a hold for 10 minutes, only if the seat is free or its old hold has expired
UPDATE seats SET status = 'held', holder = 'alice', held_until = now() + interval '10 minutes'
WHERE id = '12A' AND (status = 'free' OR (status = 'held' AND held_until < now()));

-- on payment success, confirm only if the hold is still Alice's and still valid
UPDATE seats SET status = 'sold'
WHERE id = '12A' AND holder = 'alice' AND status = 'held' AND held_until > now();

Expired holds need no cleanup job to become available, because the condition treats them as free; a background job can still tidy them for reporting. The same pattern books hotel rooms, restaurant tables and driver assignments.

Serialise per key

When one item is extremely hot, stop many servers fighting over it: route every request for that key to one place that handles them one at a time. For example, put booking requests on a Kafka topic partitioned by event_id, and have one consumer per partition apply them in order from memory, writing results to the database. There is no contention because there is no concurrency for that key. Catch: one consumer's speed is the ceiling for that key, users wait for an asynchronous answer, and the consumer needs a clean failover.

A virtual waiting room is the same idea at the front door: admit users to the purchase flow at a controlled rate (say 2,000 a minute) and hold the rest in a queue page.

Distributed locks, with fencing tokens

Sometimes the thing being protected is not a single database row: a job that must run on one machine, or a file in object storage. A distributed lock gives one client exclusive rights, usually as a lease that expires automatically (so a crashed client doesn't hold it forever). In Redis: SET lock:job42 <random-id> NX PX 30000, released only if the value still matches. ZooKeeper and etcd provide locks built on consensus.

Leases have a deadly flaw: a client can pause (a long garbage-collection pause, a VM migration, a network stall) beyond its lease without knowing it. Another client takes the lock, and the first one wakes up and writes anyway. The fix is a fencing token: a number that increases each time the lock is granted, which the client sends with every write, and which the storage checks.

A fencing token stops a paused lock holder from writing

ZooKeeper's zxid and etcd's revision numbers work as fencing tokens. A plain Redis lock does not provide one, so on its own it is fine for efficiency (avoiding duplicate work) but not for correctness.

Why not Redlock? Redlock (locking a majority of independent Redis nodes) still issues no fencing token, and its safety depends on timing assumptions (bounded pauses, clocks that don't jump) that real systems break, as Martin Kleppmann's well-known critique shows. Use it for efficiency at most; for correctness use fencing or a conditional write.

Comparing the tools

ToolGood atWeak atUse when
Pessimistic lock (FOR UPDATE)Simple; no retriesWaiting; deadlocks; one row ~hundreds/sShort transactions, moderate contention
Optimistic (version)No locks held; cheap when rareRetries pile up under contentionConflicts are rare
Conditional write / unique constraintOne atomic step; DB is refereeOne row's write rate is still a ceilingThe default for claims and counters
Hold with TTLMulti-minute flowsHolds expiring mid-paymentCheckout, booking flows
Serialise per keyExtreme hot keysAsync answers; single consumerFlash sales, auctions
Distributed lock + fencingResources outside one DBNeeds storage that checks tokensJobs, external resources

Worked example: a flash sale of 5,000 phones

  • 300,000 people click "buy" within the first minute; peak 20,000 attempts a second.
  • A single row stock = stock - 1 WHERE stock > 0 holds a row lock for 1–2 ms per transaction: roughly 500–1,000 decrements a second, far below demand. Requests queue on the lock and time out.
  • Option A, buckets: split stock into 20 rows of 250 units; each request picks a random non-empty bucket. Capacity rises about 20× to 10,000–20,000 a second. "Sold out" means all buckets are empty, so the last few units take a little searching.
  • Option B, Redis first: keep the count in Redis, where DECR is atomic and a node handles 100,000+ operations a second. A request that gets a result ≥ 0 has won a unit and creates the order (with a hold) in the database; a result below 0 means sold out. Redis must be the single gate, and you need a recovery plan if Redis fails over mid-sale (rebuild the count from the orders table).
  • Option C, waiting room: admit 5,000–10,000 users a minute into checkout; the database sees a calm rate.
  • Real systems combine C with A or B. Only 5,000 people can succeed; the design's job is to tell the other 295,000 quickly and correctly.

When not to use these tools

  • No shared limit. If two users editing their own profiles never collide, locking adds cost for nothing.
  • Conflicts can be merged. Collaborative editing, shopping carts and counters can often combine concurrent changes (with operational transforms, CRDTs or commutative updates) instead of rejecting one.
  • Overselling is acceptable and cheaper. Airlines oversell flights on purpose; some shops accept a tiny oversell and apologise. That is a business decision, but name it.
  • A distributed lock when the database can decide. If the data is in one database, a conditional write or FOR UPDATE is simpler and safer than a separate lock service.

Which case studies use it

In the interview

Your turn: meeting-room booking

A company's room-booking app lets people book rooms in 30-minute slots, but also arbitrary ranges like 10:15–11:40. Two people must never hold overlapping bookings for the same room. Contention is low. How do you enforce it?

Compare with our answer
  • For fixed slots, one row per (room, slot) with a unique constraint: the second insert fails.
  • For arbitrary ranges, a unique constraint can't detect overlaps. Options: Postgres exclusion constraint (EXCLUDE USING gist (room_id WITH =, during WITH &&) on a time range column; equality on a plain column inside a GiST constraint needs CREATE EXTENSION btree_gist), which rejects overlapping ranges atomically.
  • Or lock the room's row with SELECT ... FOR UPDATE, check for overlaps, insert, commit: fine because contention is low and the transaction is short.
  • Avoid an application-level "check then insert" without a lock: it races.
  • Return a clear "slot taken" error and let the user pick again.

A strong answer mentions: the database enforces it, not just app code · unique constraint for fixed slots · exclusion constraint or row lock for ranges · low contention makes pessimistic locking acceptable · no unguarded check-then-insert.

Your turn: the requirement changes

Your ticketing system uses UPDATE ... WHERE holder IS NULL on a seats table and works well. Now a superstar's tour goes on sale: 2 million fans for 60,000 seats, most wanting the best few sections, at 10:00 sharp. What breaks, and what do you add?

Compare with our answer
  • Conditional writes stay correct, but the database load explodes: millions of seat-map reads and attempts in the first minutes, concentrated on a few sections (hot rows and hot pages).
  • Add a virtual waiting room: admit users at a rate the booking system can sustain, in random or arrival order, and show queue position.
  • Serve the seat map from a cache refreshed every second or two; the conditional write is the real check, so a stale map only means an occasional "just taken".
  • Consider serialising per event or section (a partitioned queue with one consumer each) or best-available allocation (the system picks seats) to cut conflicts.
  • Holds with TTL during payment, rate limits per user, and bot protection.

A strong answer mentions: correctness holds but capacity fails · waiting room / admission control · cached seat map with the write as the check · per-key serialisation or best-available · holds with TTL · bot and per-user limits.

Contention on one page
  • The bug: read, decide, write. Two readers both see "free".
  • Default fix: one atomic conditional write (WHERE holder IS NULL, stock > 0) or a unique constraint; check rows affected.
  • Pessimistic (FOR UPDATE): simple, but waits and deadlocks; never across user think time. One hot row ≈ hundreds/s.
  • Optimistic (version column): no locks; retries explode under contention.
  • Default isolation levels don't stop the race; SERIALIZABLE does, with retries.
  • Long flows: holds with held_until; confirm conditionally; refund if the hold was lost.
  • Hot items: buckets, Redis DECR as gate, per-key serialisation, waiting room.
  • Distributed locks are leases; a paused holder can still write. Use fencing tokens checked by storage.
Check what stuck

1. A booking service reads a seat's status and, if it is free, updates it to booked. Under load, some seats are sold twice. Which change fixes it most simply?

2. A team uses optimistic locking with a version column on a flash-sale stock row. During the sale, most purchases fail after several retries. Why?

3. A checkout holds a seat for 10 minutes. A customer's payment succeeds after 12 minutes, and the seat was sold to someone else at minute 11. What should the system do?

4. A worker takes a Redis lock with a 30-second lease, then pauses for 45 seconds during garbage collection, wakes up and overwrites a file another worker has since written. What prevents this?

5. One stock row receives 15,000 purchase attempts a second, and each transaction holds the row lock for about 2 ms. Roughly what is the ceiling, and what helps?

6. Room bookings can be any time range, and two bookings for the same room must never overlap. Which database feature enforces this most directly?

7. Why is a conditional write usually preferred to a distributed lock for claiming a seat stored in one database?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.