System Design: [Maps and navigation service name]

Reference design for a maps and turn-by-turn navigation service: map rendering with pre-generated vector tiles, a routing engine built on a contraction-hierarchy style road graph that accepts live traffic weights, ETA prediction, rerouting from streamed location updates, geocoding and offline map packs. It follows the structure of the System Design Document template, adds a 45-minute interview path, access-pattern and failure-mode tables, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; values marked Example are assumptions, not benchmarks.

Document control

Approvals

Revision history

Contents

1. Overview
2. Requirements
3. Capacity estimation
4. API design
5. Data model
6. High-level design
7. Detailed design
8. Scalability and performance
9. Reliability, security and operations
10. Trade-offs and alternatives
11. Delivery plan and risks
12. Appendices

1. Overview

1.1 Problem statement

[Example: The current product shows raster map images from a third-party provider and computes routes with a plain shortest-path search on static speed limits. Routes ignore congestion, ETAs are wrong by more than 20% at rush hour, and the per-request provider bill grows faster than usage. The product needs its own map rendering, traffic-aware routing and navigation for [coverage area].]

1.2 Proposed solution

[Example: A batch pipeline turns map data into vector tiles, a routing graph and a geocoding index for each release. Clients fetch tiles from a CDN and render them locally. A routing service holds a preprocessed road graph per region in memory and applies live traffic weights every minute through a customization step, so queries stay fast while weights change. Navigating clients stream batched location samples; a traffic pipeline map-matches them to road segments and publishes segment speeds. A navigation session service compares each client's progress with its route and triggers rerouting when the client leaves the route or a much faster route appears. Offline packs bundle tiles, a compact routing graph and a geocoding subset per area.]

1.3 Decisions requested from reviewers

1.4 45-minute interview path

Use this order when the document serves an interview or a short review. It fits the time and leaves room for one deep dive chosen by the interviewer.

Pick the routing deep dive unless the interviewer steers elsewhere: it is where a naive answer (run Dijkstra on the planet per request) fails most visibly. Say early that tiles are a caching problem, not a compute problem.

2. Requirements

2.1 Core functional requirements

2.2 Non-functional requirements

2.3 Below the line (out of scope)

• [Example: public transit routing with timetables (needs a different algorithm family)]
• [Example: collecting and editing base map data (consumed as releases from the data team)]
• [Example: places reviews, photos and business listings]
• [Example: truck routing with legal restrictions per vehicle]
• [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

3.2 Location updates

Sessions per day and average concurrent sessions:

Consequence: location ingestion is the highest-rate write path. It goes into a partitioned log, never into a database on the request path, and the session service keeps only the latest position per session in memory.

3.3 Route requests

Assume per day one route per session, two reroutes per session on average, and 60 million route previews from users who do not start navigation:

Consequence: the route rate is modest, so routing is bounded by memory (the graph must stay resident) more than by CPU. Even at an Example 15 ms of CPU per query including two alternatives, the peak needs about $6\,250 \times 0.015 \approx 94$ cores per copy of the fleet, which is small.

3.4 Routing graph memory

With shortcuts, a contracted graph holds roughly twice the original edges. At an Example 20 bytes per stored edge:

Consequence: one region fits on one large-memory server, so we shard routing by region (continent or country group), replicate each region graph, and handle the rare cross-region route with a coarse overlay graph.

3.5 Tiles

Tile requests and origin load with an Example CDN hit rate of 95%:

Zoom 14 has $4^{14} \approx 2.7 \times 10^{8}$ tiles. If 30% hold data and an average vector tile is Example 20 KB, zoom 14 needs about 1.6 TB, and all lower zooms together add about one third more, about 2.1 TB per release.

Consequence: tiles are generated once per data release, stored in object storage and served through a CDN; the origin only fills cache misses.

3.6 Summary

4. API design

4.1 Endpoints

4.2 Request and response examples

A route request, its response, and one location batch from a navigating client:

POST /v1/routes HTTP/1.1
Content-Type: application/json

{"origin": {"lat": 10.7769, "lng": 106.7009}, "destination": {"lat": 10.8231, "lng": 106.6297}, "profile": "car", "alternatives": 2, "depart_at": "now", "avoid": ["tolls"]}

{"routes": [{"route_id": "rt_9f2c", "distance_m": 11240, "duration_s": 1680, "duration_no_traffic_s": 1260, "polyline": "[encoded polyline]", "legs": [{"steps": [{"maneuver": "turn-right", "street": "[Street name]", "distance_m": 420}]}], "traffic_version": "2026-10-22T08:14Z", "graph_release": "2026.42"}]}

{"session_id": "nav_51ab", "samples": [{"t": 1792640000, "lat": 10.7771, "lng": 106.7012, "speed_mps": 8.1, "heading": 82, "accuracy_m": 6}]}

4.3 Errors and limits

Route requests are idempotent reads. Location batches carry a sequence number per session so the server drops duplicates after client retries.

5. Data model

5.1 Entities

The graph entities come from the data release; speeds and sessions are runtime data with short lifetimes.

5.2 Storage choices

5.3 Access patterns

6. High-level design

7. Detailed design

7.1 Deep dive: map tiles

The map is cut into square tiles addressed by zoom $z$, column $x$ and row $y$ in the Web Mercator projection; zoom $z$ has $2^{z} \times 2^{z}$ tiles.

Choice: vector tiles pre-generated up to zoom 14, with the client overzooming (reusing zoom 14 geometry) for closer views. Reason: one tile set serves every style and language, transfers are smaller than raster, and the client can rotate the map during navigation without new requests. Generalise geometry per zoom so a zoom 5 tile does not carry every building.

Tile URLs include the release, so tiles are immutable and cacheable for the life of the release. A new release changes the URL prefix; nothing is purged.

7.2 Deep dive: routing on a road graph with live traffic

The road network is a directed graph: intersections are nodes, road segments are edges with a travel-time weight. Turn restrictions are modelled as edges between segment pairs or as a turn-cost table.

How contraction works, in short: rank nodes by importance, remove them one at a time from least important upward, and add a shortcut edge whenever removing a node would break a shortest path between its neighbours. A query then runs two searches, forward from the origin and backward from the destination, each only climbing to more important nodes, and meets in the middle.

Choice: a customizable variant. The expensive step depends only on the road topology and runs once per data release; a customization step applies the live travel times every minute and finishes in seconds. Reason: plain CH would need full preprocessing for every traffic update, while Dijkstra or A* cannot meet NFR-02 on long routes.

Alternatives come from penalising the edges of the best route and searching again, keeping routes that differ enough and are not much longer. Return the traffic_version so a reroute can be compared fairly with the original.

7.3 Deep dive: ETA with live traffic

The ETA is the sum of predicted travel times along the route at the time the driver will reach each segment, not at departure time.

Choice: blend. For each segment use the live speed if the driver reaches it soon, fade toward the historical profile further ahead, then apply a learned correction per route (intersections, turns, time of day) trained on completed trips. Reason: it meets NFR-03 without a heavy model on the request path; the correction is a small model served next to the router.

Speeds come from map-matched samples. Aggregate per segment per minute only when at least Example 3 distinct sessions contributed; otherwise fall back to the profile. This also protects privacy (9.2).

7.4 Deep dive: location updates and rerouting

Clients sample GPS every second and send a batch every 5 s while navigating. The session service keeps the route, the last matched position and the expected progress.

Choice: hybrid. The client detects leaving the route (for example a distance above a threshold for several consecutive samples) and requests a reroute immediately; the server re-evaluates the remaining route every Example 2 minutes against fresh traffic and pushes a better route only when it saves more than Example 3 minutes or 10%. Reason: NFR-05 needs a local decision, while traffic changes are visible only on the server.

Map matching snaps noisy samples to the most likely sequence of segments, using the road geometry and the order of samples, not just the nearest road. A nearest-road snap confuses parallel roads and overpasses.

7.5 Geocoding

Forward geocoding parses a free-text query, matches it against an address and place index, and ranks by text score, importance and distance from the user. Reverse geocoding finds the nearest address or street to a point with a spatial index. Keep one index per country so formats and releases stay independent. Typing suggestions reuse the prefix techniques in Search Autocomplete System Design (system-design/design-search-autocomplete).

7.6 Offline maps

An offline pack holds the vector tiles for an area up to zoom 14, a compact routing graph for the same area with typical speed profiles, and a geocoding subset. Packs are versioned with the data release; the client downloads a binary diff when a new release covers its packs. Offline routing has no live traffic, so the client labels the ETA as an estimate and switches to online routing when connectivity returns.

7.7 How real systems do it

How real systems do it (paraphrased, not copied). Delling, Goldberg, Pajor and Werneck describe Customizable Route Planning (SEA 2011): a preprocessing phase that depends only on the road network, a fast customization phase that applies any cost function, and a query phase. Microsoft Research states that the approach underlies the routing engine of Bing Maps. The key idea for this design is the same split: run the expensive work per map release, and run the cheap work per traffic update. Uber's H3 write-up (2018) describes a hexagonal, hierarchical grid used to aggregate and analyse spatial data, which is the role H3 cells play here for partitioning location samples. Read the originals in 12.3; this box keeps only the general idea.

8. Scalability and performance

Latency budget for a route request (target p95 300 ms):

9. Reliability, security and operations

9.1 Failure modes

9.2 Security and privacy

9.3 Observability

9.4 Cost estimate

10. Trade-offs and alternatives

11. Delivery plan and risks

11.1 Milestones

11.2 Rollout and rollback

[Example: Each data release ships to one region first and to the rest after 48 hours without regressions in reroute rate or ETA error. The previous release stays loaded on routing servers and tile URLs, so rollback is a configuration change that takes effect within 5 minutes.]

11.3 Risks

12. Appendices

12.1 Open questions

12.2 Glossary

12.3 References

Standard and licence note

Based on common industry practice for map rendering and route planning and on the published research and specifications cited in 12.3. The book and engineering write-ups listed there are inspiration only; no text, diagrams or numbers were copied, and all figures here are illustrative examples. Check the current version of each cited specification and the licence of your map data before use. Original text written for this collection. Template licence: MIT.