Case study: Ticket booking

Seats are the classic small stock with a big crowd. The interviewer says: "Design a ticket booking app for trains and cinemas. Tatkal opens at 10 am, and everyone arrives in the same minute. Two people must never get the same seat."

A weak answer draws a seat table and says "use a lock". It does not say what happens while the customer pays, or what happens to the other 199,000 people. A strong answer treats a seat as a small state machine. It holds a seat for a few minutes, lets the hold end by itself, and keeps the crowd away from the part that books seats. It also says what happens when a payment finishes late.

At SDE-1 level you should follow one booking from the seat map to the ticket. At SDE-2 level you should add holds, expiry and the numbers. At SDE-3 level you should add a fair line for the crowd, late payments, and the version for hotel rooms.

Quick recap (lessons 22, 37, 58 and 66). A conditional update such as UPDATE ... WHERE status = 'free' lets only one buyer win a seat. A hold is a saved reservation with an end time, and an ended hold counts as free. One row takes about 500 updates per second when each update takes 2 ms. Redis is a fast store in memory. A sorted set keeps items in order of a score, and INCR adds 1 in one atomic step. A queue lets slow work finish after the answer. A state machine is a list of states with a table of legal moves.

Think about a railway booking counter. A board shows which berths are free. A clerk marks a berth (a bed in a train) "held" in pencil and takes the customer's money. Then the clerk writes the name in pen. If the customer walks away, the pencil mark is rubbed out. When a big crowd waits outside, a guard at the door lets in a few people at a time.

In this lesson, Tatkal is the last-minute booking window of Indian Railways. We use these assumptions: it opens at 10 am for one train, and a seat is sold for the whole journey. We also cover cinema seats.

The parts

• Seat map service. It shows each seat as free, held or booked. Readers get it from a cache that is at most 1 second old. An old map only costs a "seat taken" answer.
• Seat service. It is the only writer of seat state. It uses a SQL database, split by show or by train and date (sharding, lesson 43).
• Payment service. It takes the money. A payment can finish late, so the booking waits for it.
• Ticket queue. After the booking is confirmed, a queue (lesson 58) sends the ticket PDF, the SMS and the email.
• Waiting room. It keeps the crowd away from the seat service. It is described below.

A seat as a state machine

A seat has three states. A seat row holds the state, the booking that owns it, and the end time of a hold.

With 3 states there are 3 x 2 = 6 pairs of different states. The table allows 4. The other 2 are illegal: FREE to BOOKED (a seat must be held first) and BOOKED to HELD. Each move is one conditional update (lesson 66).

The hold

A customer picks 2 seats. The seat service takes both with one conditional update, inside one transaction. A seat counts as free when it is FREE, or when it is HELD and its end time has passed. If fewer rows change than the seats asked for, it rolls back, so the customer gets all seats or none. The seats are taken in order of seat number, so two customers cannot block each other (lesson 22).

Because an ended hold counts as free, no cleanup job is needed to free the seats. The seat map must use the same rule. The database clock decides the time, not the clock of an app server.

After payment, a second conditional update turns the seats from HELD to BOOKED, only if the hold is still ours and has not ended. A unique constraint on (show, seat) for booked seats is the last guard against a double sale.

Where does the hold live?

A hold could be a Redis key with a time to live (lesson 37). That is fast. But a lost key lets a second buyer take the seat, and a restart can lose recent holds. So the hold lives in the database, which is the truth. Redis keeps only hints, such as the seats-left counter below.

Payments that finish late

A UPI payment (lesson 68) can stay pending for minutes. Suppose the hold ends while the payment is still pending. The seat could go to another customer, and then the first customer's money arrives.

The rules:

1. When the customer starts to pay, extend the hold by a short time, up to a limit. Extend it again while the gateway says pending.
2. When the result arrives, run the confirm update. If it changes 1 row per seat, the seats are booked.
3. If it changes fewer rows, the seat is gone. Refund the money with the same idempotency key (lesson 61), and tell the customer.

A gateway can report a payment as failed after a timeout, and the payment can still succeed later (see Sources). So the confirm update, not the payment result, decides the booking.

The waiting room

At 10 am, far more people come than the seat service can serve. A waiting room is a line in front of the seat service (a queue, lesson 58). It works in four steps:

1. Join. Each person joins the line and gets a place. Joining is cheap work, because it only writes one small record. The line is a sorted set in Redis: the score is the place.
2. Fair order. People who join in the first 30 seconds get a random score, so a random place. This way, how fast a person taps, or a script, does not decide who goes first. People who join later get a score after all of those, so they go behind them in the order they arrive. The line keeps one place for each account.
3. Admit. A job takes people from the front of the line at a steady rate. The rate is what the seat service can take. Each admitted person gets a signed admit token. It is a short text that your server signs with a secret key (as in lesson 69), with an end time. The hold call refuses any request without a valid token. So nobody can skip the line by calling the seat service directly.
4. Sold out. A counter in Redis holds the seats left. Each hold lowers it with DECR, which is INCR in the other direction. Once each second, a small job counts the free seats in the database with the rule above, which adds back the ended holds, and sets the counter to that number. When the counter reaches 0, a small status file says "sold out", and everyone in the line sees it at once. The counter is only a hint. The database decides each seat.

Everyone who is not admitted does not touch the seat service. They see their place, or "sold out". This is the "say no, quickly" idea: the answer is cheap.

The hotel version

A hotel has no seat numbers. A guest asks for "a Deluxe room for 3 nights". The stock is a count for each hotel, room type and night: "rooms left". Three things change:

• One update for each night. For each night in order of date, run UPDATE ... SET rooms_left = rooms_left - 1 WHERE ... AND rooms_left > 0. If any night changes 0 rows, roll back. The guest gets all nights or none.
• A hold needs a job. Each hold is a booking row with an end time. A seat can be freed by a condition, because the row says who holds it. A count cannot say which hold ended. So a timer job moves ended holds to EXPIRED with a conditional update and adds the rooms back in the same transaction.
• A shared row. Every booking for that night updates one row. The limit is the same 500 updates per second. It is far above the load of one hotel.

Assumptions (made up to teach with, not real data):

• One train with 1,000 seats. Tatkal opens at 10 am. 200,000 people arrive in the first 60 seconds. Each booking asks for 2 seats.
• Each waiting person refreshes the seat map every 5 seconds.
• A hold attempt uses 8 ms of CPU. A join of the waiting room uses 1 ms. A server has 4 cores, and we plan for 70% busy (lesson 15).
• The hold lasts 5 minutes. A payment takes up to 3 minutes, but a UPI payment can stay pending for 6 minutes. 30% of holds are never paid (lesson 22).

Step 1: attempts and winners. Without a waiting room, 200,000 x 10 = 2,000,000 attempts in 60 seconds. That is 2,000,000 / 60 = 33,333 attempts per second. This answers the predict box. At most 1,000 / 2 = 500 bookings can win. That is 500 / 200,000 = 0.25% of the people.

Step 2: the servers without a waiting room. One server does 4 x 1,000 / 8 = 500 attempts per second, and 350 at 70%. So 33,333 / 350 = 95.2, which is 96 servers, for one minute a day.

Step 3: the seat map. 200,000 people x (60 / 5 = 12 refreshes) = 2,400,000 reads in 60 seconds, which is 40,000 per second. The map is small: 1,000 seats x 2 bits = 2,000 bits = 250 bytes. With a cache that lives 1 second, the database loads it once per second. That is 1 read, not 40,000.

Step 4: the waiting room. Joins: 200,000 / 60 = 3,333 per second, which is 3,333 ms of CPU per second. One server does 4,000 joins, and 2,800 at 70%. So 3,333 / 2,800 = 1.19, which is 2 servers. The line has 200,000 records of 50 bytes (Assumption): 200,000 x 50 = 10,000,000 bytes = 10 MB, which fits easily in Redis.

We admit 100 people per second. Assumption: an admitted person needs 3 attempts, because the map from the room is fresh. That is 100 x 3 = 300 attempts per second. They use 300 x 8 = 2,400 ms of CPU, which is 2,400 / 4,000 = 60% of one server. We use 1 server for holds and 1 spare. The total is 2 + 1 + 1 = 4 servers, against 96. That is 96 / 4 = 24 times fewer.

Each admitted person makes at most 1 booking, so selling out takes at least 500 / 100 = 5 seconds. Clashes make it a little longer.

Step 5: unpaid holds. 30% of 500 bookings = 150 are never paid. That is 150 x 2 = 300 seats. After 5 minutes the holds end, and the seats count as free. Within 1 second the recount sets the counter to 300. The status file says "seats left" again, and the room admits the next people. They need 150 / 100 = 1.5 seconds at least.

Step 6: a late payment. A customer starts to pay at minute 4. At minute 5 the gateway says pending, so we extend the hold to minute 10 (Assumption: the limit is 5 extra minutes). The result arrives at minute 6, the confirm update changes 2 rows, and the seats are booked. If the result arrives at minute 11, the hold has ended. If another customer took the seats, the confirm changes 0 rows. We refund and say so.

Step 7: the hotel. A hotel has 20 Deluxe rooms. A guest wants nights 12, 13 and 14. The code runs 3 updates in date order. Night 12 changes 1 row. Night 13 has 0 rooms left and changes 0 rows, so we roll back. Night 12 returns to 20 rooms. The guest sees "not available for all nights".

• A hold that expires solves seats blocked by people who leave. It costs a slow payer who may lose the seat, and extra rules for pending payments. I would make the hold longer than a normal payment, and extend it while pending.
• The database as the truth solves double sales when Redis is lost. It costs a limit of about 500 updates per second for one row. I would change it only if one row gets more than that.
• A cached seat map solves 40,000 reads per second. It costs a map that is up to 1 second old. I would show held seats as taken, because they may return.
• A waiting room solves the rush (4 servers instead of 96) and fairness. It costs one more part, and waiting for the customer. I would use it only for a known rush.
• A random order in the first 30 seconds solves the advantage of speed. It costs that an early person can get a later place.
• Hotel counters solve the lack of seat numbers. They cost a job to give back ended holds.

"Lock the seat while the customer pays." A lock held for minutes makes others wait, and a crashed server can keep it. Use a hold with an end time.

"The waiting room is fair because the first person to arrive goes first." A script arrives first every time. In this lesson, the first 30 seconds are random, and each account has one place.

"After the customer pays, the seat is theirs." The payment can finish after the hold ended. Only the confirm update decides. If it changes too few rows, refund the money.

1. Name the three seat states and the four legal moves. Why does a seat need no cleanup job, but a hotel room count does?
2. A cinema show has 400 seats. 50,000 people try in 30 seconds. Each booking asks for 4 seats, and each person makes 6 attempts without a waiting room. (a) At most how many bookings can win? (b) What share of the people is that? (c) How many attempts per second? (d) How many servers at 350 attempts per second?
3. A guest wants nights 5 and 6. Night 5 has 3 rooms left. Night 6 has 0. What does your transaction do, and what does the guest see?