Google Maps

A scalable Google Maps system integrates location updates, navigation ETA, and map rendering, alongside core features like geocoding, geohashing, and real-time updates. This note focuses on these areas with an emphasis on efficient data handling, real-time responsiveness, and storage estimation for hierarchical tiles.

Pillars: geocoding and geohashing

Geocoding converts addresses to geographic coordinates, while reverse geocoding transforms coordinates into human-readable addresses. Typically, a fast-access database (e.g., Redis) stores key-value mappings for rapid lookups. Geohashing represents geographic areas as compact strings (e.g 9d9hu) that represents geographic regions, allowing for efficient spatial indexing and querying. Geohashing divides the world into a grid, facilitating quick location searches and proximity calculations.

Location Updates

Devices send periodic GPS updates (e.g., every 5 seconds) containing coordinates and timestamps. These updates are processed to compute movement, speed, and direction. Challenges and Approaches:

• Data ingestion: High-throughput pipelines like Kafka partition data by device ID for parallel processing.
• Accuracy: Kalman filters smooth noisy GPS data.
• Storage:
  • Real-time state is stored in-memory (e.g., Redis) for fast access.
  • Historical data is written to long-term storage (e.g., S3 or BigQuery).
• Geohashing:
  • Location data is encoded into compact strings (e.g., 9q9hu) that represent geographic regions.
  • Enables efficient spatial indexing for proximity searches and updates.

---

Rendering subsystem

Maps are divided into hierarchical tiles using a quadtree structure. Each tile corresponds to a specific region at a given zoom level.

Tile-Based Rendering:

• Base tiles:
  • Tiles are pre-rendered (raster or vector format) at multiple zoom levels.
  • Vector tiles allow efficient client-side rendering and customization.
• Real-time layers:
  • Dynamic overlays (e.g., traffic, POIs) are rendered on top of base tiles.

Hierarchical Tile Estimation:

• The world is divided into a Mercator projection, covering ~85°N to ~85°S.
• At zoom level n, the world is split into 4^n tiles. Summing across all zoom levels (up to 23) results in ~5.6 trillion tiles.
• Assuming 50 KB per tile, storing all tiles requires ~280 PB. Optimizations include:
  • Storing only landmass tiles (~30% of the Earth).
  • Using vector tiles (~5 KB/tile).

Serving tiles

CDN provides the basic infrastructure for serving tiles for rendering

Vector or raster tiles trade-offs

Raster Tiles

Pre-rendered images of the map at specific zoom levels, stored in formats like PNG or JPEG.

• Storage Requirements:
  • Raster tiles are large since each zoom level must store a complete set of tiles. For a high zoom level, the storage scales exponentially (5^n for zoom level n).
  • Example: A raster tile is ~50 KB, leading to significant storage needs (~280 PB for full world coverage).
• Advantages:
  • Quick to render on the client as no additional processing is required.
  • Ideal for static or pre-rendered maps.
• Disadvantages:
  • Storage-intensive and less flexible (e.g., cannot dynamically change styles).

Raster Tile size

a 256x256 raster tile, using 24-bit color depth (8 bits per RGB channel) would take 256*256 (65k) * 3 bytes = 195k size, but PNG or JPG compression would bring it down to 50kb

Vector tiles

Contain raw geometric data (e.g., points, lines, polygons) encoded in formats like GeoJSON or protobuf (e.g., Mapbox Vector Tiles).

• Storage Requirements:
  • Vector tiles are smaller (~5–10 KB per tile) because they encode map features rather than rendering them as images.
  • A single set of vector tiles can represent multiple styles, reducing redundancy.
• Advantages:
  • Flexible: Styles and overlays can be applied dynamically on the client.
  • More storage-efficient and better suited for high zoom levels.
• Disadvantages:
  • Requires client-side rendering, which increases complexity and GPU usage.

Navigation Subsystem

ETAs are computed using algorithms like A* or Dijkstra over a road graph using hierarchical routing tiles:

• Higher levels represent coarser data (e.g., major highways), while lower levels detail finer-grained roads (e.g., city streets).
• Hierarchy Example:
  • Level 0: Inter-city highways.
  • Level 1: Major roads within a city.
  • Level 2: Local streets.

Using routing tiles

The first phase is global planning, starting with higher-level tiles to calculate a rough route (e.g., from city A to city B via highways). The next step is local Refinement, which drills down into lower-level tiles near the source and destination for fine-grained navigation (e.g., turn-by-turn directions). The algorithm can be optimized by reducing graph size for initial computations by ignoring unnecessary details (e.g., local roads far from the planned route).

Tip

Routing tiles are mostly immutable(unless there is a closed road), so they can be stored on an object storage rather than a database since they are never accessed by the frontend. They also have different granularity from rendering tiles

Traffic prediction

Traffic prediction combines real-time updates with historical patterns using machine learning. Core Components:

• Dynamic routing: Routes update as the user moves or traffic changes.
• Traffic prediction: Models predict delays based on live and historical data.
• Routing tiles:
  • The road graph is partitioned into routing tiles, each representing a manageable subset of roads.
  • These tiles enable parallel computation of routes.
• Scalability: Sharded road graphs support distributed route computation by region.

Estimating Traffic in a Routing Tile

Traffic estimation combines:

1. Historical Data:
   • Average speed and congestion patterns for different times of day (e.g., rush hour).
   • Collected from GPS pings, user contributions, and historical logs.
2. Real-Time Updates:
   • Aggregating live GPS data from users traveling within the tile.
   • Detecting anomalies like slowdowns or closures based on deviations from historical norms.
3. Edge Weight Adjustment:
   • Each road segment (edge) within the tile has a weight representing travel time or distance.
   • Real-time traffic adjusts these weights dynamically (e.g., increasing weight for congested roads).