How to design a maps and navigation service

In this lesson, we’ll design a planet-scale maps and navigation service by treating it as three separate systems and never letting one system’s answer settle another’s question. That discipline is the whole trick: most confusion in this design comes from reaching for a storage answer to a graph question, or a graph answer to a prediction question. By the end you’ll be able to size the road graph, explain why we never run Dijkstra live, split topology from metric so live traffic stays cheap, and defend the whole ladder in an interview.

flowchart TD
    M["Maps and navigation"] --> D["Draw the map<br/>storage problem"]
    M --> R["Find a route<br/>graph problem"]
    M --> E["Predict arrival time<br/>prediction problem"]
    D --> D1["Keep a representation of the planet,<br/>serve any square of it"]
    R --> R1["Fastest sequence of roads<br/>between two points"]
    E --> E1["A path is not an arrival time"]

We own three of those pieces here: the tile pyramid (drawing), the shortest-path machinery (routing), and the traffic feedback loop that feeds both. Finding a place by name is autocomplete plus a spatial index (Autocomplete and Proximity Service); tracking where friends are is Nearby Friends. Predicting how long a road takes is a machine-learning problem, which we frame here and do not build.

Two numbers set up everything else

Routing is a graph problem, and two measurements of that graph decide the whole design. Hold both in your head, because every later section leans on one of them.

• The graph is small. All the world’s roads, encoded as junctions and segments, come to about 10.2 GB: the RAM of one ordinary server. Because the whole thing fits on one box, there is no distributed-database problem here.
• Searching that graph is slow. Answering one long route by the textbook method (Dijkstra) costs about 31 seconds of CPU, roughly 150x over any interactive budget. Since that is 150x too slow, the design has to avoid the search entirely.

We derive both figures in the routing deep dive below. Tiles, traffic, and ETA all follow from them.

The three requests the service answers

• A tile request is a zoom level and a grid position (“zoom 14, column 8,192, row 5,461”). The response is the drawable content of that one square.
• A route request is an origin, destination, travel mode, and departure time. The response is a short list of candidate routes, each with a polyline (an ordered list of latitude/longitude points that draws the path), a distance, turn-by-turn steps, and an estimated time of arrival (ETA).
• A probe upload is a batch of anonymized position fixes from a phone that is navigating: latitude, longitude, timestamp, speed, heading. The response is just an acknowledgement.

We reuse three planet constants throughout, shared with Proximity Service so every chapter agrees: the equator is 40,000,000 m around, Earth’s surface is 510,000,000 km², and 15,000,000 km² of it is settled land with mapped detail.

Two numbers, three request types, three planet constants: that is enough vocabulary to see why three decisions bind the design before any code is written.

The three binding decisions

Three decisions constrain the design, and we take them in the order they bind. Each one has a matching failure, so we name the number that punishes getting it wrong.

1. How much of the map do you pre-render? The two most zoomed-in levels are 93.75% of every map square you would store, so this is really “ship pixels or geometry.” Getting it wrong means a pre-rendered image pyramid of 431 TB instead of 526 GB of geometry.
2. How do you answer a shortest-path query in under 100 ms on a 205-million-node graph? Not by searching it. A live search prices at ~31 s per query and a ~19,600-box fleet; precomputation buys that down to ~0.5 ms.
3. How often can the edge weights change? An edge weight is how many seconds it takes to drive one road segment: the number the router minimizes. The fastest precomputation only works if weights are fixed while it runs, and live traffic changes them every two minutes. Get this wrong (let the router react to its own effect on traffic with no damping) and it performs worse than shipping no router at all.

Requirements

The functional list is short, so we move through it quickly. The non-functional targets matter more, because each one rules out a design before we start.

Functional:

• Render the map at any location, zoom levels 0-20.
• route(origin, destination, mode, depart_at) returning a polyline, turn steps, and an ETA.
• Re-route when the user leaves the route, in practice every few minutes.
• Live traffic overlaid on the map and reflected in the route.
• Ingest anonymized probe data from navigating devices.

Non-functional targets come next, and two terms set them up. p99 is the ninety-ninth-percentile latency: the response time 99 of 100 requests come in under, describing the slow tail. The edge is a content delivery network (CDN): caches placed physically near users so a request never crosses an ocean if the answer is already cached nearby.

Back of the envelope

We size every later section against three rates: how many people are navigating at once, how many route requests that produces, and how many position reports arrive from phones. Let’s compute each one, because each one sizes a different tier.

Vocabulary: DAU is daily active users. The 2.5x peak multiplier converts a daily average into the busiest second, since usage is not spread evenly (nobody navigates at 04:00). A day is 86,400 seconds. Rates per second are also called queries per second (QPS).

Concurrent navigators come first. At 1 billion DAU × 0.2 sessions/user/day × 1,800 s per session / 86,400 s, about 4.2 million sessions are in progress at any second. This is Little’s Law: concurrency = arrival rate × how long each thing lasts, and the figure is a daily average, not a peak.

Route requests follow from that. A 30-minute session makes one request at the start plus a re-route every 5 minutes, so 7 total. 7 × 200M sessions/day / 86,400 ≈ 16,000/s, and ×2.5 gives 40,510 route requests/s at peak. Every fleet size in this chapter is computed against that number.

Probe uploads are the third rate. Each navigating phone takes one GPS fix per second and uploads a batch of ten every 10 seconds (keeping the radio awake is what drains the battery). So 4.2M fixes/s average → 416,667 uploads/s average. Applying the same 2.5x peak multiplier gives 1.04M peak uploads/s and 10.4M peak fixes/s. Forgetting the peak here is a common slip: the phones held by the peak population do not stop uploading during the busy hour, so both rates are carried at peak.

Those two rates size different things:

• Peak uploads/s sizes the ingest tier: each network request needs a connection, a parse, an acknowledgement.
• Peak fixes/s is what the traffic pipeline reasons over: that is how many individual measurements arrive.

We do not store the fix stream durably. A position reading is worthless within a minute of being taken, so writing 4.2M/s to disk buys history nobody reads while putting a durable write on every upload’s critical path. The full argument is in Nearby Friends.

Those rates are what force the API next: a probe upload must return before its data is processed, and a base tile must outlive a traffic tile.

API sketch

Notation: .mvt is the Mapbox Vector Tile format, which carries drawable geometry (roads as lines, parks as polygons), not a finished picture. A TTL (time to live) is how long a cache may serve a copy before refetching. HTTP 202 means “accepted, will process later”: the right response for a probe, because the device must not wait for the traffic pipeline before it carries on driving.

GET  /v1/tiles/{z}/{x}/{y}.mvt         -> vector tile, immutable, CDN-cached
GET  /v1/tiles/traffic/{z}/{x}/{y}     -> speed overlay, 2-minute TTL

POST /v1/route
       {origin, destination, mode, depart_at, avoid[]}
    -> {routes: [{polyline, distance_m, eta_s, steps[], confidence}]}

POST /v1/probes                        {fixes: [{lat, lng, ts, speed, heading}]}
    -> 202

Two shapes in that contract carry decisions that are hard to undo once clients depend on them:

• Base tiles and traffic tiles are separate resources. The base tile (roads, parks, labels) never changes, so it lives at the edge forever; the traffic overlay expires in two minutes. Merge them and the combined resource inherits the shorter lifetime, dragging the whole map to a 2-minute TTL and making it uncacheable.
• /v1/route returns a list, not a single best route. The feedback-loop fix below needs the server to hand different near-optimal routes to different users. An API that can only return one route makes that fix a breaking change.

Data model

We keep five artifacts on one page because their lifetimes differ so sharply, and that difference is the design. A node is a road junction; a directed edge is one segment travelled one way (a two-way street is two edges); free_flow_s is the drive time with no traffic.

road_graph          immutable, versioned, loaded into RAM
  nodes[]           lat, lng, first_edge_index
  edges[]           target_node, length_m, free_flow_s, road_class, restrictions

overlay             precomputed shortcuts, rebuilt with the graph
metric              per-edge traversal time, rebuilt every 2 minutes
tiles               immutable blobs in object storage, CDN in front
segment_speeds      current speed per directed edge, in memory, 2-minute windows

The split that makes live traffic tractable is the one between topology and metric, so let’s name both:

• The topology is the shape of the network: which junctions connect to which, and how many metres lie between them. It changes only when a road is built or closed, on the order of weeks.
• The metric is the number on each edge: the seconds it currently takes to drive that segment. It changes whenever traffic moves, every couple of minutes.

Any design that fuses them into one artifact has to redo the expensive thing at the frequency of the cheap thing, which is why the fused design fails. That is the trap contraction hierarchies walk into and the cell overlay walks out of, both below.

High-level architecture

The architecture divides into a read path along the top, where the client asks for tiles and routes, and a write path along the bottom, where phones send position data that changes the routes. The two meet at the graph-plus-overlay artifact.

flowchart LR
    C["Client"] --> CDN["CDN<br/>edge cache for bytes"]
    CDN --> TS["Tile storage<br/>immutable vector tiles"]
    C --> RS["Route service<br/>stateless, answers from RAM"]
    RS --> G["Graph + cell overlay<br/>20.0 GB per box, replicated"]
    RS --> ETA["ETA model<br/>prediction, framed here"]
    C --> PI["Probe ingest<br/>acknowledge immediately"]
    PI --> MM["Map matching<br/>fix -> directed edge"]
    MM --> AGG["Speed aggregator<br/>2-minute windows"]
    AGG --> CUST["Metric customization<br/>re-price the overlay"]
    CUST --> G
    AGG --> TT["Traffic tiles"]
    TT --> CDN

On the read path, the client fetches map squares through the CDN, served from tile storage: a bucket of immutable vector tiles. Because they never change, the CDN holds them indefinitely and the origin is almost never touched. Separately, the client calls the route service, which answers entirely out of RAM (no database on this path). What it holds is the graph plus cell overlay: the road network plus the precomputed shortcut structure queried on top of it, 20.0 GB per box (derived below; note it is not the 12.7 GB of a plain contraction hierarchy). The route service also consults the ETA model for arrival times.

The write path is four boxes in a chain:

1. Probe ingest accepts batched uploads and acknowledges immediately.
2. Map matching turns each raw fix into a directed edge: deciding which road the car is actually on instead of trusting the reported point. GPS often lands a fix on the wrong side of a divided highway; this corrects it.
3. The speed aggregator groups matched observations into 2-minute windows and emits one current speed per segment. Two minutes is the freshness target, and a shorter window holds too few distinct vehicles to trust.
4. Metric customization turns those speeds back into the routing weights the graph is queried against.

The same aggregated speeds branch off as traffic tiles pushed through the CDN: the red-and-green overlay the user sees.

One loop is what makes this chapter different. Probes become speeds, speeds become the metric, the metric changes the routes, and the routes change where the probes go.

flowchart LR
    P["Probes"] --> S["Segment speeds"]
    S --> M["Routing metric"]
    M --> R["Routes returned"]
    R --> P

That is a control loop with the users inside it. Closing it without making it oscillate is the last deep dive.

The tile pyramid, and why the top is free

Storing a map as pictures has a cost, and almost all of it lives in the two most zoomed-in levels. Once we see where the cost concentrates, shipping geometry to the client instead of pixels stops being a preference and becomes the obvious move.

A tile pyramid slices the world into square images at every zoom level. Zoom 0 is the whole planet in one square; each level down splits every square into four, so level z has 4^z tiles. Web Mercator is the standard projection: it stretches the map into a square with north up (which is why Greenland looks the size of Africa), giving a 2^z × 2^z grid of 256×256-pixel tiles.

Because each level holds 4× the one above, the bottom level alone is 3/4 of all tiles and the bottom two are 15/16. The whole cost of a tile scheme is decided by where you stop at the bottom; the top is free.

Ground resolution follows from the 40,000,000 m circumference: a tile is 40,000,000 / 2^z metres wide. Zoom 14 is a 2.4 km square (a neighbourhood); zoom 20 is a 38 m square, so with 256 pixels across, one pixel is 0.15 m of ground: building-outline and parking-space detail. That is what the expensive bottom levels buy.

A zoom-z tile is exactly a geohash cell with z longitude bits (a geohash turns a lat/lng pair into a short string by repeatedly halving the world). Tiles and geohash cells are the same subdivision, which is why one cell id can both key the tile cache and shard the map matcher (Proximity Service derives the cell scheme).

Ship geometry, not pixels

flowchart TD
    A["Map tiles, zoom 0-20"] --> B{"Ship pixels or geometry?"}
    B -->|"Raster, pre-drawn to zoom 20"| C["Finished images<br/>431 TB, 93.75% in the bottom 2 levels"]
    B -->|"Vector geometry to zoom 14"| D["Client draws finer zooms<br/>526 GB, 819x smaller"]

A raster tile is a small pre-drawn image (~10,000 B). A full raster pyramid to zoom 20, restricted to the 2.94% of Earth that is settled land, is about 431 TB (dropping open ocean already cut an all-surface 14.7 PB by ~34x). But 93.75% of that 431 TB is the two bottom zoom levels, which exist only to show building outlines.

The fix is vector tiles: ship the geometry (coordinates of roads, outlines of parks, positions of labels) once at a coarse zoom, and let the client draw every finer zoom by scaling it on the device. Stop the pyramid at zoom 14 and it comes to about 526 GB, 819x smaller.

The 819x decomposes cleanly: a vector tile is 5x bigger than a raster one (50,000 B vs 10,000 B), but there are 4^6 = 4,096x fewer of them because six zoom levels stop existing. Net: 4096 / 5 ≈ 819. The win is entirely the deleted levels; the format itself costs a factor of 5.

Three further wins come free: a restyle needs no re-render (colours are applied on the device), labels rotate with the device, and the client can zoom smoothly. The cost is client work: the device now spends its own processor time rasterizing geometry into pixels, so the design takes a hard dependency on a capable client. Raster tiles therefore stay for two cases: old devices, and satellite imagery (photography, which cannot be expressed as vectors).

Storage is settled. The harder number is the one that decides routing: how long a single search takes, and why it is far too long.

The graph, and why nobody runs Dijkstra

The routing design rests on two facts, and we’ll prove both with numbers: the world road network fits in one machine’s memory, and searching it live is four orders of magnitude too slow.

How big the graph is

Model roads as a graph: junctions are nodes, each segment travelled one way is a directed edge. Starting from 64,000,000 km of paved road and a 0.25 km mean segment:

• 64M km / 0.25 km = 256M segments, so 512M directed edges (two per segment).
• A node’s degree is how many road ends meet at it (a crossroads is 4, a dead end is 1; 2.5 is a planet-wide average). 512M road ends / 2.5 ≈ 205M nodes.

Stored as flat arrays (a node is 20 B: lat/lng + first-edge index + attributes; an edge is 12 B: target + length + time), that is 205M × 20 + 512M × 12 ≈ 10.2 GB. Every road on Earth fits in one commodity 128 GB box, with headroom.

That removes distributed shortest path from consideration, which matters because shortest-path search is inherently sequential. It grows outward from the origin one ring at a time. The advancing boundary is the frontier, and each ring needs the previous one finished. Split the graph across machines and every cross-machine frontier step becomes a ~500 µs network round trip instead of a ~100 ns memory read (Estimation supplies both numbers), about 5,000x slower on the most frequent step.

One more figure: nodes per km² is 205M / 15M km² = 13.65. Search cost depends on the area it covers, so this converts area into nodes.

What a search costs

Dijkstra’s algorithm explores outward in order of increasing cost, and it cannot stop until it settles the destination, meaning it has already settled every node cheaper to reach. With a distance-like cost, that is a disc centred on the origin whose radius is the route length.

Take a 1,000 km straight-line trip. Roads are not straight, so a 1.2 detour factor gives a 1,200 km route and a disc of that radius:

• Disc area ≈ π × 1,200² ≈ 4.5M km², so 13.65 × 4.5M ≈ 61.8M nodes settled, 30% of the whole planet’s road network.
• At ~500 ns per settled node (each touches memory at an unpredictable address, so it is a random reference, not a cheap sequential read), that is 61.8M × 500 ns ≈ 31 seconds on one core.
• At 40,510 peak QPS that needs 30.9 × 40,510 / 64 ≈ 19,559 boxes, and p99 would still be half a minute.

That rules out “just run Dijkstra.”

A* (Dijkstra plus a heuristic: an optimistic guess of the remaining distance to the destination, which biases the search toward the goal) shrinks the search region from a disc to an ellipse with the origin and destination as foci, because the settled set becomes the points whose distances to those two sum to the route length. That works out about 7.2x smaller (roughly 8.5M nodes, 4.3 seconds), still ~20x over budget.

The 7.2x is set by the detour-factor geometry, not the implementation, so better code does not move it. Neither does a better heuristic: straight-line distance is the largest admissible guess available (admissible means it never overestimates the remaining cost, which is what guarantees the true shortest path), so nothing can shrink the ellipse further. The only way out is to not search the graph at all.

Contraction hierarchies, and what preprocessing buys

Here is the idea before the machinery: if searching live is too slow, we do the searching once, ahead of time, and let each query reuse the result. That trade buys the largest single win in the chapter, a 61,800x speedup for about 18 core-hours of preprocessing, with one catch we’ll hit at the end.

Contraction hierarchies (CH) are three steps:

flowchart TD
    S1["1. Rank nodes by importance<br/>motorway junction &gt; cul-de-sac"] --> S2["2. Contract least-important first<br/>remove node v, add shortcut u-&gt;w<br/>where u-&gt;v-&gt;w was the only shortest path"]
    S2 --> S3["3. Query: bidirectional search from both ends,<br/>moving only upward in importance"]

The query is fast because a real journey climbs local road → arterial → motorway → arterial → local. The upward-only rule turns that into a short climb from each end, so the two searches meet after a few hundred steps regardless of how far apart the endpoints are.

Contracting a node needs witness searches: small local searches checking whether a neighbour pair u, w already has an equally short path avoiding v (if so, no shortcut). At degree 2.5 that is ~6.25 pairs per node, ~50 µs each, over 205M nodes ≈ 64,000 core-seconds, about 18 core-hours to preprocess the planet. The shortcuts inflate the edge count ~40% (to ~716.8M edges), growing the artifact to 12.7 GB: the node array is unchanged at 4.1 GB, but the edge array is replaced with an 8.6 GB one.

The bidirectional upward search settles about 1,000 nodes on a continental network, an empirical property of real road hierarchies, essentially independent of trip length. That is ~0.5 ms, and 40,510 QPS × 0.5 ms ≈ 20 cores.

Eighteen core-hours of preprocessing turns a 19,559-box fleet into 20 cores.

The catch is that the shortcut set is derived from the edge weights, so it is only valid for the metric it was built against. A shortcut u→w exists because the path through v was the shortest: a statement about current travel times. Let traffic slow one road and a shortcut may no longer be justified, and the invalidation can propagate anywhere in the hierarchy. You cannot patch it; rebuilding is the only sound fix, and 18 core-hours does not fit a 120-second window (squeezing it in would take ~533 cores running continuously before serving one query). So CH alone is incompatible with live traffic.

That catch is what forces the next move: keep almost all of the CH speedup, but build the precomputed structure so that traffic relabels it instead of rebuilding it.

Separating topology from metric

We can keep almost all of the CH win while refreshing travel times every two minutes, by splitting the precomputed artifact along its rate of change: build a structure whose existence depends only on topology, and where only the labels depend on the metric. Then a traffic update relabels instead of rebuilding, which is the whole point.

The structure is four moves:

1. Cut the graph into cells of a few thousand nodes each (roughly a chunk of a city). A planar partitioner cuts a map-like graph into balanced regions with as few edges crossing the cuts as possible.
2. Identify the doorways. A boundary node has an edge leaving its cell. Any route through a cell enters and leaves through boundary nodes.
3. Precompute a clique over each cell’s doorways: an edge from every boundary node to every other, labelled with the shortest travel time between them through the inside of the cell. “Enter at doorway 3, leave at doorway 17: 84 seconds.”
4. Query across the doorways. A route hops doorway-to-doorway across this overlay of cliques, descending into road-level detail only in the two cells holding the origin and destination.

Which nodes are boundaries and which clique edges exist is a fact about the shape of the graph. Traffic never changes it: it only changes the numbers on the clique edges, which recompute one cell at a time.

How big the overlay is

Boundary count scales as the square root of cell size (a region’s perimeter grows as the square root of its area). Using 2 × sqrt(cell size) for typical partitioner output, a 4,096-node cell has ~128 doorways:

• Cells: 205M / 4,096 ≈ 50,000.
• Clique edges per cell: 128 × 127 ≈ 16,256 (every doorway to every other doorway).
• Overlay edges: 50,000 × 16,256 ≈ 813M, at 12 B each ≈ 9.8 GB.
• Served artifact: 10.24 GB graph + 9.8 GB overlay = 20.0 GB.

That 20.0 GB, not 12.7 GB, is what a route box holds. The difference is replaces versus sits on top of. A contraction hierarchy replaces the edge array (12.7 GB total, old edges gone). The cell overlay sits on top of the untouched graph, because a query still descends into road-level detail inside the two endpoint cells and cannot do that if the roads are thrown away. So the full 10.24 GB stays resident alongside the 9.8 GB of cliques. Quoting 12.7 GB for this design understates the real footprint by 57%.

Customization: re-pricing the overlay

Customization recomputes the numbers on the overlay edges against a new metric. It is cheap because it never leaves a cell: one bounded Dijkstra per boundary node, restricted to that cell’s ~4,096 nodes, produces one row of the cell’s clique. The 50,000 cells are therefore independent.

• Full pass: ~0.26 core-s/cell × 50,000 ≈ 13,100 core-seconds (3.6 core-hours), or 205 s on 64 cores.
• But only ~5% of cells see a material change in a given window (an unchanged cell yields an identical clique), so real work ≈ 655 core-seconds ≈ 10.2 s on 64 cores, fitting the 120-second window with better than a 10x margin. The 5% is an assumption to check, not a guarantee.

Against 64,000 core-seconds to rebuild a CH, that is 97.7x cheaper. Split it: 4.9x is the two-phase structure itself (full customization vs full rebuild, which holds unconditionally), and the other 20x is exactly 1 / 0.05, the incrementality assumption. Even at 50% incrementality the win is still 9.8x. So the division of labour is: topology preprocessing runs when a road is built; customization runs every two minutes.

The split is not free. The overlay query walks a clique at each crossed cell, so it is ~a few ms instead of CH’s 0.5 ms (~10x slower). That is negligible against a 200 ms p99 (5 ms is 2.5% of the budget), and 40,510 × 5 ms ≈ 203 cores. You trade a 10x slower query for a 97.7x cheaper update, the right side of the trade when traffic changes every two minutes.

We now have a fast path and a fresh metric. What we still do not have is an arrival time, and that turns out to be a different kind of problem.

ETA is a prediction, not a graph traversal

The graph gives you a path; it cannot give you an arrival time, which is the metric users actually judge. You might expect that summing the edge times along the path gives the ETA, and it does not, for three reasons:

• Turn and intersection costs live at junctions, not edges. A left turn across oncoming traffic costs 20-40 s and belongs to the junction, not either road.
• Speeds are conditional on time. The same segment behaves completely differently at 08:00 Tuesday and 22:00 Sunday. The historical profile (the recorded distribution of past traversals at this time of week) carries more information than a live reading when live coverage is thin, and at most 1.2% of segments have live data at any moment (shown below).
• Error is asymmetric. Arriving 5 minutes late is worse than 5 minutes early, so the loss function must punish lateness harder, and the best number to report ends up above the mean outcome.

We frame the model here rather than build it, and the framing asks four things:

Two terms from that last row. A feature store is the shared service that computes and serves the model’s inputs so training and serving read them from the same place. Train/serve skew is what happens when they do not: the model is trained on features computed one way in batch and served features computed slightly differently at request time, and accuracy quietly degrades with nothing failing.

The consistency trap is that the metric the router optimizes and the model that reports the ETA must be the same function. If routing uses the customized edge times and the ETA comes from a separately trained model, the route you return is fastest under the routing metric while the number you display comes from a different function, so the route is not the fastest one under the model that quoted the time. Nothing fails a test; the product is quietly wrong. Two acceptable fixes: the model produces the edge metric (customization runs on its output), or the ETA is the metric’s own path cost plus a learned correction for turn costs and bias. What is not acceptable is two independent estimates of the same quantity.

Traffic ingestion, and the loop that eats itself

Live traffic data is far scarcer than the raw ingest rate suggests, and a router that reacts to it naively makes traffic worse.

How little of the network has live data

Fixes are not observations. Consecutive fixes from the same vehicle on the same segment carry no new information. A car sitting on one segment for eight seconds sends eight fixes but tells you one thing: one vehicle crossed at this speed. So the quantity that matters is distinct vehicle-segment observations.

Using the average population (coverage describes the typical moment, not the busiest second): a car at 15 m/s covers 1,800 m per 2-minute window, so it crosses 1,800 / 250 ≈ 7.2 segments. With 4.2M cars, that is about 30M observations per window against 512M directed edges: 5.9% touched. Requiring five distinct vehicles before trusting a live speed gives 30M / 5 / 512M ≈ 1.2%.

That 1.2% is a ceiling, not an expectation. The 5.9% line only makes sense if every observation lands on a distinct segment; dividing by five assumes the opposite, that observations arrive in tidy groups of five all on the same segment. Both cannot hold, so obs / 5 / edges is the best case under perfect concentration. At the other extreme, observations spread uniformly (a Poisson distribution with mean 0.059 per edge), the chance of five-or-more on an edge is about 6e-9, effectively zero. Reality sits between, near the ceiling, because traffic concentrates on the roads that carry traffic.

The corollary decides the design: at most 1.2% of the network has a live speed at any moment, and raising the ping frequency does not change that, because information is set by how many distinct vehicles are on the road, not how often each reports. So the historical profile is the primary signal (live probes correct the small slice where they exist), and batching aggressively at the client (the 10-second upload) is free, because the extra fixes carry no information.

The feedback loop

A router that sees a jam and reroutes everyone around it creates a jam on the detour. Let’s model that with two routes whose time rises with load (x = vehicles/hour), because the tiny example makes the failure obvious:

• Route A (short, congests fast): 10 + x_A / 200 minutes.
• Route B (long way round, tolerant): 20 + x_B / 400 minutes.
• Demand is 3,000/hour, and x_A + x_B = 3,000.

At equilibrium (the split where no driver could get home faster by switching) both routes take the same time. Solving gives x_A = 2,333, x_B = 667, and 21.7 minutes for everyone.

A greedy router always recommends whichever route is currently fastest, but its view of traffic lags one 2-minute window. So it acts on the previous state: window 1 sends everyone to B (which becomes slow), window 2 sends everyone to A, and it flips forever. Averaging the two extremes it spends equal time in:

A traffic-aware router with a control lag and no damping is worse than no router at all (26.25 vs 25.0). The fix is structural, in three parts:

1. Split the demand instead of switching it. Return k near-optimal routes (this is why /v1/route returns a list) and assign each request one at random, weighted by that route’s spare capacity. Different users get different answers, so there is nothing for the population to stampede toward, and the split lands near equilibrium by construction.
2. Damp the update, moving only part of the way each window. With p_next = (1 - α)·p + α·p_target and α = 0.3, the residual error is 0.7^n, so reaching 5% takes ~9 windows, 18 minutes, longer than most trips. Damping alone is insufficient; the split does the real work. Damping only keeps the oscillation gentle.
3. Do not optimize for the system optimum. The equilibrium above is the user equilibrium (no driver can improve their own time). A system-optimal assignment minimizes total driving time but requires routing some individuals onto slower paths for strangers’ benefit: a product nobody keeps installed, and an ethics question, not an engineering one. Route each user selfishly, and manage the aggregate only by splitting among routes that are genuinely near-optimal for that user.

Bottlenecks and scaling

What runs out first has an answer unusual for this track: nothing here is fixed by partitioning the data. To shard is to split a dataset across machines that each hold a disjoint slice; to replicate is to give every machine the same complete copy. The rule of thumb: shard when the data does not fit, replicate when the requests do not fit. Here the data fits in 20.0 GB, so every row below is a replication answer.

Failure modes

Every mitigation degrades to a worse answer, not to no answer: stale traffic still routes, missing live speeds fall back to the historical profile. A slightly wrong route beats a spinner.

Alternatives rejected

Each was priced out, so every rejection has a number attached.

What breaks the design

Some assumptions are load-bearing: if wrong, the design is not merely suboptimal, it is invalid: a box appears or disappears. The test: move the assumption an order of magnitude each way and ask whether the set of boxes changes, or only the number of machines inside them.

Two numbers look load-bearing but are not:

• The 500 ns per settled node multiplies Dijkstra, A*, CH, and customization by the same factor, so every ratio (the 7.24x, 61,800x, 97.7x) is independent of it. Even ten times faster memory leaves a live Dijkstra query at 3.1 s, still 15x over budget.
• The 1,000 km trip used to price the search is not what the 30.9 s was reverse-engineered from. Shrink it a full order of magnitude to a 100 km trip and Dijkstra still needs ~196 boxes against contraction hierarchies’ 20 cores, two orders of magnitude apart. “But most trips are short” does not rescue live search.

Tunable dials (the 5-vehicle threshold, the 5% incrementality, the α = 0.3 step, the 4,096-node cell size) move a threshold or a cost along a smooth curve, but change no box: the two-phase structure survives every value.

Conclusion

flowchart TD
    subgraph DRAW["Draw the map"]
        V["Vector tiles to zoom 14, client rasterizes<br/>526 GB, 819x smaller than raster to zoom 20"]
    end
    subgraph ROUTE["Find a route"]
        CO["Cell overlay on the 10.2 GB graph = 20.0 GB per box<br/>~few ms query, replicated"]
        CU["Customization re-prices only changed cells<br/>10.2 s every 2 minutes, 97.7x cheaper than a CH rebuild"]
        CU --> CO
    end
    subgraph PREDICT["Predict arrival time"]
        ET["ETA model = routing metric + learned correction<br/>historical profile primary, live probes correct ~1%"]
    end
    subgraph LOOP["Traffic loop"]
        FB["Split demand across k routes + damp<br/>avoids the greedy router that makes its own jam"]
    end
    LOOP --> ROUTE
    ROUTE --> PREDICT

The load-bearing takeaways:

• Maps is three systems. Rendering is storage, routing is a graph, ETA is prediction. Keeping them separate is what makes the whole thing tractable.
• Ship geometry, not pixels. 4^z per level means the bottom two zoom levels are 15/16 of any pyramid, so vector tiles to zoom 14 beat raster to zoom 20 by 819x.
• Never search the graph live. Dijkstra is 30.9 s and A* is 4.3 s; precomputation is 0.5 ms. The graph is small (10.2 GB), so routing is a replication problem, never a partitioning one.
• Split topology from metric. Preprocess the metric-independent shape once; re-price only the changed cells every two minutes. That is what makes contraction-hierarchy-class routing coexist with live traffic.
• The router is inside a control loop. Reroute everyone naively and you build the jam you avoided. Split demand across near-optimal routes so different users get different answers.

One line to remember: maps is storage, a graph, and a prediction wearing one app, and the whole design is just the discipline of never letting one of them answer for another.

Further reading

• Geisberger, Sanders, Schultes, Delling: Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (2008), the original CH paper.
• Delling, Goldberg, Pajor, Werneck: Customizable Route Planning (Microsoft Research), the topology/metric separation this chapter’s overlay is based on.
• Mapbox Vector Tile specification, the geometry-tile format behind the 819x saving.
• J. G. Wardrop: Some Theoretical Aspects of Road Traffic Research (1952), the source of user equilibrium and the feedback-loop analysis.

Related: Proximity Service derives the cell scheme the tiles and map matching share; Nearby Friends owns the location stream this chapter ingests; Back-of-the-Envelope Estimation supplies the 100 ns and 500 µs that price every search above.