Design Google Maps: Map Tiles, Fast Routing, Live Traffic and Accurate ETAs

Listen

Requirements. Users pan and zoom a map of the whole world. They search for an address or a place and get a location, which is geocoding. They ask for a route from A to B, with an ETA and a couple of alternatives. During turn-by-turn navigation, the app reroutes when traffic changes, and roads are coloured by live traffic. Street-level imagery, reviews and transit schedules are out of scope.

Qualities. Panning must feel smooth, so tiles need to arrive in about a hundred milliseconds, mostly from cache. A route, even across a continent, should come back in under a second. ETAs should be accurate to within a few percent, which is what users judge the product by. Traffic should be fresh within a minute or two. Location probes must be anonymous. And downloaded areas should work offline.

Ask scale

Assume three hundred million daily users opening the map five times a day, each session loading about fifty tiles. That's seventy-five billion tiles a day, nearly nine hundred thousand a second, so tiles must come from a CDN with a very high hit rate. Route requests are about seven thousand a second, twenty thousand at peak. And with ten million people navigating at peak, each phone sending a speed probe every five seconds, that's two million probes a second feeding traffic.

Data sizes. Tiles form a pyramid: zoom level z has four to the z tiles, so zoom fourteen alone is two hundred sixty-eight million, though most are ocean or empty land. Vector tiles average a few kilobytes, so the planet up to zoom fourteen is around a hundred gigabytes, and closer zooms just stretch zoom fourteen data. The road graph is around half a billion intersections and a billion directed road segments, tens of gigabytes. Partition it by region and keep each region in memory.

DAU                   300M
map sessions/user     5
tiles per session     50
  75B tiles/day
  / 86,400 s         = ~870K/s
  -> CDN, >95% hits

route requests        600M/day
  = ~7K/s, peak ~20K/s
navigating at peak    10M
  probe every 5 s    = 2M/s

tiles: zoom z has 4^z tiles
  z14 = 268M tiles (most
  empty: ocean, desert)
vector tiles: few KB avg,
  z0-z14 planet ~100s of GB
  higher zooms: overzoom z14

road graph: ~500M nodes,
  ~1B directed edges x ~40 B
  = ~40 GB + shortcuts
-> partition by region, in RAM

Define API

The API. Tiles are plain URLs by zoom, x and y, with a data version in the path, so each URL is immutable and caches forever; a new map release simply means a new version. Geocoding takes a query and a hint of where the user is. Routes take origin, destination, mode, departure time and things to avoid, and return a polyline, ETA, steps and traffic spans. Navigation keeps a connection open: the phone sends positions up, and the server pushes reroutes down.

GET {cdn}/tiles/v42/{z}/{x}/{y}
  -> vector tile (immutable)
GET /v1/geocode?q=..&near=..
  -> [{ placeId, lat, lng }]
POST /v1/routes
  { origin, dest, mode,
    departAt, avoid[] }
  -> [{ polyline, etaSec,
       steps[], trafficSpans }]
WS  /v1/nav/{sessionId}
  up: position  down: reroute

Data model

Data model. There's one versioned source of truth for the map: points, roads made of points with tags like road class, speed limit and one-way, and places with names and addresses. From it, batch pipelines compile three products: the tile pyramid, the preprocessed routing graph, and a search index for geocoding. Live traffic is separate and tiny by comparison: for each road segment, the current speed and when it was measured.

map source (versioned):
  node (id, lat, lng)
  way  (id, nodes[], tags:
        road class, speed, oneway)
  place(id, name, addr, point)
compiled outputs:
  tiles  z/x/y -> vector data
  graph  edges + shortcuts
  search index for geocoding
live: segmentId -> speed, ts

High-level design

The map path. Tiles are built in batch from map data and pushed to object storage behind a CDN. When you pan, the app computes which tile coordinates cover the screen at the current zoom and fetches them from the CDN, almost always an edge hit. Search goes through the API to the geocoding service, which turns a query like an address or a place name into a point and returns candidates ranked by relevance and distance.

The route path. The routing service runs a shortest-path search on the in-memory road graph, using live segment speeds from the traffic service as edge weights, and asks the ETA model for a final time estimate. During navigation, the phone's positions flow to the navigation service and, anonymised, into a probe stream. The traffic service turns those probes into current speeds per road segment, which feed back into routing. The users are the sensors.

Deep dive: tiles

Deep dive one: tiles. Zoom level zero is one tile showing the world. Each level splits every tile into four, so tile coordinates are a quadtree address, computed from latitude, longitude and zoom using the Web Mercator projection. Modern maps send vector tiles, which carry roads and labels as geometry. The client styles and renders them, so one tile works for dark mode, any language and a rotated map, and they're much smaller than images. On a map update, rebuild only the tiles whose data changed.

Deep dive: routing

Deep dive two: routing. Plain Dijkstra expands outward in every direction, settling nodes in order of distance until it reaches the destination. For a trip across a country, that's millions of nodes and seconds of work per query, at twenty thousand queries a second. A star helps by steering toward the target with a straight-line estimate, but on long trips it's still too slow. The real answer is to preprocess the graph once, so every query does very little work.

One well-known technique is contraction hierarchies. Offline, rank intersections by importance, local streets low, highway junctions high. Remove the least important nodes one by one, adding shortcut edges so shortest distances are preserved. At query time, run a search from both ends that only moves to more important nodes; the two searches meet near the top, on the highways. A cross-country route then touches a few hundred nodes and takes milliseconds. Then unpack the shortcuts into the real road path.

There's a catch: shortcuts bake in travel times, and traffic changes them every minute. So production systems separate structure from weights. Partition the graph into regions and precompute an overlay of boundary nodes, which depends only on the road network. Then, every minute or so, quickly recompute the overlay's weights from current speeds, which takes seconds. Routing algorithms in this family are often called customisable route planning. Long trips search locally at both ends and use the overlay in between.

Deep dive: traffic

Deep dive three: live traffic. Phones send anonymous probes: a point, a speed, a heading and a time, with rotating anonymous IDs. GPS is noisy, so the first step is map matching: snap a short trace of points to the most likely road path, typically with a hidden Markov model. Then for each road segment, compute a robust average speed over the last minute or two. With too few probes, blend in the historical speed for that hour and weekday. Drop outliers like cars parked in a lot.

Deep dive: ETA

Deep dive four: ETA and rerouting. Adding up current segment times is a start, but you'll reach the far segments thirty minutes from now, when traffic will be different. So the ETA model blends live speeds for segments near you with historical patterns for segments you'll reach later, plus delays for turns, traffic lights and incidents. It's trained on real trip times. During navigation, the server re-runs the route every minute and suggests a new one only if it's clearly faster, to avoid flip-flopping.

Trade-offs

Failures. If the traffic pipeline lags, routing falls back to historical speeds, which are surprisingly good, and the app can say live traffic is unavailable. Routing nodes hold replicated copies of each region's graph, so one dying just shifts load. A bad map edit, like a closed bridge marked open, is why map data is versioned: roll the release back. A new tile version can cause a miss storm, so prewarm it. The north-star metric is ETA error against actual arrival time.

Trade-offs. Preprocessing costs hours of batch compute and lots of memory, in exchange for millisecond routes. Vector tiles move rendering work to the client, but are smaller and far more flexible than images. Strict probe privacy limits what you can learn, but keeps users' trust, which keeps the probes coming. At ten times the scale, use finer graph partitions, run routing closer to users, and lean on downloadable offline packs.

Say it like this

The summary. One versioned map source compiles into three products: vector tiles, a routing graph and a search index. Tiles use immutable zoom, x, y URLs on a CDN. Routing keeps a partitioned graph in memory, preprocessed with an overlay or shortcuts so queries take milliseconds, and re-weighted every minute with live speeds. Traffic comes from anonymous phone probes, map matched to road segments. ETAs blend live speeds nearby with historical ones further along.