Collect GPS data and show live traffic on a map

01The design, in the six-step framework

1. Requirements

Functional

• Phones running the maps app report their position while moving.
• Aggregate reports into a current speed for every road segment and colour the map (green, amber, red).
• Expose the speeds to routing so ETAs use them.
• Keep historical speed profiles per segment by time of day for prediction and fallback.
• Out of scope: incident reports from users, camera feeds, routing itself.

Non-functional

• 50 million phones reporting at peak, one report every 5 s.
• A segment's displayed speed reflects reports from the last 2 minutes; the map repaints within a minute of a change.
• Privacy: no individual's trajectory can be reconstructed from stored data; raw reports are deleted within minutes.
• Availability 99.9 percent; when the pipeline lags, the map falls back to historical profiles rather than showing nothing.
• Handle a 5x spike (a holiday evening) without dropping accuracy.

2. Core entities

• Location report: session_token, lat, lon, speed, heading, timestamp; held only for the aggregation window.
• Matched sample: segment_id, speed, timestamp, derived by map-matching; no identity.
• Segment speed: segment_id, minute, mean speed, sample count, confidence.
• Speed profile: segment_id, day of week, slot, typical speed.
• Traffic tile: zoom, x, y, version, rendered overlay.

3. API

• POST /reports: a batch of positions from the last 5 to 20 s, under a rotating session token. Called by the app.
• GET /tiles/traffic/{z}/{x}/{y}?v=…: the overlay tile; served by the CDN.
• GET /speeds?segments=…: current speed and confidence per segment. Called by routing.
• GET /profiles/{segment}: the historical profile. Called by routing for prediction.

4. High-level design

From a phone to a red road:

1. The app batches its last few positions and posts them under a session token that rotates every 15 minutes; ingest validates (plausible speed, timestamp skew) and appends them to a stream with a 30-minute retention.
2. The map matcher, a streaming job partitioned by geographic cell, snaps each position to the most likely road segment using the heading and the previous positions in the same session, then emits (segment, speed, time) with the identity dropped.
3. The aggregator keeps a sliding 2-minute window per segment, computes a trimmed mean and a sample count, and writes the live speed when the count passes a threshold; otherwise the segment keeps its profile value.
4. Every minute the tile renderer repaints overlay tiles for cells whose speeds changed colour band and publishes them under a new version; the app refreshes the overlay version every minute from the CDN.
5. Routing reads the same live speeds for ETAs; a nightly batch job folds the day's aggregates into the historical profiles.

5. Deep dives

How does map-matching work at 10 million reports a second, and why not just use the nearest road?

Nearest-road snapping puts a car on the wrong carriageway of a motorway or on a parallel service road, which corrupts speeds for both. The matcher keeps a short window of a session's positions and chooses the segment sequence that best explains them given headings and road connectivity, a small hidden-state problem per session. To make this parallel, reports are partitioned by the cell of their first position so one worker sees all of a session's points; the geospatial index of segments for that cell is loaded in the worker's memory. At 10 M/s with about 50 microseconds per match, the fleet is roughly 500 cores, plus headroom for the spike.

How is privacy enforced rather than promised?

The design treats privacy as a property of the data flow: there is no table anyone could query for a person's route, because that data does not exist after the matcher.

What happens when the pipeline falls behind?

If the aggregator lags, speeds grow stale. Each live speed carries its window end time; routing and the renderer treat a value older than 3 minutes as missing and fall back to the historical profile, so the map degrades to typical rather than wrong. Backpressure is applied at ingest by asking apps to report every 10 s instead of 5 s during an overload, which halves input with little loss of accuracy because the aggregation is over many cars per segment anyway. The stream's short retention bounds how far behind the job can get, and lag is the pipeline's primary alert.

Why render tiles instead of sending segment speeds to the client?

A viewport at city zoom contains tens of thousands of segments; sending speeds per segment to 100 million clients every minute is terabits per second of pointless repetition. Overlay tiles are small images or vector layers that the CDN serves at a very high hit rate, and only changed tiles are re-rendered. The client blends the overlay on the base map, so the base tiles stay cacheable for weeks while the overlay changes by the minute.

How are speeds kept honest against bad data?

A bus stuck at a stop reports zero on a free-flowing road; a phone in a train reports 120 km/h on the road beside the track. The trimmed mean removes extremes, the matcher rejects speeds that are impossible for the segment's class, and a sample is weighted by how well its session matched the road. A segment also needs reports from several sessions, not one, before its speed is published, which is the same rule that protects privacy.

6. What a strong answer sounds like

• Say the shape: a stream pipeline whose stages are ingest, map-match, window-aggregate, publish, and that the output is small (800 MB live) while the input is huge (400 MB/s).
• Explain why map-matching is a sequence problem and how partitioning by cell makes it parallel.
• Describe privacy as enforced by the data flow, with retention and identity-dropping at specific stages.
• Expect follow-ups on how routing uses live versus predicted speeds, on the minimum sample count, and on how you would validate accuracy (compare predicted and actual trip times).
• A common mistake is to store every report in a database and compute speeds with queries; the data is obsolete before the query finishes.

02Where this question was reported

• IGotAnOffer · EM low-level list