Google Maps System Design Interview Guide

Nearly every other system design question is about moving data between machines. This one is about a computation. The data barely moves at all — the road network of the entire planet fits in the memory of one ordinary server, and it changes slowly. What makes the question hard is that the answer a user wants is the result of a graph search that, run honestly, takes seconds.

The hard problem sits in one sentence. A shortest-path search over a continental road network is nearly two orders of magnitude too slow to run inside a web request, and the only way to make it fast is to precompute — but the weights on the graph change every minute. Those two facts pull in opposite directions, and the entire design is the resolution between them. Precomputation buys a query that settles a few hundred nodes instead of nine million. It buys it by baking assumptions about edge weights into a structure that takes ten minutes to rebuild. Live traffic invalidates those assumptions continuously. An answer that reaches "use Dijkstra with a priority queue" has not started; an answer that reaches "precompute shortest paths" and stops has not noticed that it just made the traffic feed useless.

The second thing being tested is whether you notice there are two systems here, not one. Drawing the map is not the same problem as routing across it. Tiles are immutable, enormously cacheable, and read by everyone; routes are unique per user, uncacheable, and computed fresh. They share a data source and almost nothing else, and a candidate who gives both the same architecture is telling the interviewer they have not looked closely.

Notice what the question is not about. It is not "find the twenty restaurants near me", which is a spatial index over points and is covered in designing proximity search. Geohash and S2 answer which things are near this point; they say nothing about how to get from this point to that one, because road distance is not a function of straight-line distance and a river with no bridge is invisible to a geohash. This post uses a spatial index exactly once, to snap a pair of coordinates onto the graph, and then never again. It is also not the matching problem from the ride-sharing guide: Uber's hard question is pairing supply with demand and tracking moving drivers, and it calls a routing engine as a black box for ETAs. This post is that black box. Where the two touch — live location ingest — the ride-sharing post cares about the freshness of one driver's position, and this one cares about what a million anonymous traces say about the speed of one road segment.

The functional list is short, and worth reading for what it implies about load rather than what it says. Two of these five are read paths that every user hits constantly; one of them is a background pipeline that never faces a user and yet sets the quality of everything else.

• Render the map. Serve map geometry for any location on earth at any zoom level, fast enough to pan and zoom without visible tearing.
• Route between two points. Given an origin, a destination, a departure time and a travel mode, return the best route with a distance, an ETA, and turn-by-turn instructions. Offer two or three meaningfully different alternatives.
• Navigate. Follow a user along a route, detect when they have left it, and re-route. This is the same routing call at a much higher frequency and a much lower tolerance for latency.
• Reflect live conditions. Congestion, incidents and closures must change both the ETA and the chosen route, not just a colour on the screen.
• Learn from traffic. Turn anonymous position traces from devices into per-segment speeds, and per-segment speeds into the weights the router uses.

The non-functional targets below are where the design actually comes from. Each one is referenced by at least one decision later; the accordions say which.

What each target forces

The usual opening move — daily active users times requests each — is the wrong first question here, because the quantity that shapes this design is not a rate at all. It is the size of the road network, and the surprising thing about it is how small it is.

Start from measured ground truth rather than a guess. The standard benchmark road networks in the routing literature are Western Europe at about 18 million nodes and 42 million directed edges, and the continental United States at about 24 million nodes and 58 million directed edges. Both sit close to 2.3 directed edges per node, which is a property of road networks rather than a coincidence: roads meet mostly at three-way and four-way junctions, and a road graph is very nearly planar. Scaling those to the whole routable planet lands somewhere around 150 million nodes, and the estimator below defaults there.

A node is an intersection, not a GPS point. The curve of a road between two junctions is geometry for drawing, not structure for searching, so it lives with the tiles and never enters the graph. That distinction is worth stating out loud in an interview, because a candidate who models every shape point as a graph node inflates the graph by an order of magnitude and then concludes, wrongly, that it must be sharded.

So the dimensions that bind are: the size of the graph, which decides whether a routing server can hold it; the rate of route computations, which is dominated by navigation re-routes rather than by people tapping “Directions”; the tile corpus, which is the actual storage bill; and the probe volume, which is the actual bandwidth bill.

The shape below follows directly from §1's observation that drawing the map and routing across it are different problems. The left half is a classic cacheable read path that ends at a CDN edge for 97 requests in 100. The right half never caches a response at all. Underneath both sits a pipeline that produces the artifacts they serve, and around the whole thing runs the loop that turns user movement back into routing weights.

Client / Map SDK. Fetches vector tiles and draws them locally, which is why zoom and pan feel instant even though the corpus stops at zoom 14. It also holds the full route geometry after a single request, so ordinary navigation needs no network at all between re-route checks. The non-obvious constraint is that it is also a sensor: the position batches it uploads are the input to the traffic pipeline, which means a client bug can degrade routing for everyone in a city.

CDN edge. Terminates almost all tile traffic. The constraint that makes 97% achievable is that tile URLs are immutable — the map version is part of the path, so a tile is never invalidated, only superseded. A design that PUTs new tiles at the same URL trades that hit rate for an invalidation storm on every map release.

Regional gateway. Authenticates, applies per-key quotas, and pins the request to a regional routing cluster. Quota enforcement matters more here than in most systems because the cost of requests varies by three orders of magnitude between a tile and a distance-matrix call (§10b).

Tile origin. A static file server in front of the tile corpus, handling the 3% of requests the edge misses. It computes nothing: every tile it returns was rendered hours or weeks earlier by the build pipeline. Treating it as a renderer is the common design error, and it turns an 8 TB storage problem into an unbounded compute problem.

Routing service. Holds the entire road graph and its overlay in memory and answers searches. It is stateless in the sense that matters — any replica can answer any query — but it is not small: process start means loading several gigabytes, so replicas are added in minutes, not seconds, and the fleet is provisioned for peak rather than autoscaled into it.

Snap & geocode. Converts a coordinate pair into the graph node the search must start from. This is the one place the spatial-index machinery from the proximity search guide appears, and it is deliberately a separate service because it is the only component whose index is organised by geography rather than by graph structure.

Versioned artifact store. Holds the compiled graph, the overlay topology and the tile corpus, each immutable under a release id. Everything upstream produces artifacts; everything downstream loads them. The constraint is that a release is not atomic across the fleet — servers on the old and new version coexist for as long as the rollout takes, which §10 turns into a real failure mode.

Probe ingest, map matcher, speed aggregator. The pipeline that turns raw positions into per-edge speeds: a durable log absorbs the batches, the matcher decides which road each trace was actually on, and the aggregator combines matched traversals into a speed per segment. The constraint here is statistical rather than architectural — a segment with three observations cannot be distinguished from noise, which is what §10b's minimum-contributor threshold is for.

Customisation. Takes the new speeds and recomputes the overlay weights, then publishes them to every routing replica. This is the component that makes live traffic compatible with precomputation, and §5 is mostly about why it has to exist.

Architectural rationale

How real systems differ

The engines below are all in production and all make different choices, which is the useful part — it shows which decisions are genuinely open rather than settled. Two caveats on the Google column: its routing internals have never been published, so those cells are inference from observed behaviour rather than documented fact, and the customisable-route-planning work itself came out of Microsoft Research and is documented as shipping in Bing Maps. Saying that out loud is worth more in an interview than asserting an architecture nobody outside Google has seen.

There is one dominant algorithm here rather than a menu of comparable options, and the way to present it is as a ladder: start with the textbook answer, measure why it fails, and climb until something meets the budget. Each rung buys an order of magnitude and charges for it in a different currency — memory, preprocessing time, or flexibility — and the last rung is chosen not because it is fastest but because it is the only one compatible with §2's traffic requirement.

Rung 1: Dijkstra, and the size of the problem

Dijkstra's algorithm explores outward from the origin in order of increasing distance, settling every node closer than the destination before it reaches it. On a road network that is a roughly circular region centred on the origin with the destination on its rim, so a cross-continent query settles something close to half the graph. On the 18-million-node Europe benchmark that is around nine million nodes, and the measured runtime is on the order of seconds — call it two, with a good priority queue and a warm cache.

Against a 40 ms server budget (§6), that is not a factor of two out. It is a factor of fifty. No amount of profiling recovers it.

Rung 2: search from both ends

Running a second search backwards from the destination and stopping when the two frontiers meet halves the radius of each circle. Because the explored area grows with the square of the radius, two circles of half the radius cover about half the area of one full circle — a factor of two, occasionally a little better. Useful, free, and nowhere near enough.

Rung 3: aim the search

A* adds a lower-bound estimate of the remaining distance to each node's priority, which stretches the explored region into an ellipse pointed at the destination. The obvious estimate — straight-line distance divided by the maximum speed limit — is a legal lower bound but a weak one, because on a fast-road network the ratio between straight-line distance and travel time varies enormously. The strong version, usually called ALT, precomputes exact distances to a few dozen well-chosen landmark nodes and uses the triangle inequality to derive much tighter bounds. That gets a continental query into the low hundreds of milliseconds.

Notice what just happened: the first genuinely large win required precomputation. From here on, every rung is a different answer to the question of what to precompute.

Rung 4: contraction hierarchies, and why they are not the answer here

Contraction hierarchies take the precomputation idea to its conclusion. Order every node by how “important” it is to shortest paths — a residential cul-de-sac is unimportant, a motorway junction is not — then remove nodes one at a time from least to most important. Each time a node is removed, check whether any path through it was the unique shortest path between two of its neighbours; if so, insert a shortcut edge carrying that path's total weight so no distance is lost. The result is the original graph plus roughly one shortcut per node, arranged so that every shortest path can be walked as an upward sequence followed by a downward one.

A query then runs bidirectionally and only ever moves up the hierarchy, which prunes the search to a few hundred nodes. Measured queries on the Europe benchmark are around a tenth of a millisecond — four orders of magnitude faster than rung 1, on the same graph, for the same answer.

So why is rung 4 not the answer? Because of one sentence in §2. The node ordering and every shortcut weight are functions of the metric. Which nodes are important depends on which roads are fast; what a shortcut costs depends on the travel time of the path it replaces. Change the speed of one motorway and the shortcuts through it are wrong. Rebuilding the hierarchy for a continental graph takes minutes. Traffic changes every minute. The two requirements are incompatible, and a candidate who stops at contraction hierarchies has built a routing engine that cannot use the traffic system they just designed.

Rung 5: separate the topology from the weights

The resolution is to split the preprocessing into a part that depends only on the shape of the graph and a part that depends on the weights, then make the second part cheap. This is the customisable-route-planning approach, and it is the one this design uses.

Partition the graph into cells of a few thousand nodes each, chosen so that as few edges as possible cross cell boundaries. The nodes sitting on those boundaries are the only ones that matter for travel between cells. Build an overlay graph whose vertices are exactly those boundary nodes. It carries two kinds of arc: one between every pair of boundary nodes in the same cell, standing for the best path through that cell's interior, and the original road arcs that cross a cell border, which are what let a search move from one cell to the next. That structure — which cells exist, which nodes are on their borders, which overlay edges exist — depends only on topology, and is built once per map release.

The weights on those overlay edges are a different matter: each one is the shortest-path distance between two boundary nodes through the interior of one cell. That does depend on the metric, and recomputing it is embarrassingly parallel, because each cell's interior can be searched independently of every other cell. That step is customisation, and for a continental graph it completes in about a second across a modest number of cores.

A query now runs bidirectionally over a mixed graph: real edges inside the origin's cell, then overlay edges to skip whole cells at a stride, then real edges again inside the destination's cell. It settles a few thousand nodes instead of a few hundred, so it lands at one to two milliseconds where contraction hierarchies land at a tenth of one. That is the price, and against a 40 ms budget it is a price worth paying — 2 ms of a 40 ms budget buys the entire traffic system.

def route(src, dst, metric):
    # metric: the per-edge weight array published by customisation (§7)
    src_cell, dst_cell = cell_of[src], cell_of[dst]

    def edges_from(v):
        # inside the endpoint cells, walk the real road graph
        if cell_of[v] in (src_cell, dst_cell):
            yield from road_edges(v, metric)
        if is_boundary[v]:
            # jump boundary-to-boundary across a whole cell interior...
            yield from overlay_edges(v, metric)
            # ...and take the real arcs that cross into the next cell
            yield from cut_edges(v, metric)

    fwd = Dijkstra(src, edges_from)
    bwd = Dijkstra(dst, edges_from, reverse=True)
    best, meet = INF, None
    while fwd.min_key() + bwd.min_key() < best:      # standard meeting condition
        side = fwd if fwd.min_key() <= bwd.min_key() else bwd
        v = side.settle_next()
        if fwd.seen(v) and bwd.seen(v) and fwd.dist[v] + bwd.dist[v] < best:
            best, meet = fwd.dist[v] + bwd.dist[v], v
    return unpack(meet)                # expand overlay edges into real roads

A routing API is a query engine, not a CRUD surface, and the useful way to think about its design is the same way you would think about a search API: what can the caller express, what can they tune about the ranking, and what are they promised about how current the answer is. That last one is unusual and it is where most designs are weakest — a route is a prediction, and a prediction with no stated vintage cannot be reasoned about by the caller.

The request

Endpoints are GET for cacheability at the edge where it helps, but the directions call is a POST because a multi-waypoint request does not fit comfortably in a query string and, as §8 explains, it is not cacheable anyway.

POST /v1/directions

{
  "origin":      { "lat": 37.7955, "lng": -122.3937 },
  "destination": { "place_id": "ChIJ_id_of_a_known_place" },
  "waypoints":   [ { "lat": 37.8078, "lng": -122.4177 } ],
  "optimize_waypoint_order": false,

  "mode": "driving",                    // driving | walking | cycling
  "departure_time": "now",              // "now" | RFC 3339 timestamp, future only
  "traffic_model": "best_guess",        // best_guess | optimistic | pessimistic
  "alternatives": 2,                    // 0-2 beyond the primary route
  "avoid": ["tolls", "ferries"],        // tolls | ferries | highways | unpaved
  "units": "metric",
  "language": "en-GB"
}

Three of those fields carry more design weight than the rest. departure_time must accept a future timestamp, because the ETA machinery in §6 is time-dependent and a query about tomorrow morning is answered from historical profiles rather than live speeds — a system that only understands "now" has hard-coded an assumption it will later have to unpick. traffic_model is the ranking knob: it selects which quantile of the predicted travel-time distribution is reported, and exposing it is what lets a calling application be conservative about a flight connection without the routing service having to guess its risk appetite. optimize_waypoint_order is the trap — it turns a shortest-path query into a travelling-salesman problem, which is why §10b treats it as a separate, tightly-quota'd cost class.

The response

200 OK

{
  "routes": [
    {
      "summary": "I-80 W",
      "distance_m": 14820,
      "duration_s": 1140,               // free-flow / historical baseline
      "duration_in_traffic_s": 1685,    // what the user is actually told
      "confidence": 0.86,               // see freshness, below
      "polyline": "ogtcF~lfhVe@...",    // encoded, ~6 bytes per point
      "warnings": ["Toll road"],
      "legs": [
        {
          "distance_m": 14820, "duration_in_traffic_s": 1685,
          "steps": [
            { "instruction": "Head west on Bryant St",
              "distance_m": 210, "duration_s": 48,
              "maneuver": "depart", "polyline_range": [0, 12] }
          ]
        }
      ]
    }
  ],
  "traffic_as_of": "2026-09-17T14:03:11Z",
  "map_version": "2026-09-a",
  "status": "OK"
}

Both duration_s and duration_in_traffic_s are returned, and returning only the second one is a mistake worth avoiding: the difference between them is the congestion signal, and clients use it to draw the red line on the map and to decide whether a delay is worth notifying about. polyline_range indexes into the route's polyline rather than repeating geometry per step, which matters because a long route has thousands of points and duplicating them per instruction roughly doubles the payload.

The freshness contract

This is the part specific to a prediction service. traffic_as_of states when the speed data behind this answer was last updated, and confidence states how well-observed the route was — derived from how many of its edges had live speeds from enough contributors versus how many fell back to historical profiles. A route across a motorway at rush hour is densely observed; the same route at 04:00 through a rural area is not, and a caller that treats both ETAs as equally trustworthy will mislead its users.

The contract is explicitly not a guarantee of currency. It is a statement of vintage, which is the honest thing a system with §2's two-minute loop can offer. When the traffic pipeline is degraded (§10), traffic_as_of simply goes stale and confidence falls; the API does not fail, and callers who care can notice.

Errors, and what they mean

The rest of the surface

The dominant path is a user tapping Directions. What makes it worth tracing step by step is that the part everyone talks about — the graph search — turns out to be the cheapest thing in it, and the parts nobody mentions in interviews are where the budget actually goes.

The steps

Snap. Both endpoints are coordinates; the graph search needs nodes. The spatial index returns candidate road segments within a radius, and the snap picks one — ideally using the device heading, because a coordinate on a divided highway is metres from both carriageways and picking the wrong direction produces a route that begins with an infuriating U-turn. The destination is snapped differently: a caller wants the entrance to the building, not the nearest point of tarmac, which is why place ids carry an explicit access point when one is known.

Search. The overlay search from §5, run bidirectionally against the current metric. Two milliseconds.

Unpack. The path contains overlay edges that skip whole cells; each is expanded into the real road segments it stands for, producing the few hundred to few thousand edges the user will actually drive.

Evaluate the ETA. This is the step that is usually skipped in interviews and it is the second-largest block on the bar. Walk the unpacked edges in order, maintaining a running predicted clock, and for each edge look up the speed at the time you are predicted to reach it — live speed for the first few minutes of the trip, blending into the historical profile for that road at that hour and day for everything beyond. Add turn costs and signal delay, which for an urban route is a substantial fraction of the total and is invisible if you only sum edge lengths over speeds.

Alternatives. Generated by re-running the search with penalties applied to the edges of the route already found, then rejecting candidates that overlap it by more than a threshold or are more than a set fraction slower. Two alternatives cost slightly more than two extra searches because the overlap filtering is itself work, which is why the bar shows 9 ms rather than 4.

Instructions. Turning an edge sequence into "keep left to stay on I-80" requires road names, junction geometry, sign text and lane data — none of which was in the search graph (§3). It is a second pass over the path against a different dataset, and it is the reason the routing service is not quite as slim as the 4.6 GB figure suggests.

The other flow: how a traversal becomes a weight

Running continuously underneath is the loop that produced the speeds the ETA step just read. It has the same shape as the route path — a search problem wrapped in a data problem — but it never faces a user, which is what lets it be slow enough to be accurate.

A device in motion uploads a batch of positions. Each position is a coordinate with several metres of error, which in a city is enough to be ambiguous between a road, the service road beside it, and the one underneath it. Map matching resolves that ambiguity for the whole trace at once rather than point by point, and the standard formulation is a hidden Markov model: the hidden states are candidate road segments, the emission probability of a candidate falls off with its distance from the observed point, and the transition probability between consecutive candidates compares the driving distance between them against the straight-line distance between the two observations. Viterbi then finds the most likely sequence of segments.

Match each point to its nearest road independently and you get traces that teleport between parallel roads, and every one of those teleports becomes a fictitious traversal at an impossible speed. The joint formulation is what makes the transition term able to reject them.

Matched traces yield per-segment traversal times. Those are aggregated over a window, filtered for the minimum-contributor threshold of §10b, compared against the historical profile to reject implausible excursions, and written into the live-speed array of §7. Customisation picks the array up and re-weights the overlay. Total loop time: the two minutes of §2.

The entities are unremarkable — nodes, edges, road attributes, speeds, tiles — and listing them teaches nothing. What decides the model here is the enormous gap between how often each one is read and how often it is written, so the access patterns come first.

The first row is derived, not assumed: an overlay query settles on the order of three thousand nodes (§5), each node has about 2.3 outgoing edges (§3), and there are roughly 158 thousand route computations a second (§3) — call it seven thousand edge relaxations per query and a little over a billion a second across the fleet. Only the edge-weight reads it drives are in the same league; every other row in the table is two to three orders of magnitude below it.

Two observations force the entire model. First, the thing that is read a billion times a second is never written online. Road topology changes on a weekly release cadence, so it can be compiled into a form optimised purely for reading — no indirection, no locks, no query planner, no rows. Second, the weights on that structure change every minute while the structure itself does not. Keeping them in the same object would mean rewriting the object to change a speed. Keeping them apart means a speed update is an array swap.

The search graph

Stored as a compressed adjacency structure: one array of per-node offsets and one array of edges sorted by tail node, so a node's outgoing edges are a contiguous slice. This is the layout the 8-bytes-per-edge and 4-bytes-per-node constants in §3 describe.

// Topology — immutable for the life of a map release, memory-mapped read-only
offsets   : uint32[num_nodes + 1]   // edges of node v are [offsets[v], offsets[v+1])
edge_head : uint32[num_edges]       // the node each edge points at

// Metric — one array per routing profile, hot-swapped by customisation
overlay_w : uint32[num_overlay_edges]   // what customisation computes and publishes
weight    : uint32[num_edges]           // decisec; derived on the replica from live_kph
                                        // and the profile. UINT32_MAX = impassable

// Live speeds — the only thing the traffic loop writes
live_kph  : uint8[num_edges]        // 0 = no live data, fall back to the profile

A closure is UINT32_MAX rather than a removed edge, which is what lets §2's minutes-not-weeks requirement ride the fast path: reopening the road is another array write, and no topology was ever touched.

live_kph at one byte per edge is 495 MB for the whole planet at §3's defaults — small enough to hold densely rather than as a sparse map, even though only a minority of edges ever carry live data. The dense form is worth its extra memory because it makes a lookup a single indexed read with no branch, on the hottest path in the system, and because publishing a new one is a pointer swap that readers cannot observe half-applied.

Most systems have one caching story. This one has two, pointing in opposite directions, and the interesting half is the side where caching does not work — because the resolution there is what most of §5 was about.

Tiles: about as cacheable as anything gets

A tile's content depends on nothing but its coordinates and the map version. Every user looking at the same square of the world at the same zoom gets byte-identical data, the version is in the URL, and the object is therefore immutable forever. That is half of §3's 97% edge hit rate. The other half is demand: a metro's working set is a few thousand tiles that everyone there requests, and immutability is what lets the edge keep them. Over a uniform draw from 107 million objects the same immutable keys would miss almost every time — which is exactly the argument that kills the route cache below.

Two design choices do the heavy lifting. The corpus stops at zoom 14 and clients overzoom: because vector tiles carry geometry rather than pixels, a client showing zoom 18 renders from the zoom-14 tile it already has, scaled up. Without that, the pyramid would need zoom levels 15 through 22, and since each level has four times the tiles of the one below, a pyramid to zoom 22 is on the order of 10¹³ tiles. Vector tiles do not make the map prettier; they make the corpus finite.

And because the version is in the path, a map release never invalidates anything. The new version populates the edge gradually as users request it, the old version stays valid and servable throughout, and a rollback is pointing clients back at the previous version string. An in-place tile update would instead invalidate tens of millions of objects at once and send the miss rate — and therefore origin load — through the roof for hours.

Routes: a response cache would be pointless

Caching route responses fails on the key space, and the arithmetic is quick. Even after snapping, an origin-destination pair is drawn from 150 million nodes, so there are on the order of 10¹⁶ possible pairs. Add departure time, travel mode and avoidance options as part of the key, and add the fact that the answer legitimately changes every minute as traffic moves, and the achievable hit rate is indistinguishable from zero. A cache in front of the directions API would consume memory to serve stale answers to nobody.

Smaller things around the edges do cache conventionally, and they are worth naming because together they account for a meaningful slice of the §6 budget:

The last row is the one with a real tradeoff rather than a free win: it is a cache whose contents are invalidated wholesale every minute by customisation, so its value depends entirely on whether a corridor is hot enough to be re-requested many times inside one traffic window. In dense metros it is; in rural regions it is not, and it is reasonable to enable it per region rather than globally.

§3 established that routing compute is small — a few hundred cores for the planet — and §4 established that the graph is replicated rather than sharded. Between them they dispose of the scaling question most candidates prepare for. Adding routing capacity is adding identical machines, there is no hot shard, and there is no rebalancing.

The scaling problem that actually exists is distribution: getting a freshly customised metric onto every replica in every region, once a minute, without saturating anything. That is the deep dive.

Sizing the overlay, and therefore the update

Work it through from §5's structure. At three thousand nodes per cell, a 150-million-node graph has about fifty thousand cells. A cell of that size in a near-planar graph has on the order of fifty boundary nodes, and the overlay holds one edge per ordered pair of them — about 2,450 per cell, so roughly 122 million overlay edges in total. That is reassuringly close to the one-shortcut-per-node constant §3 used for the memory estimate, which is a useful consistency check to perform out loud.

The same decomposition gives the customisation cost. Each cell needs one search per boundary node, confined to that cell's three thousand interior nodes — call it half a millisecond each, so 25 ms per cell, so about 1,250 core-seconds for the planet. On 1,250 cores that is the one second quoted in §5, and the number of cores is a dial rather than a constraint because cells are perfectly independent.

At four bytes per weight, a full overlay metric is roughly 490 MB. Publishing that to every routing replica every minute is where the design has to be careful.

This system degrades unusually well, and knowing exactly how is most of the answer. Almost every input has a previous version that remains servable, so the dangerous failures are not the ones where something stops — they are the ones where something keeps going while being wrong.

The threats here are specific to a system that is publicly readable, expensive to query, and built from data its users generate by moving around. That last property is the one with no analogue in most system design questions, and it is where the strongest answers go.

Traffic data poisoning

The routing metric is computed from device-reported positions, which makes it an input an attacker controls. This is not hypothetical: in 2020 an artist walked a handcart of 99 borrowed phones, all running Google Maps navigation, slowly down empty Berlin streets, and the streets turned red — the system inferred a traffic jam from a cart. It was a stunt with no victim, and it is a clean demonstration of the attack. The version with a victim redirects traffic away from a business, or towards a road an attacker wants congested.

The defences are statistical rather than cryptographic, and they compound:

• A minimum contributor threshold. A segment's live speed is only published if at least k distinct devices traversed it in the window, with k in the low tens. Below that, the historical profile stands. This alone raises the cost of the handcart attack by an order of magnitude.
• Per-device contribution caps. One device contributes at most one observation per segment per window, and devices are weighted down when their traces are implausible — physically impossible accelerations, positions inconsistent with the cell tower or the reported accuracy, several devices moving in unnaturally tight formation.
• A deviation clamp. A segment's speed may not move more than a bounded fraction from its historical profile in one window. Real congestion builds over minutes and is admitted; a step-change to a walking pace on an empty motorway is rejected and alerted on.
• Device attestation. Raising the cost of a synthetic fleet by requiring probe uploads to come from attested app installations. This raises the bar without ever being decisive on its own — the Berlin attack used ordinary phones running the real app.

L5 asks how the handcart is stopped. L6 asks who is trusted to report a closure, and what happens when a mapping authority's feed is wrong. L7 asks how you would detect a coordinated campaign across a city rather than a single anomalous segment, which is a different problem: correlated anomalies across adjacent segments look exactly like real congestion, and the signal that separates them is the contributing device population, not the speeds.

Location privacy and retention

The probe pipeline ingests 20.7 TB a day (§3) of where people are. A sequence of positions from a single device is among the most identifying data any consumer system holds — a commute identifies a home and a workplace, and those two points identify a person — so the design question is how quickly the raw form stops existing.

• Rotating pseudonyms. The identifier on a probe batch is not a stable device id and is rotated frequently, which limits how long a single trace can be. It is a mitigation rather than a solution: rotation does not prevent linking traces by where they start and end.
• Aggregate early, discard the input. The output of the pipeline is a speed per segment per window, with no device attribution. Raw traces have a short retention measured in hours to days — long enough to reprocess after a matcher bug, not long enough to be a history.
• The k-threshold does double duty. The minimum contributor count that blocks poisoning is also what makes the published aggregate non-identifying: a speed derived from one vehicle on a rural lane at 04:00 is that person's journey. One mechanism, two unrelated threats.
• Separate the product from the pipeline. A user's own saved location history is a distinct system with distinct consent, retention and deletion semantics. Conflating it with the traffic pipeline is a compliance error and an architectural one, because deleting a user's history must not require recomputing historical traffic.

Scraping and cost-of-abuse

The map is the asset, and every API response gives away a piece of it. A patient scraper issuing valid requests can reconstruct road geometry, travel times and place data, and no request in that campaign looks anomalous on its own. Detection is behavioural — systematic spatial coverage, grid-shaped query patterns, request volume with no corresponding map rendering — and the response is graduated: quota, then degradation, rather than a block that simply teaches the scraper to spread out.

The sharper operational problem is cost asymmetry, from §5b. A tile is served from an edge cache; a directions call is a millisecond of CPU; a 25 × 25 distance matrix is fifty searches feeding a 625-cell merge; an isochrone is a search that cannot terminate early. A quota that counts requests makes the expensive calls effectively free, so quotas are weighted by cost class, and the weights are published so callers can budget rather than discover the limit by hitting it.

The ladder in §5 is also the level ladder, which makes this question unusually legible to an interviewer. Each rung corresponds to noticing something the previous rung missed, and the gap between L5 and L6 is almost entirely the moment of realising that preprocessing and live traffic are in conflict.

Classic probes, and how the answers differ by level

Latency: the numbers that set the budget