Google Maps Cheat Sheet

Key concepts, trade-offs, and quick-reference notes for your interview prep.

Quadtree Tile Pyramid: Tiles Quadruple per Zoom Level

The world map is divided into a quadtree tile pyramid with 22 zoom levels (0 through 21). At zoom level

z

, the tile count is

4^z

: level 0 has 1 tile, level 10 has roughly 1 million, level 18 has about 69 billion tiles. Each tile is addressed by three coordinates:

z/x/y

. The client requests only the 30 to 40 tiles visible in the current viewport. We pre-render tiles offline because rendering a single tile from raw geodata takes 50 to 200ms of GPU compute. At 521K requests/sec, on-demand rendering would need 26,000 GPUs. Pre-rendered tiles are served as static files from CDN. Trade-off: map updates propagate with a 1 to 2 week delay.

💡 Tiles are pre-rendered, not generated on demand. Tile count quadrupling at every zoom level makes on-demand rendering infeasible at scale.

Vector Tiles over Raster: 3x Smaller, Client-Rendered

We chose vector tiles (Protocol Buffer MVT format) over raster PNG tiles because vector tiles contain geometric primitives (polylines, polygons, points) that the client GPU rasterizes using a style sheet. A vector tile at zoom 14 is 20 to 50 KB compressed versus 80 to 200 KB for a raster PNG. This 3 to 4x size reduction cuts CDN bandwidth and enables client-side rotation, re-styling, and retina rendering without a server round-trip. Google, Mapbox, and Apple all migrated from raster to vector between 2013 and 2015. Trade-off: vector tiles push rendering to the client GPU. Low-end devices fall back to pre-rasterized PNG tiles.

⚠ Serving raster PNG tiles and re-rendering the full 500 TB tile set every time the map style changes. Vector tiles decouple data from presentation.

CDN Absorbs 98% of 521K Tile Requests/sec

Tile QPS:

300\text{M DAU} \times 5\text{ sessions} \times 30\text{ tiles} / 86{,}400 = 521\text{K tiles/sec}

. CDN absorbs 98%, so origin handles only 10.4K tiles/sec. The 98% hit rate (versus music's 99%) is because map tiles have higher diversity: zoom level, region, and style all create distinct cache keys. Each POP caches the hot tile set for its geographic region. We stagger tile regeneration across POPs over 24 hours to prevent simultaneous cache invalidation. Trade-off: staggered rollout means some POPs show older tiles for up to 24 hours during a map update cycle.

⚠ Invalidating all CDN tiles globally on a map update. This sends 521K requests/sec directly to origin, overwhelming the tile rendering infrastructure.

Contraction Hierarchies: 100x Faster Than Dijkstra

We chose Contraction Hierarchies (CH) over Dijkstra and A* for routing on a 500M-node road graph. Offline preprocessing (30 minutes for the US graph) contracts low-importance nodes and adds shortcut edges to preserve shortest-path distances. At query time, bidirectional upward search explores roughly 1,000 nodes in under 10ms versus millions of nodes in 500ms for Dijkstra. The CH graph with shortcuts fits in 100 GB per routing server. We deploy 230 servers for 23K peak QPS at ~100 queries/server/sec. Trade-off: preprocessing takes 30 minutes and must be partially re-run when roads permanently change. Road closures use a real-time Redis overlay instead.

💡 CH trades expensive offline preprocessing for sub-10ms online queries. The key insight is bidirectional upward-only search that explores ~1,000 nodes.

Real-Time Edge Weight Overlay from Redis

The static CH graph uses base travel times derived from speed limits and road type. But real-time conditions (congestion, accidents, road closures) change edge weights constantly. We solve this with a two-layer approach: the static CH graph provides the structural shortest path, and a Redis overlay adjusts edge weights using live traffic data. The overlay stores 50M road segment speeds in 900 MB of Redis, updated every 60 seconds from GPS probes. When a road closes, we set its edge weight to infinity in the overlay, forcing CH search to find alternatives. Trade-off: the overlay does not change the CH node ordering (which was computed with base weights), so routes may be suboptimal by 1 to 3% compared to a full re-contraction with live weights.

⚠ Re-contracting the full CH graph in real time when traffic changes. Preprocessing takes 30 minutes, far too slow for 60-second traffic updates. Use an edge weight overlay instead.

4M GPS Probes/sec: Raw Sensor to Road Segment Speed

20M active navigators each send a GPS probe every 5 seconds:

20\text{M} / 5 = 4\text{M probes/sec}

at 40 bytes each = 160 MB/sec. The pipeline has three stages: (1) HMM map matching snaps noisy GPS coordinates (5 to 15m accuracy) to the correct road segment, handling overpasses and parallel roads. (2) Speed aggregation computes median speed per road segment in a 60-second sliding window. Segments with fewer than 3 probes fall back to historical speed averages with a confidence weight. (3) Redis publish: 50M segments x 18B = 900 MB, read by routing servers for traffic-aware edge weights. Trade-off: 60-second aggregation smooths noise but delays detecting sudden congestion by up to 60 seconds.

💡 Raw GPS is noisy (5-15m accuracy). Map matching with HMM is essential before speed aggregation. Without it, probes from overpasses corrupt surface road traffic estimates.

Two-Stage ETA: CH Routing + ML Correction to 97%+ Accuracy

We chose a two-stage ETA model. Stage 1: Contraction Hierarchies computes the shortest-time path using live traffic edge weights from Redis, producing a graph-based ETA. Stage 2: a gradient-boosted decision tree (GBDT) takes the CH ETA plus 15 features (day of week, hour, weather, traffic signal count, historical variance) and outputs a correction factor (0.95 to 1.10). Google reports this achieves 97%+ accuracy (actual arrival within 3% of predicted). During navigation, ETA re-estimates every 30 seconds from the current position. Trade-off: the ML layer adds 5 to 10ms latency per query, acceptable within the 500ms total budget.

⚠ Using distance divided by speed limit for ETA. Real-world speeds vary by time of day, weather, road type, and traffic signals. Simple division yields 20-30% ETA errors.

HMM Map Matching: Snapping GPS to the Correct Road

Raw GPS coordinates have 5 to 15m accuracy, insufficient to distinguish between an overpass and the road below it. We use a Hidden Markov Model (HMM) where states are candidate road segments within 50m of the GPS reading. Emission probability depends on GPS-to-road distance. Transition probability depends on route distance between candidates versus GPS distance between readings. The Viterbi algorithm finds the most probable road sequence. Map matching serves two critical purposes: (1) navigation accuracy (ensuring turn-by-turn references the correct road) and (2) traffic probe processing (attributing speed to the correct segment). Trade-off: adds 2 to 5ms per GPS reading, negligible compared to routing errors from unmatched coordinates.

💡 Map matching is not optional. A probe on an overpass attributed to the road below corrupts traffic estimates for both roads.

Elasticsearch for 200M POI Search with Geo Filtering

We chose Elasticsearch (not PostgreSQL LIKE queries) for 200M POI search because free-text queries with geo-proximity ranking at scale require inverted indexes with geospatial support. Each POI averages 500 bytes: place_id, name, category, address, lat/lng, rating, review_count, hours. Total:

200\text{M} \times 500\text{B} = 100\text{ GB}

, replicated 3x = 300 GB. We use a two-phase query: (1) geo filter to a bounding box (typically 5 km radius), then (2) BM25 text search on name and category, boosted by rating and distance. Trade-off: Elasticsearch replication costs 3x storage but delivers sub-200ms full-text search that PostgreSQL GIN indexes cannot match at 200M rows.

⚠ Using SQL LIKE queries on a 200M-row places table. LIKE '%coffee%' triggers a full table scan, taking seconds instead of the required 200ms.

Traffic Overlay Tiles with 60-Second TTL

#10

Base map tiles are pre-rendered and cached for weeks. But traffic conditions change every minute. We solve this with a separate traffic overlay tile layer that renders congestion colors (green/yellow/red) on top of the base map. Traffic tiles have a 60-second TTL in the CDN. The client fetches traffic tiles independently from base tiles, so a traffic refresh does not invalidate the base tile cache. Traffic tiles are generated on demand from the 900 MB Redis traffic segment data: each tile queries only the segments visible at that zoom/x/y and renders colored polylines. At zoom 14 (city level), each traffic tile covers a few hundred segments. Trade-off: 60-second TTL means traffic colors can lag by up to 60 seconds, but shorter TTLs would increase CDN miss rates significantly.

⚠ Baking traffic colors into the base map tiles. This forces re-rendering and re-caching 500 TB of tiles every 60 seconds, which is impossible.