BOOK DEEP READ · System Design Interview Vol 2 · Ch 3
System Design Interview Vol 2 · Ch 3 · Alex Xu & Sahn Lam · 2022
You pull out your phone at an intersection, open the map, and within two seconds the streets fill the screen. Tap navigate and it says "23 minutes, and the freeway saves you 6." This chapter builds that from nothing: where the map comes from, how the route is found, and where that "23 minutes" actually comes from.
A system used by a billion people a day, and most of what it shows you is not computed when you ask. The map on your screen is a pile of small square pictures drawn long ago and parked on a disk — they have nothing to do with who you are or when you opened the app. Exactly one thing genuinely has to be worked out live: how bad the traffic is right now.
Two things that do not fit. First, if the world map were a single image, it would be far too large for any phone to download. Second, all the roads on Earth form one network with hundreds of millions of junctions, and to find a shortest path through it, that network will not fit in one machine's memory. The difficulty is not that the computing is slow. It is that the thing is too big to move.
Cut the map into squares. Slice the world map like a sheet cake and store each square as its own picture. Your screen is only so big, so you only ever need the few squares around you — a few hundred kilobytes — and the millions of other squares are none of your business. Each square is also kept at several levels of detail: looking at a whole province gets you the coarse set (freeways and big cities only), and only when you zoom into a block does the fine set arrive.
Finding a route works the same way: big map first, small map later. It is how people give directions. Work out how to get onto the freeway (that needs detail), drive the freeway all the way to the target city (for that stretch you only need a very coarse map — nobody cares about the side streets you pass), then exit and look at streets again. A machine does exactly this: for that long middle stretch it loads only "the map with nothing but freeways on it", so it never has to haul the whole road network into memory.
Whether it's jammed is something everyone's phones say together. Every phone with the map open reports, anonymously, "here's how fast I'm moving right now." Thousands of those dots, stitched together, are a live traffic picture. Google described this publicly back in 2009, and their own wording was that the more people take part, the better the traffic reports get for everybody.
One line: draw the things that don't change ahead of time and move them to the data centre nearest you; only compute the things that do change. A map barely changes in a year, so it can ship as static pictures for almost nothing. Traffic changes every minute, so it must be computed live — and it is the only part worth that money. The cost deserves saying plainly too: that useful live traffic is paid for with everyone's location data. It is anonymised, which is not the same as free.
A map service = a pile of pre-cut square pictures + a road network layered coarse-to-fine and loaded on demand + a traffic picture everyone contributes to. The hard part was never the algorithm. It is how you cut down something too big to move.
Want the mechanisms, the numbers and the diagrams? → switch to the deep read
What this chapter builds is not "a service that computes shortest paths" but a pipeline that separates the static from the dynamic: map geometry and the road graph are both baked offline into tiles and shipped to a billion people as static files over a CDN, and only traffic and ETA are worth computing live. Hold on to the counter-intuitive line: the engineering in Google Maps is not in Dijkstra, it is in cutting down what doesn't fit and loading it on demand — and the same "tile" idea gets used twice here, once for display and once for routing.
Chapter 3 of Volume 2, right after Ch1 "Proximity Service" and Ch2 "Nearby Friends". All three are geo problems, but the first two only answer "who is near me"; this is the first one that has to draw the map itself and find a path through a road network, which makes it the heaviest of the group. Its real-world counterparts are Google Maps, Apple Maps, and the OpenStreetMap + OSRM open-source stack.
The authors narrow the requirements to three things: location updates, navigation (including ETA), and map rendering. What's hard is not the logic of any one of them — it's that their magnitudes differ by orders of magnitude, so one mechanism serving all three is guaranteed to fail. A few concrete numbers set the difficulty:
4²¹ ≈ 4.4 trillion tiles; at 100KB each that is roughly 440PB, and summing levels 0–21 adds another third (geometric series), approaching 590PB. But most of Earth's surface is ocean, desert and empty land — don't store what nobody looks at and the figure falls back to tens of petabytes. That is the chapter's first judgement call: the storage problem is solved by not storing, not by compressing.What happens if you don't solve this? You get a system that renders on every open and traverses the whole planet on every navigation — neither the cost nor the latency can possibly work.
Start by flattening the sphere with a Mercator projection into one square world image. Level 0 is that whole world as a single tile; each level up halves every side, so level z holds 4ᶻ tiles — the tile pyramid. The client takes its own viewport centre and current zoom and computes the URLs of the tiles it needs itself, then fetches them straight from a CDN. One screen is roughly 6–10 tiles, a few hundred kilobytes of transfer.
There is a design consequence here that's easy to skim past: the render path needs no "tile service" at all. No server logic, no database query — just a pile of content-addressable static files. So when millions of people look at the same city block over and over, the cache hit rate can be enormous, the CDN absorbs practically all the traffic, and the origin only re-bakes a batch when the map data updates (typically on a weekly or monthly cadence). A single "make it static" decision eats the bulk of a billion users' read load.
A raster tile is a picture drawn server-side; the client just blits it. A vector tile carries geometry instead (where this road runs, what class it is, what it's called) and the client draws it live. Vector wins because one payload covers continuous zoom and rotation — lines and labels stay crisp as you pinch, with no re-download for every intermediate scale — it's smaller on the wire, and it incidentally solves night mode and multilingual labels. The cost is that the client needs to be able to draw (mobile GPUs are fine) and pays one heavier parse-and-render on first paint. Google Maps publicly moved to vector rendering with version 5.0 on Android in December 2010, and began caching frequently visited areas so the app stayed usable on a weak connection.
The test in one line: whether you need continuous zoom decides which end renders.
Treat the roads as a graph — junctions as nodes, segments as edges, travel time as weight — and navigation is a shortest-path search. But running Dijkstra directly over a continental network does not stall on algorithmic complexity; it stalls because the graph does not fit in memory and should not be there in the first place.
So the tile idea gets borrowed a second time. An offline pipeline cuts the road graph into routing tiles at several levels: the fine level holds every street, the coarse level keeps only freeways and arterials, and tiles record which other tiles they connect to. The shortest-path service starts in the fine tile around the origin, switches up to coarse tiles once it is far enough from the start, crosses the long middle on the highway layer alone, then drops back to fine tiles near the destination. What gets loaded is therefore proportional to the length of the route, not to the size of the planet. This is exactly the order humans give directions in: streets by your door, one province-level map for the freeway, streets again at the far end.
A* and friends prune directions that clearly point the wrong way, but the order-of-magnitude win comes from hierarchy and preprocessing, not from the heuristic. Industry's more aggressive move is contraction hierarchies (CH): offline, nodes are "contracted" one by one in order of importance and shortcut edges are added, so a query only ever walks upward and a continental route drops to milliseconds — the open-source router OSRM works this way. The price is concrete: the preprocessing is bound to the edge weights. Change a weight (live traffic arrives) and it must be recomputed, which is why live traffic is usually not fed straight into CH but layered on top as a correction, or handled by variants designed for swappable weights.
The client batches its positions (roughly one send per 15 seconds). The location service writes them into a high-write-throughput store like Cassandra and publishes them to Kafka at the same time, where several consumers each take what they need: one aggregates the anonymous speed points on a given road segment into "how fast this stretch is right now" — live traffic; one feeds the ETA model; one drives long-term corrections to the road graph (new roads, a one-way street recorded backwards). Kafka's job here is "write once, derive many ways" — a pattern that recurs throughout the book.
ETA is not distance ÷ speed limit; it is a prediction: how fast this road usually is at this hour, adjusted by what's measured now. The approach Google and DeepMind published in 2020 cuts the network into Supersegments — runs of adjacent road segments that share traffic volume — and predicts travel time with a graph neural network.
One more conclusion that's easy to miss: navigation is a continuing session, not a single request. The client reports throughout, and when the service sees traffic worsening ahead it recomputes and pushes a new route — adaptive rerouting.
The soul of this chapter is pricing each of the three paths by how often it changes: map geometry barely changes → bake it static and push it as close to the edge as possible; the road graph changes slowly → trade offline preprocessing for query latency; traffic changes every minute → it alone deserves live computation.
Table 1 · Map rendering: raster vs vector tiles
| Raster (drawn server-side) | Vector (drawn client-side) | |
|---|---|---|
| What ships | A finished bitmap; the client blits it | Geometry + attributes; the client draws |
| Continuous zoom / rotation | A separate set per scale; intermediate states look blurry | One payload covers zoom and rotation; labels stay crisp |
| Bytes on the wire | Larger, and independent per level | Smaller, reusable across levels |
| Restyling (night mode, languages) | Re-bake the whole tile set | Same geometry, different paint |
| Cost | Storage and origin bandwidth | Client compute and first paint; more complex |
| Pick it when | Clients are weak, or imagery is highly custom (satellite, terrain basemaps) | The mobile default: continuous zoom, thrifty data, offline caching |
Table 2 · Routing: the preprocessing / query / dynamism triangle
| Approach | Offline preprocessing | Query cost | With live traffic | Fits |
|---|---|---|---|---|
| Plain Dijkstra | None | Explodes with graph size; unusable at continental scale | Native — change weights freely | One city, teaching |
| A* heuristic | None | Searches far less than Dijkstra, still degrades with distance | Native | Mid-size graphs with shifting weights |
| Hierarchical routing tiles | Moderate: cut tiles, build levels (re-baked weekly/monthly) | Proportional to route length, bounded memory | Good — weights inside a tile can be refreshed | This chapter: global scale that must track traffic |
| Contraction hierarchies | Heavy: contract the whole graph, add shortcuts | Milliseconds — the fastest | Poor: a weight change invalidates the preprocessing | Static weights, offline / open-source routers (OSRM) |
Table 3 · Location reporting: every second vs batched
| Once per second | Batched every 15s | |
|---|---|---|
| Write QPS (3.5M concurrent navigations) | about 3.5M/s | about 230K/s |
| Phone battery / data | Battery collapses first | Markedly cheaper on both |
| Freshness of traffic | Freshest | At most 15s behind — ample for aggregation |
| Verdict | Traffic is a statistic, not anyone's exact trace, so trading freshness for cost is clearly worth it. What genuinely cannot lag is "off route → replan", and that travels a separate, faster path. | |
In an interview or an architecture review, the valuable thing here is not reciting A*; it is splitting static from dynamic in your first sentence: the bulk of a billion DAU's reads are static tiles and belong pinned to a CDN, while the only things that really spend server money are location writes and traffic/ETA. Say that line first and you are already half right.
The real-world mapping is clear too: Google Maps (tile pyramid + CDN + vector client rendering + crowdsourced traffic), Mapbox (whose vector tile format MVT became the de facto standard), OpenStreetMap + OSRM / Valhalla (open implementations of both the CH and the hierarchical route), and Uber (ETA prediction and dispatch routing).
① One line: a pipeline that separates static from dynamic — map and road graph are baked offline into tiles and shipped via CDN; only traffic and ETA are computed live.
② Requirements narrow to three: location updates, navigation (with ETA), map rendering — magnitudes apart, so each needs its own mechanism.
③ The tile pyramid: 4ᶻ tiles at level z; level 21 is ~4.4 trillion ≈ 440PB, pulled back to tens of PB by not storing what nobody looks at.
④ The client derives tile URLs itself, so no service sits on the render path — just static files on a CDN. That's how the bulk of a billion users' reads disappears.
⑤ Raster vs vector: whether you need continuous zoom and rotation decides which end renders. Mobile picks vector, which also buys restyling and offline.
⑥ Routing's key is not the algorithm but hierarchy plus on-demand loading: the middle runs on the highway layer, so load grows with route length, not planet size.
⑦ CH gets queries to milliseconds at the price of preprocessing bound to edge weights; live traffic needs a correction layer on top.
⑧ Batching reports every 15s takes write QPS from ~3.5M to ~230K, and the bigger win is phone battery; traffic is a statistic, so 15s of lag is harmless.
⑨ Once positions are in Kafka it's "write once, derive many ways": live traffic, ETA model, road-graph corrections each take a feed.
⑩ Navigation is a continuing session, not one request: reporting throughout, recomputed and pushed when traffic worsens; ETA is prediction (Google/DeepMind's Supersegments + graph neural networks).