Notes
Requirements
Fix the scope. Flights run on a weekly schedule, each with an aircraft whose seat map has business and economy cabins. Travellers search by origin, destination, date and cabin, hold seats for fifteen minutes while paying, and get a six character booking reference, the PNR. Fares depend on the fare type and on demand. Bookings can be cancelled under refund rules, travellers check in for a boarding pass, and the airline may overbook within a limit.
Ask the questions that change the code. Must every traveller pick a seat? No: those who skip get one at check-in, which is what makes overbooking possible. When is the price fixed? At hold time. When does check-in open and close? Twenty-four hours before departure until forty-five minutes before. How much overbooking? Whatever the policy says, for example twenty percent extra in economy. And for now, one flight leg per booking.
- flights run on a weekly schedule
- aircraft seat map: business,
- economy
- search by from, to, date, cabin
- hold seats while paying: 15 min
- confirm: a 6 char PNR
- fare by fare type and demand
- cancel with refund rules
- check in, get a boarding pass
- overbooking: a configurable limit
- out of scope: crew, baggage
- must every traveller pick a seat?
- no: free seat at check-in
- price fixed when?
- quoted at hold time
- check-in window?
- 24h to 45 min before departure
- overbooking how much?
- a policy, e.g. 20% of economy
- one leg or many?
- one leg; multi-leg is an
- extension
Entities
The most important split in this design: a flight is not a departure. Flight A R one zero one, Bangalore to Delhi at nine every day, is a schedule. The plane leaving on the twentieth of December is a flight instance. Seats, holds, bookings and sold counts belong to the instance, because seat two A can be free on Sunday and sold on Monday. The schedule and the seat map never change, so they are shared by every instance.
Class diagram
Turn them into types. Cabin and fare type are enums. A seat, a seat map and a flight schedule are records, because they never change. The flight instance is the one class with changing state: which seat is owned by which hold or booking, the active holds, and how many tickets are sold per cabin. Departure time is computed in the origin airport's time zone. Money is a long number of paise.
enum Cabin { BUSINESS, ECONOMY }
enum FareType { SAVER, FLEX }
record Seat(String code, Cabin cabin)
record Flight(number, from, to, departs,
zone, Set<DayOfWeek> days, SeatMap,
Map<Cabin, Long> baseFareCents)
class FlightInstance {
Map<String,String> seatOwner;
Map<String,Hold> holds;
Map<Cabin,Integer> sold;
} Flow: search
Search walks the schedule. A flight matches if the route is right and it operates on that day of the week, so the Monday, Wednesday, Friday flight is skipped on a Sunday. The dated instance is created on first use with compute if absent, so two searches never create two copies. For each match we count what is left to sell and quote both a saver and a flex fare. Like any search, it is only a hint; hold checks again.
for (Flight f : schedule)
if route matches and
f.days contains date.dayOfWeek
fi = instances.computeIfAbsent(..)
synchronized (fi) {
left = sellLimit - sold - held
if (left >= n) offer(saver, flex)
}
sorted by departure time Holds
Paying takes a few minutes, so seats are held first. A hold remembers its seats, its quoted total and an expiry fifteen minutes away. There is no timer per hold. Instead, every operation on a flight instance first drops the holds whose time has passed and frees their seats, under the same lock. A traveller who wanders off simply stops counting the moment anyone looks. The clock is injected, so the demo moves time without sleeping.
// called under the instance lock
for (Hold h : holds.values())
if (!now.isBefore(h.expiresAt)) {
remove h
free every seat h owned
}
taken(cabin) = sold + travellers
in the holds that are left Flow: hold
Walk the hold. Lock the flight instance and drop expired holds. Check capacity against the overbooking policy's sell limit, not the physical seats. Then check every requested seat: it must exist, be in the right cabin, and have no owner. Only if every check passes do we price the hold and mark the seats as owned by it. All or nothing, so a family of two never ends up with one seat held and one lost.
synchronized (fi) {
fi.dropExpired(now);
if (taken + pax > sellLimit)
throw: sold out
for each seat: in cabin? owned?
throw: seat 1A is taken
total = price(..) * pax
for each seat: owner = holdId
fi.holds.put(hold)
} Concurrency
Now the race. Eight travellers tap seat one A on the same departure at the same moment. If checking and claiming were separate steps, two threads could both see the seat free and both claim it. So both happen inside one lock on the flight instance. The first thread claims the seat; the others wait a moment, see the owner and fail with seat taken. The lock is per departure, so tomorrow's flight and every other route never wait.
- bad: is 1A free? then claim
- two threads both see free
- good: check and claim inside
- synchronized (flightInstance)
- the second thread waits, then
- sees the owner and fails
- one lock per departure:
- other flights never wait
Flow: confirm
Once payment succeeds, confirm. Removing the hold from the map first means a hold can be confirmed only once, even if the payment callback arrives twice. Under the instance lock, drop expired holds; if ours is gone, the traveller took too long and must search again. Otherwise generate a PNR, hand the seats from the hold to the booking, and add the travellers to the sold count for their cabin.
Hold h = holds.remove(holdId);
if (h == null) throw: unknown or used
synchronized (fi) {
fi.dropExpired(now);
if (fi.holds.remove(id) == null)
throw: expired, search again
pnr = pnrs.next();
seat owners: holdId to pnr
sold[cabin] += pax
} PNR generation
A PNR is six characters a traveller reads over the phone, so the alphabet drops I, O, zero and one, which leaves thirty-two symbols, exactly five bits each. Six of them give thirty bits. We take an atomic counter and scramble it: multiply by an odd number and add a constant, modulo two to the thirtieth. With an odd multiplier that mapping is one to one, so codes never repeat, yet consecutive bookings look unrelated. No retry loop on collisions is needed.
ALPHABET: 32 symbols, no I O 0 1 6 symbols x 5 bits = 30 bits long x = seq.incrementAndGet() * 0x2545F491L + 0x9E3779B1L; x &= (1L << 30) - 1; // odd multiplier mod 2^30: // a one to one mapping take 5 bits at a time into ALPHABET.charAt(..)
Strategy: pricing
Pricing is a strategy, because revenue teams change it constantly. Ours reads a small query: the flight, cabin, fare type, how full the cabin is, and days to departure. Under half full the economy fare is the base five thousand rupees, up to eighty percent full it is thirty percent higher, and beyond that seventy percent higher. Inside a week it rises again, and flex costs thirty percent more than saver. The fare is computed under the instance lock, so the load it reads is exact.
interface PricingStrategy {
long fareCents(PriceQuery q);
}
demand: load under 50% x1.0,
under 80% x1.3, else x1.7
last minute (under 7 days) x1.25
FLEX x1.3
economy base 5,000: load 33%: 5,000
load 83%: 8,500, FLEX empty: 6,500 Overbooking
Some travellers never show up, so airlines sell a few more seats than the plane has. That is a business decision, so it is a policy: an interface that returns the sell limit for a cabin. No overbooking returns the seat count. Percent overbooking adds, say, twenty percent to economy, so six seats can sell seven tickets. Selling more is easy; the bill comes at check-in, when the last traveller without a seat may find none left.
interface OverbookingPolicy {
int sellLimit(Cabin c, int seats);
}
NoOverbooking: seats
PercentOverbooking(ECONOMY, 20):
6 + 6 * 20 / 100 = 7
seat chosen at booking: owned now
no seat chosen: assigned at
check-in, if one is left Strategy: refunds
Cancellation depends on the fare type, so each type maps to a refund policy. Saver refunds the total minus a fee of two thousand five hundred per traveller if you cancel seventy-two hours or more before departure, and nothing after that. Flex refunds everything until the plane leaves. Cancel runs under the instance lock: it computes the refund, frees the booking's seats, lowers the sold count and marks the booking cancelled, so it can only happen once.
interface RefundPolicy {
long refundCents(Booking b,
Instant now);
}
Saver: 72h or more before departure:
total - 2,500 per traveller
later: nothing
Flex: everything until departure
cancel releases seats and
sold count under the lock Flow: check-in
Check-in opens twenty-four hours before departure and closes forty-five minutes before. Under the instance lock, a traveller who chose a seat keeps it; anyone else gets the first free seat in their cabin. The boarding pass carries the seat, a boarding group, business first and then the back rows of economy, and a sequence number from a counter on the instance. Checking in twice is rejected.
window: 24h to 45 min before
synchronized (fi) {
if (t.seat == null)
t.seat = first seat in cabin
with no owner
if still null: denied boarding
t.checkedIn = true
return new BoardingPass(..,
group, ++boardingSeq)
} Denied boarding
Here is overbooking coming due. Seven economy tickets were sold for six seats, and everyone shows up. The first six travellers get seats. The seventh finds none free, so check-in records them on the denied boarding list and the agent offers the next flight plus compensation. Notice that travellers who chose a seat at booking were never at risk, because their seat was owned from the start.
Concurrency
Check every shared field. Everything that changes for one departure, the seat owners, holds, sold counts, booking status and check-in state, is guarded by that instance's lock. Instances are created once with compute if absent. A hold is removed from the map before confirming, so it is used once. The PNR counter is atomic, and schedules and seat maps are immutable records. Each call takes at most one lock, so deadlock cannot happen.
- per departure, one lock:
- seat owners, holds, sold,
- booking status, check-in
- instances: computeIfAbsent
- holds by id: remove() once
- PNR counter: AtomicLong
- schedules, seat maps: records
- one lock at a time: no deadlock
- pricing reads load under lock
At scale
With many servers, the lock moves into the database. Each seat of each departure is a row with an owner and a hold expiry, and claiming it is a conditional update that only succeeds if the owner is empty or the hold has expired. The sold count is a conditional update too: add the travellers only if the result stays within the sell limit. Search, which is most of the traffic, reads from caches and replicas, because hold re-checks anyway.
- seat_inventory(instance, seat,
- owner, hold_expires_at)
- unique (instance, seat)
- sold count: UPDATE .. SET sold =
- sold + n WHERE sold + n <= limit
- one row update = the lock
- holds: expires_at column
- PNR: unique index, scrambled seq
- search: cached, read replicas
Extensibility
Now the stretches. A multi-leg trip, Bangalore to Delhi to London, is an itinerary of legs that must all succeed: hold each leg, take instance locks in a fixed id order to avoid deadlock, and release every hold if one fails. Loyalty miles are an observer that hears when a booking is flown and credits miles by distance. Exit row fees are another pricing rule, and a sold-out waitlist reuses the cancel path.
- multi-leg itinerary: hold every
- leg, lock instances in id order,
- release all if one fails
- loyalty miles: Observer on
- booking flown, miles by distance
- seat fees: PricingStrategy per
- seat type (exit row, window)
- waitlist when sold out
- schedule change: rebook flow
Testing
The full code is below the player. The demo searches on a Sunday and gets only the daily flight. A hold expires after sixteen fake minutes and its late confirm is rejected. Eight threads race for seat one A and exactly one wins. Economy fares climb as the cabin fills, the eighth ticket is refused, the two refund rules pay out differently, and at check-in six travellers get boarding passes while the seventh is denied boarding.
search: AR101 only on a Sunday H1 held, 16 minutes pass: confirm H1: expired race for seat 1A: 1 held, 7 refused economy 33% load: saver 5,000.00 83% load: saver 8,500.00 8th economy ticket: sold out saver cancel 119h before: 17,000 flex cancel 47h before: all back check-in: 6 passes, 1 denied
Follow-ups
Expect follow-ups. Why one lock per departure and not per seat? A booking claims several seats and a sold count together, and they all live in one departure. What if payment succeeds after the hold expired? Try to hold again, and refund automatically if the seats are gone. How is the overbooking percent chosen? From no-show history per route. And which patterns did you use? Strategy for pricing, overbooking and refunds.
- why lock per departure?
- seats only clash within one
- payment after hold expiry?
- try to re-hold, else refund
- fare changed while paying?
- quoted price is kept
- how to pick overbooking %?
- no-show history per route
- which patterns? Strategy x3,
- Observer for miles
Say it like this
Here is the short version to say out loud. A flight is a schedule; a flight instance is that flight on one date, and it owns the seats, holds and sold counts under one lock. Holds expire lazily against an injected clock. Confirm turns a hold into a booking with a scrambled, unique PNR. Pricing, overbooking and refunds are strategies, and travellers without a chosen seat get one at check-in.
- "A Flight is a schedule; a
- FlightInstance is one date and
- owns seats, holds and sold
- counts under one lock. Holds
- expire lazily. Confirm makes a
- PNR. Pricing, overbooking and
- refunds are strategies; seats
- without a choice are given at
- check-in."