Design Google Maps
Problem
Design a mapping and navigation service. Users can view a map of anywhere on Earth at any zoom level, search for an address or place, and get driving directions with an ETA that accounts for live traffic. During navigation, the app gives turn-by-turn instructions and reroutes when the user goes off course or traffic changes. The service has 1 billion monthly users and handles about 5 billion route requests per month.
- Which travel modes are needed: driving only, or also walking, cycling, and transit?
- Do we render map imagery on the server, or send vector data for the client to render?
- How fresh must traffic data be, and where does it come from?
- Should the app work offline for downloaded regions?
- How accurate must ETAs be, for example within 10% for 90% of trips?
- Is place search (restaurants, businesses) in scope, or only addresses?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Display a pannable, zoomable map of the world.
- Geocode addresses and place names to coordinates, and coordinates back to addresses.
- Compute the fastest route between two points with an ETA using live traffic.
- Provide turn-by-turn navigation with automatic rerouting.
- Show live traffic conditions as colored road overlays.
- Support offline maps for downloaded regions.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- 5 billion route requests per month: about 2,000 per second on average and 10,000 at peak.
- Map tile requests far exceed routes: assume 500,000 per second at peak, nearly all served from a CDN.
- Route computation under 1 second at p99 for cross-country trips.
- The road graph has about 1 billion nodes and 2 billion edges worldwide.
- Traffic updates reflected in ETAs within 2 minutes.
- Map data across zoom levels is tens of terabytes as vector tiles, plus petabytes of satellite imagery.
The map is prebuilt into vector tiles at every zoom level and served from a CDN, with the client rendering them. Routing runs on an in-memory road graph preprocessed into a multi-level partition (customizable route planning), with live traffic speeds folded into the precomputed cell shortcuts every minute, so queries take milliseconds even across continents. Navigating phones send anonymized speed samples that feed the traffic pipeline, which in turn updates edge weights and the traffic overlay.
Loading diagram...
View the map. The app computes which tiles cover the viewport at the current zoom (/tiles/{z}/{x}/{y}) and requests them from the CDN. Vector tiles contain roads, labels, and polygons, which the client styles and renders. Traffic overlay tiles are requested separately with a short cache lifetime.
Search. The user types an address. The geocoding service parses it into components, looks them up in the address index, and returns coordinates and a formatted address ranked by proximity to the map center.
Route. The app sends origin, destination, and mode. The routing service snaps each point to the nearest road segment, runs a bidirectional search over the multi-level overlay graph using current traffic weights, unpacks the shortcut edges into the real path, and returns the polyline, maneuvers, and ETA.
Navigate. The app follows the route locally and sends its position every few seconds to the navigation session service. If the user leaves the route or a significantly faster route appears due to new traffic, the service computes a new route and pushes it to the app.
Learn traffic. Speed samples from navigating phones are map-matched to road segments, aggregated per segment per minute, and published as current speeds.
Prebuilds and serves map tiles for every zoom level.
- An offline build pipeline (Spark) that cuts map data into vector tiles (Mapbox Vector Tile format), stored in object storage and served through a CDN.
Data Model
- Tile key
z/x/ymaps to a compressed protobuf of layers (roads, water, buildings, labels) simplified for that zoom.
Scalability
At zoom 0 one tile covers the world; each zoom level quadruples tile count. Rather than building all tiles at high zoom (trillions), empty ocean tiles are skipped and high-zoom tiles are generated lazily on first request, then cached. Popular tiles have near 100% CDN hit rates.
Tradeoffs
Vector tiles are much smaller than raster images, scale smoothly between zooms, and let the client restyle (dark mode, language) without new downloads. Raster tiles are simpler for old devices and are kept only for satellite imagery.
Computes fastest paths on the road graph.
- C++ service holding the road graph in memory, preprocessed with customizable route planning: the graph is split into nested cells, and shortcut costs between each cell's boundary nodes are precomputed.
Diagram
Loading diagram...
API
GET /route?from=&to=&mode=driving&departAt=returns{ routes: [{ polyline, distanceM, durationS, maneuvers }] }with up to three alternatives.
Scalability
The preprocessed global driving graph fits in a few hundred gigabytes, so it is replicated on a fleet of large memory machines, or partitioned by continent since most routes stay within one. A query visits only thousands of nodes instead of millions, finishing in milliseconds.
Tradeoffs
Plain Dijkstra or A* on a graph this size would explore millions of nodes for a long route and take seconds. Contraction hierarchies answer queries even faster, but their preprocessing depends on edge weights and takes hours, so live traffic could not be applied. Customizable route planning builds its partition once from the road topology and recomputes cell shortcuts for new traffic weights in seconds.
Turns raw GPS probes into current speeds per road segment.
- Kafka for probes, Flink for map matching and per-segment aggregation, and a key-value store for current speeds.
Data Model
segment_speed(segment_id, minute, median_speed_kph, sample_count)historical_speed(segment_id, weekday, time_of_day, typical_speed_kph)
Scalability
Probes are partitioned by region. Map matching uses a hidden Markov model over nearby segments. Segments with too few live samples fall back to historical speeds for that time of week.
Tradeoffs
ETAs blend live speeds for the first part of the route with historical predictions for later parts, since current traffic 40 minutes ahead is a poor predictor. Probes are anonymized and trimmed at trip start and end to protect privacy, which loses a little data near home locations.
Converts between addresses and coordinates.
- An address parser (statistical model trained on international formats) plus a search index of addresses and places such as Elasticsearch.
API
GET /geocode?q=&near=returns candidates with coordinates.GET /reverse?lat=&lng=returns the nearest address.
Scalability
The index is replicated per region. Results are cacheable since addresses rarely change.
Tradeoffs
Biasing results toward the viewport makes "Main Street" resolve to the nearby one, at the cost of occasionally surprising users searching far away; showing several candidates mitigates this.
Keeps state for active navigation and decides when to reroute.
- Stateful service with sessions sharded by session id, using WebSocket or periodic HTTP for updates.
Scalability
Most guidance happens on the device; the server only receives periodic positions and checks traffic along the remaining route every minute, so per-session load is light.
Tradeoffs
Doing turn-by-turn on the client keeps navigation working through tunnels and dead zones. The server only proposes a reroute when the time saving exceeds a threshold, to avoid flip-flopping between similar routes.