Design a Movie Ticket Booking System

 City 1---* Theatre 1---* Screen 1---* Seat (id, category)
                            |
 Movie 1---* Show *---------+   Show = movie + screen + start + prices
               |
               | 1
               *
         ShowSeat state  (show, seat) -> AVAILABLE | HELD | BOOKED
               ^                 owner id, hold expiry, version
               |
      SeatInventory  <--- BookingService ---> PaymentGateway
       ^    ^                  |         \--> RefundPolicy
       |    |                  v
 Pessimistic Optimistic      Hold (id, user, show, seats, expiry)
                             Booking (id, user, show, seats, amount, status)

             hold() ok                    confirm() ok
 AVAILABLE --------------> HELD ------------------------> BOOKED
     ^                     |   |                             |
     |  payment declined   |   | hold expiry passes          |
     +---------------------+   | (lazy: treated as free)     |
     ^                         |                             |
     +-------------------------+                             |
     |                    cancel()                           |
     +-------------------------------------------------------+

boolean isFreeAt(Instant now) {
    return status == SeatStatus.AVAILABLE
        || (status == SeatStatus.HELD && !now.isBefore(holdExpiresAt));
}

for (String id : ids) if (!state(showId, id).isFreeAt(now)) return false;  // check
for (String id : ids) ref(showId, id).set(held(...));                       // act

time   Alice's request                 Bob's request
 t1    read A5 -> AVAILABLE
 t2                                    read A5 -> AVAILABLE
 t3    write A5 = HELD by alice
 t4                                    write A5 = HELD by bob  (overwrites)
 t5    "A5 is yours"                   "A5 is yours"

time   Alice                          Bob
 t1    lock(A5)
 t2    read A5 -> AVAILABLE           lock(A5)  ... waits
 t3    write A5 = HELD by alice           ... waits
 t4    unlock(A5)                     acquires lock
 t5                                   read A5 -> HELD: return false

List<String> sorted = new ArrayList<>(ids);
Collections.sort(sorted);                 // global order: seat id
for (String id : sorted) locks.get(id).lock();

BEGIN;
SELECT status, hold_expires_at FROM show_seat
 WHERE show_id = 42 AND seat_id IN ('A3','A4')
 ORDER BY seat_id
 FOR UPDATE;            -- row locks, taken in seat order
-- if every row is free:
UPDATE show_seat SET status = 'HELD', owner = 'H17', hold_expires_at = now() + interval '10 minutes'
 WHERE show_id = 42 AND seat_id IN ('A3','A4');
COMMIT;

time   Alice                                   Bob
 t1    read A5 (AVAILABLE, v7)
 t2                                            read A5 (AVAILABLE, v7)
 t3    CAS A5: v7 -> HELD v8   success
 t4                                            CAS A5: v7 -> HELD v8  FAILS
 t5    "A5 is yours"                           "seat just taken"

UPDATE show_seat
   SET status = 'HELD', owner = 'H17', version = version + 1,
       hold_expires_at = now() + interval '10 minutes'
 WHERE show_id = 42 AND seat_id = 'A5' AND version = 7;
-- 1 row updated: you won.  0 rows updated: someone else changed it.

1. Look up the hold; fail if unknown.
2. If the hold already expired: fail, ask the user to choose again.
3. Charge the user.
   - Declined: release the seats now (do not wait for expiry), fail.
4. Confirm the hold in the inventory (atomic: still HELD, still mine, not expired).
   - If confirm fails (hold expired while paying, or was taken): refund in full.
5. Record the booking.

more than 24 h before the show  -> 100%
more than 4 h, up to 24 h       ->  50%
4 h or less                     ->   0%

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

// ---------- Catalogue: cities, theatres, screens, shows ----------

record City(String name) {}
record Movie(String id, String title, int minutes) {}
enum SeatCategory { REGULAR, PREMIUM }
record Seat(String id, SeatCategory category) {}               // id like "A5"
record Screen(String id, List<Seat> seats) {}
record Theatre(String id, String name, City city, List<Screen> screens) {}
record Show(String id, Movie movie, Theatre theatre, Screen screen, Instant start,
            Map<SeatCategory, Long> price) {}

// ---------- Seat state for one show ----------

enum SeatStatus { AVAILABLE, HELD, BOOKED }

/** Immutable snapshot of one seat in one show. A new object replaces it on every change. */
record SeatState(SeatStatus status, String ownerId, Instant holdExpiresAt, long version) {
    static SeatState available(long version) { return new SeatState(SeatStatus.AVAILABLE, null, null, version); }

    /** Lazy expiry: a hold past its deadline counts as available without any background job. */
    boolean isFreeAt(Instant now) {
        return status == SeatStatus.AVAILABLE
                || (status == SeatStatus.HELD && !now.isBefore(holdExpiresAt));
    }
}

/** The contract every locking approach implements. */
interface SeatInventory {
    /** Hold all seats or none. Returns false if any seat is taken. */
    boolean hold(String showId, List<String> seatIds, String holdId, Instant now, Instant expiresAt);
    /** Turn a still-valid hold into a booking. */
    boolean confirm(String showId, List<String> seatIds, String holdId, String bookingId, Instant now);
    void release(String showId, List<String> seatIds, String ownerId);
    SeatState state(String showId, String seatId);
    String name();
}

abstract class BaseInventory implements SeatInventory {
    protected final Map<String, AtomicReference<SeatState>> seats = new ConcurrentHashMap<>();

    void addShow(Show show) {
        for (Seat s : show.screen().seats()) seats.put(key(show.id(), s.id()), new AtomicReference<>(SeatState.available(0)));
    }

    static String key(String showId, String seatId) { return showId + "/" + seatId; }
    AtomicReference<SeatState> ref(String showId, String seatId) {
        AtomicReference<SeatState> r = seats.get(key(showId, seatId));
        if (r == null) throw new NoSuchElementException("no seat " + seatId + " in " + showId);
        return r;
    }
    public SeatState state(String showId, String seatId) { return ref(showId, seatId).get(); }

    public void release(String showId, List<String> seatIds, String ownerId) {
        for (String id : seatIds) {
            AtomicReference<SeatState> r = ref(showId, id);
            SeatState cur = r.get();
            if (ownerId.equals(cur.ownerId())) r.compareAndSet(cur, SeatState.available(cur.version() + 1));
        }
    }
}

/** Deliberately broken: check, then act, with a gap in between. Used only to show the race. */
final class NaiveInventory extends BaseInventory {
    private final CyclicBarrier gap;
    NaiveInventory(CyclicBarrier gap) { this.gap = gap; }
    public String name() { return "naive"; }

    public boolean hold(String showId, List<String> ids, String holdId, Instant now, Instant exp) {
        for (String id : ids) if (!state(showId, id).isFreeAt(now)) return false;   // check
        try { gap.await(); } catch (Exception e) { throw new RuntimeException(e); }  // both threads get here
        for (String id : ids) {                                                       // act
            AtomicReference<SeatState> r = ref(showId, id);
            r.set(new SeatState(SeatStatus.HELD, holdId, exp, r.get().version() + 1));
        }
        return true;
    }
    public boolean confirm(String s, List<String> ids, String h, String b, Instant now) { return false; }
}

/** Pessimistic: lock each seat before reading it. Locks are taken in sorted order, so no deadlock. */
final class PessimisticInventory extends BaseInventory {
    private final Map<String, ReentrantLock> locks = new ConcurrentHashMap<>();
    public String name() { return "pessimistic"; }

    private List<ReentrantLock> lockAll(String showId, List<String> ids) {
        List<String> sorted = new ArrayList<>(ids);
        Collections.sort(sorted);                                   // global order: seat id
        List<ReentrantLock> taken = new ArrayList<>();
        for (String id : sorted) {
            ReentrantLock l = locks.computeIfAbsent(key(showId, id), k -> new ReentrantLock());
            l.lock();
            taken.add(l);
        }
        return taken;
    }
    private static void unlockAll(List<ReentrantLock> taken) {
        for (int i = taken.size() - 1; i >= 0; i--) taken.get(i).unlock();
    }

    public boolean hold(String showId, List<String> ids, String holdId, Instant now, Instant exp) {
        List<ReentrantLock> taken = lockAll(showId, ids);
        try {
            for (String id : ids) if (!state(showId, id).isFreeAt(now)) return false;
            for (String id : ids) {
                AtomicReference<SeatState> r = ref(showId, id);
                r.set(new SeatState(SeatStatus.HELD, holdId, exp, r.get().version() + 1));
            }
            return true;
        } finally { unlockAll(taken); }
    }

    public boolean confirm(String showId, List<String> ids, String holdId, String bookingId, Instant now) {
        List<ReentrantLock> taken = lockAll(showId, ids);
        try {
            for (String id : ids) {
                SeatState s = state(showId, id);
                if (s.status() != SeatStatus.HELD || !holdId.equals(s.ownerId()) || !now.isBefore(s.holdExpiresAt())) return false;
            }
            for (String id : ids) {
                AtomicReference<SeatState> r = ref(showId, id);
                r.set(new SeatState(SeatStatus.BOOKED, bookingId, null, r.get().version() + 1));
            }
            return true;
        } finally { unlockAll(taken); }
    }
}

/** Optimistic: no locks. Read versions, then compare-and-set each seat; on any conflict undo and fail. */
final class OptimisticInventory extends BaseInventory {
    final AtomicInteger conflicts = new AtomicInteger();
    public String name() { return "optimistic"; }

    private boolean swapAll(String showId, List<String> ids, Map<String, SeatState> expected,
                            java.util.function.Function<SeatState, SeatState> change) {
        List<String> done = new ArrayList<>();
        for (String id : ids) {
            SeatState old = expected.get(id);
            if (ref(showId, id).compareAndSet(old, change.apply(old))) { done.add(id); continue; }
            conflicts.incrementAndGet();                             // someone changed it since we read it
            for (String d : done) {                                  // compensate: put back what we changed
                AtomicReference<SeatState> r = ref(showId, d);
                SeatState mine = r.get();
                r.compareAndSet(mine, new SeatState(expected.get(d).status(), expected.get(d).ownerId(),
                        expected.get(d).holdExpiresAt(), mine.version() + 1));
            }
            return false;
        }
        return true;
    }

    public boolean hold(String showId, List<String> ids, String holdId, Instant now, Instant exp) {
        Map<String, SeatState> read = new HashMap<>();
        for (String id : ids) {
            SeatState s = state(showId, id);
            if (!s.isFreeAt(now)) return false;
            read.put(id, s);
        }
        return swapAll(showId, ids, read, old -> new SeatState(SeatStatus.HELD, holdId, exp, old.version() + 1));
    }

    public boolean confirm(String showId, List<String> ids, String holdId, String bookingId, Instant now) {
        Map<String, SeatState> read = new HashMap<>();
        for (String id : ids) {
            SeatState s = state(showId, id);
            if (s.status() != SeatStatus.HELD || !holdId.equals(s.ownerId()) || !now.isBefore(s.holdExpiresAt())) return false;
            read.put(id, s);
        }
        return swapAll(showId, ids, read, old -> new SeatState(SeatStatus.BOOKED, bookingId, null, old.version() + 1));
    }
}

// ---------- Payment and refunds ----------

interface PaymentGateway { boolean charge(String userId, long amount); void refund(String userId, long amount); }

final class FakeGateway implements PaymentGateway {
    private final Set<String> declineUsers;
    final List<String> ledger = new ArrayList<>();
    FakeGateway(Set<String> declineUsers) { this.declineUsers = declineUsers; }
    public boolean charge(String user, long amount) {
        boolean ok = !declineUsers.contains(user);
        ledger.add((ok ? "charged " : "declined ") + user + " Rs " + amount);
        return ok;
    }
    public void refund(String user, long amount) { ledger.add("refunded " + user + " Rs " + amount); }
}

interface RefundPolicy { int refundPercent(Duration beforeShow); }

/** 100% if more than 24 h before the show, 50% if more than 4 h, otherwise nothing. */
final class TieredRefundPolicy implements RefundPolicy {
    public int refundPercent(Duration before) {
        if (before.compareTo(Duration.ofHours(24)) > 0) return 100;
        if (before.compareTo(Duration.ofHours(4)) > 0) return 50;
        return 0;
    }
}

// ---------- Booking service ----------

enum BookingStatus { CONFIRMED, CANCELLED }

final class Booking {
    final String id, userId; final Show show; final List<String> seats; final long amount;
    BookingStatus status = BookingStatus.CONFIRMED;
    Booking(String id, String userId, Show show, List<String> seats, long amount) {
        this.id = id; this.userId = userId; this.show = show; this.seats = List.copyOf(seats); this.amount = amount;
    }
    public String toString() { return id + " " + userId + " " + show.movie().title() + " " + seats + " Rs " + amount + " " + status; }
}

record Hold(String id, String userId, Show show, List<String> seats, Instant expiresAt) {}

final class BookingService {
    static final Duration HOLD_TIME = Duration.ofMinutes(10);
    private final SeatInventory inventory;
    private final PaymentGateway gateway;
    private final RefundPolicy refunds;
    private final Clock clock;
    private final Map<String, Show> shows = new ConcurrentHashMap<>();
    private final Map<String, Hold> holds = new ConcurrentHashMap<>();
    private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
    private final AtomicLong seq = new AtomicLong();

    BookingService(SeatInventory inventory, PaymentGateway gateway, RefundPolicy refunds, Clock clock) {
        this.inventory = inventory; this.gateway = gateway; this.refunds = refunds; this.clock = clock;
    }

    void addShow(Show s) { shows.put(s.id(), s); ((BaseInventory) inventory).addShow(s); }

    List<Show> showsFor(String city, String movieTitle) {
        return shows.values().stream()
                .filter(s -> s.theatre().city().name().equals(city) && s.movie().title().equals(movieTitle))
                .sorted(Comparator.comparing(Show::start)).toList();
    }

    List<String> availableSeats(String showId) {
        Instant now = clock.instant();
        return shows.get(showId).screen().seats().stream().map(Seat::id)
                .filter(id -> inventory.state(showId, id).isFreeAt(now)).toList();
    }

    Optional<Hold> hold(String userId, String showId, List<String> seatIds) {
        Show show = shows.get(showId);
        if (!clock.instant().isBefore(show.start())) throw new IllegalStateException("show already started");
        if (seatIds.isEmpty() || seatIds.size() > 10) throw new IllegalArgumentException("1 to 10 seats");
        String holdId = "H" + seq.incrementAndGet();
        Instant now = clock.instant(), expires = now.plus(HOLD_TIME);
        if (!inventory.hold(showId, seatIds, holdId, now, expires)) return Optional.empty();
        Hold h = new Hold(holdId, userId, show, List.copyOf(seatIds), expires);
        holds.put(holdId, h);
        return Optional.of(h);
    }

    long price(Show show, List<String> seatIds) {
        Map<String, Seat> byId = new HashMap<>();
        for (Seat s : show.screen().seats()) byId.put(s.id(), s);
        return seatIds.stream().mapToLong(id -> show.price().get(byId.get(id).category())).sum();
    }

    /** Pay, then confirm. If the hold expired while paying, refund in full. */
    Booking book(String holdId) {
        Hold h = holds.remove(holdId);
        if (h == null) throw new IllegalStateException("unknown hold " + holdId);
        if (!clock.instant().isBefore(h.expiresAt())) {
            throw new IllegalStateException("hold " + holdId + " expired, choose seats again");
        }
        long amount = price(h.show(), h.seats());
        if (!gateway.charge(h.userId(), amount)) {
            inventory.release(h.show().id(), h.seats(), holdId);
            throw new IllegalStateException("payment declined, seats released");
        }
        String bookingId = "BK" + seq.incrementAndGet();
        if (!inventory.confirm(h.show().id(), h.seats(), holdId, bookingId, clock.instant())) {
            gateway.refund(h.userId(), amount);                         // compensating action
            throw new IllegalStateException("hold lost during payment, refunded");
        }
        Booking b = new Booking(bookingId, h.userId(), h.show(), h.seats(), amount);
        bookings.put(bookingId, b);
        return b;
    }

    long cancel(String bookingId, String userId) {
        Booking b = bookings.get(bookingId);
        if (b == null || !b.userId.equals(userId)) throw new NoSuchElementException("no such booking");
        synchronized (b) {
            if (b.status == BookingStatus.CANCELLED) throw new IllegalStateException("already cancelled");
            int pct = refunds.refundPercent(Duration.between(clock.instant(), b.show.start()));
            long refund = b.amount * pct / 100;
            b.status = BookingStatus.CANCELLED;
            inventory.release(b.show.id(), b.seats, bookingId);
            if (refund > 0) gateway.refund(userId, refund);
            return refund;
        }
    }
}

final class ManualClock extends Clock {
    private volatile Instant now;
    ManualClock(Instant start) { now = start; }
    void advance(Duration d) { now = now.plus(d); }
    public Instant instant() { return now; }
    public ZoneId getZone() { return ZoneOffset.UTC; }
    public Clock withZone(ZoneId z) { return this; }
}

public class MovieBookingDemo {
    static Show sampleShow(String id, Instant start) {
        List<Seat> seats = new ArrayList<>();
        for (char row : new char[] { 'A', 'B' })
            for (int n = 1; n <= 6; n++)
                seats.add(new Seat("" + row + n, row == 'A' ? SeatCategory.PREMIUM : SeatCategory.REGULAR));
        Screen screen = new Screen("S1", seats);
        Theatre t = new Theatre("T1", "Lakeview Cinemas", new City("Bengaluru"), List.of(screen));
        return new Show(id, new Movie("M1", "The Long Monsoon", 150), t, screen, start,
                Map.of(SeatCategory.PREMIUM, 350L, SeatCategory.REGULAR, 200L));
    }

    /** 200 threads each try to hold two adjacent seats in row A, half of them listing seats in reverse. */
    static void race(BaseInventory inv) throws Exception {
        Show show = sampleShow("SHOW-RACE", Instant.parse("2026-10-12T13:00:00Z"));
        inv.addShow(show);
        Instant now = Instant.parse("2026-10-12T10:00:00Z"), exp = now.plusSeconds(600);
        ExecutorService pool = Executors.newFixedThreadPool(16);
        CountDownLatch go = new CountDownLatch(1);
        List<Future<List<String>>> fs = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            final int n = i;
            fs.add(pool.submit(() -> {
                int first = n % 5 + 1;                                   // pairs A1A2, A2A3 ... A5A6
                List<String> want = new ArrayList<>(List.of("A" + first, "A" + (first + 1)));
                if (n % 2 == 1) Collections.reverse(want);
                go.await();
                return inv.hold(show.id(), want, "U" + n, now, exp) ? want : null;
            }));
        }
        go.countDown();
        Map<String, Integer> heldBy = new TreeMap<>();
        int winners = 0;
        for (Future<List<String>> f : fs) {
            List<String> got = f.get();
            if (got == null) continue;
            winners++;
            for (String s : got) heldBy.merge(s, 1, Integer::sum);
        }
        pool.shutdown();
        boolean doubleBooked = heldBy.values().stream().anyMatch(c -> c > 1);
        // How many threads win (2 or 3) depends on timing; the invariants below must always hold.
        System.out.printf("%-11s every winner got 2 distinct seats: %s, any seat held twice: %s%n",
                inv.name(), heldBy.size() == 2 * winners, doubleBooked);
    }

    public static void main(String[] args) throws Exception {
        System.out.println("== 1. The double-booking race (naive check-then-act) ==");
        NaiveInventory naive = new NaiveInventory(new CyclicBarrier(2));
        Show s0 = sampleShow("SHOW-0", Instant.parse("2026-10-12T13:00:00Z"));
        naive.addShow(s0);
        Instant t0 = Instant.parse("2026-10-12T10:00:00Z");
        ExecutorService two = Executors.newFixedThreadPool(2);
        Future<Boolean> a = two.submit(() -> naive.hold("SHOW-0", List.of("A5"), "alice", t0, t0.plusSeconds(600)));
        Future<Boolean> b = two.submit(() -> naive.hold("SHOW-0", List.of("A5"), "bob", t0, t0.plusSeconds(600)));
        System.out.println("alice got A5: " + a.get() + ", bob got A5: " + b.get()
                + "  <- both were told yes; one hold silently overwrote the other");
        two.shutdown();

        System.out.println("== 2. Same race, 200 threads, overlapping pairs ==");
        race(new PessimisticInventory());
        race(new OptimisticInventory());

        System.out.println("== 3. Search, hold, pay, book ==");
        ManualClock clock = new ManualClock(Instant.parse("2026-10-11T08:00:00Z"));
        FakeGateway gw = new FakeGateway(Set.of("carol"));
        BookingService svc = new BookingService(new PessimisticInventory(), gw, new TieredRefundPolicy(), clock);
        Show evening = sampleShow("SHOW-1", Instant.parse("2026-10-12T13:00:00Z"));   // 18:30 IST
        svc.addShow(evening);
        System.out.println("shows: " + svc.showsFor("Bengaluru", "The Long Monsoon").stream().map(Show::id).toList());
        Hold dev = svc.hold("dev", "SHOW-1", List.of("A3", "A4")).orElseThrow();
        System.out.println("dev holds " + dev.seats() + " until " + dev.expiresAt());
        System.out.println("meena tries A4,A5 -> " + svc.hold("meena", "SHOW-1", List.of("A4", "A5")).isPresent());
        Booking devBooking = svc.book(dev.id());
        System.out.println("booked: " + devBooking);

        System.out.println("== 4. Payment declined releases the hold ==");
        Hold carol = svc.hold("carol", "SHOW-1", List.of("B1")).orElseThrow();
        try { svc.book(carol.id()); } catch (IllegalStateException e) { System.out.println("carol: " + e.getMessage()); }
        System.out.println("B1 available again: " + svc.availableSeats("SHOW-1").contains("B1"));

        System.out.println("== 5. Hold expiry ==");
        Hold farah = svc.hold("farah", "SHOW-1", List.of("B5", "B6")).orElseThrow();
        clock.advance(Duration.ofMinutes(11));
        Hold gopal = svc.hold("gopal", "SHOW-1", List.of("B6")).orElseThrow();
        System.out.println("after 11 min gopal holds " + gopal.seats());
        try { svc.book(farah.id()); } catch (IllegalStateException e) { System.out.println("farah: " + e.getMessage()); }
        svc.book(gopal.id());
        System.out.println("free seats: " + svc.availableSeats("SHOW-1"));

        System.out.println("== 6. Cancellation and refunds ==");
        Hold h1 = svc.hold("hari", "SHOW-1", List.of("B2", "B3")).orElseThrow();
        Booking hb = svc.book(h1.id());
        System.out.println("time to show: " + Duration.between(clock.instant(), evening.start()).toHours() + " h");
        System.out.println("hari cancels, refund Rs " + svc.cancel(hb.id, "hari"));
        clock.advance(Duration.ofHours(20));
        System.out.println("time to show: " + Duration.between(clock.instant(), evening.start()).toHours() + " h");
        System.out.println("dev cancels, refund Rs " + svc.cancel(devBooking.id, "dev"));
        try { svc.cancel(devBooking.id, "dev"); } catch (IllegalStateException e) { System.out.println("dev again: " + e.getMessage()); }
        System.out.println("ledger: " + gw.ledger);
    }
}

== 1. The double-booking race (naive check-then-act) ==
alice got A5: true, bob got A5: true  <- both were told yes; one hold silently overwrote the other
== 2. Same race, 200 threads, overlapping pairs ==
pessimistic every winner got 2 distinct seats: true, any seat held twice: false
optimistic  every winner got 2 distinct seats: true, any seat held twice: false
== 3. Search, hold, pay, book ==
shows: [SHOW-1]
dev holds [A3, A4] until 2026-10-11T08:10:00Z
meena tries A4,A5 -> false
booked: BK3 dev The Long Monsoon [A3, A4] Rs 700 CONFIRMED
== 4. Payment declined releases the hold ==
carol: payment declined, seats released
B1 available again: true
== 5. Hold expiry ==
after 11 min gopal holds [B6]
farah: hold H5 expired, choose seats again
free seats: [A1, A2, A5, A6, B1, B2, B3, B4, B5]
== 6. Cancellation and refunds ==
time to show: 28 h
hari cancels, refund Rs 400
time to show: 8 h
dev cancels, refund Rs 350
dev again: already cancelled
ledger: [charged dev Rs 700, declined carol Rs 200, charged gopal Rs 200, charged hari Rs 400, refunded hari Rs 400, refunded dev Rs 350]