Design Google Maps

Google Maps looks like one app but is three very different systems behind one screen. At 6 p.m. in Bengaluru the city appears instantly, crisp at every zoom. You type “Kempegowda airport” and get a route that knows the Hebbal flyover is jammed, with an arrival time right to within minutes. The phone then talks you through every turn and, when you miss an exit, has a new route before you have finished swearing. Behind that sit a planet cut into billions of tiles, a road graph of hundreds of millions of junctions that must answer a cross-country query in milliseconds, and GPS pings from millions of moving phones. Google says more than a billion people use it and over a billion kilometres are driven with it every day. You will design the core: the map, search, driving routes with live-traffic ETAs, and turn-by-turn navigation.

Understand the problem

“Design Google Maps” is too big as asked: the product includes Street View, transit, reviews and imagery. Narrow it to the driving core and say why: those features exercise three scaling shapes — read-heavy static content (the map), CPU- and memory-heavy graph search (routes) and a write-heavy stream (traffic). Give each its own architecture.

Functional requirements

1. Users should be able to view the map and pan and zoom smoothly, anywhere on Earth, from the whole world down to individual buildings.
2. Users should be able to search for a place or address and see it on the map. Geocoding is kept brief here; the place-search side is its own problem in design nearby places search.
3. Users should be able to get a driving route from A to B with an ETA that reflects live traffic, with up to two alternatives.
4. Users should be able to navigate turn by turn, with automatic rerouting when they leave the route or when traffic makes another route clearly faster.

Non-functional requirements

• Scale. About 1 billion monthly users (Google reported more than a billion in 2020); plan for 250 million daily active users and 100 million navigated drives a day.
• Map latency. First screen of map in under 1 s on 4G; each tile from the CDN under 100 ms at p99 and 20–30 ms at p50.
• Route latency. A route with alternatives and a traffic-aware ETA under 1 s at p99 and about 200 ms at p50, even for Delhi to Mumbai.
• Traffic freshness. A new jam reaches routes and the traffic layer within about 2 minutes. Google reports ETAs accurate for over 97% of trips; aim for that class of accuracy.
• Navigation must survive bad networks. Tunnels and highway dead zones are normal: guidance must work without the server, and a reroute should return in under 1 s when there is signal.
• Availability over consistency. 99.99% for tiles and routing. Staleness is fine — traffic 60 seconds old, a new road hours late. Nothing is transactional.
• Privacy. Traffic comes from anonymised, aggregated data; no stored sample can be tied to an account.

Out of scope

• Street View and satellite imagery. A separate, petabyte-scale imagery pipeline.
• Transit and walking specifics. Transit routing runs on timetables, not road speeds; it is a follow-up below.
• Reviews, photos and place details. That is places content, closer to nearby places search.
• Collecting map data. Survey vehicles, imagery and user edits belong to an upstream team; we consume a versioned map dataset published daily.
• Accounts, saved places, location sharing and ads. Standard CRUD; not where this design is won.

The set-up

Plan the approach

Say the shape early: “static content for tiles, in-memory compute for routes, streaming for traffic, joined by a navigation service.” Build each requirement simply, then spend the deep dives on the hard parts: the tile pyramid, millisecond routing, live traffic inside routing, GPS to speeds, ETAs, and keeping millions of drivers on the best route.

Core entities

• Map dataset. Versioned features — roads, buildings, water, places — with geometry and attributes, such as planet-2026-10-20.
• Tile. The bytes for one square of the map at one zoom: (z, x, y) plus the dataset version. Immutable once built.
• Road graph. Junctions (nodes) and directed road segments (edges) with length, road class, speed limit, access rules and turn restrictions. Segment IDs stay stable across versions so traffic history survives map updates.
• Speed snapshot. Per segment: current speed, number of distinct trips behind it and a confidence, published every 60 seconds. Plus a historical profile: typical speed for each 15-minute slot of the week.
• Route. Ordered segment IDs, an encoded polyline, manoeuvres (“turn left onto Bellary Road in 300 m”), expected time per segment, the ETA and a route token.
• Navigation session. Session ID, route token, progress and last ETA sent. Soft state the phone can rebuild.
• Probe point. An anonymous trip token, latitude, longitude, timestamp, speed, heading and GPS accuracy — no user ID.

API

Tiles are plain, cacheable GETs. The client works out which tiles cover its screen and requests each one:

GET /tiles/v1/14/11723/7596.mvt
Accept-Encoding: gzip

HTTP/1.1 200 OK
Content-Type: application/vnd.mapbox-vector-tile
Content-Encoding: gzip
Cache-Control: public, max-age=86400, stale-while-revalidate=604800
ETag: "planet-2026-10-20:8f3c1a"

Tile 14/11723/7596 is the square containing MG Road in Bengaluru at zoom 14, about 2.4 km across. The style, fonts and icon sprites are fetched once and cached for weeks.

Search turns text into places, biased towards what the user is looking at:

GET /v1/geocode?q=kempegowda+airport&near=12.9756,77.6050&lang=en

{
  "results": [
    { "place_id": "p_blr_kia", "name": "Kempegowda International Airport",
      "lat": 13.1989, "lng": 77.7068, "type": "airport", "score": 0.97 }
  ]
}

Routes:

POST /v1/routes
Content-Type: application/json

{
  "origin": { "lat": 12.9756, "lng": 77.6050, "heading": 40 },
  "destination": { "place_id": "p_blr_kia" },
  "mode": "drive",
  "departure": "now",
  "alternatives": 2,
  "avoid": ["tolls"]
}

{
  "routes": [
    {
      "route_token": "r_7f3e…",
      "distance_m": 34100,
      "duration_s": 3960,
      "duration_free_flow_s": 2580,
      "polyline": "ezxmAgd~xMk@uB…",
      "traffic_spans": [ { "from_m": 9200, "to_m": 11800, "level": "heavy" } ],
      "steps": [ { "at_m": 650, "maneuver": "turn-left", "road": "Cubbon Road" } ],
      "segment_ids": "delta-encoded…",
      "data_version": { "map": "planet-2026-10-20", "traffic": "2026-10-27T12:32:00Z" }
    }
  ]
}

Navigation keeps one long-lived connection per drive. The phone sends progress every 30 seconds; the server pushes changes:

→ { "type": "progress", "session": "n_51a…", "route_offset_m": 5230,
    "points": [[12.98911, 77.61872, 1793104380, 9.4, 38], "…5 more"] }
← { "type": "eta", "eta_s": 3480, "traffic_spans": [ "…" ] }
← { "type": "better_route", "route_token": "r_9c1d…", "saves_s": 420 }

A reroute is just another POST /v1/routes carrying the current position and heading plus "reroute_of": "r_7f3e…", so the server can prefer a route that does not demand a U-turn.

Back-of-envelope estimates

These numbers decide what is a CDN problem, a memory problem or a streaming problem (method: back-of-envelope estimation).

Tile fetches. 250M daily users × 3 map sessions × 60 tile fetches per session (a dozen for the first screen, the rest from panning and zooming) = 45 billion tile fetches a day. 45B ÷ 86,400 s ≈ 520k/s on average; the evening peak is about 3× that, ≈ 1.6M tile fetches/s. At about 20 KB per compressed vector tile, 1.6M × 20 KB = 32 GB/s, roughly 260 Gbit/s at peak. With a 98% CDN hit ratio the origin sees 2% × 1.6M ≈ 32k requests/s.

Navigated drives. Over 1 billion km a day ÷ an assumed 10 km average drive = 100M drives a day. At 20 minutes each, 100M × 20 min ÷ 1,440 min ≈ 1.4M concurrent on average; at a 3× peak, ≈ 4.2M phones navigating at once.

Route computations. About 2 fresh route requests per drive, counting previews never driven: 200M ÷ 86,400 ≈ 2.3k/s, ≈ 7k/s at peak. Each active drive is also re-checked about every 2 minutes: 4.2M ÷ 120 s = 35k/s at peak. Total ≈ 42k route computations/s. At about 20 ms of CPU each (alternatives plus the ETA model), 42k × 0.02 s = 840 busy cores — around 30 servers of 64 cores at 50% load, before regional replicas.

Probe points. Each navigating phone contributes one point every 5 s: 4.2M ÷ 5 = 840k points/s at peak, uploaded in 30-second batches of six, so 4.2M ÷ 30 = 140k uploads/s. Per day: 100M drives × 1,200 s ÷ 5 s = 24B points; at about 24 bytes each, 24B × 24 B ≈ 580 GB/day of raw probes.

Road graph. The standard Western Europe benchmark has 18M junctions and 42M directed segments; assume the world is about ten times that, ≈ 200M junctions and 500M segments. In the Customizable Route Planning paper, routing data for all of Africa, Asia and Europe from OpenStreetMap needs about 3.4 GB plus about 200 MB per set of weights. One server holds a whole continent, so a query never crosses machines.

Tile storage. Zooms 0 to 14 hold (4^15 − 1) ÷ 3 ≈ 358M tiles. About 70% of the planet is water, and much of the land is uniform forest, desert or ice, so assume roughly 30% of tiles carry unique content: 358M × 0.3 ≈ 107M tiles × 20 KB ≈ 2 TB of vector tiles for the planet. Raster tiles to zoom 18 would be (4^19 − 1) ÷ 3 ≈ 91.6B tiles; at 30% and 15 KB that is 91.6B × 0.3 × 15 KB ≈ 410 TB — per style, per language and per screen density.

What the numbers decide. Tiles are a CDN and object-storage problem. Routing is a memory-and-CPU problem solved by replicating continents, not sharding. Traffic is a streaming problem at nearly a million events a second. No hot path needs a transactional database.

High-level design

Build one requirement at a time; the result works for one city, and the deep dives make it work for the planet.

Users should be able to view the map and pan and zoom

The map is a grid of square tiles. At zoom 0 one tile shows the world; each zoom level splits every tile into four, so zoom z has 2^z × 2^z tiles, addressed by z/x/y. The phone works out which handful of tiles cover its screen and fetches only those; panning fetches tiles sliding into view, zooming fetches children.

Tiles change only when map data changes, so they cache perfectly. An offline tile builder cuts the day’s map dataset into tiles, simplifies geometry per zoom (a river is a few points at zoom 5, hundreds at zoom 14), drops what is too small to see, and writes everything to object storage. A thin tile service reads it, a CDN absorbs almost all traffic, and the phone keeps its own cache.

What goes inside a tile — pixels or geometry — and how many tiles there are is the first deep dive.

Users should be able to search for a place or address

A small geocoder turns “Kempegowda airport” or “12th Main, Indiranagar” into coordinates with an inverted index over names and address parts, scoring results partly by distance from the map’s centre — so “MG Road” means Bengaluru’s when you are looking at Bengaluru and Pune’s when you are looking at Pune. Reverse geocoding (drop a pin, get an address) is a nearest-feature lookup in a spatial index such as S2 cells (see geospatial indexes); suggestions are a typeahead problem. Treat it as a black box returning a place_id and a point.

Users should be able to get a driving route with a traffic-aware ETA

The routing service loads the road graph into memory, each edge weighted by its travel time; a nightly graph builder produces it from the same map dataset as the tiles. A request runs four steps:

1. Snap origin and destination to the nearest drivable segment, using the heading to pick the right side of a divided road.
2. Search for the path with the least total travel time, applying turn restrictions and penalties.
3. Unpack it into an encoded polyline and manoeuvres such as “keep left onto the Hebbal flyover”.
4. Estimate the ETA by adding up the expected time on each segment.

A segment speeds store holds the latest speed per segment, which routing turns into edge weights, falling back to historical speed and then the speed limit.

A first version runs Dijkstra’s algorithm on these weights: fine across Bengaluru, hopeless for Bengaluru to Mumbai, where it scans millions of nodes. Making routing fast, and keeping it fast while weights change every minute, are two deep dives.

Users should be able to navigate turn by turn, with rerouting

Navigation adds a navigation service holding one session per active drive, and a traffic pipeline that turns those drives into speeds.

The phone guides itself. The route already contains geometry, manoeuvres and expected time per segment, so the phone snaps each GPS fix to the route, announces “in 300 metres, turn left” and updates the remaining time locally, with or without signal. Over a long-lived connection it sends progress every 30 seconds and receives ETA updates and “faster route” offers; if it leaves the route, it asks for a new one.

The navigation service strips identity from the GPS points and forwards them under a random trip token to a probe stream. A map matcher works out which segments each trip drove, and an aggregator turns traversal times into a speed per segment every 60 seconds.

This works for one city. At planet scale six things break: the tile pyramid’s size, routing speed, routing under changing traffic, noisy GPS, ETAs for long trips, and keeping 4 million drivers on the best route.

Deep dives

How do we serve map tiles for the whole planet?

Web Mercator projects the globe onto a square, stretching it towards the poles and cutting off at about 85.05° north and south, where the world becomes exactly square. Longitude maps linearly to x; latitude maps to y through the Mercator formula. Zoom 0 is one 256-pixel tile and zoom z has 4^z. The addressing is a quadtree, as in geospatial indexes: a tile’s children are (z+1, 2x or 2x+1, 2y or 2y+1) and its parent is (z−1, x÷2, y÷2), so the phone can stretch the parent while sharper children load.

Bad: render raster tiles on demand. The server queries the features in the tile’s box and draws a PNG, costing tens to hundreds of milliseconds of CPU per tile; 1.6M fetches a second would need a data centre of renderers. Caching helps, but the first visitor to every tile waits, and a stadium on IPL final night triggers a stampede of identical renders.

Good: pre-render popular zooms, render the rest on a miss, cache everything. The classic raster tile server pre-renders zooms up to about 12 (only 22M tiles in total) and draws deeper tiles on first request. You gain bounded storage and trivial clients. You pay with slow cold tiles and a baked-in look: every style (day, night, terrain), label language (Kannada, Hindi, English) and screen density is a separate tile set — about 410 TB per variant to zoom 18, petabytes across a few dozen. Rotating the map turns labels upside down.

Great: vector tiles, pre-built to around zoom 14 to 16, served from the CDN and drawn on the phone. A vector tile carries geometry, not pixels. The Mapbox Vector Tile format is a Protocol Buffers message of named layers (roads, water, buildings, labels); each feature has attributes such as class=motorway or name:kn, and geometry as integer coordinates in a local grid (the specification’s example extent is 4096 per side), written as zigzag-encoded, delta-coded MoveTo, LineTo and ClosePath commands that compress very well.

You gain one tile set for every look (night mode or Kannada labels are just a different style JSON), about 2 TB for the planet instead of hundreds of terabytes per variant, smooth fractional zoom, rotation and tilt with upright labels, and offline maps measured in megabytes. Beyond the last built zoom the phone overzooms, drawing zoom-14 geometry at zoom 18. You pay with a real rendering engine on the phone (GPU drawing, Indic text shaping, label collision), more battery on low-end phones, and a size budget for dense tiles such as central Mumbai, met by simplifying geometry and dropping minor features per zoom. Satellite imagery stays raster.

Three refinements finish it:

• Deduplicate empty tiles. Open sea and uniform land cover are byte-for-byte identical, so index z/x/y to a content hash and let one “ocean” blob serve billions of tiles — the source of the 30% in the estimate.
• Separate fast data from slow data. Traffic changes every minute, so serve it as its own overlay layer with a 60-second cache lifetime, keyed by the same z/x/y; a jam never invalidates base tiles.
• Update without a cold CDN. Changing every URL on each daily release empties the CDN. Keep stable tile URLs with a one-day lifetime and an ETag, rebuild only “dirty” tiles (a new flyover dirties one tile per zoom plus a buffer) and purge those when urgent. Styles, fonts and icons, which must stay consistent with each other, get versioned, immutable URLs.

How do we find the fastest route on a continental road graph in milliseconds?

The fastest route is a shortest path on travel times; the difficulty is scale. On the standard Western Europe benchmark — 18 million junctions, 42 million directed segments — one long Dijkstra query scans about 9.4 million nodes in about 2.5 seconds, per the Customizable Route Planning paper. At 42k computations a second that is over 100,000 busy cores.

Bad: plain Dijkstra. It grows a disc of settled nodes around the start until it reaches the destination. For Bengaluru to Mumbai, about 980 km by road, it explores every direction, deep into Tamil Nadu and Kerala, which you will never drive through.

Better: bidirectional search and A*. Search forwards from the start and backwards from the destination until they meet: two discs of half the radius cover half the area (2 × π(r/2)² = πr²/2). A* steers towards the target with a lower bound on the remaining time, such as straight-line distance divided by the top road speed — a weak bound for travel time, so the search still fans out. Landmark bounds (precomputed distances to a few dozen landmarks, via the triangle inequality) are tighter but cost a lot of memory. You gain a constant factor, not orders of magnitude.

Great: Contraction Hierarchies (CH). The insight of Geisberger, Sanders, Schultes and Delling (2008) is that road networks are hierarchical: long trips leave residential streets quickly, run on highways and come back down at the end.

• Preprocessing. Rank nodes by importance, side streets first and motorway junctions last, using heuristics such as the edge difference (shortcuts added minus edges removed). Then contract nodes in that order: remove v, and wherever u→v→w is the only shortest path between neighbours u and w, add a shortcut u→w with the combined weight. A local “witness search” skips shortcuts that another path makes unnecessary.
• Query. Run bidirectional Dijkstra where both searches only move to more important nodes. They climb to the motorway level and meet near the top.
• Unpacking. Each shortcut bypasses exactly one node; store it, and expand shortcuts recursively into real segments for drawing and directions.

On the 18M-node Western Europe graph the original paper reports about 10 minutes of preprocessing on one core (about 9 to order nodes, 1 to build the hierarchy), queries settling a few hundred nodes in around 0.2 ms, and a structure no bigger than the plain graph — four orders of magnitude faster than Dijkstra. Turn restrictions and U-turn penalties, modelled by making turns explicit, enlarge the graph, but queries stay well under a millisecond.

The catch is the word preprocessing: the hierarchy is built for one set of weights, and traffic changes them every minute.

How do we keep routes right when traffic changes every minute?

Every 60 seconds the pipeline publishes new speeds for millions of segments, and routing must use them within seconds.

Bad: rebuild the Contraction Hierarchy from scratch. Ten minutes per update for Europe; “live” traffic would always be ten minutes old.

Good: keep the node order and re-contract. Motorways stay important when traffic changes, so keep the ordering and recompute only the shortcuts — about a minute for Europe in the CH paper, and the CRP authors cite the same order for small weight changes. OSRM’s CH pipeline accepts traffic this way, though its documentation recommends the partition-based MLD pipeline by default. You keep sub-millisecond queries; you pay a minute per update per continent, and searches grow when traffic upends the hierarchy (a jammed motorway is still ranked important).

Great: Customizable Route Planning (CRP). Designed by Delling, Goldberg, Pajor and Werneck at Microsoft Research for exactly this, it became the routing engine behind Bing Maps; OSRM implements it as Multi-Level Dijkstra (MLD). It splits the work into three phases at three speeds:

1. Partition (minutes, only when roads change). Cut the graph into cells with few boundary edges — roads have natural cuts at rivers, railways and ridges — and repeat inside cells for several levels, from hundreds of nodes up to millions. Topology only, never speeds.
2. Customise (about a second, whenever weights change). For every cell, bottom level first, compute travel times between each pair of its boundary nodes and store them as a small overlay that replaces the interior. If few segments change, redo only their cells and parents.
3. Query (a couple of milliseconds). Bidirectional Dijkstra on full detail inside the start’s and destination’s cells, and on overlays everywhere else.

On Western Europe, customising a new metric takes about one second on a 12-core server, and a query scans about 3,000 nodes in about 1.7 ms. One metric’s weights take about 70 MB, so a server holds several — car, truck, avoid-tolls — where CH needs a hierarchy each. On OpenStreetMap’s Africa–Asia–Europe graph (189 million nodes, since OSM stores road-shape points as nodes) customisation takes about 7.5 seconds, or 1.5 with an extra contraction step, and queries stay under 2 ms.

The recommendation: CRP (or MLD) for live routing. You trade queries about ten times slower than CH — still around 2 ms — for traffic seconds old instead of minutes, and cheap extra metrics. Keep CH where weights are static and volume is huge, such as travel-time matrices for logistics.

In production:

• Replicate continents; don’t shard a query. Each routing server holds one continent (Africa–Asia–Europe is one connected graph, the Americas another); any healthy replica in the nearest region answers.
• Double-buffer the metric. Every 60 seconds each server customises a fresh copy of the overlay weights, then swaps a pointer; in-flight queries finish on the old one, and responses record the snapshot used.
• Closures are infinite weights. A road shut for a procession or flooded in the monsoon needs no topology change.
• Alternatives. Keep a few candidates that share little with the best path and are not much longer (good “via” nodes reached by both searches), and return up to two.

How do we turn GPS pings from phones into live traffic?

Navigating phones are the sensors: 840k points a second at peak. Two problems sit between raw GPS and a speed per segment: which road was the phone on? — GPS is noisy by metres, worse among Nariman Point’s towers, and roads run side by side — and how do you publish trustworthy speeds without learning where anyone lives?

Bad: snap each point to the nearest road. On the Hebbal flyover, with a service road directly beneath, a car’s points wobble between the two. Snapped independently, the trace jumps up and down a wall and the service road looks impossibly fast.

Great: HMM map matching. Newson and Krumm (2009) treat the true road position as the hidden state of a Hidden Markov Model. Each GPS point’s candidates are road positions within 200 m. The emission probability falls off as a Gaussian in the point-to-road distance (their GPS noise had a standard deviation of about 4 m). The transition probability between consecutive candidates falls off with the difference between driving distance and straight-line distance: cars do not teleport between parallel roads, because flyover to service road needs a ramp a kilometre away. Viterbi then finds the most likely sequence. On their 80 km test drive the match was perfect at one point a second, with only 0.11% error at one point every 30 seconds — so a point every 5 seconds is plenty. OSRM ships this as its Match service.

What you pay: every transition needs a short route-distance computation, making matching the most CPU-hungry stage. Cap candidates (200 m, at most five per point) and give each matcher a copy of its region’s graph.

Matching needs a trip’s points in order; speeds are per segment. So the pipeline has two stages with different keys:

1. Match, keyed by trip token. All of one trip’s points reach the same matcher, which keeps a few minutes of per-trip state and emits traversals: “trip T crossed segment 4,412 from 18:02:11 to 18:02:29” — 180 m in 18 s, or 36 km/h.
2. Aggregate, keyed by segment ID. Per segment, a sliding window of the last few minutes yields a robust speed — a median, so a parked autorickshaw or a bus at its stop does not drag it down — published every 60 seconds. Segments with few recent trips are blended towards their historical speed, weighted by sample count.

Privacy is structural, not a footnote. Google describes live traffic as built from aggregate location data. Only the navigation gateway sees both account and location; it forwards points under a random trip token rotated every 15 minutes, so no long trace can be stitched together, and drops each trip’s first and last 500 m, where home and office are. The aggregator publishes a speed only if at least 5 distinct trips contributed, and raw probes expire within days. (The thresholds are tuning choices; the structure is the point.) You pay with coverage: quiet roads fall back to history more often.

Sizing. If one matcher core handles about 10k points a second, 840k points need 84 busy cores at peak; double it and run per region. Flink-style stream processors give keyed state and sliding windows; Kafka gives replayable topics.

How do we predict the ETA, not just measure today’s speeds?

Leave Bengaluru at 4 p.m. on a 90-minute drive and the segments near the airport are driven at 5:15 p.m., in different traffic.

Bad: add up current speeds. Fine for a 10-minute hop, wrong for long trips: it misses the evening jam that has not formed and keeps a jam that will have cleared.

Good: time-dependent historical profiles blended with live speeds. Keep per segment a typical speed for each 15-minute slot of the week, 7 × 96 = 672 numbers. Walk the route forward, pricing each segment at the time you will reach it, with live speeds for the first stretch fading into history. Google describes this mix — historical patterns (a freeway doing 65 mph at 6 a.m., 15–20 mph in the late afternoon) combined with live data — and says that when 2020 lockdowns cut worldwide traffic by up to 50%, it reweighted history towards the last two to four weeks. Storage: 500M segments × 672 × 1 byte ≈ 336 GB, far less if segments share a few thousand profile shapes.

Great: a learned model over the route. A hand-tuned blend misses interactions such as a side-street jam spilling onto the main road. Google and DeepMind deployed a graph neural network for ETAs (Derrow-Pinion et al., 2021): 50–100 m segments grouped into supersegments of about 20; features include live speeds in seventeen 2-minute windows before departure and historical speeds averaged over 17 weeks; outputs are traversal times at fixed horizons — now, +10, +20, +30 and +60 minutes — which serving interpolates as it walks the route. It cut bad ETAs by over 40% in cities such as Sydney against the previous production model.

You gain better ETAs across changing peaks; you pay inference on every route. Predictions depend on supersegment and horizon, not the user, so cache them for a minute or two: every route crossing the Outer Ring Road reuses them, and cost grows with the road network, not with requests. CRP proposes candidates, the model re-scores them, and logging predicted versus actual arrival per trip, by city and hour, catches regressions before drivers do.

How do we keep 4 million navigating phones on the best route?

Bad: the server drives the navigation. It tracks each phone and sends “turn left in 200 m” — a round trip per manoeuvre, impossible in a tunnel or on the Mumbai–Pune ghats, and 4.2M messages a second just to say “keep going”.

Good: the phone navigates and polls. The route holds geometry, manoeuvres, lane hints, speed limits and time per segment. The phone matches GPS fixes to the route polyline (a light HMM using heading too), announces manoeuvres and updates the remaining time. It is off route after a few seconds more than about 50 m away with a disagreeing heading, and then requests a new route. Every 2 minutes it asks for a re-check. Guidance never waits on the network; you pay up to 2 minutes of lag on a new jam and 35k re-checks a second, mostly finding nothing.

Great: the phone navigates; the server pushes on change. The navigation service keeps a small session per drive (route token, remaining segments, last ETA), sharded by session ID, plus an inverted index from segment ID to sessions whose remaining route uses it. When a snapshot or incident changes a segment materially, only affected sessions are re-checked, and an ETA update or “better route” is pushed over the open connection (see real-time connections). A jam on the airport road might touch 20,000 sessions instead of all 4.2 million. A slow periodic re-check remains as a safety net.

Three details make it pleasant rather than twitchy:

• Hysteresis. Offer a new route only if it saves a real margin, say 5 minutes and 10%, and never flip back within minutes, or near-equal routes make the phone flap.
• Soft, rebuildable state. Sessions live in memory. If a server dies, phones reconnect elsewhere with their route token and position, with jittered backoff to avoid a stampede. At 50k connections per server, 4.2M drivers need about 84 servers at peak, plus headroom.
• Reroutes avoid U-turns. The request carries heading and previous route, so the search starts in the direction of travel and prefers rejoining the old route.

The final design

Three systems, joined at the phone: tiles through the CDN, routes through the gateway, and a drive’s live loop through the navigation service and the traffic pipeline.

1. Tiles. The phone computes which z/x/y tiles cover the screen and fetches them from the CDN; the rare miss reads the deduplicated vector tile from object storage. The phone styles and draws them.
2. Search. The gateway sends the query to the geocoder, which returns place IDs ranked by text match and distance from the viewport.
3. Route. A routing server holding the whole continent snaps the endpoints, runs a CRP query with live weights, unpacks a few candidates and lets the ETA model re-score them. About 2 ms of search inside a response of about 200 ms.
4. Navigate. The phone opens a session and guides itself from the route it holds, sending progress every 30 seconds.
5. Probe. The navigation service strips identity, trims trip ends and writes points under a rotating trip token to the probe stream.
6. Match and aggregate. Matchers turn each trip into segment traversals; aggregators compute robust per-segment speeds over sliding windows.
7. Customise. Every 60 seconds the speed snapshot is applied to every routing server’s overlay weights in about a second, and to the traffic tile layer.
8. Push. The navigation service finds sessions whose remaining route got materially slower, asks routing to re-check them, and pushes ETA updates or better routes. Off-route phones request reroutes directly.
9. Build. Nightly, builders turn the new map dataset into changed tiles and a new road graph, which routing servers load as a new partition.

Check it against the requirements. Tiles: a CDN serving about 1.6M fetches a second with an origin under 40k a second, from about 2 TB of tiles. Routes: well under 1 s, with traffic at most about two minutes old, from about 30 servers’ worth of CPU per region. Traffic: 840k points a second, partitioned twice, published every minute and anonymised before anything is stored. Navigation: keeps working with no signal, and pushes changes only to drivers they affect. Every component can lose a replica without losing data that matters.

What interviewers look for by level

Follow-up questions

What if users want offline maps?

Package a region: its vector tiles to zoom 14, the style and fonts, a geocoding index, and a routing graph preprocessed with Contraction Hierarchies, which suits a phone because the weights are static offline and queries are tiny. Size it: a zoom-14 tile near Bengaluru is about 2.4 km wide, so a 200 km square is about 83 × 83 ≈ 6,900 tiles, plus a third more for lower zooms, ≈ 9,200 tiles × 20 KB ≈ 180 MB. Offline routes use historical profiles, not live traffic, and the package expires after a few weeks so nobody navigates on a year-old road network. Updates ship as diffs of changed tiles.

What if we add walking and transit?

Walking is another metric on the same road graph — footpaths allowed, one-way rules ignored — and CRP makes extra metrics cheap, about 70 MB each for a Europe-sized graph. Transit is different: you route over timetables, not edge weights, with algorithms built for schedules such as RAPTOR, and the hard part is multimodal stitching (walk to the metro, ride, take an auto) and live delays fed by operators.

What if a road is suddenly closed?

A flooded underpass or a procession needs no new graph: set the segments’ cost to infinity in the next customisation, seconds later. Closures arrive from authoritative sources such as city traffic police and from user reports, which Google describes using alongside its own data. Push the change to sessions whose remaining route crosses the closure and draw it on the traffic layer.

What if the user asks for an ETA for 8 a.m. tomorrow?

Live data is irrelevant that far out, so route on historical profiles for that time. Because one CRP metric is about 70 MB, you can precompute a metric per hour of the week — 168 × 70 MB ≈ 12 GB — and pick the one for the departure hour; the ETA model then prices each segment at the time you will reach it.

What if trucks and two-wheelers need different routes?

Each is a different metric and different access rules: height and weight limits and banned hours for trucks, narrow lanes allowed for two-wheelers. With CRP each vehicle profile is another customisation over the same partition. With CH each would need its own hierarchy, rebuilt for every traffic update.

How to say it in the interview

“I’ll scope this to the map, search, driving routes with live-traffic ETAs, and turn-by-turn navigation, for about a billion monthly users. These are three systems with different shapes: static content, in-memory compute and streaming.

For the map, an offline job cuts the planet into z/x/y vector tiles. There are 4 to the z tiles per zoom, so I build to about zoom 14 — roughly 358 million tiles, about 2 terabytes after deduplicating ocean — and the phone overzooms beyond that. Vector tiles mean one tile set for every style and language. They sit in object storage behind a CDN serving well over a million fetches a second at peak.

For routing, each server holds a whole continent’s road graph in memory. Dijkstra scans millions of nodes and takes seconds. Contraction Hierarchies take it to a fraction of a millisecond, but bake the weights into a preprocessing step. Because traffic changes every minute, I’d use Customizable Route Planning: partition the graph once, recompute overlay costs from live speeds in about a second, and answer queries in about 2 milliseconds.

Traffic comes from navigating phones. The navigation service strips identity and forwards points under a rotating trip token. A stream job map-matches each trip with an HMM and Viterbi, re-keys traversals by segment, and publishes median speeds every minute, only where enough trips contributed. ETAs come from a model that blends live and historical speeds and predicts at several horizons, because a long trip meets traffic that hasn’t formed yet.

The phone does the guiding, so navigation survives tunnels. It asks for a reroute when it leaves the route, and the server pushes a better route when a traffic change hits that driver’s remaining segments.”

Concepts used in this design

• Geospatial indexes: geohash, quadtrees, S2 and H3 — the tile pyramid is a quadtree; reverse geocoding uses spatial cells.
• Content delivery network — serving tiles at over a million fetches a second.
• Blob storage — the tile store and map releases.
• Hot keys, cache stampede and invalidation — tile updates without a cold CDN, and popular tiles.
• Proximity search — snapping points to the nearest road and ranking places by distance.
• Kafka — the probe and traversal topics, keyed by trip and by segment.
• Flink and stream processing — keyed state and sliding windows for speeds.
• Batch vs stream processing — nightly tile and graph builds versus minute-level traffic.
• Real-time connections — the navigation stream that carries pushes.
• Push vs pull architecture — polling for better routes versus pushing to affected drivers.
• Stateful vs stateless design — soft navigation sessions that phones can rebuild.
• Strong vs eventual consistency — why a minute-old speed is acceptable everywhere.
• Design nearby places search — the places side of search.
• Design Uber — ETAs and location streams from moving drivers.

References and further reading

1. Slippy map tilenames (OpenStreetMap wiki)wiki.openstreetmap.orgThe /zoom/x/y tile URL scheme, 2^z × 2^z tiles per zoom, the Web Mercator formulas from longitude and latitude to tile numbers, and tile counts per zoom.
2. Zoom levels (OpenStreetMap wiki)wiki.openstreetmap.orgTiles per zoom level for storage planning and metres per pixel at the equator: about 156,543 m at zoom 0 and 0.6 m at zoom 18.
3. Mapbox Vector Tile Specification 2.1github.comProtocol-buffer tiles made of named layers, integer coordinates in a tile extent such as 4096, zigzag-encoded MoveTo/LineTo/ClosePath commands, and the .mvt MIME type.
4. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (Geisberger, Sanders, Schultes, Delling, WEA 2008)algo2.iti.kit.eduNode contraction with shortcuts and upward-only bidirectional queries; on an 18M-node Western Europe graph, about 10 minutes of preprocessing and queries settling a few hundred nodes in roughly 0.2 ms.
5. Customizable Route Planning in Road Networks (Delling, Goldberg, Pajor, Werneck, Microsoft Research)microsoft.comMulti-level partitions with overlay graphs; Dijkstra scans 9.4M vertices in about 2.5 s on Europe, CRP customises a new metric in about a second and answers queries in under 2 ms; the engine behind Bing Maps.
6. Open Source Routing Machine (OSRM) backendgithub.comA production routing engine offering both Contraction Hierarchies and Multi-Level Dijkstra pipelines (MLD recommended by default), plus a Match service for noisy GPS traces.
7. Hidden Markov Map Matching Through Noise and Sparseness (Newson and Krumm, ACM GIS 2009)microsoft.comHMM map matching with Gaussian emission and exponential transition probabilities, Viterbi decoding, a 200 m candidate radius, and 0.11% error even at 30-second sampling.
8. Google Maps 101: How AI helps predict traffic and determine routes (Google, 2020)blog.googleOver 1 billion km driven with Google Maps every day; aggregate location data for live traffic; historical patterns plus live data in ML models; ETAs accurate for over 97% of trips.
9. ETA Prediction with Graph Neural Networks in Google Maps (Derrow-Pinion et al., CIKM 2021)arxiv.orgSupersegments of about 20 road segments of 50–100 m, live and 17-week historical speed features, fixed prediction horizons up to an hour, and 40%+ fewer bad ETAs in cities such as Sydney.
10. Google Maps turns 15 (Google, 2020)blog.googleMore than 1 billion people use Google Maps.