Design a mapping and navigation service

In one minute

• Three systems share one map. Tile serving, routing and live traffic have different read patterns, freshness needs and failure costs. Scale them separately.
• The road graph is a compiled artifact, not a database. Routing runs on an in-memory, preprocessed graph, because plain Dijkstra on a continental graph takes seconds while a hierarchy-based query takes under a millisecond.
• Traffic changes the weights, not the graph. Pick a routing technique whose expensive phase depends only on topology and whose cheap phase absorbs new speeds every minute.
• Tiles are immutable files behind a CDN. Address every tile by (version, z, x, y), build offline, and never edit in place.
• The phones are the sensors. Live traffic comes from anonymised location reports; map matching, privacy thresholds and abuse resistance decide whether it is trustworthy.

Requirements

Functional

• Pan and zoom a world map on phone and web, with roads, labels, buildings and points of interest.
• Search for a place or address and show it on the map (search ranking itself is covered in Design Google Search and Elasticsearch).
• Compute driving routes between two points with an ETA, up to three alternatives, and options such as avoiding tolls.
• Turn-by-turn navigation that reroutes when the driver leaves the route or traffic changes.
• Show live traffic colouring on roads and incidents such as closures.

Non-functional

• Route response under 300 ms p99 for trips of any length, including continental ones.
• First map paint under 1 second on a mid-range phone on 4G; panning should feel instant.
• ETA error small enough that users trust it: a target such as median absolute error under 10% of trip time.
• Traffic freshness: a new jam visible on the map within about 2 minutes.
• Availability of 99.99% for tiles and routing; navigation must degrade gracefully offline.

Out of scope: satellite imagery capture and Street View, transit timetables and multimodal routing, place reviews, and the map editing tools themselves (we consume their output).

Back-of-envelope

Round assumed numbers, not Google's figures.

• DAU: 500M. Each opens the map 4 times a day: 2B sessions/day.
• Tile requests: about 50 vector tiles per session that miss the device cache: 2B × 50 = 100B/day, so 100B / 86,400 ≈ 1.16M/s average, about 3.5M/s at a 3x peak. At 20 KB per compressed tile, that is 23 GB/s average egress, served almost entirely by the CDN.
• Route and ETA queries: 100M navigated trips a day, plus drive times shown on search results and place cards, plus reroutes. Call it 1B route computations/day: about 11.6K/s average, 35K/s peak.
• Concurrent navigators: 100M trips × 25 minutes / 1,440 minutes ≈ 1.7M at once on average, about 5M at peak. If each sends a batched location report every 5 seconds, peak ingest is 1M reports/s; at 60 bytes each, 60 MB/s.
• Road graph: assume 500M directed road segments. With 4-byte target and 4-byte weight per edge in compact arrays, the routing core is 4 GB, plus about as much again for hierarchy shortcuts. It fits in RAM on one machine, and that single fact shapes the routing design.
• Tiles: zoom 14 has 4^14 ≈ 268M tiles; if 30% are non-empty at 50 KB each, that is about 4 TB, and all lower zooms add a third (1 + 1/4 + 1/16 ...), roughly 5.4 TB per full map version. Higher zooms are drawn by overzooming z14 data on the client, so they cost no storage.
• Traffic history: 50M segments × 672 weekly 15-minute slots × 2 bytes = 67 GB, small enough for every routing worker.
• Location reports over 5 years: 350K/s average × 60 B × 86,400 ≈ 1.8 TB/day, about 3.3 PB over 5 years if kept raw. Keep raw reports for days and only aggregates after that.

API

GET  /tiles/v{map_version}/{z}/{x}/{y}.mvt
     -> protobuf vector tile (roads, labels, buildings), Cache-Control: immutable

POST /v1/routes
     { origin: {lat, lng}, destination: {lat, lng}, depart_at?, avoid: ["tolls"], alternatives: 2 }
  -> { routes: [ { eta_s, distance_m, polyline, traffic_spans: [ {from_idx, to_idx, level} ],
                   steps: [ {maneuver, road_name, distance_m} ] } ],
       route_token, map_version }

WS   /v1/navigate?route_token=...
  -> { kind: "position", lat, lng, heading, speed, ts }            (batched every few seconds)
  <- { kind: "eta", eta_s }  |  { kind: "reroute", route }  |  { kind: "incident", ... }

GET  /v1/traffic?tile=z/x/y&v={traffic_epoch}   -> per-segment congestion levels for one tile
POST /v1/probes  { session_pseudonym, points: [ {lat, lng, ts, speed, accuracy_m} ] }

map_version in the URL makes tiles cacheable forever. route_token lets a navigation session resume on another server. Traffic is a separate short-lived overlay, so a speed change never invalidates a base tile.

Data model

road_segments (the editable source of truth): segment_id, from_node, to_node, geometry polyline, length_m, road_class, speed_limit, oneway, turn restrictions, toll flag. Partitioned by an S2 cell around level 6 so editors and builds work region by region. Never on the query path.

routing graph (compiled, read-only): nodes renumbered so nearby nodes get nearby IDs, edges in compressed sparse row arrays, plus shortcuts and a partition structure. One file per map version, loaded whole by each routing worker.

traffic_live: key (segment_id, direction) → speed_kmh, confidence, sample_count, updated_at. In memory, sharded by S2 cell so one shard owns a metro area, rewritten every 30 to 60 seconds.

traffic_history: (segment_id, day_of_week, slot) → median and 85th percentile speed. Columnar files rebuilt weekly, used for future departures and as the fallback when live data is thin.

tiles: object storage keyed v{map_version}/{z}/{x}/{y}. Build output, written once.

probes: an append-only log partitioned by time and keyed by a rotating session pseudonym rather than a user ID. Retained for days, not years.

High-level design

flowchart LR
  C["Phone / browser"] --> CDN["CDN edge"]
  CDN --> TS[("Tile store by version")]
  C --> GW["API gateway"]
  GW --> RS["Route service"]
  RS --> RW["Routing workers (graph in RAM)"]
  TR["Traffic store (live speeds)"] --> RW
  C -->|"location batches"| PI["Probe ingest"]
  PI --> Q["Log (Kafka)"]
  Q --> MM["Map matcher"]
  MM --> AG["Speed aggregator"]
  AG --> TR
  MD[("Road segments")] --> GB["Graph and tile builders"]
  GB --> TS
  GB --> RW

Write paths. There are two, on very different clocks. Slow: map edits land in road_segments; a periodic build compiles a new routing graph, regenerates only tiles whose cells changed, and publishes a new map_version. Fast: navigating phones send batched positions to probe ingest, which appends them to a log; map matchers snap traces to road segments, and the aggregator turns traversals into per-segment speeds every 30 to 60 seconds and publishes a new traffic epoch.

Read paths. For the map, the client computes which tiles cover the viewport and fetches them; nearly every request is a CDN hit, and the client renders vectors on the GPU. For a route, a routing worker with the current graph and traffic metric snaps origin and destination to the nearest segments, runs the query, builds alternatives and returns geometry plus ETA. During navigation, the session server compares positions with the route, reroutes on deviation, and refreshes the ETA as traffic epochs change.

Deep dives

1. Fast routes on a continent-sized graph

Plain Dijkstra settles every node closer than the destination: for a 1,000 km trip, millions of nodes, each costing cache misses, so seconds per query. On the standard Western Europe benchmark (18 million vertices, 42.5 million arcs), a random query with Dijkstra scans about 9.3 million vertices and takes about 2.2 seconds (Bast et al., Table 1). A* with a straight-line heuristic helps little on roads, and ALT (A* with landmarks) still settles hundreds of thousands of nodes.

Contraction hierarchies (CH) changed the game. Preprocessing orders nodes by importance and contracts them one at a time, adding a shortcut edge whenever removing a node would break a shortest path between its neighbours. A query runs two small Dijkstra searches, forward from the origin and backward from the destination, each only moving to more important nodes, meeting near the top of the hierarchy. On the same benchmark CH scans about 280 vertices and answers in about 110 microseconds after 5 minutes of preprocessing.

The catch is traffic: CH preprocessing bakes in edge weights and takes minutes for a continent, and its performance degrades with realistic turn costs. So I would split the work into a metric-independent phase (partition or order nodes from topology alone, once per map version) and a customisation phase (recompute shortcut weights from new speeds every minute). Customizable Route Planning (CRP) does exactly this: its topology phase takes about an hour, but a new cost function applies in roughly 370 ms on 12 cores, and queries take about 1.65 ms, slower than CH but nearly independent of the metric (Bast et al.). OSRM ships both: osrm-contract for CH, and osrm-partition plus osrm-customize for its multi-level Dijkstra (MLD), which its docs recommend when data needs live updates such as traffic (OSRM wiki). Customizable contraction hierarchies are a third option on the same principle. Google has not published what it runs, so say what you would build and why. Alternatives come from the same search: keep a few meeting points whose paths differ enough and are not much longer than the best.

2. Live traffic from phones

A raw GPS trace has 5 to 20 metres of error and does not say which of two parallel roads the car is on. Map matching uses a hidden Markov model: candidate segments near each point are hidden states, emission probability falls with distance from the point, and transition probability favours pairs whose route distance matches the straight-line distance between points. Viterbi picks the likeliest sequence, giving "segment S traversed in 42 seconds at 14:03". This is the formulation of Newson and Krumm, who tested it on a 1 Hz drive around Seattle and measured how accuracy falls as sampling gets sparser and noisier (Microsoft Research, 2009).

The aggregator needs enough distinct devices on a segment within a window before publishing a speed, for accuracy and for privacy: one phone on a quiet street identifies a person and says little. Below the threshold, use the historical speed. Trim the start and end of each trip so homes are never revealed, and weight recent samples so a new jam shows within one or two windows.

The ETA is a prediction, not a sum of current speeds: a segment 40 minutes ahead will have changed by the time you reach it. Blend live speeds near the origin with historical patterns further out, and correct with a learned model. Google and DeepMind described graph neural networks over "supersegments" of adjacent roads for this: ETAs were already accurate for over 97% of trips, and the model cut the remaining inaccurate ones by up to about 50% in cities such as Taichung (DeepMind, 2020). History also goes stale: when lockdowns cut traffic by up to 50% in early 2020, Google changed its models to weight the last two to four weeks of patterns over older data (Google, 2020). Plan for that knob from the start.

3. Tiles: raster or vector, built or rendered on demand

Raster tiles (256 x 256 PNGs) render identically everywhere, but every style, language and screen density needs its own set, and rotation blurs labels. Vector tiles ship geometry in a protobuf and the client draws it: several times smaller, with smooth zoom, tilt, dark mode and local-language labels from the same bytes, and one zoom 14 tile overzooms to cover zooms 15 to 20. I choose vector tiles, keeping raster for static image APIs.

Pre-building every non-empty tile is about 5 TB per version, cheap in object storage, and makes every request a static read. On-demand rendering saves storage but puts CPU on the request path during a cache-cold surge. Build up to zoom 14 ahead of time, rebuild only cells touched by edits, and publish atomically by flipping the version clients receive.

Down the stack

Failure modes

• 10x load (holiday exodus, evacuation). Routing workers are stateless replicas, so autoscale from a warm pool with the graph already mapped, cache routes for popular cell pairs per traffic epoch, and shed alternatives before primary routes.
• Region outage. Each region holds a full copy of graph, tiles and recent traffic. Fail routing over; the failed region's traffic falls back to historical speeds. Navigating clients keep guiding on their cached route.
• Hot key. A stadium emptying sends millions to the same tiles and segments. Immutable tiles let CDN request collapsing absorb it; pre-split metro traffic shards so one city cannot overload one aggregator.
• Bad map data. An edit that wrongly closes a highway misroutes thousands within minutes. Route a fixed benchmark set on every build and diff against the previous version, canary by region, and keep instant rollback to the previous map_version.
• Spoofed traffic. In 2020 an artist pulled a wagon of 99 phones through Berlin and produced fake jams (Simon Weckert). Require device diversity, plausible motion and agreement with neighbouring segments, and cap how far a small sample can move a busy road's speed.
• Traffic pipeline stall. Publish the epoch timestamp, alert on its age, and switch workers to historical speeds when it is too old.

In the wild

• Google Maps, 2020: 99 phones in a handcart. Artist Simon Weckert pulled 99 second-hand phones, each running Google Maps, through Berlin streets, including past Google's office. Maps read them as slow-moving cars, turned empty streets red, and routed real drivers away. The attack needed no hacking, only many devices agreeing, which is why traffic aggregation needs device-diversity and plausibility checks, not just sample counts (Simon Weckert; The Guardian).
• Google Maps, 2020: lockdowns broke the history. Historical speed patterns are a core ETA input, and when lockdowns began worldwide traffic fell by up to 50%. Google changed its models to weight the last two to four weeks of patterns automatically and deprioritise older data (Google).
• Google and DeepMind, 2021: graph neural networks for ETAs in production. The CIKM 2021 paper describes a GNN over supersegments deployed in Google Maps, which cut negative ETA outcomes significantly against the prior production system, by more than 40% in cities like Sydney (Derrow-Pinion et al., arXiv 2108.11482). DeepMind reported that training was unstable because batches mixed two-node graphs with graphs of over 100 nodes, and used MetaGradients to adapt the learning rate so results were reproducible (DeepMind).

Trade-offs

Leadership lens

• Build first: tiles from an open dataset behind a CDN, then routing on a static graph with historical speeds. Live traffic and ML ETAs come next because they need probe volume that only exists once people use the app.
• Team ownership: map data (source graph, edits, validation), build (graph compilation, tiles), routing (query engine and latency), traffic (probes, matching, ETA models) and clients (rendering, offline). map_version and the traffic epoch are the contracts between them.
• Cost drivers: CDN egress for tiles dominates; routing workers are memory-heavy but few; probe storage stays moderate with short raw retention.
• Rollout: map versions go through benchmark comparison, regional canary, then global, with one-step rollback. ETA models ship behind experiments measured on real trip outcomes.
• Review questions: what is our privacy threshold for publishing a segment speed, and who signed off; how long until a closure reported by a city shows up in routes; what does a driver see when the traffic epoch is ten minutes old.

Check yourself

1. Why is plain contraction hierarchies not enough once live traffic is involved, and what is used instead?

   Show answer

   CH preprocessing bakes in edge weights and takes minutes for a continent, so it cannot absorb new speeds every minute. A customizable approach (CRP or MLD, or customizable CH) does a metric-independent phase from topology once per map version and recomputes shortcut weights from new speeds in seconds, at the cost of more complexity and somewhat slower queries than CH.

2. The traffic pipeline stalls. How should the system detect and handle it?

   Show answer

   Publish the traffic epoch timestamp and alert on its age. When it is too old, routing workers switch to historical speeds, which also serve as the fallback for segments without enough samples.

3. Why can the routing graph be replicated to every worker instead of being sharded?

   Show answer

   About 500M directed segments at 4-byte target and 4-byte weight per edge is a 4 GB core, plus about as much again for shortcuts, which fits in RAM on one machine. Replicating it keeps cross-machine hops off the critical path and lets workers scale as stateless replicas.

4. How does the aggregator protect privacy and resist spoofed traffic such as a wagon of 99 phones?

   Show answer

   It publishes a segment speed only when enough distinct devices traversed it in a window, falling back to historical speed otherwise, and trims trip starts and ends so homes are not revealed. Against spoofing it requires device diversity, plausible motion and agreement with neighbouring segments, and caps how far a small sample can move a busy road's speed.

Sources and further study

Primary

• Hidden Markov Map Matching Through Noise and Sparseness (Newson and Krumm, 2009): the HMM map-matching paper, with its Seattle test data published for reuse.
• ETA Prediction with Graph Neural Networks in Google Maps (CIKM 2021): the production ETA model behind the supersegment approach.
• RFC 6928: Increasing TCP's Initial Window: the 10-segment initial window that decides how many round trips a cold tile fetch takes.

Systems docs

• OSRM: Running OSRM: the CH pipeline (osrm-contract) versus the MLD pipeline (osrm-partition, osrm-customize) for live updates.
• Mapbox Vector Tile Specification 2.1: layers, per-layer extent, geometry commands and the .mvt media type.

Books

• System Design Interview, Volume 2, Alex Xu and Sahn Lam, Ch 3 "Google Maps": tiles, routing tiles, location updates and ETA services at interview depth.
• Designing Data-Intensive Applications (1st ed.), Martin Kleppmann, Ch 10 "Batch Processing": building derived, immutable outputs (here the routing graph and tiles) offline and swapping them in whole.

Other curricula

• Azure Architecture Center: Static Content Hosting pattern: frames pre-built tiles as static assets served from storage and a CDN rather than by compute.
• Azure Architecture Center: Geode pattern: frames full per-region copies of graph, tiles and traffic as geodes that each serve any request.

Watch

• Google Maps System Design Interview Question (codeKarle): an interview walkthrough covering segments, routing between them and real-time traffic.
• Design Navigation Systems like Google Maps, Uber & Doordash (Irtiza Hafiz): navigation design from location updates to route computation.
• Designing a location database: QuadTrees and Hilbert Curves (Gaurav Sen): the spatial indexing ideas behind tiles and place lookups.

Free resources

• Route Planning in Transportation Networks (Bast et al.): the survey of Dijkstra speed-ups, including contraction hierarchies and customizable route planning, with measured query times.
• Contraction hierarchies (Wikipedia): a clear description of node ordering, shortcuts and the bidirectional query.
• Google Maps 101: How AI helps predict traffic and determine routes (Google): how historical patterns and live data combine into ETAs.
• Traffic prediction with advanced Graph Neural Networks (Google DeepMind): the supersegment model used to improve ETA accuracy.
• Slippy map tilenames (OpenStreetMap wiki): the z/x/y tile scheme and conversion formulas in many languages.
• Mapbox Vector Tile Specification: the protobuf layout, command encoding and extent used by vector tiles.