Google Maps: routing, live traffic, navigation and follow-ups

Google Maps: scope, scale and map tiles scoped the problem and solved the part that is straightforward. This lesson is the rest: the routing engine, the live-traffic ETA that feeds back into it, navigation as a half-hour session, and the follow-ups interviewers ask in order.

The routing engine is the deep dive, and the first half of the one new idea this section owns: routing algorithms that survive continental scale, and live traffic feeding back into them.

The routing engine

The model

The road network is a weighted directed graph. Intersections are nodes; road segments are directed edges. The weight on an edge is travel time, not distance — a 2 km motorway segment is a cheaper edge than a 500 m congested side street, and getting this right is what makes routes sensible.

One-way streets are single directed edges. Turn restrictions ("no left turn here") are not expressible as edge weights at all, and are usually handled either by expanding intersections into several nodes or by carrying turn tables alongside the graph. Mention this — it is the detail that shows familiarity.

Dijkstra, and exactly how badly it fails

Dijkstra's algorithm settles nodes in increasing order of distance from the source. It is correct and it explores in every direction at once, like a circle spreading from the origin.

That is the problem. For a 1,000 km route, the circle of "everywhere reachable in the time it takes to reach the destination" covers an enormous area, and every node in it is settled.

A continental road graph: on the order of 10⁸ nodes

A long route settles a large fraction of them: call it 10⁷ to 10⁸ node settles

At an optimistic 10⁶ to 10⁷ settles per second: seconds to tens of seconds per query

Against a 500 ms budget at 2,000 queries per second, that is roughly four orders of magnitude too slow, and it needs the whole graph in memory per query. This is the failure that no ordinary engineering repairs: caching does not help, because the set of possible routes is effectively infinite; sharding does not help, because a route crosses shards.

A*: the first real improvement

A* is Dijkstra plus a heuristic: an estimate of the remaining distance from each node to the destination, used to prefer nodes that head the right way. For road routing the natural heuristic is straight-line distance divided by the maximum plausible speed, which never overestimates and so never breaks correctness.

The search changes shape from a circle into an ellipse pointed at the destination. That is a genuine improvement — often several-fold on long routes — and it is not enough. Several times faster than ten seconds is still seconds.

Bidirectional search (running from both ends and meeting in the middle) helps again, roughly squaring down the explored area. Still not milliseconds.

Contraction hierarchies: preprocessing buys the orders of magnitude

The insight is that most long journeys use the same important roads. A route from one city to another leaves on a main road, uses a motorway, and arrives on a main road — the residential streets matter only at the two ends.

Contraction hierarchies encode that. Order all nodes by importance, then remove them one at a time from least important upward. Whenever removing a node would break a shortest path through it, add a shortcut edge summarising the removed path. The result is the original graph plus a layer of shortcuts, with every node ranked.

A query then searches from the source and the destination simultaneously, only ever moving to more important nodes. The searches meet somewhere in the important core. On continental graphs this reduces a query to a few hundred or few thousand node settles — around a millisecond, which comfortably meets the budget.

The cost is preprocessing: hours over a planet-scale graph, producing an index that depends on the edge weights.

The problem live traffic creates

Contraction hierarchies precompute shortcuts from the weights. Change the weights and the shortcuts may no longer summarise shortest paths. With traffic updating every few minutes, an hours-long preprocessing step is unusable.

This is the genuine tension in the design: the technique that makes routing fast assumes the thing that traffic makes false.

Customizable route planning is the published answer to it. Partition the graph into cells of bounded size. For each cell, precompute an overlay: the shortest paths between that cell's boundary nodes, using only edges inside the cell. A query then runs over boundary nodes and overlays rather than the full graph.

The structural part — the partition — depends only on topology, so it is computed once and never recomputed. Only the overlay weights depend on the metric, and recomputing them for changed cells is fast because each cell is small and cells are independent, so the work parallelises. A traffic update therefore refreshes overlays in seconds to minutes rather than triggering hours of preprocessing. The approach is described publicly in the customizable route planning literature from Microsoft Research (Delling, Goldberg, Pajor, and Werneck); the description here is in my own words and the papers are worth reading directly.

What production systems actually do

Honestly: the details are proprietary and not fully published. What is publicly described across the field is the combination — hierarchical or partitioned graphs, precomputed overlays or shortcuts that are refreshed as traffic changes, multi-level partitions so that long routes touch few cells, and separate metrics for different travel modes and preferences (fastest, shortest, avoid tolls), each of which needs its own weights and therefore its own overlay set.

The interview answer and the production answer differ here in one respect worth naming: in an interview, "Dijkstra, then A*, then contraction hierarchies, then customizable route planning because traffic changes the weights" is a complete and strong answer. In production, the same progression is buried under years of data engineering about the map itself — turn restrictions, road closures, addressing, and map quality — which is where most of the real work goes.

ETA and live traffic

Routing finds the path. The ETA is the number the user actually cares about, and producing it is the second half of the section's new idea: feeding a live measurement stream back into the graph the router runs on.

The ingest pipeline

Devices running navigation report position fixes. Requirements and scale sized that at 900,000 positions per second, batched into around 60,000 uploads per second.

1. Anonymise and strip. Remove identifiers at the edge of the pipeline, before storage. What is needed downstream is "a vehicle traversed this segment at this speed at this time", not who.
2. Map match. A raw position is a coordinate with error; the pipeline needs a road segment. Map matching, in the navigation section below, covers how.
3. Derive segment speeds. Consecutive matched fixes give a distance and a time, and therefore a speed for a specific segment.
4. Aggregate. Per segment, per time bucket of a few minutes, compute a robust average — a median or trimmed mean, because a single vehicle stopped for coffee should not close a motorway.
5. Publish. Write the aggregated speeds to a store the routing tier reads, and emit them as a stream so overlays can be refreshed incrementally.

This is a stream-aggregation pipeline of exactly the shape Section 23 (Design an Ad Click Event Aggregation) builds in detail, with one difference: exact correctness is not required here. An ETA that is 8% wrong is a normal ETA; a billing figure that is 8% wrong is a lawsuit.

The coverage problem

Traffic data is abundant where there is traffic and absent where there is not. A motorway segment may have thousands of observations in a five-minute bucket; a rural lane may have none for hours.

The standard answer is a fallback ladder, most specific first:

1. Live speed, if enough observations exist in the recent bucket.
2. Historical speed for this segment at this time of day and day of week — Tuesday 08:30 looks like last Tuesday 08:30.
3. Free-flow speed for the road category and posted limit.

Blend rather than switch abruptly: a segment with three observations should be a weighted mix of live and historical, not a hard jump. Abrupt switching produces visible ETA jitter, which users notice and distrust.

Time-dependent routing, the idea most candidates miss

A route two hours long cannot be costed with current traffic. The traveller will reach a segment 120 km away in ninety minutes, and the relevant question is what that segment looks like then — which for a rush-hour approach into a city is completely different from now.

So edge weights are functions of arrival time at that edge, not constants. The search carries the accumulated time so far and evaluates each edge's weight at that predicted moment, using historical patterns for the future and live data for the near term.

This is why an ETA system needs a prediction layer, not only a measurement layer, and it is the point at which machine learning enters the design.

The learned layer

Predicting travel time from segment speeds is a regression problem with strong structure: segments are connected, congestion propagates along them, and conditions correlate across a road network. Graph-structured models are a natural fit, and their use for arrival-time prediction in a production mapping product has been described publicly by Google DeepMind and the Google Maps team — the description here is in my own words, and the published work is worth reading for the details.

Features that matter: recent and historical segment speeds, road category, time of day and day of week, weather, known events, and the composition of the route. Machine Learning System Design Interview covers how such a system is designed, trained, and served; the point here is architectural. The model consumes the same aggregated stream the router uses and produces a corrected ETA on top of the graph's own estimate, which keeps routing and prediction decoupled — the router remains correct without the model, and the model improves the number the user sees.

Navigation as a session

Routing is a request. Navigation is a stateful conversation lasting half an hour, and it has its own failure modes.

What the session holds

When a user starts navigating, the server (or the client, if offline) holds: the chosen route as an ordered list of segments, the user's current position along it, the remaining ETA, and the turn-by-turn instruction sequence. The client caches the route and the tiles along it, so a connectivity gap does not stop navigation.

That last point is a design requirement, not a nicety. Tunnels, rural roads, and border crossings all interrupt connectivity, and a navigation app that stops working in a tunnel is a navigation app that is not trusted.

Map matching

A position fix is not a location on a road. Consumer GPS is accurate to roughly 5 metres with a clear sky and degrades badly in cities, where signals reflect off buildings — errors of tens of metres in an urban canyon are ordinary. At that error, a raw fix can land on the wrong side of a divided road, on a parallel street, or on a building.

Map matching snaps a sequence of noisy fixes onto a plausible path through the road network. The standard formulation is a hidden Markov model: each candidate road segment near a fix is a possible hidden state, the probability of a fix given a segment falls with distance, and the probability of moving between two segments falls when the road distance between them is implausible given the elapsed time. The Viterbi algorithm then finds the most likely sequence of segments.

The important property is that matching uses the sequence, not each point alone. A single fix 30 m off is ambiguous; ten consecutive fixes tracing a line down one street are not. This is why map matching runs over a window of fixes rather than pointwise, and why it improves as a journey progresses.

Rerouting

The user misses a turn. Detecting this is easy and reacting well is not.

The naive rule — "not on the route, so reroute" — fires constantly on GPS noise, on parallel service roads, and in tunnels, and each false reroute produces a wrong spoken instruction. That is worse than a brief silence.

The reliable rule combines three conditions: the matched position is off-route by more than a distance threshold, it has been off-route for several consecutive fixes, and the deviation is consistent with an actual road rather than noise. Only then compute a new route from the current position to the unchanged destination.

Rerouting is also cheap relative to the original request, because the remaining distance is shorter and the destination is unchanged. It is the same query on a smaller problem.

The adaptive update interval

Position reporting is the dominant battery cost of navigation, and the required frequency varies enormously:

The rule is that update frequency should track how soon the next decision point arrives, not the clock. A client that knows the route knows the distance to the next manoeuvre and can set its own interval accordingly — which is a good argument for keeping route state on the client rather than only on the server.

Aggregating over a session, adaptive intervals can cut position reports substantially against a fixed 1 Hz baseline, which reduces both battery drain and the 900,000-positions-per-second ingest from Requirements and scale.

Follow-ups

Five extensions, in the order they are usually asked.

Offline map packs

A downloadable region contains three things: vector tiles for a zoom range, the routing graph restricted to that region, and a place index for search. The sizing in Requirements and scale suggests a metropolitan area is in the low hundreds of megabytes and a country is several gigabytes — order-of-magnitude figures, dependent on the zoom range and level of detail included.

Three consequences worth naming:

• The routing engine must run on the device, which is a real constraint on the algorithm. A precomputed structure that fits in a pack and answers queries with modest memory is required.
• Traffic is unavailable offline, so ETAs use free-flow or bundled historical speeds and should be presented as such.
• Packs go stale. Roads change, so packs need versioning, expiry warnings, and incremental updates rather than a full re-download.

Multi-modal and transit routing

Public transport is not a shortest-path problem on a weighted graph, and this is the most interesting thing to say about it. A bus edge is not always available — it exists at 08:14 and at 08:44 and not in between — so the cost of an edge depends on when you arrive at it, and waiting is part of the journey.

Timetable-based algorithms handle this natively by working in rounds over trips and transfers rather than by relaxing edges; the RAPTOR family of algorithms (published by Delling, Pajor, and Werneck) is the well-known public example, and the sketch here is in my own words. Multi-modal journeys — walk, train, walk — compose several of these with the walking graph, and the objective usually becomes multi-criteria (fastest, fewest transfers, least walking), which means returning a set of non-dominated options rather than one answer.

Incident reporting

Users report crashes, road closures, and speed traps. The engineering problem is trust: a single report is weak evidence and acting on it lets one person close a road.

The usual approach is a confirmation threshold — several independent reports in the same place within a short window — weighted by reporter history, and cross-checked against observed speed data, since a real closure shows up as vehicles stopping. Reports expire on a timer unless reconfirmed.

Privacy in aggregated traffic data

Traffic aggregates are built from individual journeys, and journeys are sensitive. Three controls matter:

• Strip identifiers early, at ingest, so the pipeline never carries them.
• Never publish an aggregate below a minimum contributor count. A segment speed derived from one vehicle is that vehicle's speed, and on a quiet road it identifies a person.
• Add calibrated noise where formal guarantees are required. Differential privacy techniques give a quantifiable bound on what an aggregate reveals about any individual contributor, at a measurable cost in accuracy.

Legal requirements for location data differ substantially by jurisdiction and are changing, so treat the engineering controls above as necessary and have any specific compliance claim reviewed by someone with current regional expertise.

Continental-scale graph partitioning

The routing engine above relied on partitioning without saying how. The goal is cells of bounded size with as few boundary nodes as possible, because overlay cost scales with the square of a cell's boundary size. Graph partitioning tools optimise exactly this, and geography helps: rivers, coastlines, mountain ranges, and sparse rural regions are natural low-cut boundaries.

Partitions are hierarchical — cells grouped into larger cells, several levels deep — so a long route uses coarse cells in the middle and fine cells near the endpoints. That is the same importance-based idea as contraction hierarchies, expressed as geography rather than as node ranking.