Design a Maps & Routing Service

Geo, Maps & MarketplacesHarddesign-maps-routing

Design turn-by-turn routing over a continental road graph: precomputed shortcuts, live traffic that changes edge weights, and map tiles served from the edge.

Graph PreprocessingContraction HierarchiesTile ServingLive Traffic Overlay

Traffic & Capacity Estimates:

100M road segments · 50k route requests/second · route computed in <100ms

Functional Requirements

•Compute the fastest route between two points, accounting for current traffic and road restrictions.
•Serve vector map tiles at multiple zoom levels through the CDN.
•Re-route in real time when the traveller deviates or conditions change.
•Ingest live speed data from probe devices and reflect it in edge weights within minutes.

Non-Functional Requirements

•Route computation under 100ms at p99 for continental-scale queries.
•Tile serving must be almost entirely cache hits.
•A traffic-ingest outage must fall back to historical speed profiles, not fail routing.

Back-of-the-Envelope Math

Plain Dijkstra over 100M edges is seconds per query; contraction hierarchies bring the same answer to milliseconds after hours of preprocessing.
Tiles: 20 zoom levels of a world map is billions of tiles — generated on demand and cached, never all precomputed.

Key Architectural Trade-offs

Heavy graph preprocessing (contraction hierarchies, A* landmarks) buys millisecond queries and makes every traffic update an expensive partial rebuild.
Live traffic changes edge weights continuously, which breaks the assumptions preprocessing relies on — hence overlay corrections rather than full recomputation.
Vector tiles rendered client-side are small and flexible; raster tiles are heavy and render identically everywhere.

Click or drag a component onto the canvas, then connect the handles to draw the data flow.

3 nodes · 2 edges

Components · 35

Client & Edge4

Compute & Gateway7

Storage & Caching11

Messaging & Streaming6

Coordination & Ops5

Intelligence2

React Flow