Design Google Maps

1Clarifying the requirements#

Pin down what we actually owe the user before drawing a box. The answers here quietly decide the whole architecture, so treat them as load-bearing.

Candidate: Are we building the whole product, map tiles, search, and routing, or one slice?

Interviewer: Assume the client already renders tiles. I care most about search for a place and turn-by-turn routing with live traffic.

Candidate: Do routes need to react to traffic that changes mid-trip, or is a route computed once at the start good enough?

Interviewer: Mid-trip. If there's a wreck ahead, we should reroute.

Candidate: What's our scale? Global, or one country?

Interviewer: Global. Treat it like planet scale.

Candidate: Last one. Is the road network mostly static, updated maybe daily, while traffic is the fast-moving layer?

Interviewer: Exactly. Roads change slowly. Traffic changes every few seconds.

What those answers just told me:

• The interview is about routing and the traffic loop, not tile rendering.
• "Roads change slowly, traffic every few seconds" is the thesis of the whole design: precompute against roads, overlay traffic at query time.
• Had the interviewer said "roads change by the minute," half of section 6.2 would be wrong. This is why I ask.

Functional requirements

• Search a place by name or address and get its coordinates (geocoding).
• Given a dropped pin, return the nearest places or the address (reverse geocoding).
• Compute a route between two points for driving, with distance and ETA.
• Reflect live traffic in the ETA and reroute mid-trip when conditions change.
• Serve map tiles for a viewport at a given zoom level.

Non-functional requirements

• Low latency. Route requests under about 300 ms at p99. Tile and search under 100 ms.
• Massive read skew. Reads crush writes by orders of magnitude.
• High availability. A stale ETA beats a 500. Degrade, do not die.
• Eventual consistency is fine for traffic. The map does not need the last 200 ms of the world.
• Global. Users in Jakarta and Chicago both get served from somewhere close.

One explicit non-goal, so I do not get dragged off scope:

• I am not building the tile rendering pipeline.
• I am not building the data pipeline that ingests OpenStreetMap-style road edits.
• I consume both as given inputs.

2Back-of-the-envelope estimation#

Get the scale in your head, because it decides the architecture. The point is not arithmetic for its own sake. It is to find the one number that dictates everything.

Users and traffic.

• 1 billion daily active users.
• Most open the app, look at the map, maybe search once. A smaller slice actually navigates.

Read QPS (tiles and search).

• Say each DAU triggers roughly 40 tile and map reads a day.
• 40 billion reads over 86,400 seconds is about 460K QPS average.
• Peak is spiky, call it 3x: about 1.4M QPS.
• Tiles dominate and are trivially cacheable, so this is a CDN problem more than a backend problem. Note it and move on.

Routing QPS.

• Suppose 100 million people navigate per day, each recomputing a few times (reroutes, re-searches), say 5 route calls each.
• 500 million route requests over 86,400 is about 5,800 QPS average, roughly 20K QPS at peak.
• Routing is expensive per call, so this is the number that scares me.

Traffic write ingest.

• 100M active navigators, one GPS ping every 5 seconds, is 100M / 5 = 20M writes per second of raw location data.
• That is the firehose. We never store it raw; we aggregate it into per-segment speed.

Storage.

• Road graph: roughly 100M segments globally, each with geometry, speed limits, turn restrictions, maybe 2 KB each. About 200 GB.
• Places and POIs: about 500M places at roughly 1 KB each is about 500 GB.
• Map tiles: petabytes of pre-rendered images, but those live on a CDN and object store, never our hot path.

3Core APIs#

Keep the surface small and make the cache keys obvious from the shape of the request. Clean APIs are a feature.

GET /v1/geocode?q=blue+bottle+coffee&near=37.77,-122.41&limit=5
200 OK
{
  "results": [
    { "placeId": "p_8f2a", "name": "Blue Bottle Coffee",
      "lat": 37.7764, "lng": -122.4172, "score": 0.94 }
  ]
}

GET /v1/reverse?lat=37.7764&lng=-122.4172
200 OK
{ "address": "66 Mint St, San Francisco, CA", "placeId": "p_8f2a" }

POST /v1/route
{
  "origin": { "lat": 37.77, "lng": -122.41 },
  "dest":   { "lat": 37.80, "lng": -122.27 },
  "mode": "drive",
  "depart": "now"
}
200 OK
{
  "routeId": "r_19c3",
  "distanceMeters": 11200,
  "etaSeconds": 1380,
  "polyline": "}_~iF~ps|U...",
  "steps": [ { "text": "Head east on Mint St", "meters": 120 } ]
}

Three choices worth defending:

• Geocode and reverse are GET, so a CDN or edge cache serves repeat queries without touching the backend.
• Route is POST, because the body (origin, destination, departure) is the cache key and it is almost never a repeat.
• The route returns a routeId, so the navigation stream references the trip the server already computed instead of re-sending both endpoints on every ping.

For live navigation, the client streams its position over a long-lived connection:

WS /v1/navigate?routeId=r_19c3
client -> { "lat": 37.78, "lng": -122.39, "speed": 14.2 }
server -> { "etaSeconds": 1290, "reroute": false }
server -> { "etaSeconds": 1510, "reroute": true, "polyline": "..." }

Why a WebSocket and not polling:

• A navigating phone sends a ping every 5 seconds for 20-plus minutes.
• A fresh HTTPS handshake per ping would be wasteful at 20M pings per second.
• The connection stays open for the trip.

4High-level design#

The spine is the split from section 1: slow-moving road data on one path, fast-moving traffic on another.

• Clients hit a CDN for tiles and a gateway for everything else.
• The gateway does auth, rate limiting, and routing to three real services.
• The traffic loop runs continuously and independently of any single request.

Tiles bypass everything.

• They hit the CDN directly.
• On a miss, the CDN pulls a pre-rendered image from object storage.
• The backend never sees a tile request.

Search service handles geocoding and reverse geocoding.

• Queries a geospatial index to narrow by location.
• Queries a text index to match names, then ranks.

Routing service holds the road network as an in-memory graph.

• Runs the shortest-path algorithm.
• Weights edges by current speed read from the live speed cache.

Navigation service owns an active trip.

• Takes the client's GPS stream and matches it to the route.
• Recomputes ETA and decides when a reroute is worth it.

The traffic loop (bottom path).

• Phones send GPS pings to a stateless ingest tier.
• Ingest drops them onto an event stream.
• A speed aggregator consumes the stream, map-matches pings to segments, computes a rolling average speed, and writes the live speed cache that routing reads.

5Data model#

The road graph is the heart. Model it as nodes (intersections) and directed edges (road segments).

• Directed matters: a one-way street is one edge, a two-way street is two.
• Turn restrictions (no left turn here) live as forbidden node-to-node transitions, checked during the search rather than modeled as extra edges.

nodes

edges

places

Live speed is deliberately not a durable table. It lives in an in-memory key-value store keyed by edge:

Why the TTL is exactly 2 minutes:

• If the aggregator falls behind, stale traffic expires and routing reverts to the static speed_limit (free-flow speed).
• Better than trusting a 10-minute-old number that might send someone into a jam that already cleared.
• Two minutes survives a brief aggregator hiccup and is short enough that we never route on badly stale data.
• The key property is the fallback: a missing key is not an error, it is "assume the road is clear," the safe default.

6Deep dives#

6.1 The geo-index: finding things near a point#

"Coffee near me" means "find places inside this box, then rank." The naive index fails:

• A plain B-tree on lat and lng is 1D; a bounding box is a 2D range.
• Indexing on lat alone returns everything at that latitude across the entire planet.
• I want to turn 2D space into a 1D key that preserves locality, so nearby places sit near each other in the index.

Use a space-filling curve.

• Divide the world into a grid, then number cells along a curve that snakes through 2D space (a Hilbert or Z-order curve).
• Two points close on the ground usually get close cell numbers.
• Store cell_id on every place and index it.
• A nearby query becomes: compute the handful of cells covering the viewport, then range-scan those cell ranges.

The sharp edge is cell size.

• Too coarse and a cell holds a whole city, so I scan millions of rows.
• Too fine and a small viewport spans thousands of cells, so I issue thousands of range scans.
• The trick: a hierarchical cell id where top bits encode a coarse cell and lower bits refine it.
• Pick the zoom level whose cells roughly match the query radius, usually 4 to 16 cells covering the viewport. This is essentially how S2 cells (the library behind Google's own geo work) are built, and naming that tends to land well.

Why the last two steps matter.

• Cells are squares; the query is a circle. The cell cover overfetches.
• The exact haversine filter and ranking happen in memory, keeping the index simple and pushing the fuzzy part into cheap math.
• One failure mode to raise unprompted: a cell straddling a curve discontinuity can place two physically close points far apart in cell-id space. That is why I always cover the viewport with several cells and union the results rather than trusting a single range.

6.2 Routing on a planet without melting#

This is the signature hard part, and where I spend the most time. Plain Dijkstra is hopeless at this scale:

• From San Francisco to a point 10 miles away, it explores a growing blob of edges in every direction until it stumbles onto the destination.
• On a 100M-edge graph that is hundreds of thousands of edge relaxations per query.
• At 20K QPS, dead.

Idea one: give the search a sense of direction (A*).

• A* uses a heuristic, the straight-line distance to the destination divided by the fastest plausible speed, to prefer edges heading the right way.
• The heuristic must stay admissible (never overestimate remaining time) or A* can return a wrong route, which is why I divide by the fastest speed on the whole network, not the local speed.
• A* explores a narrow cigar between origin and destination instead of a blob.
• Big win, but still too slow coast to coast, because a cross-country trip still walks every residential street near the highway.

Idea two, the real unlock: precompute (contraction hierarchy).

• Remember the one fact from estimation: roads change daily, so I can afford an expensive offline step.
• Pick "important" nodes (highway junctions, major arterials) and precompute shortcut edges that skip the unimportant residential streets between them.
• At query time a long route is: short hop from origin up to the highway layer, a fast run across precomputed shortcuts, short hop down to the destination.
• A cross-country route touches thousands of edges instead of tens of millions. This turns a multi-second Dijkstra into a sub-millisecond lookup.

Live traffic and the structure-versus-weights split.

• The shortcuts were built on static free-flow speeds, so a jammed highway makes a shortcut's weight wrong.
• Keep the contraction's structure fixed (which roads exist, stable day to day) but recompute shortcut weights from live speeds.
• Apply live speeds only to the top road classes, highways and major arterials, where traffic moves the needle and edges are relatively few.
• Residential streets use static speeds, because a 25 km/h residential road being 10 percent slower never changes the route choice.
• This keeps the live-weight update cheap and bounded: re-weighting thousands of important edges per region, not all 100 million. That static-structure, live-weight split is what makes planet-scale routing with live traffic tractable.

6.3 Live traffic and mid-trip reroute#

The traffic loop has to turn 20M raw GPS pings per second into clean per-segment speeds without ever bottlenecking the routing read path.

Ingest is stateless and does almost nothing.

• Validate, attach a timestamp, drop onto the event stream partitioned by geo-cell.
• Partitioning by geo-cell is deliberate: a traffic jam is dense in space, so a hot road loads one partition's consumers, and I add consumers to exactly the busy cells.

The aggregator does the heavy lifting.

• For each ping it map-matches: snap the raw GPS point (which jitters 5 to 20 meters) onto the most likely segment given recent history.
• It updates a sliding-window average speed for that segment.
• Every few seconds it flushes speed:{edge_id} to the cache.

Map-matching is the subtle part.

• A naive "nearest road" snap flaps between a highway and the frontage road beside it, making a clear highway look jammed because it borrowed slow frontage-road pings.
• I keep a short per-device trajectory and prefer the segment sequence that is physically consistent with the last few pings, a hidden Markov model over candidate roads.
• Noisy device, consistent answer.

The reroute decision (where good products get ruined by bad judgment).

• Every new position re-estimates ETA on the remaining route using fresh speeds.
• Periodically, say every 60 seconds or when ETA jumps past a threshold, compute a fresh route from the current position.
• Only tell the user to reroute if the new route saves meaningful time: "more than 90 seconds or more than 10 percent," whichever is larger.
• Below that, a reroute just annoys someone halfway through a turn. The threshold is a product decision baked into the engineering: cheap to compute, expensive to spam.

7Bottlenecks and trade-offs#

The traffic firehose is the pressure point.

• 20M writes per second is the thing most likely to fall over.
• Defense: never store raw pings durably, aggregate in-stream, partition by geo-cell so load spreads naturally.
• If the aggregator lags, the speed cache TTL expires stale data and routing degrades gracefully to speed limits.
• We lose traffic awareness, not availability. That is the right failure mode, straight from the TTL-plus-fallback design in section 5.

Hot regions.

• Manhattan at 6pm gets vastly more routes and pings than rural Montana. A uniform shard map would hotspot.
• Shard the routing graph geographically but size shards by historical load, not area, so a dense city splits across many shards while a sparse region shares one.
• Cross-shard routes (origin in one shard, destination in another) need a boundary protocol; the contracted highway layer helps, because long routes travel on the shared upper layer rather than stitching across many low-level shards.

Stale routes versus recompute cost.

• I recompute ETA cheaply on every ping but recompute the full route rarely and act only on big improvements.
• The trade-off: a user might drive 30 seconds on a slightly suboptimal path before we suggest better.
• I take that over burning 20K route computations per second on reroutes nobody wanted.

Consistency and the graph swap.

• The road graph updates daily via a blue-green swap: build the new contracted graph offline, validate it, flip traffic to the new in-memory copy, keep the old one warm for rollback.
• In-flight routes finish on whichever version they started on.
• There is no live write path to the graph at all, which is what makes holding it in RAM safe and fast. A live write path into a 200 GB in-memory graph would mean fighting locks on the hot read path; removing that path entirely is the whole trick.

Precompute cost.

• The contraction hierarchy is expensive to build, hours on a large cluster, and it assumes stable topology.
• If a major road closes permanently, we eat the rebuild. Fine at daily cadence.
• It would be wrong if roads changed by the minute, but they do not, and recognizing that is the whole reason this design is fast. This is me cashing in the clarifying answer from section 1.

Search ranking under skew.

• Popular places get queried far more.
• Cache the top results per cell so "coffee near Times Square" does not rescan the index every time.
• Accept that a brand-new cafe takes a few minutes to show up in the hot cache. Freshness traded for latency, deliberately.

Know which parts of the world are allowed to be stale, and build for cheap, graceful degradation instead of perfect, fragile freshness.

8Summary#

The decisions I would defend in the room:

• Split slow data (roads) from fast data (traffic) onto separate paths. This one choice shapes everything else.
• Hold the road graph in RAM. It is only a couple hundred GB, and it makes the fast algorithms possible. This is the number that drove the design.
• Index geography with a space-filling curve, so a 2D nearby-search becomes 1D range scans, then refine with exact distance in memory.
• Route with A* over a precomputed contraction hierarchy, keeping the structure static and applying live speeds only to the high road classes where traffic matters.
• Treat the GPS firehose as a stream to aggregate, never a table to store, with a cache TTL that degrades to free-flow speeds under lag.
• Make reroute a judgment call with a time-savings threshold, run async, never blocking the blue dot.

For related walkthroughs, see our guides on designing a ride-sharing dispatch system and a nearby-friends location service.