19 — Design Google Maps

A planet-scale mapping and navigation service is three distinct systems:

1. Drawing the map — a storage problem. How do you keep a representation of the whole planet and serve any square of it?
2. Finding a route — a graph problem. Given two points, which sequence of roads is fastest?
3. Predicting how long that route takes — a prediction problem. The graph gives you a path; it does not give you an arrival time.

Each requirement belongs to one of the three. Confusing them leads to applying a storage answer to a graph question.

This chapter covers four results: the cost of a shortest-path query over the world’s roads, why no production router answers one by searching, the precomputation that replaces the search, and why a traffic-aware router can be worse than no router at all.

The service answers three kinds of request.

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

Those three shapes are written out as an interface in Api sketch.

The spine of the answer is two numbers

Routing is not a spatial-index problem. It is a graph problem, and two measurements of that graph decide everything else in the chapter.

The graph is small. All the world’s roads, encoded as junctions and segments, come to 10,240,000,000 B = 10.2 GB. That fits in the RAM of a single ordinary server (RAM being random-access memory, the fast working memory a program computes out of), so there is no distributed-database problem here.

Searching that graph is slow. Answering one long route by the textbook method costs 61,751,290 x 0.0000005 = 30.9 seconds of processor time, roughly 150x over any interactive budget. The design has to avoid the search entirely.

Both figures are derived step by step in Deep dive 2 the graph and why nobody runs dijkstra. Tiles, traffic, and ETA all follow from them.

What this chapter owns, and what it does not

Half of what people call “Maps” belongs to other chapters:

• Finding a place by name is ch 13 plus ch 17’s index.
• Tracking where your friends are is ch 18.
• Predicting how long a road takes is a machine-learning problem, and this chapter frames it rather than builds it (ml/01).

This chapter owns three things: the tile pyramid, the shortest-path machinery, and the traffic feedback loop.

Four common mistakes:

• Proposing Dijkstra’s algorithm — the textbook shortest-path search, which expands outward from the origin one ring at a time until it reaches the destination — with no cost estimate attached.
• Pre-rendering every zoom level, an 819x overspend on storage (Deep dive 1 the tile pyramid and why the top is free).
• Treating the ETA as a sum of speed limits along the path.
• Missing that a router which reroutes everyone creates the jam it was avoiding.

Three constants about the planet are used unchanged throughout. They are stated once in Framing what decision and what breaks so that every chapter agrees on them: the equator is 40,000,000 m around, the Earth’s surface is 510,000,000 km^2, and 15,000,000 km^2 of that surface is settled land with mapped detail.

1. Framing: what decision, and what breaks

Three decisions constrain the design. Take them in the order they bind.

Decision 1: how much of the map do you pre-render?

Deep dive 1 the tile pyramid and why the top is free shows that the two most-zoomed-in levels are 93.75% of every map square you would ever store. So this is really the question “do you ship pixels or geometry”, and the answer moves the storage bill by nearly three orders of magnitude — 431 TB down to 526 GB.

Decision 2: how do you answer a shortest-path query in under 100 ms on a graph with 205 million nodes?

Not by searching it. Deep dive 2 the graph and why nobody runs dijkstra prices the search at 30.9 s per query, and Deep dive 3 contraction hierarchies and what preprocessing buys buys that back down to 0.5 ms with precomputation done ahead of time.

Decision 3: how often can the edge weights change?

An edge weight here is how many seconds it takes to drive one road segment. It is the number the router is minimizing over.

This question decides which precomputation you use. The fastest technique (Deep dive 3 contraction hierarchies and what preprocessing buys) only works if the weights are fixed while it runs, and live traffic changes them every two minutes. Deep dive 4 separating topology from metric resolves that collision.

Each decision has a matching failure. Get decision 2 wrong and a live search needs a 19,559-box fleet (Deep dive 2 the graph and why nobody runs dijkstra). Get decision 1 wrong and a pre-rendered pyramid of images needs 431 TB (Deep dive 1 the tile pyramid and why the top is free). Get decision 3 wrong — let the router react to its own effect on traffic with no damping — and it performs worse than shipping no router at all (Deep dive 6 traffic ingestion and the loop that eats itself).

2. Requirements

The functional list is brief. The five non-functional targets matter more, because each rules out a design you might otherwise propose.

Functional

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

Non-functional — these decide the design

Two pieces of vocabulary before the table. p99 is the ninety-ninth-percentile latency: the response time that 99 out of 100 requests come in under, so it describes the slow tail rather than the typical case. The edge means a content delivery network (CDN) — a fleet of caches physically near users, so that a request never crosses an ocean if the answer is already cached nearby.

Each row pairs a requirement with the design it kills.

3. Back of the envelope

Every later section is sized against three rates: how many people are navigating at once, how many route requests per second that produces, and how many position reports arrive from their phones.

Vocabulary first. DAU is daily active users, the count of distinct people who open the app on a given day. The 2.5x peak multiplier converts a daily average into the busiest second of the day, because usage is not spread evenly over 24 hours — nobody navigates at 04:00. Rates written per second are also called queries per second (QPS) later in the chapter; it is the same quantity under a shorter name. And 86,400 is simply the number of seconds in a day (60 x 60 x 24).

3.1 How many people are navigating right now

The first block turns a daily user count into a concurrent population — how many navigation sessions are open at the same instant.

DAU                            1,000,000,000
navigation sessions/user/day   0.2
sessions/day                   1,000,000,000 x 0.2      =  200,000,000
mean session length            1,800 s
concurrent navigators          200,000,000 x 1,800 / 86,400  =  4,166,667

Understand the last line rather than memorize it. Multiply sessions per day by seconds per session and you get session-seconds per day: 200,000,000 x 1,800 = 360,000,000,000 seconds of navigation happen every day. Spread that evenly across the day’s 86,400 seconds and 360,000,000,000 / 86,400 = 4,166,667 sessions are in progress at any given second.

That is Little’s Law: concurrency equals arrival rate times how long each thing lasts.

Note the word evenly. This 4,166,667 is a daily average, not a peak. That matters later in this section.

3.2 Route requests per second

A session asks for a route once at the start, and then re-routes every five minutes because the user drifted off the path or traffic moved. A 30-minute session therefore contains 1,800 / 300 = 6 re-routes plus the original request, so 7 requests total.

route requests/session         1 + 1,800 / 300          =  7
route requests/day             200,000,000 x 7          =  1,400,000,000
per second                     1,400,000,000 / 86,400   =  16,204
peak, 2.5x average             16,204 x 2.5             =  40,510

40,510 route requests per second at peak. Every fleet size in this chapter is computed against that number.

3.3 Probe uploads coming back in

Now the write path. Each navigating device takes a GPS fix — one position reading from the Global Positioning System, giving latitude, longitude, speed and heading — once a second. It does not send each one immediately; it batches ten of them and uploads every 10 seconds, because keeping the radio awake is what drains a phone battery.

GPS fixes/s, average           4,166,667 x 1            =  4,166,667
uploads/s, average             4,166,667 / 10           =  416,667
uploads/s, peak at 2.5x        416,667 x 2.5            =  1,041,667
fixes/s, peak at 2.5x          4,166,667 x 2.5          =  10,416,667

Line by line: 4,166,667 phones each producing one fix per second is 4,166,667 fixes per second. Batching ten fixes into one HTTP request divides the request rate by ten, to 416,667 uploads per second, while leaving the fix rate untouched. Then both get the 2.5x peak multiplier.

Do not forget the peak multiplier here

Forgetting the 2.5x on this block is a common mistake. The 4,166,667 concurrent navigators everything descends from is a daily average: §3.1 divided the whole day’s session-seconds by the whole day.

Route requests got 2.5x applied to that same population one block ago, and the phones held by that population do not stop uploading during the busy hour.

Quoting a peak QPS beside an average uploads/s compares two different quantities. ch 01 treats that as a bug, so both rates are carried at peak from here on.

Two rates, two different things they size

The same population produces two numbers, and they are not interchangeable:

• 1,041,667 peak uploads/s sizes the ingest tier, because that is how many network requests arrive and each one needs a connection, a parse and an acknowledgement.
• 10,416,667 peak fixes/s is what the traffic pipeline reasons over, because that is how many individual measurements the requests contain.

A third rate matters more than either: the pipeline’s information rate — how many genuinely new facts about the road network arrive per second. How little of the road network has live data shows it is far smaller than both of these, and that it should be computed at the average rather than the peak, because coverage is a question about the typical moment rather than the busiest second.

What this envelope deliberately does not do

It does not store the fix stream durably. A position reading is worthless within a minute of being taken, so writing 4.2 million of them a second to disk buys history nobody reads while putting a durable write on the critical path of every upload. The full argument, with the storage bill attached, is Back of the envelope and why the database is the wrong answer.

4. API sketch

Two of the request and response shapes below carry design decisions that are hard to undo later.

Three pieces of notation appear below. .mvt is the Mapbox Vector Tile format, which carries drawable geometry (roads as lines, parks as polygons) rather than a finished picture. A TTL is a time to live: how long a cache may serve a copy before it must fetch a fresh one. HTTP 202 means “accepted, will process later”, which is the right response for a probe upload because the device must not wait for the traffic pipeline to finish before it carries on driving.

Two things in the block below carry weight: the first two lines are separate endpoints for what looks like one thing, and the response type of POST /v1/route is a list where you would expect a single answer.

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

The shapes commit you to two things.

Base tiles and traffic tiles are separate resources. The base tile — roads, parks, labels — never changes, so it can live at the CDN edge forever. The traffic overlay expires in two minutes. If you merged them into one resource, the merged thing would have to carry the shorter of the two lifetimes, which would drag the entire map down to a two-minute TTL and make it effectively uncacheable. Splitting them means the expensive part is cached forever and only the cheap overlay is re-fetched.

/v1/route returns a list rather than a single best route. This is not just a convenience. The fix for the feedback loop in The feedback loop requires the server to hand out different near-optimal routes to different users, and an API shape that can only return one route makes that fix impossible without a breaking change.

5. Data model

The system stores five artifacts. They belong on one page because they have very different lifetimes.

Three terms first. A node is a road junction. A directed edge is one road segment travelled in one direction, so an ordinary two-way street is two edges pointing opposite ways, and a one-way street is one edge. free_flow_s is how long the segment takes to drive with no traffic on it, the best case.

Read the right-hand comments in the block below rather than the field names. The comments are the lifetimes, ranging from “rebuilt when a road is built” to “rebuilt every 2 minutes”.

road_graph          immutable artifact, 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. Section 9
metric              per-edge traversal time, rebuilt every 2 minutes. Section 10
tiles               immutable blobs in object storage, CDN in front. Section 7
segment_speeds      current speed per directed edge, in memory, 2-minute windows

The overlay is derived in Deep dive 3 contraction hierarchies and what preprocessing buys and re-shaped in Deep dive 4 separating topology from metric; the metric refresh is Deep dive 4 separating topology from metric; the tiles are Deep dive 1 the tile pyramid and why the top is free.

The split that makes traffic tractable is this: the topology and the metric are different artifacts with different lifetimes.

The topology is the shape of the network — which junctions connect to which, and how many metres of tarmac lie between them. It changes only when a road is built or closed, so on the order of weeks.

The metric is the number attached to each edge — the seconds it currently takes to drive that segment. It changes whenever traffic moves, so every couple of minutes.

Keep the two words straight; they are used through the rest of the chapter. Topology is the map. Metric is the current conditions on it.

The consequence: any design that fuses them into one artifact has to redo the expensive thing at the frequency of the cheap thing. That is the trap Deep dive 3 contraction hierarchies and what preprocessing buys walks into and Deep dive 4 separating topology from metric walks out of.

6. High-level architecture

The architecture has two halves plus a feedback loop that makes this problem different from every other chapter in the track. Read the diagram as a read path along the top (client asks for map squares and routes) and a write path along the bottom (phones send position data back, which changes the routes). The two meet at the box marked Graph + cell overlay.

flowchart LR
    C["Client"] --> CDN["CDN"]
    CDN --> TS["Tile storage<br/>immutable vector tiles"]
    C --> RS["Route service<br/>overlay query, in RAM"]
    RS --> G["Graph + cell overlay<br/>20.0 GB per box"]
    RS --> ETA["ETA model<br/>ml/01"]
    C --> PI["Probe ingest"]
    PI --> MM["Map matching<br/>fix -> directed edge"]
    MM --> AGG["Speed aggregator<br/>2-minute windows"]
    AGG --> CUST["Metric customization"]
    CUST --> G
    AGG --> TT["Traffic tiles"]
    TT --> CDN

    style CDN fill:#bc6c25,color:#fff
    style G fill:#2d6a4f,color:#fff

6.1 The read path, across the top

The client does two independent things.

It fetches map squares through the CDN, which serves them out of tile storage — a bucket of immutable vector tiles sitting in object storage. Because those tiles never change, the CDN can hold them indefinitely and the origin is almost never touched.

It separately calls the route service, which answers entirely out of RAM. There is no database on this path. What it holds in memory is the graph plus cell overlay artifact: the full road network plus the precomputed shortcut structure queried on top of it. That is 20.0 GB per box, a size derived in Deep dive 4 separating topology from metric.

One number to get right: that box is not the 12.7 GB of a contraction hierarchy. Deep dive 3 contraction hierarchies and what preprocessing buys prices that design and Deep dive 4 separating topology from metric rejects it. The difference is explained where the two are derived.

The route service also consults the ETA model for arrival times. That model is framed rather than built here (ml/01, and Deep dive 5 eta is a prediction not a graph traversal).

6.2 The write path, along the bottom

Four boxes in a chain, each doing one job.

1. Probe ingest accepts the batched position uploads from phones and acknowledges them immediately.
2. Map matching turns each raw fix into a directed edge: it decides which road the car is actually on, rather than trusting the exact point the phone reported. GPS often lands a fix on the wrong side of a divided highway, and this box corrects that.
3. The speed aggregator groups those matched observations into 2-minute windows and emits one current speed per segment. Two minutes because that is the freshness target from Requirements, and because a shorter window would contain too few distinct vehicles to trust.
4. Metric customization turns those speeds back into the routing weights the graph is queried against (Deep dive 4 separating topology from metric).

The same aggregated speeds branch off and are also rendered as traffic tiles, then pushed out through the CDN — that is the red-and-green overlay the user sees on the map.

6.3 The loop that makes this chapter different

Probes become speeds. Speeds become the metric. The metric changes the routes. 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. Nothing else in this track has one. Deep dive 6 traffic ingestion and the loop that eats itself is about closing it without making it oscillate.

6.4 Why those two boxes are coloured

Colours follow ch 01’s key, unchanged. Only two boxes get one.

Green #2d6a4f means read capacity: anything that answers a read without asking the authoritative copy. That is what the graph-plus-overlay artifact is: a derived, immutable, replicated copy that answers every route without consulting the offline build that produced it.

Orange #bc6c25 means forced by something other than processor time. The CDN is here for bytes, not compute, as in ch 01’s assembled diagram.

Two boxes are deliberately left uncoloured:

• The route service is a stateless request-path tier holding no authoritative state, so it cannot be blue.
• Metric customization is the most processor-bound box on the page, at 13,100 core-seconds a pass (Deep dive 4 separating topology from metric). Orange means the opposite of that.

Nothing on this diagram is blue, because the authoritative copy of the map is an offline versioned build (Data model) rather than a running box.

7. Deep dive 1: 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. That is what justifies shipping geometry to the client instead.

7.1 The shape of the pyramid

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: zoom 1 is 2 by 2 squares, zoom 2 is 4 by 4, and so on.

Web Mercator is the projection everyone uses for this. It stretches the map so the world comes out as a square with north always up, which is why Greenland looks the size of Africa on a web map. It gives zoom level z a grid of 2^z by 2^z tiles, each 256 by 256 pixels.

So the tile count at level z is 2^z x 2^z = 4^z. Everything in this subsection follows from that expression.

The block below counts the whole pyramid. Note the third line: a single zoom level holds three quarters of every tile in the pyramid.

tiles at zoom z            4^z
tiles at zoom 0-20         (4^21 - 1) / 3           =  1,466,015,503,701
zoom 20 alone              4^20                     =  1,099,511,627,776
zoom 20 share              1,099,511,627,776 / 1,466,015,503,701   =  0.75
zoom 19 and 20 share       0.75 + 0.75 / 4          =  0.9375

Where the second line comes from: adding up 4^0 + 4^1 + ... + 4^20 is a geometric series, and the closed form for 1 + 4 + 16 + ... up to 4^n is (4^(n+1) - 1) / 3. With n = 20 that is (4^21 - 1) / 3 = 1,466,015,503,701 tiles. The formula matters less than the fact that the sum is dominated by its last term.

Why 3/4 and not something messier: if the bottom level holds T tiles, the level above holds T/4, the one above that T/16, and the whole stack above the bottom sums to about T/3. So the bottom level is T / (T + T/3) = 3/4 of everything. Add the level above it and you get 0.75 + 0.75/4 = 0.9375, which is 15/16.

Each level down holds exactly four times as many tiles as the level above, so the bottom level alone is 3/4 of the pyramid and the bottom two are 15/16 of it. Run the same sum for zoom 0 through 10 and you get (4^11 - 1) / 3 = 1,398,101 tiles, which is 0.0001% of the total.

That is the first finding, and it is why nobody bothers optimizing the top of the pyramid: the cost of a tile scheme is entirely decided by where you stop at the bottom.

7.2 What one tile covers on the ground

This block converts zoom levels into metres, using the 40,000,000 m equatorial circumference from ch 17. It tells you what detail each level can actually show.

tile width at zoom z, m    40,000,000 / 2^z
zoom 14                    40,000,000 / 16,384       =  2,441
zoom 20                    40,000,000 / 1,048,576    =  38.1
metres per pixel at 20     38.1 / 256                =  0.149

Reading it: the world is 40,000,000 m across, and zoom z divides that width into 2^z columns, so one tile is 40,000,000 / 2^z metres wide. At zoom 14 a tile is a 2.4 km square — a neighbourhood. At zoom 20 it is a 38 m square, and since the tile is 256 pixels across, one pixel is 38.1 / 256 = 0.149 m of ground. 15 cm per pixel is building-outline and parking-space detail. That is what the bottom of the pyramid is buying you, and §7.4 prices it.

One identity is worth stating, because it saves designing the same thing twice. A geohash is a scheme that turns a latitude/longitude pair into a short string by repeatedly halving the world and recording which half the point fell in, so that nearby points share a prefix. A zoom-z tile column is exactly a geohash cell with z longitude bits (Bits per character and where the cell sizes come from).

Tiles and geohash cells are the same subdivision wearing different clothes. That is why one cell identifier can both key the tile cache and shard the map matcher.

7.3 Pricing the obvious design: pre-rendered pictures

Now price the implementation many reach for first, in which every tile is a finished picture drawn ahead of time. A raster tile is exactly that: a small compressed image with pixels already baked in.

raster bytes/tile          10,000
full pyramid               1,466,015,503,701 x 10,000  =  14,660,155,037,010,000  B  =  14.7 PB

Fourteen petabytes is far too much, for a fixable reason: most of those tiles are open ocean with nothing on them. So restrict the count to settled land, which ch 17 puts at 15,000,000 km^2 of the planet’s 510,000,000 km^2 surface.

settled fraction           15,000,000 / 510,000,000  =  0.0294
tiles worth rendering      1,466,015,503,701 x 0.0294  =  43,100,855,809
bytes                      43,100,855,809 x 10,000   =  431,008,558,090,000  B  =  431 TB

Dropping the empty ocean cuts 14.7 PB to 431 TB — a 34x saving for one multiplication. But 93.75% of what is left is still the two bottom zoom levels, which exist only to show building outlines.

7.4 The fix: ship geometry, not pixels

The fix is vector tiles. Instead of a finished picture, ship the geometry itself — the coordinates of the roads, the outlines of the parks, the positions of the labels — once at a coarse zoom level, and let the client draw every finer zoom by scaling that geometry on the device.

Stop the pyramid at zoom 14 and price it the same way:

vector pyramid, zoom 0-14  (4^15 - 1) / 3             =  357,913,941
worth rendering            357,913,941 x 0.0294       =  10,522,670
bytes/tile                 50,000
total                      10,522,670 x 50,000        =  526,133,500,000  B  =  526 GB
reduction                  431,008,558,090,000 / 526,133,500,000   =  819

Eight hundred and nineteen times smaller, because six zoom levels stop existing.

Check that factor of 819 by decomposing it, since an interviewer will push on it. A vector tile is bigger than a raster tile: 50,000 B against 10,000 B, so 5x worse per tile. But there are far fewer of them: 1,466,015,503,701 / 357,913,941 = 4,096 times fewer, which is 4^6, because you deleted six zoom levels and each level is 4x the one above. The net is 4,096 / 5 = 819. The win is entirely the deleted levels; the format costs a factor of 5.

Three further wins come free:

• A styling change needs no re-render at all, because the colours are applied on the device rather than baked into the stored image.
• Labels rotate with the device instead of being stored sideways.
• The client can zoom smoothly instead of snapping between pre-rendered levels.

What you give up is client work. The device now spends its own processor time and battery rasterizing (turning geometry into pixels), so the design takes a hard dependency on a client capable of doing it. That dependency is listed as load-bearing in The assumption ledger.

Raster tiles therefore stay in the system for two cases: the long tail of old devices, and satellite imagery, which is photography rather than geometry and cannot be expressed as vectors.

8. Deep dive 2: the graph, and why nobody runs Dijkstra

The routing design rests on two facts: the world road network is small enough to fit in one machine’s memory, and searching it live is four orders of magnitude too slow. The first is good news; the second closes off the obvious answer.

8.1 How big the graph actually is

Turning road kilometres into bytes of RAM produces the number that removes distributed shortest path from consideration.

Model the road network as a graph: junctions are nodes, and each road segment travelled in one direction is a directed edge. Start from the total length of paved road on Earth and a typical distance between junctions.

world road length, km          64,000,000
mean segment length, km        0.25
undirected segments            64,000,000 / 0.25      =  256,000,000
directed edges                 256,000,000 x 2        =  512,000,000
mean node degree               2.5
nodes                          256,000,000 x 2 / 2.5  =  204,800,000

Two lines in that block need explanation.

Why segments times 2. Each undirected road segment becomes two directed edges, one for each way you can drive it. 256 million streets, 512 million directed edges.

Why the node count divides by degree. A node’s degree is how many road ends meet at it: a plain four-way crossroads has degree 4, a dead end has degree 1, and 2.5 is a reasonable planet-wide average. Counting road ends: 256,000,000 segments each have 2 ends, so 256,000,000 x 2 = 512,000,000 road ends exist. Each junction consumes 2.5 of them on average, so there are 512,000,000 / 2.5 = 204,800,000 junctions. 205 million nodes.

Now size that in memory. Store the nodes and edges as two flat arrays rather than as objects with pointers, so that a node’s identifier is simply its position in the array and costs zero bytes to store. Each node records where its own edges start in the edge array, and the edges of consecutive nodes sit next to each other.

node    lat, lng 8 B + first-edge index 4 B + attributes 8 B   =  20 B
edge    target index 4 B + length 4 B + time 4 B               =  12 B

nodes   204,800,000 x 20        =  4,096,000,000  B
edges   512,000,000 x 12        =  6,144,000,000  B
                                   -------------
total                              10,240,000,000  B  =  10.2 GB

Every road on Earth is 10.2 gigabytes and fits in the RAM of one ordinary server. A commodity box today has 128 GB, so this leaves ample headroom.

Establish this early in an interview, because it removes distributed shortest path from consideration, and distributed shortest path is hard for a specific reason.

A shortest-path search grows outward from the origin one ring at a time. That advancing boundary is the frontier, and each ring can only be computed once the previous ring is finished. The algorithm is inherently sequential and cannot be split across machines the way a batch job can.

Split the graph across machines anyway and every frontier step that crosses a machine boundary becomes a network round trip at 500 microseconds (ch 02). Compare that with the 100 ns memory reference it replaced: 0.0005 / 0.0000001 = 5,000 times slower, on the most frequent step.

One more figure is needed before pricing a search: how many nodes sit in a square kilometre. The cost of a search depends on the area it covers, and this converts area into nodes. Divide the node count by the settled-land area used in Deep dive 1 the tile pyramid and why the top is free:

nodes per km^2                 204,800,000 / 15,000,000   =  13.65

8.2 What a search costs

Pricing one live shortest-path query, and the fleet it implies at peak, gives the rest of the chapter a number to reduce.

How much of the map Dijkstra has to touch

Dijkstra’s algorithm explores outward from the origin in order of increasing cost. It settles a node (finalizes the best-known distance to it) and then moves to the next cheapest. It cannot stop until it settles the destination, which means it has already settled every node cheaper to reach than the destination.

With a distance-like cost, “everything closer than the destination” is a disc centred on the origin whose radius is the length of the route. The destination sits on the rim. Everything inside was settled on the way.

So the work is proportional to the area of that disc, which is why §8.1 computed nodes per km^2.

Take a 1,000 km straight-line trip. Roads do not run straight, so multiply by the usual 1.2 detour factor (the ratio of driving distance to straight-line distance), giving a 1,200 km route and therefore a disc of radius 1,200 km:

disc area, km^2                3.1416 x 1,200 x 1,200     =  4,523,904
nodes settled                  13.65 x 4,523,904          =  61,751,290

That is pi r^2 with r = 1,200 km, then multiplied by the 13.65 nodes per km^2 from §8.1. A single long route makes Dijkstra settle 61.8 million nodes — 30% of the entire planet’s road network.

Turning nodes settled into seconds

Each settled node costs one heap pop — pulling the cheapest unvisited node off a priority queue — plus about 2.5 edge relaxations, one per outgoing road. Relaxing an edge means checking whether going through this node reaches the neighbour more cheaply than the route already known.

Every one of those operations touches memory at an unpredictable address, because the next node to visit has nothing to do with where the last one sat in the array. So each costs a random memory reference at 100 ns (ch 02) rather than a cheap sequential read. Round the whole settle — pop plus relaxations plus bookkeeping — to 500 ns.

query time                     61,751,290 x 0.0000005     =  30.9   s

0.0000005 s is 500 ns written in seconds. Thirty-one seconds on one processor core, for one route.

Now apply the peak demand derived in Back of the envelope of 40,510 route requests per second. If each request needs 30.9 core-seconds and 40,510 of them arrive every second, you need 30.9 x 40,510 core-seconds of work per second, meaning that many cores running flat out.

core-seconds per second        30.9 x 40,510              =  1,251,759
boxes at 64 cores              1,251,759 / 64             =  19,559

Nineteen and a half thousand machines to serve routes, and the p99 would still be half a minute. That number rules out the “just run Dijkstra” answer.

A* narrows the region but cannot save it

The standard improvement is A* (pronounced “A star”), which is Dijkstra’s algorithm plus a heuristic: an optimistic guess of the remaining distance from each node to the destination. Adding that guess to the known cost-so-far biases the search toward the goal instead of expanding evenly in all directions.

Use straight-line distance as the guess. Then A* settles a node n only if dist(origin, n) + straightline(n, destination) is no more than the final route length of 1,200 km.

That condition has a name in geometry. The set of points whose distances to two fixed points sum to a constant is an ellipse, with those two points as its foci. So A*‘s settled region is an ellipse with the origin and destination as foci, and a “sum of distances” of 1,200 km — instead of Dijkstra’s disc.

Two standard ellipse facts give you its size. The sum of distances equals 2a, where a is the semi-major axis, so a = 1,200 / 2 = 600 km. The distance between the two foci equals 2c, and the foci here are the origin and destination, 1,000 km apart in a straight line, so c = 1,000 / 2 = 500 km. The semi-minor axis is then b = sqrt(a^2 - c^2), and the area is pi a b.

semi-major     a       1,200 / 2                          =  600
half focal sep c       1,000 / 2                          =  500
semi-minor     b       sqrt(600^2 - 500^2)                =  331.7
ellipse area, km^2     3.1416 x 600 x 331.7               =  625,197
speedup                4,523,904 / 625,197                =  7.24
nodes settled          13.65 x 625,197                    =  8,533,939
query time             8,533,939 x 0.0000005              =  4.27   s

Substituting: 600^2 - 500^2 = 360,000 - 250,000 = 110,000, and sqrt(110,000) = 331.7 km. The ellipse is 1,200 km long and 663 km across at its waist — a fat cigar, not a thin corridor.

A* is a real 7.2x speedup and still takes 4.3 seconds, roughly 20x over a 200 ms budget.

The 7.2 comes from the shape of the search region, which is fixed by the detour factor, not by the implementation. Better code does not move it.

Neither does a better heuristic. A heuristic is admissible when it never overestimates the remaining cost to the destination. Admissibility is the guarantee: an admissible heuristic biases the search toward the goal while still provably returning the true shortest path, and an inadmissible one returns a route that is merely plausible.

Straight-line distance is the largest admissible guess available here, because nothing can be closer than the straight line. A larger guess would overestimate and break correctness. So it is already the best heuristic available, A* cannot shrink the region below that ellipse, and no tuning rescues the approach.

The only way out is to not search the graph at all.

9. Deep dive 3: contraction hierarchies, and what preprocessing buys

Doing work ahead of time instead of at query time buys the largest single win in the chapter, a 61,800x speedup for about eighteen core-hours of preprocessing, with a catch that Deep dive 4 separating topology from metric has to solve.

9.1 How contraction hierarchies work

Contraction hierarchies (CH) are a three-step idea. Take them one at a time.

Step 1 — rank every node by importance. Importance means roughly “how many shortest paths run through this node”, so a motorway junction outranks a cul-de-sac. The ranking is a total order: every node gets a distinct position.

Step 2 — contract the nodes one at a time, starting from the least important. Contracting a node means removing it from the graph. But you cannot just delete it, or you would lose routes that went through it. So when you remove node v, you look at each pair of its neighbours u and w, and if the path u -> v -> w was the only shortest way from u to w, you add a shortcut edge straight from u to w carrying the combined travel time. No route is lost; the graph just gets fewer nodes and more edges.

Step 3 — query with a bidirectional upward search. A bidirectional search runs two searches at once, one growing from the origin and one growing from the destination, and stops when they meet in the middle. In a contraction hierarchy each of those two searches is only allowed to move upward in the importance ranking — from less important nodes toward more important ones.

Why that is fast: a real journey looks like “leave your street, get on a main road, get on the motorway, come off the motorway, arrive on their street”. The upward-only rule turns that into a short climb from each end. The upward graph is shallow, so the two searches meet after a few hundred steps regardless of how far apart the endpoints are.

9.2 What the preprocessing costs

Contracting one node is not free, because deciding whether a shortcut is needed requires witness searches: small local searches that check whether the neighbour pair u, w already has an equally short path avoiding v. If such a witness path exists, no shortcut is added.

With a mean node degree of 2.5, each node has about 2.5 incoming and 2.5 outgoing neighbours, so there are 2.5 x 2.5 incoming-outgoing pairs to check.

witness searches per node      2.5 x 2.5                  =  6.25
cost of one local search       100 nodes x 0.0000005 s    =  0.00005   s
per-node contraction           6.25 x 0.00005             =  0.0003125 s
whole planet                   204,800,000 x 0.0003125    =  64,000    s
in hours                       64,000 / 3,600             =  17.8

Reading it: a witness search is local, so budget 100 settled nodes at the same 500 ns each, giving 50 microseconds per search. Multiply by 6.25 searches to contract one node, then by 204.8 million nodes, and you get 64,000 core-seconds, about 18 core-hours to preprocess the planet. §10 compares against that 64,000 figure repeatedly.

Those shortcuts are extra edges, so the graph gets bigger. In practice the shortcut set inflates the edge count by roughly 40%:

edges after contraction        512,000,000 x 1.4          =  716,800,000
edge bytes                     716,800,000 x 12           =  8,601,600,000  B
graph plus overlay             4,096,000,000 + 8,601,600,000  =  12,697,600,000  B  =  12.7 GB

Note what happened to the total: the node array is unchanged at 4.096 GB, but the edge array replaced the old 6.14 GB one with an 8.60 GB one. So the artifact is 12.7 GB, up from 10.24 GB. Deep dive 4 separating topology from metric uses a different structure with different memory arithmetic; confusing the two is a common slip, and that section flags it explicitly.

9.3 What a query costs, and the table that ends the argument

The bidirectional upward search settles on the order of 1,000 nodes on a continental road network. That figure is an empirical property of real road hierarchies rather than something derived here, and it is essentially independent of how long the trip is, because both searches climb to the top of the hierarchy and come back down whether the trip is 20 km or 2,000 km.

query time                     1,000 x 0.0000005          =  0.0005  s
speedup over Dijkstra          30.9 / 0.0005              =  61,800
core-seconds per second        40,510 x 0.0005            =  20.3

The table below puts all three approaches on one row each. The column that matters is the last one: it is the same 40,510 peak QPS from Back of the envelope multiplied by each query time, so it is a direct fleet-size comparison.

Eighteen core-hours of preprocessing turns a 19,559-box fleet into 20 cores. That is the trade, and it has the best cost-per-engineering-hour ratio in this book.

9.4 The catch that breaks it

The shortcut set is derived from the edge weights, so it is only valid for the metric it was built against.

A shortcut from u to w exists precisely because the path through some node v was the shortest one. “Shortest” is a statement about the current travel times. Let traffic slow one road down: a path that was not shortest may become shortest, a shortcut that was justified may no longer be, and because the hierarchy was built bottom-up, the invalidation can propagate anywhere in it.

You cannot patch it. Rebuilding is the only sound answer, and rebuilding is the 64,000 core-seconds just priced: 64,000 / 3,600 = 17.8 core-hours.

Traffic changes tens of millions of weights every two minutes. Eighteen core-hours does not fit inside a 120-second window. Squeezing it in would take 64,000 / 120 = 533 cores running continuously (nine 64-core boxes doing nothing but rebuilding) before serving a single query. Deep dive 4 separating topology from metric is the way out.

10. Deep dive 4: separating topology from metric

Almost all of Deep dive 3 contraction hierarchies and what preprocessing buys’s precomputation win can be kept while still refreshing the travel times every two minutes, by splitting the precomputed artifact along its rate of change.

10.1 The idea: precompute the shape, recompute the numbers

Deep dive 3 contraction hierarchies and what preprocessing buys failed because its precomputed structure — which shortcuts exist — depended on the travel times. Change a time, invalidate the structure.

So build a structure whose existence depends only on the topology, and where only the labels on it depend on the metric. Then a traffic update relabels; it does not rebuild.

Here is that structure, in four moves.

Cut the graph into cells. A cell is a contiguous region of the road network holding a few thousand nodes, roughly a chunk of a city. Every node belongs to exactly one cell.

Identify the doorways. A boundary node is a node inside a cell that has an edge leaving the cell. It is a doorway in or out. Any route that passes through a cell must enter and leave through boundary nodes.

Precompute a clique over each cell’s doorways. A clique is an edge from every boundary node to every other boundary node. Label each of those edges with the shortest travel time between that pair through the inside of the cell. So the clique is a summary: “if you enter this cell at doorway 3 and leave at doorway 17, it costs 84 seconds.”

Query across the doorways. A route now hops doorway-to-doorway across this overlay of cliques, skipping the interior roads entirely, and only descends into road-level detail in the two cells holding the origin and destination.

The payoff: which nodes are boundary nodes, and which pairs need a clique edge, is a fact about the shape of the graph. Traffic never changes it. Traffic only changes the numbers written on the clique edges — and recomputing those is a small job confined to one cell at a time.

10.2 How big the overlay is

Sizing the overlay comes down to one question: how many boundary nodes does a cell have?

Cutting a roughly two-dimensional road network into compact cells is the job of a planar partitioner — an algorithm that cuts a map-like graph into balanced regions with as few edges crossing the cuts as possible. The result is cells that look like patches of territory rather than scattered fragments.

For such a patch, the boundary count scales as the square root of the cell size, because a region’s perimeter grows as the square root of its area: double the area and you get about 1.4x the perimeter. The estimate used here is 2 x sqrt(cell size), where the 2 is a shape constant for typical partitioner output. Treat it as an order-of-magnitude estimate, not an exact count.

The block below plugs in a 4,096-node cell. Note the third line: sqrt(4096) = 64, so a cell has 128 doorways.

cell size, nodes               4,096
cells                          204,800,000 / 4,096        =  50,000
boundary nodes per cell        2 x 64                     =  128
clique edges per cell          128 x 127                  =  16,256
overlay edges                  50,000 x 16,256            =  812,800,000
overlay bytes                  812,800,000 x 12           =  9,753,600,000  B  =  9.8 GB
graph + cell overlay           10,240,000,000 + 9,753,600,000  =  19,993,600,000  B  =  20.0 GB

Walking those lines: 204.8 million nodes divided into cells of 4,096 gives 50,000 cells. Each cell has 128 doorways, and a clique over 128 nodes has 128 x 127 = 16,256 directed edges — every doorway to every other doorway, which is why it is 127 and not 128. Multiply by 50,000 cells for 812.8 million overlay edges, and by 12 B each (the same edge record as the road graph) for 9.75 GB.

The memory trap: 20.0 GB, not 12.7 GB

That last line is the number a route box actually holds, and it is not the 12.7 GB of Deep dive 3 contraction hierarchies and what preprocessing buys.

The difference is replaces versus sits on top of.

A contraction hierarchy replaces the edge array with a larger one — the original edges plus shortcuts, all in one structure — so its total is nodes + inflated edges = 4.10 + 8.60 = 12.7 GB, and the old edge array is gone.

This cell overlay sits on top of the untouched graph. A query hops doorway-to-doorway across the cliques, but it still has to descend into road-level detail inside the two endpoint cells, and it cannot do that if you threw the roads away. So the full 10.24 GB stays resident alongside the 9.75 GB of clique edges: 10.24 + 9.75 = 20.0 GB.

Quoting 12.7 GB for this design quotes the memory footprint of the design the chapter rejects, understating the real one by 57% (20.0 / 12.7 = 1.57).

10.3 Customization: re-pricing the overlay against new traffic

Customization is the name for recomputing the numbers on the overlay edges against a new metric. It is cheap for one reason: it never leaves a cell.

The procedure is one bounded Dijkstra search per boundary node, restricted to the 4,096 nodes inside that boundary node’s own cell. That search produces the shortest interior time from that doorway to every other doorway — which is exactly one row of the cell’s clique.

Nothing outside the cell is read, so the 50,000 cells are independent and can run on 50,000 different cores if you have them.

per cell                       128 x 4,096 x 0.0000005    =  0.262   s
all cells                      50,000 x 0.262             =  13,100  s
in hours                       13,100 / 3,600             =  3.64
on 64 cores                    13,100 / 64                =  205     s

Substituting: 128 searches (one per doorway) x 4,096 nodes each x 500 ns per settled node = 0.262 core-seconds per cell. Across 50,000 cells that is 13,100 core-seconds, or 3.64 core-hours. Spread over one 64-core box, 13,100 / 64 = 205 seconds of wall clock.

205 seconds is still too slow for a 120-second refresh window. But the calculation assumed every cell needs re-pricing. Most of the planet’s traffic did not change in the last two minutes, and a cell whose speeds did not move produces the identical clique, so re-running it is wasted work.

cells with a material change   5 %
work                           0.05 x 13,100              =  655     s
on 64 cores                    655 / 64                   =  10.2    s

10.2 seconds of wall clock against a 120-second window: 120 / 10.2 = 11.8, so it fits with better than a 10x margin. The 5% is an assumption, not a measurement, and The assumption ledger files it as something to ask about rather than something the design guarantees.

10.4 Compare like with like

Now set that against redoing the contraction hierarchy from scratch, which Deep dive 3 contraction hierarchies and what preprocessing buys priced at 64,000 core-seconds.

Compare core-seconds against core-seconds, or wall clock against wall clock on the same box — never one against the other. A wall-clock figure set beside a core-hours figure is two different quantities, and the only reason such a comparison ever looks right in this section is that both sides happen to divide by the same 64 cores.

The block below puts all three costs in the same unit — core-seconds — and then splits the headline win into its two parts. The last line converts to wall clock so you can see the same comparison the other way.

full customization             13,100 core-s
incremental at 5%              655 core-s
CH rebuild                     64,000 core-s

ratio, structure alone         64,000 / 13,100           =  4.9
ratio, incremental             64,000 / 655              =  97.7
the difference                 97.7 / 4.9                =  20      ( = 1 / 0.05 )

same comparison in wall clock on 64 cores:  10.2 s against 1,000 s

655 core-seconds to re-price the planet against new traffic, against 64,000 core-seconds to redo a contraction hierarchy: 97.7x. In wall clock on the same 64-core box that is 10.2 s against 64,000 / 64 = 1,000 s.

Split that 97.7x into its two parts, which have different standing.

• 4.9x is the two-phase structure itself — full customization against a full rebuild. That factor is a property of the design and holds unconditionally.
• 20x is entirely the assumption that only 5% of cells see a material change in a window. That is an Ask it in The assumption ledger, not something the architecture guarantees. Note that 20 = 1 / 0.05 exactly: this half of the win is the incrementality fraction inverted.

If the interviewer disputes the 5%, the argument still holds. At 50% incrementality the work is 0.5 x 13,100 = 6,550 core-seconds, so the win drops to 64,000 / 6,550 = 9.8x, and a 9.8x cheaper update every two minutes still makes the two-phase split the right choice.

The division of labour is then: the topology preprocessing runs when a road is built. The customization runs every two minutes.

10.5 What the split costs you

The overlay query is slower than a pure contraction-hierarchy query. A CH query follows a chain of shortcuts; an overlay query has to walk a clique at each cell it crosses, checking every doorway against every doorway. Budget a few milliseconds instead of 0.5 ms, roughly 10x worse.

Both ends of that are affordable:

• Against a 200 ms p99 target, a few milliseconds is negligible: 5 ms is 2.5% of the budget.
• Against 40,510 queries per second, 40,510 x 0.005 = 203 cores, so a few hundred cores rather than twenty. Both are small next to the 19,559 boxes a live search needed.

You trade a 10x slower query for a 97.7x cheaper update. Traffic changing every two minutes makes that the right side of the trade.

11. Deep dive 5: ETA is a prediction, not a graph traversal

The graph gives you a path. It cannot give you an arrival time. ETA accuracy is the metric users actually judge, and it is the one thing in this chapter a shortest-path algorithm cannot produce.

Adding up the travel times of the edges along the path fails for three separate reasons.

• Turn and intersection costs are not on edges. A left turn across oncoming traffic costs 20-40 s, and that cost belongs to the junction, not to either road segment meeting there.
• Speeds are conditional. The same segment has a completely different distribution of travel times at 08:00 Tuesday and 22:00 Sunday. The historical profile — the recorded distribution of past traversals of this segment at this time of week — carries more information than a live probe reading when live coverage is thin, and How little of the road network has live data shows that at most 1.2% of segments have live data at any moment, and that 1.2% is an optimistic ceiling.
• The error is not symmetric. Arriving 5 minutes early and arriving 5 minutes late are not equally bad for a user. That means the loss function — the formula the model is scored against — must punish lateness harder than earliness, and once it does, the best single number to report is no longer the average outcome but something above it.

Frame it, do not build it here. A system design round is not the place to design a model; it is the place to identify which problem you are holding and where it goes. ml/01 is the framework, and the four things it makes you state map onto this problem.

The table is that framework’s form, filled in: the left column is what it asks, the right column the answer for the ETA model.

Two terms from that last row, since they decide whether the model works in production. A feature store is the shared service that computes and serves the model’s inputs, so that 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 a batch job and served features computed a slightly different way at request time, and its accuracy quietly degrades with nothing failing.

The consistency trap

One trap survives all the way to production: the metric the router optimizes and the model that reports the ETA must be the same function.

The failure: routing uses the customized edge times from Deep dive 4 separating topology from metric. The ETA comes from a separately trained model. Both are reasonable in isolation. But the route you returned is the fastest route under the routing metric, while the number you displayed came from a different function, so the route is not the fastest one under the model that just quoted the time.

Nothing fails. No test catches it. The router is correct against its own metric, the model is accurate against its own labels, and the product is quietly wrong.

Two resolutions are acceptable:

1. The model produces the edge metric. Customization then runs on model output, and there is only one function.
2. The ETA is the metric’s own path cost plus a learned correction. The model adds turn costs and systematic bias on top; it does not re-estimate the whole thing.

What is not acceptable is two independent estimates of the same quantity.

12. Deep dive 6: traffic ingestion, and the loop that eats itself

Live traffic data is far scarcer than the raw ingest rate suggests, and that scarcity decides what the traffic system can be built on. A second problem sits on top: a router that reacts to traffic naively makes traffic worse, and fixing that takes two specific mechanisms.

12.1 How little of the road network has live data

The rate of probe data and its information content are different quantities, and the gap between them is what decides that the historical profile — not the live feed — is the primary signal.

Fixes are not observations

The naive count says probes are plentiful: 4,166,667 position fixes a second.

But consecutive fixes from the same vehicle on the same road segment carry no additional information. A car sitting on one 250 m segment for eight seconds sends eight fixes; the second through eighth tell you nothing the first did not. What you learn is “one vehicle crossed this segment at this speed” — one fact, not eight.

So the quantity that matters is distinct vehicle-segment observations, not fixes. Count those instead.

Everything below uses the average population of 4,166,667 concurrent navigators from Back of the envelope, not the peak. Coverage describes the typical moment, whereas the peak describes the busiest second the ingest tier has to survive. They are different questions.

vehicle speed, m/s             15
distance per 2-minute window   15 x 120                   =  1,800   m
concurrent navigators          4,166,667
segments crossed               1,800 / 250                =  7.2
observations per window        4,166,667 x 7.2            =  30,000,002
directed edges                 512,000,000
coverage                       30,000,000 / 512,000,000   =  0.0586

Step by step. A car doing 15 m/s (54 km/h) covers 15 x 120 = 1,800 m in one 2-minute aggregation window. Segments average 250 m (How big the graph actually is used 0.25 km), so it crosses 1,800 / 250 = 7.2 of them. With 4,166,667 cars each crossing 7.2 segments, one window collects about 30 million vehicle-segment observations. Against 512 million directed edges, that is 30,000,000 / 512,000,000 = 5.86%.

The five-vehicle threshold, and why 1.2% is a ceiling

A single observation is not a speed estimate. One car stopped at a red light does not mean the road is jammed. So require five distinct vehicles on a segment before trusting a live speed for it.

segments with 5 or more, upper bound   30,000,000 / 5 / 512,000,000   =  0.0117

Read that 1.2% as a ceiling, not an expectation, because it and the line above it assume opposite things.

The 5.86% figure divides observations by edges. That is only a coverage number if every observation lands on a distinct segment — 30 million observations touching 30 million different roads.

Dividing by five assumes the exact opposite: that observations arrive in tidy groups of exactly five, all on the same segment, so that 30 million observations cover 6 million roads five times each.

Both cannot be true at once. obs / 5 / edges is the maximum achievable under perfect concentration — the best case, where every group of five lands together and none is wasted.

It is worth knowing how far the opposite model sits from it. Suppose observations were spread uniformly and independently across edges. Then the mean number per edge is 30,000,000 / 512,000,000 = 0.0586. The Poisson distribution describes how many independent events land in one bucket when the average is known, and it puts the chance of a given edge collecting five or more at about 5.5e-9 — roughly six in a billion. That is six orders of magnitude below 1.2%, so: effectively zero.

Reality is neither extreme. Vehicles concentrate on the roads that carry traffic, which is where you want the coverage, so the true figure sits between the two bounds and much closer to the ceiling than to the uniform model. The accurate statement is “at most 1.2%, and structurally impossible to be much more.”

The corollary that decides the design

At most 1.2% of the road network has a live speed at any moment, and raising the ping frequency does not change that number. The information rate is set by how many distinct vehicles are on the road, not by how often each one reports.

That corollary holds at either end of the range. Whether real coverage is 1.2% or a thousand times less, more fixes from the same cars add no distinct vehicles and therefore no information.

Two design conclusions follow.

The historical profile is the primary signal. Live probes are a correction applied to the small slice of segments where they exist, not the other way round. If you build the ETA around live data, 98.8% of the network has nothing to build on.

Batch aggressively at the client, which is where Back of the envelope’s 10-second upload interval comes from, and aggregate near the user before the data reaches a central pipeline. Since the extra fixes carry no information, nothing downstream is made more accurate by carrying the raw stream further than necessary.

12.2 The feedback loop

A router that sees a jam and reroutes everyone around it creates a jam on the detour. This is a common complaint about navigation apps, and it has an exact model.

The two-route model

Take two routes between the same origin and destination. Each has a travel time that rises as more vehicles use it, the key property here.

Write each as free-flow time + congestion penalty, where x is the number of vehicles per hour on that route:

route A, minutes               10 + x_A / 200
route B, minutes               20 + x_B / 400
demand                         3,000

Read the constants. Route A is the short one: 10 minutes when empty, but it congests fast — every 200 extra vehicles per hour adds a minute. Route B is the long way round: 20 minutes empty, but it takes 400 extra vehicles per hour to add a minute, so it is twice as tolerant of load. Total demand is 3,000 vehicles per hour, and every vehicle takes one route or the other, so x_A + x_B = 3,000.

Where the traffic settles on its own

At equilibrium — the split at which no individual driver could get home faster by switching — both routes take exactly the same time. If one were faster, somebody would move to it, which is the definition of not being settled.

So set the two expressions equal. Write x for x_A, which makes x_B = 3,000 - x:

                               10 + x/200  =  20 + (3,000 - x)/400
multiply through by 400        4,000 + 2x  =  8,000 + 3,000 - x
collect terms                  2x + x      =  8,000 + 3,000 - 4,000
                               3x          =  7,000
x_A                            7,000 / 3                  =  2,333
x_B                            3,000 - 2,333              =  667
equilibrium time               10 + 2,333 / 200           =  21.7  min

Check it on the other route: 20 + 667/400 = 21.7 min. Both sides agree, so 2,333 on the short route and 667 on the long one is the split, and everyone takes 21.7 minutes.

What a greedy router does instead

A greedy router always recommends whichever route is currently fastest. Its view of traffic lags by one 2-minute aggregation window, so it is acting on the previous state of the world.

Follow the loop. Window 1: B looks faster, so the router sends everybody to B. That makes B the slow one — but the router will not know for two minutes. Window 2: A now looks faster, so the router sends everybody to A. And so on, flipping forever.

Price both extremes, and average them because the system spends half its time in each:

everybody on A                 10 + 3,000 / 200           =  25.0
everybody on B                 20 + 3,000 / 400           =  27.5
mean under oscillation         25.0 / 2 + 27.5 / 2        =  26.25

The table below lines up the three policies. Compare the middle row against the top: the router is losing to doing nothing.

The percentages are each row against the 21.7-minute equilibrium: 25.0 / 21.67 = 1.154, so 15.4% worse, and 26.25 / 21.67 = 1.212, so 21.2% worse.

A traffic-aware router with a control lag and no damping is worse than no router at all: 26.25 minutes against 25.0. The fix has to be structural rather than a tuning exercise.

Fix 1: split the demand instead of switching it

Return k near-optimal routes — this is why /v1/route in Api sketch returns a list rather than one answer — and assign each request one of them at random, with probability proportional to how much spare capacity that route has.

The mechanism is that different users get different answers. Nobody is following a single global recommendation, so there is nothing for the population to stampede toward, and the split lands near equilibrium by construction rather than by convergence.

Fix 2: damp the update

Rather than moving instantly to whatever split the latest traffic implies, move only part of the way each window.

Let p be the share of traffic sent to the alternative route, p_target the share the latest traffic reading implies, and alpha the step size — how much of the gap you close per window.

p_next  =  (1 - alpha) x p_now  +  alpha x p_target

Read it as a weighted average: alpha = 1 means jump straight to the target (that is the greedy router again), and alpha = 0 means never move at all.

Each window multiplies the remaining error by (1 - alpha), so after n windows the residual error is (1 - alpha)^n. To find how many windows it takes to get within 5% at alpha = 0.3, solve 0.7^n = 0.05 by taking logs of both sides:

windows to reach 5% error      log 0.05 / log 0.7         =  8.4    ->  9
wall clock at 2 min/window     9 x 2                      =  18     min

log 0.05 = -3.00 and log 0.7 = -0.357, so n = 8.4, rounded up to 9 whole windows. At two minutes per window that is 18 minutes.

Eighteen minutes to converge is longer than most trips, so damping is not sufficient on its own; the split does the real work. Damping only keeps the oscillation from being violent while it happens.

The third mechanism: do not optimize for the system optimum

The equilibrium derived above is the user equilibrium: no individual driver can improve their own time by switching routes.

A system-optimal assignment is different: the split that minimizes total driving time summed across everybody. It is faster in aggregate, but achieving it requires deliberately routing some individuals onto slower paths for the benefit of strangers.

That is a product nobody keeps installed. It is also an ethics question rather than an engineering one, and saying so is a better answer than pretending it is a solved optimization.

Route each user selfishly, and manage the aggregate only by splitting among routes that are genuinely near-optimal for that user.

13. Bottlenecks and scaling

What runs out first as the system grows has an answer unusual for this track: nothing here is fixed by partitioning the data.

Two terms first.

To shard (equivalently, to partition) is to split one dataset across several machines that each hold a disjoint slice. No machine holds all of it, and a query may have to visit several.

To replicate is the opposite: every machine holds the same complete copy. Any machine can answer any query, and adding machines buys throughput rather than capacity.

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.

QPS is queries per second, the request rate the fleet must absorb.

14. Failure modes

The pattern in the right-hand column: every mitigation degrades to a worse answer rather than to no answer. Stale traffic still routes. Missing live speeds fall back to the historical profile. Nothing here returns an error to the user, because a slightly wrong route beats a spinner.

15. Alternatives rejected

Each design below was considered and priced out, so every rejection has a number attached rather than a preference. This table turns “I wouldn’t do that” into an argument.

16. Interviewer pushback

These six challenges are the ones this design attracts. Each answer is in italics, the way you would say it out loud: numbers first, conclusion second.

“Walk me through why you would not just run Dijkstra.”

I would price it first. The world graph is about 205 million nodes over 15 million km^2 of settled land, so 13.65 nodes per km^2. A 1,200 km route makes Dijkstra settle a disc of that radius — 4.5 million km^2, so 61.8 million nodes — and at 500 ns per settled node that is 30.9 seconds. At my 40,510 peak QPS that is 19,559 machines. A narrows the disc to an ellipse and buys 7.2x, which is real and still leaves 4.3 seconds. The gap is four orders of magnitude, so the answer has to be precomputation, not a better search.*

“Why not contraction hierarchies, then? They are the standard answer.”

Because the shortcut set is a function of the edge weights, and traffic rewrites the weights every two minutes. Preprocessing the planet is about 18 core-hours, which does not fit in a two-minute window. So I separate the two: a metric-independent partition that changes when roads change, and a per-cell boundary clique that I re-price for the new metric. Full customization is 13,100 core-seconds, about 205 seconds on one 64-core box, and only about 5% of cells have a material traffic change in any window, so the real cost is 655 core-seconds — 10.2 seconds on the same box. Against 64,000 core-seconds for a rebuild that is 97.7x, and I would split it: 4.9x is the two-phase structure itself and the other 20x is the 5% incrementality assumption, which is a number I would want to check rather than a property of the design. Even at 50% incrementality it is 9.8x, so the split is still obviously right.

“How much of the road network actually has live traffic?”

At most 1.2%, and the derivation is the useful part — including the bit that makes it a bound rather than an estimate. With 4.2 million concurrent navigators covering 7.2 segments each per two-minute window, that is 30 million segment observations against 512 million directed edges — 30,000,000 / 512,000,000 = 5.9% touched once. Dividing that by five for a five-vehicle threshold gives 1.2%, but notice the two lines assume opposite things: the first only makes sense if every observation lands on a different segment, the second only if they arrive in groups of exactly five on the same one. So 1.2% is the maximum achievable under perfect concentration. Spread them uniformly instead and the Poisson chance of five on one edge is about 5.5e-9. The truth is in between and near the top, because traffic really does concentrate. The corollary survives at either end, which is why I would still say it: raising the ping rate buys nothing, because the information is carried by distinct vehicles, not by fixes. So the historical profile is the primary signal and live probes are a correction on a small slice.

“Your router reroutes everyone around a jam. What happens?”

You create the jam you were avoiding, and it is measurably worse than doing nothing. With two routes and 3,000 vehicles an hour, the equilibrium split is 2,333 and 667 at 21.7 minutes each. A greedy router with one window of lag oscillates between sending everyone to A at 25 minutes and everyone to B at 27.5, averaging 26.25 — worse than the 25 you would get with no router at all. The fix is to split rather than switch: return several near-optimal routes and assign them probabilistically, with a damped update. Damping alone takes about nine windows, so eighteen minutes, to settle — longer than most trips — which is why the split is doing the real work.

“Where does the ETA come from?”

Not from the graph. The graph gives a path; the arrival time is a prediction problem, with the labels coming free from probe traversal times. I would frame it with the ml framework rather than design it here: the two-stage pattern maps exactly, with the router as candidate generation and the model as the scorer. The one thing I would insist on is that the ETA and the routing metric are the same function. If they are separately estimated, the route I return is not the fastest under the model that just quoted the time, and nothing in the test suite will notice.

“Why vector tiles?”

Because the pyramid is 4^z, so the bottom two zoom levels are exactly 15/16 of every tile you will ever store. A raster pyramid to zoom 20 restricted to settled land is 431 TB. Stopping at zoom 14 and shipping geometry is 526 GB, 819x smaller, because the client synthesizes the six levels below. It also decouples styling from storage, so a design change is a client release rather than a re-render of the planet.

17. The assumption ledger

Every design is a set of assumptions with a diagram attached, and the diagram is only correct relative to them. The ledger below collects everything this chapter has leaned on, so you can state the design’s foundations quickly and say what replaces the design when each one fails.

Sort each assumption into one of three bins.

• State it — you are free to pick, and being wrong costs a re-derivation, nothing more.
• Ask it — the answer moves a policy or a threshold, and it is worth an interviewer’s time.
• Load-bearing — if it is wrong the design is not suboptimal, it is invalid. A box appears or disappears, rather than the count inside a box changing.

The one-line test, from ch 03: move the assumption an order of magnitude in each direction and ask whether the set of boxes changes or only the number of machines inside them.

The table is sorted with the load-bearing assumptions first. The last column is the alternative design you would be forced into, which is what shows you understand why the assumption matters.

Two numbers that cannot sink this design

Both of these look load-bearing and both draw the challenge, so it is worth being able to dismiss them directly.

500 ns per settled node

It is the constant underneath the most quotable number in the chapter, so it invites an argument about cache behaviour and memory latency.

It does not matter, for one reason: it multiplies Dijkstra, A*, contraction hierarchies and customization by the same factor. Every ratio in the chapter is therefore independent of it: the 7.24x that A* buys, the 61,800x that preprocessing buys, and the 97.7x that separating topology from metric buys are all untouched whether memory is ten times faster or ten times slower.

The absolute conclusion survives too. Make memory ten times faster, so 50 ns per settled node, and a live Dijkstra query still takes 61,751,290 x 0.00000005 = 3.09 seconds against a 200 ms budget, 15x over.

The 1,000 km trip used to price the search

It looks like the number the 30.9 s was reverse-engineered from, and “but most trips are short” is the obvious rescue for the “just run Dijkstra” answer. It is not one.

Shrink the trip by a full order of magnitude, to a 100 km straight-line journey — that is a 120 km route after the 1.2 detour factor. Redo the disc:

• Area: 3.1416 x 120 x 120 = 45,239 km^2.
• Nodes settled: 13.65 x 45,239 = 617,513.
• Query time: 617,513 x 0.0000005 = 0.309 seconds.
• Fleet at peak: 0.309 x 40,510 / 64 = 196 boxes.

196 boxes against contraction hierarchies’ twenty cores — still more than two orders of magnitude apart, on a trip a tenth as long.

The assumption cannot move far in the other direction either, because a route ten times longer than 1,200 km is most of the way around the planet. That lets you decline the “but most trips are short” objection in one sentence instead of re-deriving the table.

A summary you can state to an interviewer: “This design rests on four things. One, the topology changes in weeks while the metric changes in minutes, which is what splits the preprocessing in two. Two, traffic must be live within two minutes, which is what rules out contraction hierarchies on their own. Three, the graph is 10.2 GB, which is what makes routing a replication problem instead of a partitioning problem. Four, this router carries enough traffic to move traffic, which is what makes the feedback loop a real failure mode rather than a curiosity. The 500 ns per node that every latency in the chapter is built on is not one of them; it cancels out of every ratio I quoted.”

Cheat sheet

The whole chapter compressed to twelve lines.

Related: 17 — Proximity Service derives the cell scheme the tiles and map matching share; 18 — Nearby Friends owns the location stream this chapter ingests; ml/01 — ML System Design Framework is where the ETA model belongs; 02 — Back-Of-The-Envelope supplies the 100 ns and 500 us that price every search above.