HLD · 21 min read

Design Google Maps

System design for a mapping and navigation platform like Google Maps

On this page
  1. 1. Requirements
  2. Functional Requirements
  3. Out of Scope
  4. Non-Functional Requirements
  5. 2. Capacity Estimation
  6. 3. API Gateway
  7. 4. Map Tile System
  8. Tile Coordinate System
  9. Map Rendering Pipeline (Offline Batch)
  10. Tile Serving via CDN
  11. Tile Storage in S3
  12. Bottlenecks in the Tile System
  13. 5. Navigation Service and Routing
  14. Graph Data Model
  15. Contraction Hierarchies (CH) Preprocessing
  16. Full Routing Flow: Bandra to Connaught Place
  17. Bottlenecks in the Navigation Service
  18. 6. Location Service and Traffic Pipeline
  19. Location Ingestion
  20. Map Matching Service
  21. Traffic Aggregation with Apache Flink
  22. Location Data Storage
  23. Bottlenecks in the Traffic Pipeline
  24. 7. Geocoding Service
  25. Data Model
  26. 8. User Service
  27. 9. Analytics Service
  28. 10. Full Data Flow Summary
  29. 11. Resilience and Fault Tolerance
  30. 12. Technology Choices Summary

1. Requirements

Functional Requirements

  • User location fetching (GPS coordinates from device)
  • Map rendering (serving map tiles at all zoom levels)
  • Route calculation (find best path between two points)
  • ETA calculation (estimated time of arrival with real-time traffic)
  • Real-time traffic integration
  • Search for places on the map

Out of Scope

  • Street View
  • Indoor maps
  • Public transit routing
  • Offline maps
  • Google Maps Platform API for third-party developers
  • Satellite imagery pipeline

Non-Functional Requirements

  • High reliability: maps must never go down
  • High accuracy for routing and location
  • Low latency: map tiles under 50ms, route calculation under 2 seconds
  • Massive scalability: 500M DAU with 50M concurrent users
  • Real-time traffic updates reflecting current road conditions within minutes

2. Capacity Estimation

MetricValue
DAU500 million
Concurrent users10% of DAU = 50 million
Location pings per second50M users pinging every 10-20 seconds = ~2.5-5M QPS
Map tile requests per second50M users × 20 tiles per interaction / 15 seconds = ~67M tile requests/second
CDN cache hit rate for tiles90%+ (popular city tiles requested millions of times)
Origin tile requests after CDN~7M requests/second
Route calculations10% of concurrent users (5M) actively navigating; at one route or re-route per user every ~30 seconds, that's ~170,000 route calculations per second
Total map tile storage~50 PB (440 PB theoretical at the deepest zoom level, reduced by sparse tiles for oceans, deserts, and uninhabited land)
Traffic data ingestion~5M GPS pings/second, same as location pings

The scale here dwarfs every previous system in this series. 67 million tile requests per second makes the CDN the single most critical infrastructure component. Without a globally distributed CDN absorbing 90%+ of tile traffic, origin infrastructure would collapse instantly.

3. API Gateway

All client requests enter through the API Gateway which handles authentication, rate limiting, and routing. Google Maps has several distinct traffic patterns that the Gateway must handle differently:

TrafficCharacteristicsHandling
Tile requestsAnonymous (no user auth needed for public map tiles), extremely high volume, entirely read-onlyServed by the CDN layer in front of the Tile Service
Location pingsAuthenticated, high volume write operationsRate limited per device to prevent abuse
Route calculationsAuthenticated, computationally expensive, lower volumeRate limited per user to prevent routing service overload
Search requestsAuthenticated and relatively low volumeRouted to the search and geocoding services

4. Map Tile System

Tile Coordinate System

The world map is divided into a grid of square tiles at 22 zoom levels (0 to 21):

ZoomTiles
0Entire world in 1 tile (256×256 pixels)
1World in 4 tiles (2×2 grid)
NWorld in 4^N tiles
21Street-level detail, ~4.4 trillion tiles

Each tile is a 256×256 pixel PNG image, roughly 100 KB each. The theoretical storage at the deepest zoom level alone is 440 PB. After excluding ocean tiles, desert tiles, and uninhabited regions (oceans alone cover roughly 70% of the Earth's surface), and storing each identical "empty" tile only once, effective storage drops to approximately 50 PB.

Tiles are addressed by a deterministic three-component key: {zoom_level}/{x}/{y} where x and y are the tile grid coordinates at that zoom level. Any client can construct the URL for any tile without a database lookup:

text
https://tiles.maps.google.com/{zoom}/{x}/{y}.png

This deterministic URL structure is what makes CDN caching so effective. The cache key is the URL itself.

(Modern Google Maps actually sends vector tiles, the raw road and label geometry for each tile, and lets the client draw them. That makes tiles much smaller, lets the map rotate and tilt smoothly, and lets one tile serve any language or style. The tiling, addressing and caching ideas below are the same either way.)

Map Rendering Pipeline (Offline Batch)

Tiles are pre-rendered offline from vector map data, not rendered on demand. The rendering pipeline runs when map data changes.

Data Sources:

Map data comes from multiple sources that feed into the Map Data Store:

  • Licensed map data providers (HERE, TomTom)
  • OpenStreetMap contributions
  • Ground truth operators who manually verify road changes
  • User-submitted reports (road closures, new roads via the app)
  • Satellite imagery analysis (ML pipeline detects new roads from aerial photos)

The Map Data Store is a specialized geospatial database (PostGIS at its core) that is the source of truth for all road, building, and geographic data.

Rendering Flow:

When a new road is built in Mumbai:

  1. Ground truth operator verifies the road and updates the Map Data Store
  2. Map Data Store publishes map.data.updated event to Kafka with the bounding box of the changed area
  3. Map Rendering Pipeline consumes the event:
    • Identifies which tiles at which zoom levels intersect the changed bounding box
    • A single road change can affect thousands of tiles across zoom levels 10 to 21
    • Re-renders only affected tiles, not the entire world
    • Each tile rendered as a 256×256 PNG from vector map data (roads, buildings, labels, colors)
  4. Rendered tiles stored in S3 under deterministic path: tiles/{zoom}/{x}/{y}.png
  5. CDN cache invalidated for affected tile URLs via cache purge API
  6. Users requesting those tiles get the updated version on next request

The rendering pipeline is horizontally scaled across thousands of workers since rendering is CPU-intensive but embarrassingly parallel. Each tile is rendered independently with no dependency on other tiles.

Tile Serving via CDN

When a user pans or zooms the map, the client calculates which tile coordinates are needed for the current viewport and requests them:

http
GET https://tiles.maps.google.com/15/24456/14689.png
  • Cache hit (90%+ of requests): CDN edge node serves the tile directly from edge cache. Latency under 10ms for users near an edge node.
  • Cache miss: CDN fetches from S3 origin, caches the tile at the edge, and serves it. CDN populates automatically for future requests. Latency 50-100ms.

Tiles at low zoom levels (0-10, world to country scale) are cached at every CDN edge node globally since they are requested by everyone. Tiles at high zoom levels (15-21, neighborhood to street scale) are cached at regional CDN nodes since they are only relevant to users in that geography.

Tile Storage in S3

S3 is the origin store for all 50 PB of tile data. S3's virtually unlimited storage and native CDN integration make it the right choice. Each rendered tile is immutable. When a tile is re-rendered due to a map data change, the new version overwrites the old S3 object at the same key, and the CDN cache is invalidated.

Purging millions of URLs from a CDN after a big data update is slow, so many tile systems put a data version in the URL instead (/v2041/15/24456/14689.png). A new map release simply changes the version clients ask for, old tiles age out of the cache on their own, and each URL's content truly never changes.

Bottlenecks in the Tile System

The Map Rendering Pipeline is the bottleneck when large-scale map data changes occur (a major highway opening affects thousands of tiles at multiple zoom levels). This is mitigated by prioritizing high-zoom tiles (street level, most frequently requested) over low-zoom tiles (country level, cached for months) in the rendering queue.

The CDN is not a bottleneck at normal traffic levels but can become one during major events (earthquake emergency routing, major sporting events) when a specific geographic area sees a sudden spike in map requests. This is handled by pre-warming CDN edge nodes for expected high-traffic events.

5. Navigation Service and Routing

Graph Data Model

The road network is modeled as a directed weighted graph:

  • Nodes: road intersections and endpoints (~500 million globally)
  • Edges: road segments connecting intersections (~1 billion globally)
  • Edge weights: travel time based on distance and speed limit (adjusted by real-time traffic)

Nodes Table (PostgreSQL + PostGIS)

text
Nodes
node_id           BIGINT, primary key
lat               FLOAT
long              FLOAT
location          GEOGRAPHY(POINT, 4326) [GIST spatial index]
importance_rank   INTEGER (assigned during CH preprocessing)
node_type         ENUM('intersection', 'highway_junction', 'traffic_signal', 'roundabout')

Edges Table (PostgreSQL)

text
Edges
edge_id           BIGINT, primary key
from_node_id      BIGINT, foreign key -> Nodes
to_node_id        BIGINT, foreign key -> Nodes
distance_m        INTEGER
speed_limit_kmh   INTEGER
road_type         ENUM('highway', 'arterial', 'local', 'shortcut')
is_one_way        BOOLEAN
is_shortcut       BOOLEAN (true for CH preprocessed shortcut edges)
shortcut_via      BIGINT (contracted node ID this shortcut bypasses)
free_flow_speed   FLOAT (historical average speed at this segment)

The road graph for each region is loaded into memory on Navigation Service instances as an adjacency list. All routing queries are served from in-memory data for sub-second performance.

Contraction Hierarchies (CH) Preprocessing

Running standard Dijkstra on a graph with 500 million nodes would take minutes per query, completely unacceptable. Contraction Hierarchies solves this with offline preprocessing.

Importance Ranking:

Every node is assigned an importance rank based on:

  • Road type (highway junctions rank higher than local street intersections)
  • Number of shortest paths passing through the node (betweenness centrality)
  • Road connectivity (nodes connecting major roads rank higher)

Node Contraction:

Nodes are contracted one at a time, from least important to most important. Contracting a node means setting it aside and adding shortcut edges between its neighbors to preserve shortest path distances:

text
Before contracting node B (low importance local intersection):
A --5km--> B --3km--> C

After contracting B:
A --8km--> C (shortcut edge added, B set aside)

A shortcut is only added when the path through B really is the shortest way from A to C. If some other route from A to C is already as short (a "witness" path), no shortcut is needed, which keeps the number of shortcuts down.

Every node is eventually contracted, so nothing is thrown away. The result is the original graph plus the shortcuts, with every node labelled by its rank. A query then only ever moves upward in rank, from less important nodes to more important ones. Because the shortcuts let it jump over all the minor roads in one step, a Mumbai to Delhi query only has to look at a few hundred to a few thousand nodes, instead of exploring millions of streets like plain Dijkstra would.

Shortcut edges are stored in the Edges table with is_shortcut = true and shortcut_via pointing to the contracted node. Path reconstruction expands shortcuts back into original road segments for turn-by-turn directions.

Full Routing Flow: Bandra to Connaught Place

Step 1 - Geocoding

Navigation Service calls Geocoding Service to convert addresses to coordinates:

text
Bandra, Mumbai          -> (19.0544, 72.8375)
Connaught Place, Delhi  -> (28.6315, 77.2167)

Step 2 - Graph Partitions

The world graph is partitioned into regional pieces. Navigation Service identifies the partitions the route passes through (Maharashtra, Madhya Pradesh, Rajasthan, Delhi). These partitions are already held in memory on the instance (see bottlenecks below), so nothing has to be loaded from disk during the query.

Step 3 - Contraction Hierarchies Query

Navigation Service runs a bidirectional CH search:

text
Forward search from Bandra, moving up through increasingly important roads:
Local streets -> SV Road -> Bandra-Worli Sea Link -> Western Express Highway -> NH48

Backward search from Connaught Place, moving up the same way:
Local streets -> Ring Road -> NH48

Both searches meet on NH48 somewhere in Rajasthan. The meeting point is found and the path is reconstructed by expanding all shortcut edges back into original road segments.

Step 4 - Traffic Layer Applied

Traffic changes edge weights in real time. Navigation Service fetches current speeds for all road segments on the computed route from Redis:

redis
MGET traffic:segment_1 traffic:segment_2 ... traffic:segment_N

Travel times are recomputed using current speeds. If the optimal path under normal conditions is heavily congested, the top 3 alternative routes are evaluated and the truly fastest route by time is returned.

Re-checking a few alternatives catches most jams, but it can miss a clever detour that none of the precomputed alternatives includes. Plain CH bakes the edge weights into its shortcuts, so any weight change would mean redoing the preprocessing. That's why production routing engines use customizable variants (Customizable Contraction Hierarchies, or the closely related Customizable Route Planning). These split preprocessing into a slow, structure-only phase that runs when roads change, and a fast "customization" phase that re-applies new weights in seconds. Live traffic then becomes part of the search itself.

Step 5 - ETA Calculation

text
ETA = SUM(segment_distance_km / current_speed_kmh) for all segments
    + estimated delay at traffic signals (historical average per signal)
    + time-of-day adjustment (6pm Friday is slower than 2am Sunday on the same route)

Historical speed patterns are stored per road segment per hour per day of week. A route computed at 5:30pm on Friday uses Friday evening historical speeds for segments the user will reach in 2 hours, not current speeds.

Step 6 - Route Caching

Computed routes are cached in Redis:

text
Key:   route:{origin_geohash_p6}:{dest_geohash_p6}:{time_bucket_5min}
Value: { waypoints, segment_ids, base_eta, alternative_routes }
TTL:   5 minutes

Routes stale quickly due to traffic changes. A 5-minute TTL balances freshness with computation cost. Two users in the same ~1 km cell share the cached long-distance part of the route, while the first and last few hundred metres, from each user's exact location, are computed per request.

Step 7 - Active Navigation and Re-routing

During navigation, the client sends location pings every 5 seconds. Navigation Service monitors:

  • Deviation detection: user has left the planned route
  • Traffic change detection: a segment on the route has become significantly more congested

Either condition triggers re-routing from the user's current position using the same CH query.

Bottlenecks in the Navigation Service

The CH query itself is fast (milliseconds on the preprocessed graph). The bottleneck would be loading regional graph partitions into memory for very long routes that cross many partitions. This is avoided by keeping all partitions pre-loaded on Navigation Service instances with sufficient RAM. A Navigation Service instance for South Asia keeps the entire South Asia graph in memory and never loads it on demand.

6. Location Service and Traffic Pipeline

mermaid
flowchart TD
    D[Devices] -->|GPS pings| LS[Location Service]
    LS --> K1[["Kafka: location.pings"]]
    K1 --> MM["Map Matching (HMM)"]
    MM --> K2[["Kafka: location.matched"]]
    K2 --> F["Flink: 2-min windows"]
    F -->|every 30 s| R[("Redis traffic:{edge}")]
    F --> C[(Cassandra history)]
    F -->|big change| K3[["Kafka: traffic.updated"]]
    K3 --> NS[Navigation Service]
    NS -->|WebSocket| U[Navigating users]

Location Ingestion

Every user with navigation or location sharing active sends a GPS ping every 10-20 seconds:

json
{
  "user_id": "uuid",
  "lat": 19.0721,
  "long": 72.8846,
  "speed_kmh": 45,
  "heading": 270,
  "accuracy_m": 8,
  "timestamp": 1726123456
}

Location Service receives up to 5 million pings per second and immediately publishes to the Kafka location.pings topics, one per geographic region, keyed by user_id within each so that one user's pings always stay in order (the map matching step below depends on that). The Location Service itself is stateless and horizontally scalable. Kafka absorbs the write burst and decouples ingestion from processing.

Map Matching Service

Raw GPS coordinates cannot be attributed to road segments directly due to GPS error (5-10 meters) and ambiguity (multiple roads within error radius). The Map Matching Service snaps each GPS ping to the correct road segment using a Hidden Markov Model (HMM).

The Problem:

A user sends ping at (19.0721, 72.8846) with heading 270 degrees (westbound). Three road segments are within 15 meters:

  1. Western Express Highway flyover (westbound)
  2. SV Road below the flyover (westbound)
  3. A service road alongside SV Road (eastbound only)

Which segment gets the 45 kmh speed update?

HMM Map Matching:

The HMM scores each candidate segment using three signals simultaneously:

  • Signal 1 - Proximity: Closer segments score higher. GPS accuracy (8 meters reported) defines the probability distribution around the reported coordinate.
  • Signal 2 - Heading alignment: User heading (270 degrees, westbound) must match the segment direction. Eastbound-only segments are eliminated. Westbound segments score higher.
  • Signal 3 - Transition probability: Given the user was on segment X in the previous ping (15 seconds ago), what is the probability they are now on segment Y? The HMM uses road network topology to eliminate physically impossible transitions. A user cannot teleport from the flyover to a road 500 meters away in 15 seconds.

The HMM looks at the whole recent sequence of pings rather than each one alone (the Viterbi algorithm picks the most likely path through the candidates), which is what separates the flyover from the road directly beneath it. The highest-scoring segment wins. Low confidence matches (below a 0.7 threshold) are discarded rather than corrupting traffic data.

Map Matching Service Output:

json
{
  "edge_id": "highway_segment_447",
  "speed_kmh": 45,
  "timestamp": 1726123456,
  "confidence": 0.94
}

Output published to Kafka topic location.matched.

The Traffic Service consumes from location.matched using Apache Flink for real-time stream processing (the same tool Netflix uses for its real-time metrics). Rather than writing to Redis on every single ping (5 million Redis writes per second would be catastrophic), Flink aggregates using a sliding time window:

  • Window: 2-minute sliding window per road segment
  • Aggregation: median speed of all matched pings on this segment in the window
  • Update frequency: every 30 seconds

Median rather than average filters outliers. A stationary GPS ping (0 kmh from a user stopped at a red light) does not make a flowing highway appear congested when 50 other pings show 80 kmh. (It's the same sliding-window idea as Twitter's trending counts, applied to speeds.)

Congestion Level Computation:

python
def congestion_level(current_speed, free_flow_speed):
    ratio = current_speed / free_flow_speed
    if ratio > 0.8:  return 'free_flow'
    if ratio > 0.6:  return 'light'
    if ratio > 0.4:  return 'moderate'
    if ratio > 0.2:  return 'heavy'
    return 'standstill'

free_flow_speed is the historical average speed for that segment at the current time of day and day of week.

Redis Update:

text
Key:   traffic:{edge_id}
Value: { current_speed_kmh: 45, free_flow_speed: 80, congestion_level: 'light', updated_at: timestamp }
TTL:   5 minutes

If no pings arrive for a segment within 5 minutes, the Redis key expires and Navigation Service falls back to historical speed data for route calculations.

Traffic Broadcast to Active Navigators:

When Flink detects significant congestion change on a segment (congestion level changes by one level), it publishes traffic.updated to Kafka. Navigation Service consumes this and pushes updates via WebSocket to all users whose active routes include that segment.

Location Data Storage

Raw GPS pings are not stored permanently. Only aggregated traffic data (road segment speeds) is persisted in a time-series store. Besides saving storage, this is a privacy decision: the long-term data says how fast a road was, not where any particular person went.

TrafficHistory Table (Cassandra)

text
TrafficHistory
edge_id           BIGINT, partition key
time_bucket       TIMESTAMP (rounded to 5 minutes), clustering key
avg_speed_kmh     FLOAT
congestion_level  TEXT
sample_count      INTEGER

Partitioning by edge_id and clustering by time_bucket makes time-range queries for historical speed patterns extremely fast. This data feeds the historical speed model used for ETA calculations.

Bottlenecks in the Traffic Pipeline

The Map Matching Service is the primary bottleneck at 5 million pings per second. Looking up candidate road segments within 50 meters of every ping in PostGIS would be far too slow at this rate. This is mitigated by:

  • Splitting the Kafka location.pings topics by geographic region so Map Matching workers only handle pings from their assigned region (partitioning by location)
  • Caching the road network graph in memory on Map Matching workers (same adjacency list as Navigation Service), with a spatial index over it, so both the candidate lookup and the HMM transition probabilities avoid database calls
  • Discarding low-accuracy pings (accuracy_m > 50) before map matching to reduce volume

7. Geocoding Service

Geocoding converts human-readable addresses to coordinates (forward geocoding) and coordinates to addresses (reverse geocoding).

text
Forward geocoding:  "Connaught Place, Delhi" -> (28.6315, 77.2167)
Reverse geocoding:  (28.6315, 77.2167)      -> "Connaught Place, New Delhi, Delhi 110001"

Data Model

text
Places
place_id        UUID, primary key
name            VARCHAR
address         TEXT
city            VARCHAR
country         VARCHAR
lat             FLOAT
long            FLOAT
location        GEOGRAPHY(POINT) [GIST spatial index]
place_type      ENUM('city', 'neighborhood', 'street', 'poi', 'address')
search_vector   TSVECTOR (PostgreSQL full-text search index)

Forward geocoding uses a combination of full-text search on name and address fields plus geospatial ranking (results near the user's current location rank higher). Reverse geocoding uses ST_DWithin to find the nearest address to a coordinate (the same PostGIS query covered in the Proximity Service design).

Hot geocoding queries (major cities, famous landmarks) are cached in Redis with long TTLs since these change rarely.

8. User Service

Manages user profiles, saved places, search history, and navigation preferences.

text
Users
user_id           UUID, primary key
email             VARCHAR, unique
name              VARCHAR
home_location     GEOGRAPHY(POINT)
work_location     GEOGRAPHY(POINT)
preferred_routes  JSONB (avoid highways, avoid tolls, etc)
created_at        TIMESTAMP

SavedPlaces Table:

text
SavedPlaces
user_id     UUID, foreign key -> Users
place_id    UUID, foreign key -> Places
label       VARCHAR (Home, Work, Favorite, etc)
saved_at    TIMESTAMP

User preferences (avoid highways, avoid tolls, prefer scenic routes) are applied as edge weight modifiers during the routing query. A toll road edge gets a significantly higher weight for users who prefer to avoid tolls. (Like live traffic, these weight changes are something plain CH can't do per user, and the customizable variants handle with a small set of prepared weight profiles.)

9. Analytics Service

The Analytics Service processes aggregated location and routing data for business intelligence and map quality improvement:

  • Popular routes and destination patterns inform infrastructure planning
  • High congestion areas consistently identify road capacity issues
  • Route deviation patterns (users frequently going off-route at a specific point) signal missing roads or incorrectly mapped one-way streets in the Map Data Store
  • Search query patterns identify missing places in the geocoding database

Analytics data flows from Kafka through an Apache Spark batch pipeline to a data lake in S3. Standard analytics tools (BigQuery, Redshift) query the data lake for reporting.

10. Full Data Flow Summary

Map Tile Request Flow:

text
Client pans/zooms map -> calculates needed tile coordinates
Client -> CDN: GET tiles/{zoom}/{x}/{y}.png
    Cache hit (90%+): CDN edge serves tile under 10ms
    Cache miss: CDN fetches from S3 origin, caches at edge, serves tile

Map Data Update Flow:

text
Ground truth operator updates road data -> Map Data Store (PostGIS)
Map Data Store -> Kafka (map.data.updated with changed bounding box)
Map Rendering Pipeline:
    -> Identify affected tiles at all zoom levels
    -> Re-render affected tiles in parallel (thousands of workers)
    -> Store updated tiles in S3
    -> Purge CDN cache for affected tile URLs (or bump the tile version)
Users see updated map on next tile request

Location Ping Flow:

text
User device -> Location Service (up to 5M pings/second)
    -> Kafka (location.pings per region, keyed by user_id)
    -> Map Matching Service:
        -> In-memory road graph: find candidate road segments within 50m
        -> HMM: score candidates by proximity + heading + transition probability
        -> Output: matched edge_id + speed
    -> Kafka (location.matched)
    -> Apache Flink:
        -> 2-minute sliding window per edge_id
        -> Compute median speed, congestion level
        -> Every 30 seconds: Redis SET traffic:{edge_id} {speed, congestion}
        -> On congestion change: Kafka (traffic.updated)
    -> Navigation Service consumes traffic.updated
        -> WebSocket push to active navigators on affected routes

Route Calculation Flow:

text
Client -> API Gateway -> Navigation Service
    -> Geocoding Service: addresses to coordinates
    -> Use the in-memory regional graph partitions
    -> Bidirectional CH query on preprocessed graph
    -> Redis MGET traffic:{edge_id} for all route segments (apply traffic weights)
    -> Evaluate top 3 alternative routes
    -> ETA calculation (segment times + time-of-day historical patterns)
    -> Cache route: Redis route:{origin_hash}:{dest_hash}:{time_bucket} TTL 5min
    -> Return route + ETA + alternatives to client

Active Navigation Flow:

text
User navigating -> device sends ping every 5 seconds to Navigation Service
Navigation Service monitors:
    -> Deviation: user off route -> trigger re-route from current position
    -> Traffic change: traffic.updated event for segment on route
        -> Recompute ETA with new traffic data
        -> If faster alternative exists: push re-route suggestion via WebSocket

11. Resilience and Fault Tolerance

  • CDN absorbs 90%+ of tile traffic, making the Tile Service extremely resilient. S3 origin failure only affects the 10% cache miss traffic. The CDN keeps serving stale tiles for hours if S3 is temporarily unavailable, so users see slightly outdated map data rather than a broken experience.
  • Kafka durability for location pings means no GPS data is lost even if Map Matching workers crash. Workers replay from Kafka offsets on recovery, catching up on missed pings.
  • In-memory graph on Navigation Service instances means routing continues even if the PostgreSQL road graph database is temporarily unavailable. Route calculations degrade to using cached historical traffic rather than real-time traffic but never fail completely.
  • Redis TTL on traffic data (5 minutes) means stale traffic data auto-expires. If the traffic pipeline lags, Navigation Service automatically falls back to historical speed models rather than showing incorrect real-time data.
  • Flink stateful stream processing maintains sliding window state across restarts using Flink's checkpointing mechanism. A Flink worker restart does not lose the aggregation window state.
  • Geographic partitioning of both the road graph and the Kafka location pipeline provides fault isolation. A regional infrastructure issue in Southeast Asia does not affect routing in Europe.
  • Map Matching confidence threshold (0.7) prevents corrupt GPS data from polluting traffic data. Low confidence matches are discarded, accepting slightly reduced traffic data coverage in exchange for higher accuracy.
  • CH preprocessing is stable. The structural part of the preprocessed graph is stored durably and only needs recomputation when the road network itself changes (a new highway opens). Day-to-day traffic only changes edge weights, which the customizable variant re-applies in seconds without touching the structure.

12. Technology Choices Summary

ComponentTechnologyWhy
API GatewayKong / AWS API GatewayAuth, rate limiting, traffic type routing
Map Tile StorageAWS S350 PB tile storage, immutable objects, native CDN integration
Tile CDNCloudFront / AkamaiGlobal edge caching, 90%+ hit rate, deterministic URL cache keys
Map Rendering PipelineDistributed rendering workers via KafkaParallel tile rendering on map data change, priority queue for high-zoom tiles
Map Data StorePostgreSQL + PostGISSource of truth for all road and geographic data, GIST spatial index
Road Graph StoragePostgreSQL + PostGIS + in-memory adjacency list on Navigation Service instancesCH preprocessed graph loaded into RAM for fast traversal
Routing Algorithm(Customizable) Contraction Hierarchies with bidirectional searchPreprocessed offline, query in milliseconds, live weights re-applied in seconds
Location IngestionApache Kafka, per-region topics keyed by userUp to 5M pings/second, decoupled from processing
Map MatchingHidden Markov Model on in-memory road graphGPS coordinate to road segment attribution, confidence threshold filtering
Traffic AggregationApache Flink with 2-minute sliding windowsMedian speed per segment, 30-second update cadence
Traffic StoreRedis with 5-minute TTLCurrent speed and congestion per road segment, MGET for batch route traffic lookup
Traffic HistoryApache CassandraTime-series road segment speeds, partition by edge_id, cluster by time_bucket
Route CacheRedis with 5-minute TTLCached routes keyed by origin/destination geohash + time bucket
Geocoding DBPostgreSQL + PostGIS + full-text search indexForward and reverse geocoding, spatial ranking
Active NavigationWebSocketsReal-time route updates, traffic change pushes, re-routing triggers
Analytics PipelineApache Kafka + Apache Spark + S3 data lakeBatch processing of location and routing patterns
User Service DBPostgreSQLUser profiles, saved places, route preferences