flight-search — tirogla

How it is built

Architecture overview

A flight-search system answers "SFO to BOS on April 2, back April 5" with a ranked list of itineraries, each a set of flights and a price. It is a shortest-path problem only on the surface. The flights form a time-dependent network, but the price is not the sum of per-flight prices: it comes from fares with rules (advance purchase, minimum stay, allowed combinations) that apply to groups of flights, and whether a fare may be used depends on the other flights and fares in the same ticket. Carl de Marcken of ITA Software, whose engine powered travel sites and airline sites, described this in his MIT 6.034 course notes (2003) and presented complexity results showing why the cheapest-fare question is hard.

Two architectures are in use, and many systems mix them. Own-data search loads schedules, fares and rules and searches them in-house; this is the ITA design described in the paper. Metasearch fans a query out to many suppliers (airlines, consolidators, agents) and merges what comes back, trading control for freshness. Both need the same core: build candidate itineraries, price them, rank them, and keep latency low with caches whose entries are known to go stale. The one idea that makes it work: separate the cheap, cacheable part (which flights connect) from the expensive, volatile part (which fares apply and whether seats are available), and spend your effort in the second only for itineraries that survive the first.

Parts:

Inventory and fare data — schedules, fares, rules, availability; from supplier feeds or live calls — Event deduplication, Money representation, calendar-date-arithmetic (no page yet)
Connection builder — which flight sequences are valid and sensible — raptor-transit-routing (no page yet), k-shortest-paths (no page yet), Time-window feasibility, Dijkstra
Fare and rules engine — which fares may pay for which flights — Rete rules engine
Pricing and currency — totals, taxes, display currency — Money representation, currency-cross-rate-triangulation (no page yet), FX conversion and quoting
Ranking — pick and order what to show — Top-k selection, Learning to rank, Gradient-boosted trees
Cache and freshness — answer repeats quickly without lying for long — W-TinyLFU, stale-while-revalidate (no page yet), Cache invalidation, Tiered cache, Consistent hashing
Supplier gateway — calls to external systems under quota and failure — hedged-requests (no page yet), Circuit breaker, Token bucket, Exponential backoff with jitter
Booking hand-off — re-price and confirm — Booking and reservations, Idempotency keys

 query (O, D, dates, pax, filters)
        │
        ▼
   normalise ──► cache (key: O-D-date-pax-cabin ...) ──hit, fresh──► rank ──► response
        │ miss / stale                    ▲
        ▼                                 │ store with TTL, flag stale
   connection builder ──► candidate itineraries (flights only)
        │                       │
        │               prune: min connect time, max duration, routing sanity
        ▼
   fare + rules engine  ◄── fare/rule data   +   availability / live price from suppliers
        │                                         (quota, timeout, circuit breaker, hedge)
        ▼
   priced itineraries ──► currency, taxes ──► rank (score, top-k, diversity) ──► response
        │
        └── later: price check at selection ──► booking

How the parts fit together

Inventory and fare data

de Marcken's notes list three kinds of data the engine runs on, provided electronically by the world's airlines: flight schedules, prices, and seat availability, plus a large share of published data used by all the major engines and some private data restricted to individual parties. As of 2003 he gives their update rates: flight data daily with occasional faster updates for unexpected cancellations, prices about ten times a day, seat availability continuously. The numbers have changed since, but the structure matters: the three kinds change at different speeds, so they are cached and refreshed at different speeds. A schedule is stable enough for hours; a fare for minutes to hours; availability can change between two clicks.

The data contract between the feed and the engine should be an immutable snapshot version per data kind. An engine that mixes yesterday's schedule with this morning's fares must know it, because a fare may refer to flights that no longer exist. Event deduplication keeps repeated feed messages from creating duplicate entries.

Amounts are integer minor units with a currency; dates are calendar dates with time zones: a flight departs on one date and arrives on another, and a fare rule counted in days is evaluated on local dates (calendar-date-arithmetic, no page yet).

Connection builder

For one origin and destination the builder lists sequences of flights that a human would accept. In graph terms: nodes are airport-times, edges are flights, and waiting is allowed if it respects a minimum connection time at that airport. This resembles public-transit journey planning, where RAPTOR (Delling, Pajor, Werneck) computes all Pareto-optimal journeys for arrival time and number of transfers by rounds: round k holds the best arrivals using k trips, so the number of transfers is built into the search rather than added to the cost. The paper's abstract says the algorithm is not Dijkstra-based and looks at each route at most once per round (raptor-transit-routing, no page yet). For air travel the same round structure gives itineraries by number of connections.

Why not plain Dijkstra? Because the aim is not one shortest path but a set of distinct, reasonable ones, and the "cost" is not additive. De Marcken's notes show that the number of flight combinations grows exponentially with trip length, that the number of round-trip combinations is roughly the square of one-way ones, and that Dijkstra-style tricks cannot reduce the exponential number of paths to polynomial. He adds that standard algorithms can produce the k shortest flight paths but that enumerating good paths fast enough for a planner is a considerable challenge. The practical answer is a bounded enumeration: generate the best few thousand per route by duration and connection quality (k-shortest-paths, no page yet; Yen's 1971 algorithm for k loopless shortest paths is the classic reference), prune by minimum connection time and maximum duration, and check time-window constraints incrementally (Time-window feasibility gives the O(1) check for an insertion). Everything before pricing deals only with flights, so its result can be cached per route and date.

Fare and rules engine

This is the core difficulty and the reason the problem is hard. From de Marcken's notes: a fare has rules that restrict its use; a fare component is a fare plus the flights it covers; a priceable unit groups one to four fare components; many fare rules apply to the priceable unit as a whole (a minimum stay, a Saturday-night stay, a restriction that a round-trip fare may not be used one-way). A traveller may choose any combination of fares as long as every rule holds, usually the cheapest. The same flights can be grouped into fare components and priceable units in several ways, and that choice changes how rules are read. The notes show rules that test combinations of two flights far apart in time and on the ticket, and he presents complexity results for the full problem, including that for some rule combinations the general search is undecidable.

A Rete rules engine fits the rule side: thousands of fares each with conditions over the same facts (dates, days of week, booking date, flight numbers, cabin, passenger type), and many candidate itineraries that share most facts. Rete caches the partial matches so evaluating a new itinerary re-does only what differs. It does not solve the combination search itself; that remains an optimisation over fare groupings, and the rules engine is used to validate each candidate grouping. It is also a real system: expect fare data in vendor formats, with a long tail of special cases, which the engine must treat as data, not code.

Contract with its neighbours: input is a candidate itinerary (flights with local dates and times) plus a pricing date; output is zero or more priced options (fare components, base amounts, rule notes, the fare basis to buy) and, for each, the availability it needs.

Pricing and currency

Totals combine base fares, taxes and fees, each in its own currency. Money representation says: integer minor units, one named rounding mode, round once. Showing the price in the traveller's currency needs a rate and a convention for whose rate and when; currency-cross-rate-triangulation (no page yet) is the calculation when two currencies have no direct quote, and FX conversion and quoting covers the system view. A price shown in one currency and charged in another must say which rate applied, or the displayed and charged amounts will disagree.

Ranking

A search can yield thousands of valid priced itineraries; the page shows tens. The score blends price, duration, number of stops, departure time, airline and the risk of a short connection. A plain weighted sum with top-k selection (bounded heap, so you never sort everything) is the baseline. When there is click and booking data, learning to rank with gradient-boosted trees (LambdaMART in Burges's overview) learns what people choose; features are price relative to the cheapest option, extra duration, connection quality, and time of day. Pure price ranking produces many near-identical results from one airline; add diversity: guarantee at least one nonstop, one cheapest, one fastest. This is design reasoning rather than a documented recipe for any particular product.

Cache and freshness

Searches repeat: many people ask the same route and dates. Caching the result for a key (origin, destination, date, passengers, cabin) answers most requests without touching suppliers. Three techniques fit together:

Admission and eviction with W-TinyLFU: a window plus a frequency sketch admits an item only if it beats the victim, which suits skewed query popularity and keeps one-off searches from pushing out popular routes.
Staleness: price entries get a short time to live; after it, stale-while-revalidate (no page yet; the HTTP form is RFC 5861) serves the old value once while refreshing in the background. Which fields may be stale differs: a schedule can be hours old, a price minutes old, availability should be treated as a hint. See Cache invalidation and Tiered cache.
Placement: consistent hashing on the key routes a query to the node that holds its entry, and keeps a node join or loss from emptying the whole cache.

Cached prices are indications. The booking step must re-price (see below).

Supplier gateway

Metasearch fans out to many suppliers and must tolerate slow and failing ones; this is the usual tail-latency problem. A hedged request sends a duplicate to a second replica or route after the typical latency has passed and uses whichever answers first (Dean and Barroso, The Tail at Scale), hedged-requests, no page yet. A circuit breaker stops calling a supplier that fails repeatedly. A token bucket keeps you inside each supplier's quota. Exponential backoff with jitter spaces retries. The response to the user is built at a deadline: whatever has arrived by then, with the slow suppliers' results streamed later or dropped.

Booking hand-off

When the traveller picks an itinerary, the system re-prices it with the supplier and checks availability; only then does the booking system hold and ticket it, with idempotency keys so a retry does not double-book. The difference between the cached and the live price is the most common user-visible failure of this whole stack.

Data and control flow

One search:

The request is normalised (airport codes expanded to city groups, dates validated against time zones) and a cache key is built.
The cache is consulted. A fresh hit goes straight to ranking. A stale hit is served and a refresh queued. A miss continues.
The connection builder produces candidate flight sequences from the schedule snapshot. This is cacheable per route and date and is cheap relative to pricing.
The fare and rules engine prices the candidates in order of promise until a budget of candidates or time is spent; for metasearch, the supplier gateway runs in parallel with a deadline.
Currency and tax are applied; results are scored; the top k are chosen with diversity; the response and the cache entry are written.
Time goes mostly to pricing (rule evaluation and supplier calls), not to graph search.

One refresh: a background job re-runs the search for popular keys whose entries are about to expire, weighted by how often they are asked; it uses the same engine at lower priority and respects supplier quotas.

One booking: re-price with the selected itinerary and the live supplier; if the amount changed, show it and ask; if availability is gone, return alternatives.

Scaling

Pricing cost: the number of candidates times the fare combinations. Levers: prune candidates earlier (connection quality, duration), cache priced itineraries per route and date, limit combinations per query and rank the promising first.
Cache hit rate: the cheapest way to scale; route popularity is skewed. Levers: W-TinyLFU admission, longer TTLs for schedule-only results, background refresh for the head of the distribution.
Supplier latency and quota in a metasearch: hedging, deadlines, per-supplier budgets, circuit breakers, and priority between interactive and refresh traffic.
Fan-out for flexible dates: "cheapest in the next month" is thirty or more searches. Lever: precomputed per-route calendars from cached results, clearly marked as indications.
Data refresh: fares change many times a day (de Marcken, 2003 figure); loading must not stall searching. Lever: build the new snapshot beside the old one and switch atomically.

Failure modes

Failure	Symptom	Cause	Fix
Price changed at checkout	the price rises after the user selects	cache returned a stale indication; fare sold out	re-price at selection, show cache age, shorter TTL on volatile routes
Rule misapplied	a fare shown that cannot actually be ticketed	rule interpretation error, wrong priceable-unit grouping, stale rule data	test against supplier answers; keep rule data versioned with the snapshot
Impossible connection	itinerary with too short a transfer	minimum connection time missing or wrong for that airport or terminal change	data check, conservative default, flag risky connections
Date errors	arrival "before" departure, or off-by-one day on a fare rule	time zones and local dates mixed	store local time plus zone, convert once, use calendar arithmetic that knows zones
Slow tail	some searches take many seconds	one slow supplier holds the response	deadlines, hedged requests, return partial results
Retry storm	suppliers throttle or ban	retries without backoff, no quota control	token bucket, backoff with jitter, circuit breaker
Rounding mismatch	total differs by a cent between screens	rounding at each step or mixed rounding modes	integer minor units, round once
Cache stampede	many identical misses at once on a hot key	expiry of a popular entry	stale-while-revalidate, request coalescing

Real implementations

name	what it is	repo	licence	notes
ITA Software search engine	own-data flight search; powered travel sites, airlines and reservation systems	—	—	documented in de Marcken's course notes (2003); not open
OpenTripPlanner	open-source multi-modal trip planner for scheduled public transport (GTFS)	opentripplanner/OpenTripPlanner	LGPL-3.0-or-later	closest open relative of the connection builder; the repository contains a `raptor` module; not a flight engine
IATA NDC	airline distribution standard for offers and orders	—	—	see the IATA programme page; defines how retailers get offers from airlines

No open-source flight-shopping engine with fare-rule evaluation was found for this page; public documentation of production flight search is mostly the ITA paper and academic work on related routing problems.

Sources

C. de Marcken, Computational Complexity of Air Travel Planning, annotated slides, ITA Software, notes for MIT 6.034, 2003. PDF (mirror)
D. Delling, T. Pajor, R. F. Werneck, Round-Based Public Transit Routing (RAPTOR). ALENEX paper and publication page
J. Y. Yen, Finding the K Shortest Loopless Paths in a Network, Management Science 1971, DOI 10.1287/mnsc.17.11.712 (confirmed via Crossref).
C. L. Forgy, Rete: A fast algorithm for the many pattern/many object pattern match problem, Artificial Intelligence 1982, DOI 10.1016/0004-3702(82)90020-0 (confirmed via Crossref).
J. Dean and L. A. Barroso, The Tail at Scale, Communications of the ACM 2013. Google Research page
G. Einziger, R. Friedman, B. Manes, TinyLFU: A Highly Efficient Cache Admission Policy. arXiv:1512.00727
C. J. C. Burges, From RankNet to LambdaRank to LambdaMART: An Overview, Microsoft Research. publication page
M. Nottingham, HTTP Cache-Control Extensions for Stale Content, RFC 5861. RFC
IATA, NDC programme page.
OpenTripPlanner: documentation and repository.