Design Google Maps

A mapping service shows a map at any zoom level, finds routes between two places, and estimates travel time using current traffic. It combines three separate sub-systems: rendering and delivering map imagery, computing routes on a road graph with hundreds of millions of edges, and ingesting location data to estimate traffic.

Requirements

Functional

• Display a map for any viewport and zoom level, with panning and zooming.
• Compute a route between an origin and destination (driving, walking, cycling).
• Return an estimated time of arrival (ETA) that accounts for traffic.
• Turn-by-turn navigation with re-routing when the user leaves the route.
• Search for places (covered lightly, see proximity service).

Non-functional

• Low latency: map tiles appear within a fraction of a second, routes are returned within about a second.
• High availability of map display and routing.
• Accuracy: routes must obey road rules (one-way streets, turn restrictions).
• Scalability to hundreds of millions of users and billions of location updates.
• Efficient mobile data and battery use.
• Traffic data may be eventually consistent. Static map data changes slowly.

Estimation

Assumptions: 1 billion monthly users, 100 million daily active users (DAU) of which 20 million use navigation, and each navigation session averages 20 minutes.

Map tiles. The world map is pre-rendered into square tiles (commonly 256 x 256 or 512 x 512 pixels). At zoom level z the world is divided into 2^z x 2^z tiles, so zoom 0 is 1 tile and zoom 21 is about 4.4 trillion tiles. Most of them are ocean or empty, and detailed zoom levels are generated only where data exists.

• A viewport on a phone needs roughly 6 to 20 tiles. Assume 10 tiles per map view, 30 map views per DAU per day: 100M x 30 x 10 = 30 billion tile requests/day, about 350,000 per second average.
• At about 20 KB per tile (vector tiles are often smaller), that is about 7 GB/s average egress. This is served almost entirely by a CDN.

Location updates. Navigating users send a GPS point every 5 seconds. Total navigation time is 20M sessions x 20 min = 400M minutes/day, so average concurrency is 400M / 1,440 minutes = about 280,000 navigating users. Assume peak concurrency of 3x, about 830,000 users. Updates: 830,000 / 5 s = about 166,000 updates/s at peak. At about 100 bytes each, that is roughly 17 MB/s inbound. Batching several points per request reduces the request count.

Road graph. The global road network has on the order of hundreds of millions of road segments. At about 100 bytes per edge with geometry and attributes, this is tens of GB, which fits in memory on a single large machine per region or per full graph.

What the numbers imply

• 350,000 tile requests/s (about 1 million at a 3x peak) is only viable with a CDN. At a 99% hit ratio the origin sees about 3,500 requests/s and 70 MB/s, which is manageable. At 90% it would see 10x more, so the hit ratio is a design target, achieved with long TTLs and versioned URLs.
• Pre-rendering all zooms is infeasible: zoom levels 0 to 14 hold about 358 million tiles (about 7 TB at 20 KB each as an upper bound, less after skipping ocean). Pre-generate up to about zoom 14 to 16 for populated areas, generate deeper levels on demand, and let clients over-zoom vector tiles.
• 166,000 location updates/s is about 17 MB/s, small for Kafka, but partitions are needed for consumer parallelism. Uploading a batch every 15 seconds instead of each point cuts request count 3x.
• Assume 100 million route requests/day, about 1,200/s average and 4,000/s peak. At about 10 ms of CPU per query, that is about 40 cores. Routing is CPU-bound and read-only, so it scales with replicas.
• The graph (10^8 to 10^9 edges at 100 B) is 10 to 100 GB, so each routing server holds its region entirely in RAM and there is no disk seek per edge.

API design

GET  /v1/tiles/{z}/{x}/{y}.pbf                         -> map tile (vector) 
POST /v1/routes  { origin, destination, mode, departAt, alternatives } 
                                                        -> { routes: [ { polyline, distance, etaSeconds, steps[] } ] }
POST /v1/locations   [ { userId, lat, lng, speed, heading, ts } ]   -> 202
WS   /v1/navigation/{sessionId}                         -> re-route and ETA updates

The tile URL is deterministic from z/x/y, so tiles are cacheable at the CDN and in the client with long TTLs and a version identifier in the path. Location updates return 202 because they are processed asynchronously.

Data model

Edge record: edge_id, from_node, to_node, length, road_class, speed_limit, direction, restrictions. Node record: node_id, lat, lng.

High-level design

graph TD
    U["Client"] -->|"tiles"| CDN["CDN"]
    CDN --> TS["Tile service"]
    TS --> TST[("Tile storage")]
    U -->|"route request"| GW["API gateway"]
    GW --> RS["Routing service"]
    RS --> GS["Graph shards (in memory)"]
    RS --> TR[("Traffic store")]
    RS --> ES["ETA service"]
    U -->|"location updates"| LS["Location service"]
    LS --> K["Kafka: location stream"]
    K --> MM["Map matching + traffic aggregator"]
    MM --> TR
    K --> ARCH[("Location archive")]
    BATCH["Map data pipeline"] --> TST
    BATCH --> GS

Components:

• Tile service and CDN. Serve pre-computed tiles. The CDN takes almost all traffic.
• Map data pipeline. Offline batch jobs ingest map source data, build tiles for all zoom levels and the routing graph, and publish new versions.
• Routing service. Finds paths using the graph, and combines traffic for edge weights.
• Location service. Accepts location batches and writes them to a log (Kafka).
• Map matching and traffic aggregator. Snaps GPS points to road segments and computes average speed per segment over recent windows.
• ETA service. Sums predicted segment travel times along the route.

Deep dive

1. Map tile serving

Rendering maps on demand for each request is too expensive, so tiles are pre-generated.

• Raster tiles are images (PNG or JPEG). Simple for clients but larger, and labels rotate poorly.
• Vector tiles contain geometry and attributes in a compact binary format (for example Protocol Buffers). The client renders them. They are smaller, allow smooth zoom, rotation, and style changes, and reduce the number of stored variants. Rendering costs client CPU and GPU.

Each tile is immutable per map version, so it is cached with long TTLs and addressed by version. When the map updates, a new version is published and clients request new URLs. Tiles of popular areas are always in CDN cache. For rarely viewed areas or zoom levels, tiles may be generated on the first request and then cached. Clients cache tiles locally and prefetch tiles surrounding the viewport and along a planned route, which also enables offline use.

2. Route computation

Model the road network as a weighted directed graph: nodes are intersections, edges are road segments, and weights are travel time or distance.

• Dijkstra's algorithm finds the shortest path but explores nodes in all directions around the origin. On a continental graph, it visits millions of nodes per query, which is too slow.
• A* adds a heuristic, such as straight-line distance divided by maximum speed, to bias the search toward the destination. It reduces the search area but is still slow for long routes.
• Bidirectional search runs from both ends and stops when the searches meet.
• Hierarchical methods such as contraction hierarchies preprocess the graph offline. They rank nodes by importance and add shortcut edges that bypass unimportant nodes, so a query searches mostly upward through important roads. Queries become orders of magnitude faster than plain Dijkstra, at the cost of preprocessing time and extra memory. The weakness is that shortcuts encode the weights used in preprocessing, so changing weights for live traffic needs either re-customization of the weights on the fixed hierarchy structure or a different technique.
• Partitioning the graph into cells with a small boundary, then precomputing distances between boundary nodes, gives another route: queries mix a precomputed overview of far cells with detailed search near the endpoints.

Practical design: a routing service holds the graph in memory. Long routes use a hierarchy (highways form the top level), and local search runs near the origin and destination. The graph is split geographically into shards, and a route crossing shard boundaries uses the boundary overview. The service returns several alternatives by penalizing edges of the first route and searching again.

3. Live traffic and ETA

1. Navigating clients send location points to the location service.
2. The stream processor map-matches each point: it assigns the GPS position (which has error of several meters) to the most likely road segment, using the heading and continuity with earlier points.
3. It aggregates speeds per segment over a sliding window (for example the last few minutes), and writes the current speed to the traffic store. Segments with few samples fall back to historical averages for that time of week.
4. The routing service uses travel_time = length / current_speed as the edge weight.

ETA for the whole route sums segment travel times. A naive sum uses current conditions everywhere, but traffic changes by the time the driver arrives at a distant segment. Better estimates use a time-dependent model: the predicted speed of a segment at the expected arrival time at it, taken from historical patterns blended with current conditions. Only recent traffic data is kept hot, and older data is archived for building historical profiles offline.

4. Re-routing and navigation sessions

The client compares its position with the route polyline. When it deviates by more than a threshold or the ETA of the current route becomes clearly worse than an alternative, the client or server requests a new route from the current position. A session channel (WebSocket, see WebSockets, SSE, and long polling) lets the server push traffic incidents. To limit load, the server re-evaluates active routes periodically instead of continuously, and only sends changes above a threshold.

5. Thresholds and consistency choices

• Tile caching. Tiles are immutable per version, so serve them with Cache-Control: max-age=31536000, immutable under a versioned path. Only the small manifest that points to the current version has a short TTL, for example 5 minutes. Warm the CDN with popular tiles before switching versions to avoid an origin stampede.
• Routing choice. Plain Dijkstra visits millions of nodes for a long route, which takes seconds. A contraction hierarchy query visits hundreds to a few thousand nodes and takes about a millisecond, but preprocessing a continental graph takes minutes to hours. Customizable variants split the structure from the weights, so applying new traffic weights takes seconds to minutes. Chosen: a hierarchy for the static structure, plus live weights through re-customization or a short-lived overlay of penalties for closures.
• Traffic aggregation. Use a 3 to 5 minute sliding window per segment, publish every 1 to 2 minutes, and require a minimum number of distinct probes (for example 5) before trusting live speed, or fall back to the historical speed for that time of week. Set the traffic store TTL to about 10 minutes so stale speeds disappear. Partition the stream by segment or coarse cell, and pre-aggregate in each partition so that a busy highway does not overload one consumer.
• Consistency. Traffic is eventually consistent, with 1 to 2 minutes of lag. The graph version is switched atomically per routing server, and a route response carries the version used, so a re-route with a different version is detectable.

Bottlenecks and scaling

• Tile traffic. CDN with long TTLs, client caching, vector tiles for size.
• Routing compute. Replicate stateless routing servers with the graph loaded in memory. Route queries are read-only, so replicas scale linearly. Cache routes between popular origin-destination pairs at coarse granularity.
• Graph updates. Road closures and new roads arrive continuously. Build a new graph version offline, distribute it, and switch atomically. Short-lived closures are handled by a dynamic overlay of edge penalties.
• Location ingestion. Partition the log by geographic cell or segment (see sharding and partitioning), so a stream processor aggregates a segment's data locally. Batch client uploads and shed low-priority data under load.
• Privacy. Location histories are sensitive. Anonymize, aggregate, and set retention limits.
• Failure. If traffic data is missing, routing degrades to static speeds. If a routing shard fails, replicas serve the region.

Failure modes

• CDN region or provider degraded. Origin load can jump 10 to 100x. Use an origin shield tier and request coalescing so that a single miss per tile hits storage, and rely on client tile caches so maps already viewed still render.
• Traffic pipeline lag or outage. Routing uses historical speeds, so ETAs are less accurate but routes still work. Show that traffic is unavailable rather than showing stale data as current.
• At 10x scale. Tile traffic of 3.5 million requests/s is again absorbed by the CDN if the hit ratio holds, but new-version rollouts risk cold-cache stampedes, so roll out gradually. Location updates of 1.7 million/s need 10x more partitions and stream workers. The graph itself barely grows, so routing scales by adding replicas.

Trade-offs and follow-up questions

• Raster versus vector tiles: simplicity versus bandwidth and flexibility.
• Preprocessing-heavy routing algorithms are fast but make live-traffic weights harder to apply.
• Traffic freshness versus stability: too-reactive ETAs cause flapping between routes.
• How would offline maps work? Download vector tiles and a compact graph for a region, and route on the device.
• How would multi-modal routing (transit) change the design? The graph includes time-table edges with departure times, so the search is time-dependent.
• How to find nearby places along the route? See Design a proximity service and geospatial indexing.
• How do you apply live traffic with contraction hierarchies? Use customizable hierarchies, which re-weight shortcuts in seconds to minutes on the fixed structure, or use a hierarchy for the static part plus a bounded search on affected edges.