Google Maps (tiles, routes, ETA)

01 · CONTEXT AND REQUIREMENTS

What a maps service needs to do

A maps service does three very different things: it draws the map on the screen, computes the route between two points, and estimates how long it takes. Each has its own load, data, and tolerance for stale data, and so the design usually splits into three independent paths, rather than a single service. This is the first step of any requirements gathering.

The functional requirements are viewing the map with zoom and pan, requesting a route between origin and destination, and receiving a time estimate that reflects traffic. Among the non-functional ones, three dominate: the map must appear fast even on a slow network, the route must come back in a few moments, and the service must stay available even when the traffic data is delayed.

02 · THE MAP IN PIECES

Tiles: never download the whole map

The device never downloads the whole map: it requests only the pieces (tiles) that fit on the screen. In the OpenStreetMap open scheme, each tile is a 256 by 256 pixel PNG image, addressed by zoom, column, and row.

In this scheme the zoom goes from 0 (zoomed out) to 18 (zoomed in). At zoom 0 a single tile covers the whole world, and at each level the number of tiles per side doubles, so the same place is covered by more and more numerous and detailed tiles.

Because the tile depends only on zoom, column, and row, the response is the same for everyone and rarely changes. This makes it ideal to pre-generate, store in object storage, and serve through a CDN: a good share of the requests can be served at the edge, without touching the origin servers.

1. The device computes, from the position and zoom, which tiles cover the screen and requests each one by the zoom, column, and row address.

2. The request first reaches the CDN. If it already has the tile, it responds right there, without bothering the origin servers.

3. If the CDN does not have the tile, it forwards the request to the tile service.

4. The service fetches the ready-made tile from storage, without drawing anything on the spot.

5. The tile goes back to the device and the CDN keeps a copy for the next requests from the region.

6. Outside the user's path, the generator rereads the map data when it changes and rewrites only the affected tiles.

There are two ways to deliver a tile. In the vector one, the server returns data clipped to the tile's boundaries instead of a pre-rendered image, and only what is in the current window and zoom is transferred.

03 · ROUTES ON THE ROAD GRAPH

Shortest path at country scale

To compute routes, the road network becomes a graph: intersections are vertices, road segments are edges, and the weight of each edge is the time to traverse it.

The shortest path can come from Dijkstra's algorithm, but road networks have tens of millions of vertices, which makes running it from scratch on every request impractical.

The way out is to preprocess. Contraction hierarchies create shortcuts in a prior phase, skipping unimportant vertices, and rely on the fact that road networks are highly hierarchical. Since the network changes little, the precomputation can take from seconds to hours and be done once; afterward, many queries are answered in microseconds each.

The graph of a country or of the world does not fit on one machine. A common choice is to partition it by region, keeping each partition close to whoever queries it; routes that cross a region's border need to query the neighboring partitions, and that is where the design demands the most care.

1. The device sends origin and destination; the gateway forwards the request to the route service.

2. The route service asks the location service to link each point to the nearest road vertex.

3. With the vertices, it loads the graph partitions that cover the region between origin and destination.

4. The search uses the precomputed shortcuts to skip unimportant segments and reach the shortest path quickly.

5. The route goes back to the device as a list of segments to draw on the map.

6. Outside the user's path, preprocessing recomputes the shortcuts when the road network changes.

Finding the nearest vertex to a point calls for a spatial index. Geohash is a simple option: the longer the common prefix between two codes, the closer the points are.

The reverse, however, does not hold: two very close points can have a short prefix or none at all, and this happens, for example, on opposite sides of the 180-degree meridian. One way around it is to also query the neighboring squares, which Solr does with a list of prefixes.

04 · TRAFFIC AND ETA

Estimating travel time

Google Maps analyzes live traffic data for road segments worldwide and uses machine learning to combine current traffic with historical patterns. History alone is not enough, because the exact time of the peak varies quite a lot from day to day and month to month.

In an interview design, the usual source of live traffic is the anonymous positions sent by devices. They arrive in a high, continuous stream, so they go into a message queue and a consumer aggregates them, in a data pipeline, into current speed per road segment.

1. The device sends its position from time to time; the gateway delivers it to the ingestion service.

2. Ingestion validates the position and puts it on the queue, without waiting for the traffic calculation.

3. The aggregator consumes the queue, computes the current speed of each segment, and writes the result.

4. When the user asks for the ETA of a route, the gateway invokes the ETA service.

5. The service reads the current traffic and the history for the route's segments and hands everything to the prediction model.

6. The sum of the segments' predicted times goes back to the device as the route's ETA.

In 2020, DeepMind described how it divided the network into Supersegments, adjacent segments that concentrate traffic volume. The system has a route analyzer, which processes terabytes of traffic information to build them, and a graph neural network that predicts the travel time of each one.

In the model's graph, each segment is a node and the edges link consecutive segments on the same road or connected by an intersection. This lets the model look at adjacent roads, because congestion on a side street can affect a larger road.

The result was measured: according to DeepMind, ETAs were already accurate in more than 97% of trips, and the work with graph neural networks improved real-time ETA accuracy by up to 50% in some cities.

05 · DECISIONS AND TRADE-OFFS

Three paths, three profiles

Putting the parts together, each path has a different tolerance for stale data, and that is what justifies separating them. The base map changes slowly and tolerates long caching; the road network changes little and tolerates precomputation; traffic changes all the time and requires its own stream.

This separation also isolates failures: a delay in the traffic pipeline makes the ETA less accurate, but does not bring down the map or the route calculation, which matches the priority of disponibilidade set in the requirements.