Design Google Maps: Tiles, Routing, and Real-Time Traffic

"Design Google Maps" hides three different systems behind one blue app icon. There's a rendering system that paints the world at every zoom level, a routing engine that finds the fastest path across a 50-million-node road graph in under a millisecond, and a data pipeline that turns billions of anonymous GPS pings into live traffic. Each has its own bottleneck, its own datastore, and its own reason not to use the obvious textbook answer.

The interview reward comes from separating those subsystems cleanly and knowing where the naive design breaks. Dijkstra is the "correct" shortest-path algorithm and it is completely unusable here. A CDN gives you a 99% hit rate on tiles for free, but only because you made a specific rendering choice upstream. This walks the standard rubric — requirements, capacity, architecture, then deep dives — and shows why Maps makes the calls it does.

What does Google Maps actually have to do?#

Strip the product down to the operations a client can request:

• Render the map. Given a viewport (lat/lng bounds + zoom), return the imagery to draw it.
• Route between two points. Given origin, destination, and a travel mode, return the fastest path and its ETA, accounting for current traffic.
• Search for places. Given a text query and a location ("coffee near me"), return ranked nearby points of interest (POIs).
• Show live traffic. Color road segments by current speed and reroute when conditions change.

The non-functional bounds are what make it hard. Tile rendering must feel instant, so p99 for a tile fetch should sit under ~50ms. Routing needs a fresh answer in a few hundred milliseconds end-to-end even though the underlying graph spans continents. Traffic should be no more than a few minutes stale. And the whole thing has to survive one billion monthly users without the cost of serving static imagery bankrupting you.

Capacity estimation: where the money goes#

Put real numbers on it. Assume 1B monthly active users, each opening Maps about 3 times a day. A session loads roughly 40 tiles as the user pans and zooms, and triggers about 0.2 route computations (most sessions are "where am I / what's around me," not navigation).

Those two workloads want opposite treatment. Tiles are static and identical for every user, so a global CDN absorbs 99%+ of them — the origin sees maybe 10–50K/sec despite the millions at the edge. That is the whole reason serving imagery to a billion people is affordable.

Routing is the expensive path: each request is CPU-bound and needs the road graph resident in RAM. At ~7K/sec average you size a fleet of roughly 1,000–2,000 routing servers, each holding one partitioned shard of the graph in memory. The asymmetry — cheap fan-out reads, costly compute — drives every architecture decision below.

High-level architecture#

Four largely independent subsystems sit behind an API gateway:

The subsystems are decoupled on purpose: a spike in navigation traffic must not degrade tile serving, and the traffic pipeline updates edge weights asynchronously so a slow map-matching job never blocks a live route request. The only tight coupling is the routing fleet reading fresh edge weights that the traffic pipeline produces.

Serving the map: the tile pyramid#

The world is flattened with the Web Mercator projection and recursively cut into a pyramid of 256×256-pixel tiles. Each tile is addressed by (z, x, y) — z is the zoom level (z=0 is the entire planet in one tile, z≈20 is street level), and x, y are the grid coordinates at that zoom. Every zoom quadruples the tile count, so level z holds 4^z tiles.

Tiles are pre-rendered by a batch MapReduce job whenever the underlying imagery updates, then stored in blob storage keyed by (z, x, y) and pushed to the CDN. The key decision is raster vs vector:

Vector tiles (the Mapbox Vector Tile format) win at higher zooms because the client draws them. Rotating the map, switching to dark mode, or re-labeling in another language happens on-device without re-fetching — one download serves many visual states, which is why the CDN hit rate stays near 100% and origin traffic stays tiny.

Routing: why Dijkstra loses and CRP wins#

Textbook shortest path is Dijkstra, at O((V+E) log V). On a graph with ~50M nodes it settles into seconds-to-minutes per continental query because it explores outward in all directions. A* with a good heuristic — great-circle distance divided by max road speed — prunes the search toward the goal and roughly halves the work, but it's still far too slow at planet scale.

The trick is precomputation. Contraction Hierarchies (CH) rank nodes by importance and "contract" the unimportant ones one at a time, inserting shortcut edges that preserve exact shortest-path distances. A query then runs a bidirectional Dijkstra over this hierarchy and finishes a continent-length route in under 1ms.

CH has one fatal flaw for Maps: it bakes edge weights into the shortcuts, so a traffic change means recomputing the hierarchy. Google uses Customizable Route Planning (CRP), a CH variant that separates the graph topology (the partition structure) from the edge weights. A traffic update only recomputes weights inside the affected cells — the topology is untouched — so live-traffic recustomization runs in seconds instead of hours.

Sharding a graph where paths cross boundaries#

The 50M-node graph doesn't fit on one server, and shortest paths ignore shard lines. You partition geographically with a multi-level graph partitioner (METIS or KaHIP) that minimizes the number of edges cut between partitions — effectively a quadtree-style recursive split. Each shard holds its partition plus an overlay of boundary nodes linking to neighbors. A within-shard query runs locally; a cross-shard query does a two-level search: route from the source to its partition boundary, hop across the overlay graph of boundary nodes, then descend into the destination partition. Because CRP nests these partitions across multiple levels, a continent-spanning query only touches on the order of O(log N) cells instead of loading the whole planet.

Real-time traffic and place search#

Live traffic is a streaming pipeline. Opted-in Android devices emit anonymized GPS pings; these are de-identified and buffered in Kafka. A Flink job performs map-matching — snapping each noisy ping onto the correct road segment using a Hidden Markov Model to disambiguate parallel roads, the genuinely hard part at scale. Per-segment speeds (median over a 5-minute sliding window) land in a traffic KV store keyed by segment_id. The routing layer picks these up through CRP's per-cell customization step every few minutes. Segments with too few probes fall back to a historical speed profile bucketed by hour-of-week, so a quiet country road still gets a sane ETA.

Place search combines text and geography. POIs live in an inverted index (Elasticsearch/Lucene) with text fields (name, category, aliases) scored by BM25, plus a geo-point field indexed as a BKD tree or geohash. A query runs a text match and a bounding-box geo-filter around the user, then reranks the top candidates by text_relevance × distance_decay × popularity. Hot queries like "coffee near me" are precomputed per H3 grid cell and cached in Redis for sub-5ms responses. The index is sharded by region — a Paris query never scans Tokyo — and replicated for throughput.

How this shows up in interviews#

Interviewers use Maps to see whether you can hold several unrelated subsystems in your head at once and pick the right tool for each. The strongest signals: naming the CDN + vector-tile combination and explaining why the hit rate is near-perfect; rejecting Dijkstra out loud and reaching for a precomputed hierarchy; and separating topology from weights so traffic updates stay cheap.

Common traps to avoid: proposing to route with live Dijkstra ("it's the shortest-path algorithm") without acknowledging it can't hit the latency bound; storing raster tiles and then wondering why egress is enormous; and treating traffic ingestion as a synchronous write into the routing graph rather than an asynchronous pipeline feeding a recustomization step. If time is short, spend it on routing and tiles — those are where the non-obvious decisions live.

Maps shares DNA with other feed-and-fan-out designs. If you want contrast on how different products resolve the read-heavy-vs-write-heavy tension, compare it with Design Netflix and Design Spotify, and with the real-time delivery problems in Design Discord and Design Slack.

Further learning#

• Google Maps System Design Interview Question — codeKarle's walkthrough of tile serving, routing, and the traffic pipeline, a good companion to the structure above.
• Practice this topic on YeetCode — step through the requirements, capacity math, and deep dives interactively.

FAQ#

Why can't Google Maps just use Dijkstra for routing?#

Dijkstra is correct but explores the graph in every direction, so on a ~50M-node road network a continental query takes seconds to minutes — far beyond an interactive latency budget. Maps precomputes a shortcut hierarchy (Customizable Route Planning, a Contraction Hierarchies variant) so the live query is a bidirectional search over a much smaller structure that returns in under a millisecond. Dijkstra still runs under the hood, but only on the contracted hierarchy, not the raw graph.

What is the difference between raster and vector map tiles, and why does it matter?#

Raster tiles are pre-rendered images: the server bakes in the styling and labels, so any change (rotation, dark mode, a different language) needs a fresh download. Vector tiles ship the raw geometry and are drawn by the client's GPU, so one ~20KB tile can be restyled, rotated, and re-labeled on-device with no new request. That drastically cuts CDN and origin load, which is why vector tiles dominate at higher zooms and keep the tile hit rate near 100%.

How does live traffic get into the routing graph so quickly?#

Anonymized GPS pings from opted-in devices flow through Kafka into a Flink map-matching job that snaps each ping onto a road segment with a Hidden Markov Model. Median segment speeds over a rolling 5-minute window are written to a traffic KV store. CRP separates the graph topology from its edge weights, so a traffic update only recomputes weights inside the affected cells — a "customization" step that runs in seconds every few minutes rather than rebuilding the whole hierarchy.

How much traffic does serving map tiles actually generate?#

At 1B users opening Maps ~3 times a day and loading ~40 tiles per session, that's roughly 120 billion tile requests per day, or about 1.4M/sec on average and 3–5M/sec at peak. At ~20KB per compressed vector tile that's around 28 GB/s of egress. Because tiles are static and identical for everyone, a global CDN absorbs 99%+ of it and the origin sees only tens of thousands of requests per second.

How do offline maps work without a network connection?#

A downloaded region bundles vector tiles as an MBTiles/SQLite blob (tens of MB per city), a per-region CRP partition containing the topology plus its customization weights (roughly 50–200MB per country), and a compact prebuilt Lucene index over local POIs. On-device, a lightweight engine runs bidirectional Dijkstra over the extracted graph for routing. Updates ship as content-hashed differentials — only the changed tiles and segments — so the phone never re-downloads an entire region.