Design Maps and Navigation

You open a maps app, the city appears in a blink, you type an address, and a blue line with "10 min" shows up. You start driving. A few minutes later the app says "Faster route found, saves 5 min" because a crash has just blocked the motorway ahead.

Interviewers like it because three systems hide behind one screen: static content (the map), an algorithm (shortest paths on a huge graph) and a stream (moving phones turned into traffic). A strong answer keeps them apart and goes deep on one. The steps follow A Framework for Any Design. Try each "Your turn" box before you read on.

#Clarify the problem

• Functional: show a pannable, zoomable map; compute the fastest driving route between two points with an ETA; while driving, update the ETA from live traffic and offer a faster route when one appears; reroute when the driver leaves the route.
• Non-functional: map tiles load in under 100 ms from nearby; a route in under 200 ms at the server; a new jam shows up in ETAs within 2 to 3 minutes; routing stays available without live traffic; location data is anonymised and kept briefly.
• Out of scope: place search, walking and transit, map editing tools, street-level imagery.

#Estimate the scale

A day has 86,400 seconds.

• Tiles: if each user loads about 100 map tiles a day, that is 100 million × 100 = 10 billion tiles a day, or 10¹⁰ ÷ 86,400 ≈ 116,000 a second, about 350,000 at a 3x peak. If the CDN answers 95% of them, the origin sees 5% of 350,000 ≈ 17,000 a second.
• Routes: 100 million ÷ 86,400 ≈ 1,200 a second on average, about 3,500 at peak.
• Pings: 1 million batches a second at peak (worked below). At about 100 bytes each that is 100 MB/s: a stream, not a database.
• Road graph: assume 500 million junctions and 1.2 billion one-way road segments. At 8 bytes a junction (two packed coordinates) and 12 bytes a segment (target, travel time, segment id), that is 4 GB + 14.4 GB ≈ 18 GB. The whole graph fits in the memory of one large server.

#Define the API

GET  /tiles/v812/{z}/{x}/{y}.mvt           served by the CDN, cached for days
  200  vector tile (roads, labels, areas)
  404  outside the map
 
POST /routes
  body: { "from": [52.37, 4.89], "to": [52.09, 5.12], "depart": "now" }
  200  { "route_id": "r_51x", "polyline": "...", "eta_s": 600,
         "steps": [ { "turn": "left", "road": "...", "at_m": 1200 }, ... ],
         "graph_version": 812 }
  404  no road connects the two points
  503  routing overloaded; the app retries with backoff
 
POST /nav/{route_id}/pings
  body: { "points": [ [t, lat, lng, speed, heading], ... ] }   5 points, one a second
  200  { "eta_s": 540, "better_route": null }
  200  { "eta_s": 1020, "better_route": { "route_id": "r_52k", "saves_s": 300 } }

The decision worth arguing is how the phone hears about a faster route. A WebSocket per driver means 5 million open connections. The phone already pings every 5 seconds, so the reply carries the ETA and any better route: no extra connection, at most 5 seconds late. See realtime communication for when push is worth it.

The tile URL contains the map version (v812). A rebuild changes the URLs, so the CDN never needs purging and a phone never mixes two builds. The cost: a new version starts with a cold CDN, and the origin would see the full 350,000 requests a second. Push the popular tiles to the CDN before the app switches versions.

#Model the data

-- road graph: built offline from map data, shipped as a file, loaded into RAM
junction   id INT, lat INT, lng INT                 -- 8 B packed coordinates (+ id by position)
segment    from INT, to INT, segment_id INT,
           length_m INT, road_class TINYINT, turn_rules ...   -- one row per direction
 
-- live speeds: key-value, overwritten every minute
live_speed       segment_id -> (speed_kmh, samples, updated_at)   -- about 16 B each
 
-- typical speeds: a weekly curve, 672 slots of 15 minutes. Segments share
-- a few thousand curve shapes, so each stores a curve id, not 672 numbers
typical_curve    segment_id -> curve_id                      -- 2 B each
curve            (curve_id, slot 0..671) -> speed_kmh
 
-- active routes: one per navigating phone, deleted when the trip ends
active_route     route_id -> (segments, eta_s, better_route)  -- a few KB
 
-- pings: a partitioned stream, kept for a few hours, no user id
ping       trip_token, t, lat, lng, speed, heading

Tiles never change and are read by exact key: files in blob storage behind a CDN. The search reads the graph in random order millions of times a second, so it sits in memory as compact arrays. Only main roads get enough pings for a live speed; for 100 million such segments that is 100 million × 16 B = 1.6 GB. Typical-speed curve ids add 1.2 billion × 2 B = 2.4 GB. Every routing server can hold both. Pings are written once and read once, so they belong in a stream, with a random token per trip instead of a user id.

#High-level design

The three flows share only the phone and the gateway, so each can fail alone.

Step through a map load, a route, and a jam that becomes a faster route.

#Deep dives

#Map tiles

The world is cut into squares. At zoom 0 one square holds the whole world; each zoom level splits every square into four. A tile is named by z/x/y, so the phone can work out which tiles cover the screen without asking anyone.

#Routing on a huge road graph

A route is a shortest path on a weighted graph, where the weight of a segment is its travel time. Dijkstra's algorithm is correct, but it grows a circle of settled junctions around the start until it reaches the destination. For a long trip that circle can hold tens of millions of junctions. Suppose it is 20 million at about 1 µs each (a heap operation plus a memory miss): 20 seconds per route, against a goal of 200 ms.

Searching from both ends, or aiming at the target (A*), shrinks the circle a few times. Not enough: most of the work must happen before anyone asks.

In outline: cut the graph into cells along natural borders, so each cell has few border junctions. For each cell, precompute the fastest time between every pair of its border junctions; these become shortcut edges. A query runs Dijkstra on real roads in the start and end cells and on shortcuts everywhere else. With several levels of cells, a long query settles tens of thousands of junctions, not tens of millions, and the answer is still exact for the current weights.

Capacity check: 50,000 junctions at 1 µs is 50 ms of one core, and 3,500 routes a second × 0.05 s = 175 busy cores: about 20 servers of 16 cores keeps them near half busy. Each holds the 18 GB graph, so they are replicas, not shards. Sharding the graph would turn one search into many network hops.

#From pings to traffic and ETAs

A GPS point says where a phone is, not which road. The aggregator first map-matches: it snaps each run of points to the most likely chain of segments, using heading and speed to tell a motorway from the road under it. Then it keeps each segment's speeds from the last few minutes.

• Partition by area. The stream is keyed by map tile, so one aggregator owns an area and averages it alone.
• Ignore noise. One car stopping for fuel is not a jam. Publish a new speed only when several phones agree.
• Blend with history. With few samples, use the typical speed for that segment and 15-minute slot of the week.

The ETA is the sum of segment times. Mia's route before and after the crash:

A senior refinement: live speed suits the next few minutes, but a segment you reach in 50 minutes should use the typical speed for that later time.

#Rerouting

Two different events lead to a new route, handled in different places.

• The driver leaves the route. The phone notices several points in a row more than, say, 50 m off the line, and asks for a route from where it is. Local detection is fast and works on a bad connection.
• Traffic makes another route faster. Re-pricing all 5 million active routes every 90 seconds would be 55,000 searches a second, 15 times the route traffic. So re-price only routes that cross a segment whose speed changed, and offer an alternative only if it saves enough, say 2 minutes and 10% of the remaining time, so drivers are not flipped back and forth.

#Bottlenecks and failures

At 10x (10 million pings a second, 35,000 routes a second), the stream and aggregator add partitions, since areas are independent. Routing adds replicas: 35,000 × 0.05 s = 1,750 cores. The awkward part is the shortcut refresh, which every replica repeats; at that size, compute it once and ship the result to the replicas.

#What a strong answer sounds like

#Follow-up questions

#How do you ship a new version of the map data?

Load the new graph next to the old one, then switch. Routes carry a graph version, so a reroute during the switch uses its route's version.

#How would offline navigation work?

The user downloads a region's tiles and graph slice with typical speeds, and the phone runs the same search, without live traffic.

#How do you protect people's privacy?

Pings carry a random token per trip, trip ends are trimmed so homes are not revealed, and raw pings are deleted after hours. Only per-segment averages are kept.

#How do you know the ETAs are good?

Every finished trip gives a predicted and an actual arrival time. Track the error by region and time of day, and use it to tune how live and typical speeds are blended.

#How do you handle road closures and turn restrictions?

Closures are weight changes, set to infinity, and go through the same per-cell shortcut refresh as traffic. Turn restrictions are modelled in the graph itself (edges between segments), so the search can never produce an illegal turn.