Design Google Maps

Design a maps product used by hundreds of millions of people on phones and in browsers. It has three jobs: draw a smooth, zoomable map anywhere on Earth; find the fastest route between two places by car, taking current traffic into account; and give an arrival time people can trust, updating it during the drive.

The road network has hundreds of millions of segments, traffic changes minute to minute, and a route request that takes a full second feels broken. Phones that are navigating can also share anonymous speed readings, which is where live traffic comes from.

In 45 minutes, size the problem, sketch how map tiles are produced and served, design the routing service and how live traffic gets into it, and discuss how ETAs are computed and kept accurate.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Location & Marketplaces · problem 24 of 70

Ask before you design. Try answering each yourself, then compare.

1. Which features are in scope?
   Typical answer

   Map display, place search/geocoding at a basic level, driving directions with live traffic, and ETA. Transit, walking and street imagery are out.

2. What scale?
   Typical answer

   About 300 million daily users, ~1.5 billion route or ETA requests a day, and tens of millions of phones navigating at peak.

3. How fresh must traffic be?
   Typical answer

   Speeds per road segment updated about every minute; incidents like closures within a few minutes.

4. Do we build the base map data ourselves?
   Typical answer

   Assume we have road and place data from an existing pipeline; we design how it is turned into tiles and a routing graph.

5. Must routes be optimal?
   Typical answer

   Near-optimal is fine; fast response (p99 under ~200 ms for a cross-city route) matters more than the last few seconds of a route.

6. Do we support offline maps?
   Typical answer

   Nice-to-have follow-up; design online first.

Requirements

Functional

• Render the map at any location and zoom level, including labels and points of interest.
• Search for places and addresses and convert them to coordinates.
• Return the fastest driving route between two points with alternatives, using live traffic.
• Show an ETA and update it, and reroute, during navigation.
• Collect anonymous speed readings from navigating phones to estimate traffic.

Non-functional

• Tile load p95 under 100 ms from the CDN; tile serving near 100% cacheable.
• Route computation p99 under 200 ms for a city-scale route, under 1 s for cross-country.
• Traffic data at most ~2 minutes old on the routing servers.
• Ingest ~1 million speed probes per second at peak.
• 99.99% availability for tiles and routing; graceful fallback to typical-traffic routing.

Out of scope

• Collecting the base map (survey cars, satellite imagery).
• Public transit, cycling and walking modes.
• Turn-by-turn voice guidance on the device.

Back-of-the-envelope estimates

• Routes and ETAs: 1.5 B/day ≈ 17,000 QPS on average, ~50,000 at peak. Plain Dijkstra across a country takes about a second and touches millions of nodes; with a precomputed hierarchy a query takes a millisecond or two, so a few hundred cores cover peak.
• Speed probes: 300 M users × ~120 probes on days they drive ≈ 36 B/day ≈ 420,000 per second, over 1 M/s at peak; at ~100 bytes each that is ~3.6 TB/day of raw input, which we aggregate down and only sample into long-term storage.
• Tiles: ~100 tile fetches per user per day ≈ 30 B/day ≈ 350,000 per second, nearly all served from CDN. The full planet of vector tiles to street-level zoom is on the order of a few hundred GB, so the origin is small; the work is in regenerating changed tiles.
• Road graph: a continent's routable graph plus precomputed shortcuts is tens of GB, which fits in memory on large machines, one replica set per region.

The numbers that drive the design are the 50,000 route QPS (forces precomputation instead of plain search) and the 1 M probes per second (forces a streaming aggregation pipeline separate from serving).

API

GET  /tiles/{style}/{z}/{x}/{y}.mvt                  -> vector tile (CDN, immutable per version)
GET  /v1/geocode?q=..&near=lat,lng                  -> [{placeId, name, lat, lng}]
POST /v1/routes  {origin, destination, departAt?, avoid?[], alternatives: 2}
                 -> {routes:[{polyline, distanceM, etaSeconds, steps[], trafficSpans[]}]}
POST /v1/navigation/{sessionId}/progress  {lat, lng, speed, heading, ts}
                 -> {etaSeconds, reroute?: route}
POST /v1/probes  [{segmentHint, lat, lng, speed, ts}, ...]  (batched, anonymised)

Tile URLs include a data version and are immutable, so the CDN can cache them for a long time and a new map release simply changes the version in the style document.

Data model

Map data (source of truth): road segments, nodes, turn restrictions and places in a spatial database, partitioned by region; a batch pipeline builds everything served from it.

Tiles (object store + CDN): vector tiles keyed by {version}/{z}/{x}/{y}. Lower zooms are generalised (fewer, simpler roads); empty ocean tiles are shared.

Routing graph (in-memory, per region): nodes and directed edges with length, free-flow speed, road class and turn costs, plus precomputed shortcut edges and node ordering (contraction hierarchies / customisable route planning cells). Loaded into RAM on routing servers from a versioned snapshot.

Live traffic (in-memory key-value): segment_id -> {speed_kmh, confidence, updated_at} per minute, plus historical profiles: typical speed per segment per 15-minute slot of the week, built offline from probe history in a columnar store.

Places index: a search index with text fields and geo-points for geocoding and autocomplete.

High-level design

Drawing the map. The phone computes which tiles cover the screen for its zoom level and fetches them by URL from the CDN. Misses go to the tile store, where a nightly map build pipeline has written versioned vector tiles; the device styles and renders them, so one set of tiles serves light mode, dark mode and every screen density.

Searching. Typing an address goes through the API gateway to the geocoding service, which queries a places index ranked by text match and distance from the user.

Routing. The gateway sends the route request to a routing server that holds the region's road graph in memory. It snaps both points to the nearest road segments and runs a bidirectional search over the precomputed hierarchy, with edge costs taken from the live traffic store (falling back to the historical profile for that time of week). The routing service then applies an ETA model that adjusts the raw sum of segment times for turns, signals and predicted traffic later in the trip.

Traffic. Navigating phones send batches of anonymised GPS speed probes to the probe ingest service, which writes them to a stream. A traffic aggregator map-matches each probe to a road segment, averages speeds per segment per minute with outlier filtering, and writes the result to the live traffic store that routing servers read. During navigation the phone reports progress; the server refreshes the ETA and pushes a reroute if a clearly faster path appears.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Fast routing on a huge graph

Dijkstra explores outward in a circle and touches millions of nodes on a long trip. A* with a straight-line heuristic helps a bit on its own. The big win is precomputation: contraction hierarchies order nodes by importance and add shortcut edges so a bidirectional search climbs to highways and back down, touching a few thousand nodes and answering in about a millisecond. The catch is that shortcuts bake in weights. Customisable route planning splits the graph into nested cells, precomputes the topology once, and recomputes the cell-crossing costs from new edge weights in seconds, which is what makes per-minute traffic updates practical. Very long trips can be split at region boundaries.

From GPS probes to segment speeds

A probe is a noisy point, not a road. The aggregator first map-matches a short trace of consecutive probes from the same anonymous session onto the most likely sequence of segments (a hidden Markov model over nearby candidates works well), which also separates a highway from the frontage road beside it. It then computes the speed on each segment, drops outliers such as parked cars or delivery stops, and keeps a per-minute rolling median per segment with a confidence based on sample count. Segments with too few samples fall back to the historical profile. Partition the stream by geographic cell so each aggregator owns an area and keeps state in memory. Session ids rotate frequently and are dropped after matching, for privacy.

Producing and serving tiles

Tiles follow the standard z/x/y pyramid: zoom z has 4^z square tiles. Pre-render vector tiles for every zoom up to street level, generalising geometry at low zooms so a country-level tile is not megabytes of road detail. Most of the surface is ocean or empty land, and those tiles deduplicate to a handful of shared objects. Because tiles are versioned and immutable, the CDN hit rate is very high; when map data changes, rebuild only the tiles whose bounding boxes intersect the edits and publish a new version. Vector tiles also let the client rotate, tilt and restyle without new downloads, and a few large tiles beat many small ones on mobile networks.

Trustworthy ETAs

Summing current speeds along the route assumes today's traffic will stay put for the whole trip. For a 50-minute drive the last segments are reached 50 minutes from now, so blend live speeds for the near part of the route with historical speeds for the time slot when the car will actually arrive at each segment. Add turn and traffic-light delays. Then train a correction model on completed trips (predicted vs actual arrival) using features like time of day, road mix and weather. During navigation, recompute from the current position every minute or so and only offer a reroute when the saving exceeds a threshold, to avoid flapping between near-equal routes.

Failure modes

• If the traffic pipeline stalls, routing servers keep the last good speeds and, once they are older than a few minutes, fall back to historical profiles; routes stay valid but less accurate.
• If a routing server dies, the load balancer shifts traffic to other replicas of that region; new servers load the graph snapshot before taking traffic.
• If the tile origin is down, the CDN keeps serving cached immutable tiles; only rarely viewed areas fail to load.
• If a bad map release ships (a missing bridge), roll back to the previous graph and tile version, since both are versioned.
• If probe ingest is overloaded, sample probes at the edge; traffic estimates get noisier but the system stays up.

Core algorithm in code

import heapq
import math


def build_grid(n, block_km=0.5):
    """A city grid of n x n intersections. Every 5th street is an arterial (60 km/h),
    the rest are local roads (30 km/h). Real systems load a road graph per region."""
    graph, coords = {}, {}
    for x in range(n):
        for y in range(n):
            coords[(x, y)] = (x * block_km, y * block_km)
            graph[(x, y)] = []
    for x in range(n):
        for y in range(n):
            for dx, dy in ((1, 0), (0, 1)):
                nx, ny = x + dx, y + dy
                if nx < n and ny < n:
                    fast = (dy == 0 and y % 5 == 0) or (dx == 0 and x % 5 == 0)
                    kmh = 60.0 if fast else 30.0
                    graph[(x, y)].append(((nx, ny), block_km, kmh))
                    graph[(nx, ny)].append(((x, y), block_km, kmh))
    return graph, coords


def edge_minutes(u, v, length, free_kmh, traffic):
    return length / (free_kmh * traffic.get((u, v), 1.0)) * 60


def search(graph, src, dst, traffic, heuristic):
    """Dijkstra when heuristic returns 0; A* when it returns an optimistic time bound."""
    best = {src: 0.0}
    prev = {}
    pq = [(heuristic(src), 0.0, src)]
    expanded = 0
    done = set()
    while pq:
        _, t, u = heapq.heappop(pq)
        if u in done:
            continue
        done.add(u)
        expanded += 1
        if u == dst:
            path = [u]
            while path[-1] != src:
                path.append(prev[path[-1]])
            return t, path[::-1], expanded
        for v, length, kmh in graph[u]:
            nt = t + edge_minutes(u, v, length, kmh, traffic)
            if nt < best.get(v, math.inf):
                best[v] = nt
                prev[v] = u
                heapq.heappush(pq, (nt + heuristic(v), nt, v))
    return math.inf, [], expanded


graph, coords = build_grid(40)
src, dst = (2, 3), (33, 31)
MAX_KMH = 60.0


def straight_line(v):                 # admissible: nobody beats a straight line at top speed
    (x1, y1), (x2, y2) = coords[v], coords[dst]
    return math.hypot(x2 - x1, y2 - y1) / MAX_KMH * 60


no_h = lambda v: 0.0
t1, p1, n1 = search(graph, src, dst, {}, no_h)
t2, p2, n2 = search(graph, src, dst, {}, straight_line)
print("free flow  Dijkstra: %.1f min, expanded %d nodes" % (t1, n1))
print("free flow  A*      : %.1f min, expanded %d nodes" % (t2, n2))

# Live traffic: a jam on the arterial the route uses (speed drops to 15% of free flow).
traffic = {}
for a, b in zip(p2, p2[1:]):
    if a[0] == 5 or a[1] == 5 or b[0] == 5 or b[1] == 5:
        traffic[(a, b)] = 0.15
stale = sum(edge_minutes(a, b, 0.5, next(k for v, _, k in graph[a] if v == b), traffic) for a, b in zip(p2, p2[1:]))
t3, p3, n3 = search(graph, src, dst, traffic, straight_line)
print("same route with jam: %.1f min  ->  rerouted: %.1f min (jammed edges on new route: %d)"
      % (stale, t3, sum(1 for e in zip(p3, p3[1:]) if e in traffic)))
print("path start:", p3[:6], "...")

Trade-offs

• Contraction hierarchies answer in milliseconds but bake in weights; cell-based customisable planning absorbs traffic updates quickly at somewhat slower queries.
• Vector tiles shrink storage and allow client-side styling but cost CPU on the device and more complex rendering code.
• Per-minute traffic aggregation gives fresh speeds but costs a large streaming pipeline; longer windows are cheaper but miss sudden jams.
• Keeping the whole regional graph in RAM gives fast routing but costs large, slow-to-start servers that must be loaded from snapshots.
• Using historical profiles for future segments improves long-trip ETAs but can be wrong on unusual days such as holidays or storms.

What a strong answer shows

• Separates the three subsystems (tiles, routing, traffic) and gives each its own scaling story.
• Explains why plain Dijkstra is too slow and how precomputation (hierarchies or cells) fixes it while still allowing traffic updates.
• Designs a streaming pipeline from raw probes to per-segment speeds, including map matching.
• Uses tile pyramids with versioned, immutable URLs and a CDN.
• Treats ETA as a prediction problem using historical and live data.
• Uses numbers (route QPS, probe rate) to justify choices.

Mistakes to avoid

• Running plain Dijkstra on a database-backed graph per request.
• Storing every raw GPS probe in the serving database.
• Rendering tiles on demand for every request instead of pre-building and caching.
• Computing ETA as distance divided by speed limit.
• Ignoring that precomputed shortcuts must be refreshed when traffic changes edge weights.

Follow-ups to expect

• How would you support offline maps? (Download a region's tiles and a compact routing graph to the device.)
• How do you detect a road closure from probe data? (Sudden absence of probes on a normally busy segment plus user reports.)
• How would you add alternative routes? (Penalise edges of the best route and search again, keeping routes that differ enough.)
• How do you route across continents? (Region graphs with a top-level overlay graph of border nodes.)
• How do you protect user privacy in probes? (Rotating session ids, dropping trip start and end points, aggregation thresholds.)

Practice next