Google Maps System Design: The Whole Whiteboard, Box by Box.

I keep coming back to one whiteboard-style diagram of a Google Maps style system. It is dense. Fifteen lettered sections, three colour-coded flows, and something like a hundred boxes. Every time I look at it I understand one more corner. So I decided to do the slow thing: go through it section by section, in order, and write down what every part does and why it is there.

One honest note before we start, and the board says the same thing in its small print. This is a high-level educational design. It is not Google's internal architecture. The service names are generic. PostGIS, Kafka, Redis, Elasticsearch and friends are example choices that any team could make, not a claim about what Google runs. Where I mention something Google has said publicly, I say so and link it in the references.

How to read the board: three flows

The top of the board has three one-line summaries. If you only remember three lines from this post, remember these.

• Routing flow. origin and destination → geocoding → snap to road graph → route search → traffic-weighted edge costs → ETA → ranked routes → selected route.
• Traffic flow. anonymised location signals → traffic ingestion → stream processing → road segment matching → segment speeds → traffic aggregation → routing engine.
• Map delivery. geographic data → processing → geographic DB → tile generation → tile storage → CDN → client map renderer.

Notice where the flows touch. The traffic flow ends at the routing engine, because traffic is just a number on each road segment that changes how expensive that segment is. The map delivery flow and the routing flow both start from the same geographic database, but they produce very different things. Tiles are for drawing. The road graph is for computing. They are two derived views of one source of truth, and a lot of the design falls out of keeping those two views separate.

The legend also tells you how the steps are numbered. M steps are map and tile delivery, R steps are routing, T steps are traffic, N steps are navigation, and S steps are search. Letters A to O point to sections. I will use the same labels so you can follow along with the picture.

A. Clients

The left edge of the board lists who is talking to the system: an Android app, an iOS app, a web app (a browser using WebGL), a desktop browser, and in-car or navigation devices where the map is projected from the phone or built in. Five kinds of client, one backend.

What I find more useful is the second list, labelled on the device. A maps client is not a thin screen. It does real work locally.

• GPS and sensors. The device produces a position fix, a speed and a heading. Phones fuse GPS with accelerometer, gyroscope, compass, Wi-Fi and cell signals. This fusion happens on the device because it needs to be fast and because raw sensor data is too much to ship.
• Map renderer. Vector tiles arrive as geometry and get drawn by the GPU. That is why you can rotate, tilt and zoom smoothly without asking the server for anything.
• Tile cache. Tiles are kept locally, both the ones you have looked at and the ones you downloaded for offline use (section L).
• Nav UI and voice. The banners, the arrows and the text-to-speech voice. The server says "turn left onto MG Road in 300 m", the device turns it into pixels and audio.
• Location reporter. Sends batched location pings up to the backend (section J). Batched matters. Sending one HTTP request per GPS fix would drain the battery and flood the servers.

The board then has a little table of who the client talks to for what. Tiles come from the CDN. Search goes to the Places services. Directions go to the Routes services. A navigation session talks to the navigation service. Location pings go to traffic ingestion. And the traffic overlay you see on the map is not a separate picture: it is tiles plus segment speeds.

Two different doors: rendering a map is not computing a route. The app can pan and zoom from cache with no API call at all.

This is the first big idea. If you pan around a city you already loaded, the backend application servers do nothing. The device has the tiles, or the CDN has them. Only when you type a search or ask for directions does a request reach a real service. Keeping the heaviest traffic (map viewing) completely away from the application servers is what makes the whole thing affordable.

B. Edge and traffic management

Section B is subtitled "a tile door and an API door". Every request from a client goes through one of two entrances, and they are built very differently.

DNS and regional traffic routing

Both doors start at DNS. The DNS layer is geo-aware or latency-based, and it works with anycast or geo-DNS to send each user to the nearest healthy region or point of presence (PoP). Anycast means the same IP address is announced from many locations, and the internet's routing delivers you to the closest one. The board has a nice line here: a dead region is drained by changing what DNS returns. Failover is not a special mechanism. It is the same routing decision, made with one region marked unhealthy.

The tile door: CDN and edge network

The request on this door looks like GET /tiles/{z}/{x}/{y}, and the board labels it step M7, "highest-volume path, cached everywhere". The CDN serves vector and raster tiles, sprites (icon sheets), fonts and style files. The cache key is roughly style / z / x / y / version.

A cache hit is served from a PoP near the user with zero backend work. A miss goes back to tile storage (step M6). Hot tiles, meaning big cities at low zoom levels, basically live at the edge forever. The long tail, a village at zoom 18 that someone opens once a month, goes back to origin.

Why does this cache so well? Because a tile is the same for everyone. The tile at z=14, x=11722, y=7594 does not depend on who is asking. No cookies, no personalisation, no auth in the URL path. That is the best possible shape for a CDN.

The API door: load balancer, gateway and friends

The second door handles dynamic calls: route requests, search, navigation sessions and traffic queries. The chain on the board is:

• Load balancer. Layer 7, terminates TLS, spreads requests across zones.
• API gateway. Routing to the right service, API versioning, and attaching a request ID so one request can be traced end to end.
• Authentication. API keys for developers, user tokens for signed-in users.
• Rate limiting. Per key, per user, per IP. A public maps API is a favourite target for scrapers, so this is not optional.
• Service discovery. Which instances of each service are healthy, per region.

And then the line that ties the section together: tiles never take this door. If a tile request had to pass through auth, rate limiting and a gateway, you would be paying for compute on the one request type that needs none.

C. Core backend services

Behind the API door sits a grid of services. The board groups them into five columns and adds two words that matter: "stateless" and "each scales alone".

Why stateless matters

Stateless means a service instance keeps nothing in its own memory that another instance would need. Any server can answer any request. If one dies, the load balancer sends the next request somewhere else and nobody notices. If load doubles, you add instances. The state lives in the stores (section M), not in the services.

"Each scales alone" is the other half. Route calculation is CPU and memory hungry. Location ingestion is write heavy and simple. Search is index heavy. If they were one big service, you would have to scale the whole thing to satisfy the hungriest part. Split up, each one gets the hardware profile it needs.

Sync versus async

The bottom of section C has two lines I would frame and hang on a wall.

Sync, on the request path: Directions → Geocoding, Route Calc → ETA. Nav Session → Route Calc (for a reroute). Places → search index. These are things a user is waiting for, right now, with a spinner on screen.

Async, through the event stream: Location Ingestion → traffic pipeline (J). Map Update → tile regeneration (D). Incidents → edge costs. Nobody is waiting on these. They happen in the background and publish their results when ready.

Routing never waits on traffic processing. It reads the latest published speeds and moves on.

This one sentence prevents a whole class of outages. If the traffic pipeline falls behind by five minutes, routes are a little less accurate. They are not slower, and they do not fail. The request path only ever reads a finished, published value. I will come back to this in section J because the board repeats it there, and when a diagram says something twice it is usually the point.

D. Map data and tile generation

Section D is drawn right to left, "from the real world to your screen". It is steps M1 to M7 of the map delivery flow.

M1: data sources

The raw inputs are road network data, building footprints, terrain and elevation, and points of interest. The board also lists imagery, partner data, public data and moderated user edits. No single source is complete or fully correct, which is why the next step exists.

M2: map data processing

This is the cleaning stage. Four jobs are listed:

• Conflate and dedupe. Two sources describe the same road with slightly different coordinates. Conflation decides they are the same thing and merges them.
• Validate geometry. Roads that do not connect, polygons that cross themselves, a building in the sea.
• Attach road attributes. Speed limits, one-way flags, road class, lane counts, turn restrictions.
• Build the road graph. The output that goes to section F.

M3: the geographic database

The cleaned result lands in a spatial, versioned database that the board calls the source of truth. It stores features with IDs, attributes and history. Everything downstream is derived from it. The board's side note spells out the model:

• Geo DB. Features with IDs, attributes, history. Edits land here.
• Tiles. Derived, disposable, rebuilt from the DB.
• Road graph. Another derived view, shaped for routing, not for drawing.

I like the word "disposable". If every tile vanished tomorrow, you could regenerate them. If the geographic DB vanished, you would have lost the map. That tells you where to spend your backup and replication budget.

M4: tile generation

Tiles are produced in batch, per zoom level. For each tile the generator clips features to the tile boundary, simplifies geometry, generalises, and places labels. Generalisation is the clever part. At zoom 5 you do not want every street in a city. You want a dot and a name. At zoom 16 you want every building outline. Same database, very different content per zoom level.

The tile pyramid

The board draws four little grids: z0 is one square, z1 is 2×2, z2 is 4×4, z3 is 8×8. The rule is that zoom level z has 4^z tiles, and higher z means more detail.

That growth is why nobody stores every tile at every zoom. Most of the planet is ocean, desert or forest. Deep-zoom tiles for empty areas can be generated on demand or skipped, and a client can keep zooming into a lower-zoom vector tile ("overzooming") when there is nothing more to show.

Vector tiles versus raster tiles

The board's summary: one geographic DB, two tile formats, both keyed by z/x/y, both cacheable at the edge for a long time because the keys are versioned.

M5 to M7: storage, CDN, client

Finished tiles go to object storage keyed by style/z/x/y/ver. The CDN pulls from tile storage on a cache miss, with the Map Tile service sitting in front of storage as the origin. Then the client fetches from the CDN. That is the whole delivery path.

Map updates and tile invalidation

The dashed yellow box in section D is the hard part of the section. A road is edited, a new building appears, a road closes. What happens?

1. The Map Update service writes the change to the geographic DB.
2. It finds the affected tiles, meaning every (z, x, y) at every zoom level that contains the changed feature.
3. It regenerates only those tiles and bumps their version.
4. The new version means a new cache key, or the old CDN entry is purged.

The trick is the version in the key. Purging a CDN worldwide is slow and unreliable. Changing the key is instant: clients ask for the new version and the old one simply stops being requested and ages out. This is the same idea as hashed filenames for JavaScript bundles on a website.

E. Geospatial indexing

Section E answers one question: how do you find things near a point without checking every thing in the world?

A normal database index sorts by one value. Location has two, latitude and longitude. If you index on latitude alone, "everything between 12.96 and 12.98" returns a band that goes around the entire planet. The fix is to turn two dimensions into one in a way that keeps nearby places near each other in the index. The board shows this as lat / lng → cell id, with the example (12.9716, 77.5946), which is central Bengaluru, mapping to a geohash that starts with tdr1v.

Three ways to cut up the world

The board's one-liners match this: geohash is "lat/lng bits → base32 string, prefix = nearby". S2 is "sphere → cube → Hilbert curve, hierarchical IDs". H3 is "hexagon grid, even neighbours, good to aggregate". S2 is an open-source library from Google and H3 is an open-source library from Uber, so both are things you can use yourself.

Nearby search, step by step

The worked example on the board is "fuel within 2 km".

1. Take the point and find its cell, at a level sized to the radius. For a 2 km search you want cells roughly that size, not cells the size of a country and not cells the size of a room.
2. Add the neighbouring cells, because the radius crosses cell borders. In a square grid that is your cell plus 8 around it.
3. Fetch candidates by cell ID. This is an index range scan, which is cheap.
4. Run an exact distance filter on the candidates, then rank.

Step 2 is the one people forget. If you stand at the very edge of a cell, the nearest petrol station might be ten metres away in the next cell. Looking only in your own cell would miss it. Step 4 is the other one people forget. The 3×3 block of cells is a square, the search area is a circle, so the corners contain things that are too far away. Cells fetch candidates. The exact maths decides.

Other spatial queries

The board lists a few more query types that use the same machinery:

• Bounding box. The viewport on your screen → the set of cells that cover it → the features in those cells. This is what happens when you pan the map and pins appear.
• Point in polygon. Which city, zone or time zone is this point in? Cells or an R-tree narrow it down to a few candidate polygons, and then an exact geometry test decides.
• Nearest road segment for a GPS point. Used by snapping (section G) and map matching (sections I and J).

An R-tree, if you have not met one, is a tree of nested bounding rectangles. It is what PostGIS builds through its GiST index. It handles shapes with real extent, like long roads and big polygons, better than a pure cell scheme.

No single index for every workload: tiles use z/x/y, places use cells or R-trees, traffic keys by segment ID.

I think this line is underrated. Beginners look for the one true geo index. There is not one. Each workload has a natural key, and the design uses whichever key makes that workload a cheap lookup.

F. Road network graph

Section F is "the routing foundation: how a router sees roads". A router does not see a picture. It sees a graph.

• A node is an intersection.
• An edge is a directed road segment between two nodes.
• A two-way street is two edges, one per direction. A one-way street is one edge.
• The edge weight is travel time, not length. It comes from length, speed limit, road class and live traffic.
• Edges carry attributes: speed limit, one-way flag, tolls, lanes, vehicle limits, surface, turn restrictions.

Directed edges matter more than they first seem. The two directions of the same street can have completely different speeds at 9 am. Modelling them as separate edges means the traffic system can give each its own weight with no special cases.

Turn restrictions

The board has a small "no turn" symbol in the middle of the graph and a note: a turn restriction is a cost on an (edge → edge) pair, so "no turn at e" is a forbidden transition.

This is subtle. A plain graph puts costs on edges. But "you cannot turn left from Road A onto Road B" is not a property of A or of B. Both are perfectly usable. It is a property of the pair. So routers either search over edge-to-edge transitions, or expand the graph so each node represents "arriving at this intersection via this edge". Either way, a forbidden turn gets infinite cost and an awkward turn (a left across traffic, a U-turn) gets a penalty in seconds.

A tiny worked graph

Here is my own simplified version of the example on the board. Seven minutes of staring at it teaches more than a page of text. Origin is a, destination is f, numbers are minutes.

Before the jam, the lower path a → d → g → f costs 5 + 4 + 2 = 11 minutes and wins. The upper path a → b → e → f costs 4 + 3 + 5 = 12. Then traffic builds on g → f and that edge goes from 2 to 11 minutes. The lower path is now 20. The upper path, unchanged at 12, becomes the best route. Nothing about the roads changed. Only one number on one edge changed. That is all "traffic-aware routing" means at the graph level.

Four search strategies

A word on the A* heuristic, because the board writes it precisely: straight-line distance divided by maximum speed. The heuristic must never overestimate the remaining travel time, or A* can return a wrong answer. Dividing by the fastest possible speed guarantees an optimistic guess. You could not possibly get there faster than a straight line at top speed.

Contraction hierarchies deserve one more paragraph. In preprocessing, you rank nodes by importance and "contract" the unimportant ones, adding shortcut edges so that shortest paths are preserved without them. A query then only ever climbs upward in importance from both ends and meets in the middle. A cross-country query that would touch millions of nodes with Dijkstra touches a few hundred. The price is that shortcuts bake in edge weights. Change a weight and the shortcuts through it may be wrong. That tension, speed from precomputation versus freshness from live traffic, is the question the board asks in its bottom line, and I get to it in the FAQ.

The section ends with a careful sentence: these are concepts from the routing literature, and which mix Google runs per query is not public. The graph is built from the geographic DB per region and kept in memory on the routing servers. In memory, because a graph search does millions of random lookups, and a disk read per lookup would be hopeless.

G. Route calculation and optimization

Section G is the green box, the heart of the routing flow. Its subtitle is "one request in, ranked route options out, stateless". Eleven steps, R1 to R11.

A few of these hide more than they show.

R5, snapping. Your GPS says you are at a point. Roads are lines. The router needs to know which edge you are on and how far along it. Nearest-segment is the start, but heading matters too. If you are on a flyover above a surface street, or on a divided road, the nearest line might be going the wrong way. The destination has the same problem in reverse: the pin for a mall is in the middle of the building, but the route should end at an entrance on a road. That is why R2 mentions "entrance".

R6 to R8 are one thing. The board has a note under the top row: R6 to R8 happen together in practice. Restrictions and traffic are evaluated as edge costs while the search runs. The diagram draws them as three boxes so you can see the three concerns, but there is no separate "apply traffic" pass after the search. The dashed yellow arrow coming up from section J into R8 is the traffic flow meeting the routing flow.

R10, not tiles. The response is a polyline (an encoded list of coordinates), an ETA, a distance and a list of steps. The route is drawn by the client on top of the tiles it already has. The routing service never touches images.

Shortest distance is not fastest time

The board's example: the fastest route is 6.8 km and takes 9 minutes on the ring road. The shortest is 4.1 km and takes 17 minutes through signals and city streets. Routers usually minimise time, and distance is merely shown.

This is why edge weight is time. If weight were distance, every route would crawl through the city centre. It also explains why your route sometimes looks like a strange detour on the map. It is longer on the ground and shorter on the clock.

What the cost function weighs

cost(route) = Σ edge_time(t)
            + turn penalties
            + toll / ferry / highway penalty   (user prefs)
            + forbidden turn = ∞

Line by line:

• Σ edge_time(t). The sum of travel time over every edge. The (t) is important and I explain it below.
• Turn penalties. A left turn across traffic costs more than going straight. A U-turn costs a lot.
• Toll, ferry and highway penalties. This is how "avoid tolls" works. The router does not delete toll roads. It adds a penalty, large or infinite depending on how strict the preference is.
• Forbidden turn = ∞. Infinite cost means the search will never choose it.

The router optimises over distance, travel time, traffic, restrictions, tolls and preferences, all folded into that one number. Having one number is what lets a single shortest-path algorithm serve "fastest", "avoid highways" and "truck-legal" by changing the weights instead of the algorithm.

edge_time(t) is time-dependent: you reach segment 40 at 9:20, not at 9:00.

If you leave at 9:00 on a 40-minute trip, the traffic that matters on the last stretch is the traffic at 9:35, not the traffic right now. A road that is clear now may be jammed when you get there, and the other way round. So the cost of an edge should be looked up at the time you are predicted to arrive at it. That is exactly where traffic prediction (section N) plugs in.

Alternatives

R9 says "distinct routes". Showing three routes that differ by one side street is useless. Good alternatives share little road with each other, are not much slower than the best, and have no silly loops. This is a ranking and filtering problem layered on top of the search, and it is one reason there is a separate Route Optimization service in section C.

Route calculation is not navigation

The yellow-outlined box in section G compares the two directly, and the board calls mixing them up the classic interview mistake.

Navigation is a stateful loop on top of a stateless calculator. Keep the calculator pure and you can scale it, cache it and reuse it for everything: the directions page, reroutes, ETA sharing, delivery apps on the public API.

The cache key in that table is neat. Exact coordinates almost never repeat, so you cannot cache on them. But round the origin and destination to cells, add the mode, and bucket the time into a few minutes, and suddenly "city centre to the airport, driving, around 8:05" is a key that many users share.

H. ETA and traffic-aware routing

The ETA is the number people actually judge a maps app by. Section H shows what feeds it. The ETA Estimation box takes five inputs:

• Route candidate from R6.
• Segment travel times, the graph weights from section F.
• Current traffic, the live speeds from section J.
• Historical patterns by time of day and weekday.
• Route distance and turn count.

And the formula on the board is: the sum of the predicted time per segment at the moment you will reach it, plus an ML correction (section N). Its output goes to Route Ranking at R9, which picks the fastest first plus distinct alternatives, not three copies of one route.

Why both live and historical

Live traffic tells you what is true now. For the first ten minutes of a trip, that is the best information you have. For a segment you will reach in 45 minutes, "now" is weak evidence. What usually happens on that road at that time on a Tuesday is stronger. So the estimate blends the two, leaning on live data for near segments and on history and forecasts for far ones.

Turn count is on the list because the simple sum of segment times misses things. Each turn, signal and merge adds delay that does not belong to any one segment. The ML correction exists to learn those leftovers: the systematic gap between the simple sum and what real trips took.

During navigation

The timeline at the bottom of the section is a small story:

The initial calculation happens once, with many candidates (section G). During navigation the system re-estimates the remaining route as traffic changes, and switches only when the gain is big enough. The board adds: no flip-flopping between two similar routes.

That last rule is hysteresis, and it is a product decision as much as an engineering one. If route A is 30 seconds faster now and route B is 20 seconds faster a minute later, an app that keeps switching is unbearable and probably dangerous. So there is a threshold. Offer a new route only if it saves a meaningful amount of time, and do not offer it at all if the turn-off is already too close to take safely.

I. Turn-by-turn navigation

Section I is "a stateful loop on the chosen route". At the top sits the Navigation Session Service, holding session = chosen route + progress + ETA, and streaming traffic and ETA updates to the client. Below it is a six-step loop, N1 to N6, that repeats for the whole trip.

Map matching, properly

N2 is the step everything else depends on. GPS is off by several metres on a good day and far more between tall buildings. If you simply pick the nearest road for each fix, the blue dot jumps onto parallel service roads, onto the road under a flyover, onto side streets at every intersection.

A proper matcher looks at the sequence of fixes, not one fix. It asks which path through the road graph best explains the whole recent trace, given that cars move along connected roads at plausible speeds and do not teleport. The standard approach treats this as a hidden Markov model: the true road is the hidden state, the noisy fix is the observation, and the graph says which transitions are possible. During navigation there is an extra hint that the general traffic pipeline does not have. You know the planned route, so being on it is the most likely explanation.

Arrival and going off-route

Arrival detection: you are near or past the destination and slowing → end the session and log the trip (which feeds section N).

Off-route or wrong turn is the red box. The rule on the board: the matched road is not on the route for a few fixes, not one noisy fix → reroute. One bad GPS point should not trigger anything. Three in a row on a road that is not part of the route means the driver really did leave it.

Rerouting is described as a new route request from the current position and heading, back to R4 in section G. Two details here are easy to miss:

• Heading. The new origin is not just a point. The car is moving in a direction, and a route that begins with an immediate U-turn is usually wrong.
• Keep guiding on the old route until the new one lands. Never show a blank screen. Stale guidance for one second is better than none.

The board adds a thoughtful footnote: a wrong turn is not always off-route in the sense of needing a whole new plan. A U-turn back to the original route may still be cheaper than a new route. The router decides, by cost, like everything else.

Where does the loop run?

The note at the bottom says location updates keep flowing all trip → progress, ETA refresh, traffic alerts, maybe a reroute. And then: matching and guidance often run on the device, for tunnels and lost signal, while the server sends the route, traffic and reroutes.

This is a reliability decision. If turn instructions depended on a round trip to the server, every tunnel and every dead zone would silence the app at exactly the moment a driver needs it. So the device carries the route geometry and the maneuver list and can keep guiding alone. In a tunnel with no GPS at all, it can even estimate position from speed and time (dead reckoning). The server's job is the things only the server knows: fresh traffic and better routes.

J. Real-time traffic processing

Section J is the yellow box, the traffic flow, and its subtitle is the mental model: "a stream, not request / response". Nobody asks for this work. It simply never stops. Seven steps, T1 to T7.

Why each step is there

T2, partition by region. Kafka keeps order within a partition. If all pings from one area land in one partition, one consumer sees all the data for a road segment and can aggregate it without coordinating with others. Ingestion also "acks fast" (section C): it writes to the log and returns. It does not wait for any processing.

T3, outliers. A phone in a parked car reports speed zero on a road that is flowing freely. A phone in a pedestrian's pocket reports 5 km/h next to a highway. A GPS glitch reports a jump of 300 metres in one second. All of these would poison the average if they got through.

T3, windows. One to two minute windows are a trade-off. Shorter windows react faster but have fewer samples and more noise. Longer windows are smooth but slow to notice a new jam.

T5, enough devices. A segment's speed is published only when enough devices contributed. This is both a quality rule and a privacy rule, and the board gives it its own box.

The picture of the junction

The board draws a small crossroads with dots. One arm shows segment 811 at 48 km/h. Another shows segment 812 at 7 km/h where the usual speed is 40, drawn as a line of red dots bunched together. A third shows 45, a fourth 52. The caption: a dot is a device ping. Many slow devices on one segment = congestion. One slow device = someone parking or a delivery stop.

That caption is the whole statistical idea. No single phone tells you anything. Agreement between many phones does.

What goes into a segment's colour

• Current speed from this window's observations.
• Historical pattern for the same segment, same hour, same weekday.
• Congestion level = current ÷ free-flow speed. This ratio is what matters. 30 km/h is a disaster on a motorway and perfectly normal on a residential street.
• Incident reports: crash, closure, hazard.
• Traffic forecast (section N): what it will be in 20 minutes.

When a segment has no live data, at 3 am on a quiet road for example, the historical pattern fills in. That is also why confidence is stored at T7. A speed backed by 200 devices and a speed backed by history alone should not be trusted equally.

Privacy

Raw locations never reach other users.

The board's rules: data is anonymised and aggregated per segment. A segment publishes only with enough devices. What leaves the pipeline is a speed and a colour, not who was there. Raw traces get short retention and controlled access. The board also marks as public that Google says live traffic is built from aggregated, anonymised location data from people who opt in.

The minimum-device threshold is worth understanding. If one car is on a rural road at night and that road turns green on the map, then the map has just told the world that someone is driving there. Aggregation thresholds make sure the published signal describes a crowd.

Incident detection

The red box: many devices slow sharply on one segment, plus user reports → incident or closure → the edge cost goes very high or to infinity → routes avoid it (R7 and R8) and alerts go out in navigation (section I). Notice it is the same mechanism again. An incident is not a special feature in the router. It is an edge weight.

And the board closes the section by repeating the rule from section C: routing reads traffic, it never waits on this pipeline. Stale traffic is a quality problem, not an outage.

K. Places search and geocoding

Section K covers everything where the input is text. The main flow is six steps, S1 to S6.

The three example queries in S1 are chosen well, because they are three different intents. "coffee near me" is a category search: many acceptable answers, distance matters most. "12 MG Road" is an address: one right answer, and it needs geocoding. "JFK" is a specific place: one famous answer, and distance barely matters. S2 has to tell these apart before anything else can go right.

Three related operations

• Geocoding. Address → coordinates. "12 MG Road" → (12.97, 77.60). This involves parsing the address into parts, normalising them ("Rd" and "Road", different scripts, missing postcodes) and matching against known addresses. When the exact house number is unknown, geocoders interpolate along the street's number range.
• Reverse geocoding. Coordinates → address. Find the nearest address point, or the nearest street plus its number range. This is what turns a dropped pin into something readable.
• Nearby search. Places inside an area: a radius or a viewport, resolved through spatial cells.

Ranking is where the product lives

The board lists oval tags along the bottom, restaurants, hospitals, petrol stations, airports, businesses, landmarks, with a caption I really like: same index, very different ranking. "hospital" weighs distance. "airport" weighs prominence.

Think about it. If you search "hospital", you want the close one, even if it is small. If you search "airport", you want the big international one 30 km away, not the private airstrip 5 km away. Same index, same query pipeline, but the ranking signals are weighted differently per category. "Open now" is another signal that changes by the minute.

Freshness

The places database holds name, category, hours, phone, photos, reviews and owner edits. It is indexed into the search index asynchronously, in minutes, not instantly. This is the standard pattern: a database of record takes the write, and the search index catches up through a queue. A new cafe being searchable three minutes after it is added is fine. Blocking the write until every index shard confirms is not worth it.

L. Offline maps and client caching

Section L is headed "on the device (a copy, not the server DB)". That bracket is the important part. The device never has the real database. It has a packaged, versioned snapshot of one region.

Four things are stored on the device:

• Cache manager. LRU eviction for tiles, a size cap, expiry and versions. LRU means least recently used goes first when space runs out.
• Local tile storage. Tiles you viewed plus tiles you downloaded.
• Local geographic data. A slice of the road graph, for routing.
• Local search data. A subset of places and addresses.

Offline map download: the user picks a region → the server packs tiles + a road graph slice + places into a versioned bundle. Map data sync: a version check when online, delta updates, and a bundle that is not refreshed eventually expires.

The split makes sense once you sort data by how fast it changes. Road geometry changes over months, so a snapshot works. Traffic changes over minutes, so a snapshot is useless. GPS needs no network at all, because the satellites broadcast and the phone only listens.

Offline routing means the phone itself runs a graph search on the downloaded graph slice. This is one more reason the road graph is a separate artifact from tiles. You cannot route on pictures.

M. Data storage

Section M lines up eight stores. The subtitle repeats the disclaimer: illustrative choices, not Google's stack. What matters is the pairing of data shape to store type.

Three things stand out to me.

TTL on location events. A location ping is valuable for a few minutes and a liability afterwards. Giving it a time-to-live at the storage layer means deletion is automatic. It does not rely on someone remembering to run a cleanup job.

Replayable Kafka. If the map-matching code had a bug for an hour, you can fix it and reprocess that hour from the log. A queue that deletes messages after delivery cannot do that.

Graph snapshots are built, not edited. The routing graph is compiled from the geo DB into a compact, read-only, in-memory format and shipped to routing servers as a versioned file. Live changes arrive as weights (traffic), not as edits to the structure. Structural changes, a new road, arrive with the next build.

N. Analytics and machine learning

Section N has two lanes, and the note on the right names them: real-time is fresh signals and millisecond-latency inference. Offline is months of history, retraining and backtests.

The events going in: traffic events, historical travel times, navigation events, route deviations and search events.

The real-time lane: Events → streaming pipeline (Kafka → stream jobs) → feature processing (segment + time of day, last-N-minute speeds) → online ML models (traffic forecast, ETA, incident detection) → outputs: the ETA in section H, the forecast in section J, and route optimisation in section G.

The offline lane: Data warehouse (months of trips and segment speeds) → offline training (batch features, retrain the models) → backtest and registry (ETA error versus actual, before it ships) → deploy to the online models.

The feedback loop

The nice thing about ETA as an ML problem is that the labels are free. Every finished trip has a predicted arrival time and an actual one. Nobody has to annotate anything. Arrival detection in section I logs the trip, the trip lands in the warehouse, and the next model is trained on how wrong the last one was.

Route deviations are an interesting signal too. If many drivers ignore a suggested turn at the same place, something is wrong there. Maybe the turn is illegal now, maybe the road is closed, maybe locals just know better. Either way it is evidence about the map.

Backtesting before shipping

The registry box says "ETA error vs actual, before it ships". You replay historical trips through the candidate model and compare its predictions with what really happened. If it is better on average but far worse in one city or on rainy evenings, you want to know before real users do. The same features must be computed the same way in the training lane and the live lane, otherwise the model sees one thing in training and another in production. That mismatch is called training-serving skew and it is a classic way for a good offline model to be bad online.

O. Reliability and system design challenges

The last section is a list of ten challenges under the heading "what makes this hard", each with a one-line answer. This is basically an interview cheat sheet, so I will keep it as a table and then expand the cross-cutting notes.

The cross-cutting notes

• Cache invalidation: versioned tile keys, short TTL on routes. Tiles change rarely, so you version them. Routes change with traffic, so you let them expire in a minute or two.
• Fault tolerance: stateless services, replicas across zones.
• Regional failover: DNS or anycast shifts users to a healthy region.
• Retries: idempotent reads, backoff + jitter, no retry storms. A read can be retried safely. But if a million clients all retry at the same instant after a blip, the retry wave is a bigger outage than the blip. Jitter spreads them out.
• Data freshness: traffic in minutes, map edits in hours to days. Different data, different promises.
• Distributed tracing: one trace ID from gateway → route → ETA.
• Metrics and logs: p99 route latency, ETA error, tile hit ratio.

Those three metrics map onto the three flows. Tile hit ratio tells you if map delivery is healthy. p99 route latency tells you if routing is healthy. ETA error tells you if traffic and ML are healthy. If I had to put three numbers on one dashboard for this system, it would be those.

Graceful degradation

Read the answers to 9 and 10 again. Neither says "never fail". They say what the user still gets when something does. I wrote out the ladder as I understand it from the board:

Putting it together: one trip, end to end

Let me run one trip through every section, to check that the pieces really connect. I open the app in Bengaluru at 8:50 and type "airport".

1. The map appears (A, B, D). The renderer asks for the tiles covering my viewport. Most are already in the device cache. The rest come from the CDN through the tile door. No application server is involved.
2. I type the query (K). "airport" goes through the API door: load balancer, gateway, auth, rate limit. Query processing decides it is a category with one very prominent answer. The index is filtered by cells around me (E) and ranked. The international airport comes first.
3. I tap Directions (G). The Directions service takes my GPS fix as the origin and the airport's place ID as the destination. Both are snapped to road segments. The search runs on the in-memory graph (F), reading live segment speeds (J) as edge costs and respecting restrictions.
4. ETAs are computed (H, N). For each candidate, segment times are predicted for the moment I will reach them, with an ML correction. Three distinct routes come back as polylines with ETAs. My phone draws them over its tiles.
5. I press Start (I). A navigation session is created with my chosen route. My phone begins map matching and guidance locally and sends batched location updates.
6. My pings become traffic (J). If I have opted in, those same updates are anonymised, written to Kafka, matched to segments and averaged with everyone else's. I am now a tiny part of someone else's ETA.
7. A jam forms at 9:05 (J, H, I). Many devices slow down on a segment ahead. The published speed drops. The session re-estimates my remaining route, finds an alternative that saves 7 minutes, and offers it.
8. I enter a tunnel (I, L). No signal. The device keeps guiding from the route it holds.
9. I arrive (I, N). Arrival is detected, the session ends, and the trip (predicted versus actual) is logged for the next round of model training.

Every section got used, and at no point did one flow block another. That, to me, is the sign of a good decomposition.

Common mistakes when explaining this design

These are the traps the board itself warns about, plus the ones I fell into.

• Mixing up route calculation and navigation. One is a stateless function, the other is a stateful session that calls it. The board calls this the classic interview mistake.
• Sending tiles through the API gateway. The highest-volume path should have the least machinery on it.
• Using distance as the edge weight. Shortest is not fastest.
• Snapping GPS to the nearest road. Map matching uses the whole trace and the graph's connectivity.
• Making routing wait for traffic. Read the latest published value. Never call into the pipeline.
• Treating tiles as the source of truth. Tiles are derived and disposable. The geo DB is the truth.
• Looking in only one cell for nearby search. Always include neighbours, then filter by exact distance.
• One database for everything. Eight stores is not over-engineering here. The data shapes really are that different.
• Forgetting the time dimension in ETA. You will reach segment 40 at 9:20, not at 9:00.
• Publishing speed from one device. Bad statistics and bad privacy at the same time.
• Rerouting on one noisy fix. Wait for a few consistent fixes, and keep the old guidance on screen until the new route arrives.

FAQ

Is this how Google Maps is actually built?

No, and the diagram says so itself. It is an illustrative reference architecture built from general system design knowledge and a few publicly documented facts. Service names are generic and the technologies are example choices. Treat it as a way to learn the problem, not as a leak of anyone's internals.

The board ends with a question: precompute contraction hierarchies and patch in live traffic, or run plain A* on fresh weights every query. Which one?

My answer is "neither extreme". Plain A* on a continent-sized graph is too slow for interactive long-distance queries. Classic contraction hierarchies are fast but their shortcuts assume fixed weights. The routing literature has a middle path: split preprocessing into a slow, weight-independent phase (the structure of the graph) and a fast customisation phase that re-applies new weights in seconds. Customisable route planning and customisable contraction hierarchies both work this way. You precompute the expensive structure once per map build, then refresh the weights every few minutes as traffic changes. For short trips, where traffic matters most and the search space is small, plain A* on live weights is perfectly fine. So a realistic system can mix both, depending on trip length.

Why not store the road graph in a graph database?

Because the workload is not "flexible queries over relationships". It is one algorithm, run millions of times, where every microsecond per edge lookup matters. A compact array-based graph in memory, built for exactly that algorithm, is far faster than a general-purpose graph database with a query language and disk access in the way.

How does the traffic layer get drawn on the map?

The board says the traffic overlay is tiles plus segment speeds. The base map tiles stay cached for a long time. The speeds are a small, fast-changing layer keyed by segment that the client colours on top. Keeping them separate means the fast-changing data does not destroy the cacheability of the slow-changing data.

What if very few people are on a road? Is there no traffic data?

Below the device threshold, no live speed is published for that segment. The system falls back to the historical pattern for that segment, hour and weekday, and stores a lower confidence. On an empty road that fallback is usually right anyway, since empty roads flow freely.

Why are vector tiles preferred over raster tiles?

They are smaller, they can be restyled on the device without re-downloading (dark mode, a different language for labels), and they stay sharp when you rotate, tilt or zoom between levels. Raster still makes sense for satellite imagery, which is a picture by nature, and for very simple clients.

Geohash, S2 or H3. Which should I use in my own project?

For a first version of "find things near me", geohash is fine and works in almost any datastore. If you already use Postgres, PostGIS with a GiST index is even simpler and handles real shapes. Reach for S2 when you need consistent cell sizes worldwide and need to cover arbitrary regions. Reach for H3 when you are aggregating values over space, like demand or speeds, and want every neighbour at an equal distance.

How can route results be cached if every user has a different location?

By coarsening the key. The board suggests origin and destination cells, the travel mode and a time bucket. Two users a few hundred metres apart, heading to the same area in the same few minutes, share most of a route. The TTL has to be short because traffic changes.

What happens to navigation when the server is unreachable?

The device already has the route geometry and the list of maneuvers, and it runs map matching and guidance locally. So turn instructions continue. What you lose is anything that needs fresh server knowledge: traffic updates, better-route offers and server-side reroutes. With an offline bundle, the phone can even compute a new route itself, without traffic.

How fresh is each kind of data?

The board gives the rough promises: traffic in minutes, map edits in hours to days, places indexed within minutes of a change. Tiles are versioned, so a tile is always exactly as fresh as its version.

How would I answer this in a 45-minute system design interview?

Do not try to draw all fifteen sections. Start with the three flows at the top of the board. State the two doors. Then go deep on whichever part the interviewer steers toward, usually routing (graph, edge weights, A* versus precomputation) or traffic (stream, map matching, aggregation, privacy). Say out loud that route calculation is stateless and navigation is stateful, and that routing reads traffic but never waits on it. Finish with the degradation story.

Where do walking, cycling and transit fit?

The board focuses on driving and only mentions modes in R1 and real-time transit in section L. Conceptually, each mode is a different view of the graph with different allowed edges and different weights. Walking can use footpaths and ignore one-way rules. Cycling cares about gradient and bike lanes. Transit adds timetables, which makes the graph time-dependent in a much stronger way. I would treat transit as its own design problem.

Takeaways

• Three flows, one source of truth. Map delivery, routing and traffic all derive from the geographic database, and they only meet at well-defined points.
• Two doors. Tiles go through the CDN. Everything dynamic goes through the gateway. Never mix them.
• Tiles are for drawing, the graph is for computing. Both are derived views, rebuilt when the truth changes, and only the affected parts are rebuilt.
• Everything in routing is an edge cost. Traffic, tolls, turn penalties, closures and preferences all become one number, so one algorithm serves every case.
• Time is the weight, and time is time-dependent. Cost each segment at the moment you will reach it.
• Route calculation is stateless. Navigation is a stateful loop that calls it.
• Traffic is a stream. Routing reads its latest published output and never waits. Stale traffic is a quality problem, not an outage.
• No single device matters. Speeds are published only from enough devices, which is good statistics and good privacy.
• There is no universal geo index. z/x/y for tiles, cells or R-trees for places, segment IDs for traffic.
• The device is part of the system. It renders, caches, matches, guides and routes offline, which is what makes the product survive bad networks.
• Design the failure, not just the success. For each component, know what the user still gets when it is down.

References and extra reads

• Traffic prediction with advanced Graph Neural Networks DeepMind blog, 2020. The public source for the GNN-based ETA work with Google Maps.
• ETA Prediction with Graph Neural Networks in Google Maps Derrow-Pinion et al., 2021. The paper behind the blog post.
• S2 Geometry The open-source library for S2 cells: sphere → cube → Hilbert curve.
• H3 Uber's open-source hexagonal hierarchical spatial index.
• Geohash The base32 encoding and its precision table.
• PostGIS documentation Spatial types, GiST indexes and distance queries in Postgres.
• Mapbox Vector Tile specification The open format most vector tile stacks use.
• Slippy map tilenames How z/x/y tile addressing works, with the maths.
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks Geisberger, Sanders, Schultes and Delling, 2008. The original CH paper.
• Customizable Route Planning Delling, Goldberg, Pajor and Werneck. Separating structure from weights so traffic can be applied fast.
• Customizable Contraction Hierarchies Dibbelt, Strasser and Wagner. The CH answer to changing weights.
• Hidden Markov Map Matching Through Noise and Sparseness Newson and Krumm, 2009. The standard HMM map matching paper.
• OSRM and Valhalla Open-source routing engines you can run on OpenStreetMap data to see these ideas working.
• Apache Kafka documentation Partitions, ordering and retention, the basis of the traffic stream.

Sourcing note: this article explains a whiteboard-style educational diagram of a maps system. It is not a description of Google's internal architecture. Statements about Google are limited to what Google and DeepMind have published. The worked road graph, the degradation table and the end-to-end trip are my own illustrations.