Strava

The problem

"Design Strava." People record runs and rides on their phones, often with no signal, and upload each activity when they stop. The app shows the ride's map and races everyone on segments: popular stretches of road, each with its own leaderboard.

This practice problem reuses two patterns: GPS positions and map cells from Design Uber, and the sorted set from the Top K Leaderboard. What's new: a whole track uploaded at the end, the segments found in each ride, a board per segment, and privacy zones. Park the feed of friends' rides and live tracking.

The numbers

From the interviewer: 10 million activities uploaded a day, each about an hour long with a GPS point every second. Say a point packs into about 30 bytes (time, latitude, longitude, elevation) and a summary row takes about 500 bytes. Round a day to 100,000 seconds (86,400 really).

• One track: 3,600 points × 30 bytes = 108,000 bytes, about 100 KB.
• Tracks: 10 million × 100 KB ≈ 1 TB a day, about 400 TB a year, 1.2 PB with 3 copies.
• Summary rows: 10 million × 500 bytes = 5 GB a day, about 200 times less (sizing each point as a 500-byte record would give 18 TB).
• Uploads: 10 million ÷ 100,000 s = about 100 a second, about 500 at busy hours (5×).

The track: a file and a row

record     what it holds
activity   id, athlete_id, start_time, title, distance, moving_time, climb, track_key
track      a file under track_key: time, lat, lng, elevation per point

A track is always read whole, to draw the map or match segments, never one point at a time. So each track is one file in object storage, about 100 KB, and the activity's summary row keeps its key next to the numbers that lists and totals need. The phone sends POST /activities with the file and an id it made for the ride, so a retry after a lost signal doesn't save it twice (Idempotency Keys).

A row per point would be 36 billion rows a day, 360,000 writes a second; say one database server takes about 5,000, and that's over 70 servers for points nobody reads one at a time. Keeping only the summary fails the other way: no map, and nothing to match segments against.

Matching segments: off a queue

After an upload, split the work at the moment the phone hears "saved":

• Before answering: store the track file, save the summary row, put a match job on a queue. The phone may delete its copy once it hears "saved", so the ride must be safe first; the queued job promises the rest.
• Later, off the queue: match workers read the track, look up the segments in the map cells it crosses (as Uber finds drivers by cell), check that it passes each one's start, path and end, time each effort, update the boards, and notify the athlete of a best time.

Matching inside the upload request would make the phone wait seconds for a long ride, and a burst after a big race would tie up the upload servers. With a queue the burst waits a little, and a failed match is retried without failing the upload.

Segment leaderboards: a sorted set each

Each segment gets its own sorted set: one entry per athlete, scored by their best time in seconds, ranked lowest first. When a worker times Ana at 6:12 on Hawk Hill, where her best was 6:30 (372 seconds instead of 390), it replaces her entry and she moves from 4th to 3rd. A slower ride leaves the board alone: an "only if lower" update (Redis's ZADD has an LT option for exactly this).

Adding every effort as an entry would let one athlete fill the top with her own rides; replacing her entry with her latest time would drop her to last after an easy ride. Say 10 million segments hold 1 billion best times; at about 100 bytes an entry that's about 100 GB, split by segment id across a few in-memory servers.

Privacy zones: cut on the server

Ana's rides start and end at home, so she sets a privacy zone around it. Cut the points inside the zone on the server, from every copy sent to anyone but Ana, and keep her stored track whole: other phones never receive those points, matching still uses the full track, and if she moves the zone, old rides follow. A worker can write the cut copy once per upload.

Hiding them only in the app fails: the whole track still reaches every phone, and anyone reading the API's answer finds her home. Deleting them from the file loses part of her ride for good. Two more traps: an effort on a segment that starts or ends inside the zone shouldn't show on a public board, and a circle centered exactly on her door gives it away, since her rides all vanish on that circle. Move its center a little, at random.

Same pattern as Uber and the Top K Leaderboard

From Uber: positions from phones' GPS, and map cells that find what's near, here the segments near a track. Uber keeps only each driver's latest position; here every point is kept, as one file per ride. From the Top K Leaderboard: the sorted set, a rank in about log n steps and the top read off the front, here one per segment, scored by time.

Summary

• Scope: record, upload at the end, segments and their boards, privacy zones.
• Data: a 500-byte summary row; the track as a 100 KB file.
• API: POST /activities with the track file; GET /segments/{id}/board.
• Numbers: 10 million uploads a day, about 1 TB of tracks.
• Services: an activity service; match workers off a queue.
• Leaderboards: a sorted set per segment, one best time per athlete.
• Privacy zones: cut on the server from every copy others get.