A maps product does three things that feel like one to the person holding the phone. It draws the world at any zoom level, it computes a route with an arrival time, and it talks you through that route turn by turn while traffic shifts under you. Interviewers like this question because no single clever trick carries it; the tile system is a storage and delivery problem, routing is an algorithms problem with a hard latency budget, and traffic is a streaming aggregation problem, and a strong answer keeps the three pillars separate while showing where they connect. It is also a question that rewards saying plainly what you will not build, because the full product is decades of work, and pretending otherwise spends the interview on geography instead of design.
The walkthrough below scopes the problem, sizes the pillars, and then digs into each in turn, covering tiles and the zoom pyramid, routing on a continental road graph, and the traffic pipeline that keeps ETAs believable.
Scope and requirements
In scope are map display on phones and browsers, routing between two points with a predicted ETA for driving, turn-by-turn navigation that follows the user and reroutes when they deviate or when traffic changes, and the ingestion of live traffic signals. Out of scope, and worth stating in the first two minutes, are geocoding, which is the conversion of typed addresses into coordinates, place search and business listings, Street View imagery, and transit or cycling modes; each is its own large system, and the interviewer almost always agrees to park them. The three pillars that remain are still plenty, and they conveniently exercise three different kinds of engineering, which is the real reason the question endures.
Non-functionally, map display should feel instant, which in practice means tiles arrive from a nearby edge server in tens of milliseconds and the client caches aggressively. Route computation should return in well under a second even across a continent, ETAs should reflect live traffic, and navigation must keep working through flaky cellular coverage, which pushes intelligence toward the client. Accuracy matters in a specific and asymmetric sense, because the map can lag reality by days for a new road without anyone suffering, while a closed road that keeps being recommended sends drivers into a barricade, so closures must stop being recommended within minutes.
Sizing the problem
Assume 1 billion monthly users producing 200 million sessions a day, each loading on the order of 50 tiles after client caching. Multiplying gives 10 billion tile requests per day, and dividing by 86,400 seconds yields about 116,000 per second on average with several hundred thousand at peak. That sounds alarming until you notice tiles are static files, so a CDN, a network of edge caches that serves content from locations near users, absorbs nearly all of it and the origin sees a trickle of cache misses. With a hit rate above 99 percent, which immutable popular files easily achieve, the origin's share of those hundreds of thousands of requests drops to a few thousand per second, a load an ordinary storage tier shrugs at.
The tile count itself is the famous number. The map is a pyramid of zoom levels where level 0 is one tile covering the world and each level quadruples the count, so level z has 4 to the power z tiles and zoom 20 alone has 4 to the 20th, about 1.1 trillion. At even 15 KB per rendered image tile, materializing all of zoom 20 would cost around 16 PB, and summing the levels adds another third on top, since each level above contributes a quarter of the one below it and the geometric series converges to four thirds of the deepest level. That arithmetic is why nobody renders everything. Most of those tiles are open ocean or empty desert, so dense areas are precomputed, sparse ones are rendered on demand and cached, and vector tiles shrink the problem further.
Routing traffic is comparatively small, since 100 million route requests a day works out to about 1,200 per second, peaking a few times higher, and each request is CPU work rather than storage work. Traffic ingestion is the big stream. With 20 million clients navigating concurrently, each recording its position every second and uploading a batch every 30 seconds, the pipeline receives about 667,000 uploads per second carrying 20 million position points per second in aggregate, and that stream runs all day in every region the product serves. At roughly 30 bytes per packed point, the raw feed is around 600 MB per second before protocol overhead, which is the scale that pushes the pipeline toward a partitioned log rather than anything resembling a database write path.
The API
Three interfaces cover the pillars, namely a tile fetch keyed by zoom and grid coordinates, a route request, and a position stream for active navigation sessions. Keeping them separate mirrors the architecture, because each path scales and fails on its own terms.
GET /v1/tiles/{z}/{x}/{y}.pbf → 200 (vector tile, CDN cached)
POST /v1/routes
{ "origin": { "lat": 37.7749, "lng": -122.4194 },
"destination": { "lat": 34.0522, "lng": -118.2437 },
"mode": "drive" }
→ 200 { "polyline": "a~l~Fjk~uOwHJy@P...",
"distance_m": 614000, "eta_s": 20580,
"steps": [ { "instruction": "Merge onto US-101 S", ... } ] }
POST /v1/navigation/{session_id}/position
{ "points": [ { "lat": ..., "lng": ..., "ts": ... }, ... ] }
→ 200 { "reroute": null } (or a fresh route when off course or traffic shifts)
The data model
The road network is a graph in the standard sense, where intersections become nodes and the road segments between them become edges carrying length, speed limit, geometry for drawing, and turn restrictions, and the whole structure is partitioned geographically so each shard owns a region. Live speeds sit in a separate, constantly rewritten table keyed by segment and time window, kept apart from the static graph because the two change on wildly different clocks, with the graph rebuilt over days while speeds churn every minute.
CREATE TABLE graph_nodes (
node_id BIGINT PRIMARY KEY,
lat DOUBLE PRECISION NOT NULL,
lng DOUBLE PRECISION NOT NULL
);
CREATE TABLE graph_edges (
edge_id BIGINT PRIMARY KEY,
from_node BIGINT NOT NULL,
to_node BIGINT NOT NULL,
length_m REAL NOT NULL,
speed_kph REAL NOT NULL, -- free-flow speed
road_class SMALLINT NOT NULL, -- 0 highway ... 4 local
geometry BYTEA -- packed polyline for rendering
);
CREATE TABLE live_segment_speed (
edge_id BIGINT NOT NULL,
window_start TIMESTAMPTZ NOT NULL,
speed_kph REAL NOT NULL,
sample_count INT NOT NULL,
PRIMARY KEY (edge_id, window_start)
);
The high-level architecture
Three mostly independent paths serve the three pillars, and the independence is deliberate, since an outage in traffic aggregation should never stop a map from drawing. Tiles flow from a build pipeline into origin storage and out through the CDN. Route requests hit a routing service that queries a geographically partitioned road graph annotated with live weights. Position probes from clients stream into an ingestion tier, get aggregated into per-segment speeds, and feed those weights back to the graph, while map data edits flow through validated builds on the slowest loop of all.
Tiles, routing, and traffic run as three loosely coupled paths; probes flow up from clients, become per-segment speeds, and feed the same graph the routing service queries. The dashed path is the validated map data build.
Map tiles and the zoom pyramid
A tile is a small square piece of the map, conventionally 256 pixels on a side, addressed by zoom level and an x, y position in that level's grid, so the client computes exactly which handful of tiles covers the viewport and fetches them by URL with no server-side query at all. The pyramid math from the sizing section drives every decision here. Because zoom 20 alone implies a trillion tiles, the pipeline prerenders tiles only where people actually look, which correlates tightly with population, renders the rest lazily on first request, and caches everything at the CDN and on the device, where the client keeps recently viewed areas so panning back is free and a subway commute does not blank the screen. The latency budget explains why the CDN is not optional. A pan gesture wants fresh tiles within a frame or two, and only an edge server tens of milliseconds away can meet that, while a round trip to an origin data center on another continent would make the map visibly smear in behind the user's finger.
The raster versus vector distinction is worth defining plainly. A raster tile is a finished picture, an image rendered on the server, which is simple for clients but heavy on the wire and frozen in one style, so supporting a dark mode means rendering and storing the entire pyramid a second time. A vector tile instead ships the underlying geometry, the road centerlines, polygons, and labels in a compact binary encoding, and the client's GPU renders them with a style sheet. Vector tiles are typically several times smaller, restyle instantly between day and night modes, rotate and tilt without re-fetching, and label in the local language from one set of files, which is why modern clients use them, while raster remains the fallback for simple embeds and old devices that lack the rendering muscle. Either way the delivery story is identical, resting on immutable files with long cache lifetimes, version-stamped URLs so a new map build invalidates cleanly, and a CDN doing the real serving.
Routing on a continental graph
The road graph for a continent has hundreds of millions of edges, and the latency budget is a few hundred milliseconds, so the algorithm choice is the heart of this pillar. Dijkstra's algorithm, the textbook method that grows a frontier outward from the origin, always expanding the unvisited node with the smallest known cost until it reaches the destination, is correct but explores in every direction, so a cross-country query can settle tens of millions of nodes, which takes seconds of CPU per request, and at thousands of requests per second that means thousands of cores doing nothing but routing. Bidirectional search, which runs one frontier from the origin and one backward from the destination until they meet, roughly halves the explored area, and A* with landmarks adds a learned sense of direction by precomputing distances to a few dozen reference nodes and using them to steer the search toward the goal, but both still touch far too many nodes at continental scale, and both lose to precomputation for the same underlying reason, which is that they rediscover the highway network from scratch on every single query.
The production answer is precomputation, and contraction hierarchies are the canonical version. The intuition mirrors how people actually drive, since nobody considers every side street in Nebraska when planning San Francisco to Los Angeles; they get onto a highway and stay there. Preprocessing orders nodes by importance and removes them one at a time, and whenever removing a node would break a shortest path through it, the algorithm inserts a shortcut edge that directly connects the node's neighbors with the same total cost, so the finished structure layers shortcuts over the original graph with the most important roads at the top. A query then runs two searches that only ever climb upward in importance, one from each end, and they meet near the top of the hierarchy after touching a few hundred to a few thousand nodes instead of millions, answering in about a millisecond, which leaves the few-hundred-millisecond budget almost entirely to the network and to assembling the turn-by-turn response. The price is paid in preprocessing, which costs hours of compute over the whole graph, and the shortcuts bake in the edge weights, so a naive contraction hierarchy cannot absorb live traffic. The practical fix is the family of partition-based variants in which the expensive structural phase is separated from a cheap customization phase that re-applies fresh weights in minutes, letting traffic update the metric continuously while the topology work is reused.
A query from the blue origin climbs through arterials to the highway level (1), crosses on a few precomputed shortcut edges (2), and descends to the blue target (3), touching thousands of nodes instead of millions.
Traffic, ETA, and navigation sessions
Live traffic comes from the users themselves, because phones running navigation contribute anonymized GPS probes, sampled positions stripped of identity and chopped into short unlinked segments so no one can reconstruct a person's trip from the pipeline. Raw GPS is noisy, drifting tens of meters in cities, so the first processing stage is map matching, the inference of which road segment a sequence of noisy points actually traveled, and a point that appears to float in a river gets snapped onto the bridge above it. After matching, the aggregator computes the average observed speed per segment per short window, on the order of one to five minutes, keeping sample counts alongside the averages so that one slow driver looking for parking does not declare a jam. With 20 million concurrent contributors, busy segments get hundreds of samples per window while rural segments get none, which is fine because rural free-flow speeds barely vary. The alternative source of truth would be fixed road sensors, and crowdsourced probes beat them decisively, since sensors cost money per intersection, cover only the roads someone paid to instrument, and fail silently, while probes scale with usage and concentrate exactly where the traffic question matters most.
ETA prediction blends two signals. Live speeds describe the road now, but a 6-hour drive cares about conditions when you arrive at each segment, so the predictor combines current observations with historical profiles per segment, per time of day, and per day of week, trusting live data for the next stretch and sliding toward history for the far end of the route. A concrete case makes the blend visible, because a driver leaving Los Angeles at 2 pm will hit the Bay Bridge around 8 pm, and the right weight for that bridge is its typical 8 pm Tuesday speed rather than the jam someone is sitting in right now, which will have dissolved hours before this driver arrives. The same blended weights flow into the routing layer's customization phase, so fresh route requests avoid the jam, and they also drive rerouting of active sessions, since the server knows each navigator's remaining corridor and can push a better route when the predicted saving clears a threshold, with hysteresis preventing the route from flapping between two near-equal options and barking contradictory instructions at the driver.
A navigation session itself is a thin loop. The client streams batched positions, snaps itself to the route locally so the arrow moves smoothly between updates, and detects deviation, meaning the matched position leaves the route corridor, either locally or on the server, which triggers a reroute from the current position. The reroute itself is just another contraction hierarchy query from the new origin, so a missed exit costs the driver a moment of recalculating and then a fresh instruction, usually before the next intersection arrives. Before departing, the client downloads the corridor, the route's geometry, instructions, and a band of surrounding map data, so a dead zone in the mountains costs only live traffic updates rather than navigation itself. Map data changes ride a separate, slower loop, in which edits, new roads, and imported closures flow through a build pipeline with validation that compares connectivity and routing outcomes against the previous build before anything reaches production, while emergency closures take a fast path that simply marks edges impassable in the live weight layer, which the next customization pass folds in within minutes.
Scaling, failures, and operations
Each pillar scales on its own axis. Tiles scale almost entirely at the CDN, where adding edge capacity is routine, and the origin plus render-on-demand tier scales with cache miss rate rather than user count; a CDN regional outage degrades to a farther edge with higher latency rather than failure, so the user sees a slightly slower pan rather than a gray grid. The routing tier scales by replicating graph shards, since queries are read-only against structures rebuilt out of band, and regional sharding means the European replicas never feel an American rush hour; cross-region routes stitch at boundary nodes or run on a coarser global overlay graph. The traffic pipeline scales like any high-volume stream, partitioned by region through a log such as Kafka, and its failure mode is gracefully invisible, because if aggregation lags or dies the system falls back to historical speeds, so ETAs get blander rather than wrong by the minute, which is the kind of degraded mode worth designing on purpose. A driver mid-trip during such an outage sees an ETA that stops reacting to a building jam, which is mildly worse advice rather than a broken product, and most users never learn anything happened.
The sharpest operational risk is a poisoned graph build, a data update that passes validation yet breaks routing somewhere subtle, perhaps by disconnecting a neighborhood behind a mis-imported one-way flag. That risk is why builds roll out region by region with automatic comparison of sampled routes against the previous build, and why rollback to the prior graph version stays one command away. The metrics that matter are tile latency from the edge, route computation latency percentiles, ETA error measured against actual arrivals, probe pipeline lag, and reroute rates, where a sudden spike in reroutes often means a data problem rather than a traffic event, because thousands of drivers do not simultaneously leave their routes unless the routes themselves moved underneath them.
Follow-up questions
- Why precompute tiles at all instead of rendering on demand? Hot areas are requested millions of times, so rendering once and caching forever is vastly cheaper, while cold areas flip the argument and get rendered lazily on first request. The pyramid arithmetic, a trillion tiles at zoom 20, rules out precomputing everything, so the split between hot and cold is forced by the numbers rather than chosen by taste.
- Why is plain Dijkstra unacceptable when it is only a few seconds? A few seconds of CPU per query at thousands of queries per second means thousands of cores doing nothing but routing, and the experience of sub-second route updates during navigation dies entirely. Contraction hierarchies cut per-query work by four to five orders of magnitude, which turns the same hardware budget into comfortable headroom.
- How does live traffic get into routes if shortcuts bake in weights? The trick is separable preprocessing, in which the structural phase that finds shortcuts is reused while a fast customization phase re-applies current weights in minutes, so the metric stays fresh without ever redoing the expensive topology work.
- How do you compute an ETA for a trip arriving hours from now? The predictor blends live speeds for the near segments with historical profiles for the far ones, keyed by time of day and day of week, because current conditions decay in predictive value over the trip's duration, and a jam observed now says little about a road you will reach at midnight.
- What happens when a navigating phone loses signal? The downloaded corridor keeps turn-by-turn working locally, the client continues matching itself to the route, and on reconnect it uploads buffered probes and receives any pending reroute, so connectivity loss degrades traffic awareness rather than navigation itself, and the driver in the mountains keeps hearing instructions.
- How would you catch a bad map data release? Builds are validated against the previous version with sampled route comparisons and connectivity checks, rolled out region by region, and watched through reroute and ETA-error dashboards, with one-command rollback to the prior graph held ready, because the cheapest fix for a poisoned build is the version that came before it.
References
- Geisberger, Sanders, Schultes, Delling, Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (WEA 2008).
- OpenStreetMap Wiki, Slippy map tilenames, on the z/x/y tile addressing scheme.
- Google Official Blog, The bright side of sitting in traffic: Crowdsourcing road congestion data (2009).
- Mapbox, Vector Tile Specification, the open encoding for vector tiles.
- Xu, System Design Interview, Volume 2 (2022), chapter on Google Maps.