LLD Series: BookMyShow (Movie Ticket Booking) (LLD)

Overview

1. Problem statement and how it is asked
2. Requirements clarification
3. Entities and class diagram
4. Design patterns and why
5. Code
6. Key flows
7. Extensibility
8. Concurrency and edge cases
9. Follow-ups and model answers
10. Common mistakes and rubric

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

"Design a movie ticket booking system. Users browse shows, pick seats, pay and get a ticket. Two users must never book the same seat." The real question is concurrency: temporary seat holds with expiry, payment in between, and no double booking. Asked at PayU, Visa, Amex, Mastercard, NPCI (payment-flavoured follow-ups: idempotency, refunds on timeout), and also BookMyShow/Paytm/Flipkart.

2. Requirements clarification

Functional

Shows (movie + screen + time) each with a seat layout; seat types with prices.
View available seats for a show.
Select seats -> temporary lock (e.g. 5 min), all-or-nothing for multi-seat selection.
Pay -> confirm booking; payment failure or timeout releases seats.
Cancel pending booking. Non-functional: no double booking under concurrency; contention only within the same show; correct under payment latency; deterministic expiry (injectable clock). Assumptions: single JVM; one payment attempt per booking; price by seat type; search/browse of cities/theaters is a thin catalog and omitted. Out of scope: user auth, catalog/search, refunds after confirmation, offers/coupons, notifications (see doc 11).

3. Entities and class diagram

Show 1 ---- * ShowSeat (seatId, SeatType, status, lockedBy, expiry, bookingId)
  |  lock: ReentrantLock (one per show)
  |
BookingService ---> Map<showId, Show>, Map<bookingId, Booking>
  |  lockSeats() confirm() cancel() sweepExpired()
  |--uses--> <<interface>> PaymentGateway { charge(), refund() }  <- FakeGateway
  |--uses--> java.time.Clock  <- MutableClock (tests)
Booking (id, userId, showId, seatIds, amount, status, lockExpiry)
Enums: SeatType{SILVER,GOLD,PLATINUM}  SeatStatus{AVAILABLE,LOCKED,BOOKED}
       BookingStatus{PENDING,CONFIRMED,EXPIRED,CANCELLED,FAILED}

Seat state machine:
 AVAILABLE --lock--> LOCKED --confirm--> BOOKED
     ^                  |  expiry / cancel / pay-fail
     +------------------+

(Seat physical vs ShowSeat per-show: the status belongs to the show, not the physical seat - a common modelling mistake.)

4. Design patterns and why

Pattern	Where	Why / rejected alternative
Strategy / Adapter	`PaymentGateway`	Swap Razorpay/UPI/card; tests use `FakeGateway`.
State (lightweight)	`SeatStatus`, `BookingStatus`	Explicit lifecycle; transitions only in service under lock. Full State classes would be over-engineering.
Dependency injection	`Clock`, gateway	Deterministic expiry tests without sleeping.
Service/Facade	`BookingService`	Single place enforcing invariants.
(Extension) Strategy	pricing	`PricingStrategy` for weekend/surge; here price from `SeatType`.

Locking approaches compared:

Global lock: correct but serializes the whole system. Rejected.
Per-seat lock: multi-seat all-or-nothing needs ordered acquisition to avoid deadlock; more complex.
Per-show lock (chosen): atomic multi-seat check-then-act, contention only among users of the same show, simple. Max ~hundreds of seats so critical section is microseconds.
Optimistic (DB version/CAS): the distributed answer, see follow-ups.

5. Code

Default package; javac *.java && java Main.

Enums and exceptions

public enum SeatType { SILVER(200), GOLD(350), PLATINUM(500);
    public final long price; SeatType(long p) { price = p; } }
public enum SeatStatus { AVAILABLE, LOCKED, BOOKED }
public enum BookingStatus { PENDING, CONFIRMED, EXPIRED, CANCELLED, FAILED }
public class Exceptions {
    public static class SeatUnavailableException extends RuntimeException {
        public SeatUnavailableException(String m) { super(m); } }
    public static class LockExpiredException extends RuntimeException {
        public LockExpiredException(String m) { super(m); } }
    public static class NotFoundException extends RuntimeException {
        public NotFoundException(String m) { super(m); } }
}

ShowSeat.java

Mutated only while holding the show lock. isFree(now) does lazy expiry: a LOCKED seat past its deadline is treated as available, so correctness never depends on a background thread running on time.

/** Per-show seat state. Mutated only while holding the owning Show's lock. */
public class ShowSeat {
    final String seatId; final SeatType type;
    SeatStatus status = SeatStatus.AVAILABLE;
    String lockedBy; long lockExpiryMs; String bookingId;
    ShowSeat(String seatId, SeatType type) { this.seatId = seatId; this.type = type; }

    /** Lazy expiry: a LOCKED seat past its deadline is effectively AVAILABLE. */
    boolean isFree(long now) {
        return status == SeatStatus.AVAILABLE || (status == SeatStatus.LOCKED && now >= lockExpiryMs);
    }
    void release() { status = SeatStatus.AVAILABLE; lockedBy = null; bookingId = null; lockExpiryMs = 0; }
}

Show.java

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

/** A movie screening. One lock per show => shows never contend; multi-seat ops are atomic. */
public class Show {
    final String id, movie, screen;
    final Map<String, ShowSeat> seats = new LinkedHashMap<>();
    final ReentrantLock lock = new ReentrantLock();

    public Show(String id, String movie, String screen, Map<String, SeatType> layout) {
        this.id = id; this.movie = movie; this.screen = screen;
        layout.forEach((sid, t) -> seats.put(sid, new ShowSeat(sid, t)));
    }
    public String getId() { return id; }
    public String getMovie() { return movie; }

    public List<String> availableSeats(long now) {
        lock.lock();
        try {
            List<String> r = new ArrayList<>();
            seats.values().forEach(s -> { if (s.isFree(now)) r.add(s.seatId); });
            return r;
        } finally { lock.unlock(); }
    }
}

Booking.java

import java.util.List;

public class Booking {
    final String id, userId, showId; final List<String> seatIds; final long amount; final long lockExpiryMs;
    volatile BookingStatus status = BookingStatus.PENDING;
    Booking(String id, String userId, String showId, List<String> seatIds, long amount, long lockExpiryMs) {
        this.id = id; this.userId = userId; this.showId = showId; this.seatIds = seatIds;
        this.amount = amount; this.lockExpiryMs = lockExpiryMs;
    }
    public String getId() { return id; }
    public BookingStatus getStatus() { return status; }
    public long getAmount() { return amount; }
    @Override public String toString() {
        return "Booking{" + id + ", " + userId + ", " + seatIds + ", Rs." + amount + ", " + status + "}";
    }
}

PaymentGateway.java and FakeGateway.java

public interface PaymentGateway {
    /** Idempotent on idempotencyKey (= bookingId). Returns true on success. */
    boolean charge(String userId, long amount, String idempotencyKey);
    void refund(String idempotencyKey);
}
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

public class FakeGateway implements PaymentGateway {
    private final Set<String> failingUsers = ConcurrentHashMap.newKeySet();
    private final Set<String> charged = ConcurrentHashMap.newKeySet();
    private volatile Runnable beforeCharge = () -> {};
    public void failFor(String user) { failingUsers.add(user); }
    public void onCharge(Runnable r) { beforeCharge = r; }      // test hook: simulate slow payment
    public boolean charge(String userId, long amount, String key) {
        beforeCharge.run();
        if (failingUsers.contains(userId)) return false;
        charged.add(key); return true;
    }
    public void refund(String key) { if (charged.remove(key)) System.out.println("  [gateway] refunded " + key); }
}

BookingService.java

Key decision: the show lock is NOT held during gateway.charge (slow network I/O would block everyone on that show). Instead: validate under lock -> charge outside -> re-validate under lock and commit; if the hold expired meanwhile, refund. Validation happens for all seats before any mutation (all-or-nothing); seat ids are sorted so behaviour is deterministic.

import java.time.Clock;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

public class BookingService {
    private final Map<String, Show> shows = new ConcurrentHashMap<>();
    private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
    private final PaymentGateway gateway;
    private final Clock clock;
    private final long lockTtlMs;
    private final AtomicLong seq = new AtomicLong();

    public BookingService(PaymentGateway gateway, Clock clock, long lockTtlMs) {
        this.gateway = gateway; this.clock = clock; this.lockTtlMs = lockTtlMs;
    }
    public void addShow(Show s) { shows.put(s.getId(), s); }
    public List<String> availableSeats(String showId) { return show(showId).availableSeats(clock.millis()); }

    /** Step 1: all-or-nothing temporary hold. */
    public Booking lockSeats(String userId, String showId, List<String> seatIds) {
        Show show = show(showId);
        List<String> ids = new ArrayList<>(new TreeSet<>(seatIds));   // dedupe + deterministic order
        show.lock.lock();
        try {
            long now = clock.millis();
            long amount = 0;
            for (String id : ids) {                                  // validate ALL first
                ShowSeat s = show.seats.get(id);
                if (s == null) throw new Exceptions.NotFoundException("No seat " + id);
                if (!s.isFree(now)) throw new Exceptions.SeatUnavailableException("Seat " + id + " not available");
                amount += s.type.price;
            }
            String bid = "B" + seq.incrementAndGet();
            long expiry = now + lockTtlMs;
            for (String id : ids) {                                  // then mutate
                ShowSeat s = show.seats.get(id);
                s.status = SeatStatus.LOCKED; s.lockedBy = userId; s.lockExpiryMs = expiry; s.bookingId = bid;
            }
            Booking b = new Booking(bid, userId, showId, ids, amount, expiry);
            bookings.put(bid, b);
            return b;
        } finally { show.lock.unlock(); }
    }

    /** Step 2: pay and confirm. Payment is done OUTSIDE the show lock (slow network call). */
    public Booking confirm(String bookingId) {
        Booking b = bookings.get(bookingId);
        if (b == null) throw new Exceptions.NotFoundException("No booking " + bookingId);
        Show show = show(b.showId);

        show.lock.lock();
        try { assertHeld(show, b); } finally { show.lock.unlock(); }   // fail fast before charging

        boolean paid = gateway.charge(b.userId, b.amount, b.id);

        show.lock.lock();
        try {
            if (!paid) { releaseSeats(show, b); b.status = BookingStatus.FAILED; return b; }
            try { assertHeld(show, b); }                               // lock may have expired during payment
            catch (Exceptions.LockExpiredException e) {
                gateway.refund(b.id); b.status = BookingStatus.EXPIRED; throw e;
            }
            for (String id : b.seatIds) {
                ShowSeat s = show.seats.get(id);
                s.status = SeatStatus.BOOKED; s.lockExpiryMs = 0;
            }
            b.status = BookingStatus.CONFIRMED;
            return b;
        } finally { show.lock.unlock(); }
    }

    /** User abandons / cancels a pending booking. */
    public void cancel(String bookingId) {
        Booking b = bookings.get(bookingId);
        Show show = show(b.showId);
        show.lock.lock();
        try {
            if (b.status == BookingStatus.PENDING) { releaseSeats(show, b); b.status = BookingStatus.CANCELLED; }
        } finally { show.lock.unlock(); }
    }

    /** Optional background sweeper (reads are already correct via lazy expiry; this just frees memory/state). */
    public int sweepExpired() {
        long now = clock.millis(); int n = 0;
        for (Show show : shows.values()) {
            show.lock.lock();
            try {
                for (ShowSeat s : show.seats.values())
                    if (s.status == SeatStatus.LOCKED && now >= s.lockExpiryMs) { s.release(); n++; }
            } finally { show.lock.unlock(); }
        }
        return n;
    }

    private void assertHeld(Show show, Booking b) {
        long now = clock.millis();
        for (String id : b.seatIds) {
            ShowSeat s = show.seats.get(id);
            boolean mine = s.status == SeatStatus.LOCKED && b.id.equals(s.bookingId) && now < s.lockExpiryMs;
            if (!mine) throw new Exceptions.LockExpiredException("Hold on " + id + " expired for " + b.id);
        }
    }
    private void releaseSeats(Show show, Booking b) {
        for (String id : b.seatIds) {
            ShowSeat s = show.seats.get(id);
            if (b.id.equals(s.bookingId) && s.status == SeatStatus.LOCKED) s.release();
        }
    }
    private Show show(String id) {
        Show s = shows.get(id);
        if (s == null) throw new Exceptions.NotFoundException("No show " + id);
        return s;
    }
}

MutableClock.java

import java.time.*;
import java.util.concurrent.atomic.AtomicLong;

/** Test clock so expiry is deterministic. */
public class MutableClock extends Clock {
    private final AtomicLong now = new AtomicLong(1_000_000);
    public void advance(long ms) { now.addAndGet(ms); }
    @Override public long millis() { return now.get(); }
    @Override public Instant instant() { return Instant.ofEpochMilli(now.get()); }
    @Override public ZoneId getZone() { return ZoneOffset.UTC; }
    @Override public Clock withZone(ZoneId z) { return this; }
}

Main.java (demo)

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String[] args) throws Exception {
        MutableClock clock = new MutableClock();
        FakeGateway gw = new FakeGateway();
        BookingService svc = new BookingService(gw, clock, 300_000);   // 5 min hold

        Map<String, SeatType> layout = new LinkedHashMap<>();
        for (int i = 1; i <= 4; i++) layout.put("A" + i, SeatType.SILVER);
        for (int i = 1; i <= 4; i++) layout.put("B" + i, SeatType.GOLD);
        svc.addShow(new Show("S1", "Dune", "Screen-1", layout));

        System.out.println("1) Happy path");
        Booking b1 = svc.lockSeats("alice", "S1", List.of("A1", "A2"));
        System.out.println("   " + b1);
        System.out.println("   available while held: " + svc.availableSeats("S1"));
        System.out.println("   " + svc.confirm(b1.getId()));

        System.out.println("2) Bob tries a seat that is booked / partly held (all-or-nothing)");
        try { svc.lockSeats("bob", "S1", List.of("A3", "A1")); }
        catch (Exceptions.SeatUnavailableException e) { System.out.println("   rejected: " + e.getMessage()); }
        System.out.println("   A3 still free: " + svc.availableSeats("S1").contains("A3"));

        System.out.println("3) Hold expiry (carol holds, never pays)");
        Booking b3 = svc.lockSeats("carol", "S1", List.of("A3"));
        clock.advance(300_001);
        System.out.println("   after 5min A3 free again: " + svc.availableSeats("S1").contains("A3"));
        try { svc.confirm(b3.getId()); } catch (Exceptions.LockExpiredException e) { System.out.println("   carol confirm -> " + e.getMessage()); }
        Booking b3b = svc.lockSeats("dave", "S1", List.of("A3"));
        System.out.println("   dave got it: " + b3b);

        System.out.println("4) Payment failure releases seats");
        gw.failFor("erin");
        Booking b4 = svc.lockSeats("erin", "S1", List.of("B1"));
        System.out.println("   " + svc.confirm(b4.getId()));
        System.out.println("   B1 free: " + svc.availableSeats("S1").contains("B1"));

        System.out.println("5) Lock expires DURING payment -> refund");
        Booking b5 = svc.lockSeats("frank", "S1", List.of("B2"));
        gw.onCharge(() -> clock.advance(300_001));
        try { svc.confirm(b5.getId()); } catch (Exceptions.LockExpiredException e) { System.out.println("   " + e.getMessage() + " status=" + b5.getStatus()); }
        gw.onCharge(() -> {});

        System.out.println("6) Concurrency: 50 users race for B3,B4");
        ExecutorService pool = Executors.newFixedThreadPool(16);
        CountDownLatch start = new CountDownLatch(1);
        AtomicInteger winners = new AtomicInteger();
        List<Future<?>> fs = new ArrayList<>();
        for (int i = 0; i < 50; i++) { final String u = "user" + i;
            fs.add(pool.submit(() -> {
                try { start.await(); Booking b = svc.lockSeats(u, "S1", List.of("B3", "B4"));
                      if (svc.confirm(b.getId()).getStatus() == BookingStatus.CONFIRMED) winners.incrementAndGet();
                } catch (Exceptions.SeatUnavailableException | InterruptedException ignored) {}
            })); }
        start.countDown();
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("   successful bookings = " + winners.get() + " (expected 1)");
        System.out.println("   available now: " + svc.availableSeats("S1"));
    }
}

Actual output (compiled with javac, run with java)

1) Happy path
   Booking{B1, alice, [A1, A2], Rs.400, PENDING}
   available while held: [A3, A4, B1, B2, B3, B4]
   Booking{B1, alice, [A1, A2], Rs.400, CONFIRMED}
2) Bob tries a seat that is booked / partly held (all-or-nothing)
   rejected: Seat A1 not available
   A3 still free: true
3) Hold expiry (carol holds, never pays)
   after 5min A3 free again: true
   carol confirm -> Hold on A3 expired for B2
   dave got it: Booking{B3, dave, [A3], Rs.200, PENDING}
4) Payment failure releases seats
   Booking{B4, erin, [B1], Rs.350, FAILED}
   B1 free: true
5) Lock expires DURING payment -> refund
  [gateway] refunded B5
   Hold on B2 expired for B5 status=EXPIRED
6) Concurrency: 50 users race for B3,B4
   successful bookings = 1 (expected 1)
   available now: [A3, A4, B1, B2]

(Booking ids B1.. are separate from seat ids like B1/B2 - unfortunate naming coincidence in the demo; in scenario 3 "B2" in the message is carol's booking id.)

6. Key flows

lockSeats(user, show, [A1,A2])
  show.lock.lock()
    validate all seats isFree(now)?  no -> SeatUnavailableException (nothing mutated)
    mark LOCKED(user, expiry=now+TTL, bookingId); create Booking PENDING
  unlock

confirm(bookingId)
  lock; assertHeld (still LOCKED by me and not expired); unlock     <- fail fast
  gateway.charge(...)                                                <- no lock held
  lock
    paid?  no  -> release seats, FAILED
    assertHeld fails -> refund, EXPIRED, throw
    else seats -> BOOKED, booking CONFIRMED
  unlock

7. Extensibility

New payment method: implement PaymentGateway; inject.
Dynamic pricing: introduce PricingStrategy used at lock time (price frozen into Booking so it cannot change mid-payment).
Notifications on confirm: Observer/event bus fired after commit (outside lock).
Theater/city catalog: add Theater, Screen, Movie entities and a ShowRepository; BookingService untouched.
Different hold policy (TTL per user tier): inject a LockPolicy.

8. Concurrency and edge cases

Double-booking prevention: check-then-act on seats is atomic under the per-show ReentrantLock; the demo has 50 threads racing for the same two seats and exactly one wins.
Deadlock: a single lock per operation; no nested locks across shows.
Expiry: lazy (isFree) + optional sweepExpired via ScheduledExecutorService. Expiry + confirm race: confirm re-validates now < expiry under lock.
Payment succeeded but hold expired: refund (shown in scenario 5); in production make charge idempotent with bookingId and run a reconciliation job for "charged but not confirmed".
Same user locks again: new booking, old one expires or is cancelled (could also cap holds per user).
Duplicate seat ids in request: deduped. Unknown seat/show: NotFoundException.
Double confirm (retry): second call fails assertHeld on BOOKED seats; better to make confirm idempotent by returning an already CONFIRMED booking (add a status check).
Lock hold TTL trade-off: too long hurts inventory, too short breaks slow UPI payments.

9. Follow-ups and model answers

Make it distributed? Move seat state to a DB/Redis. Option A: DB row per show-seat with UPDATE show_seat SET status='LOCKED', locked_by=?, expiry=? WHERE show_id=? AND seat_id=? AND (status='AVAILABLE' OR expiry<now()) and check affected-rows == seats requested, inside one transaction (all-or-nothing). Option B: Redis SET key NX PX ttl per seat (TTL = expiry, free auto-release) with a Lua script for multi-seat atomicity. Final BOOKED write in the DB with a unique constraint (show_id, seat_id) as the ultimate guard against double booking.
Persist? Bookings and payments in an RDBMS; seat locks in Redis (ephemeral); outbox pattern to publish BookingConfirmed events.
Payment webhooks arriving late? Confirm via idempotent webhook handler keyed by bookingId; if hold gone and seat taken, auto-refund.
Thundering herd for a blockbuster? Virtual waiting room/queue, rate limit (doc 07), shard by showId.
Why not synchronized on the Seat? Multi-seat atomicity needs ordered lock acquisition; per-show lock is simpler and cheap.
Complexity: lockSeats O(k) for k seats; availableSeats O(S) per show; confirm O(k); memory O(shows x seats).

10. Common mistakes and rubric

Red flags: check-then-act without a lock; synchronized on the whole service; holding the lock across the payment call; seat status stored on the physical Seat; locking seats one by one without rollback on partial failure; relying only on a timer thread for expiry; using System.currentTimeMillis() directly (untestable); no refund path for expiry-during-payment; ignoring idempotency. Rubric (10 pts): requirements incl. hold + payment flow 1; model (ShowSeat) 2; atomic multi-seat lock + lock granularity 2; expiry handling 1; payment outside lock + failure paths 2; runnable concurrency demo 1; distributed answer (conditional update/Redis NX) 1.

Previous Blog← LLD Series: Elevator System (LLD)

Next BlogLLD Series: Notification Service (Low-Level Design) →