Design Google Maps ETA

Advanced55 minBuilds Maps Routing and ETARead first: 25.3 Tracking moving objects, 21.3 Stream processing, 7.3 Keeping caches correct

STEP 1 OF 12

The brief

You are designing the backend that answers "how do I get there, and when will I arrive?" Users ask for a route between two points; the answer must reflect traffic right now, not yesterday's average. Phones in moving cars help: while navigating, each one reports its position and speed every few seconds.

How big it is

Route requests: 4,000 / second
Speed report batches: 4,000 / second
Drivers sending pings: about 20 million at rush hour
Freshness of speeds: about a minute
p99 goal: under 300 ms

Phones don't send each ping on its own: an ingestion edge batches them, so 4,000 requests a second carry millions of pings.

What makes it tricky

The graph is huge. A continent has hundreds of millions of road segments; a textbook shortest-path search over all of them takes seconds.
Weights change constantly. A crash turns a 2-minute segment into a 20-minute one, and the route should notice within a minute.
Two loads collide. Route queries are CPU heavy and latency bound; speed reports are a write firehose that peaks at rush hour, exactly when routing peaks too.

All changes saved

0 components · 0 connections

A blank canvas. A better system.

Add components from the palette, then drag between them to connect the request and event flow.

React Flow

Design Google Maps ETA

Advanced55 minBuilds Maps Routing and ETARead first: 25.3 Tracking moving objects, 21.3 Stream processing, 7.3 Keeping caches correct

STEP 1 OF 12

The brief

How big it is

Route requests: 4,000 / second
Speed report batches: 4,000 / second
Drivers sending pings: about 20 million at rush hour
Freshness of speeds: about a minute
p99 goal: under 300 ms

Phones don't send each ping on its own: an ingestion edge batches them, so 4,000 requests a second carry millions of pings.

What makes it tricky

The graph is huge. A continent has hundreds of millions of road segments; a textbook shortest-path search over all of them takes seconds.
Weights change constantly. A crash turns a 2-minute segment into a 20-minute one, and the route should notice within a minute.
Two loads collide. Route queries are CPU heavy and latency bound; speed reports are a write firehose that peaks at rush hour, exactly when routing peaks too.

All changes saved

0 components · 0 connections

A blank canvas. A better system.

Add components from the palette, then drag between them to connect the request and event flow.

React Flow