35 — LLD: Movie Ticket Booking (BookMyShow)

Understanding the Problem

A movie ticket booking system like BookMyShow or Fandango sells seats for scheduled shows. The hard part is concurrent seat selection — when a blockbuster drops, thousands of users hit the same show in the first minute and the system must deliver an all-or-nothing reservation per user. The design rewards a disciplined lock-per-aggregate pattern and a clear state machine on bookings.

What is a Movie Ticket Booking System?

Hierarchy: Cinema → Screen → Show → Seat. Users browse shows, reserve seats for a brief hold window, complete payment, and confirm. If payment fails or the hold expires, seats snap back to available.

---

Requirements

Clarifying Questions

You: Is there a hold window before payment, or do we book immediately?

Interviewer: 5-minute hold. If payment does not complete in that window, the hold expires and seats release.

Two-phase booking. Seats go AVAILABLE → HELD → BOOKED (or back to AVAILABLE on expiry).

You: Can one user hold multiple seats in a single request?

Interviewer: Yes, up to 10.

Atomic multi-seat reserve is the core challenge.

You: Does cancel trigger a refund?

Interviewer: Out of scope. Just release the seats.

You: What is the concurrency target?

Interviewer: Thousands of users hammering the same blockbuster opening minute.

That rules out a single global lock. We need per-show isolation.

Final Requirements

1. search(city, movie, date) -> List<Show>.
2. getSeatMap(showId) -> SeatMap — current availability.
3. reserve(showId, seatIds, userId) -> Booking — atomic; fails if any seat is taken.
4. confirm(bookingId, paymentResult) — transitions HELD seats to BOOKED.
5. cancel(bookingId) — releases seats back to AVAILABLE.
6. subscribe(showId, listener) — notify on availability changes.
7. Thread-safe: concurrent users on the same show handled correctly.

Out of scope: Payment processing internals, refunds, dynamic pricing, notifications to end user.

Deferred tradeoff: Listener dispatch inside the lock is fine for fast in-process listeners; for external subscribers, hand off to an executor.

---

Core Entities and Relationships

The consistency boundary is the Show. Every mutation to seat state on a show must go through that show. No seat can be touched from outside without the show's knowledge — otherwise you get torn state.

Entity	Responsibility
Cinema, Screen	Static reference data.
Movie	id, title, runtime, rating.
Show	id, movieId, screenId, startTime, seat map, lock. The aggregate root.
Seat	id, type, price, state, heldBy.
SeatState	AVAILABLE, HELD, BOOKED.
Booking	id, showId, userId, seatIds, state, expiresAt.
BookingState	HOLD, CONFIRMED, CANCELLED, EXPIRED.
BookingService	Orchestrates reserve/confirm/cancel.
HoldExpirator	Background sweeper that cancels expired holds.
AvailabilityPublisher	Observer registry per show.

Why is Show the aggregate root? Because the invariant "seats do not double-book" is scoped to a single show. Every reserve touches one show. Making the show the lock boundary means users on different shows run in parallel.

Design is iterative. For a blockbuster release, you might later shard a single show across workers with a token-based queue — mention this only if pressed.

---

Class Design

Seat

• id, type (REGULAR/PREMIUM), price.
• state: SeatState — mutable, guarded by the show's lock.
• heldByBookingId: String | null — identifies which booking holds it.

Show (aggregate root)

• id, movieId, screenId, startTime.
• seats: Map<String, Seat>.
• lock: ReentrantLock — the consistency boundary.

Booking

• id, showId, userId, seatIds, state, expiresAt.

BookingService

• shows: Map<String, Show>, bookings: Map<String, Booking>, listeners: Map<String, List<AvailabilityListener>>.
• Methods: reserve, confirm, cancel, subscribe.

Java

public enum SeatState { AVAILABLE, HELD, BOOKED }
public enum BookingState { HOLD, CONFIRMED, CANCELLED, EXPIRED }

public class Seat {
    final String id;
    final String type;
    final BigDecimal price;
    volatile SeatState state = SeatState.AVAILABLE;
    volatile String heldByBookingId;
    public Seat(String id, String type, BigDecimal p) { this.id=id; this.type=type; this.price=p; }
}

public class Show {
    final String id;
    final String movieId;
    final String screenId;
    final Instant startTime;
    final Map<String, Seat> seats;
    final ReentrantLock lock = new ReentrantLock();
    // constructor omitted
}

public class Booking {
    final String id;
    final String showId;
    final String userId;
    final List<String> seatIds;
    volatile BookingState state = BookingState.HOLD;
    final Instant expiresAt;
    // constructor omitted
}

public interface AvailabilityListener {
    void onChange(String showId, Set<String> changedSeatIds);
}

public class BookingService {
    private final Map<String, Show> shows;
    private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
    private final Map<String, List<AvailabilityListener>> listeners = new ConcurrentHashMap<>();

    public Booking reserve(String showId, List<String> seatIds, String userId) { /* ... */ }
    public void confirm(String bookingId, PaymentResult pr) { /* ... */ }
    public void cancel(String bookingId) { /* ... */ }
    public void subscribe(String showId, AvailabilityListener l) { /* ... */ }
}

C++

enum class SeatState { AVAILABLE, HELD, BOOKED };
enum class BookingState { HOLD, CONFIRMED, CANCELLED, EXPIRED };

struct Seat {
    std::string id, type;
    double price;
    SeatState state = SeatState::AVAILABLE;
    std::string heldByBookingId;
};

class Show {
public:
    std::string id, movieId, screenId;
    long startTime;
    std::unordered_map<std::string, Seat> seats;
    std::mutex mtx;
};

struct Booking {
    std::string id, showId, userId;
    std::vector<std::string> seatIds;
    BookingState state = BookingState::HOLD;
    long expiresAt;
};

TypeScript

export enum SeatState { AVAILABLE, HELD, BOOKED }
export enum BookingState { HOLD, CONFIRMED, CANCELLED, EXPIRED }

export interface Seat { id: string; type: string; price: number; state: SeatState; heldByBookingId?: string; }
export interface Show { id: string; movieId: string; screenId: string; startTime: number; seats: Map<string, Seat>; }
export interface Booking { id: string; showId: string; userId: string; seatIds: string[]; state: BookingState; expiresAt: number; }
export interface AvailabilityListener { onChange(showId: string, changed: Set<string>): void; }

Design principles at play:

• Observer: listeners subscribe per show; the publisher fans out on seat state change.
• State pattern: Booking has explicit, linear-ish transitions; invalid transitions throw.
• Lock-per-aggregate: one lock per show, so concurrency is proportional to number of shows.
• Facade: BookingService exposes a narrow API; callers never see Show.lock.

---

Implementation

Core Logic: reserve (atomic multi-seat)

1. Validate input (non-empty, at most 10 seats).
2. Sort seat ids — deterministic ordering so two concurrent requests with overlapping seats deadlock-free (same lock, same order).
3. Acquire the show lock.
4. Check all requested seats are AVAILABLE. If any fails, release the lock and throw.
5. Transition all seats to HELD, set heldByBookingId, record the booking with expiresAt = now + 5 min.
6. Publish the change to listeners (fast path — fast listeners only).
7. Release the lock.

Core Logic: confirm

1. Look up the booking. Must be in HOLD state. Must match payment success.
2. Acquire the show lock. Re-check state inside lock (the hold could have expired between the payment round trip and now).
3. Transition all seats from HELD to BOOKED. Mark booking CONFIRMED.

Core Logic: cancel

1. Look up the booking. If already CANCELLED/EXPIRED, no-op.
2. Acquire the show lock.
3. For each seat: if heldByBookingId == this booking, release to AVAILABLE. (Idempotency check — so the expirator and a user cancel cannot double-release.)
4. Mark booking CANCELLED.

Implementations

Java

public Booking reserve(String showId, List<String> seatIds, String userId) {
    if (seatIds.isEmpty() || seatIds.size() > 10)
        throw new IllegalArgumentException("seat count out of range");
    Show show = shows.get(showId);
    if (show == null) throw new NoSuchElementException("show not found");

    List<String> sortedIds = seatIds.stream().sorted().toList();

    show.lock.lock();
    try {
        for (String sid : sortedIds) {
            Seat seat = show.seats.get(sid);
            if (seat == null) throw new NoSuchElementException("seat " + sid);
            if (seat.state != SeatState.AVAILABLE)
                throw new IllegalStateException("seat " + sid + " not available");
        }
        String bookingId = UUID.randomUUID().toString();
        Instant expiry = Instant.now().plusSeconds(300);
        Booking booking = new Booking(bookingId, showId, userId, sortedIds, BookingState.HOLD, expiry);
        for (String sid : sortedIds) {
            Seat s = show.seats.get(sid);
            s.state = SeatState.HELD;
            s.heldByBookingId = bookingId;
        }
        bookings.put(bookingId, booking);
        publish(showId, new HashSet<>(sortedIds));
        return booking;
    } finally {
        show.lock.unlock();
    }
}

public void confirm(String bookingId, PaymentResult pr) {
    Booking b = bookings.get(bookingId);
    if (b == null) throw new NoSuchElementException();
    if (b.state != BookingState.HOLD) throw new IllegalStateException("not on hold");
    if (!pr.success()) { cancel(bookingId); return; }
    Show show = shows.get(b.showId);
    show.lock.lock();
    try {
        if (b.state != BookingState.HOLD) return;  // re-check inside lock
        for (String sid : b.seatIds) {
            Seat s = show.seats.get(sid);
            s.state = SeatState.BOOKED;
        }
        b.state = BookingState.CONFIRMED;
    } finally { show.lock.unlock(); }
}

public void cancel(String bookingId) {
    Booking b = bookings.get(bookingId);
    if (b == null) return;
    Show show = shows.get(b.showId);
    show.lock.lock();
    try {
        if (b.state == BookingState.CANCELLED || b.state == BookingState.EXPIRED) return;
        for (String sid : b.seatIds) {
            Seat s = show.seats.get(sid);
            if (b.id.equals(s.heldByBookingId)) {
                s.state = SeatState.AVAILABLE;
                s.heldByBookingId = null;
            }
        }
        b.state = BookingState.CANCELLED;
        publish(b.showId, new HashSet<>(b.seatIds));
    } finally { show.lock.unlock(); }
}

private void publish(String showId, Set<String> seatIds) {
    List<AvailabilityListener> ls = listeners.get(showId);
    if (ls == null) return;
    for (AvailabilityListener l : ls) {
        try { l.onChange(showId, seatIds); } catch (Exception ignore) {}
    }
}

C++

std::optional<Booking> BookingService::reserve(
    const std::string& showId,
    std::vector<std::string> seatIds,
    const std::string& userId) {
    auto it = shows.find(showId);
    if (it == shows.end()) return std::nullopt;
    auto& show = *it->second;
    std::sort(seatIds.begin(), seatIds.end());

    std::lock_guard<std::mutex> lk(show.mtx);
    for (auto& sid : seatIds) {
        auto sit = show.seats.find(sid);
        if (sit == show.seats.end() || sit->second.state != SeatState::AVAILABLE)
            return std::nullopt;
    }
    Booking b{newUuid(), showId, userId, seatIds, BookingState::HOLD, now() + 300};
    for (auto& sid : seatIds) {
        show.seats[sid].state = SeatState::HELD;
        show.seats[sid].heldByBookingId = b.id;
    }
    bookings[b.id] = b;
    publish(showId, seatIds);
    return b;
}

TypeScript

reserve(showId: string, seatIds: string[], userId: string): Booking {
  if (seatIds.length === 0 || seatIds.length > 10) throw new Error("seat count");
  const show = this.shows.get(showId);
  if (!show) throw new Error("no show");
  const sorted = [...seatIds].sort();
  // Node is single-threaded per tick. No lock needed for pure sync mutation.
  for (const sid of sorted) {
    const seat = show.seats.get(sid);
    if (!seat || seat.state !== SeatState.AVAILABLE) throw new Error("not available");
  }
  const b: Booking = {
    id: crypto.randomUUID(),
    showId, userId,
    seatIds: sorted,
    state: BookingState.HOLD,
    expiresAt: Date.now() + 300_000,
  };
  for (const sid of sorted) {
    const seat = show.seats.get(sid)!;
    seat.state = SeatState.HELD;
    seat.heldByBookingId = b.id;
  }
  this.bookings.set(b.id, b);
  this.publish(showId, new Set(sorted));
  return b;
}

Thread Safety

The unit of concurrency is a Show. Each show owns its own ReentrantLock. Two users on the same show serialize; two users on different shows run in parallel.

Seats are never locked individually. If two users request overlapping seat sets, they still both lock the same show — that serializes them. No deadlock risk because there is only one lock per request.

HoldExpirator runs on a ScheduledExecutorService. It scans bookings for state == HOLD && expiresAt < now and calls cancel(id). The cancel path is idempotent thanks to the heldByBookingId guard.

Listener dispatch inside the lock works only if listeners are fast. For external subscribers, submit to an executor: listenerExecutor.submit(() -> l.onChange(...)) — but now you decouple the event from the lock's atomicity, so duplicates and reorderings are possible. Document that.

Verification

Two users both try to book seats [A1, A2] on the same show at roughly the same time.

Time	U1	U2	Show state
t=0	acquires show lock	blocks on lock	A1, A2 AVAILABLE
t=1	checks all seats AVAILABLE → marks HELD → returns → releases lock	-	A1, A2 HELD by U1
t=2	-	acquires lock, checks A1 → HELD → throws	A1, A2 HELD by U1
t=3	confirms → A1, A2 BOOKED	retries with B1, B2 → holds them	A1, A2 BOOKED / B1, B2 HELD

---

Complete Code Implementation

Java

import java.math.BigDecimal;
import java.time.Instant;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

public enum SeatState { AVAILABLE, HELD, BOOKED }
public enum BookingState { HOLD, CONFIRMED, CANCELLED, EXPIRED }

public class Seat {
    final String id, type;
    final BigDecimal price;
    volatile SeatState state = SeatState.AVAILABLE;
    volatile String heldByBookingId;
    public Seat(String id, String type, BigDecimal p) { this.id=id; this.type=type; this.price=p; }
}

public class Show {
    public final String id, movieId, screenId;
    public final Instant startTime;
    public final Map<String, Seat> seats;
    public final ReentrantLock lock = new ReentrantLock();
    public Show(String id, String m, String sc, Instant start, Map<String, Seat> seats) {
        this.id = id; this.movieId = m; this.screenId = sc; this.startTime = start; this.seats = seats;
    }
}

public class Booking {
    public final String id, showId, userId;
    public final List<String> seatIds;
    public volatile BookingState state = BookingState.HOLD;
    public final Instant expiresAt;
    public Booking(String id, String s, String u, List<String> seats, BookingState st, Instant exp) {
        this.id=id; this.showId=s; this.userId=u; this.seatIds=seats; this.state=st; this.expiresAt=exp;
    }
}

public interface AvailabilityListener {
    void onChange(String showId, Set<String> changedSeatIds);
}

public record PaymentResult(boolean success) {}

public class BookingService {
    private final Map<String, Show> shows;
    private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
    private final Map<String, List<AvailabilityListener>> listeners = new ConcurrentHashMap<>();
    private final ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();

    public BookingService(Map<String, Show> shows) {
        this.shows = shows;
        scheduler.scheduleWithFixedDelay(this::expireHolds, 10, 10, TimeUnit.SECONDS);
    }

    public Booking reserve(String showId, List<String> seatIds, String userId) {
        if (seatIds.isEmpty() || seatIds.size() > 10) throw new IllegalArgumentException();
        Show show = shows.get(showId);
        if (show == null) throw new NoSuchElementException();
        List<String> sorted = seatIds.stream().sorted().toList();
        show.lock.lock();
        try {
            for (String sid : sorted) {
                Seat seat = show.seats.get(sid);
                if (seat == null || seat.state != SeatState.AVAILABLE)
                    throw new IllegalStateException("seat unavailable: " + sid);
            }
            String bId = UUID.randomUUID().toString();
            Booking b = new Booking(bId, showId, userId, sorted, BookingState.HOLD, Instant.now().plusSeconds(300));
            for (String sid : sorted) {
                Seat s = show.seats.get(sid);
                s.state = SeatState.HELD;
                s.heldByBookingId = bId;
            }
            bookings.put(bId, b);
            publish(showId, new HashSet<>(sorted));
            return b;
        } finally { show.lock.unlock(); }
    }

    public void confirm(String bookingId, PaymentResult pr) {
        Booking b = bookings.get(bookingId);
        if (b == null) throw new NoSuchElementException();
        if (!pr.success()) { cancel(bookingId); return; }
        Show show = shows.get(b.showId);
        show.lock.lock();
        try {
            if (b.state != BookingState.HOLD) return;
            for (String sid : b.seatIds) show.seats.get(sid).state = SeatState.BOOKED;
            b.state = BookingState.CONFIRMED;
        } finally { show.lock.unlock(); }
    }

    public void cancel(String bookingId) {
        Booking b = bookings.get(bookingId);
        if (b == null) return;
        Show show = shows.get(b.showId);
        show.lock.lock();
        try {
            if (b.state == BookingState.CANCELLED || b.state == BookingState.EXPIRED) return;
            for (String sid : b.seatIds) {
                Seat s = show.seats.get(sid);
                if (b.id.equals(s.heldByBookingId)) {
                    s.state = SeatState.AVAILABLE;
                    s.heldByBookingId = null;
                }
            }
            b.state = BookingState.CANCELLED;
            publish(b.showId, new HashSet<>(b.seatIds));
        } finally { show.lock.unlock(); }
    }

    public void subscribe(String showId, AvailabilityListener l) {
        listeners.computeIfAbsent(showId, k -> new CopyOnWriteArrayList<>()).add(l);
    }

    private void publish(String showId, Set<String> seatIds) {
        var ls = listeners.get(showId);
        if (ls == null) return;
        for (var l : ls) { try { l.onChange(showId, seatIds); } catch (Exception ignore) {} }
    }

    private void expireHolds() {
        Instant now = Instant.now();
        for (Booking b : bookings.values()) {
            if (b.state == BookingState.HOLD && b.expiresAt.isBefore(now)) {
                cancel(b.id);
                b.state = BookingState.EXPIRED;
            }
        }
    }
}

C++

// See the Class Design and reserve method above; expansion follows Java skeleton.

TypeScript

export class BookingService {
  private bookings = new Map<string, Booking>();
  private listeners = new Map<string, AvailabilityListener[]>();

  constructor(private shows: Map<string, Show>) {
    setInterval(() => this.expireHolds(), 10_000);
  }

  reserve(showId: string, seatIds: string[], userId: string): Booking {
    if (seatIds.length === 0 || seatIds.length > 10) throw new Error("seat count");
    const show = this.shows.get(showId);
    if (!show) throw new Error("no show");
    const sorted = [...seatIds].sort();
    for (const sid of sorted) {
      const seat = show.seats.get(sid);
      if (!seat || seat.state !== SeatState.AVAILABLE) throw new Error("unavailable");
    }
    const b: Booking = {
      id: crypto.randomUUID(),
      showId, userId, seatIds: sorted,
      state: BookingState.HOLD,
      expiresAt: Date.now() + 300_000,
    };
    for (const sid of sorted) {
      const seat = show.seats.get(sid)!;
      seat.state = SeatState.HELD;
      seat.heldByBookingId = b.id;
    }
    this.bookings.set(b.id, b);
    this.publish(showId, new Set(sorted));
    return b;
  }

  confirm(bookingId: string, paymentSuccess: boolean): void {
    const b = this.bookings.get(bookingId);
    if (!b) throw new Error("no booking");
    if (!paymentSuccess) { this.cancel(bookingId); return; }
    const show = this.shows.get(b.showId)!;
    if (b.state !== BookingState.HOLD) return;
    for (const sid of b.seatIds) show.seats.get(sid)!.state = SeatState.BOOKED;
    b.state = BookingState.CONFIRMED;
  }

  cancel(bookingId: string): void {
    const b = this.bookings.get(bookingId);
    if (!b) return;
    if (b.state === BookingState.CANCELLED || b.state === BookingState.EXPIRED) return;
    const show = this.shows.get(b.showId)!;
    for (const sid of b.seatIds) {
      const s = show.seats.get(sid)!;
      if (s.heldByBookingId === b.id) { s.state = SeatState.AVAILABLE; s.heldByBookingId = undefined; }
    }
    b.state = BookingState.CANCELLED;
    this.publish(b.showId, new Set(b.seatIds));
  }

  subscribe(showId: string, l: AvailabilityListener): void {
    if (!this.listeners.has(showId)) this.listeners.set(showId, []);
    this.listeners.get(showId)!.push(l);
  }

  private publish(showId: string, ids: Set<string>): void {
    for (const l of this.listeners.get(showId) ?? []) { try { l.onChange(showId, ids); } catch {} }
  }

  private expireHolds(): void {
    const now = Date.now();
    for (const b of this.bookings.values()) {
      if (b.state === BookingState.HOLD && b.expiresAt < now) {
        this.cancel(b.id);
        b.state = BookingState.EXPIRED;
      }
    }
  }
}

---

Extensibility

1. "Seat pricing by zone or time of day?"

Introduce a PricingStrategy per show: computePrice(Seat, Context). Swap strategies per show tier. The Seat.price becomes a cached base rate; the strategy overrides.

public interface PricingStrategy {
    BigDecimal price(Seat seat, Show show, Instant bookingTime);
}

Tradeoff: Pricing complexity leaks into booking. Keep the strategy pure (no I/O) so it can run inside the lock.

2. "Real-time UI updates via WebSocket?"

AvailabilityListener publishes to a WebSocket hub keyed by show. Clients subscribe by showId. On change, the hub fans out to connected sockets. Move dispatch off the booking thread so the lock is held briefly.

3. "Concurrent blockbuster — 50k users per seat?"

Per-show lock becomes the bottleneck. Options: shard show state (e.g., rows A-K on worker 1, L-Z on worker 2), or switch to a token queue where users take a ticket and are processed FIFO. Name it as an explicit scale-out path, not a default.

4. "Payment failure?"

confirm(bookingResult) with success=false calls cancel(bookingId). For transient payment failures, retry with an outbox so the client is not stuck.

---

What is Expected at Each Level

Level	Expectations
Junior (L4)	Mutates seats individually without an atomic multi-seat check. Misses the hold/confirm distinction.
Mid (L5)	Per-show lock, sorted-id iteration, correct Observer, hold expiration. Identifies Show as the aggregate root.
Senior (L5A)	All of the above, plus explicit state-machine guards, idempotent cancel via heldByBookingId check, listener dispatch trade-offs, clean extension path to sharded shows.
Staff (L6)	State-machine guarded transitions, event sourcing, regional sharding, failure recovery playbook, per-user rate limiting, SLOs for booking latency.