Design a maps and navigation service

The problem

A maps service must:

• Draw the map smoothly as you pan and zoom.
• Find places (search, addresses).
• Route: the best way from A to B by car, foot or transit.
• Estimate arrival times using live traffic, and re-route when conditions change.

Part 1: showing the map

The world is too big to send at once. The standard answer is tiles.

• The map is cut into a grid of small squares at each zoom level. Zoom 0 is one tile for the world; each level doubles the tiles along each side (4x the tiles).
• A tile is addressed by zoom, x and y. The client works out which tiles cover the screen and requests just those.
• Tiles are static files, so they are cached in the browser and on a CDN.
• Raster tiles are pre-drawn images. Vector tiles carry the shapes and labels as data, and the client draws them. Vector tiles are smaller, scale smoothly, and allow styling and rotation.

100%

Figure SDA-RWS-03-1 · Map tiles, routing and traffic · © forcsguy.com

100%

Figure SDA-RWS-03-2 · Tiles multiply with every zoom level · © forcsguy.com

Part 2: routing

Roads become a graph: intersections are nodes, road segments are edges with a cost (distance, or better, travel time).

• Dijkstra finds the cheapest path but explores too much of a continent-sized graph. A* adds a heuristic (straight-line distance) to head towards the goal.
• Real systems precompute: they build a hierarchy where highways are shortcuts (such as contraction hierarchies), so a long route only searches a small part of the graph.
• The graph is split into regions or tiles that are loaded as needed, and routing steps across boundaries.
• Costs depend on mode (car, bike, walking), turn restrictions, tolls and one-way streets.

100%

Figure SDA-RWS-03-3 · A road network as a graph · © forcsguy.com

Part 3: traffic and arrival times

• Phones send anonymous location updates every few seconds. These flow through a stream and are matched to road segments (map matching).
• An aggregator computes the current speed per segment, combined with historical speeds for the time of day and day of the week.
• Route cost uses these speeds, so the fastest route changes through the day. ETA is the sum of segment times.
• During navigation, the client reports progress; if a faster route appears or traffic changes, the server suggests re-routing.

Search and places

Place search is separate: an index of names and addresses (geocoding turns an address into coordinates; reverse geocoding does the opposite), plus a geospatial index for "near me" (next lesson).

Scale and reliability

• Map data changes slowly: rebuild tiles in batches, publish a new version, and invalidate CDN caches.
• Tile traffic is huge and cacheable: serve it from the edge.
• Routing and traffic are the CPU-heavy, latency-sensitive parts: keep the graph in memory, replicate by region.
• Location data is sensitive: anonymise it, limit retention, and let users opt out.

Real-world reading