Design Google Maps

A system design for a mapping and navigation platform handling tile-based rendering, real-time routing with traffic awareness, geocoding, and offline maps. The interesting part is not “draw a map and find a path” — it is the gap between a textbook Dijkstra (seconds per query on a continental graph¹) and the sub-millisecond response a navigation app actually needs, plus the operational reality of overlaying live traffic on a precomputed hierarchy without rebuilding it.

Abstract

A mapping platform is really three loosely-coupled systems wearing one URL:

1. Map rendering — a quadtree tile pyramid built on the Web Mercator projection (EPSG:3857). Zoom 0 is one 256×256 tile covering the world; each zoom doubles the linear resolution². Tiles are static, cacheable, and overwhelmingly read-heavy, so they belong on a CDN with very high hit ratios.

2. Routing — plain Dijkstra is in the seconds per query on a continental graph¹, which is unusable for navigation. Production engines preprocess the road network into a Contraction Hierarchies (CH) graph³ so that query-time work collapses to a bidirectional “upward-only” search; OSRM reports a 163 µs median query on the 87M-vertex North America graph⁴. Real-time traffic is overlaid as edge-weight multipliers on top of the static hierarchy, not by rebuilding it.

3. ETA prediction — Google Maps reports that ETAs were already accurate within ±10 % on more than 97 % of trips before its 2020 work with DeepMind; a Graph Neural Network operating on “supersegments” (sequences of adjacent road segments) then cut negative ETA outcomes by up to 50 % in cities like Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C.⁵⁶.

The core trade-off everywhere is preprocessing time vs. query latency, and the hidden constraint is how dynamic the inputs are. CH wins when the road graph is stable and traffic is layered as a multiplier; Customizable Route Planning (CRP) wins when the metric itself changes (driving vs. walking, hourly cost overlays).

Requirements

Functional Requirements

Non-Functional Requirements

Scale Estimation

The exact daily numbers are not public; Google has stated that Maps has more than 2 billion monthly active users⁷. The estimates below are interview-style back-of-the-envelope, not measured production figures.

Users (assumed):

• MAU: ~2 B (publicly stated⁷).
• DAU: ~1 B (≈ 50 % of MAU; sensitivity analysis: doubling DAU only doubles RPS, all conclusions hold).
• Peak concurrent: ~100 M (≈ 10 % of DAU).

Tile traffic (estimate):

• Average session: 50 tile requests (zoom/pan).
• Daily tile requests: 1 B × 50 = 50 B/day.
• Peak RPS: 50 B / 86,400 × 3 ≈ 1.7 M RPS, almost all absorbed by the CDN.

Routing traffic (estimate):

• ~2 routes per DAU per day → 2 B/day ≈ 23 K RPS average, ~70 K RPS peak.

Storage (order-of-magnitude):

• Global road network: ~10⁸–10⁹ edges depending on attributes.
• CH index: tens of bytes per node of overhead on top of the original graph³; tens of TB for a global dataset, sharded by region.
• Vector tiles across all zoom levels: tens of PB before compression.
• Traffic observations: 10⁹ segments × 24 h × 4 B/observation per hour ≈ 30+ TB/year of raw probe-aggregated data.

Design Paths

The shortest-path literature offers three viable production techniques; pick by how much the underlying graph and the metric move.

Path A: Preprocessing-heavy — Contraction Hierarchies

Best when the road network is stable, query latency is the dominant requirement, and live traffic can be applied as a per-edge multiplier on top of a precomputed structure.

• Preprocess offline: order nodes by a “least-important first” heuristic, then iteratively contract them and add shortcut edges that preserve shortest-path distances³.
• At query time, run bidirectional Dijkstra but only relax edges that go “upward” in the hierarchy. The two searches meet at the highest-importance node on the optimal path.
• Apply traffic as edge_weight = base_weight × traffic_multiplier; the topology never changes, so the hierarchy stays valid.

Trade-offs:

• ✅ Median query times in the hundreds of microseconds on continental graphs (OSRM: 163 µs on N. America⁴).
• ✅ Predictable latency; the search space is tiny compared to plain Dijkstra.
• ❌ Preprocessing is in the minutes-to-hours range and must rerun whenever the topology changes (new road segments, permanent closures).
• ❌ Memory overhead from shortcuts is non-trivial (tens of bytes per node).

Used in production by: OSRM, GraphHopper, Valhalla-style stacks. Google Maps’ exact routing engine is not publicly documented; CH is the default reference architecture in the academic literature¹.

Path B: Customizable — CRP / Customizable Contraction Hierarchies

Best when the metric changes often (driving vs. walking, time-of-day cost overlays, user preferences), but the topology is still stable.

• Precompute a multi-level partition of the graph once (slow).
• “Customize” the metric in seconds to minutes by recomputing intra-cell shortcuts.
• Query time is competitive with CH (low ms).

Trade-offs vs. CH: cheaper customization for a given network, more bookkeeping, slightly slower queries. Bing Maps documented CRP as the engine behind its routing service⁸; CCH (Customizable Contraction Hierarchies) is the open-source variant.

Path C: Dynamic — ALT (A* + Landmarks + Triangle inequality)

Best when the topology itself changes frequently (research, construction-heavy regions) and you cannot afford to rebuild the hierarchy.

• Precompute shortest-path distances from a small set of landmarks.
• Use the triangle inequality to derive a tight A* heuristic.

Trade-offs: handles dynamic networks natively, but queries are typically 10-100× slower than CH and quality depends heavily on landmark selection¹.

Path comparison

This article’s focus

The rest of this design assumes Path A (CH) as the routing core because it stresses the most interesting trade-off — sub-millisecond queries on a 10⁸-edge graph by accepting a heavy offline build — and because Path B/C reuse most of the same surrounding services (tiles, traffic ingestion, geocoding, ETA prediction).

High-Level Design

Tile Service

Serves pre-rendered or dynamically generated map tiles using a quadtree addressing scheme.

Tile addressing (Web Mercator, Slippy Map / XYZ scheme):

1/{z}/{x}/{y}.{format}

• z: zoom level (0–22).
• x: column index, 0 (west) to 2^z − 1 (east).
• y: row index, 0 (north) to 2^z − 1 (south) under the OSM/Google “Slippy Map” convention. The older TMS scheme inverts the Y axis — y_tms = 2^z − 1 − y_xyz — and is still common in some open-source toolchains. Address every URL template with the convention written next to it; silent flips are a routine source of “everything is upside-down” bugs.

Zoom Level Properties:

Each zoom level is a quadtree subdivision of the previous one — every tile splits into four children, which is what makes the addressing scheme cache- and CDN-friendly and lets clients prefetch a parent or sibling tile while a finer one is fetching.

Vector tiles vs. raster tiles:

Vector tiles, as defined by the Mapbox Vector Tile specification, encode geometry and attributes as Protocol Buffers. Each tile uses an integer coordinate system with a default extent of 4,096 units mapping the tile’s square dimensions; geometry commands (MoveTo, LineTo, ClosePath) are encoded as varint-packed integers with zig-zag encoding for deltas. Keys and values are deduplicated per layer for compression. Tiles are typically gzip-encoded on the wire.

The practical consequence: a vector tile is small (commonly tens of KB), can be re-themed entirely on the client (dark mode, traffic overlays, language switches), and can be drawn at any subpixel zoom without resampling artifacts. The cost is a GPU-shaped client (WebGL or native) and a more complex parsing pipeline.

Routing Service

Computes optimal paths using Contraction Hierarchies with traffic overlays.

How Contraction Hierarchies Work:

1. Node Ordering: Rank nodes by importance (highways > arterials > local roads). Importance is computed using edge difference, contraction depth, and original edges.

2. Contraction: Iteratively remove least-important nodes. For each removed node, add “shortcut” edges between its neighbors if the shortest path went through it.

3. Query: Run bidirectional Dijkstra, but only traverse edges going “upward” in the hierarchy. The searches meet at the highest-importance node on the optimal path.

Performance benchmarks (North America, 87M vertices, 113M edges):

OSRM numbers from the Parallel Contraction Hierarchies (ICS 2025) benchmark⁴:

For reference, plain Dijkstra on a continental graph is in the seconds per query¹; even a conservative 4 s baseline against 163 µs is roughly a 25,000× speedup, which is why every production routing engine preprocesses.

Traffic-Aware Routing:

Real-time traffic is applied as edge weight multipliers without recomputing the hierarchy:

1. Collect probe data (GPS traces from devices)
2. Map-match probes to road segments
3. Compute segment speeds from probe timestamps
4. Store speed multipliers: actual_speed / free_flow_speed
5. At query time: edge_weight = base_weight × traffic_multiplier

This hybrid approach preserves sub-millisecond queries while incorporating live traffic.

Traffic Service

Collects, processes, and serves real-time traffic data.

Data Sources:

Floating Car Data (FCD) Pipeline:

1Probe → Map Matching → Segment Assignment → Speed Aggregation → Traffic State

1. Probe ingestion: Timestamped (lat, lon, speed) tuples
2. Map matching: Hidden Markov Model assigns probes to road segments
3. Aggregation: Window-based speed averaging (2-5 minute windows)
4. Traffic state: Free flow / Light / Moderate / Heavy / Standstill

ETA prediction with Graph Neural Networks:

Google Maps’ work with DeepMind, peer-reviewed at CIKM 2021⁶ and described in the DeepMind blog post:

• Supersegments are sequences of adjacent road segments that experience correlated traffic — built dynamically by a route analyzer rather than statically per-region.
• Graph structure: nodes are road segments, edges are connectivity within a supersegment; a separate GNN runs per supersegment.
• Features: real-time speeds, historical speeds bucketed by day-of-week and time-of-day, segment metadata.
• Output: predicted travel time per supersegment; the route’s ETA is the sum.

Reported results:

• The Google Maps baseline (before the GNN rollout) was already accurate within ±10 % on >97 % of trips⁵ — the GNN’s job is to attack the long tail of bad ETAs, not the median.
• The GNN model produced up to ~50 % reduction in “negative ETA outcomes” (cases where the actual time deviated from the prediction by more than the per-region threshold) in cities including Berlin, Jakarta, São Paulo, Sydney, Tokyo, and Washington D.C.⁵
• The CIKM paper reports a >40 % reduction in negative ETA outcomes specifically in Sydney⁶; the “up to 50 %” figure is from the broader DeepMind blog announcement and varies by city.

Geocoding Service

Converts between addresses and coordinates.

Forward Geocoding Pipeline:

1Input: "1600 Amphitheatre Parkway, Mountain View, CA"2  ↓3Address Parsing (libpostal): {street: "1600 Amphitheatre Parkway", city: "Mountain View", state: "CA"}4  ↓5Normalization: Expand abbreviations, standardize format6  ↓7Candidate Generation: Query spatial index for matching addresses8  ↓9Scoring: Rank by text similarity, location confidence10  ↓11Output: {lat: 37.4220, lng: -122.0841, confidence: 0.98}

Reverse Geocoding:

Given (lat, lon), find the nearest address:

1. Query R-tree/S2 index for nearby address points
2. Interpolate street address from road segment data
3. Return formatted address with administrative hierarchy

Spatial indexing — pick by query shape, not by hype:

Trade-offs that actually drive the choice:

• Cell-area uniformity. Hexagons (H3) have a single neighbor distance and the lowest area variance; S2 cells are roughly equal-area thanks to a quadratic projection adjustment¹⁰; geohash rectangles get noticeably skinnier toward the poles.
• Hierarchy semantics. S2 and geohash are strict hierarchies — every child cell is fully contained in its parent, which makes cell-prefix containment queries trivial. H3’s parent/child relationship is approximate — a child hexagon can poke outside its parent — so containment queries need a small fudge buffer¹¹.
• Locality. S2’s Hilbert curve keeps spatially close cells close in the 1-D ID, which makes range scans on a normal B-tree behave like spatial scans¹⁰. H3 has no global space-filling curve.
• Tooling. Geohash is supported almost everywhere out of the box. S2 powers Google Maps, Foursquare’s place index, MongoDB’s 2dsphere, and CockroachDB’s spatial queries¹². H3 is the Uber-internal default and the de-facto standard for ride-hailing-style aggregations.

Google Maps standardized on S2 internally — it gives them strict hierarchy + Hilbert-curve locality, which is what makes prefix-bound BETWEEN scans behave like spatial range scans on standard storage engines.

Search Service (POI and Autocomplete)

Place Autocomplete Data Structures:

Where m = query length.

Ranking Signals:

• Text relevance (edit distance, prefix match)
• Popularity (visit frequency)
• Recency (user’s recent searches)
• Proximity (distance from user’s location)
• Category match (restaurants, gas stations)

API Design

Tile API

Endpoint: GET /tiles/{z}/{x}/{y}.{format}

Path Parameters:

• z: Zoom level (0-22)
• x: Tile column
• y: Tile row
• format: png, mvt (vector), pbf

Response Headers:

1Content-Type: image/png | application/vnd.mapbox-vector-tile2Cache-Control: public, max-age=864003ETag: "abc123"

Response: Binary tile data

Caching Strategy:

• CDN cache: 24 hours for zoom < 15, 1 hour for zoom ≥ 15
• Client cache: ETag-based conditional requests
• Cache hit rate target: > 95%

Routing API

Endpoint: POST /routes

Request:

1{2  "origin": { "lat": 37.422, "lng": -122.0841 },3  "destination": { "lat": 37.7749, "lng": -122.4194 },4  "waypoints": [{ "lat": 37.5585, "lng": -122.2711 }],5  "mode": "driving",6  "departure_time": "2024-01-15T08:00:00Z",7  "alternatives": true,8  "traffic_model": "best_guess"9}

Response:

1{2  "routes": [3    {4      "legs": [5        {6          "distance": {"value": 45000, "text": "45 km"},7          "duration": {"value": 2700, "text": "45 min"},8          "duration_in_traffic": {"value": 3300, "text": "55 min"},9          "steps": [10            {11              "instruction": "Head north on Amphitheatre Pkwy",12              "distance": {"value": 500, "text": "500 m"},13              "duration": {"value": 60, "text": "1 min"},14              "polyline": "encoded_polyline_string",15              "maneuver": "turn-right"16            }17          ]18        }19      ],20      "overview_polyline": "encoded_polyline_string",21      "bounds": {"northeast": {...}, "southwest": {...}},22      "warnings": ["Route includes toll roads"]23    }24  ]25}

Error Responses:

• 400 Bad Request: Invalid coordinates, missing required fields
• 404 Not Found: No route found (disconnected points)
• 429 Too Many Requests: Rate limit exceeded

Rate Limits: 1000 requests/minute per API key

Geocoding API

Forward Geocoding:

GET /geocode?address={address}&bounds={sw_lat,sw_lng,ne_lat,ne_lng}

Response:

1{2  "results": [3    {4      "formatted_address": "1600 Amphitheatre Parkway, Mountain View, CA 94043",5      "geometry": {6        "location": {"lat": 37.4220, "lng": -122.0841},7        "location_type": "ROOFTOP",8        "viewport": {...}9      },10      "address_components": [11        {"long_name": "1600", "types": ["street_number"]},12        {"long_name": "Amphitheatre Parkway", "types": ["route"]}13      ],14      "place_id": "ChIJ..."15    }16  ]17}

Reverse Geocoding:

GET /geocode?latlng={lat},{lng}

Place Autocomplete API

Endpoint: GET /places/autocomplete?input={query}&location={lat},{lng}&radius={meters}

Response:

1{2  "predictions": [3    {4      "description": "Googleplex, Mountain View, CA",5      "place_id": "ChIJ...",6      "structured_formatting": {7        "main_text": "Googleplex",8        "secondary_text": "Mountain View, CA"9      },10      "distance_meters": 120011    }12  ]13}

Debouncing: Client should debounce requests (300ms) to reduce API calls during typing.

Data Modeling

Road Graph Schema

Primary Store: Custom binary format for in-memory graph processing

1Node:2  - id: uint643  - lat: float324  - lon: float325  - ch_level: uint16  // Contraction hierarchy level67Edge:8  - source: uint649  - target: uint6410  - distance: uint32  // meters11  - duration: uint32  // seconds (free flow)12  - road_class: uint8 // motorway, primary, secondary, etc.13  - is_shortcut: bool14  - shortcut_middle: uint64  // For path unpacking

Storage:

• Memory-mapped file for O(1) access
• Compressed with LZ4 for disk storage
• Sharded by geographic region (continent-level)

Tile Metadata Schema

Primary Store: Object storage (S3-compatible) with key-value index

1Key: {layer}/{z}/{x}/{y}2Value: {3  tile_data: bytes,4  etag: string,5  generated_at: timestamp,6  source_version: string7}

Tile Generation Pipeline:

1. Raw map data (OpenStreetMap format)
2. Feature extraction and simplification per zoom level
3. Vector tile encoding (Mapbox Vector Tile spec)
4. Compression (gzip)
5. Upload to object storage

Traffic Data Schema

Primary Store: Time-series database (InfluxDB, TimescaleDB, or custom)

1CREATE TABLE traffic_observations (2  segment_id BIGINT NOT NULL,3  timestamp TIMESTAMPTZ NOT NULL,4  speed_kmh SMALLINT,5  probe_count SMALLINT,6  confidence REAL7);89-- Hypertable for time-series performance10SELECT create_hypertable('traffic_observations', 'timestamp');1112-- Index for real-time lookups13CREATE INDEX idx_traffic_segment_time14ON traffic_observations(segment_id, timestamp DESC);

Retention:

• Raw observations: 7 days
• Hourly aggregates: 1 year
• Daily patterns: 5 years

POI Schema

Primary Store: PostgreSQL with PostGIS extension

1CREATE TABLE places (2  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),3  name TEXT NOT NULL,4  location GEOGRAPHY(POINT, 4326) NOT NULL,5  category VARCHAR(50),6  address_components JSONB,7  popularity_score REAL DEFAULT 0,8  created_at TIMESTAMPTZ DEFAULT NOW(),9  updated_at TIMESTAMPTZ DEFAULT NOW()10);1112CREATE INDEX idx_places_location ON places USING GIST(location);13CREATE INDEX idx_places_category ON places(category);14CREATE INDEX idx_places_name_trgm ON places USING GIN(name gin_trgm_ops);

Database Selection Matrix

Low-Level Design

Contraction Hierarchies Implementation

Node Ordering Heuristic:

1priority(v) = edge_difference(v)2            + contract_depth(v)3            + original_edges(v)

Where:

• edge_difference: Number of shortcuts that would be added minus edges removed
• contract_depth: Maximum hierarchy level among neighbors
• original_edges: Number of non-shortcut edges (prefer removing shortcuts first)

Witness Search:

Before adding a shortcut u→w (through v), check if a shorter path u→w exists without v:

1shortcut_needed = (d(u,v) + d(v,w)) < witness_search(u, w, excluding v)

Witness search is a bounded Dijkstra; the bound is the proposed shortcut length.

Query Algorithm:

1def ch_query(source, target):2    # Bidirectional Dijkstra, only "upward" edges3    forward = dijkstra_upward(source)4    backward = dijkstra_upward(target)56    # Find best meeting point7    best_dist = infinity8    meeting_node = None9    for node in forward.visited ∩ backward.visited:10        dist = forward.dist[node] + backward.dist[node]11        if dist < best_dist:12            best_dist = dist13            meeting_node = node1415    # Unpack shortcuts recursively16    return unpack_path(source, meeting_node, target)

Why “upward” only works:

The hierarchy ensures that for any shortest path, there exists a path in the CH graph that only goes up (in CH level) from source, meets at some top node, then only goes up (reversed = down in original) to target. This dramatically prunes the search space.

Map matching algorithm

Map matching assigns noisy, potentially sparse GPS probes to specific road segments. The reference algorithm is the Hidden Markov Model (HMM) approach by Newson and Krumm¹³:

• Hidden states: candidate road segments near each GPS observation.
• Observations: the GPS lat/lon (and sometimes heading and speed) at each timestep.
• Emission probability: a Gaussian centered on the candidate segment’s projection of the GPS point — P(z | r) ∝ exp(−d² / (2σ_z²)) where d is the perpendicular distance and σ_z is the GPS error (Newson uses 4.07 m on the dataset they collected).
• Transition probability: an exponential of the difference between great-circle distance and shortest-path routing distance between consecutive candidates — penalises sequences that would require teleportation.

Algorithm (Viterbi):

1. For each GPS point, take all road segments within ~200 m (Newson’s default — denser radii like 50 m are sometimes used in dense urban networks at the cost of recall in tunnels and GPS-degraded areas).
2. Compute emission probability for each candidate.
3. Compute transition probabilities between consecutive candidates using shortest-path routing distance.
4. Find the maximum-likelihood path with Viterbi; backtrack to recover the matched segment sequence.

Output: a stream of (segment_id, t_enter, t_exit) tuples — the input the traffic aggregator needs to compute per-segment speeds.

Tile Rendering Pipeline

Vector Tile Generation:

1. Feature extraction: Query PostGIS for features in tile bounding box
2. Simplification: Douglas-Peucker algorithm, tolerance based on zoom level
3. Clipping: Clip features to tile boundary with buffer
4. Encoding: Convert to Mapbox Vector Tile (MVT) format
5. Compression: gzip for storage/transfer

Simplification Tolerance:

MVT Structure:

1message Tile {2  repeated Layer layers = 3;3}45message Layer {6  required string name = 1;7  repeated Feature features = 2;8  repeated string keys = 3;    // Shared key list9  repeated Value values = 4;   // Shared value list10  optional uint32 extent = 5;  // Default 409611}1213message Feature {14  optional uint64 id = 1;15  repeated uint32 tags = 2;    // Indices into keys/values16  optional GeomType type = 3;17  repeated uint32 geometry = 4; // Command-encoded18}

Keys and values are deduplicated across features for compression.

Frontend Considerations

Tile Loading Strategy

Viewport-Based Loading:

1interface Viewport {2  center: LatLng3  zoom: number4  bounds: LatLngBounds5}67function getTilesForViewport(viewport: Viewport): TileCoord[] {8  const { bounds, zoom } = viewport9  const tiles: TileCoord[] = []1011  const minTile = latLngToTile(bounds.southwest, zoom)12  const maxTile = latLngToTile(bounds.northeast, zoom)1314  for (let x = minTile.x; x <= maxTile.x; x++) {15    for (let y = minTile.y; y <= maxTile.y; y++) {16      tiles.push({ z: zoom, x, y })17    }18  }1920  return tiles21}

Prefetching:

• Load tiles 1 level above and below current zoom (for smooth zoom transitions)
• Load adjacent tiles outside viewport (buffer for panning)
• Typical: 20-30 tiles per view state

Tile Cache (Client-Side):

1class TileCache {2  private cache: Map<string, ImageBitmap>3  private maxSize: number = 500 // tiles4  private lru: string[] = []56  get(key: string): ImageBitmap | undefined {7    const tile = this.cache.get(key)8    if (tile) {9      // Move to end of LRU10      this.lru = this.lru.filter((k) => k !== key)11      this.lru.push(key)12    }13    return tile14  }1516  set(key: string, tile: ImageBitmap): void {17    if (this.cache.size >= this.maxSize) {18      const evict = this.lru.shift()!19      this.cache.delete(evict)20    }21    this.cache.set(key, tile)22    this.lru.push(key)23  }24}

Vector Tile Rendering

WebGL Rendering Pipeline:

1. Parse MVT protobuf → geometry arrays
2. Upload vertex buffers to GPU
3. Apply style rules (zoom-dependent line widths, colors)
4. Render with appropriate shaders

Libraries:

• Mapbox GL JS / MapLibre GL JS (WebGL-based)
• Leaflet with vector tile plugins (Canvas/SVG fallback)
• deck.gl for data visualization layers

Performance Considerations:

• Batch draw calls per layer
• Use instanced rendering for repeated symbols (icons)
• Level-of-detail: reduce vertex count at lower zooms
• Web Workers for MVT parsing (off main thread)

Route Visualization

Polyline Rendering:

1interface RouteLayer {2  // Decoded polyline as [lat, lng] pairs3  coordinates: [number, number][]45  // Style6  strokeColor: string7  strokeWidth: number89  // Animation state (for traffic coloring)10  trafficSegments: {11    startIndex: number12    endIndex: number13    severity: "free_flow" | "light" | "moderate" | "heavy"14  }[]15}

Traffic Coloring:

Animation (Navigation Mode):

• Update position marker at 60fps
• Smooth interpolation between GPS updates
• Re-route detection: compare current position to expected route

Offline Maps Implementation

Download Strategy:

1interface OfflineRegion {2  bounds: LatLngBounds3  minZoom: number4  maxZoom: number5  includeRouting: boolean6}78function estimateDownloadSize(region: OfflineRegion): number {9  let totalTiles = 010  for (let z = region.minZoom; z <= region.maxZoom; z++) {11    const tilesAtZoom = countTilesInBounds(region.bounds, z)12    totalTiles += tilesAtZoom13  }14  // Average 30KB per compressed vector tile15  return totalTiles * 30 * 102416}

Storage Format:

SQLite database with:

• Tile blobs keyed by (z, x, y)
• Metadata (region bounds, version, expiry)
• Road graph subset for offline routing

Delta updates:

1. Server generates a per-region diff between map versions, expressed as a list of changed (z, x, y) tile keys.
2. Client downloads only changed tiles, applies them to the local SQLite store, and bumps the version pointer.
3. Checksums per tile guard against partial downloads on flaky networks.

The savings depend entirely on edit density: a routine map data refresh in a stable region touches only a small fraction of tiles, while a major release that changes styling or schema is closer to a full re-download.

Infrastructure Design

CDN Architecture

Tile CDN requirements:

• Edge locations in 100+ cities for low first-byte time globally.
• High cache hit rate is the design target — public CDN guidance puts well-tuned static-content workloads in the 90–99 % range¹⁴; tiles are an unusually friendly workload (immutable per version, addressable by a deterministic key) so the upper end is realistic.
• Origin shield to absorb cache misses and protect tile servers.
• Custom cache keys: /{layer}/{z}/{x}/{y} plus a version segment so you can invalidate a generation by changing the prefix.

Cache Hierarchy:

1User → Edge PoP → Regional Cache → Origin Shield → Tile Server

Cache TTLs:

Routing Service Deployment

Memory Requirements:

• North America CH graph: ~20 GB RAM
• Europe CH graph: ~15 GB RAM
• Global: ~100 GB RAM (sharded)

Deployment Strategy:

1. Regional sharding: Each region runs its own CH graph
2. Cross-region routing: Stitch at border nodes
3. Replication: 3 instances per region for availability
4. Updates: Blue-green deployment for new CH builds

Cloud Architecture (AWS)

Self-Hosted Alternatives

Monitoring and Observability

Key Metrics

Tile Service:

• Cache hit rate (target: > 95%)
• Tile generation latency (p99 < 200ms)
• Error rate by zoom level

Routing Service:

• Query latency (p50, p99)
• Routes not found rate
• Traffic overlay staleness

Traffic Service:

• Probe ingestion lag (target: < 30s)
• Segment coverage (% of roads with data)
• ETA accuracy (actual vs. predicted)

Alerting Thresholds

Conclusion

The hard parts of a mapping platform are the boundaries between subsystems, not any one subsystem in isolation:

1. Rendering at scale: a quadtree of vector tiles is overwhelmingly cacheable and client-themable. The system’s job at the tile boundary is mostly version management and CDN behavior.

2. Fast routing: a CH preprocessing step (minutes for a continent⁴) buys hundreds-of-microseconds queries; live traffic is layered on as a per-edge multiplier so the static structure stays valid. CRP and CCH are the better fit when the metric itself changes; ALT when the topology is dynamic.

3. Accurate ETAs: a Graph Neural Network on supersegments attacks the long tail of bad ETAs that aggregating per-segment averages misses, with 40–50 % reductions in negative outcomes in major cities⁶⁵.

Key trade-offs accepted:

• Preprocessing time for query latency (CH model).
• Storage overhead (tens of bytes per node) for sub-millisecond queries.
• Eventual consistency in traffic data (1–5 minute aggregation windows are typical).

Limitations:

• CH rebuilds block on topology changes (new roads, permanent closures); transient closures have to be encoded as edge-weight overrides.
• Probe-based traffic falls off in rural and tunnel coverage; historical models fill the gap with reduced confidence.
• Offline routing requires shipping a regional CH subgraph and accepting that it cannot incorporate real-time traffic.

Where it goes next:

• Personalized routing (preferences, vehicle profiles, accessibility).
• Real-time construction and closure detection from probe anomalies.
• Multi-modal stitching (walk → transit → walk → ride-hail) over a unified routing surface.

Appendix

Prerequisites

• Graph algorithms (Dijkstra, A*)
• Spatial indexing concepts (R-tree, quadtree)
• Distributed systems fundamentals
• CDN caching strategies

Terminology

Summary

• Tiles: quadtree pyramid of MVT vector tiles, CDN-cached behind a versioned key, ~20–30 tiles loaded per viewport.
• Routing: Contraction Hierarchies with ~163 µs median queries on continental graphs (OSRM⁴); traffic applied as edge-weight multipliers, never as a rebuild.
• Traffic: FCD probes mapped to segments via HMM matching¹³, aggregated in 1–5 minute windows, fused with historical patterns.
• ETA: per-segment baseline plus a GNN over supersegments to attack the long tail of bad ETAs⁶.
• Geocoding: address parsing (e.g. libpostal) + spatial index (R-tree / S2), autocomplete on a pruning radix trie.
• Offline: SQLite-packed tiles plus a regional CH subgraph, refreshed via per-tile diffs.
• Scale (estimated): ~1.7 M RPS tiles, ~70 K RPS routing at peak.

References

• Route Planning in Transportation Networks — Bast, Delling, Goldberg, Müller-Hannemann, Pajor, Sanders, Wagner, Werneck (2015). The canonical survey of speedup techniques.
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks — Geisberger, Sanders, Schultes, Delling (2008). The original CH paper.
• Parallel Contraction Hierarchies Can Be Efficient and Scalable — Wang et al., ICS 2025. Source for the OSRM 307 s / 163 µs benchmark on 87M-vertex North America.
• Customizable Route Planning in Road Networks — Delling, Goldberg, Pajor, Werneck (2017). The CRP engine behind Bing Maps.
• Hidden Markov Map Matching Through Noise and Sparseness — Newson, Krumm (ACM SIGSPATIAL 2009).
• ETA Prediction with Graph Neural Networks in Google Maps — Derrow-Pinion et al. (CIKM 2021).
• Traffic Prediction with Advanced Graph Neural Networks — Google DeepMind blog (2020).
• Mapbox Vector Tile Specification 2.1.
• OpenStreetMap zoom levels — meters per pixel formulas.
• Web Mercator projection (EPSG:3857).
• Google S2 Geometry Library and Announcing the S2 Library.
• OSRM (Open Source Routing Machine) — production CH implementation.
• GraphHopper — alternate open-source CH stack.
• libpostal — address parsing library.