Skip to main content

Low-Level Design: BookMyShow Seat Booking in Java (Handling Concurrent Bookings)

Build a BookMyShow-style seat booking system in Java: start with the version that sells one seat twice, fix it with locks and with compare-and-set, then add expiring holds, payment timeouts and a database version. Every output is from a real JDK 25 run.

Two people open the seat map for the same show. Both tap seat C5. Both taps reach your servers within the same millisecond. Exactly one of them may get that seat — and the other has to find out now, not after typing in a card number. This post builds the core of a BookMyShow-style seat booking system in Java. It starts with the version everyone writes first, which sells one seat twice, and ends with two correct designs, holds that expire, payments that time out, and what changes when the seat state has to live outside the JVM. It is the classic low-level design interview question, and every claim here was compiled and run on JDK 25: every number and console line below is quoted from a file in the companion module (regenerate them all with ./scripts/run-all.sh, script here), and every code block and output block links to the file it came from. You do not need to know anything about concurrency. The sections run in difficulty order and the collapsible “going deeper” panels hold the intermediate and reference-level material, so read straight through the first time and open the panels later. The same style of low-level design walk-through, for a simpler problem, is in Parking Lot System.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS; the java -version banner reads 2026-10-20), JUnit 6.1.3 (the latest GA on Maven Central, taken from maven-metadata.xml for junit-bom; 6.2.0-M1 is a milestone, and the <release> element in that file points at it), H2 2.5.252 for the database section only, and Maven 3.9.11. No frameworks: everything except section 10 is plain Java.

Two people tap the same seat; exactly one may get it

Before any code, the rules of the game. A show has a fixed set of seats. A customer picks one or more seats and has a few minutes to pay. While they pay, nobody else may take those seats. If they pay in time, the seats are theirs. If they do not, the seats go back on sale. And under no circumstances may one seat belong to two people. That is five requirements: hold seats, expire the hold, confirm after payment, never sell a seat twice, and cope with payment being slow or failing. Four of them are bookkeeping. The fourth — never twice — is the whole difficulty, because it has to stay true when many threads are asking at once. Here is the shape of the solution before any code.
BookingServicehold, pay, confirmPaymentGatewaycharge, refundClockMutableClock in the testsSeatInventory (interface)tryHold, confirm, releaseNaiveInventorycheck, then act (wrong)PessimisticInventorya lock per seatOptimisticInventorycompare-and-set per seatAll three keep one SeatSlot per seat. They differ only in how they stop two threads changing it at once.
BookingService is what a web controller would call: start a booking, pay for it. It never touches a lock. Everything that decides who gets a seat sits behind one interface, SeatInventory, and this post builds three versions of it — one wrong and two right — so you can see the bug and both cures side by side. The clock and the payment gateway are injected, which is what lets the tests check five-minute expiry without waiting five minutes. The whole interface is three verbs, in SeatInventory.java:
    /** Attempts to hold every seat for {@code holdId} for {@code ttl}. Returns false, changing nothing observable, if any seat is taken. */
    boolean tryHold(String showId, List<String> seatIds, String holdId, Duration ttl);

    /** Turns {@code holdId}'s unexpired holds on all these seats into BOOKED. False (and nothing booked) if any hold is missing, expired or not owned. */
    boolean confirm(String showId, List<String> seatIds, String holdId);

    /** Frees the seats that {@code holdId} still holds. Seats held by anyone else, or already booked, are left alone. */
    void release(String showId, List<String> seatIds, String holdId);
Going deeper: why one interface, and what this module leaves out Putting all the concurrency behind SeatInventory is what makes the comparison honest. The same BookingService, the same fixtures and the same single-threaded test run against all three implementations, and HappyPathTest.java asserts that they produce an identical log when only one user is active. If they differed there, the concurrent results later would be comparing different things. The shared parts — show registry, argument validation, the seat summary — live in AbstractSeatInventory.java, so each implementation contains only its synchronisation strategy. tryHold is all-or-nothing: a booking of three seats either holds all three or none, which is the property that makes sections 5, 6 and 9 interesting. Deliberately out of scope: cancelling a confirmed booking, refunds beyond the one payment-timeout case, multiple cities and screens, seat-map rendering, and persistence (section 10 shows the persistence question for a single seat).
Going deeper
  • Show.java — the screening and its 6×10 seat grid, with price by seat category
  • AbstractSeatInventory.java — validation and the seat summary shared by all three
  • Fixtures.java — the common show, clock and inventory setup the tests use

A seat is a tiny state machine, and a hold is a state with a deadline

A seat for one show is in exactly one of three states. It is AVAILABLE when nobody has a claim on it, HELD when someone has a claim that will lapse, and BOOKED when it has been paid for. Why a middle state at all? Because paying takes minutes. If seats were only ever AVAILABLE or BOOKED, you would have to either sell the seat the moment someone taps it (and lose money when they abandon the payment page) or let several people fill in card details for the same seat (and tell all but one of them “sorry” afterwards). A hold is a reservation with a stopwatch.
AVAILABLEnobody has a claimHELDowner and expiresAtBOOKEDpaid fortryHold(holdId, ttl)confirmsame holdId,before expiresAtrelease, cancel, or the clock reaches expiresAtExpiry is not an event. Nothing runs at expiresAt; every reader compares the clock with the slot.
Read the diagram left to right: a hold is placed with an owner and a time-to-live, a confirm by the same owner turns it into a booking, and a release, a cancel or the passing of time sends it back. The last point matters most: nothing runs at the deadline. The module has no timer and no background thread. Instead every reader asks the slot “what are you, at this moment?” and the slot answers. The rest of the design hangs off the small immutable record in SeatSlot.java:
    /**
     * What a reader should believe at {@code now}. A hold is valid strictly before {@code expiresAt}; at the
     * expiry instant itself it is already gone. Expiry is lazy: nothing rewrites the slot, readers just do this check.
     */
    public SeatState effectiveState(Instant now) {
        if (state == SeatState.HELD && !now.isBefore(expiresAt)) {
            return SeatState.AVAILABLE;
        }
        return state;
    }

    /** True when {@code holdId} owns a hold that has not expired at {@code now}. This is the check confirm() relies on. */
    public boolean isHeldBy(String holdId, Instant now) {
        return state == SeatState.HELD && this.holdId.equals(holdId) && now.isBefore(expiresAt);
    }
effectiveState is the expiry rule: a HELD slot whose time has come reads as AVAILABLE, and the deadline instant itself already counts as expired. isHeldBy is the question confirm asks: “is this still your unexpired hold?” Every change of state creates a new SeatSlot with version + 1; keep that in mind, because it is what makes the optimistic design in section 6 possible and what the transcripts use to show what happened to a seat.
Going deeper: lazy expiry versus a sweeper, and the two ownership checks Lazy expiry means an expired hold stays in the map as a HELD slot until somebody overwrites or reads it. The benefit is that expiry is exact and testable — section 8 moves a fake clock to T+04:59 and T+05:00 and the seat flips — and that there is no timer thread to race with the booking threads. The cost is memory held by dead holds on seats nobody asks about again; a periodic sweeper that rewrites expired slots to AVAILABLE would reclaim that. This module does not implement one, and nothing in the article depends on it. There are two ownership checks on purpose. isHeldBy(holdId, now) also requires the hold to be unexpired, and confirm uses it: you cannot buy a seat with a lapsed hold. ownsHold(holdId) ignores expiry, and release uses it: releasing your own lapsed hold is harmless, and releasing someone else’s hold must never work (section 9 shows both in the transcript).
Going deeper

The smallest flow that works: hold, pay, confirm

With one user at a time there is nothing clever to do. Asha picks A1 and A2; the service asks the inventory to hold both for five minutes and returns a booking in PENDING_PAYMENT. Ravi then asks for A2 and A3 and is refused, because A2 is spoken for. Asha pays; the inventory turns her holds into bookings. The method that starts a booking is short, in BookingService.java:
    /** Step 1: put a time-limited hold on the seats. Throws {@link SeatUnavailableException} if any seat is taken. */
    public Booking startBooking(String userId, String showId, List<String> seatIds) {
        Show show = inventory.show(showId);
        String bookingId = "BK-%04d".formatted(sequence.incrementAndGet());
        if (!inventory.tryHold(showId, seatIds, bookingId, holdTtl)) {
            throw new SeatUnavailableException(showId, seatIds);
        }
        Instant now = clock.instant();
        Booking b = new Booking(bookingId, userId, showId, List.copyOf(seatIds), show.priceOf(seatIds),
                now, now.plus(holdTtl), BookingStatus.PENDING_PAYMENT);
        bookings.put(bookingId, b);
        return b;
    }
The booking id doubles as the hold id: it is the owner token written into every seat the booking holds, and the only thing that later lets confirm and release tell Asha’s seats from Ravi’s. This is the real run, written by HappyPathTest.java to output/01-happy-path.txt:
A1 at the start:          AVAILABLE                          v0
startBooking(asha, A1+A2): BK-0001 PENDING_PAYMENT, Rs 440
A1 after the hold:        HELD    by BK-0001 until T+05:00  v1
A3 untouched:             AVAILABLE                          v0
startBooking(ravi, A2+A3): refused (seats not available for show SH-1: [A2, A3])
A3 after ravi's refusal:  AVAILABLE                          v0
pay(BK-0001):              CONFIRMED, booking is CONFIRMED
A1 after payment:         BOOKED  by BK-0001                v2
seat summary:             {AVAILABLE=58, BOOKED=2, HELD=0}
Three details are worth reading twice. A1 goes from v0 to v1 when held and v2 when booked: one version per transition. Ravi’s refusal leaves A3 at v0, so a refused request did not disturb a seat it never needed. And the price is Rs 440 because Show.priceOf adds the two Rs 220 regular seats.
Why hold first, rather than just checking at payment time? Because the check has to happen when the customer is still choosing, not after they have typed a card number. If you only verified availability at payment, two people could both sit on the payment page for seat C5 and one of them would learn, after paying, that the seat was never theirs. The hold moves the “sorry” to the moment of the tap.
Going deeper: one log, three implementations The test runs this exact flow against NaiveInventory, PessimisticInventory and OptimisticInventory and asserts the three logs are equal, including the version numbers. The last line of the transcript says so. It matters because it pins the single-threaded contract: everything that differs between the three from here on is a concurrency effect, not a difference in what a hold means. The seat summary at the end counts effective states (expiry applied), via AbstractSeatInventory.summary, so it is correct even when expired holds are still sitting in the map as HELD.
Going deeper

Where it breaks: check, then act, with two threads

Here is the version most people write first. It is not careless; each line is reasonable. It looks at every requested seat, and if they are all free it marks them held. This is NaiveInventory.java:
    public boolean tryHold(String showId, List<String> seatIds, String holdId, Duration ttl) {
        validate(showId, seatIds);
        Map<String, SeatSlot> m = slots.get(showId);
        Instant now = clock.instant();
        for (String id : seatIds) {                                  // CHECK
            if (m.get(id).effectiveState(now) != SeatState.AVAILABLE) {
                return false;
            }
        }
        gap.run();                                                   // <- another thread can act here
        Instant expiresAt = now.plus(ttl);
        for (String id : seatIds) {                                  // ACT
            m.put(id, m.get(id).held(holdId, expiresAt));
        }
        return true;
    }
Notice what it is not: it is not using a plain HashMap. The seats live in a ConcurrentHashMap, which is safe for many threads — no operation can corrupt the map. And it is still wrong. A thread-safe collection makes each single call safe; it does nothing about the gap between two calls. The code checks, then acts, and another thread can slip in between.
Thread 1 (Asha)Thread 2 (Ravi)1. read C5: AVAILABLE2. read C5: AVAILABLE3. write C5: HELD by BK-00014. write C5: HELD by BK-0002timeBoth reads finish before either write starts, so both threads believe the seat is free.Two holds are granted for one seat. The second write silently replaces the first.
The diagram is the whole bug. Thread 1 reads C5 and sees AVAILABLE. Before it writes, thread 2 also reads C5 and sees AVAILABLE. Now both are entitled, by their own logic, to proceed, and both do. The second write overwrites the first. Nobody did anything unusual; the interleaving alone broke the guarantee. To make this happen on every run instead of once in a few thousand, the test (see the panel below) stops both threads in the gap between the check and the write until both have arrived. Run through RaceConditionTest.java, it produces output/02-naive-race.txt:
holds granted for C5:        2  (a seat can only be sold once)
both users now pay:
  outcomes (sorted):         [CONFIRMED, HOLD_LOST_AFTER_PAYMENT]
  customers charged:         2
  customers refunded:        1
Two holds for one seat. Both customers were told they had the seat and both were charged; one was then refunded. The damage here is a bad experience rather than two tickets for one seat, but only because confirm happens to check the owner. The hold itself was already wrong. Is that a contrived race that only a barrier can produce? The question deserves a direct answer, so the contention test fires 200 threads at one seat, 30 times, without any barrier inside the inventory. The control line for the naive version, from output/04-contention.txt:
NaiveInventory:       rounds with exactly one winner: 10 of 30
In the committed run, only 10 of 30 rounds ended with exactly one winner; the other rounds granted the seat to more than one thread. Earlier runs of the same test printed 12, 11 and 9, so treat the figure as indicative. And the same experiment first written with virtual threads printed 30 of 30 on this 2-vCPU sandbox — the threads mostly ran one after another, the bug never fired, and the test passed. That version was not kept, and the lesson is in the next callout.
A passing concurrency test proves little. A race needs real overlap to show itself, and whether you get overlap depends on the machine, the thread type and luck. The reliable tests are the ones that force the interleaving, which is what the barrier does, and the ones that assert an invariant over thousands of attempts, which is section 7.
Going deeper: how the barrier forces the race, and why confirm caught it NaiveInventory has one test seam: a hook that runs exactly between the check loop and the write loop. In production it is a no-op. The test installs a two-party CyclicBarrier there, so the first thread to finish checking waits until the second has also finished checking, and only then do both write. In RaceConditionTest.java:
        CyclicBarrier bothHaveChecked = new CyclicBarrier(2);
        inv.betweenCheckAndAct(() -> {
            try {
                bothHaveChecked.await(10, TimeUnit.SECONDS);
            } catch (Exception e) {
                throw new IllegalStateException(e);
            }
        });
The barrier uses a 10-second timeout so a mistake fails the test instead of hanging the build. This is the general technique for testing concurrency code: do not hope for the interleaving, build a place in the code where you can choose it. Why did one of the two payments end in a refund rather than two confirmed bookings? confirm checks that the slot’s owner is the confirming booking. The last writer’s id is in the slot, so only that booking passes. A version of confirm that simply wrote BOOKED would have issued two tickets.
Going deeper

Fix one: lock the seat before you look at it

The first cure closes the gap by making the check and the write one indivisible step. Give every seat its own lock; to hold seats, lock all of them, then check, then write, then unlock. While you hold the locks nobody else can look at those seats, so nobody can slip into the gap. This is called pessimistic locking because it assumes a collision is likely and pays for protection up front. Taking the locks is the interesting part, in PessimisticInventory.java:
    /** Locks the cells in the configured order; returns null (holding nothing) if a lock could not be had in time. */
    private List<Cell> lockAll(String showId, List<String> seatIds) throws InterruptedException {
        List<String> ids = new ArrayList<>(seatIds);
        if (order == AcquireOrder.SORTED) {
            Collections.sort(ids);
        }
        List<Cell> locked = new ArrayList<>();
        for (String id : ids) {
            Cell c = cells.get(showId).get(id);
            if (!c.lock.tryLock(lockWait.toMillis(), TimeUnit.MILLISECONDS)) {
                lockTimeouts.incrementAndGet();
                unlockAll(locked);
                return null;
            }
            locked.add(c);
            if (locked.size() == 1) {
                afterFirstLock.run();
            }
        }
        return locked;
    }
Look at the first lines: when the order is SORTED, the seat ids are sorted before any lock is taken. That one line is the difference between a design that works and one that can freeze. With the locks held, the hold itself is straightforward (same file, PessimisticInventory.java):
    public boolean tryHold(String showId, List<String> seatIds, String holdId, Duration ttl) {
        validate(showId, seatIds);
        List<Cell> locked;
        try {
            locked = lockAll(showId, seatIds);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return false;
        }
        if (locked == null) {
            return false;
        }
        try {
            Instant now = clock.instant();
            for (Cell c : locked) {
                if (c.slot.effectiveState(now) != SeatState.AVAILABLE) {
                    return false;                       // nothing was written yet, so there is nothing to undo
                }
            }
            Instant expiresAt = now.plus(ttl);
            for (Cell c : locked) {
                c.slot = c.slot.held(holdId, expiresAt);
            }
            return true;
        } finally {
            unlockAll(locked);
        }
    }
The finally is not decoration: every path out, including “a seat was taken, give up”, must release every lock, or the next request for those seats waits forever. And because the check of all seats finishes before the first write, a refused request has written nothing, so there is nothing to undo. Now the failure that locking introduces. Suppose request H1 asks for [A1, A2] and request H2 asks for [A2, A1] — the same two seats, listed in opposite order. If each takes its locks in the order it was given:
Locks taken in the order requestedLocks taken in sorted orderRequest H1: A1, A2seat A1seat A2Request H2: A2, A1holdswaitsholdswaitsEach holds one lock and waits for the other’s.Neither can ever finish: a cycle.Request H1: A1, A2seat A1seat A2Request H2: A1, A2holdsthenwaits for A1H2 asked for A1 first, so it waits behind H1.Nobody waits on someone who is waiting for them.
The left panel is a deadlock: H1 holds A1 and waits for A2, H2 holds A2 and waits for A1, and neither can proceed. The right panel is the cure: sort the seat ids first, and both requests ask for A1 first, so the second simply waits behind the first and the cycle cannot form. Here is what the test recorded in output/03-lock-ordering.txt (the code is in LockOrderingTest.java):
PessimisticInventory, AS_REQUESTED (each thread holds one lock, then waits for the other's):
  stuck until a lock wait timed out (300 ms): true
  at least one lock wait timed out:           true
  requests that succeeded:                    at most 1 (never both; which one is timing dependent)
  Without the timeout both threads would wait forever.

PessimisticInventory, SORTED (both requests lock A1 first, so one simply waits):
  requests that succeeded:   1 of 2
  lock waits that timed out: 0
A timeout does not solve a deadlock; it picks a victim. To keep the demonstration from hanging, the unsorted variant uses tryLock with a 300 ms timeout. My first version of this test asserted that both requests fail, and it did not hold: when the first timeout fires, that thread gives up its lock, and the other thread, which was waiting for exactly that lock, gets it and succeeds. So the honest assertion is “stuck until a timeout, and never both succeed”, which is what the transcript says. Sorting the locks is the fix; the timeout is only a safety net.
Going deeper: coarser locks, finer locks, and why tryLock A simpler correct design than a lock per seat is one lock per show: every hold on a show takes that single lock, so there is only ever one lock to take and no ordering problem at all. This module does not implement or measure it; the trade-off is that it serializes every booking on that show, including bookings for completely different seats. A lock per seat lets requests for disjoint seats proceed in parallel, at the price of needing the ordering discipline above. The implementation uses ReentrantLock.tryLock(timeout) instead of synchronized because a synchronized block cannot give up after a timeout; with tryLock a stuck request can give up, release what it holds and report failure. Lock ordering is a general rule worth remembering outside this problem: if every code path that takes more than one lock takes them in the same global order, a cycle of waiting threads cannot exist.
Going deeper

Fix two: look first, and change the seat only if nobody else did

The second cure takes the opposite bet: collisions are rare, so do not lock; just notice if one happened. Each seat is an AtomicReference to its immutable SeatSlot. To take a seat you read the slot you see, build the slot you want, and call compareAndSet(whatIRead, whatIWant), which succeeds only if the reference still points at exactly the object you read. If another thread changed the seat in between, your attempt fails and you look again. This is optimistic locking, and it is the in-memory version of UPDATE seat SET ... WHERE version = ? that section 10 runs against a real database. The code is in OptimisticInventory.java:
    public boolean tryHold(String showId, List<String> seatIds, String holdId, Duration ttl) {
        validate(showId, seatIds);
        Instant now = clock.instant();
        Instant expiresAt = now.plus(ttl);
        List<Taken> taken = new ArrayList<>();
        for (String id : ordered(seatIds)) {
            AtomicReference<SeatSlot> ref = refs.get(showId).get(id);
            boolean got = false;
            while (true) {
                SeatSlot seen = ref.get();                                         // LOOK
                if (seen.effectiveState(now) != SeatState.AVAILABLE) {
                    break;                                                         // genuinely taken: give up
                }
                SeatSlot wanted = seen.held(holdId, expiresAt);
                if (ref.compareAndSet(seen, wanted)) {                             // CHANGE, only if unchanged
                    taken.add(new Taken(ref, wanted));
                    got = true;
                    break;
                }
                casRetries.incrementAndGet();                                      // somebody else moved first: look again
            }
            if (!got) {
                beforeRollback.run();
                rollback(taken, SeatSlot::released);
                return false;
            }
            if (taken.size() == 1) {
                afterFirstAcquire.run();
            }
        }
        return true;
    }
Read the inner loop as three beats: look (ref.get()), decide (is it effectively available?), change if unchanged (compareAndSet). If the seat is genuinely taken the loop gives up; if only the compare-and-set lost to a concurrent change, it re-reads and decides again. A multi-seat request takes its seats one at a time. If a later seat turns out to be taken, the seats already taken must be handed back, and rollback does that with compare-and-set too, so it can only undo our own holds:
    private static void rollback(List<Taken> taken, java.util.function.UnaryOperator<SeatSlot> undo) {
        for (Taken t : taken) {
            t.ref().compareAndSet(t.installed(), undo.apply(t.installed()));
        }
    }
That brief “taken, then handed back” window is the price of not locking, and the same ordering question as before decides how much it hurts. Here are the two crossed requests again, now against the optimistic inventory (the second half of output/03-lock-ordering.txt):
OptimisticInventory, AS_REQUESTED (each request takes one seat, then finds the other taken):
  results:                   [false, false]
  A1 / A2 afterwards:        AVAILABLE / AVAILABLE  (versions v2 / v2: held, then handed back)
  Both seats are free and both customers were turned away.

OptimisticInventory, SORTED (both start at A1, so only one can get past the first seat):
  requests that succeeded:   1 of 2
  HELD seats afterwards:     2
With the seats taken in the order requested, each request grabs one seat, finds the other seat held by its rival, and hands its own back. Both are refused although both seats are free, and the versions v2 / v2 are the fingerprint: each seat was held and then released. With the ids sorted, both requests start at A1, only one can get past it, and that one proceeds. Same cure as before, for a different reason.
Optimistic does not mean it cannot turn customers away for nothing. Reproducing the mutual refusal on every run needed two barriers in the test: one after each request takes its first seat, and one after each has seen the other’s seat but before either hands its own back. With only the first barrier the test failed on some runs, because one request had already rolled back by the time the other looked, and the other then succeeded. So in real traffic the unsorted version refuses both customers only sometimes — which is worse to debug than always.
Going deeper: why the slot must be an immutable record AtomicReference.compareAndSet compares references, not values. Because every transition in SeatSlot allocates a new object, an old reference can never equal a newer state even if the seat has returned to “the same” contents, so a stale read cannot be mistaken for a current one. (The same reasoning is why the database version uses a version counter: a counter only goes up, so an old read can never look current.) The inventory also counts how often a compare-and-set lost and the seat was re-read, in casRetries(). That figure depends on thread timing, so it is not printed in any transcript and the article does not quote it. Rollback is also compare-and-set rather than a plain write, so a rollback that arrives late cannot undo a seat that someone else has since taken.
Going deeper

How to test it: assert what must always be true, not who wins

With many threads you cannot assert which customer gets a seat; it changes with the interleaving. What you can assert is what must be true whatever the interleaving. For one contested seat that is simply “exactly one winner”. For many users and many seats it is a short list of invariants: no seat is held by two granted requests, every granted request really owns all its seats, and the seats counted as HELD are exactly the seats of the granted requests. The check, in ContentionTest.java:
            Set<String> seen = new HashSet<>();
            boolean noSeatTwice = true;
            boolean ownsItsSeats = true;
            int grantedSeats = 0;
            for (Request r : granted) {
                for (String s : r.seats()) {
                    noSeatTwice &= seen.add(s);
                    SeatSlot slot = inv.slot(SHOW_ID, s);
                    ownsItsSeats &= slot.state() == SeatState.HELD && slot.holdId().equals(r.holdId());
                    grantedSeats++;
                }
            }
            long held = inv.summary(SHOW_ID).get(SeatState.HELD);
            long available = inv.summary(SHOW_ID).get(SeatState.AVAILABLE);
            assertTrue(noSeatTwice);
            assertTrue(ownsItsSeats);
            assertEquals(grantedSeats, held);
            assertEquals(60 - grantedSeats, available);
            assertTrue(!granted.isEmpty());
The first test fires 200 threads at seat D4 and repeats it 30 times per inventory. The second fires 400 requests of one to three random seats each (a seeded plan, so every inventory faces the same demand) at a 60-seat show. From output/04-contention.txt and output/05-random-seats.txt:
PessimisticInventory: rounds with exactly one winner: 30 of 30
OptimisticInventory:  rounds with exactly one winner: 30 of 30
seats requested in total (seeded, identical for every inventory): 800

PessimisticInventory, SORTED:
  no seat granted to two requests:                 true
  every granted request owns all of its seats:     true
  HELD seats == seats of granted requests:         true
  AVAILABLE + HELD == 60:                          true
The other two variants print the same four true lines in the file. How many requests were granted is deliberately not printed: it differs from run to run, and a number that moves would make the transcript look like a result when it is a coincidence. A decision table for the two designs, using only what the transcripts above showed:
Pessimistic (locks)Optimistic (compare-and-set)
How the second request is stoppedwaits for the first one’s lockits compare-and-set fails
Threads block?yes, on a lockno, they retry or give up
Multi-seat requestlock all, check all, write all: nothing to undo (v0 after a refusal)take one by one, hand back on failure (v2 after a refusal)
Failure when seats are taken in request orderdeadlockboth requests refused although the seats are free
Curesort the seat idssort the seat ids
Same idea in SQLSELECT ... FOR UPDATEUPDATE ... WHERE version = ?
Which is faster?not measured here; it depends on how often requests collide. Measure your own workload with a proper harness (JMH Tutorial)
Going deeper: platform threads, seeded plans and the stampede helper The 200-thread test releases every thread at once through a CountDownLatch so they contend instead of arriving one by one. It uses platform threads on purpose: the first version used virtual threads, and on this 2-vCPU sandbox the naive inventory then passed 30 of 30 rounds, because the virtual threads mostly ran one after another. The helper, in ContentionTest.java:
    private static void stampede(List<Runnable> tasks) throws Exception {
        CountDownLatch go = new CountDownLatch(1);
        try (ExecutorService pool = Executors.newThreadPerTaskExecutor(Thread.ofPlatform().name("stampede-", 0).factory())) {
            List<Future<?>> fs = new ArrayList<>();
            for (Runnable r : tasks) {
                fs.add(pool.submit(() -> {
                    go.await();
                    r.run();
                    return null;
                }));
            }
            go.countDown();
            for (Future<?> f : fs) {
                f.get(60, TimeUnit.SECONDS);
            }
        }
    }
The random plan uses new Random(20261120L), so the 800 requested seats are identical on every run and every inventory. The thread interleaving is not seedable, which is why the assertions are invariants. For the effect of virtual threads on blocking code in general, see Virtual Threads vs WebFlux vs Platform Threads.
Going deeper

A hold is a promise with a deadline, and payment is slower than you think

Now the clock. A hold lasts five minutes, and a payment is not instant: the customer types a card, the bank answers, a one-time password arrives. So the interesting question is what happens when the deadline passes around the payment. The picture first, then the code.
HELD by BK-0001 (Asha)reads AVAILABLEHELD by BK-0002 (Ravi)T+00:00Asha holds B1, B2T+04:59B1 reads HELDpaying now would workT+05:00B1 reads AVAILABLE(slot still says HELD)T+05:01Ravi holds B1T+05:02Asha presses Payno charge is madenot to scaleExpiry is a comparison, not an event: at T+05:00 nothing runs, readers just compare the clock with expiresAt.If the charge starts at T+04:59 and the bank takes two minutes, the deadline passes during the charge.The seat is lost, so the charge is refunded (transcript scenarios 3 and 4).
The timeline is the second scenario of the transcript below. Asha holds B1 and B2 at T+00:00. At T+04:59 B1 still reads HELD, so a payment now would succeed. At T+05:00 it reads AVAILABLE, although the stored slot still says HELD. At T+05:01 Ravi takes B1 and the seat is his. When Asha finally presses Pay at T+05:02, she is told her hold expired and she has not been charged. The method that decides all this is pay, in BookingService.java:
    /** Step 2: charge and confirm. See {@link BookingOutcome} for the five ways this can end. */
    public BookingOutcome pay(String bookingId) {
        Booking b = transition(bookingId, BookingStatus.PENDING_PAYMENT, BookingStatus.PAYMENT_IN_PROGRESS);

        if (!clock.instant().isBefore(b.expiresAt())) {
            inventory.release(b.showId(), b.seatIds(), b.id());
            set(bookingId, BookingStatus.EXPIRED);
            return BookingOutcome.HOLD_EXPIRED_BEFORE_PAYMENT;
        }

        PaymentResult result = payments.charge(b.id(), b.amountRupees());
        if (!result.success()) {
            inventory.release(b.showId(), b.seatIds(), b.id());
            set(bookingId, BookingStatus.PAYMENT_FAILED);
            return BookingOutcome.PAYMENT_DECLINED;
        }

        if (inventory.confirm(b.showId(), b.seatIds(), b.id())) {
            set(bookingId, BookingStatus.CONFIRMED);
            return BookingOutcome.CONFIRMED;
        }

        payments.refund(b.id());
        set(bookingId, BookingStatus.REFUNDED);
        return BookingOutcome.HOLD_LOST_AFTER_PAYMENT;
    }
Read it as four exits. Expired before payment: nothing is charged and the seats are released. Declined: seats released, nothing charged. Confirmed: the happy path. And the awkward one: the customer was charged, but the hold is gone, so the money is refunded. The first line, transition(..., PAYMENT_IN_PROGRESS), is what stops a double-clicked Pay button from charging twice; it gets its own demonstration in section 9. Five scenarios on a fake clock, from output/06-expiry-and-payment.txt (the test is ExpiryAndPaymentTest.java):
1. Pay one second before the deadline
   hold placed T+00:00, expires T+05:00, pay pressed T+04:59
   outcome: CONFIRMED   charges: 1   refunds: 0
2. The deadline passes while Asha is on the payment page (she holds B1 and B2)
   T+04:59  B1 reads as HELD
   T+05:00  B1 reads as AVAILABLE   (stored slot still says HELD: expiry is lazy)
   T+05:01  Ravi asks for B1: BK-0002 PENDING_PAYMENT
   T+05:02  Asha presses Pay: HOLD_EXPIRED_BEFORE_PAYMENT   charges: 0
   B1: HELD    by BK-0002 until T+10:01  v2
   B2: AVAILABLE                          v2
3. Pay pressed at T+04:59, the gateway takes two minutes, nobody else wants the seat
   outcome: HOLD_LOST_AFTER_PAYMENT   charges: 1   refunds: [BK-0001]   booking: REFUNDED
4. Same slow payment, but Ravi takes B4 while the gateway is still working on Asha's charge
   outcome: HOLD_LOST_AFTER_PAYMENT   charges: 1   refunds: [BK-0001]   booking: REFUNDED
   B4: HELD    by BK-0002 until T+11:59  v2
5. The card is declined
   outcome: PAYMENT_DECLINED   booking: PAYMENT_FAILED   B5 now: AVAILABLE
Scenarios 3 and 4 are the ones that cost real money. In scenario 3 the payment starts at T+04:59, the fake gateway takes two minutes, and the hold lapses while the bank is thinking: the customer is charged and then refunded, even though nobody else wanted the seat. In scenario 4 Ravi takes the seat during that window, and the refund is now unavoidable. Scenario 2 also shows a subtle safety property: when Asha’s late payment releases her seats, B1 stays with Ravi (BK-0002) and only B2, which was still hers, goes back to AVAILABLE.
The policy here is strict, and that is a choice. Once the deadline has passed the hold is gone, even if nobody else took the seat. That is the simplest rule to reason about and to test. A friendlier product would extend the hold while a payment is in flight, so a slow bank does not cost the customer their seat; the cost is a more complicated state (a hold that can be extended once, by whom, up to what limit). This module does not implement that, and the transcript above is what the strict rule does.
Going deeper: extending the hold, refunds and a real clock Extending the hold. The natural design is a second transition, HELD to HELD with a later expiresAt, applied when the payment begins and bounded by the gateway’s own timeout. With the optimistic inventory that is one more compare-and-set on the seat; with the pessimistic one it is one more write under the lock. It is not in this module, so nothing in the transcripts exercises it. Refunds must be safe to repeat. A refund call that times out leaves you not knowing whether it happened, so a real integration sends an idempotency key with each charge and refund; the mechanics are in Idempotency Keys for POST APIs. The fake gateway here just records what it was asked to do. Time itself. Production code would pass Clock.systemUTC(); the tests pass a clock that only moves when told to, so a five-minute hold is verified instantly, in MutableClock.java:
    private final AtomicReference<Instant> now;

    public MutableClock(Instant start) {
        this.now = new AtomicReference<>(start);
    }

    public void advance(Duration d) {
        now.updateAndGet(i -> i.plus(d));
    }

    @Override
    public Instant instant() {
        return now.get();
    }
The three inventories produce an identical log for all five scenarios; the last line of the transcript says so.
Going deeper

The quiet bugs: half-finished holds, foreign releases and a double-clicked Pay

The failures so far announce themselves. These do not, and each one is pinned by a test in PitfallsTest.java, whose transcript is output/07-pitfalls.txt. A request that fails half way must leave nothing behind. Someone else holds A3; a customer asks for A1, A2 and A3. The request must fail, and A1 and A2 must be free for the next person. All three inventories get this right, but not in the same way:
1. Request [A1, A2, A3] while someone else holds A3
   NaiveInventory        result false A1 AVAILABLE v0   A2 AVAILABLE v0
   PessimisticInventory  result false A1 AVAILABLE v0   A2 AVAILABLE v0
   OptimisticInventory   result false A1 AVAILABLE v2   A2 AVAILABLE v2
   (v0 means the seat was never touched; v2 means it was held and handed back during the attempt)
The pessimistic version checked everything before writing, so it never touched A1 or A2 (v0). The optimistic version really did take A1 and A2 before discovering A3, then handed them back, which is why they are at v2. Same result for the customer; a different history for the seat, and exactly the window that the unsorted optimistic request in section 6 collided in. Pressing Pay many times. Browsers retry, people double-click, mobile networks resend. The booking status moves through PENDING_PAYMENT to PAYMENT_IN_PROGRESS in one atomic step, so only one call may start the payment. In BookingService.java:
    /** Atomically moves a booking from one status to another, or throws if it was not in the expected status. */
    private Booking transition(String bookingId, BookingStatus from, BookingStatus to) {
        while (true) {
            Booking cur = booking(bookingId);
            if (cur.status() != from) {
                throw new IllegalStateException("booking " + bookingId + " is " + cur.status() + ", expected " + from);
            }
            Booking next = cur.withStatus(to);
            if (bookings.replace(bookingId, cur, next)) {
                return next;
            }
        }
    }
bookings.replace(id, cur, next) succeeds only if the booking is still equal to what we read, which is the same look-then-change-if-unchanged idea as section 6, applied to a map entry. The test presses Pay 50 times at once (PitfallsTest.java, transcript output/07-pitfalls.txt):
5. Pay pressed 50 times at once for the same booking
   calls that confirmed:                    1
   calls refused with IllegalStateException: 49
   times the card was charged:               1
Going deeper: foreign releases, booked seats and bad input Three more behaviours, each asserted for all three inventories. Only the owner can release or confirm a hold. If release freed whatever seat id it was given, anyone who could guess a seat number could kick a paying customer out of their hold. A BOOKED seat is not freed by release, even by its owner, so a late cleanup call cannot resell a paid seat. Bad input is refused before any state changes: duplicate seat ids, unknown seats, an empty request, an unknown show. Duplicates are rejected up front rather than handled; I did not investigate what each inventory would do with them, because the module never lets one through. The ownership checks are the two methods from section 2, ownsHold and isHeldBy. The real output, from output/07-pitfalls.txt:
2. Someone who does not own the hold tries to release or confirm it
   NaiveInventory        after Ravi's release and confirm: C1 is HELD by ASHA, Ravi's confirm returned false
   PessimisticInventory  after Ravi's release and confirm: C1 is HELD by ASHA, Ravi's confirm returned false
   OptimisticInventory   after Ravi's release and confirm: C1 is HELD by ASHA, Ravi's confirm returned false

3. A BOOKED seat is not released by release(), even by its owner
   NaiveInventory        C2 after owner's release: BOOKED, a new hold on it returns false
   PessimisticInventory  C2 after owner's release: BOOKED, a new hold on it returns false
   OptimisticInventory   C2 after owner's release: BOOKED, a new hold on it returns false

4. Bad input (identical for all three inventories)
   duplicate seat ids: IllegalArgumentException: duplicate seat id in request: A1
   unknown seat:       IllegalArgumentException: unknown seat Z99 for show SH-1
   no seats at all:    IllegalArgumentException: no seats requested
   unknown show:       IllegalArgumentException: unknown show: SH-404
Going deeper

Taking it to production: the seat state moves out of the JVM

Everything so far lives in one process. The moment you run two copies of the application behind a load balancer — which any real ticketing site does — a ReentrantLock or an AtomicReference in one JVM is invisible to the other, and the double booking is back. The shared truth has to move to something both can see, usually a database row per seat. The good news is that the three ideas carry over almost word for word. JdbcSeatStore.java holds a single seat in an H2 table and implements the same race three ways, plus a naive control. The simplest correct one is a single conditional UPDATE, in which the check is the WHERE clause, so there is no gap between check and act:
    /** Strategy 3, one conditional UPDATE: the "check" is the WHERE clause, so there is no gap between check and act. */
    public boolean holdConditionalUpdate(String showId, String seatId, String holdId, Instant now, Instant expiresAt) throws SQLException {
        try (Connection c = dataSource.getConnection();
             PreparedStatement write = c.prepareStatement("""
                     UPDATE seat SET state = 'HELD', hold_id = ?, expires_at = ?, version = version + 1
                     WHERE show_id = ? AND seat_id = ?
                       AND (state = 'AVAILABLE' OR (state = 'HELD' AND expires_at <= ?))""")) {
            write.setString(1, holdId);
            write.setTimestamp(2, Timestamp.from(expiresAt));
            write.setString(3, showId);
            write.setString(4, seatId);
            write.setTimestamp(5, Timestamp.from(now));
            return write.executeUpdate() == 1;
        }
    }
The other two are the SQL spellings of sections 5 and 6: SELECT ... FOR UPDATE inside a transaction (pessimistic: the row is locked until commit), and a plain SELECT followed by UPDATE ... WHERE version = ? (optimistic: zero rows updated means someone else got there first). The control reads the row and then updates it with no version and no lock. Thirty-two connections are released at once at one seat, twenty times per strategy (from output/08-database-strategies.txt, test in DatabaseSeatTest.java):
optimistic   (SELECT, then UPDATE ... WHERE version = ?):  rounds with exactly one winner: 20 of 20
pessimistic  (SELECT ... FOR UPDATE, then UPDATE):         rounds with exactly one winner: 20 of 20
conditional  (one UPDATE ... WHERE state = 'AVAILABLE'):   rounds with exactly one winner: 20 of 20

Control, not asserted and timing dependent:
naive        (SELECT, then UPDATE with no version or lock):    rounds with exactly one winner: 3 of 20
The three real strategies pick exactly one winner every round. The naive control, which is the same check-then-act as NaiveInventory but in SQL, picked exactly one winner in only 3 of 20 rounds in the committed run (earlier runs printed 4, 2 and 3, so treat it as indicative). Moving to a database does not fix a check-then-act bug; it relocates it.
Going deeper: Redis holds, Postgres lock options and what H2 cannot tell you Holds in Redis. A common alternative for the hold itself is a key per seat set with SET seat:show:C5 <holdId> NX PX 300000: NX means “only if absent” (the check and the write are one command), and PX attaches the five-minute time-to-live so expiry is done by Redis. The Redis documentation describes this pattern, including that the value must be unique per client so that only the owner releases it, in Distributed Locks with Redis and Redis SET command. I did not run Redis for this article, so this is the documented design, not a measured one. Postgres lock options. The Postgres documentation describes NOWAIT (error instead of waiting if a selected row cannot be locked at once) and SKIP LOCKED (rows that cannot be locked at once are skipped), and warns that skipping gives an inconsistent view, so it is meant for queue-like tables (PostgreSQL SELECT (the locking clause)). A customer asked for seat C5 specifically, so in my reading NOWAIT is the closer fit for a seat hold and SKIP LOCKED is for “give me any free seat” features. Again, docs, not executed here. What this section does not prove. The tests run against H2 in memory, so they show the shape of each strategy but say nothing about Postgres or MySQL lock behaviour, isolation-level defaults, or what happens across a network. Treat them as a runnable sketch of the SQL, not a benchmark.
Going deeper

How to present this in an interview

A 35-minute low-level design round rewards order more than volume. A sequence that fits: requirements (hold, expire, confirm, never twice), entities (Show, Seat, SeatSlot, Booking), the seat state machine, the one interface where concurrency lives, then the naive version and its race, then one cure done well and the other named, then expiry and payment timeout, and finally what changes in production. Interviewers rarely need both locking styles implemented; they need you to find the check-then-act gap on your own whiteboard and say why a thread-safe map does not close it.
Going deeper: follow-up questions, with short answers These are discussion answers, not executed results; where the module proves something, the section is named. Why not just make tryHold synchronized? It is correct and it is a fine first answer. It serializes every booking on that inventory, including for different shows, so the follow-up is to narrow the lock (per show, then per seat) and to say what that costs: with per-seat locks you must order them (section 5). What happens if the server restarts during a hold? In this in-memory design every hold vanishes and the seats are free again, which is safe but loses customers mid-payment. A database or Redis hold survives, which is one reason the state moves out of the JVM (section 10). How do you show the seat map without locking it? Reads only look at each seat’s effective state and do not hold anything while the customer studies the map, so the map can be stale by the time they tap. That is fine: the hold is the authority, and a stale tap simply gets “seat unavailable” (section 3). How do you handle a hot release, when thousands ask for the same seats? Both designs serialize correctly on a contested seat (section 7); throughput on a hot show is then a capacity and queueing question (a waiting room, rate limits such as in Rate Limiting Spring Boot APIs with Bucket4j and Redis), which this module does not model. How would you add “best available seats together”? It is a search over the seat map followed by one all-or-nothing tryHold; the all-or-nothing hold is already the building block.
Going deeper
  • Parking Lot System — the same step-by-step low-level design approach for a simpler problem
  • LRU Cache in Java — a data-structure design question with a thread-safe second half

Should you build this yourself?

Mostly, only in an interview. For a real ticketing product, seat inventory is a database problem first: one authoritative store, a single conditional update or a row lock to claim a seat, and a hold with a deadline. The in-JVM inventories in this post are the right thing to write on a whiteboard because they make the reasoning visible, and they are the right thing to unit test the booking rules against. They are the wrong thing to run on two servers. If you are building it for real, also budget for what this module skips: confirmed-booking cancellations, payment webhooks and reconciliation, fairness under heavy demand, and idempotent retries on every external call.

Further reading

No Comments yet!

This site uses Akismet to reduce spam. Learn how your comment data is processed.