Design Google Maps

Scope the interview to three features for about 1 billion daily users: user location updates, navigation including ETA, and map rendering. Navigation should support driving, walking, transit and cycling, and must react to traffic. Multi-stop routes, business search and photos are out of scope.

Non-functionally, accuracy is paramount: a wrong turn instruction is a real-world failure. Rendering must be smooth on mobile, data usage and battery drain must be low, and the service must be highly available. Before designing, it helps to cover a little map vocabulary, because the data representations drive the architecture.

A position is a latitude (north-south) and longitude (east-west). Drawing a sphere on a flat screen requires a projection; web maps commonly use a variant of Mercator, which preserves angles but inflates areas near the poles. Geocoding turns an address into coordinates and reverse geocoding does the opposite, often by interpolating along road segments. Geohashing encodes an area as a short string and is handy for naming tiles.

The world is rendered as square tiles, typically 256 by 256 pixels. At zoom level 0 one tile covers the planet; each level splits every tile into four, so level n has 4^n tiles. The client fetches only the tiles covering its viewport at the current zoom. Separately, roads are modelled as a graph of intersections and segments. The whole planet's graph is far too large for one machine's memory, so it is cut into routing tiles, each holding the nodes and edges in a geographic square plus references to neighbouring tiles.

Tiles: at zoom 21 there are 4^21, about 4.4 trillion tiles. At 100 KB each that is 440 PB. But roughly 90% of the Earth is ocean, desert or otherwise empty and compresses to almost nothing, cutting it to around 44–88 PB. All lower zoom levels together add about one third more, since 1/4 + 1/16 + ... converges to 1/3. So imagery is on the order of 50–100 PB, a pure storage-and-CDN problem.

Location updates: suppose users navigate 35 minutes per week, which is 5 minutes per day. 1B x 5 minutes = 5 billion minutes per day. Sending GPS every second gives 5B x 60 / 86,400, about 3.5 million updates per second. Clients batch, sending every 15 seconds, so the request rate falls to roughly 3.5M / 15, around 230K QPS on average and perhaps 1M at peak.

The location service receives batched GPS points over HTTP from navigating clients. Batching is the key client-side optimisation: recording every second preserves accuracy for traffic analysis, while sending every 15 seconds cuts request overhead and radio wake-ups, saving battery. The write rate is huge, data is append-only, and availability matters more than strict consistency, so a wide-column store like Cassandra, keyed by user ID and timestamp, fits well.

The raw stream is also valuable to many other systems: live traffic estimation, detecting new or closed roads, personalisation and ETA model training. So the service writes each batch to Kafka, and independent consumers read the stream at their own pace. This decoupling means the ingestion path stays simple and fast, and new analytics can be added without touching it.

Rendering tiles on the fly per request would waste enormous compute on the same output, because tiles are identical for every viewer. Instead tiles are pre-computed offline for every zoom level and served as static files from a CDN, which caches them at edge locations near users. A tile's URL can be derived purely from a geohash of its area and the zoom level, so the client can compute the URLs it needs locally with no server round trip.

Many systems add a tiny tile-URL service so the URL scheme can change without client releases. Modern clients increasingly use vector tiles rather than raster images: they carry paths and polygons that the device draws itself with WebGL. Vector tiles compress far better, scale smoothly between zoom levels instead of jumping between pixelated images, and allow restyling on the client, at the cost of more client-side rendering work.

A navigation request flows through several components. The geocoding service resolves origin and destination addresses to coordinates. The route planner asks the shortest-path service for the top-k candidate routes; this runs an A* style search over routing tiles loaded on demand from object storage, ignoring traffic and climbing the tile hierarchy to highways for long trips. The ETA service then predicts travel time for each candidate using machine learning over current and historical traffic. A ranker applies user filters such as avoiding tolls or highways and returns the best few.

Behind the scenes, updater services consume the Kafka location stream: one rebuilds routing tiles when roads change, another maintains live traffic per road segment that the ETA model reads. Because routing tiles change slowly while traffic changes by the minute, separating static graph structure from dynamic edge weights keeps tile processing cheap.

Once a user is navigating, conditions change: an accident blocks a lane, traffic clears up. The system must know which active navigators are affected by a change to a given road segment. Naively scanning every active route for every traffic update is far too slow. A better structure records, for each navigating user, the routing tiles their route covers and, hierarchically, the larger tiles that contain them; when traffic changes in a tile, only users whose routes touch that tile are re-evaluated.

To deliver new ETAs or a reroute, the server needs to push to the client. WebSocket is the natural choice because it is bidirectional and lighter than long polling for frequent messages; mobile push notifications are too limited in payload and latency. The client then fetches any new tiles needed for the changed route.

The main trade-offs are pre-computation versus freshness, and client versus server work. Pre-rendered tiles and pre-built routing tiles make every online request cheap but mean map edits propagate through a batch pipeline. Vector tiles shift rendering to the device in exchange for smaller downloads. Batching GPS saves battery but adds delay to traffic signals.

For failures, tiles are static and replicated across CDN edges and object storage, so they survive almost anything. The location service is stateless and buffered by Kafka, so a consumer outage only delays traffic updates. Navigation services are stateless and horizontally scalable; routing tiles can be cached on each shortest-path node. The key interview message is to split the problem into ingest, render and route, and to lean heavily on offline pre-processing.