Location & mobility · Advanced

Maps, routing & tiles

Vector tiles from a CDN, routing over a contraction-hierarchy graph, and ETAs from live probe traffic.

Every part, and why it is there

Maps app

Panning the map fetches tiles; searching an address calls geocoding; tapping Directions calls routing. Three very different workloads.

Navigating phones (GPS probes)

Phones in navigation mode report speed and position. Aggregated, anonymised, they are the live traffic sensor network.

Tile CDN

The world is cut into tiles addressed by zoom/x/y. The same tiles are requested by millions of users, so almost every tile is a CDN hit.

Pre-rendered vector tiles

Tiles are built offline from map data and stored as files. Vector tiles are small and styled on the device, so one set serves every theme and screen size.

API gateway

Routes geocoding, routing and probe uploads, and enforces API quotas.

Geocoding & places

Turns “221B Baker Street” into coordinates and back. It is a search problem with fuzzy text and a location bias, not a graph problem.

Places index

Addresses and points of interest indexed by text and location.

Routing service

Finds the fastest path between two points. Plain Dijkstra over a continent would take seconds, so it runs over a preprocessed graph with shortcuts and is split by region.

Road graph + shortcuts

Roads as nodes and edges, preprocessed with contraction hierarchies: shortcut edges let a query skip millions of minor roads. It is loaded in memory on each routing server.

ETA model

Predicts travel time from current and historic traffic. Keeping ETA separate from path-finding means traffic changes do not force rebuilding the whole graph.

Live traffic speeds

Speed per road segment per minute. Read by the ETA model, written by the traffic aggregator.

Probe ingest

Accepts batches of GPS points, strips identity and drops them on a stream. It must be cheap because the probe volume is huge.

Probe stream

Buffers raw probe points so aggregation can fall behind briefly without losing data.

Traffic aggregator

Snaps GPS points to road segments (map matching) and averages speeds per segment per minute.

Asked in interviews at

  • google
  • meta
  • amazon

Learn more

All system design examples