Google Maps is one of those systems that looks simple until you try to actually build it. Type in a destination and a route appears in a fraction of a second, complete with an ETA that somehow accounts for the accident three exits ahead. Underneath that simplicity sits a genuinely hard distributed systems problem: how do you serve map imagery to billions of devices, compute shortest paths across a graph with hundreds of millions of nodes, and fold in live traffic data, all while keeping response times under 200 milliseconds? This is also a classic Navigation System Design problem and a favorite in system design interviews, since it touches so many core concepts at once: caching, graph algorithms, and streaming data pipelines. Let's walk through how it actually works.
21 Petabytes of Map Data
Google Maps has driven over 10 million miles with Street View cars, mapped 220 countries, indexed 200 million businesses, and stores roughly 21 petabytes of geographic data. When you ask for directions from New York to Los Angeles, the system must find the best path through a graph of 500 million road intersections in under 200 milliseconds, while accounting for real-time traffic from billions of anonymous phone pings. That combination of scale and latency is really the whole story of this system's architecture.
Map Tile Architecture
The first problem to solve is rendering. Nobody's device is downloading the entire planet every time they open the app, so the map has to be broken into pieces that can be fetched independently and cached aggressively. This is where a good grasp of caching strategies pays off, since almost the entire tile-serving layer is built around cache placement and invalidation decisions.
Map Tile System:
Zoom Level Tiles Detail
────────── ─────────── ───────────────────────
0 1 Entire world
5 1,024 Country level
10 ~1 million City level
15 ~1 billion Street level
21 ~4 trillion Building detail
Each tile: 256x256 pixels (PNG/WebP/Vector)
All tiles pre-rendered and cached at CDN
How rendering works:
[User pans/zooms] -> [Calculate visible tile coords]
|
For each visible tile:
CDN cache hit? -> Serve in <5ms
Miss? -> Fetch from tile server
|
Only 12-20 tiles visible at once
Total map never loaded - only your viewport
Modern: vector tiles (JSON data, client renders)
instead of raster tiles (pre-rendered images)
3-5x smaller downloads, smooth zoom animation
Route Calculation: Why Dijkstra Fails
Tip: Contraction Hierarchies aren't the only trick in this space, and interviewers like when you know that. A* with landmarks (the ALT algorithm) is another common speedup, and a lot of production routers actually layer both: landmarks for a quick heuristic, hierarchy shortcuts for the heavy lifting. If you're asked this in an interview, naming the general pattern (precompute structure offline, shrink the search space online) matters more than memorizing one algorithm's name.
Once the map is on screen, the harder problem starts: finding a route. A naive shortest-path approach falls apart at this scale, and understanding why is usually the crux of a strong answer in a Google Maps System Design Interview.
Shortest Path at Scale:
Road graph: 500 million nodes (intersections)
2 billion edges (road segments)
Dijkstra's algorithm: explores nodes outward from start
NYC to LA: would explore ~100 million nodes
Time: several minutes -> UNACCEPTABLE for real-time
Contraction Hierarchies (what Google actually uses):
OFFLINE pre-processing (takes hours, done once):
1. Rank all nodes by 'importance'
Highway interchange = high importance
Residential cul-de-sac = low importance
2. Add 'shortcut edges' for important nodes
'Interstate I-80: Chicago to NYC' = 1 shortcut edge
(replaces traversing 10,000 individual road segments)
ONLINE query (milliseconds):
1. Search upward from start (toward important nodes)
2. Search downward from destination
3. Meet in the middle at highway-level shortcuts
4. Expand shortcuts back to actual road segments
Result: explores ~1,000 nodes instead of 100,000,000
Query time: < 200ms for ANY route on Earth
Live Traffic Architecture
Watch out: "snap the GPS point to the nearest road segment" sounds simple but is where real map-matching systems get messy. A phone's GPS can drift 10-20 meters, which is enough to snap you onto the wrong parallel street, a frontage road, or the wrong level of a highway overpass. Production systems handle this with something closer to a Hidden Markov Model over a sequence of points (weighing both distance to the road and consistency with the previous few pings), not a single nearest-neighbor lookup per ping.
A route is only as good as its ETA, and ETAs need live conditions, not just a static graph. This is where Real-time Traffic System Design comes in: phone GPS pings get streamed, matched to road segments, and aggregated continuously. If you've worked with event streaming before, the pipeline below will look familiar, it's the same ingestion and aggregation pattern you'd see in any Kafka-based event sourcing system, just applied to location data instead of business events.
Crowdsourced Traffic Data:
[Billions of Android phones]
|
GPS sample every 30 seconds
(anonymous, aggregated)
|
[Kafka ingestion] ~100M location pings/minute
|
[Map Matching]
GPS point (40.7128, -74.006)
-> Snap to nearest road segment (Broadway & Wall St)
-> Calculate speed: distance / time between pings
|
[Traffic Aggregation]
Per road segment:
avg_speed = median(all_phone_speeds_last_5_min)
traffic_level = avg_speed / speed_limit
|
[ETA Calculation]
For each route segment:
historical_speed (this road, this time of day)
real_time_speed (crowdsourced)
predicted_speed = blend(historical, real_time)
segment_ETA = segment_length / predicted_speed
Total ETA = sum(all segment ETAs)Interview Tip
When designing Google Maps, cover: (1) tile-based rendering with CDN delivery (only 12-20 tiles visible at once), (2) Contraction Hierarchies for sub-200ms routing on a 500M node graph (not Dijkstra), (3) crowdsourced traffic from phone GPS pings aggregated in real time. The key insight: pre-computation (tiles pre-rendered, graph pre-processed with shortcuts) makes everything fast at query time.
End-to-end Google Maps navigation request flow
Putting It Together
What makes this a great Navigation System Design problem is how much of the hard work happens before a user ever taps "directions." Tiles are pre-rendered and pushed to CDNs. The road graph is pre-processed offline into a contraction hierarchy so that a query only has to touch a few thousand nodes instead of hundreds of millions. Traffic gets aggregated continuously so it's ready the instant a route is requested. None of the individual pieces, tile caching, graph pre-processing, or stream aggregation, are exotic on their own. The skill is in recognizing that Distributed System Design for Google Maps is fundamentally about shifting as much computation as possible out of the request path and into offline or streaming pipelines that run continuously in the background.
If you're preparing for interviews, it's worth practicing how you'd explain the tradeoffs behind each layer rather than just naming the technologies. Resources like system design learning platforms can help you drill this kind of scenario repeatedly until the reasoning becomes second nature.
Google Maps serves pre-rendered tiles at each zoom level from CDN. Route calculation uses Contraction Hierarchies for millisecond shortest-path on massive graphs. Traffic is crowdsourced from phone GPS data. ETAs combine historical speed profiles with real-time traffic overlays.