Flight Search Platform (Google Flights / Kayak)

0) Problem Restatement

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).

1) Requirements

• 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.

2) Architecture

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 --> GDS

3) Two Separate Problems

• Ingest airline schedules daily (standard SSIM files) into a flight graph: airports are nodes, and flights are edges with departure and arrival times.
• For a query, run a time-aware graph search: from the origin on that date, follow flights where the next departure is after the previous arrival plus the minimum connection time (e.g., ≥ 45 minutes at that airport), up to 2 stops, and limit total travel time.
• Precompute popular routes' possible connections to speed this up.

• Pricing is complex (fare classes, rules, taxes) and live GDS calls are slow and cost money per request.
• Keep a fare cache: price per (flight or itinerary, date, cabin, passenger type) with the time it was fetched. Search results mostly use cached prices, which are "indicative".
• Refresh strategy: popular routes and dates are refreshed often, and rare ones on demand. Scrape or subscribe to airline price feeds where available.

4) Search Flow

1. Check the result cache for the same query (short TTL, minutes).
2. Build candidate itineraries from the schedule graph (direct + 1-stop + 2-stop).
3. Price them from the fare cache. For important candidates with missing or stale prices, call the GDS in parallel with a time budget.
4. Rank: price, total duration, number of stops and departure time preferences. A "best" score combines them.
5. Return the first results fast, then stream in more as live prices arrive (progressive loading).
6. When the user selects an itinerary, verify the price and availability with a live call before booking. If the price changed, tell the user.

5) 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.

6) Wrap-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.