Locking: stop double booking and overselling

Many popular design questions have a small stock and a large crowd: train tickets, movie seats, or a phone in a flash sale (a short sale with very little stock). The interviewer asks: "Two users press Book on the last seat at the same moment. What happens?" This question tests if you know that two requests can overlap, and if you have a safe way to let only one win.

A weak answer checks if the seat is free, and then books it. That has a gap, and both users can win. A strong answer closes the gap in the database, explains what happens to the loser, and handles the user who takes five minutes to pay.

At SDE-1 level you should know the problem and one fix. At SDE-2 level you should compare the fixes and handle holds. At SDE-3 level you should also say what limits the speed under a very large crowd.

Think of the last seat on a bus, and two conductors with the same ticket book. If each looks at the book, sees "seat 5 free" and writes a ticket, the seat is sold twice. The fix is that only one conductor may handle seat 5 at a time. Another fix is that each conductor, when writing the ticket, checks again that the seat is still free.

In a database the same bug looks like this. The app runs two statements:

SELECT status FROM seats WHERE id = 5;                       -- returns 'free'
UPDATE seats SET status = 'booked', user_id = 42 WHERE id = 5;

SELECT reads rows. UPDATE changes rows, and WHERE chooses which rows. Between the two statements there is a gap. Another request can read 'free' inside that gap. Both then write, and both users are told "booked". This is a double booking. The same bug with a count is overselling: the shop sells 101 items when it has 100. It is the lost update from the lesson on transactions: two requests read the same value, and the second write replaces the first. A transaction alone does not close the gap at the default Read Committed level. A higher level (Repeatable Read or Serializable) would stop the second write with an error, and the app would retry. The four tools below are simpler and clearer for this problem.

There are four tools. Each one closes the gap in a different way.

1. Atomic update

An atomic change is one step that nothing can interrupt. Put the check and the write in one statement. This is a conditional update: the change happens only if the condition is true.

UPDATE seats SET status = 'booked', user_id = 42
WHERE id = 5 AND status = 'free';

The database tells you how many rows it changed. If it is 1, you won the seat. If it is 0, someone else got it. In Postgres at the default level, a second request for the same row waits for the first to finish. It then checks the WHERE condition again on the new version of the row. It now sees 'booked', so it changes 0 rows. For stock, write UPDATE products SET stock = stock - 1 WHERE id = 7 AND stock > 0. A rule such as CHECK (stock >= 0) on the column is a good second protection: the database refuses any change that breaks it.

2. Pessimistic locking

Pessimistic locking assumes a clash will happen, so it takes a lock first. A lock stops others from changing the row. SELECT ... FOR UPDATE locks the rows it reads until the transaction ends. Others who want to change or lock the same row must wait.

BEGIN;
SELECT status FROM seats WHERE id = 5 FOR UPDATE;   -- others wait here
-- the app checks the status and applies its rules
UPDATE seats SET status = 'booked', user_id = 42 WHERE id = 5;
COMMIT;

Use it when the decision needs more than one simple condition, for example when you read several rows before you write. The costs: others wait, and the lock stays until the commit, so keep the transaction short and never wait for a user or a payment inside it. Two transactions can also block each other forever: this is a deadlock. Transaction 1 holds seat 5 and wants seat 6. Transaction 2 holds seat 6 and wants seat 5. Postgres notices, and stops one of them with an error. To avoid it, always lock rows in the same order, for example by seat number from low to high.

3. Optimistic locking

Optimistic locking assumes a clash is rare, so it keeps no lock while the user thinks. It adds a version number to the row. You read the row and its version. When you write, you say "only if the version is still the one I read", and you raise the version:

UPDATE seats SET status = 'booked', user_id = 42, version = version + 1
WHERE id = 5 AND version = 7;

If 0 rows change, someone else changed the row first. You reload and decide again, or tell the user. It suits cases where the user thinks for a while and clashes are rare, such as two people editing the same profile. The cost: when clashes are common, many attempts fail and the work is wasted.

4. Unique constraint

A unique constraint tells the database that no two rows may have the same value in some columns. Create a bookings table with UNIQUE (show_id, seat_no) and insert one row per booking. The second insert for the same seat fails with a "unique violation" error, and the loser sees "seat taken". The database checks this itself, so no gap exists. Never write "count the rows, and insert if zero": that has the same gap as before. With INSERT ... ON CONFLICT DO NOTHING the insert is skipped instead of failing, and the row count (0 or 1) tells you who won. Use a unique constraint whenever the rule is "at most one booking per seat".

Seat holds that expire

A user needs minutes to pay. You cannot keep a lock that long. Instead, save a hold in the row: a short reservation with an end time. Take a hold with one conditional update:

UPDATE seats
SET status = 'held', held_by = 42, hold_until = now() + interval '5 minutes'
WHERE id = 5 AND (status = 'free' OR (status = 'held' AND hold_until < now()));

After payment, confirm the seat:

UPDATE seats SET status = 'booked'
WHERE id = 5 AND status = 'held' AND held_by = 42 AND hold_until > now();

An expired hold counts as free, because of the hold_until < now() condition. So no cleanup job is needed. Any query that counts free seats must use the same condition. Use the database clock (now()), not the clock of each app server. If the confirm statement changes 0 rows, the hold ended and maybe someone else has the seat. If the user already paid, you must refund. To make this rare, make the hold longer than a normal payment, and extend it when the user starts to pay.

To hold several seats together, run the same conditional update inside one transaction, with id IN (5, 6, 7). If fewer than 3 rows changed, run ROLLBACK. The user then gets all the seats or none.

Tatkal is the last-minute booking window of Indian Railways. Many people try to book the few seats at the moment it opens. Here Tatkal opens at 10 am for one train.

Assumptions (made up to teach with):

• The train has 1,000 seats. Each seat is one row.
• 200,000 people press Book within the first 60 seconds.
• One update holds its row lock for 2 milliseconds (ms). The gap between a SELECT and its UPDATE is 20 ms.
• A hold lasts 5 minutes. A payment takes up to 3 minutes. 30% of people who get a hold do not pay.

Step 1: the load. Attempts = 200,000 / 60 = 3,333 per second. If people choose seats evenly, each seat gets 3,333 / 1,000 = 3.3 attempts per second.

Step 2: read, then write (the predict box). Look at one seat. The first attempt reads "free". A second attempt also reads "free" if it arrives inside the 20 ms gap before the first UPDATE. The chance is about 3.3 attempts per second x 0.020 seconds = 0.067. This is a rough estimate. For 1,000 seats, 1,000 x 0.067 = 67 seats would be sold to two users. So both users can win. The fix is to remove the gap with one conditional update.

Step 3: atomic update. One statement per attempt. One row can take 1,000 ms / 2 ms = 500 updates per second. Each seat gets 3.3 per second, far below 500. Of 200,000 attempts, 1,000 win and 199,000 change 0 rows, so they are told "seat taken" quickly.

Step 4: a single counter would fail. Suppose we used one "seats left" row for the whole train. All 3,333 attempts per second hit one row. The limit is 500 per second, so the load is 3,333 / 500 = 6.7 times too high. Requests wait too long and fail. One row per seat avoids this.

Step 5: holds. The first 1,000 winners get a hold for 5 minutes (300 seconds). Payment takes up to 3 minutes (180 seconds), so there are 120 seconds to spare. 30% do not pay: 1,000 x 0.30 = 300 seats. Their holds end after 300 seconds, and the condition hold_until < now() lets the next buyers take them. Without expiry, 300 of 1,000 seats, which is 30% of the train, would stay held forever.

Step 6: the last protection. A UNIQUE (train_id, seat_no) constraint on the bookings table helps here. Suppose some code path forgets the status check. The database still refuses a second booking for the same seat.

• It solves: two buyers getting the same seat or the last item, and seats that stay blocked by users who leave.
• It costs: some buyers are told "taken" or must retry, and a slow payer can lose a seat when the hold ends.
• I would change it when: one row gets more than 500 updates per second (the limit here), or when holds end too soon. Then I make them longer or extend them.

"A transaction alone prevents double booking." Not at the default level. A SELECT and then an UPDATE inside a transaction still leave the gap. You need an atomic update, a lock, a version check or a unique constraint (or a higher isolation level with retries).

"Optimistic locking is faster than locking, so always use it." It is faster only when clashes are rare. On a popular seat, most attempts clash. Each failed attempt wastes the work and then retries.

"Lock the seat while the user pays." A lock held for minutes makes everyone else wait, and an app that hangs can keep it held. Use a hold with an end time. It is only a saved row, not a lock.

1. Name three ways to stop two users from booking the same seat. Say one cost of each.
2. A busy product row takes 3 ms per update. (a) How many updates per second can one row take at most? (b) A sale sends 6,000 attempts per second to this one row. How many times too high is that? (c) The stock is 100 and the update has AND stock > 0. How many attempts succeed?
3. Your seat hold lasts 2 minutes, but payment through the bank page often takes 3 minutes. What goes wrong, and what do you change?