Design an airline reservation system

01The design, in the six-step framework

1. Requirements and use cases

An airline reservation system is a large domain; the interview version is the booking core: a flight instance with a seat map, fares that differ by cabin and by how early you book, itineraries of several legs, and cancellations that behave according to the fare bought.

• A passenger searches flights between two airports on a date and sees fares per cabin.
• A passenger books an itinerary of one or more flight legs; the booking is confirmed only if every leg has a seat in the requested cabin.
• A passenger selects a seat on each leg from the seat map, or is assigned one at check-in.
• A passenger cancels; the refund depends on the fare class (refundable, partial, none).
• Operations schedules a flight (a route on a day with an aircraft) and can cancel a flight, which cancels every booking on it.

Out of scope: pricing optimisation, baggage, crew, loyalty. Constraints: the multi-leg booking is all-or-nothing; the fare rule for a booking is the one at purchase time, so it is snapshotted; cabin inventory per flight is counted, seats are assigned later, exactly like room types versus rooms.

2. Core entities and relationships

• Airport, Route: static reference data (route = origin, destination).
• Aircraft: a model with a seat layout grouped by Cabin.
• Flight: a route on a date with an aircraft; owns a CabinInventory per cabin and a seat map.
• Fare: cabin, price and a CancellationPolicy; fares are published per flight.
• Itinerary: an ordered list of Segments (flight, cabin, fare snapshot, seat).
• Booking: passenger, itinerary, status enum; the unit of payment and cancellation.
• ReservationSystem: the facade that searches, books, cancels and reacts to flight cancellation.

A booking composes its segments. A segment keeps a reference to the fare it was bought under (a hollow diamond, because the fare object is shared and immutable), which is how the refund rule survives later fare changes.

3. Interfaces and key methods

from dataclasses import dataclass
from enum import Enum, auto
from typing import Optional, Protocol

class Cabin(Enum):
    ECONOMY = auto()
    BUSINESS = auto()

class CancellationPolicy(Protocol):
    def refund(self, price: int, hours_before: int) -> int:
        """Amount returned if cancelled hours_before departure."""

@dataclass(frozen=True)
class Fare:
    cabin: Cabin
    price: int
    policy: CancellationPolicy

@dataclass(frozen=True)
class LegRequest:
    flight_id: str
    cabin: Cabin

class Flight:
    def hold(self, cabin: Cabin) -> bool:
        """Decrement cabin inventory if any left; atomic per flight."""
    def release(self, cabin: Cabin) -> None: ...
    def assign_seat(self, seat: str, booking_id: str, cabin: Cabin) -> None:
        """Seat must be free and in the cabin."""

class ReservationSystem:
    def book(self, passenger: str, legs: list, now: int) -> "Booking":
        """All-or-nothing across legs: holds in order, releases on the first failure."""
    def check_in(self, booking_id: str) -> None:
        """CONFIRMED to CHECKED_IN; any leg without a seat gets the next free one in its cabin."""
    def cancel(self, booking_id: str, now: int) -> int:
        """Returns the refund; releases inventory and seats on every segment."""
    def cancel_flight(self, flight_id: str, now: int) -> list:
        """Cancels every booking touching the flight with a full refund; returns them."""

Invariants: for each flight and cabin, holds never exceed the aircraft's seat count for that cabin; a segment's fare is the published fare at booking time and never changes; a seat belongs to at most one booking; a booking is either fully held on all legs or not created.

4. Design patterns and the choices behind them

Cancellation rules as strategies on the fare

The force: refundable, partially refundable and non-refundable fares, plus "free until 24 hours before". A CancellationPolicy object per fare, asked for the refund with the hours remaining, is the strategy pattern; the booking code calls one method and never branches on fare names. A rejected alternative is a fare_type string with an if chain in cancel, which is where the fourth rule would break something.

Counted inventory now, seats later

Holding a cabin count at booking and assigning a seat later mirrors how airlines sell. It also makes the multi-leg all-or-nothing simple: holds are integers that can be released; seats are a separate step. This is the same split the hotel design makes between types and rooms, and it comes straight from walking the use cases: "book" and "select seat" are different verbs.

Statuses with legal transitions, multiplicities made explicit

BookingStatus moves confirmed, to checked-in or cancelled, and the system enforces it (state). The diagram's multiplicities, one booking to many segments, one flight to many bookings through segments, are part of the answer, which is what the relationships notation is for: an interviewer who sees "Flight composes Booking" will ask what happens to a two-leg booking when one flight is cancelled.

5. Core flow and code

1. book walks the requested legs in order; for each it calls Flight.hold(cabin).
2. If any hold fails, every hold already taken is released and the booking is not created.
3. Otherwise a Segment is built per leg with the fare snapshot, and a Booking in CONFIRMED is stored.
4. select_seat asks the flight to assign a free seat in the segment's cabin, gives back any seat the leg had, and records the new one on the segment; check_in gives each leg still without a seat the next free one.
5. cancel computes the refund per segment through its fare's policy, releases seats and cabin counts, and marks the booking cancelled.

import itertools, threading
from dataclasses import dataclass, field
from typing import Optional

class BookingStatus(Enum):
    CONFIRMED = auto()
    CHECKED_IN = auto()
    CANCELLED = auto()

class Refundable:
    def refund(self, price: int, hours_before: int) -> int:
        return price
class PartialRefund:
    def refund(self, price: int, hours_before: int) -> int:
        return price if hours_before >= 24 else price // 2
class NonRefundable:
    def refund(self, price: int, hours_before: int) -> int:
        return 0

@dataclass
class Segment:
    flight_id: str
    cabin: Cabin
    fare: Fare
    seat: Optional[str] = None

@dataclass
class Booking:
    id: str
    passenger: str
    segments: list
    status: BookingStatus = BookingStatus.CONFIRMED

class Flight:
    def __init__(self, id: str, origin: str, dest: str, departs_at: int, layout: dict, fares: dict):
        self.id, self.origin, self.dest, self.departs_at = id, origin, dest, departs_at
        self.layout = layout                      # Cabin -> list of seat ids
        self.inventory = {c: len(seats) for c, seats in layout.items()}
        self.seats = {s: None for seats in layout.values() for s in seats}   # seat -> booking id
        self.fares = fares                        # Cabin -> Fare
        self.cancelled = False
        self._lock = threading.Lock()

    def hold(self, cabin: Cabin) -> bool:
        with self._lock:
            if self.inventory[cabin] == 0:
                return False
            self.inventory[cabin] -= 1
            return True

    def release(self, cabin: Cabin) -> None:
        with self._lock:
            self.inventory[cabin] = min(self.inventory[cabin] + 1, len(self.layout[cabin]))

    def assign_seat(self, seat: str, booking_id: str, cabin: Cabin) -> None:
        with self._lock:
            if seat not in self.layout[cabin] or self.seats[seat] is not None:
                raise ValueError(f"seat {seat} not available in {cabin.name}")
            self.seats[seat] = booking_id

    def assign_any(self, booking_id: str, cabin: Cabin) -> str:
        with self._lock:                          # a held count guarantees a free seat in the cabin
            seat = next(s for s in self.layout[cabin] if self.seats[s] is None)
            self.seats[seat] = booking_id
            return seat

    def free_seat(self, seat: Optional[str]) -> None:
        if seat:
            with self._lock:
                self.seats[seat] = None

class ReservationSystem:
    def __init__(self, flights: list):
        self.flights = {f.id: f for f in flights}
        self.bookings: dict = {}
        self._ids = itertools.count(1)
        self._lock = threading.Lock()             # a booking changes status once

    def search(self, origin: str, dest: str, day_start: int, day_end: int) -> list:
        return [f for f in self.flights.values()
                if f.origin == origin and f.dest == dest and day_start <= f.departs_at < day_end
                and not f.cancelled and any(n > 0 for n in f.inventory.values())]

    def book(self, passenger: str, legs: list, now: int) -> Booking:
        if not legs:
            raise ValueError("an itinerary needs at least one leg")
        held = []
        try:
            for leg in legs:
                flight = self.flights[leg.flight_id]
                if flight.cancelled or flight.departs_at <= now or not flight.hold(leg.cabin):
                    raise ValueError(f"no {leg.cabin.name} seat on {leg.flight_id}")
                held.append((flight, leg.cabin))
            segments = [Segment(f.id, c, f.fares[c]) for f, c in held]
        except Exception:                         # all-or-nothing: whatever failed, undo what we took
            for f, c in held:
                f.release(c)
            raise
        booking = Booking(f"PNR{next(self._ids)}", passenger, segments)
        self.bookings[booking.id] = booking
        return booking

    def select_seat(self, booking_id: str, leg_index: int, seat: str) -> None:
        b = self.bookings[booking_id]
        if b.status is not BookingStatus.CONFIRMED:
            raise ValueError(f"booking is {b.status.name}")
        seg = b.segments[leg_index]
        flight = self.flights[seg.flight_id]
        flight.assign_seat(seat, booking_id, seg.cabin)
        flight.free_seat(seg.seat)                # a change of seat gives the old one back
        seg.seat = seat

    def check_in(self, booking_id: str) -> None:
        b = self.bookings[booking_id]
        with self._lock:
            if b.status is not BookingStatus.CONFIRMED:
                raise ValueError(f"booking is {b.status.name}")
            b.status = BookingStatus.CHECKED_IN
        for seg in b.segments:
            if seg.seat is None:
                seg.seat = self.flights[seg.flight_id].assign_any(booking_id, seg.cabin)

    def cancel(self, booking_id: str, now: int, full_refund: bool = False) -> int:
        b = self.bookings[booking_id]
        with self._lock:
            if b.status is BookingStatus.CANCELLED:
                return 0
            if b.status is BookingStatus.CHECKED_IN and not full_refund:
                raise ValueError("a checked-in booking cannot be cancelled")
            b.status = BookingStatus.CANCELLED
        refund = 0
        for seg in b.segments:
            flight = self.flights[seg.flight_id]
            hours_before = max(0, (flight.departs_at - now) // 3600)
            refund += seg.fare.price if full_refund else seg.fare.policy.refund(seg.fare.price, hours_before)
            flight.free_seat(seg.seat)
            flight.release(seg.cabin)
        return refund

    def cancel_flight(self, flight_id: str, now: int) -> list:
        self.flights[flight_id].cancelled = True
        affected = [b for b in self.bookings.values()
                    if b.status is not BookingStatus.CANCELLED and any(s.flight_id == flight_id for s in b.segments)]
        for b in affected:
            self.cancel(b.id, now, full_refund=True)
        return affected

Two details carry the credibility of the answer: holds are taken in leg order and rolled back in the same order on failure, so a two-leg booking never leaves a phantom seat held on leg one; and cancel_flight marks the flight cancelled, so it can no longer be searched or booked, then reuses cancel with a full-refund flag rather than duplicating the release logic. A passenger cannot cancel after check-in; the airline still can.

6. Extensions, concurrency and what interviewers probe

• "Hold then confirm, with a payment step." Insert a HELD status with an expiry, exactly as in movie ticket booking; the inventory calls already exist.
• "Fare changes after booking." The segment keeps the Fare object it was bought under; publishing a new fare replaces the flight's dictionary entry and old bookings are untouched.
• "Overbooking by cabin." Cap in hold becomes seats * factor; seat assignment at check-in handles the overflow with a bump list.
• Concurrency: per-flight locks around inventory and seat maps; a two-leg booking takes locks one flight at a time and never holds two at once, which is the deadlock-avoidance point worth saying. A booking's status flips under one system lock, so two cancels refund once.
• Test first: second leg sold out releases the first leg; refund is zero for a non-refundable fare and full when the airline cancels; a seat cannot be assigned twice.
• Common mistake: assigning seats at booking time and then being unable to express a multi-leg itinerary cleanly, or letting Flight own Booking objects so a booking appears in two flights' lists and is cancelled twice.

02Where this question was reported

• Educative · Grokking LLD chapter 25
• DesignGurus · DesignGurus case study
• dev.to · Educative top-10: scheduling, reservations, itineraries
• Codemia · Codemia Medium
• GitHub · awesome-low-level-design, Medium
• LLD Canvas · Hold-then-confirm two-step booking