Design Google Maps

Someone opens the app in a new city, pans around, searches for a cafe, taps "directions" and starts driving. In that minute the system has served a few dozen map tiles, resolved a free-text query to a place, computed a route across tens of thousands of road segments, predicted an arrival time that accounts for the traffic jam two kilometres ahead, and started tracking the phone so it can reroute if the driver misses a turn.

Behind that flow sit a map rendering system (base map data turned into tiles), a search and geocoding system (text to coordinates and back), a routing engine (paths and travel times over the road graph) and a traffic system (GPS probes turned into live road speeds). The phones that use the product also feed it: every navigating device is a traffic sensor.

Assume 300 million daily users, an average of three map sessions each, and up to 15 million devices navigating at the evening peak. Navigating devices send a location fix every four seconds.

Two offline pipelines feed the online services. The map build pipeline takes base map data (roads, buildings, labels, places), produces a numbered release, renders vector tiles into object storage, builds the search index and runs the expensive routing preprocessing. A release is published once and served unchanged until the next one, typically daily for corrections and weekly for larger updates.

The traffic loop runs continuously. Navigation sessions push pings into a partitioned stream keyed by geographic cell, so all pings for one area land on the same consumers. Map matchers snap noisy GPS points to road segments. Aggregators compute a current speed per segment per two-minute window and write it to a live speed store. Every couple of minutes, a customizer turns those speeds into new edge weights for each region and hands them to the routing servers, which swap them in atomically.

Online, the client talks to three services. Tiles come straight from the CDN. Search and geocoding answer from their own index. The routing service holds the preprocessed graph for its region in memory and answers queries using whatever weight version is current, returning that version with the route so ETAs can be traced back to the data they used.

Preprocessing. Rank every node by importance, roughly how many shortest paths would need it. Then remove nodes one by one from least to most important. When you remove a node v, look at each pair of neighbours u and w. If the only shortest path from u to w goes through v, add a shortcut edge u to w whose weight is the sum of the two edges it replaces, and remember that it stands for u, v, w. A quiet cul-de-sac is removed early and creates no shortcuts. A motorway junction is removed late and inherits shortcuts that span hundreds of kilometres. The result is the original graph plus a set of shortcuts, typically about as many as the original edges.

Query. Run Dijkstra forward from the origin and backward from the destination at the same time, but only ever follow edges that lead to a more important node. Both searches climb quickly from local streets to arterials to motorways and meet near the top of the hierarchy. The best meeting point gives the shortest path. Each search settles only a few hundred to a few thousand nodes, so a continental query takes around a millisecond.

Unpacking. The answer is a path made partly of shortcuts. Expand each shortcut recursively into the two edges it replaced until only original road segments remain. That gives the geometry for the polyline and the list of turns for navigation instructions.

Classic contraction hierarchies bake the edge weights into the node order and the shortcuts. When a motorway slows from 100 km/h to 20 km/h, the shortcut weights are wrong, and some shortcuts may no longer represent shortest paths at all. Rebuilding the hierarchy for a country takes minutes to hours of CPU, which is far too slow for traffic that changes every few minutes.

The fix used in production engines is to split preprocessing into two phases. The metric-independent phase depends only on the shape of the road network: it computes a node order or a multi-level partition of the graph, which is expensive but only reruns when the map itself changes. The customization phase takes a set of edge weights and computes the weights of every shortcut or every cell boundary clique bottom-up. It is mostly arithmetic over arrays, runs in parallel, and finishes in seconds for a large country. Customizable Route Planning, the approach Microsoft described for Bing Maps, and customizable contraction hierarchies both follow this split.

So the traffic loop does not rebuild anything. Every two minutes the customizer produces fresh edge weights, runs customization for each region, and ships the new weight arrays to the routing servers. Each server loads them next to the old arrays and flips a pointer. Requests already in flight finish on the old version, and new requests use the new one.

Raw GPS points are off by five to twenty metres and arrive irregularly. A map matcher treats the trip as a hidden Markov model: candidate road segments near each fix are the states, and the transitions favour routes that are physically drivable between consecutive fixes. The output is a list of segments with entry and exit times, from which you get a traversal speed per segment.

The aggregator groups traversals by segment and two-minute window and takes a median, not a mean, because a bus stopping, a driver parking or a delivery rider on a footpath produces outliers that would drag a mean down. A segment with fewer than three traversals in the window blends the live value with its historical profile for that weekday and time, weighting history more heavily as probes get sparse.

ETA is not just the sum of edge weights. Turns, traffic lights and the delay to join a congested road add time, and conditions will change during a long trip. A learned correction model trained on completed trips adjusts the graph estimate, and for trips longer than about 30 minutes later segments use predicted speeds for the time you will actually reach them, not the speed right now.