Design Google Maps

• Render the map at any zoom level — Pan and zoom smoothly on web and mobile, online and with a cached offline area.
• Search for places and addresses — Autocomplete as you type, biased to the viewport and the user's location.
• Compute a route between two points — Driving first; walking and transit as variants. Return the path, distance and ETA.
• Turn-by-turn navigation — Follow the user's GPS, announce manoeuvres, re-route when they deviate.
• Live traffic and traffic-aware ETAs — Traffic derived from anonymised location pings of navigating users.
• Show nearby places (POIs) — Restaurants, fuel, parking near a point or along a route.
• Out of scope — Street View imagery, business reviews, satellite imagery pipeline, and map data acquisition (we assume the road graph exists).

• Scale (1 B MAU · 50 M concurrent navigating) — Tile serving is the read-heavy part; navigation is the write-heavy part (location pings).
• Tile latency (p95 < 100 ms) — Tiles are what the user perceives as "the map is slow". Must come from a CDN edge.
• Route latency (p95 < 500 ms for 1 000 km) — Naive Dijkstra over a continent takes seconds. Needs a preprocessed graph.
• ETA accuracy (within 10 % for 90 % of trips) — Accuracy is a product metric; drives the traffic pipeline freshness requirement.
• Traffic freshness (< 2 min from ping to routing) — A jam that started 10 minutes ago must already affect ETAs.
• Availability (99.99 %) — Degrade gracefully: stale tiles and static routes are better than errors.
• Privacy — Location pings are anonymised, aggregated, and never joined back to a user for traffic purposes.
• Bandwidth — Mobile users on poor networks. Vector tiles, aggressive caching, delta updates.

• Tile requests per second: ~2 M — 1 B MAU, ~10 % daily = 100 M DAU. Each session loads ~50 tiles, 2 sessions a day: 100 M × 100 = 10 B/day ÷ 86 400 ≈ 115 k/s average, peak 5× ≈ 600 k/s… but each pan/zoom fetches a 3×3 to 5×5 grid, so budget ~2 M/s at the CDN edge. Origin sees under 1 % of that.
• Tile storage: ~100 TB (vector) — Web Mercator zoom 0–20 has 4^20 ≈ 10^12 tiles at the deepest level, but most are ocean or empty. Real data ~ 100 TB as vector tiles across all zooms, several PB if raster. Pre-render zooms 0–14, render 15–20 on demand and cache.
• Road graph size: ~500 M edges — Global road network: ~ 100 M nodes, ~ 500 M edges (intersections and segments), ~50 GB with geometry. Fits in memory on a handful of large machines per region; must be sharded or partitioned for parallel queries.
• Location pings per second: ~10 M — 50 M concurrent navigating × one ping every 5 s = 10 M pings/s. This is the single biggest stream in the system and it is write-only. Each ping ~100 B → 1 GB/s ingest.
• Route requests per second: ~50 k — 100 M DAU, ~20 % navigate daily, ~2 routes each plus re-routes: 40 M × 3 = 120 M/day ≈ 1.4 k/s average; peak ~10×, plus autocomplete-triggered previews. Budget ~50 k/s. Each is CPU heavy, so this sizes the routing fleet.
• Routing server CPU: ~500 servers — A contraction-hierarchy query costs ~1–5 ms of CPU. 50 k/s × 5 ms = 250 CPU-seconds per second → ~250 cores busy, so ~500 servers across regions with headroom and graph replication.
• Autocomplete queries per second: ~300 k — Each search types ~6 characters; ~1 query per keystroke after debounce: 100 M DAU × 2 searches × 6 = 1.2 B/day ≈ 14 k/s average, peak 20× = ~300 k/s. Must be served from an in-memory prefix index.

• Maps client (vector renderer · GPS) — Web or mobile app. Renders vector tiles on the GPU, caches tiles on disk, tracks GPS at 1 Hz, and does local map-matching and manoeuvre announcement during navigation so short network gaps do not break guidance.
• CDN edge (tiles · static) — Serves tiles and static assets from hundreds of edge locations. Cache key is (layer, z, x, y, version). Hit rate above 99 % because popular areas at popular zooms are a tiny fraction of the tile space.
• API gateway (auth · rate limit · geo-route) — Terminates TLS, authenticates API keys and user sessions, rate limits, and routes to the nearest regional deployment of each service. Stateless.
• Tile service — Origin for the CDN. Serves pre-rendered vector tiles for low zooms from object storage and renders high-zoom tiles on demand from the geo database, then caches them. Handles tile versioning when map data updates.
• Place search (prefix index + geo bias) — Autocomplete and full search. In-memory prefix tries per region, results scored by text match, popularity, and distance to the viewport or user. Backed by the places index for full queries.
• Routing service (contraction hierarchies) — Answers shortest-path queries in milliseconds using a preprocessed road graph (contraction hierarchies or customisable route planning). Holds the graph in memory, sharded by region with cross-border stitching. Applies live traffic weights.
• Navigation service (session state) — Owns an active navigation session: current route, progress, next manoeuvre. Receives location pings, map-matches them to the road graph, detects deviation, and requests a re-route. Forwards anonymised pings to the traffic pipeline.
• Geo database (PostGIS / spatial index) — Source of truth for map features: roads, buildings, boundaries, POIs, with geometry. Spatially indexed (R-tree / geohash). Read by the tile renderer and the places index builder; written by the map data pipeline.
• Places index (Elasticsearch · geo_point) — Searchable POIs and addresses with names, aliases, categories, popularity and location. Sharded by geographic region so a viewport-biased query hits one or two shards.
• Road graph store (preprocessed CH graph) — The compiled routing graph: nodes, edges, base weights, and the contraction hierarchy shortcuts. Rebuilt when map data changes (weekly) and loaded into routing servers at startup. Stored in object storage as versioned binary blobs.
• Traffic pipeline (stream processing) — Consumes anonymised location pings, map-matches them to road segments, aggregates speed per segment per minute, and publishes current segment speeds plus predicted speeds by time of day. The output is a compact weight overlay for the routing graph.
• Ping stream (Kafka · keyed by geo cell) — Durable stream of location pings, partitioned by coarse geo cell so a consumer sees all pings for an area. 10 M/s makes this one of the largest topics in the company; retention is short (hours).
• Traffic store (Redis · segment → speed) — Current speed per road segment, refreshed every minute, plus historical speed profiles. Routing servers pull deltas every 30–60 s and apply them as edge weight overrides without rebuilding the hierarchy.
• Tile storage (object storage) — Pre-rendered vector tiles for zooms 0–14 and cached on-demand tiles for deeper zooms. Versioned by map release so CDN keys change atomically on a data update.

1. Pan and zoom the map — The path that must be fast for everyone. Almost every request is answered at the CDN edge; the origin only sees cache misses and on-demand renders.
   1. Client computes the visible tile grid for the viewport and zoom.
   2. Client fetches missing tiles from the CDN.
   3. On a miss, the CDN calls the Tile service origin.
   4. Tile service serves a pre-rendered tile from storage, or renders it from the geo database and caches it.
   5. Client renders vector tiles on the GPU and styles them locally.
2. Search for a place with autocomplete — One query per keystroke at hundreds of thousands per second, answered in tens of milliseconds, biased toward where the user is looking.
   1. User types; client debounces and sends the prefix with viewport and location.
   2. API routes to the regional Place search service.
   3. Search service looks up the prefix in an in-memory trie and scores candidates.
   4. For full search (enter pressed) the places index is queried with geo bias.
   5. Client shows predictions; selecting one fetches place details and centres the map.
3. Compute a route with live traffic — Continental shortest path in under half a second, with edge weights that reflect traffic from two minutes ago.
   1. Client requests a route between origin and destination.
   2. API forwards to the Routing service for the region containing the origin.
   3. Routing snaps origin and destination to the nearest road segments.
   4. Routing runs a bidirectional query on the contraction hierarchy with traffic-adjusted weights.
   5. Routing builds the response: geometry, manoeuvres, ETA with and without traffic.
   6. Client renders the route on the map and offers to start navigation.
4. Turn-by-turn navigation and re-routing — The client does the per-second work locally; the server tracks the session, detects deviations, and re-routes without the user noticing.
   1. Client starts a navigation session with the chosen route.
   2. Client sends location pings every few seconds; it map-matches and announces manoeuvres locally in between.
   3. Navigation service map-matches server side and checks progress against the route.
   4. Navigation service forwards anonymised pings to the traffic stream.
   5. On deviation, Navigation asks Routing for a new route from the current position and pushes it to the client.
   6. Arrival ends the session; the client clears the corridor cache.
5. Live traffic: from pings to ETAs — Ten million pings a second become a speed per road segment per minute, and routing picks it up within two minutes.
   1. Pings arrive on the stream partitioned by geo cell.
   2. Traffic pipeline map-matches pings to road segments.
   3. Pipeline aggregates speed per segment per one-minute window.
   4. Pipeline writes current speeds to the traffic store and updates historical profiles.
   5. Routing servers pull deltas and re-customise their weights.
   6. Traffic overlay tiles are rendered from the same data for display.

Ask: Why ship geometry to the client instead of rendered images?

Good answers name: Vector tiles (MVT / protobuf), client-side rendering, Raster tiles, server-side rendering, Render whole viewports server side on demand.

Our pick: Vector tiles for all base map layers, raster for imagery (satellite) because it is inherently pixels. Tiles are immutable per map release and served from a CDN with year-long cache headers; the release version is in the URL path so a new release is an atomic key change. Pre-render zooms 0–14 at release time, render 15–20 on demand and cache back to storage. Keep a raster fallback endpoint for embeds and email, rendered from the same vector tiles server side.

1. A new map release goes out. How do you avoid a CDN miss storm for the whole planet at once?
   Warm the CDN for the top N most-requested tiles per edge before flipping the version, staged by region. Roll the version flag out to clients gradually over hours. Keep the previous version's tiles served for a week so old clients and in-flight sessions keep working. Request coalescing at the CDN caps origin load at one fetch per tile.
2. How big is a tile at zoom 16 in Manhattan versus in Kansas, and does that matter?
   Manhattan: hundreds of buildings, every road, POIs, could reach 500 KB uncompressed. Kansas: a few roads and fields, under 5 KB. It matters for the tail: dense tiles dominate render time on low-end phones. Mitigations are per-zoom feature simplification, dropping building footprints below zoom 15, and splitting dense layers (buildings, POIs) into separate tiles the client can defer.
3. Where does label placement happen and why is it hard?
   On the client, at render time, because labels must not overlap and must adapt to rotation and zoom. It is a collision detection problem run every frame; the renderer prioritises by importance, hides losers, and fades to avoid flicker. Server-side placement would bake one orientation and language into the tile.
4. How do offline maps work with this design?
   The client downloads the vector tiles for a bounding box at zooms up to 16 or so, plus the routing graph for the same area, as a package. Vector tiles make this feasible: a city is tens of MB rather than GB. Search and routing run locally against the package; online features degrade gracefully.

Ask: Textbook shortest path over 500 million edges takes seconds. How do you get to milliseconds and still respect live traffic?

Good answers name: Customisable Route Planning (multi-level overlay + fast customisation), Contraction Hierarchies with periodic re-contraction, Bidirectional A* with landmarks (ALT), Plain Dijkstra / A*.

Our pick: CRP. Preprocess the road graph into a multi-level partition once per map release (weekly). Every minute, pull traffic-adjusted segment speeds and run the customisation step per region, which recomputes overlay edge weights in seconds. Queries are bidirectional searches on the overlay, a few milliseconds each. Long-distance routes cross region boundaries via the top overlay level. For ETA on edges the driver will reach in 40 minutes, blend current speed toward the historical profile for that future time slot. This is, as far as public talks reveal, the approach used by the large map providers.

1. A road closes right now. How fast does routing stop using it, and how?
   The closure arrives as a segment weight of infinity through the same traffic overlay path, either from the pings (nobody moving through it) or from an authoritative feed. The next customisation run, within a minute, removes it from the overlay. Active navigation sessions get re-routed on their next ping if their route crosses it. No topology change is required because the edge still exists, it just costs infinity.
2. How do you handle turn restrictions and one-way streets in the graph?
   Edges are directed, so one-way is free. Turn restrictions (no left turn) do not fit a plain node-edge graph; the standard fix is an edge-based graph where routing nodes are road segments and edges are allowed turns, or expanding restricted intersections into small sub-graphs. This roughly doubles the graph size and is done at preprocessing time.
3. How would you give alternative routes that are genuinely different, not the same route with one detour?
   Penalty method: after finding the best route, multiply the weights of its edges by 1.2–1.5 and search again, repeat. Then filter alternatives by a similarity threshold (shared length under, say, 70 %) and by stretch (not more than 25 % longer). Via-node methods on the overlay graph do this more cheaply.
4. Memory: does the whole planet fit on one routing server?
   The base graph with geometry is around 50 GB; the overlay adds a fraction. It fits in a large-memory machine, but you would not do that: shard by region for parallelism and deploy regions near their users. Each server holds its region's full graph plus the coarse global overlay for cross-region queries, and reloads on a new map release with a blue-green swap.
5. ETA is off by 30 % on a specific highway every evening. Where do you look?
   First the sample count: if few navigating users drive it, the segment is falling back to a stale or wrong profile. Then the map-matcher: a parallel frontage road can steal or donate pings. Then the profile itself: a recent construction change shifts the pattern and the daily recompute may weight old data too heavily. The trip summary log (predicted vs actual per segment) is the tool for this.

Ask: How do you find the roads in a tile, the places near a point, or the segment a ping belongs to, fast?

Good answers name: Cell-based keys (S2 / geohash) as partition and index key, R-tree (PostGIS GiST), Quadtree.

Our pick: Use the right index per workload. The geo database uses PostGIS with GiST (R-tree) indexes because it holds polygons and lines and answers tile bounding-box queries. Everything that needs sharding or streaming uses S2 cell ids: the ping stream is keyed by a level-7 cell, the traffic store is a hash per cell, the places index is sharded by a coarse cell. Map-matching keeps an in-memory index of road segments bucketed by fine S2 cells so a ping lookup is one hash lookup plus a scan of a handful of segments in the cell and its neighbours. Explain the covering trick: a query rectangle becomes a small set of cell ranges, so a spatial query on a sorted store is a few range scans.

1. Why not just shard by country?
   Countries are wildly uneven (Monaco vs Russia) and queries near borders would hit two shards anyway. Cells give uniform-ish load, a natural hierarchy for rebalancing, and no political data model. You can still map cells to regional deployments for data residency.
2. A place search viewport straddles four S2 cells at your shard level. What happens?
   Scatter to the four shards, gather, and merge by score. That is fine and common; the goal of geographic sharding is to bound the fan-out to a handful of shards, not to guarantee one. Choose the shard cell level so a typical city viewport is one or two cells.
3. Map-matching at 10 M pings a second: describe the in-memory structure.
   Per consumer, for its assigned cells: a hash map from fine cell id (S2 level 16, ~100 m) to a small array of road segment ids with their geometry. A ping looks up its cell and the 8 neighbours, computes perpendicular distance to each candidate segment (tens at most), and feeds the candidates to the HMM. Memory per region is a few GB; lookups are sub-microsecond. The heavy part is the HMM, not the index.
4. How would you find POIs along a route, not near a point?
   Cover the route polyline with a buffer (say 500 m) as a set of cells, query the places index with a terms filter on those cells plus the category, then compute detour cost for the top candidates with the routing service. Covering a long route is many cells, so cap it or coarsen the cell level for long trips.

Ask: How do you turn ten million noisy location pings a second into trustworthy per-segment speeds, without building a surveillance system?

Good answers name: Streaming aggregation per segment with historical fallback, Batch recompute every 5–15 minutes, Road sensor and authority feeds only.

Our pick: A streaming pipeline partitioned by geo cell. Pings are anonymised at the Navigation service before they enter the stream: user and session ids stripped, a rotating trip token that lives for a few minutes so consecutive pings can be map-matched, and pings within a few hundred metres of trip start and end dropped. The pipeline map-matches, aggregates a median speed per segment per one-minute sliding window with a minimum sample count, and writes to a per-cell hash in the traffic store with a five-minute TTL. Segments without fresh data fall back to a profile keyed by weekday and 15-minute slot, recomputed daily. Authority feeds inject closures directly. Routers pull deltas every 30–60 seconds. Publish an internal freshness SLO: 95 % of observed segments updated within 90 seconds.

1. A single user drives slowly to inflate congestion on their street. Does it work?
   Not with the minimum sample threshold: one trip token cannot move the median, and a segment needs several distinct tokens in the window to count as observed. A coordinated group (the Berlin wagon-of-phones experiment) can, which is why you add anomaly detection: sudden congestion with no upstream or downstream effect, or from tokens that never move like cars, gets down-weighted.
2. What is the privacy risk in the pipeline and how is it bounded?
   Reconstructing trips. The pipeline needs short sequences of pings to map-match, so it sees a few minutes of one token. Bound it: token rotation every few minutes, trimming near origin and destination, no persistence of raw pings beyond the stream retention of hours, aggregates only in the store, and access controls plus audit on the raw topic. Differential privacy noise on low-count aggregates is a further step.
3. How do you validate that the traffic data is actually improving ETAs?
   The navigation trip log: predicted duration at departure versus actual. Compare error distributions for routes with and without live traffic applied, per region and time of day, and track it as a product metric. Holdout experiments (a small percentage of routes ETA'd without live data) give a clean baseline.
4. The stream job falls 10 minutes behind after an incident. What do users see and how do you recover?
   The store's TTL expires stale speeds, so routing falls back to profiles: ETAs get less accurate but never wrong in a dangerous way. Recovery: the job must skip ahead rather than process 10 minutes of stale pings, because a minute-old speed is worthless. Windows with end time older than the freshness budget are dropped on the floor. Alert on consumer lag as the primary health metric.

Ask: The phone has the GPS and the screen; the server has the graph and the traffic. Where does each piece of work belong?

Good answers name: Client executes guidance locally; server plans and re-routes, Server does everything; client is a thin display, Client does everything including routing on an on-device graph.

Our pick: Client-executed, server-supervised. At session start the client receives the route with geometry, instructions, and per-step distances, and prefetches tiles for the corridor. It runs a lightweight map-matcher against the route at 1 Hz and times announcements locally. Pings are batched to the server every few seconds; the server runs the authoritative map-matcher, updates ETA with fresh traffic, detects deviation with hysteresis, and pushes a new route when needed. If the network drops, the client keeps guiding on the current route and, after a long gap, can fall back to on-device routing over the offline package if present. Both matchers share the same algorithm and parameters to minimise disagreement.

1. GPS says the car is 30 m off the route in a dense city. Re-route or not?
   Not yet. Urban canyons produce 30–50 m errors routinely. Use the reported accuracy radius, heading agreement with the route, and require several consecutive off-route fixes, with a distance threshold scaled by accuracy. The cost of a false re-route (confusing instructions) is higher than a two-second delay in a true one.
2. How does the server push a new route to the client, given the client is polling with pings?
   Piggyback on the ping response: the response to a batch of pings carries either "on route, ETA X" or the new route. That keeps a single request path and avoids a separate push channel. For faster delivery, a persistent HTTP/2 or WebSocket connection per session can carry server-initiated messages, but the piggyback is sufficient at a 3–5 second ping interval.
3. What state does the Navigation service hold, and what happens if that server dies?
   Per session: route, destination, preferences, last matched position, deviation counter. It is small and can live in a shared store (Redis) keyed by session id, so any server can handle any ping. If a server dies, the next ping goes elsewhere and the session continues. The client tolerates a missed ping response anyway, so failover is invisible.
4. Battery: 1 Hz GPS and a radio ping every few seconds drain the phone. What can you do?
   Fuse GPS with accelerometer and gyroscope to reduce GPS duty cycle on straight stretches; batch pings and coalesce with tile fetches to let the radio sleep; reduce ping frequency on motorways where the next decision is far away and increase it near manoeuvres. The server can suggest the interval in the ping response.

Ask: An ETA is a forecast, not a sum. What goes into it and how do you make it accurate?

Good answers name: Time-dependent routing weights + learned correction model, Sum of current segment times, End-to-end learned model over the whole route.

Our pick: The routing engine computes a time-dependent ETA: for each edge, use the live speed if the edge is reached within the next ~15 minutes, blending toward the historical profile for the predicted arrival time slot beyond that. Add turn penalties and signal delays per intersection type from the graph. Then apply a learned correction model (gradient boosting, later a GNN) trained on completed navigation trips, with features like route length, road class mix, region, time, weather, and the baseline ETA. Serve the model in the routing response path with a strict latency budget. Track median and p90 absolute percentage error per region as the north-star metric, and run holdouts to measure each component's contribution.

1. Training data is only from people who used navigation. Why is that a problem and what do you do?
   Navigating users skew toward unfamiliar routes, long trips, and certain demographics, so the model learns their behaviour. Locals on familiar routes drive differently. You cannot fully fix it, but you can reweight by trip type, use the traffic pings from all users (not just navigators) for segment speeds, and monitor error on trips that were routed but not navigated when available.
2. Should the ETA update during the trip, and how often?
   Yes, on every ping response, using the remaining route and fresh traffic. Smooth it so it does not jitter: only show changes above a threshold and rate-limit updates to every 30 seconds or so. A jumping ETA erodes trust more than a slightly stale one.
3. How do you evaluate a new ETA model safely?
   Offline first on held-out trips with the same metric. Then online with a shadow deployment: compute both ETAs, show the old, log both against actual arrival. Then a small-percentage experiment showing the new one. Watch for regional regressions, since aggregate improvement can hide a region getting worse.
4. Departure time is tomorrow at 8 am. What changes?
   No live traffic applies; the whole route uses historical profiles for the predicted time slots, plus the model. Uncertainty is larger, so present a range rather than a point estimate. Also reroute choice may differ: the best route at 8 am tomorrow is not the best route now, so run the query with the future time-dependent weights.