Skip to content

Google Maps#

Problem statement (interviewer prompt)

Design Google Maps: serve global vector + raster tiles at sub-100ms p99, run point-to-point routing with live traffic ETAs in <500ms, handle place search + geocoding, and ingest billions of anonymised GPS probes per day to estimate live speeds.

flowchart LR
  U([User])
  TILES[Map Tile Service]
  ROUTE[Routing Service]
  PLACES[Places / Geocoder]
  TRAFFIC[Traffic Service]
  ETA[ETA Engine]
  U --> TILES
  U --> ROUTE --> ETA
  U --> PLACES
  TRAFFIC --> ROUTE

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class U client;
    class TILES,ROUTE,PLACES,TRAFFIC,ETA service;

flowchart TB
  subgraph Clients
    BR
    APP([Mobile / Auto])
    EMB[Embed API]
  end

  subgraph Edge
    CDN
    GW
  end

  subgraph Tiles[Map Tiles]
    TS[Tile Service]
    RAS[Raster tiles 256/512]
    VEC[Vector tiles]
    Z[Zoom levels 0-22]
    PROJ[Mercator projection]
    CACHE[(Tile cache on CDN)]
  end

  subgraph Data[Map Data]
    OSM([Ground truth ingest<br/>sat imagery, OSM, vendors])
    EDIT[Editor + ops tools]
    BUILD[Tile build pipeline]
    GEO[(Spatial DB - S2 cells)]
  end

  subgraph Places[Places & Geocoding]
    PSVC[Places Service]
    GEOC[Geocoder]
    REV[Reverse geocoder]
    PIDB[(POIs DB)]
    SRCH[Place search]
  end

  subgraph Route[Routing & ETA]
    R1[Route Service]
    GRAPH[(Road graph<br/>contraction hierarchies)]
    CH[CH preprocessor]
    DIJK[A* / Dijkstra]
    ETA[ETA model]
    TRAF[[Live traffic stream]]
    HIST[Historical traffic]
  end

  subgraph Live[Live signals]
    PROBES([GPS probes from phones])
    SPEED[Speed estimation]
    INCID[Incidents / closures]
  end

  subgraph Nav[Turn-by-turn navigation]
    SES[Nav session]
    REROUTE[Reroute on miss]
    LANE[Lane guidance]
    VOICE[Voice TTS]
  end

  Clients --> CDN --> GW
  GW --> Tiles --> CACHE
  Tiles -. miss .-> TS
  TS --- Data
  GW --> Places --> PIDB
  GW --> Route --> GRAPH
  Route --> DIJK
  Route --> ETA
  TRAF --> ETA
  PROBES --> SPEED --> TRAF
  HIST --> ETA
  Route --> Nav
  Live --- Route

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class APP,PROBES client;
    class EMB,TS,RAS,VEC,Z,PROJ,EDIT,BUILD,PSVC,GEOC,REV,SRCH,R1,CH,DIJK,ETA,HIST,SPEED,INCID,SES,REROUTE,LANE,VOICE service;
    class CACHE,GEO,PIDB datastore;
    class TRAF queue;
    class OSM compute;

Tiles#

  • Pre-rendered raster or thin vector tiles, served via CDN.
  • Tile key = (z, x, y). Higher z = closer zoom; tile count quadruples per level.

Routing#

  • Road network as a graph; preprocessed with Contraction Hierarchies for fast queries.
  • Online A* with edge-weight = f(distance, current_speed, predicted_speed).
  • For long routes: hierarchy of "important" edges (highways pre-computed).

ETA model#

  • Inputs: distance, speed limits, live traffic, weather, historical patterns, time of day.
  • ML regressor; updated minutely.

Live traffic#

  • GPS probes from millions of phones (privacy-aggregated).
  • Map-match probes to road segments; compute speed.
  • Detect incidents (cluster of slowdowns).

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD CDN edge caching for static assets cdn
HLD Geo indexing Geohash, Quadtree, S2, H3, R-tree geo-indexing

Quick reference#

Functional#

  • Render map at any zoom.
  • Place search + geocoding (address ↔ lat/lng).
  • Driving/transit/walking route with ETA.
  • Live traffic + incidents.
  • Turn-by-turn navigation.
  • Reviews, photos, Street View.

Non-functional#

  • p99 tile fetch < 100 ms (cached).
  • Route < 500 ms for typical city query.
  • Multi-region, 99.99% availability.

Capacity#

  • Trillions of tiles served / yr; petabytes of map data.
  • Tens of billions of probe pings/day.

Schema (abstract)#

  • Tile = (z,x,y) → image / vector blob in object store + CDN.
  • POI table sharded by S2 cell.
  • Road graph stored as adjacency lists per region.

Trade-offs#

  • Vector tiles lighter on bandwidth + stylable at client; raster simpler.
  • CH preprocessing expensive but cuts query time by 1000×.
  • Probe data privacy: aggregate, decay, anonymize.

Refs#

  • "Customizable Route Planning" (Microsoft Research) on CH variants.
  • S2 Geometry library docs.
  • Google Maps engineering talks; "How Google Maps draws roads".
  • ByteByteGo "Design Google Maps".

FAQ#

How does Google Maps serve tiles globally in under 100 ms?#

Map tiles are pre-rendered or vectorized and cached aggressively in a CDN. Clients request tiles by zoom, x, y coordinates and the nearest edge POP serves a cache hit in single digit milliseconds.

How does Google Maps compute routes in under 500 ms?#

The graph is preprocessed with contraction hierarchies or customizable contraction hierarchies. This collapses long sequences of edges so even cross country queries finish in milliseconds at runtime.

How is real time traffic integrated into ETA?#

Anonymized GPS probes from billions of devices feed a traffic service that maintains current speed per road segment. The routing engine consumes these speeds when computing ETA and rerouting.

How does Google Maps geocode and find places?#

An inverted index over place names, addresses, and points of interest is biased by location and personal history. A ranker scores candidates by relevance, popularity, and distance.

How does turn by turn navigation work offline?#

The client downloads a region's road graph and tiles. The same routing algorithm runs locally with cached speed profiles, falling back to last known traffic when connectivity is lost.

Further reading#

Curated, high-credibility sources for going deeper on this topic.

  • Proximity Service: shared geo-indexing substrate
  • Uber: applies the same geohash + quadtree primitives
  • Geofencing: polygon containment queries
  • CDN: tile delivery at edge POPs

Video walkthrough

Design Google Maps: Micro Graphs + GeoHash Segments : via System Design Walkthrough