System design practice

Ticket Booking without Double-Booking

hard consistency concurrency caching sharding external-api

The database decides holds; the cache only shows seat maps.

Solve it in your browser Read the lesson first

Tickets for a stadium concert go on sale at 10:00 and tens of thousands of fans race for the same seats. A fan picks a seat on the seat map, the seat is held for them for 10 minutes while they pay, and the booking is confirmed once the payment goes through. Two fans must never end up with the same seat, and a seat whose hold expired must go back on sale.

Functional requirements

Use these names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the fan and the external payments provider (250 ms per call, up to 5k calls per second) and holds the traffic, requirements and tests. Add the booking service, where seats, holds and bookings live, the seat map cache, the connections and the three use cases.

Mind the write path: a relational database (PostgreSQL, MySQL, …) takes about 5k writes per second per primary. Read replicas do not add write capacity; only shards do (capacity { db shards 2 }, each shard with its own primary and replicas), or a partitioned store that is still strongly consistent.

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 13 min read

Learn it: Ticket Booking without Double-Booking #

Ticket booking: selling every seat exactly once #

What you'll learn #

The problem, explained #

A stadium concert goes on sale at 10:00 and tens of thousands of fans race for seats. Three use cases:

The non-functional requirements are the interesting part: two fans never get the same seat, nobody pays without a valid hold, and no seat is booked without a payment. On top of that:

The given file fixes two nodes: the fan (the client) and the payments provider, an external system with a capacity override of 250 ms per call and up to 5k calls a second. You cannot make it faster, only call it less often and at the right moment. The given also fixes the traffic (20k seat-map loads, 6k hold attempts and 500 confirmations a second) and four flow tests:

The latency, failure and cost limits then check that the design is sized for that traffic.

Back-of-the-envelope #

database writes (every hold, won or lost, plus bookings)
6.45k / s
writes one PostgreSQL primary takes
5k / s
through the booking service
26.5k rps
service replicas to stay under 70%
≈ 19
p99 of one payment call
≈ 700 ms

Split the rates by scenario, because each scenario touches different nodes.

FlowRateWhat it costs downstream
View seats, cache hit (97%)19.4k rpscache reads only
View seats, cache miss (3%)600 rps600 database reads + 600 cache writes
Hold seat (all scenarios)6k rps6k database writes, won or lost
Confirm, check hold500 rps500 database reads
Confirm, Paid (90%)450 rps450 payment calls + 450 database writes
Confirm, declined (7%)35 rps35 payment calls

Every hold attempt is a write, even the 60% that lose: the database has to evaluate the condition and decide. With the 450 bookings, that is about 6.45k writes a second. The simulation's PostgreSQL takes 5k writes a second per primary, so one primary is at 6.45k ÷ 5k ≈ 1.3: saturated. Two shards bring each to about 65%; read replicas add read capacity only, since every write still lands on its shard's one primary (in the model and in real single-primary databases).

The service carries everything: 20k + 6k + 0.5k = 26.5k rps. At about 2k rps per replica, 26.5k ÷ 2k ≈ 13 replicas just stay below 100%. The model adds queueing delay as utilisation (how busy a node is) climbs: a replica at 90% waits about ten times its base latency. Staying under roughly 70% takes 26.5k ÷ (2k × 0.7) ≈ 19, and "survive any node failure" re-runs the analysis with one replica fewer.

The cache is barely working: 20.6k operations a second against 100k per Redis replica. Its two replicas are for availability.

The payment provider is not a bottleneck (485 calls against 5k), but its 250 ms dominates the confirmation's p99: an idle hop's p99 is about 2.8× its mean, so one call is about 700 ms at p99. Hence the 1.5 s limit, with no room for a second slow call.

Cost. Each replica of each shard has a flat monthly price: $100 per service, $150 per cache, $400 per PostgreSQL replica, $50 per load balancer. Two PostgreSQL shards with a replica each are 4 × $400 = $1,600; the service fleet is the other big line. The $4,500 budget fits one sensible design: "just add replicas everywhere" fails on cost.

Concepts #

Conditional writes: let the database pick the winner #

The naive hold is read, then write: see the seat "free", write "held". Between the two, another fan does the same, and both believe they won: the classic check-then-act race.

A conditional write puts the check inside the write, so the database does both atomically (as one step) under its own row lock:

UPDATE seats SET status = 'held', held_by = :fan, hold_expires = now() + interval '10 minutes'
WHERE seat_id = :s AND (status = 'free' OR (status = 'held' AND hold_expires < now()));

One row changed: you hold the seat; zero rows: someone else got it first. The status = 'held' check matters: without it, a booked seat would look free again once its old deadline passed. The row lock runs two concurrent UPDATEs one after the other, and the second re-checks the WHERE clause after the first commits, finding the seat taken.

Trade-off: writers to a very hot row wait in line. Seats are fine, each its own row; a single counter decremented by a whole crowd is not (see the Flash Sale lesson).

Deep dive The pattern in Proschi

A single write whose result splits into scenarios:

title "Conditional write"
user "User"  [Actor]
api  "API"   [REST API] x2
db   "Store" [PostgreSQL] x2
user -> api
api -> db : SQL

usecase "Claim item" {
  user -> api : POST /items/42/claim
  api  -> db  : UPDATE item SET owner WHERE owner IS NULL
  alt "Claimed" when "one row changed" {
    db  --> api  : 1 row
    api --> user : 201
  } alt "Already claimed" when "zero rows changed" {
    db  --> api  : 0 rows
    api --> user : 409
  }
}

Holds that expire by themselves #

A hold is a lease: a lock with a deadline. It can end through a background job that scans for expired holds and releases them, or through a deadline in the row that the conditional write treats as free once passed (the hold_expires < now() branch above).

The deadline has no moving parts. If a sweeper is late or down, seats stay stuck; with a deadline, the next fan simply overwrites the expired hold. A tidy-up job may still run, but correctness never depends on it.

When not to use it: if expiry must trigger a side effect (refund a deposit, notify someone), something still has to run at expiry time.

Optimistic versus pessimistic locking, and why not Redis #

Pessimistic locking takes a lock before acting (SELECT … FOR UPDATE in a transaction, or a distributed lock service) and holds it while working. Optimistic locking acts without a lock and fails if something changed meanwhile, usually by checking a version column in the WHERE clause. The conditional UPDATE is optimistic in spirit: it never waits for a fan to decide, it accepts or rejects one atomic write.

Holding a database lock for the 10 minutes a fan spends paying would be absurd, so the hold is data (a deadline in the row), not a lock held open.

Sharding for writes #

Sharding splits a table across independent databases, each owning a subset of keys with its own primary: the only way to add write capacity to a single-primary database. The price: cross-shard queries get harder, and every shard needs a full replica set.

The key question is the shard key. Every operation here touches one seat, so (eventId, seatId) is natural: a hold and its booking land on the same shard, and no transaction crosses shards. Sharding by eventId alone would put the one hot concert on a single shard.

title "Sharded writes"
api "API"   [REST API]   x2
db  "Store" [PostgreSQL] x2 "Partitioned by item id"
api -> db : SQL
capacity {
  db shards 2
}

Designing it step by step #

1. Scope the problem. Confirm the three use cases and the guarantees: no double booking, no charge without a hold, no booking without a charge. Ask how stale the map may be (a couple of seconds), how long a hold lasts (10 minutes), and the peak: 20k map loads, 6k holds and 500 confirmations a second. Write those on the board; the design falls out of them.

2. High-level design. A load balancer, a stateless booking service, a seat-map cache, one strongly consistent database for seats, holds and bookings, and the payment provider. Draw three flows:

3. Deep dive. This is where you spend most of the interview.

Who decides? Walk through the race with two fans and show the conditional write cannot let both win. Then explain why the cache stays off the hold path, even for invalidation: a DEL of the cached map on every hold puts an eventually consistent store on the critical path, and buys nothing, since a map rebuilt from a lagging replica can be stale anyway. A short TTL keeps the map close enough.

Ordering in confirm. Check the hold first, so an expired hold is rejected before any charge (that scenario never calls the provider). Charge next. Book last, with another conditional write (WHERE holdId = … AND still held by this fan), so a payment that raced past the deadline cannot overwrite someone else's fresh hold.

Write capacity. Count writes (about 6.5k a second) against one primary's capacity, explain why read replicas do not help, and shard by seat.

Deep dive Strongly consistent partitioned stores

A partitioned store that is still strongly consistent is the alternative: Spanner, CockroachDB, or DynamoDB with conditional writes and strongly consistent reads. In this exercise the simulation tags DynamoDB as an eventual store, so the test that forbids eventual stores on the hold path rejects it.

Sizing. Size the service from the total request rate with headroom for one lost replica, keep the cache at two replicas, and check the bill.

4. Wrap up. Summarise the guarantees and where each is enforced. With more time: a virtual waiting room for bigger crowds, and a reconciliation job matching payments to bookings.

Common mistakes #

Checking the cache before holding (wrong/hold-checks-cache). A harmless-looking optimisation: if the seat map shows the seat taken, skip the database. But that cache may be two seconds stale, and it puts an eventually consistent store on the hold path. In production it turns fans away from free seats, and if anyone ever trusts the cached "free" without the conditional write, it sells a seat twice. Caught by "A strong store, not the cache, decides who holds a seat" (the hold calls an eventual store).

Holds in DynamoDB (wrong/holds-in-dynamodb). Partitioned NoSQL stores scale writes well, tempting at 6.5k writes a second. But default reads are eventually consistent, and "who holds this seat" must be read and written consistently. Real DynamoDB offers conditional writes and strongly consistent reads; the simulation tags it as eventual, and this problem wants the decision in a store that is strong by default. Caught by "A strong store, not the cache, decides who holds a seat", and the confirmation tests fail for the same reason.

Book before charging (wrong/book-before-charge). Write the booking, then call the provider. A declined card leaves a booked seat nobody paid for, and the compensating write to undo it can itself fail. Caught by "A seat is booked only once it is paid", which wants the last strong-store call of "Paid" after payments.

Read replicas instead of shards (wrong/replicas-instead-of-shards). Four PostgreSQL replicas cost the same as two shards of two, but every write still goes to one primary: 6.5k writes on a 5k primary is about 129% utilisation, and a saturated node fails the latency requirement of every use case that touches it. Caught by p99 of Hold seat < 130 ms (and the other latency limits and the failure test with it).

Classic mistakes beyond the tests: holding a SELECT … FOR UPDATE lock while the fan pays, a cleanup job as the only way holds expire, and no idempotency key on the payment call.

In the interview #

Likely follow-ups and short answers:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems