Google Maps System Design Interview: Geospatial Indexing, Tile Serving, and Continent-Scale Routing
Google Maps covers more than 200 countries and territories and, by Google's public statements, over a billion monthly active users. It renders the whole planet as a pyramid of map tiles, answers routing queries across a continent-sized road graph in a fraction of a millisecond, and folds live GPS signals from a very large fleet of phones into traffic and ETA predictions. The device counts and query rates here are estimates unless a number is explicitly published.
The problem breaks into four hard subsystems that barely share code. First, geospatial indexing: you have to store points of interest and road geometry for the entire globe and answer 'what is near this lat/long' in milliseconds, which pushes you toward a space-filling-curve index like Google's S2 rather than a naive lat/long B-tree. Second, map rendering: the visible map is a tile pyramid keyed by zoom, x, and y, served mostly from CDN, and modern clients pull vector tiles so the same bytes restyle and rotate on the GPU. Third, routing: plain Dijkstra or A* explores far too many nodes to route across a country, so production systems precompute shortcuts (contraction hierarchies and related techniques) to prune the search to a few hundred nodes. Fourth, ETA and live traffic: phones send anonymized GPS probes, a pipeline aggregates them into per-segment speeds, and a machine-learning model, in Google's case a Graph Neural Network over road Supersegments, predicts travel time and feeds those edge weights back into routing. Around all four sit place search, autocomplete, and reverse geocoding. The interview is really about picking the right spatial data structure and the right precomputation strategy for each piece.
Asked at: Asked at Google, Uber, Lyft, DoorDash, Amazon, and most companies that run maps, dispatch, or location features. Variants show up as 'design nearby search', 'design a routing engine', or 'design Yelp'.
Why this question is asked
It forces a candidate off the standard CRUD-and-cache template and into spatial data structures, graph algorithms, and precomputation tradeoffs that most web systems never touch. A strong answer shows you know that indexing a sphere is not the same as indexing a number line, that shortest-path at continent scale is a preprocessing problem and not just an algorithm choice, and that ETA is a streaming and ML problem rather than a simple lookup. It also has clean layers, so an interviewer can start easy with nearby search and push all the way into contraction hierarchies and traffic pipelines depending on your level.
Requirements
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
Functional requirements
- Render an interactive world map at many zoom levels, panning and zooming smoothly.
- Search for places and addresses, including prefix autocomplete as the user types.
- Find points of interest near a location, for example restaurants within two kilometers.
- Reverse geocode: turn a latitude and longitude into a human-readable address.
- Compute driving, walking, cycling, and transit routes between two or more points.
- Show a realistic ETA that accounts for current and predicted traffic.
- Display live traffic conditions colored by congestion on the map.
- Ingest continuous location updates from navigating devices to keep traffic fresh.
- Support rerouting when a driver misses a turn or conditions change mid-trip.
Non-functional requirements
- Tile and search reads must feel instant, low tens of milliseconds at the edge.
- Route computation should return in well under a second even across a country.
- Very high read-to-write ratio for tiles and places; writes are map updates and probes.
- Global availability with graceful degradation, for example stale traffic beats no map.
- Horizontal scalability to a billion-plus users and a very large probe volume.
- Freshness targets: traffic within a few minutes, base map updated over days to weeks.
- Location and probe data must be anonymized and privacy-preserving.
Back-of-envelope scale estimates
Show your math. Pulling numbers from thin air signals you have not thought about the load.
Monthly active users
1B+ (published, order of magnitude)
Google has repeatedly described Maps as a product with over a billion users. Exact live counts are not published, so treat this as an order-of-magnitude anchor.
Tile requests per second
~1-2M tiles/sec at peak (Derived, estimate)
Assume 50M concurrent map sessions at peak and each session fetching roughly 10 tiles per active minute. 50M * 10 / 60 is around 8M/sec of demand, and CDN caching absorbs most of it, so origin sees a small fraction. Purely illustrative arithmetic, not a Google figure.
Road graph size
Hundreds of millions of nodes and edges (estimate)
The global drivable network is commonly cited in the hundreds of millions of road segments. This dwarfs main memory on one machine, which is exactly why routing is partitioned and precomputed.
GPS probes ingested
Tens of billions/day (Derived, estimate)
If 100M devices navigate daily and each emits a probe roughly every 5 seconds for an hour, that is 100M * 720 = 72B points/day. The input assumptions are estimates; the point is the pipeline is a firehose measured in tens of billions.
S2 cell id space
~6 x 10^18 leaf cells (published)
S2 subdivides the six cube faces down to level 30, giving about 6 x 10^18 leaf cells roughly 1 cm across, each addressable by a 64-bit id. This is a property of the S2 library, not a load estimate.
Route query latency budget
Sub-millisecond core search (published for CH)
Contraction-hierarchy research reports shortest-path queries that visit only a few hundred nodes and finish in a fraction of a millisecond after preprocessing. End-to-end user latency is larger because of network, ETA, and rendering.
High-level architecture
A client request splits by concern. Map viewing hits a tile service: the client computes which tile coordinates (zoom, x, y) cover the viewport, requests them, and a CDN serves cached tiles, falling back to a tile origin that reads pre-generated or on-the-fly-rendered vector tiles from blob storage. Place search and autocomplete go to a search service backed by an inverted index plus a geospatial index, where the geospatial index uses S2 cell ids so a 'nearby' query becomes a range scan over a handful of cell-id ranges. Reverse geocoding maps a point to its enclosing S2 cells and looks up the features that cover them. Routing goes to a route service that holds the road network as a partitioned, preprocessed graph: it runs a bidirectional search accelerated by contraction-hierarchy shortcuts, weights edges with current and predicted travel times, and returns a polyline plus an ETA. Traffic and ETA run as their own pipeline off to the side: navigating devices stream anonymized GPS probes into an ingestion layer, a stream processor map-matches them to road segments and aggregates per-segment speeds, and a machine-learning model turns those into predicted travel times that are published back to the routing edge weights on a short cycle. Everything reads far more than it writes, so caching sits at every layer, from CDN tiles to cached popular routes to in-memory current-traffic tables.
In a real interview, sketch this on the whiteboard before diving into any single box.
Core components
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
Tile service and CDN
Serves the map as a pyramid of tiles addressed by zoom, x, and y. Vector tiles carry geometry and attributes that the client styles and rotates on the GPU, so one tile set supports day mode, night mode, and 3D. The CDN absorbs the overwhelming majority of reads because base-map tiles change slowly and are shared across all users.
Geospatial index
Indexes points of interest and features by S2 cell id so that spatial proximity becomes numeric proximity on a 1D curve. A nearby query computes an S2 cell covering for the search area and scans a small set of contiguous cell-id ranges, then filters by exact distance. This is what makes 'restaurants within 2 km' cheap.
Place search and autocomplete
An inverted index over place names, addresses, and categories, combined with the geospatial index and a ranking model that blends text relevance, distance, and popularity. Autocomplete serves prefix matches with very low latency, usually from an in-memory trie or FST fronted by heavy caching of common prefixes.
Routing engine
Holds the road network as a directed, weighted, partitioned graph and answers shortest-path queries. It relies on precomputed shortcuts (contraction hierarchies and related overlay techniques) so a query prunes to a few hundred nodes instead of exploring an entire continent. Edge weights are refreshed from the traffic pipeline.
Probe ingestion and map matching
Accepts a firehose of anonymized GPS points from navigating devices, then map-matches each noisy point to the most likely road segment and direction. Map matching is nontrivial because GPS drifts near overpasses, tunnels, and parallel roads, so it usually uses a hidden Markov model over candidate segments.
Traffic aggregation and ETA model
A stream and batch pipeline that turns map-matched probes into per-segment speed distributions, then predicts travel time. Google's published approach groups adjacent segments into Supersegments and trains a Graph Neural Network to predict times across them, blending live probe data with historical patterns.
Base map data pipeline
An offline pipeline that fuses satellite imagery, Street View, authoritative datasets, and user contributions into the canonical map, then compiles it into tiles and routing graphs. This is a heavy batch process that publishes new artifacts on a slow cadence measured in days to weeks per region.
Data model
Pick the right store per table. Justify each choice with the access pattern, not by reflex.
placesplace_idnamelatlngs2_cell_idcategoryThe s2_cell_id is the workhorse index: store the leaf cell id and often a few parent-cell ids so nearby queries reduce to cell-id range scans. Text fields feed the inverted index. Denormalize rating and popularity for ranking.
road_segmentssegment_idfrom_nodeto_nodegeometrylength_mroad_classThe routing graph edges. road_class (highway, arterial, residential) drives both default speeds and the contraction order during preprocessing. Geometry is stored compactly with polyline encoding for rendering the route.
ch_shortcutsshortcut_idfrom_nodeto_nodevia_nodeweightlevelPrecomputed contraction-hierarchy shortcuts that let bidirectional search skip over contracted nodes. Rebuilt when topology changes; weights are time-dependent and refreshed as traffic updates rather than fully recomputing the hierarchy.
segment_trafficsegment_idwindow_startspeed_kmhsample_countconfidenceRolling per-segment speeds derived from map-matched probes. window_start is a short bucket, for example one to five minutes. confidence falls when sample_count is low, in which case the model leans on historical priors.
probe_eventsanon_trip_idtslatlngheadingspeedRaw anonymized location pings, retained only briefly. anon_trip_id is rotated and not linkable to a user identity. This is append-only, extremely high volume, and consumed by the streaming map-matcher rather than queried directly.
tileszoomxylayerversionblob_refMetadata for map tiles in blob storage. version supports cache busting and staged rollouts of new map data. Most reads never reach this table because the CDN answers them; the origin uses it to locate the tile blob.
Deep dives
These are the conversations the interviewer is steering you toward. Practice each one until you can talk through it without notes.
Geospatial indexing with S2 versus geohash and quadtrees
The core trick for nearby search is to map two-dimensional positions onto a one-dimensional space-filling curve so that a normal ordered index can answer spatial range queries. Geohash does this by interleaving latitude and longitude bits into a base-32 string, which is simple but has ugly seams at the equator and antimeridian and distorts cell sizes because it works in lat/long space. Google's S2 instead projects the sphere onto the six faces of a cube and orders cells along a Hilbert curve, producing 64-bit cell ids where numeric closeness strongly implies spatial closeness and cell areas stay far more uniform. A nearby query computes a cover, the small set of S2 cells that tile the query region at an appropriate level, and each cell becomes a contiguous id range to scan. Quadtrees are the other classic answer and are effectively what the tile pyramid is: recursive four-way subdivision that adapts depth to data density. In an interview the winning point is that all three turn 2D proximity into 1D ranges; S2 just does it on the sphere with better locality and no projection seams, which is why it underpins Maps and BigQuery GIS.
The tile pyramid, vector versus raster, and CDN delivery
The map is served as tiles, not as one giant image. At zoom level z the world is divided into 2^z by 2^z tiles, each conventionally 256 by 256, addressed by (z, x, y). The client figures out which tiles cover the viewport and requests only those, so bandwidth scales with screen size, not with map size. Older systems shipped raster tiles, pre-rendered PNGs, which are dead simple to cache but fix the style and label language at render time and get blurry between zooms. Vector tiles ship the underlying geometry and attributes and let the client draw them on the GPU, so the same tile restyles for night mode, rotates for heading-up navigation, and stays crisp on high-DPI screens, at the cost of more client work. Either way the delivery story is a CDN: base tiles are identical for every user and change slowly, so cache hit rates are extremely high and the origin only handles misses and freshly updated regions. Cache busting is handled with a version in the tile key so a map data release does not serve stale geometry.
Why Dijkstra and A* do not scale, and contraction hierarchies
Dijkstra explores outward uniformly and on a continent-sized graph will touch tens of millions of nodes before it reaches the destination, which is far too slow for interactive routing. A* with a good heuristic, for example straight-line distance, helps by biasing the search toward the goal, but on long intercity routes it still explores an enormous frontier because highways and back roads all look locally similar. The production answer is preprocessing. Contraction hierarchies, introduced by Geisberger and colleagues, rank nodes by importance and contract them one by one from least to most important, inserting shortcut edges that preserve exact distances whenever removing a node would otherwise change a shortest path. At query time a bidirectional search only ever moves upward in this hierarchy, so it prunes to a few hundred nodes and returns in a fraction of a millisecond while still being exact. The catch is that shortcuts encode edge weights, and live traffic changes weights constantly, so real systems use time-dependent or customizable variants that keep the expensive topology preprocessing stable while refreshing weights cheaply. Interviewers love this because it is the clearest example of trading preprocessing time and storage for query latency.
Partitioning the road graph across machines
A hundreds-of-millions-of-edge graph does not fit or preprocess well on a single node, so the network is partitioned into regions or cells, often aligned to geography or to a cut that minimizes edges crossing partition boundaries. Within each partition you precompute internal shortest paths, and at the boundaries you keep a smaller overlay graph of border nodes that stitches partitions together. A cross-region route then becomes: route to the boundary of the source partition, hop across the overlay of border nodes, and route from the destination boundary inward. This is the idea behind overlay and multilevel approaches and it maps naturally onto a distributed system where each partition is served by its own shard and the overlay is small enough to keep hot. Partitioning also localizes updates: a road closure in one metro only invalidates that partition's preprocessing, not the planet's, which matters a lot when you are refreshing continuously.
GPS probe ingestion, map matching, and traffic aggregation
Live traffic comes from the phones themselves. Navigating and, with consent, background devices emit anonymized location pings, and the pipeline first has to solve map matching: a raw GPS point can land 20 meters off the true road, near an overpass it may be ambiguous between the surface street and the highway above it, so a hidden Markov model over candidate segments picks the most probable path given the sequence of points and the road topology. Matched points are bucketed by segment and short time window to produce per-segment speed distributions, with confidence tied to how many independent probes landed in the window. Sparse segments fall back to historical priors for that road, time of day, and day of week. This is a classic streaming problem: high-volume, out-of-order, needs windowing and watermarks, and needs to publish fresh aggregates every minute or few minutes. The output, current per-segment speeds, becomes the live edge weights for routing and the colored congestion overlay on the map.
ETA prediction with Graph Neural Networks over Supersegments
Summing per-segment speeds gives a naive ETA, but it ignores interactions: the delay at a turn, the queue that spills back from a downstream light, the merge that only bites at rush hour. Google's published work with DeepMind groups adjacent, traffic-correlated segments into Supersegments and trains a Graph Neural Network where each segment is a node and edges connect consecutive or intersecting segments, letting the model do spatiotemporal reasoning over the local network rather than treating segments independently. A single trained model handles routes from two segments to a hundred-plus nodes. Google reported ETA accuracy improvements of up to 50 percent in cities including Berlin, Jakarta, Sao Paulo, Sydney, Tokyo, and Washington D.C., and has stated ETAs are accurate for the large majority of trips. The training needed care: they used techniques like MetaGradients to stabilize learning across highly variable graph structures and a combined loss to generalize. The design lesson is that ETA is a learned function of live plus historical traffic and road structure, and the model output feeds back into the routing weights, closing the loop between prediction and route choice.
Reverse geocoding, place search, and autocomplete
Reverse geocoding turns a coordinate into an address by finding which map features contain or sit closest to the point. Using S2, you compute the leaf cell for the point and walk up to parent cells, then look up the address ranges, buildings, and administrative polygons indexed against those cells, resolving the most specific containing feature. Forward place search is an information-retrieval problem: an inverted index over names, categories, and address tokens, intersected with a geospatial filter so results are biased to the user's area, then ranked by a blend of text match, distance, and popularity. Autocomplete is the latency-critical piece because it fires on nearly every keystroke, so it runs off an in-memory prefix structure such as a trie or finite-state transducer, aggressively caches popular prefixes, and personalizes with recent and nearby results. The shared theme with the rest of the system is that geography is always a filter layered on top of a text or graph structure, and S2 cells are the join key that makes that filter cheap.
Trade-offs to discuss
Every senior interviewer expects you to surface at least 3 of these. Pick the decisions, state the alternatives, and justify your choice.
Vector tiles versus pre-rendered raster tiles
Vector tiles restyle, rotate, and stay sharp on any display and cut bytes for label-heavy maps, but push rendering work to the client and complicate the pipeline. Raster tiles are trivial to cache and render but freeze style and language and blur between zooms. Modern Maps favors vector for the flexibility navigation needs.
S2 space-filling curve versus geohash for spatial indexing
Geohash is simpler and string-friendly but distorts near poles and the antimeridian and has uneven cell areas. S2 keeps cell sizes uniform, avoids projection seams by working on the sphere, and packs into sortable 64-bit ids with strong locality. S2 costs more conceptual complexity for much better geometric behavior.
Precompute contraction hierarchies versus route on demand
Precomputing shortcuts turns a multi-second continental search into a sub-millisecond query, at the cost of preprocessing time, extra storage for shortcuts, and the pain of updating them when traffic and topology change. On-demand A* needs no preprocessing but cannot meet interactive latency at country scale, so precomputation wins for a routing product.
Freshness versus cost in the traffic pipeline
Updating every segment's speed and re-publishing routing weights every few seconds would give the freshest traffic but at enormous compute cost and noisy, low-confidence data on quiet roads. Aggregating over short windows and leaning on historical priors where probes are sparse trades a little staleness for stability and far lower cost.
Serving base tiles from CDN versus rendering per request
Base map tiles are identical across users and change slowly, so caching them at the CDN edge gives near-instant loads and shields the origin. Rendering on every request would allow perfect personalization but is wasteful and slow. Personalized and dynamic layers, like traffic and your pin, are composited separately on top of the cached base.
Sum-of-segments ETA versus a learned Supersegment model
Adding up per-segment travel times is cheap and easy to reason about but misses turns, merges, and congestion spillback, so it is systematically off on complex routes. A Graph Neural Network over Supersegments captures those interactions and is far more accurate, at the cost of training infrastructure, model serving, and harder debuggability.
How Google Maps actually does it
Google open-sourced the S2 Geometry library, which projects the sphere onto a cube and orders cells along a Hilbert curve, and it is used across Maps, Earth, and BigQuery GIS. The routing techniques in this space trace directly to published academic work, most notably contraction hierarchies from Geisberger, Sanders, Schultes, and Delling, along with later customizable and time-dependent variants that make live traffic practical. On ETA, Google and DeepMind published their Graph Neural Network approach over Supersegments, reporting accuracy gains up to 50 percent in several major cities and describing the training tricks needed to stabilize learning across variable graph structures. The map itself is compiled offline from satellite imagery, Street View, authoritative data, and user edits, then published as tiles and routing graphs. Where a specific internal detail is not public, treat the description here as the standard system-design approach rather than a claim about Google's exact implementation.
Sources
- S2 Geometry developer guide: cell hierarchy
- DeepMind: Traffic prediction with advanced Graph Neural Networks
- ETA Prediction with Graph Neural Networks in Google Maps (CIKM 2021)
- Contraction Hierarchies (Geisberger, Sanders, Schultes, Delling, 2008)
- Christian Perone: Google's S2, geometry on the sphere, cells and Hilbert curve
Lessons to study before this interview
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.
Related system design interview questions
Practice these next. They lean on the same core building blocks as Google Maps.