# Seat Booking

Course: [Low-Level Design](https://www.devtutorials.ai/learn/system-design/lld) · Section: LLD Case Studies
Source: https://www.devtutorials.ai/learn/system-design/lld/case-studies/seat-booking

> Design cinema seat booking like BookMyShow: hold then confirm, expiring holds, all-or-nothing groups and a lock tested in every order.

Tickets for a popular film go on sale at 6 p.m. Thousands of customers open the seat map at the same time, and several customers may try to select the same seat.

The booking system must ensure that only one customer can hold or book a seat. For example, two customers must never be allowed to pay for seat B5.

In this case study, you will design a seat booking system for QuickBite’s movie-night feature. The design will cover seat states, temporary holds, payment confirmation, simultaneous booking requests, and the APIs used to perform these actions.

A temporary hold keeps a selected seat unavailable for a few minutes while the customer completes payment. If payment succeeds, the seat becomes booked. If payment fails or the hold expires, the seat becomes available again.

**In simple words:** you will design a system that temporarily holds a seat during payment and prevents two customers from booking the same seat.

## What You Will Learn

In this case study, you will:

1. Split booking into hold, then confirm.
2. Expire holds, so walked-away users do not block seats.
3. Hold a group of seats all or nothing.
4. Find the race with the every-order scheduler, and fix it with a lock.
5. Build the show in the sandbox and pass the hidden tests, including every-order tests.

This is the hardest case study, because it is about **time and concurrency**, not just classes. It reuses the scheduler from Concurrency Basics, so the hidden tests try every order of events.

## Step 1: Agree on the Requirements

Before writing code, confirm the rules the seat booking system must follow.

### What It Must Do

- `hold(user, seats, now)` temporarily holds the selected seats for five minutes.
- All requested seats must be held together. If even one seat is unavailable, none of them should be held.
- A booked seat or a seat held by another user cannot be held.
- `confirm(user, seats, now)` books the seats only if the same user still holds all of them.
- An expired hold cannot be confirmed. The seats must become available to other users.
- When several users request the same seat at the same time, only one request can succeed.

### What We Leave Out

- Payment itself (a payment service would be called between hold and confirm).
- Pricing by seat type.
- Several servers (a real system uses a database transaction or Redis lock).

Leaving things out on purpose is not lazy. It keeps the design small enough to finish, and you can say how you would add them later.

## Step 2: Find the Classes

A simple trick: underline the **nouns** in the requirements. Most of them become classes. The **verbs** become methods.

| Class | Its one job |
|---|---|
| Show | Knows every seat's hold and booking, and the rules |
| Hold | Who holds a seat, and until when |
| Mutex | Lets only one hold check-and-take at a time |

## Step 3: Build the Key Parts

### Hold, Then Confirm

Payment can take time to complete. During that time, another customer may try to select the same seat.

To prevent this, seat booking happens in two steps:

- **Hold:** temporarily reserve the seat while the customer completes payment.
- **Confirm:** mark the seat as booked after the payment succeeds.

If the payment fails or the hold expires, the seat becomes available again.

Step through Asha and Ravi asking for the same seat:

| Call | Result |
|---|---|
| `hold("asha", "B5", 0)` | `true`: Asha holds B5 while she pays |
| `hold("ravi", "B5", 1)` | `false`: Ravi cannot take it |
| `confirm("asha", "B5")` | `true`: payment done, B5 is booked by asha |

Here is the same idea in code:

```ts runnable title="Hold, then confirm: two steps, like a shopping cart"
type Hold = { user: string; until: number };
const holds = new Map<string, Hold>();
const booked = new Map<string, string>();

function hold(user: string, seat: string, now: number): boolean {
  if (booked.has(seat) || holds.has(seat)) return false;
  holds.set(seat, { user, until: now + 5 });
  return true;
}
function confirm(user: string, seat: string): boolean {
  if (holds.get(seat)?.user !== user) return false;
  holds.delete(seat);
  booked.set(seat, user);
  return true;
}

console.log(hold("asha", "B5", 0));  // Asha holds B5 while she pays
console.log(hold("ravi", "B5", 1));  // Ravi cannot take it
console.log(confirm("asha", "B5"));  // payment done
console.log(booked.get("B5"));
```

Expected output:

```text
true
false
true
asha
```

### Holds Must Expire

If a user holds a seat but does not complete the booking, the seat should not remain unavailable forever. Each hold therefore has an expiry time.

Before checking whether a seat is available or confirming a booking, the system removes any expired hold. The seat can then be held by another user.

Watch a hold on seat C1 that lasts until minute 5:

At minute 3, C1 is still held. At minute 5, it is free.

Here is the same idea in code:

```ts runnable title="Holds expire, so a seat is not blocked forever"
type Hold = { user: string; until: number };
const holds = new Map<string, Hold>([["C1", { user: "asha", until: 5 }]]);

function dropExpired(now: number): void {
  for (const [seat, h] of holds) if (h.until <= now) holds.delete(seat);
}

dropExpired(3);
console.log("at minute 3:", holds.has("C1") ? "held" : "free");
dropExpired(5);
console.log("at minute 5:", holds.has("C1") ? "held" : "free");
```

Expected output:

```text
at minute 3: held
at minute 5: free
```

Never let a confirm succeed after the hold has expired. By then, someone else may have held the same seat. Check that the hold still exists, and still belongs to this user, at the moment of confirming.

### All or Nothing

When a user selects several seats, the system must treat them as one request. It should first check whether all the selected seats are available.

If every seat is available, the system holds them together. If even one seat is unavailable, the request fails and none of the seats are held.

**Key point:** Holding multiple seats is an all-or-nothing operation. The system must never hold only part of the requested group.

The figure shows two group requests. Seat D2 is already taken.

Here is the same idea in code:

```ts runnable title="All or nothing: a group of seats"
const taken = new Set(["D2"]);

function holdAll(seats: string[]): boolean {
  if (seats.some((s) => taken.has(s))) return false; // check every seat first
  for (const s of seats) taken.add(s);               // then take them all
  return true;
}

console.log(holdAll(["D1", "D2"])); // D2 is taken, so nothing is held
console.log(taken.has("D1"));       // D1 was not half-taken
console.log(holdAll(["D3", "D4"]));
```

Expected output:

```text
false
false
true
```

### The Race

During a popular film release, many users may try to hold the same seat at the same time.

If the system first checks whether seat B5 is available and then separately updates it as held, another request may pass the same check before the update finishes. Both users may then believe they have successfully held the seat.

This problem is called a race condition. It happens when multiple requests access and change the same data at nearly the same time, and the result depends on which request finishes first.

To prevent this, checking and holding the seat must happen as one atomic operation. An atomic operation completes as a single protected action, so only one request can successfully hold the seat.

**Key point:** Do not check availability and hold the seat as separate unprotected steps. Perform both actions atomically so the same seat cannot be assigned to two users.

Step through one bad order. Each hold checks, waits for a database round trip, then writes:

The every-order scheduler tried every order of these steps for two users: **4 of 6 orders gave B5 to two people**.

Here is the same idea in code:

```ts runnable title="The race: two users, one seat, every order"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

let holds = new Map<string, string>();
let winners = 0;

function* hold(user: string, seat: string): Step {
  const free = !holds.has(seat); // check
  yield;                         // database round trip
  if (free) { holds.set(seat, user); winners++; }
}

const r = everyOrder(
  () => { holds = new Map(); winners = 0; return [hold("asha", "B5"), hold("ravi", "B5")]; },
  () => winners === 1,
);
console.log(`${r.bad} of ${r.runs} orders gave B5 to two people`);
```

Expected output:

```text
4 of 6 orders gave B5 to two people
```

### The Fix

Place the availability check and the seat hold inside the same lock. A lock allows only one request at a time to check and update the seat.

While one request is holding seat B5, other requests must wait. After the first request finishes, the next request checks the seat again and sees that it is no longer available.

**Key point:** The check and update must happen together inside the same lock. This prevents two users from holding the same seat.

Now three users race for B5, but check-and-hold sits inside one lock:

With three users there are 42 possible orders. With the lock, **0 of 42 orders gave B5 to two people**.

Here is the same idea in code:

```ts runnable title="The fix: a lock around check and hold"
type Step = Generator<unknown, void, unknown>;

class Mutex {
  held = false;
  *acquire(): Step { while (this.held) yield this; this.held = true; }
  release(): void { this.held = false; }
}

function everyOrder(make: () => Step[], check: () => boolean): { runs: number; bad: number } {
  const todo: number[][] = [[]];
  let runs = 0, bad = 0;
  while (todo.length) {
    const prefix = todo.pop()!;
    const tasks = make();
    const done = tasks.map(() => false);
    const wait: unknown[] = tasks.map(() => null);
    const order: number[] = [];
    while (done.some((d) => !d)) {
      const ready = tasks.map((_, i) => i).filter((i) => !done[i] && !(wait[i] instanceof Mutex && (wait[i] as Mutex).held));
      let pick = ready[0];
      if (order.length < prefix.length) pick = prefix[order.length];
      else for (const r of ready.slice(1)) todo.push([...order, r]);
      order.push(pick);
      const s = tasks[pick].next();
      done[pick] = !!s.done;
      wait[pick] = s.done ? null : s.value;
    }
    runs++;
    if (!check()) bad++;
  }
  return { runs, bad };
}

let holds = new Map<string, string>();
let winners = 0;
const lock = new Mutex();

function* hold(user: string, seat: string): Step {
  yield* lock.acquire();
  try {
    const free = !holds.has(seat);
    yield;
    if (free) { holds.set(seat, user); winners++; }
  } finally {
    lock.release();
  }
}

const r = everyOrder(
  () => { holds = new Map(); winners = 0; lock.held = false; return [hold("asha", "B5"), hold("ravi", "B5"), hold("meena", "B5")]; },
  () => winners === 1,
);
console.log(`${r.bad} of ${r.runs} orders gave B5 to two people`);
```

Expected output:

```text
0 of 42 orders gave B5 to two people
```

**Easy way to remember:** **hold** with a timer, **confirm** only if the hold is still yours, and do **check-and-hold in one locked step**. In a real database, the same thing is done with a transaction or a unique constraint on (show, seat).

## Lab: Build It

The starter code has two problems: multiple users can hold the same seat at the same time, and expired holds are not removed.

The automated tests simulate two or three users performing actions in different orders. They check that seat holds, expiry, and booking confirmation work correctly.

Follow these steps:

1. Give each show a `Mutex`. A mutex is a lock that allows only one request at a time to check and update the show’s seats.
2. At the beginning of `hold()`, acquire the lock. Release it inside a `finally` block so that the lock is released even if an error occurs.
3. While holding the lock, remove expired holds and check every requested seat.
4. If any seat is booked or held by another user, reject the complete request.
5. If every seat is available, hold all the requested seats for the user.
6. In `confirm()`, remove expired holds first. Book the seats only if the same user still holds every requested seat.

Open the lab in the sandbox. Run the tests after each step. A failing test names the situation that broke, not the test code.

## Predict the Output

<CsPredict id="seat-1" code={"var taken = new HashSet<string> { \"D2\" };\nbool HoldAll(string[] seats)\n{\n    if (seats.Any(s => taken.Contains(s))) return false;\n    foreach (var s in seats) taken.Add(s);\n    return true;\n}\nConsole.WriteLine(HoldAll(new[] { \"D1\", \"D2\" }));\nConsole.WriteLine(HoldAll(new[] { \"D3\", \"D4\" }));\nConsole.WriteLine(taken.Count);"} expected={"False\nTrue\n3"} why="D2 is taken, so the first group holds nothing. The second group holds D3 and D4. Taken now has D2, D3 and D4: three seats." />

## Common Mistakes

| Mistake | Wrong | Correct | Why it happens |
|---|---|---|---|
| Book after payment only | Two users pay for the same seat. | Hold first, then confirm. | Payment is often designed separately. |
| Holds that never expire | Abandoned carts block seats all night. | An expiry time on every hold. | Tests rarely walk away mid-payment. |
| Half a group | Holding D1 when D2 is taken. | Check every seat, then hold all or none. | Holding seat by seat in a loop. |
| Check, then hold, unlocked | A gap between "is it free?" and "hold it". | Do both inside one lock or transaction. | It never fails on a quiet laptop. |
| Confirm checks too little | Confirming any seat that is not booked. | Check it is held by this user, and not expired. | The happy path always confirms its own hold. |

## Practice

## What to Remember

- Book in two steps: **hold** while paying, then **confirm**.
- Every hold has an **expiry**.
- Groups are **all or nothing**.
- Do **check-and-hold in one locked step**, and test **every order**.
- Confirm only a hold that is **still yours** and **not expired**.

## Further Reading

These are the sources used to check this case study:

- [PostgreSQL: Unique constraints](https://www.postgresql.org/docs/current/ddl-constraints.html#DDL-CONSTRAINTS-UNIQUE-CONSTRAINTS): how a database refuses a second booking.
- [Redis: Distributed locks](https://redis.io/docs/latest/develop/use/patterns/distributed-locks/): locks across servers.
- [MDN: Generator functions](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*): the yield used by the scheduler.

You have finished the Low-Level Design tutorial. Next, try designing one of these systems end to end with the **High-Level Design** case studies.