Many hands on few rows

Every prompt here is the same problem in a different costume: far more requests than rows, all arriving at once, and all wanting the same few rows. The interviewer is testing whether you see that the scarce thing is not servers but the right to write one row, and whether you pick how writers take turns on purpose. The trap is to reach for "add more app servers" or "use a distributed lock" in the first minute. More servers only make the queue on the hot row longer, and the fix is to shrink who is allowed to reach that row at all.

Many hands, few rows: pick how writers take turns

When many requests fight over few rows there are three ways to make them take turns, and each fails differently when a spike arrives. Name the one you are picking, say what it costs at the spike, and say what you put in front of it so the spike never reaches it in full.

The numbers in this section are rough interview assumptions, not measurements: a row lock held for about 2 ms, and an in-memory owner doing about 1 microsecond of work per request.

A lock (pessimistic: `SELECT ... FOR UPDATE`): Writers wait in line on the row. One row then does at most 1 / hold time: 1 / 0.002 s = 500 writes/s, however many servers you add. Under a spike the line grows, every waiter holds a database connection while it waits, and the connection pool dies before the database does. Right for short transactions with moderate contention.
A version check (optimistic: `UPDATE ... WHERE version = ?`): Nobody waits; everyone tries, one wins, the rest see zero rows updated and retry. Nearly free when collisions are rare. Under a spike it is the worst of the three: with 100 writers on one row, one wins and 99 do the work again, so wasted work grows with the square of the crowd. Right when the rows are many and collisions are rare.
A single-writer queue per item: All writes for one item go to one owner, in order, so there is no conflict to detect at all. One core doing about 1 microsecond per request is 1 / 0.000001 s = 1,000,000 per second. The cost moves elsewhere: the queue depth becomes latency, the owner is one point that needs a standby, and items must be partitioned across owners. Right for a few hot items under a huge spike.
Always: shed at the front: Whichever you pick, reject early once the answer is known. A sold-out flag checked before the request reaches the row turns the tail of a spike into cheap reads.

Questions

Answer each one yourself before you open it.

01Design ticket booking for a concert on-sale: a 50,000-seat stadium, and 2 million fans arrive in the first minute.
The hinge is that 40 people want each seat, so the design is about who gets to try, not how fast the seat table is. A virtual waiting room admits buyers at the rate the seat inventory can absorb, an admitted buyer places a seat hold with a 10-minute expiry through a conditional update, and payment turns the hold into a sale.
These are interview assumptions; replace the arrival curve first with a real on-sale's traffic. 2,000,000 fans / 60 s ≈ 30,000 requests/s at the door. 2,000,000 fans / 50,000 seats = 40 fans per seat, so 39 of every 40 will leave without one whatever you build. At 4 tickets an order, 50,000 / 4 = 12,500 orders; selling out over 10 minutes is 12,500 / 600 s ≈ 20 holds/s, which one database handles easily. So the 30,000/s never touches the seat rows: the waiting room absorbs it and lets in about 20 buyers a second. The components are the waiting room (a token queue at the edge), a seat service doing UPDATE seats SET held_by = ?, held_until = now() + 10 min WHERE id = ? AND (status = 'free' OR held_until < now()), and payment that flips a live hold to sold.
Follow-up Two people click the same seat in the same millisecond. What happens?
Both run the conditional update, the database applies them one after the other, and only the first sees one row updated. The second sees zero rows and is told immediately to pick another seat, with no lock held across the user's think time. A buyer who never pays simply lets held_until pass, and the seat is free again for the next conditional update.
Learn more The order slip rail (queues) · Locks, latches and transactions
02Design a flash sale: 10,000 units of one phone go on sale at noon, and a million users hit buy in the first 10 seconds.
The hinge is that the stock is one hot counter, and one database row cannot take the spike. Keep the counter in memory with an atomic decrement (or split it into buckets), reject instantly once it hits zero, and write the winners' orders to the database asynchronously through a queue.
These are interview assumptions; replace the 10-second arrival window first. 1,000,000 users / 10 s = 100,000 requests/s. A locked stock row at about 2 ms a transaction does 1 / 0.002 = 500 decrements/s, so 100,000 / 500 = 200 times short. An in-memory atomic decrement (DECR on a single-threaded Redis) is a single writer at roughly 100,000 ops/s, which fits; or split the stock into 100 buckets of 100 units, and each bucket sees 100,000 / 100 = 1,000 requests/s. Only 10,000 requests can ever win, so 99% of the traffic should be rejected by a sold-out flag before it reaches the counter. The components are an edge gate with the sold-out flag, the in-memory counter, an order queue, and a consumer that writes orders idempotently to the database, which is the record of truth.
Follow-up The Redis primary fails over mid-sale. Can you oversell?
Yes, by the last few decrements that had not reached the replica, because replication is asynchronous. So the counter is only the gate: the order consumer does a final conditional decrement on the database row (WHERE stock > 0), and any order that loses there is refunded or waitlisted. Say the trade out loud: a handful of apologetic refunds beats putting a database lock back in the hot path.
Learn more Redis: one thread, many clients · Charged twice (idempotency) · Splitting the ledger (sharding)
03Design a hotel reservation system for 10,000 hotels.
The hinge is that contention here is low: bookings spread over millions of rows, one per hotel, room type and night. So each night's inventory is a row with an available count, a booking decrements every night of the stay in one transaction with a version check or WHERE available > 0, and the real load is search, served from a cache.
These are interview assumptions; replace the look-to-book ratio first. 10,000 hotels × 5 room types × 365 nights ≈ 20 million inventory rows. 1,000,000 bookings a day / 86,400 s ≈ 10 bookings/s, perhaps 100/s at a 10x peak, spread over 20 million rows, so two writers meeting on one row is rare and an optimistic check almost never retries. At 100 searches per booking, 1,000,000 × 100 / 86,400 ≈ 1,000 searches/s on average, about 10,000/s at peak, which is why availability search reads from a cache or replica and only the booking itself goes to the primary. The components are a search service over cached availability, a booking service with the inventory table, and payment.
Follow-up A guest books three nights, and night two sells out halfway through their booking.
All three decrements are in one transaction, so night two failing rolls back nights one and three and the guest sees "not available", never a partial stay. If you use locks instead, take them in date order, so two overlapping bookings cannot each hold a night the other needs and deadlock. Many hotels also allow a small deliberate overbooking, which is just a higher cap on the same row.
Learn more Transactions · Isolation levels (lab)
04Design a real-time leaderboard for a game with 10 million daily players: the top 100, and every player's own rank.
The hinge is that "what is my rank" must not scan or sort 10 million rows, so the scores live in an in-memory sorted structure (a Redis sorted set, which is a skip list) where an update and a rank lookup are both about log n. The single-threaded store is itself the single writer, so there is no locking to design.
These are interview assumptions; replace games per player per day first. 10,000,000 players × 10 games / 86,400 s ≈ 1,000 score updates/s, about 10,000/s at a 10x peak, well inside one in-memory node. log2(10,000,000) ≈ 23 steps per update or rank lookup. At about 100 bytes an entry, 10,000,000 × 100 bytes = 1 GB of memory. The components are the game servers posting final scores to a score service, ZADD into the sorted set, ZREVRANGE for the top 100 and ZREVRANK for my rank, with the durable score history in a database the set can be rebuilt from.
Follow-up Now it is 1 billion players, and one node's memory is not enough.
Shard by player id so every write goes to one shard. The top 100 is each shard's top 100 merged, and an exact rank is the sum over shards of how many scores beat mine (ZCOUNT), which is one call per shard. If that fan-out is too slow, keep the top ranks exact and give everyone else a percentile from a score histogram, because nobody checks whether they are 48,112,907th or 48,113,004th.
Learn more Redis: one thread, many clients · Trees (BST, balancing, heaps) · Splitting the ledger (sharding)
05Design the order matching engine for a stock exchange.
The hinge is fairness and determinism: orders for one symbol must be matched in exactly the order they arrived, every time. So each symbol's order book is owned by one thread in memory with no locks, fed by a sequencer that stamps every order into a replicated log, and the engine's output is itself a log of trades.
These are interview assumptions; replace the hottest symbol's share first. Say 1,000,000 messages/s at peak across all symbols, with the busiest symbol taking 5%: 1,000,000 × 0.05 = 50,000 messages/s on one book. A single thread doing about 1 microsecond per match handles 1 / 0.000001 = 1,000,000/s, so the hottest book is 50,000 / 1,000,000 = 5% busy. A database row lock at about 1 ms would be 0.001 / 0.000001 = 1,000 times slower per order and would not guarantee arrival order. The components are gateways, the sequencer and its log, matching threads partitioned by symbol, and downstream consumers of the trade log for market data, clearing and risk.
Follow-up The matching engine crashes during the trading day. What now?
A hot standby has been replaying the same sequenced log all along, and because matching is deterministic (no wall clock, no randomness inside it) it holds exactly the same book. It takes over from the last sequence number the primary published, and nothing is re-matched or lost. That determinism is why the single-writer design was chosen, not only its speed.
Learn more The ledger everyone reads (the log) · Who holds the pen (consensus and Raft) · The order slip rail (lab)

← Real-time and location Data systems: which trade-off is this? →