Google Maps

What the interviewer is asking

"Design Google Maps" packs three problems into one app. The map must pan and zoom smoothly for a hundred million people a day: a question of serving billions of small files. Directions are a graph search over a continent's roads. And the arrival time has to know about the crash two minutes ago.

Below are the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• See the map: pan and zoom anywhere, smoothly.
• Find a place by name. That's the Nearby Places design (an index of places), so one sentence covers it.
• Drive there: a route from A to B with an arrival time that counts live traffic.

Park the rest out loud: bus and train directions (timetables, a different kind of search), walking and cycling (the same search on another graph), street-level photos, and offline maps.

2. Data: tiles, the road graph, live speeds

data    what it holds
tile    zoom, x, y → a 256 × 256 picture (or vector data)
node    id → lat, lng (an intersection)
edge    a, b, length_km, speed_limit, one_way (a road segment)
speed   edge → km/h now (from phones, every minute)

The map is cut into tiles, square pictures named by zoom level and x and y position. The road graph has intersections as nodes and road segments as edges. Live speeds say how fast traffic moves on each segment now. Tiles and roads change when the map is updated; speeds change every minute.

3. The API: two calls

GET /tiles/12/655/1583
→ 200 OK  image/png  (one 256 × 256 tile)
  Cache-Control: public, max-age=604800

GET /route?from=37.7749,-122.4194&to=37.6213,-122.3790
→ 200 OK  {"path": [[37.7749, -122.4194], …], "distance_km": 20, "eta_min": 15}

The phone never asks for "the view on my screen": no two people's views line up, so such pictures could never be reused. It asks for the fixed squares that cover the screen. Everyone looking at downtown San Francisco at zoom 12 gets the same tile, 12/655/1583, so it can be stored once and cached everywhere, and panning fetches only the squares that slide in.

4. The busy path: loading tiles

Ana opens the map and about 20 tiles fill her screen. She pans for 10 seconds, about 5 new tiles a second: 20 + 10 × 5 = 70 tile requests, and not a single route yet. Even a drive with directions keeps loading tiles as the map moves. So the busy path is serving tiles; route requests are the second path that has to stay fast.

5. The numbers

Zoom 0 is one tile showing the whole world, and each zoom level splits every tile into 4, so zoom z has 4^z tiles:

zoom   tiles                             one tile covers (equator)
0      1                                 the whole world
10     4^10 = 1,048,576, about 1 million  about 39 km
18     4^18, about 69 billion             about 150 m

Then the traffic, with the interviewer's numbers and a day rounded to 100,000 seconds (86,400 really):

what              working
tiles a day       100 million people × 10 screens × 20 tiles = 20 billion
tiles a second    20 billion ÷ 100,000 s = 200,000; at busy hours (5×) 1 million
routes a second   100 million a day ÷ 100,000 s = 1,000; at busy hours 5,000
bytes out         1 million tiles × 20 KB = 20 GB a second at the peak
zoom 18 stored    69 billion × 20 KB, about 1.4 PB
all zooms stored  about 92 billion tiles, over 1.8 PB

Tiles outnumber routes 200 to 1. Twenty GB a second is twenty times what one server's network sends, and drawing every tile ahead would mean petabytes of mostly empty ocean.

6. Services: tiles apart from routes

A tile is a file: the same bytes for everyone, served straight from storage like any photo (the Files and Object Storage lesson). A route is work: each request searches the road graph, so the route service keeps the graph in memory and grows with route requests.

Does the graph fit? Say a continent has about 20 million intersections and 50 million road segments of about 40 bytes each: 2 GB, plus 20 million × 16 bytes = 320 MB of positions. Every route server can hold a full copy.

7. Scale: a CDN for tiles

At the peak the tile store would send 20 GB a second from one data center, and a user on another continent would wait about 150 ms a round trip for every tile. Tiles are perfect CDN content (the CDNs lesson): the same file for everyone, changed only when the map is. Put a CDN in front: a nearby edge answers in about 20 ms, and at 95% hits only 50,000 tiles a second, about 1 GB a second, still reach the tile store.

Tiles can carry long cache lifetimes, a week, say. When the map changes, publish new tiles under a new version in their address, so nobody waits for old copies to expire.

8. Deep dive: tiles

Map apps use the Web Mercator projection: a point's position across the world map, x, runs from 0 in the far west to 1 in the far east, and its position down, y, from 0 at the top to 1 at the bottom. Zoom z has 2^z tiles across and as many down, so the tile is the whole part of x × 2^z and y × 2^z. Sydney sits about 0.92 across and 0.60 down:

zoom   across            down             tile
1      0.92 × 2 = 1.84   0.60 × 2 = 1.2   1/1/1, the bottom-right quarter
2      0.92 × 4 = 3.68   0.60 × 4 = 2.4   2/3/2, one of the 4 inside 1/1/1

The phone does this for the corners of its screen and requests every tile in between.

Which tiles to draw ahead? Zooms 0 to 10 are only about 1.4 million tiles in all: draw them everywhere, plus the busy places at high zooms. Most of zoom 18 is ocean, ice or empty land that almost nobody zooms into, so a tile renderer draws such a tile the first time someone asks, saves it in the store, and the CDN caches it. The CDN asks the store first and the renderer only for a tile that isn't there yet (a CDN can try a second origin, or a thin tile server in front of the store makes the same check).

Many apps now send vector tiles: the roads and labels as data the phone draws itself, so labels stay sharp as the map turns and one tile serves every style, night mode included.

9. Deep dive: routing

The weight of each road is its travel time, length ÷ speed, not its length. In the lesson's graph, the shortest route from Ana's home A to the airport G is 8 km through town and takes 16 min; the highway route is 20 km but takes 15. Counting roads (breadth-first search) treats 9 km of highway like 2 km of city street.

road   length, limit   travel time
A–B    2 km, 30 km/h   4 min
A–C    3 km, 60 km/h   3 min
B–D    2 km, 30 km/h   4 min
C–D    3 km, 30 km/h   6 min
C–E    6 km, 90 km/h   4 min
D–G    4 km, 30 km/h   8 min
E–F    9 km, 90 km/h   6 min
F–G    2 km, 60 km/h   2 min

Then run Dijkstra's algorithm, as in the course's shortest-path lessons. Each round settles the closest unsettled intersection, whose time is then final, and tries its roads:

settle   at       tries its roads
A        0 min    B 4, C 3
C        3 min    D 9, E 7
B        4 min    D 8 (better than 9)
E        7 min    F 13
D        8 min    G 16
F        13 min   G 15 (better than 16)
G        15 min   done: A → C → E → F → G

The trap is stopping at G's first time, 16 min through D: F at 13 still leads to 15.

On a continent of about 20 million intersections, a long drive settles millions of them, which takes seconds, at about 5,000 requests a second. Every pair is out: 20 million × 20 million is 400 trillion pairs. Instead, route planners precompute shortcuts between important junctions: offline, they take out less important intersections one at a time, adding a shortcut wherever the fastest way ran through the one taken out (taking out E adds C–F, 10 min). A search then runs from both ends, climbs onto the big roads and meets in the middle, settling a tiny share of the nodes. That's the idea of contraction hierarchies and the older highway hierarchies.

10. Deep dive: live traffic and ETAs

Phones driving with the app open know how fast they're going. Say 10 million drive with it at busy hours, a ping every 5 seconds: 2 million pings a second.

1. Phones send their position and speed, with no name attached.
2. Each ping is matched to its road segment and put on a stream keyed by segment (the Pub/Sub and Streams lesson).
3. Every minute, the traffic job averages each segment's recent speeds.
4. It saves them in the segment speeds store, in memory.
5. The next route search turns each speed into a travel time.

In the lesson's run, a crash slows F–G, 2 km with a 60 km/h limit. The pings average 60 km/h one minute and 15 the next, so the segment goes from 2 to 8 minutes:

route               before    after the crash
A → C → E → F → G   15 min    21 min
A → B → D → G       16 min    16 min
A → C → D → G       17 min    17 min

Ana's next request gets the town route. A common design lets segments with too few pings fall back to the usual speed for that hour, learned from past weeks. Variants of the shortcut technique are built to take new weights quickly, without starting over.

What breaks first

• A map update: publish new tiles under a new version so old copies don't linger.
• A quiet area in the news: many first requests hit the renderer at once; draw it ahead as it trends, and let the CDN send one request for many identical ones.
• Route servers: each holds the whole graph, so add more behind a load balancer as requests grow.
• Sparse pings: at night or on small roads, use the historical speed.

Summary: the order to follow

1. Scope: the map, search (as in Nearby Places), a driving route with a live ETA.
2. Data: tiles per zoom level, the road graph, live speeds.
3. API: GET /tiles/{z}/{x}/{y} and GET /route?from=&to=.
4. Busy path: loading tiles as people pan.
5. Numbers: 4^z tiles at zoom z; 1 million tile requests a second at the peak.
6. Services: tiles from storage; a route service with the graph in memory.
7. Scale: tiles on a CDN with long lifetimes.
8. Deep dives: busy tiles drawn ahead, the rest on first request; travel times, Dijkstra and shortcuts; live speeds from a stream job.

The same pieces carry over to other map questions: fixed squares on a CDN, a graph search with the right weights, and a stream that keeps the weights fresh.