Design Google Maps

Clarify the problem

The question is to design Google Maps.

The service has three core jobs. It shows a map that a user can pan and zoom, it finds a route between two places, and it reports how fast the roads are moving now.

A user also searches for places by name, such as a shop or an address. That search rests on an index of named places, built in advance from map data.

Out of scope are the satellites and survey vehicles that collect raw map data. This design starts where processed map data already exists.

Estimate the scale

The service answers 1,000,000,000 map requests a day.

1,000,000,000 / 86,400 = 11,574 requests per second on average.

The road network behind those requests is modelled with about 100,000,000 road segments. That figure is a stated estimate for this design, and routing builds on it.

Most requests are reads of a map that changes slowly. That read-heavy shape is good news, because reads can be cached aggressively and served near the user.

What makes the problem hard

Detail varies wildly with zoom. One view shows a whole continent, the next shows one street, and both must arrive just as fast.

A route is a search through a huge network. Checking every possible path between two cities is out of the question, so the search needs preparation done in advance.

Traffic makes the map a moving target. A route that was fastest an hour ago may be the slowest now, and the design must know the difference.

The stated budget for this design is a route answer in about 2 seconds. Preparation may take hours in the background, but the answer itself may not.

The high-level shape

The high-level design has three parts. A map-serving layer delivers the visible map, prepared in advance and cached near users.

A routing service holds the road network and computes routes on request. A traffic pipeline keeps the network's travel times current, fed by vehicles moving on the roads.

Map display, routing, and live traffic each need their own deep dive.

The split matters because the three parts change at three speeds. The visible map changes daily, the network changes weekly, and traffic changes by the minute.

Map tiles

A map tile is one small square image of the map, cut from a grid that covers the earth at one zoom level. Any map view is a patchwork of tiles, fetched and joined on the user's screen.

The design renders the earth as map tiles, never as one giant image.

Each tile is 256 x 256 pixels, a stated convention of the design. A tile is named by its zoom level and its position in that level's grid, so any client can request exactly the tiles a view needs.

Rendering means drawing a tile from the underlying map data, with its roads, labels and shading. Rendering happens in advance for most of the earth, in the background, before anyone asks.

Zoom levels and the growing grid

Zoom levels run from 0 to 21 in this design, which is 21 + 1 = 22 levels in total. Level 0 shows the whole earth on a single tile-sized grid, and the highest levels show a single street.

Each step up in zoom doubles the grid on each side. The tile count therefore grows by 2 x 2 = 4 times at every level.

At zoom level 2 the whole earth is a grid of 4 x 4 = 16 tiles. The same growth that makes street detail possible makes storing every tile at every level a serious cost.

Most high-zoom tiles are never viewed. The design renders busy areas fully in advance and renders quiet areas on first request, then keeps the result.

Serving one view

A phone screen shows a patch of the grid, plus a border of partly visible tiles. In this design one typical view loads 12 tiles.

At an average tile size of 20 KB in this design, one view moves 12 x 20 = 240 KB of image data. The client stitches the tiles into one seamless map and discards tiles the user pans away from.

Tiles are served through a CDN, which keeps copies near users. A tile for a famous city centre may be served from cache almost every time, at a round trip of a fraction of a second.

Because a tile's content depends only on its grid position and the map data version, its address can name that version. A new version means new addresses, so stale tiles in caches are never overwritten under a reader's feet.

Storage and updates

Storage follows the tile size directly. A stored set of 1,000,000 tiles at 20 KB each takes 1,000,000 x 20 / 1,000 / 1,000 = 20 GB.

The full cost across all levels is managed by policy, not hope. Low-zoom tiles are kept everywhere, high-zoom tiles are kept where demand justifies them, and cold tiles can be re-rendered if asked for.

When map data changes, only the affected tiles are re-rendered, one tile at each zoom level that covers the change. A single new road therefore triggers a small, bounded batch of rendering, not a rebuild of the map.

Labels and languages add a quiet complication. A tile drawn with street names in one language cannot serve a reader of another, so heavily viewed areas are rendered per language, multiplying their storage.

Where tiles strain

Pre-rendering bets that tomorrow's map looks like today's. A road closure an hour old still shows as open on a tile rendered last week, which is why live closures are drawn as an overlay, not baked into tiles.

The seam between tiles can betray the patchwork. A label cut at a tile border must be drawn whole on one side, a rendering rule the pipeline enforces when it prepares each tile.

Routing on the road graph

A routing graph is a network model of the roads, where junctions are points, road segments are the links between them, and each link carries a cost such as travel time. A route is the lowest-cost path through that graph from the start to the destination.

A junction is a point where roads meet.

A segment is a link between two junctions.

A cost is the time to travel one segment.

A path is a chain of segments in order.

Routing turns the road network into a routing graph and searches that graph for the best path.

The graph holds about 100,000,000 road segments, the stated estimate given earlier. Each segment links two junctions and carries a cost, a set of rules, and the road's name.

Rules matter as much as costs. A one-way street is a link that can be travelled in one direction only, and a banned turn is a pair of links that may not be chained.

Cost means time

The cost of a segment is the time a vehicle needs to cross it. Free-flow cost is the time with no traffic, worked out from the segment's length and speed limit.

Live cost replaces the free-flow figure when traffic data exists, which live traffic supplies. The graph's shape stays fixed while its costs breathe with the day.

Different travellers need different costs. A lorry cannot use a road with a low bridge, and a cyclist avoids a motorway, so the search filters links by vehicle before it compares costs.

Searching a huge graph in time

A naive search spreads outward from the start, segment by segment, until it reaches the destination. Across a whole country that search touches far too many segments to answer in the design's budget of about 2 seconds.

Searching outward from both ends at once helps greatly. The two searches meet in the middle, and each covers a far smaller area than one search crossing the whole country.

Precomputation helps more. The work is done in advance, when nobody is waiting, so the live search can take stored shortcuts instead of exploring every street.

In this design the graph is divided into areas of about 1,000,000 segments each. That gives 100,000,000 / 1,000,000 = 100 areas, and the best paths between each area's border junctions are computed and stored in advance.

A long route is then assembled from a short local search, a chain of stored border-to-border paths, and a short local search at the far end. Only the local searches explore individual segments live.

Holding the graph ready

The graph must sit in memory for the search to run at speed. A memory read takes about 100 nanoseconds, while a disk read would stall the search at every junction.

Compact storage keeps that possible. In this design one segment's core data takes 32 bytes, so the link data for the whole network totals 100,000,000 x 32 / 1,000,000,000 = 3.2 GB.

That core fits on one strong server, and copies are replicated across data centers near users. Names, rules and live costs live beside the core and are loaded by the search as needed.

Routing servers are stateless, so any server can answer any route. A load balancer spreads requests across them, and losing one server loses no routes.

When the graph is wrong

Roads close and open daily. The graph is rebuilt from fresh map data on a regular cycle, and urgent closures are applied as small patches between rebuilds.

A closed segment is simply removed from the search. The search then finds the best path through what remains, which is exactly the behaviour a driver wants from a diversion.

If live costs are missing, the search falls back to free-flow costs. The route may be less wise, but the service still answers, which is graceful degradation applied to routing.

Live traffic

Live traffic is the current speed of travel on each road segment, estimated from vehicles moving on that segment right now. It turns the routing graph's fixed costs into costs that follow the real day.

Live traffic explains where current speeds come from and how they reach the routing graph.

No sensor network covers every road. The design instead learns speeds from the vehicles themselves, with each moving phone acting as a probe that reports where it is and how fast it is travelling.

Reports are stripped of who sent them before anything else happens. The pipeline needs movement patterns, never identities, and it keeps raw reports only briefly.

The probe stream

In this design 10,000,000 users are travelling with the service active at a busy time. Each probe sends a report every 30 seconds.

10,000,000 / 30 = 333,333 reports arrive per second. Each report is tiny, holding a position, a speed and a time, so the stream is wide but shallow.

Reports are matched to the segment the vehicle is most likely on. A report beside a motorway, moving at motorway speed, belongs to the motorway, not to the quiet street running alongside it.

Workers consume the stream from a queue, so a burst of reports at rush hour is buffered rather than dropped. The cost of a burst is a slightly older picture, never a lost one.

From reports to segment speeds

Reports are grouped by segment and averaged over a short window of 5 minutes in this design. Averaging smooths out one driver stopping for fuel, which says nothing about the road.

Across one window the probes send 10,000,000 x (300 / 30) = 100,000,000 reports. Even spread over about 100,000,000 segments, busy segments collect plenty of samples, while quiet ones may collect none.

A segment with enough reports gets a live speed. A segment with none keeps its historical pattern, the typical speed for that hour and day, learned from past weeks.

A worked example shows the effect on a route. A road that normally takes 10 minutes, with traffic moving at half its usual speed, takes 10 x 2 = 20 minutes, and its cost in the graph doubles with it.

Feeding the routing graph

Fresh segment speeds are published to the routing servers as cost updates. A routing server swaps in new costs as they arrive, without restarting or rebuilding its graph.

Precomputed paths store the graph's shape, not its live costs. A route assembled from those paths is priced again with current costs before it is offered, so a jam on a stored path can still push the search to a better one.

Drivers already travelling are re-routed sparingly. A new route is offered only when it saves real time, because constant re-routing confuses drivers and can chase jams rather than escape them.

When traffic data fails

If the pipeline stalls, costs simply age. Routing servers keep using the last known costs, then lean more heavily on historical patterns the older the live data grows.

The failure mode is gentle by design. Routes get less wise hour by hour, but the service never stops answering, and recovery is just the stream flowing again.

False reports are the hostile version of the same problem. Speeds are trusted only when several probes agree, so one vehicle crawling along a clear road cannot poison a segment for everyone.

Evaluation

A trade-off review tests a finished design on preparation, freshness and failure, and names what each choice gave up. The Google Maps design prepares almost everything in advance, and pays for that speed with storage and with data that is never perfectly fresh.

Evaluation revisits the whole Google Maps design and states what each major choice costs.

The design in one line is this. Pre-rendered map tiles serve the visible map, a routing graph with prepared shortcuts answers routes, and a probe pipeline keeps the graph's costs current.

One theme runs through every choice. Work is moved from the moment of the request to the hours before it, wherever the data allows.

Preparation against freshness

Tiles and route shortcuts are prepared in advance, which makes answers fast and cheap. The same preparation means both rest on map data that is always somewhat old.

The design patches the gap rather than denying it. Closures ride as live overlays on tiles, urgent graph patches land between rebuilds, and traffic costs never come from preparation at all.

The honest summary is layered freshness. The coastline is months old and nobody minds, the road layout is days old and patched, and the traffic is minutes old because it must be.

Storage and load against detail

The service still answers 1,000,000,000 / 86,400 = 11,574 requests per second. Caching tiles through a CDN is what makes that load ordinary rather than alarming.

Detail is rationed by demand. Busy areas are rendered at every zoom and in several languages, while quiet areas are rendered on first request, because storing everything everywhere would buy storage bills, not better maps.

The graph makes the opposite choice. It is small enough to hold whole in memory on replicated servers, so routing pays no storage-versus-detail price and every server can answer every route.

Where the design breaks

If the traffic pipeline dies, routing degrades to historical patterns and free-flow costs. Answers continue, drivers get less wise routes, and the failure shows up as quality loss rather than downtime.

If a CDN region fails, tile requests fall back to origin servers and views load slowly until caches refill elsewhere. Pre-rendering limits the blast radius, because the origin serves finished tiles rather than drawing under pressure.

A bad map data release is the deepest risk, since tiles, graph and search all drink from it. Releases are therefore staged region by region, and the previous version stays ready to restore.

Wrap up the answer

Close the interview answer by walking the method back. Clarify the three jobs, estimate the request load, sketch the three parts, then dive into tiles, the routing graph and live traffic in turn.

Name the seams honestly. Collecting raw map data and running a ride-sharing service both sit next door to this design, and naming them shows judgement about scope.

Across the Uber and Google Maps problems, one lesson repeats. The winning move is separating what changes slowly from what changes constantly, and designing each at its own speed.

The ask in numbers