STANDARDwalkthrough
Road Network Graph and Partitioning
A routing server receives 10,000 route requests per second. Each request needs to traverse a graph of 500 million nodes and over 1 billion edges.
A Contraction Hierarchies query touches 1,000 nodes, so that is per query on SSD. At 10K QPS, we need 1,000 seconds of compute per second, clearly impossible.
“If we store this graph on SSD and perform random access during pathfinding, each node lookup costs about 100 microseconds.”
The constraint: the entire graph must live in RAM. Each node stores latitude (8 bytes), longitude (8 bytes), elevation (4 bytes), and adjacency metadata (roughly 180 bytes for edge lists, road type, speed limit, turn restrictions).
That totals about 200 bytes per node. Total memory: .
With RAM, each node lookup costs 100 nanoseconds: per query. That is 1,000x faster than SSD.
We partition the global graph into geographic regions (e.g., US-West, US-East, Europe-West) so each server holds one region's subgraph. A cross-partition route (San Francisco to New York) is handled by identifying partition boundary nodes, the highway entry and exit points where regions meet.
The query engine routes within the source partition to the boundary, jumps to the destination partition, and stitches the paths together. OpenStreetMap provides the open-source road graph: 8 billion GPS points contributed by 2 million mappers, forming the same node-edge structure.
Google builds its graph from Street View imagery, satellite data, and partner feeds. Trade-off: 100 GB per server means we need high-memory machines (128 to 256 GB RAM), which limits the number of servers we can deploy.
Fewer, larger servers reduce operational complexity but create bigger blast radii if one crashes. The alternative, sharding by hash instead of geography, would scatter geographically adjacent nodes across machines, destroying data locality for pathfinding.
What if the interviewer asks: how do we handle graph updates when new roads are built? We rebuild the affected partition's subgraph and hot-swap it into the routing server.
The old graph serves queries until the new one is loaded, ensuring zero downtime.
Related concepts