CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 5 min read

The code

Hold, confirm and release.

The seat map checks every requested seat first, and only then takes them all, inside one synchronized method:

class SeatMap {
    private final Map<Seat, Status> taken = new HashMap<>();
    private final Map<Seat, String> holder = new HashMap<>();
    final Set<Seat> all = new TreeSet<>(Comparator.comparing(Seat::row).thenComparing(Seat::num));

    synchronized void hold(String holdId, Set<Seat> seats) throws SeatTaken {
        for (Seat s : seats) {
            if (!all.contains(s)) throw new IllegalArgumentException("no seat " + s);
            if (taken.containsKey(s)) throw new SeatTaken(s + " is taken");
        }
        for (Seat s : seats) { taken.put(s, Status.HELD); holder.put(s, holdId); }
    }
    synchronized void confirm(String holdId, Set<Seat> seats) {
        for (Seat s : seats) taken.put(s, Status.CONFIRMED);
    }
    synchronized void release(String holdId, Set<Seat> seats) {
        for (Seat s : seats)
            if (holdId.equals(holder.get(s)) && taken.get(s) == Status.HELD) { taken.remove(s); holder.remove(s); }
    }
}

The two loops in hold are the whole trick. The first loop only looks, so a failure on the last seat leaves nothing changed. The second loop only writes. Both run under one lock, so nobody can sneak in between them. release checks the holder id, so an old expired hold cannot free seats that now belong to someone else.

The cinema ties the steps together:

Hold hold(String showId, Set<Seat> seats) throws SeatTaken {
    if (seats.isEmpty()) throw new IllegalArgumentException("pick at least one seat");
    String id = nextId("H");
    maps.get(showId).hold(id, seats);
    Hold h = new Hold(id, showId, Set.copyOf(seats), clock.now().plusMinutes(holdMinutes));
    holds.put(id, h);
    return h;
}

Booking confirm(String holdId) throws HoldExpired {
    Hold h = holds.remove(holdId);                     // atomic: only one confirm can take it
    if (h == null) throw new HoldExpired("unknown hold");
    if (clock.now().isAfter(h.expires())) {
        maps.get(h.showId()).release(h.id(), h.seats());
        throw new HoldExpired("hold expired");
    }
    double total = 0;
    for (Seat s : h.seats()) total += rule.price(shows.get(h.showId()), s);
    maps.get(h.showId()).confirm(h.id(), h.seats());
    Booking b = new Booking(nextId("B"), h.showId(), h.seats(), total);
    bookings.put(b.id(), b);
    return b;
}

holds.remove on a concurrent map returns the hold to exactly one caller, so two clicks on "Pay" cannot both confirm. A sweep removes expired holds in the background, so seats come back even if the buyer never returns:

void sweepExpired() {
    for (Hold h : new ArrayList<>(holds.values()))
        if (clock.now().isAfter(h.expires()) && holds.remove(h.id(), h))
            maps.get(h.showId()).release(h.id(), h.seats());
}

The sweep runs on a timer, for example once a minute. Between sweeps a seat of an expired hold is still marked held, so the sweep interval is the longest delay before a seat is back on sale. Say this in a round. A stricter design would also treat an expired hold as free inside hold.

A run on a show with 3 rows of 4 seats (12 seats), flat price 10, and an extra 5 for rows C and later. Hold time is 10 minutes.

Step Result
Hold A1 and A2 Held, 10 seats free
A second buyer asks for A2 and A3 Refused with "A2 is taken". A3 is not taken either, and 10 seats are still free
Confirm the first hold Booking with total 20
Hold C1 and C2, move the clock 11 minutes, confirm "hold expired". The seats are free again, so 10 are free
Hold B1, move 11 minutes, run the sweep B1 is back on sale, 10 free
Hold and confirm C3, C4 and B2 Total 15 + 15 + 10 = 40
A seat that does not exist, such as Z9 Refused: "no seat Z9"

A race test: 100 tasks on 16 threads all try to hold A1 and A2 on the same show at once. Exactly 1 wins, and 98 seats of the 100 in that show stay free. Without the lock, several could win.

Check yourself: 1. Why does hold use two loops? 2. Why does release compare the holder id? 3. What does holds.remove guarantee in confirm?