Design Google Maps

Do the numbers before the boxes

An interviewer gives a scale, not a load. Maps has three loads, route computations, GPS fixes and map tiles, and they differ by up to 80 times.

A 45-minute version of this answer is at the end.

We assume about 30 million daily users in North America, and 7.2 million navigation sessions a day of about 20 minutes. All our estimates.

7.2M x 20 = 144M navigating minutes a day. 144M / 1,440 minutes = 100,000 devices navigating at once on average.

The rush hour runs at twice the average: 200,000 devices at the peak.

A route computation is a new route or preview, or a re-check of a trip in progress.

About every 100 s a navigating phone sends its position. The server recomputes the rest of the trip, with a fresh arrival time.

New routes and previews: 3 a session, 21.6M a day, 250 a second. Re-checks: 100,000 / 100 s = 1,000 a second.

So 1,250 route computations a second on average, 2,500 at the peak.

Each navigating phone also takes a GPS fix a second: one reading of position, speed, heading and accuracy. That is 100,000 fixes a second on average, 200,000 at the peak.

Every user sees the map: about 150 map tiles a day each. 30M x 150 = 4.5B tile requests a day, 52,083 a second, about 104,000 at the peak.

Google reports Maps is used by over 2 billion people a month worldwide (Alphabet, October 2024). Our figures are for North America.

Out of scope: finding a place by name, which is the search autocomplete page. Transit and walking use other graphs, with the same algorithms.

Check in: Close the page and derive the three peak rates.

Route on a graph held in memory

A route is a search over every road between two points. Before any boxes, decide what that search runs on.

The routing graph has a node for each intersection and an edge for each road segment between two. Each edge carries a travel time.

A-star, written A*, is a shortest-path search. It grows outward from the start, trying first the intersections whose time so far plus an estimate of the time remaining is lowest.

The estimate never overstates the time remaining, so A* still finds the fastest route while exploring less than a blind search.

In one city, A* visits thousands of intersections. Across a continent it visits millions, and that is the problem this page solves.

Live traffic is the current travel time on each road segment, measured from navigating phones. Routing prices each edge with it, so the fastest route moves with the jams.

The ETA, the estimated time of arrival, is the sum of the travel times along the route.

Each routing server keeps the whole graph in memory. A route reads thousands of segments, and a database round trip for each would take seconds.

Step through the figure to watch A* search.

The trade-off:

Every routing server holds a full copy of the graph, so memory, not CPU, can decide its size. In exchange, a search never waits on a network.

A* on the road graph

1. The routing graph: a node for each intersection, an edge for each road segment. Each edge carries a travel time.
2. A* grows from the start, trying first the intersections whose time so far plus an estimate of the rest is lowest. In one city it visits thousands.
3. Across a continent the same search visits millions of intersections. That is Stage 2's problem.

Check in: Why not keep the road graph in a database and query it during the search?

Reading the result tiles

Each stage has a live canvas and four result tiles. On this page "tiles" also means map tiles, so we call these "result tiles".

Load: the buttons count route computations per second on Stages 1 to 3, and GPS fixes per second on Stages 4 and 5. The result tile labels both req/sec.

A part saturates when it gets more work than it can serve. A card turns red at 90% of its limit; only past 100% does the result name it.

With nothing saturated, the last result tile notes the busiest part instead.

Latency is server time on the slowest path, without the phone's round trip. When a saturated part sits on that path, the tile shows a floor, such as "≥ 1.60s".

The real figure is then higher, by an amount no model can know.

Cost: each card bills its peak load for the whole month. A real fleet follows the daily curve, so the bill beat uses the average month.

The cost tile also bills the answers sent back to phones, per GB after 100 GB a month free. Data coming in, such as GPS fixes, is free.

Where a card reads differently from AWS, the stage that shows it says so.

Check in: Stage 1's latency tile reads 53ms. Is that what a user waits for a route?

A* on an in-memory graph, at launch

Stage 1 is the launch: one metro region, about a tenth of North America. That is 125 route computations a second on average, 250 at the peak.

The phone calls the navigation API through a load balancer, an ALB (AWS's application load balancer).

The API reads the trip's row, asks a routing server for the route, and writes the row only when something changed.

The routing service runs on ECS, AWS's container service, using Fargate: AWS runs the containers. Each task is a container with its own vCPUs and memory.

A vCPU is one virtual processor. Each routing task has 4 vCPUs and 16 GB, and holds the region's graph in memory: about 1M intersections, a few GB.

A* takes about 50 ms of CPU a route in one metro (our estimate). So each vCPU finishes 20 routes a second, a task 80, and 6 tasks 480.

The pool is fixed at 6 tasks, 2 in each of 3 availability zones: separate data centres within one AWS Region.

At 250 a second: 250 / 480 = 52.1%. Nothing saturates; the note reads "Busiest: Routing service at 52%".

The Trips database is Aurora, AWS's managed PostgreSQL, with a writer and one reader. Writes go to the writer, reads to the reader.

Every computation reads its trip's row once. A new route also writes once.

A re-check writes only when the driver takes a faster route: at most about 1 in 16, a generous upper estimate.

A fifth of computations are new, so writes are 0.2 + 0.8 / 16 = 0.25 a computation. That is 1.25 statements a computation, 80% of them reads.

A 2-vCPU instance serves 4,000 statements a second at 0.5 ms each, our CPU model. Real throughput also depends on connections and, for writes, commit latency.

Here the reader takes 250 reads a second and the writer 62.5 writes.

The latency tile shows 53ms: 1.5 + 1 + 50 = 52.5 ms.

The load balancer card's 1.5 ms includes 0.5 ms for TLS, the connection's encryption: a convention, since a held connection pays almost nothing.

The cost tile shows $1,873/mo. Of that, $258 is route answers sent to phones, at $0.09 a GB after the free 100 GB.

A route answer is about 4 KB. A trip keeps one connection for about 400 s (our estimate): its first route and 4 re-checks.

Opening it costs a 4 KB TLS handshake, mostly the server's certificates. Shared over 5 answers, that adds 0.8 KB: 4.8 KB an answer.

Press 125, the daily average: the note reads "Busiest: Routing service at 26%", and the cost tile shows $1,723/mo.

The trade-off:

A fixed pool pays for its spare all day. In exchange, no rush hour waits for a task to load the graph.

Stage 1: A* on an in-memory road graph, at launch

• Load: 250 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $1,873/mo

Check in: Why is the routing pool fixed, when the API scales with load?

A* across the continent

The interviewer asks: We launch across North America.

Stage 2 serves all of North America with the same A*, at 2,500 route computations a second at the peak. Some trips cross the continent.

The continent's graph is about 50M intersections and 120M road segments: about 40 GB with its indexes, in 64 GB tasks (our estimate).

A compute card checks CPU, not memory, so the 64 GB is our choice for the graph. The card would run it on any size.

A* now explores far more of it. A short trip still takes tens of ms; a cross-continent one takes seconds. On average, about 400 ms of CPU (our estimate).

Each 16-vCPU task finishes 16 x 1,000 / 400 = 40 routes a second. The fixed pool of 40 tasks, sized for an average day, finishes 1,600.

At the peak, 2,500 against 1,600: the Routing service saturates. Its warning reads "Fargate 16vCPU-64GB ×40 at 100% of a fixed 40-task ceiling".

The card caps at 100%; the load is 2,500 / 1,600 = 156% of what it finishes.

Nothing is refused. Queries queue in the tasks and time out.

Past 70% busy, a card's latency climbs, to 4 times its base at full use.

The latency tile shows "≥ 1.60s", a floor: 1.5 + 1 + 400 x 4 = 1,602.5 ms. The real wait is longer.

The cost tile shows $30k/mo. Stage 2 has no load buttons: its point is the peak.

At the average, 1,250 a second, the pool runs at 78.1%. It works on an ordinary afternoon and fails every rush hour.

At a 70% target each task holds 28 routes a second. The peak would need 2,500 / 28 = 89.3, so 90 tasks, about $60,400 a month.

A cross-country route would still take seconds.

The trade-off:

A* spends CPU in proportion to the map it explores. A continent multiplies the work, and more tasks only buy more of it.

Stage 2: A* across the continent

• Load: 2,500 req/sec
• First to saturate: Routing service
• Estimated cost: $30k/mo

• Latency past saturation is a lower bound, not an estimate. Routing service is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Routing service: Fargate 16vCPU-64GB ×40 at 100% of a fixed 40-task ceiling.

Check in: Why not 90 tasks?

Precompute what every search shares

At 2,500 routes a second x 0.4 s, A* keeps 1,000 vCPUs busy. Every search explores the same highways again.

Precomputing every route is impossible: 50M intersections make 2.5 quadrillion pairs.

Contraction hierarchies take a middle way. Offline, they rank intersections by importance and add shortcut edges that skip the minor ones.

A query climbs from both ends onto ever more important roads until the two searches meet. It touches a few thousand nodes, not millions.

Plain contraction hierarchies bake the travel times into the shortcuts. Re-contracting with the old order takes minutes on a continent: too slow on every task, every minute.

Customisable route planning splits the build. A weight-free structure is built offline, in minutes to hours, and rebuilt only when the map changes.

Every minute, each task re-weights it with live traffic times, a few seconds of work.

Bing Maps' CRP gave the family its name. OSRM, an open-source router, has MLD, multi-level Dijkstra, named after the classic shortest-path search.

Both use overlay graphs: the map cut into regions, with precomputed costs across each region.

Customisable contraction hierarchies, CCH, use shortcuts instead; we describe our tasks that way. Google publishes no engine.

With 3 alternatives, the route unpacked into its roads, the turn list and the ETA, a query takes about 5 ms of CPU (our estimate).

The searches are the smaller part. That is 80 times less CPU than A*, and milliseconds instead of seconds.

Step through the figure to follow one query.

The trade-off:

An offline build, rerun when the map changes, more memory for the structure, and a re-weight every minute on every task. In exchange, a query costs milliseconds.

Customisable route planning

1. Offline, once: the structure adds shortcut edges that skip minor intersections. It holds no travel times, so traffic cannot invalidate it.
2. Every minute, each routing task fills in the shortcuts' times from live traffic. That takes a few seconds.
3. A query climbs from both ends onto ever more important roads until the two searches meet. It touches a few thousand nodes.
4. With 3 alternatives, the turn list and the ETA, a query takes about 5 ms of CPU: 80 times less than A*.

Check in: Why not plain contraction hierarchies with live traffic?

Customisable route planning, re-weighted with live traffic

Stage 3 keeps the same 2,500 route computations a second and changes only the algorithm. The routing card's 400 ms becomes 5 ms.

Each 16-vCPU task now finishes 16 x 1,000 / 5 = 3,200 routes a second; 6 tasks finish 19,200. At the peak the Routing service is at 13.0%.

2,500 x 5 ms = 12.5 vCPUs busy. The pool is still 6 tasks, 2 a zone, sized by memory and zones, not CPU.

The pool buys 96 vCPUs to keep 12.5 busy, because a 64 GB task comes with 16 vCPUs on the card.

At 13%, the floor of 2 a zone already covers rush hour, so this pool needs no schedule.

The Navigation API runs 4 tasks at 62.5%. The Trips database is at 62.5% too: 2,500 reads against the reader's 4,000.

The writer takes 2,500 x 0.25 = 625 writes a second, 15.6%.

Nothing saturates. The cost tile shows $7,582/mo, against Stage 2's $30k that could not keep up.

Answers to phones are $2,564 of it, the same as on Stage 2: a faster search changes the work, not the replies.

On the server a route is a chain: read the trip (0.5 ms), route (5 ms), and write only if something changed. With the load balancer and the API, about 8 ms.

The tile runs the read and the route in parallel, so it shows 8ms: 1.5 + 1 + 5 = 7.5 ms.

A phone sees about 60 to 160 ms. That is a mobile round trip of 50 to 150 ms on a connection it holds (our estimate), plus about 8 ms.

A new connection adds one to three more round trips. That is one with QUIC (the transport under HTTP/3), two with TCP and TLS 1.3, three with TLS 1.2.

In all, a new connection adds 50 to 450 ms.

Press 1,250, the daily average: routing 6.5%, the database 31.3%, and the cost tile $6,077/mo. The note names the Navigation API as busiest.

Press 4,750: the Wednesday before Thanksgiving, 1.9 times the usual rush-hour peak. The result names the Trips database.

The latency tile still reads 8ms there, because the tile runs the database in parallel with the route. Really, statements queue on the database until they time out.

The Routing service is at 24.7% there, far from any limit. That preset is your turn, at the end of the page.

The trade-off:

The pool is sized by memory, so most of its vCPUs sit idle. In exchange, 6 tasks carry the peak at 13%, with a zone to spare.

Stage 3: Customisable route planning, re-weighted with live traffic

• Load: 2,500 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $7,582/mo

Check in: A zone fails at the peak. What happens to routing?

Arrival times and rerouting

A route chosen at 5 pm can be wrong by 5:20 pm, when a jam forms ahead. The arrival time must track it.

The ETA sums each segment's time. Live times are used for the next stretch, and the usual time for that hour of the week further on.

A learned correction from past trips adjusts the total (not on the canvas).

Routes, though, are chosen on current times for the whole trip. Choosing them on predicted times is time-dependent routing, a likely follow-up question.

Customisable engines can carry a time profile for each segment, at more memory and CPU. We do not size it.

About every 100 s the phone sends a re-check with the trip id and its position. The server reads the trip's route, recomputes the rest, and returns the new arrival time.

It offers a faster route only if it saves at least a few minutes, and writes the trip only when the driver takes it. The position is used, not stored.

Why read the row at all? The server re-plans against the route it issued, read from the trip row, rather than against one the phone uploads.

A fully stateless re-check, with the phone sending its whole route, is also sound. It trades the read for about 2 KB of upload a re-check.

If the phone leaves the route, it sees that itself and asks at once for a new one.

A sudden closure is pushed to the phones in the area, and each checks it against its own route (not on the canvas). The server does not search the trips for it.

Re-checks are 1,000 of the 1,250 computations a second on average, 80% of routing work. The interval is the largest lever on routing load.

Segments with no recent trace use their usual time. Stages 4 and 5 build the live times.

The trade-off:

Re-checking every trip costs most of the routing CPU. In exchange, a jam ahead changes the arrival time within a few minutes, with no push for every jam.

Check in: What would re-checking every 50 s do to routing load?

The navigation chain on one screen

Skip on a first read; come back before the interview. Every number on Stage 3 comes from the one before it, at the 2,500 peak.

Computations: 500 new routes and previews + 2,000 re-checks = 2,500 a second.

Load balancer: 2,500 calls a second. An LCU is its billing unit, and one covers 25 new connections a second.

The card assumes 0.6 new connections a call, for billing only: 2,500 x 0.6 / 25 = 60 LCU.

At $5.76 an LCU-month ($0.008 an hour): $16.20 + 60 x $5.76 = $361.80.

Navigation API: each 1-vCPU task serves 1,000 calls a second at 1 ms, 700 at its 70% target. 2,500 / 700 = 3.57, so 4 tasks, $142.19.

Routing: 2,500 x 5 ms = 12.5 vCPUs busy. 6 tasks by memory and zones, $4,026.93.

Statements: 2,500 x 1.25 = 3,125 a second. The reader takes 2,500, 62.5%; the writer 625, 15.6%. The two instances cost $486.72.

Sizes here are binary: a KiB is 1,024 bytes, and a GiB is AWS's billed GB.

Answers: 2,500 a second x 4.8 KiB, with the handshake share, about 29,700 GiB in a 30-day month.

After the free 100 GiB, 10,240 bill at $0.09 and the rest at $0.085: $2,564.06.

Total: $7,581.70 a month at the peak, the tile's $7,582.

Check in: Close the page and rebuild the chain from 2,500 computations to the reads on the reader.

Every GPS fix sent and stored alone

The interviewer asks: Traffic needs location from every navigating phone.

The page turns to location. Stages 4 and 5 count GPS fixes per second, not route computations: 200,000 at the peak.

In this design the phone sends each fix as it is taken. The location API matches it to a road, stores it, and adds its speed to that road.

Map matching is snapping GPS positions to the roads a vehicle drove. A lone fix snaps to the nearest road, often the wrong one where roads run close.

Fixes go to a probe archive: the traces of navigating phones, the probes, kept 30 days to learn usual times and train the ETA correction.

Each fix carries a trip token: a random value the phone makes for each trip, never the device or the account. A user's own timeline stays on the phone.

The archive is a DynamoDB table, AWS's key-value database. Live traffic is in Valkey, an in-memory store.

At 200,000 fixes a second: 200,000 calls, 200,000 archive items and 200,000 speed updates.

The Location API runs 286 tasks at 69.9%, and the load balancer is at 66.7%. Neither turns red.

The load balancer's 66.7% is against the card's own ceiling, 100,000 requests a second a zone, not an AWS limit. An ALB scales with traffic, so read its card for cost only.

The archive card counts write units: one per item under 1 KB, so one per fix here. Its warning reads "Write capacity 500% used (on-demand)": 200,000 against 40,000.

The Probe archive saturates. 40,000 writes a second is AWS's default for one table; the next beat asks whether to raise it.

The latency tile shows a plain 3ms: 1.5 + 1 = 2.5 ms, with the writes behind the API. Really, throttled writes are retried, and with nothing to hold them, many fixes are lost.

The cost tile shows $385k/mo. About $8,080 of it is the acknowledgements sent back. The fixes coming in are free.

Each acknowledgement is about 0.2 KB (our estimate). A trip's connection carries about 400 fixes, so the 4 KB handshake adds 0.01 KB: 0.21 KB.

The Live traffic card is a store of counters, not a cache. It takes 200,000 commands a second, one speed update a fix.

A cache.r7g.large node runs 160,000 commands a second, so this design needs a cache.r7g.xlarge, which runs 348,000: 200,000 / 348,000 = 57.5%.

Press 100,000, the daily average: the warning reads 250%, still named, and the cost tile shows $200k/mo.

The trade-off:

Every fix is a call, an item and a guess at its road. That grows with the fixes, not with what traffic needs.

Stage 4: Every GPS fix sent and stored alone

• Load: 200,000 req/sec
• First to saturate: Probe archive
• Estimated cost: $385k/mo

• Probe archive: Write capacity 500% used (on-demand): 200000 of 40000 WCU/s at 200000 RPS.

Check in: Why does a lone fix make a poor traffic reading?

Raise the limit, or batch?

The 40,000 writes a second is not a law of DynamoDB. It is the default for one table, and AWS raises it on request.

A new table in on-demand mode, billed per write, starts lower. It sustains up to 4,000 writes a second, and takes double its previous peak at once.

Raising the limit fixes the card, not the design. Every fix would still be a call: $27,664 of load balancer, $10,166 of API and $8,080 of acknowledgements, on the tile.

Every fix would still be an item. At AWS's current $0.625 a million writes, that is $324,000 a month at the peak held all month, $162,000 at the average.

Lone fixes would still match wrong roads. Their instant speeds overstate a jam's speed, because stop-and-go traffic averages its moving moments.

And the radio would never sleep. It stays in its high-power state for several seconds after each send, so sending every second keeps it there.

The radio is the part of the battery the design controls; the screen and GPS cost more while navigating.

Batching answers all four: 15 times fewer calls and items, whole traces to match, and a radio that sleeps between sends.

The trade-off:

Batching delays each fix by up to 15 s before it leaves the phone. Live traffic works by the minute, so that delay is small next to it.

Check in: Why not just raise the table's limit?

Batch on the phone, match whole traces

The phone still takes a fix a second. The change is when it sends them, and what the server does with 15 at once.

While navigating, the phone sends its last 15 fixes every 15 s, about 0.7 KB, and keeps them until the server acknowledges them.

Open but not navigating, it sends every minute or so. In the background it sends nothing unless the user shares a trip, and parked, nothing.

The location API checks the credential, drops the device id, and puts the batch on a Kinesis stream: an ordered log, kept 24 hours.

A stream is split into shards; each takes 1,000 records a second. A record's key picks its shard, and one key's records stay in order.

The key is the trip token. A trip's batches stay in order, and 200,000 trips spread evenly over the shards.

The map matcher reads the stream and snaps each 15-second trace to the roads driven. It holds the road graph in memory.

It uses a hidden Markov model, which picks the likeliest sequence of roads given every fix in the trace. That takes about 4 ms of CPU a batch (our estimate).

It turns the matched trace into traversal times: the seconds each road segment took. A segment cut by the batch's end joins the trip's next batch, which the trip key sends to the same shard.

Each batch becomes one archive item and about 3 segment times for live traffic: a 15-second trace crosses about 3 segments (our estimate).

Step through the figure to follow one batch.

The trade-off:

A stream, a matcher fleet and up to 15 s of delay on the phone. In exchange, 15 times fewer calls and items, and roads matched from whole traces.

One GPS batch, from phone to traffic

1. The phone takes a fix a second and sends the last 15 every 15 s. It keeps them until acknowledged.
2. The location API checks the credential and drops the device id. The batch becomes one stream record, keyed by the trip token.
3. The map matcher snaps the whole 15-second trace to the roads driven, then turns it into the seconds each segment took.
4. Each batch becomes one probe archive item and about 3 segment times for live traffic.
5. As each minute closes, a snapshot of current times reaches every routing task. A time arrives about 48 s later on average.

Check in: Why key the stream by trip token, and not by road segment?

Batched on the phone, streamed, matched as traces

Stage 5 carries the same 200,000 fixes a second, sent 15 at a time.

Calls: 200,000 / 15 = 13,333 a second, 15 times fewer. The Location API runs 20 tasks at 66.7%.

The Location stream has 20 shards, 20,000 records a second, so 13,333 runs it at 66.7%.

Each 16-vCPU matcher task matches 16 x 1,000 / 4 = 4,000 batches a second, 2,800 at its 70% target. 13,333 / 2,800 = 4.76, so 5 tasks.

The Probe archive takes 13,333 writes against its 40,000, 33.3%. Live traffic takes 13,333 x 3 = 40,000 commands a second.

On a cache.r7g.large that is 40,000 / 160,000 = 25%. Batching lets Live traffic run on a node one size smaller than in Stage 4.

Nothing saturates. Three cards sit at 66.7%: the Location API, the stream and the matcher.

The latency tile shows 3ms: 1.5 + 1. The API also waits for the stream before it answers the phone, tens of ms more, so no batch is lost.

The cost tile shows $33k/mo, against Stage 4's $385k that could not keep up. The archive's writes are $21,600 a month of it.

The acknowledgements are $1,023 of it. A trip's 400 s holds 400 / 15 = 26.7 batches, so each carries 4 / 26.7 = 0.15 KB of handshake: 0.35 KB.

Batching cut the calls 15 times but the acknowledgement bytes only 9 times, since each batch carries a larger share of the handshake.

The matcher scales with load, though a new task loads the graph for minutes. The stream holds the batches meanwhile, so traffic is a few minutes late and nobody waits.

Routing cannot wait, so its pool stays fixed.

A shard is read by one task at most, so 20 shards allow 20 tasks. One shard is 667 batches a second x 4 ms = 2.7 vCPUs busy.

That is more than one thread can do. So a task spreads each shard over its cores by trip token, keeping each trip in order.

On launch day the table is new and starts at 4,000 writes a second, under the 13,333 peak.

Set its warm throughput, a rate the table is ready for in advance, to the peak before phones switch over.

Press 100,000, the daily average: the stream at 33.3%, the API 10 tasks, the matcher 3, and the cost tile $19k/mo.

The trade-off:

A firehose of tiny writes is cheap only in batches. Batch on the device, stream the batches, and store once a batch.

Stage 5: Batched on the phone, streamed, matched as traces

• Load: 200,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $33k/mo

Check in: Why a stream between the API and the matcher?

From traces to traffic times

Routing needs a travel time for every busy segment, refreshed every minute. Instant speeds from single fixes cannot give it honestly.

Live traffic keeps, for each segment and minute, the sum of traversal times and a count. Speed is the segment's length over the mean time.

Unlike averaging instant speeds, this does not overstate a jam's speed.

A time is known only once a vehicle leaves the segment. So a jam that is still forming shows only as vehicles leave it.

A segment's time is used only once a few vehicles have reported, for accuracy and privacy.

As each minute closes, a small job reads that minute's times and publishes a snapshot. Each routing task downloads it and re-weights.

The snapshot is about 8 MB: about 1M touched segments x 8 bytes, a 4-byte segment id and a 4-byte time.

Segments with no recent trace use their usual time for that hour of the week.

A time reaches routing about 48 s later on average. That is 7.5 s in the batch, 30 s for its minute to close, and about 10 s to match, publish and re-weight.

At worst it is about 85 s: 15 + 60 + 10.

A jammed freeway has many vehicles on one segment, but the stream is keyed by trip, so their batches spread. The segment takes a few updates a second.

The trade-off:

Traffic lags by under a minute on average. In exchange, every time comes from whole traces, matched to the roads actually driven.

Check in: Why store a sum of traversal times and a count, not an average of speeds?

Pseudonymous probes, trimmed at both ends

The probe archive holds a trace of every navigated trip for 30 days. Kept carelessly, that is a map of where each user lives and works.

The interviewer will ask how the design keeps it from being one.

Pseudonymous means keyed by a value that names no one. That alone is not enough: a trace that starts at a house points to the house.

First, the token. The device id stops at the location API; the stream, the matcher, the archive and live traffic see only the trip token.

The server stores no token with a device, an account or a trip row. The archive is keyed by token and the batch's time.

Second, the two ends. The phone knows the trip's origin and destination, and sends nothing within a few hundred metres of either: 300 m, our estimate.

At about 8 m/s on residential streets that is about 75 s of a 20-minute trip, about 6% of its fixes. The cards still count them, so their batch rates are about 6% high.

Third, the backstop. Many trips stop short of the destination, or the app dies, so the phone's own trimming never starts.

The matcher holds each trip's last 3 minutes, 12 batches, back from the archive. It drops them on the final batch or after 3 minutes of silence, never releasing them.

If the driver stops short, the archive's trace ends about 1.4 to 2.7 km before the stop: 3 minutes at 8 to 15 m/s.

The held batches take about 1.7 GB across the matcher fleet: 200,000 trips x 12 x 0.7 KB.

Live traffic is not held back, so it stays fresh. A trip that loses signal mid-route loses up to 3 minutes of archive, never of traffic.

Step through the figure to follow one trip's ends.

The trade-off:

The archive loses each trip's ends, and sometimes its last 3 minutes. In exchange, it keeps no trip's first or last few hundred metres.

Pseudonymous probes, trimmed at both ends

1. The phone sends nothing within about 300 m of the origin or the destination: about 6% of a 20-minute trip's fixes.
2. The device id stops at the location API. Everything after it sees only the trip token, a random value made for each trip.
3. A driver may stop short of the destination. So the matcher holds each trip's last 3 minutes, 12 batches, back from the archive.
4. On the final batch, or after 3 minutes of silence, the held batches are dropped, never released. Live traffic already has their times.

Check in: A driver navigating across town stops 2 km short of the destination and closes the app. What reaches the archive?

Who reads the archive

A pseudonymous store is only as private as its readers. Name each one, and what it can look up.

Nightly jobs read a copy in S3, AWS's object storage. They fold each day into every segment's usual time for each hour of the week, and train the ETA correction.

S3 Standard objects cannot be appended to, so the matcher buffers its batches and writes one object every 5 minutes (not on the canvas).

The usual managed path from a stream to S3 is Amazon Data Firehose. We use the matcher because the copy holds matched traces with segment times, which Firehose would need a transform to compute.

A lifecycle rule deletes the copy's objects after 30 days. Because the jobs fold traces into averages, raw traces need not outlive that.

In the table, a time-to-live, an expiry DynamoDB enforces, deletes items in the background, typically within a few days of expiry. So a raw item lives 30 days plus a few.

The table answers lookups by token, which only the phone holds. The phone sends it with a report of a bad route, at the user's request, on a signed-in call.

That report is the one link between a token and an account. It keeps the token and the route, not the account.

A user's own timeline is opt-in and lives on the phone, with an optional encrypted backup. Google began doing this for Maps Timeline in 2024, announced in December 2023.

Trip rows in the Trips database are deleted a day after arrival.

Say it out loud: "Traffic and the archive use pseudonymous trip tokens; the device id stops at the API. Each trip's ends are dropped, and aggregates need a few vehicles."

The trade-off:

Bulk readers get a cheaper copy, and lookups need the user's help. In exchange, no reader can ask for a person's trips.

Check in: Support wants every trip a user made last week. What can the system give them?

The location chain on one screen

Skip on a first read; come back before the interview. Every number on Stage 5 comes from the one before it, at the 200,000 peak.

Sizes on this page are binary: a KiB is 1,024 bytes, and a GiB is AWS's billed GB.

Fixes: 200,000 devices x 1 a second = 200,000.

Calls: 200,000 / 15 = 13,333 a second. The load balancer bills 13,333 x 0.6 / 25 = 320 LCU: $16.20 + 320 x $5.76 = $1,859.40.

Location API: 13,333 / 700 = 19.05, so 20 tasks, $710.93.

Records: 13,333 on 20 shards, 66.7%. $216.00 of shard-hours plus $483.84 of records, $699.84.

Matching: 13,333 x 4 ms = 53.3 vCPUs busy; 5 tasks, $3,355.78.

Archive: 13,333 items a second, $21,600 of writes, plus $3,218.75 of storage. In all $24,818.75.

The storage is 30 days at the average: 17.28B items x 800 bytes, with DynamoDB's 100 bytes an item, is 12,875 GiB at $0.25.

Segment updates: 13,333 x 3 = 40,000 commands a second, on 2 cache.r7g.large nodes, a primary and a replica.

Valkey costs 80% of the Redis OSS price: 0.8 x $0.219 an hour x 720 hours x 2 nodes = $252.29.

Acknowledgements: 13,333 a second x 0.35 KiB, with the handshake share, about 11,500 GiB a month.

After the free 100 GiB, 10,240 bill at $0.09 and the rest at $0.085: $1,023.23.

Total: about $32,720 a month at the peak, the tile's $33k.

The holiday peak, 1.9 times the rush hour, sends about 380,000 fixes a second: 25,333 batches against the stream's 20,000.

Reshard to 37 shards ahead, to stay under 70% each. The API and the matcher scale within their maximums.

The archive takes it at once: 25,333 writes is under double its previous peak.

Each shard is read by one task, which saves a checkpoint: how far it has safely got. The task keeps each trip's cut segment and held batches in memory.

If a shard moves to another task as the fleet scales, the new task replays from the checkpoint and rebuilds that state. Live traffic counts those minutes twice, which barely moves a mean.

A replay can also write a batch into a second S3 object, so the nightly jobs drop repeats on token and batch time.

A reshard is different: a trip's new shard may go to a task with no state. Each trip in progress then loses one segment time and up to 3 minutes of archive, once.

So reshard at night, the week before. Keeping the state in Valkey would cost 2 commands a batch, 26,667 a second, to avoid that one loss.

Check in: Close the page and rebuild the chain from 200,000 fixes to the matcher's task count.

Map tiles, priced by hand

Every user sees the map, navigating or not: 4.5B tile requests a day. Tiles are static files behind a cache, so their cost is arithmetic.

A vector tile is a square of map data for one area: roads, labels and shapes as geometry. The phone draws it, so a new map style needs no rebuild.

A zoom level sets the tile size. Zoom 0 is the whole world in one tile, and each level splits every tile into 4.

A zoom-16 tile is about 611 m across at the equator, less further north. North America takes about 156M tiles at zoom 16.

Zoom 0 to 16 is about 200M tiles, most of them small rural ones.

Many tile sets stop at zoom 14: about 13M tiles for zooms 0 to 14 together, and about 9.75M for zoom 14 alone.

The phone then draws zoom-14 tiles larger, called overzoom.

Tiles are built offline, rebuilt where map data changes, and given new versioned names. So caches can keep them for a long time.

They sit in S3 behind CloudFront, AWS's CDN: a content delivery network that caches files at edges near users.

At about 20 KiB a tile (our estimate), the peak is about 104,000 tiles a second, about 17 Gbps. That is under CloudFront's default 150 Gbps and 250,000 requests a second for one distribution.

A month is 135B requests. Less 10M free, at $1 a million, that is $134,990.

The bytes are 135B x 20 KiB, about 2.57M GiB: about $78,800 through CloudFront's volume tiers.

At 20 KiB, requests cost more than bytes: $1 a million requests, against about $0.59 a million tiles at the $0.03 tier.

At a flat $0.03 a GB the two would cross at about 35 KiB a tile. With the price tiers re-applied at the larger volume, they cross at about 37 KiB.

City tiles, which take most requests, can be that big.

Either way, fewer, larger requests cut the bill. A 512-pixel tile covers four 256-pixel tiles: about a quarter of the requests for about the same bytes.

Traffic colours are a separate small layer. A route's answer carries a congestion level for each stretch; browsing fetches traffic tiles rebuilt each minute (not priced).

Step through the figure to climb the zoom levels.

The trade-off:

Every tile request is billed, whatever its size. So the tile scheme, not the servers, sets most of this system's bill.

The tile pyramid

1. Zoom 0 is the whole world in one tile. Each zoom level splits every tile into 4.
2. Zoom 1 has 4 tiles and zoom 2 has 16. The count grows 4 times at each level.
3. A zoom-16 tile is about 611 m across at the equator. North America takes about 200M tiles for zoom 0 to 16.
4. Many tile sets stop at zoom 14: about 13M tiles for zooms 0 to 14. The phone draws them larger, which is overzoom.
5. At 20 KiB a tile, requests cost more than bytes. At this volume the two cross at about 37 KiB a tile.

Check in: At 20 KiB a tile, which costs more: the requests or the bytes? When does that flip?

Map tiles are the bill

Skip on a first read; come back before the interview. The canvases show servers. Most of this system's money is map tiles.

The bill is an average month at AWS prices, unlike the canvases, which bill the peak all month.

Map tiles: about $214,400 a month at list. Requests $134,990, bytes about $78,800, misses to S3 about $540, storage under $90.

Misses assume about 1% of requests reach S3 (our estimate), since requests concentrate on city tiles.

The nodes on the canvases come to about $22,100 at the average. The probe archive is about $14,000 of it: $10,800 of writes plus $3,218.75 of storage.

Answers sent back to phones, with their handshake shares, add about $1,790: about 20,600 GiB, mostly route answers.

The canvases bill each load balancer per new connection, the card's assumption. Phones really hold one open, so the bill prices held connections.

An LCU also covers 3,000 open connections: 100,000 phones / 3,000 = 33.3 LCU, about $208 each.

Navigation holds its connections only if the idle timeout is raised past the 100-s re-check, from its default of 60 s.

The S3 copy of the archive adds about $259.

All lines: about $238,600 a month. Map tiles are 89.9%, location 7.6%, navigation 2.6%. Tile requests alone are 56.6%.

At the average, Stage 4's location chain would cost about $187,500 a month, 10.5 times Stage 5's $17,800.

Its load balancer bills its largest dimension, processed bytes: 171.7 LCU, $1,004.97.

The routing pool buys 96 vCPUs to keep 12.5 busy. A Fargate task of 8 vCPUs and 60 GB would cost about $2,551 for 6.

Memory-optimised EC2 hosts, AWS's virtual machines, with 8 vCPUs and 64 GiB: about $1,851 for 6, against $4,026.93 on the canvas.

List prices are an upper bound: at this volume CloudFront prices are negotiated.

The trade-off:

Map tiles are the bill. Cut requests first: larger tiles, overzoom and the phone's own cache.

Check in: What are the two largest lines, and what shrinks each?

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

A zone fails: 2 of 6 routing tasks go, and 4 still serve 12,800 routes a second against the 2,500 peak.

A routing task restarts: it loads the graph for up to about 10 minutes, and the others carry the load. That is why the pool has spare.

The traffic snapshot stops: routes use the last times, then the usual times. An alarm watches the snapshot's age.

The matcher falls behind: batches wait in the stream, which keeps 24 hours. Live traffic skips records older than its 10-minute window; only the archive back-fills.

The location API is slow: phones keep their batches and retry. Nothing is lost unless a phone's buffer fills.

The trips writer fails over: saves fail for about 30 s. Routes still answer, and the phone retries the save.

us-east-1 is lost: new routes and re-checks fail, and traffic freezes. The phone keeps guiding on its route and cached tiles; a second Region with a warm routing pool takes new routes.

A map data release: segment ids stay stable across releases, and new roads get new ids. So live times, the archive and trips in flight survive; routing tasks swap graphs one at a time.

At 100 times, 20M phones navigate at once. 1.33M batches a second need about 1,905 stream shards and 477 matcher tasks.

The archive would take about $1.08M a month of writes. Packing a minute of a trip into one item cuts write units only a quarter, so the archive moves to S3 alone.

Routing needs about 1,250 busy vCPUs. The world's graph, about 200 GB (our estimate), sits at the edge of Fargate's largest task, 244 GB.

So: memory-optimised hosts of several hundred GB, or the graph split into regions with a highway layer, each served by its own pool.

Tiles cost about $21M a month at list, so they move into caches inside ISPs, and the system spans many Regions.

Say it out loud: "Route on a precomputed graph re-weighted every minute. Batch location on the phone, match whole traces, and key everything by a trip token."

Minutes 0 to 5: requirements, and three rates at the peak: 2,500 route computations, 200,000 fixes and about 104,000 tiles a second.

Minutes 5 to 15: Stages 1 and 2. The graph in memory, A*, and why it fails across a continent.

Minutes 15 to 23: Stage 3. Customisable route planning with live traffic, the ETA and rerouting.

Minutes 23 to 33: Stages 4 and 5. Batching, the stream, map matching, the probe archive and traffic.

Minutes 33 to 40: map tiles. Vector tiles, the CDN, and requests against bytes.

Minutes 40 to 45: failures, privacy, and what changes at 100 times.

The trade-off:

Each answer has a price: a precompute step, a stream and a matcher are more to run than A* and one write a fix. They cost far less than the tiles.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.