Problem RestatementProblem
Meta asked: design a flight search platform. A user searches for flights from one city to another on given dates (one-way or round-trip), with filters (stops, airlines, times), and sees results sorted by price, duration or a "best" score. Results include connecting itineraries (e.g., BLR → DXB → LHR). Flight schedules change slowly, but prices and seat availability change constantly and are expensive to query from airlines and GDS systems (global distribution systems like Amadeus/Sabre, which sell airline inventory).
RequirementsRequirements
- Search by origin, destination, dates, passengers and cabin.
- Return direct and connecting itineraries with prices, sorted and filtered.
- Latency: a first set of results in ~1–2 seconds.
- Prices must be verified before booking.
- Handle huge query volume (much of it browsing) without huge fare-query costs.
ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
U["Users"] --> API["Search API"]
API --> QC[("Search result cache")]
API --> IB["Itinerary builder - graph search"]
SCH[("Schedule graph - flights, times")] --> IB
IB --> PR["Pricing layer"]
PR --> FC[("Fare cache - with age")]
PR -->|"cache miss / stale"| GDS["GDS / airline APIs"]
ING["Schedule ingestion - daily"] --> SCH
U -->|"select itinerary"| VER["Price verification - live check"]
VER --> GDSDeep Dive — Two problems wearing one search boxProblem
"Flights from Delhi to Lisbon on 12 March" hides two very different questions: which journeys are possible, and what each one costs right now. Treating them as one is what makes flight search slow.
Price every possible itinerary live
Enumerate itineraries and call the pricing system for each.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["DEL to LIS, 12 March"] --> EN["Enumerate itineraries - thousands with 1-2 stops"]
EN --> PR["Price each one live"]
PR --> SLOW["Thousands of calls to a slow, rate-limited pricing system"]
SLOW --> TO["Search takes tens of seconds or times out"]
PR --> COST["Most priced itineraries are never shown"]Pricing is the expensive, rate-limited, slowly-responding part, and this design calls it for results nobody will look at. It also couples a question that changes daily — which flights exist — to one that changes by the minute.
Cache the prices
Keep recently returned prices and serve them from cache.
Latency improves and a new failure appears: fares change constantly, so a cached price is often wrong by the time it is displayed. The user selects a $612 fare and is told at checkout that it costs $740 — the single most damaging experience a travel site can produce, and it gets worse the more aggressively you cache.
Separate the slow-changing graph from the fast-changing prices
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SSIM["Airline schedules - ingested daily"] --> G[("Flight graph - airports as nodes, flights as edges")]
Q["Query"] --> SEARCH["Time-aware graph search"]
G --> SEARCH
SEARCH --> MCT["Respect minimum connection time, max stops, max duration"]
MCT --> SHORT["Shortlist - tens of itineraries"]
SHORT --> PRICE["Price only the shortlist - live, in parallel"]
PRICE --> RES["Results with fares"]
RES --> SEL["User selects"]
SEL --> REPRICE["Re-price that itinerary before checkout - authoritative"]- Schedules are a graph problem. Airports are nodes and flights are edges with times; a query is a time-aware search where each next departure must follow the previous arrival plus the airport's minimum connection time. This runs on data ingested once a day and needs no external calls.
- Price only what will be shown. Constraining to a few tens of candidates first turns thousands of pricing calls into a manageable parallel fan-out with a deadline.
- Re-price at selection. The displayed fare is an estimate with a timestamp; the authoritative price is fetched when the user picks an itinerary, before payment. That makes cached prices safe, because nothing is ever charged from the cache.
Pre-compute connections for popular routes so the graph search is a lookup for the queries that make up most of the traffic. The long tail runs the full search and is rare enough to afford it.
Search FlowFlows
- Check the result cache for the same query (short TTL, minutes).
- Build candidate itineraries from the schedule graph (direct + 1-stop + 2-stop).
- Price them from the fare cache. For important candidates with missing or stale prices, call the GDS in parallel with a time budget.
- Rank: price, total duration, number of stops and departure time preferences. A "best" score combines them.
- Return the first results fast, then stream in more as live prices arrive (progressive loading).
- When the user selects an itinerary, verify the price and availability with a live call before booking. If the price changed, tell the user.
Scaling and Cost
- Look-to-book ratio is huge (thousands of searches per booking), so caching is the main cost control.
- Rate limits and budgets per GDS, and prioritize live queries for high-intent searches.
- Shard the search service by region, and scale out for seasonal peaks.
- Precompute "cheapest per date" calendars for popular routes (the price calendar view) from the fare cache.
Wrap-UpWrap-up
Separate schedules from prices. Build itineraries with a time-aware graph search over a daily-ingested flight graph (respecting connection times and stop limits), and price them mostly from a fare cache with fetch timestamps, refreshing popular routes proactively and calling GDS/airline APIs live only for important stale results within a time budget. Rank and stream results, cache whole searches briefly, and always verify price and availability live before booking.