Google Maps

Problem Statement

Build a mapping service used by over a billion people. Users expect to see a zoomable, pannable map of the entire planet, search for any address or business, and get directions — all with sub-second latency. Behind the scenes, the system must ingest GPS data from hundreds of millions of devices, match those noisy signals to actual roads, aggregate them into live traffic speeds, and feed those speeds back into the routing engine so that every ETA reflects conditions right now.

This is three systems in a trenchcoat: a tile rendering pipeline (read-heavy, CDN-first), a routing engine (CPU-heavy, graph algorithms), and a real-time traffic pipeline (streaming, stateful). Each has different scaling characteristics.

Requirements

Functional Requirements

Non-Functional Requirements

Scale Estimation

Let's derive the numbers from reasonable assumptions rather than memorizing them.

API Design

GET /tiles/{z}/{x}/{y}.pbf

Response: Protocol Buffer encoded vector tile
Headers:  Cache-Control: public, max-age=86400
          Content-Encoding: gzip

z = zoom level (0–20)
x = column index
y = row index

GET /directions?origin={lat,lng}
               &destination={lat,lng}
               &mode={driving|walking|cycling|transit}
               &departure_time={unix_ts}
               &alternatives={true|false}

Response: {
  routes: [{
    distance_m:    42300,
    duration_s:    2580,
    duration_traffic_s: 3120,
    polyline:      "encoded_polyline",
    steps:         [{ instruction, distance, duration, maneuver }],
    traffic_speed_segments: [{ start_idx, end_idx, speed_category }]
  }]
}

GET /geocode?address={query}&bounds={sw_lat,sw_lng,ne_lat,ne_lng}

Response: {
  results: [{
    place_id:      "ChIJ...",
    formatted:     "Dubai Mall, Dubai, UAE",
    location:      { lat: 25.1972, lng: 55.2796 },
    types:         ["shopping_mall", "point_of_interest"]
  }]
}

POST /probes  (batched, every 5-15 seconds)

Body: {
  device_id:  "hashed_anon_id",
  probes: [
    { lat, lng, speed_mps, heading_deg, accuracy_m, ts },
    { lat, lng, speed_mps, heading_deg, accuracy_m, ts },
    ...
  ]
}

High-Level Architecture

Three subsystems with different scaling profiles: a CDN-heavy tile pipeline, an in-memory routing engine, and a streaming traffic pipeline. They share the spatial database but are otherwise decoupled.

The red pipeline at the bottom is the real-time traffic system: GPS probes flow in from phones, get map-matched to road segments, aggregated into per-segment speeds, and fed back into the routing engine via CRP metric updates. The dashed amber line shows this feedback loop — updated edge weights flow from the aggregator back into the in-memory road graph.

Deep Dive — Contraction Hierarchies

The routing engine's core algorithm. Dijkstra's algorithm works for city-scale graphs, but for a cross-country route (Dubai to Istanbul), it would explore millions of nodes — seconds of compute per query. We need something that exploits the structure of road networks. Enter Contraction Hierarchies (CH).

The Algorithm in Two Phases

CH works in two phases: an expensive offline preprocessing step (run once, takes hours) and a blazing fast online query step (runs per request, takes milliseconds).

Phase 1 — Preprocessing: Node Contraction

Rank every node by "importance." A highway interchange serving 50,000 cars/day is important. A dead-end residential cul-de-sac is not. The ranking uses heuristics: how many shortcuts would contracting this node create? How many neighbors does it have? How deep in the hierarchy are its neighbors?

Then, contract nodes from least important to most important. "Contracting" a node means: remove it from the graph, and for every pair of its neighbors (u, v), check if the shortest path from u to v went through this node. If yes, add a shortcut edge u→v with weight = weight(u→node) + weight(node→v).

Phase 2 — Query: Bidirectional Upward Search

To find the shortest path from S to T, run two simultaneous Dijkstra searches:

• Forward search from S — but only explore edges that go upward in the hierarchy (to more important nodes).
• Backward search from T — same rule, only go upward.

The two searches meet at some high-importance node in the middle — typically a highway node. The shortest path passes through this meeting point. Because both searches only go upward, they each explore very few nodes — typically ~500 nodes per direction, for a total of about 1,000 node relaxations. Compare that to millions for plain Dijkstra.

Unpacking Shortcuts

The path found by the query uses shortcut edges. To get the actual turn-by-turn directions, you unpack each shortcut recursively: a shortcut A→C was created when B was contracted, so it represents A→B→C. Shortcut B→D might unpack to B→X→D, and so on until you have the full path with every intersection.

Handling Live Traffic — CRP Integration

Standard CH has a problem: the preprocessing assumes static edge weights. If traffic changes, you'd need to re-preprocess the entire graph — which takes hours. Customizable Route Planning (CRP) solves this by separating concerns:

• Metric-independent preprocessing: Partition the graph into cells based on topology. Precompute which boundary nodes connect cells. This depends on road topology only, not travel times. Run once.
• Metric customization: When traffic changes, update edge weights and recompute only the cross-cell boundary distances. This takes seconds, not hours.

The real-time traffic pipeline (GPS probes → map matching → aggregation) produces updated segment speeds every 30–60 seconds. These feed into the CRP customization step, which updates the routing graph's edge weights in near real-time. The feedback loop closes: live traffic → updated weights → better ETAs.

Key Design Decisions & Tradeoffs

Vector Tiles vs Raster Tiles

Contraction Hierarchies vs Plain Dijkstra / A*

Road Graph Storage: In-Memory vs On-Disk

Tile Pre-rendering Strategy

Traffic Aggregation: Median vs Mean

What Can Go Wrong

Interview Tips

Similar Problems

Evolution

How this design grows from MVP to planet-scale.