Transit Tracker

The problem

"Design a live transit tracker." Riders open an app to see where their bus or train is and when it will reach their stop, live.

This practice problem reuses the pattern of Design Uber: vehicles send positions every few seconds, and the latest position per vehicle is kept in memory, overwritten on each report. Four things are new: few vehicles write but many riders read, arrival times must be predicted for every stop, riders follow a stop or a route, and a vehicle that goes quiet must not fool anyone. Park tickets and trip planning across routes.

The numbers

From the interviewer: 3,000 buses and trains at rush hour, each reporting every 10 seconds, and 1 million riders with the app open. Say each rider watches a stop with about 3 vehicles on their way, and a trip has about 20 stops left on average.

what          working                        result
reports in    3,000 ÷ 10 s                   300 a second
per rider     3 vehicles × 1 every 10 s      0.3 a second
updates out   1 million × 0.3                300,000 a second
latest kept   3,000 × 100 bytes              300 KB
gateway       1 million ÷ 100,000 streams    10 servers

The reads are 1,000 times the writes, the other way round from Uber. Two common slips: 300 a second forgets that each report reaches every rider watching the stops ahead, and 30 million multiplies by the 10 seconds instead of dividing. The writes are so few that every report can be kept: 300 × 100 bytes × 86,400 s ≈ 2.6 GB a day, and those past reports are what arrival times are learned from.

Arrival times: the segments ahead at typical speeds

Split each route into segments between stops. Bus 12 reports at 8:00:20, 0.6 km before Bank, with 1.2 km more from Bank to Ana's stop, Main St:

segment          length   typical speed   time
bus 12 → Bank    0.6 km   18 km/h         2 min
Bank → Main St   1.2 km   24 km/h         3 min
total            1.8 km                   5 min, at 8:05

As in Google Maps' segment speeds, each segment has a typical speed for each hour, here learned from the vehicles' own past reports: last week's 8:00 buses took 4.5, 5 and 5.5 minutes for the 1.5 km from Park, the stop before Bank, an average of 5 minutes, 18 km/h. The timetable says 8:04, but it's a plan that can't see traffic. One moment's speed is worse: at a red light, 0 km/h means never; a moment later at 40 km/h, the 1.8 km take under 3 minutes.

Reaching riders: once per report, a channel per stop

Uber's rider searched the map cells around her; here Ana follows a stop, and the vehicles heading there are known from their routes. Since writes are few, the work goes on the write side: on each report, the ETA service works out the times at the stops ahead, 300 × 20 = 6,000 a second, and publishes each on its stop's channel.

Each rider's app keeps one server-sent events stream to a gateway, as in Live Sports Scores, naming what it follows, such as GET /stream?stops=main-st&routes=12. The gateway servers subscribe to those channels, and each update is copied once per server, then once per rider:

data: {"stop": "main-st", "route": "12", "arrives": "8:05:20", "live": true}

Asking every 10 seconds would mean 100,000 boards a second, worked out again and again for riders at the same stops, and up to 10 seconds late. One channel for the whole city would send every app all 300 reports a second: 300 million messages a second, 1,000 times as many.

What to follow: a stop, a route, or neither

• A stop's channel: arrival times at that stop for every route, for a rider waiting there or checking a departure from her desk.
• A route's channel: the positions of its vehicles, for the map, or for a dispatcher watching for bunched buses.
• No channel: timetables and which routes stop where change a few times a year: plain requests, answered from a cache.

Stale data: scheduled after 2 missed reports

Reports go missing: a tunnel, a weak signal, a broken GPS unit. Bus 12 reports at 8:00:20, then nothing at 8:00:30 or 8:00:40:

time      report   missed   Main St board
8:00:20   yes      0        12 Downtown 5 min
8:00:30   no       1        12 Downtown 5 min
8:00:40   no       2        12 Downtown 8:04 scheduled, no live data

One miss is common, so the board keeps the live time; after two, it shows the timetable's time marked "scheduled", with a warning. A quiet bus is usually still running, so taking it off the board would send riders away, and counting down its last live time would show "due" for a bus that may have broken down. The location store keeps each vehicle's last report time, and a sweep over the 3,000 vehicles finds the quiet ones. The next report brings the live time back.

Same pattern as Uber

Vehicles sending positions every few seconds and the latest position per vehicle in an in-memory store, overwritten on each report, carry over. What changes is the direction of the load: 300 writes a second fit one server easily, while 300,000 updates a second go out, so the effort goes into the fan-out.

Summary

• Scope: live positions and arrival times; follow a stop or a route.
• Data: latest positions in memory; typical speeds per segment and hour; past reports kept.
• API: a report every 10 s per vehicle; one stream per app, naming what it follows.
• Numbers: about 300 reports in and 300,000 updates out a second.
• Scale: a channel per stop and per route; times worked out once per report.
• Arrival times: the segments ahead at their typical speed for the hour.
• Following: a stop's channel, a route's channel, or a plain request.
• Stale data: after 2 missed reports, "scheduled" with a warning.