Strava (Activity Tracking & Segment Matching)

Sharpened prompt. Design an activity tracking platform for 100M athletes uploading 5M activities/day, where each uploaded GPS trace is automatically matched against millions of user-defined route "segments," leaderboards update within seconds, elevation and distance are accurate enough to be trusted for training, home addresses are never revealed, and impossible efforts are caught before they top a leaderboard.

The distinctive problem here is geometric, not just geospatial: matching a noisy polyline of thousands of points against millions of stored polylines, fast enough to do it on every upload.

1. Problem framing

Functional requirements

• Upload a recorded activity (GPX/FIT/TCX) with GPS, heart rate, cadence, and power.
• Compute distance, elevation gain, moving time, and per-kilometre splits.
• Detect which user-created segments the activity traversed and time each effort.
• Maintain all-time, annual, and age-group leaderboards per segment.
• A social feed of friends' activities with kudos and comments.

Non-functional requirements

Property	Target	Consequence
Upload → processed	P95 < 60s	Async pipeline, with the user told it is processing
Segment matching	Complete within the same window	Candidate pruning is mandatory; naive comparison is impossible
Leaderboard freshness	Seconds	Sorted sets in memory, durable store behind
Privacy	Home and work locations never inferable	Geometry must be truncated, not just hidden in the UI
Data integrity	Cheating detectable before leaderboard entry	Validation is part of the pipeline, not an afterthought

Back-of-the-envelope

Activities:  5M/day = 58/sec avg, ~400/sec peak (Saturday morning, Europe)
File size:   2-10 MB FIT (1 Hz sensor data, a 3-hour ride ≈ 11,000 samples)
             5M × 4 MB = 20 TB/day raw -> S3, cold after 30 days
Points:      5M × 5,000 avg = 25 billion GPS points/day
Segments:    ~30M user-created segments globally
Matching:    naive = 25B points × 30M segments. Absurd.
             With R-tree bbox pruning: ~50-200 candidate segments per activity.
             That is a 150,000× reduction, and it is the entire trick.
Leaderboards: 30M segments × ~500 entries avg = 15B entries; hot subset in Redis

State the 150,000× pruning factor. It reframes an impossible problem as an indexing problem, which is exactly the move the interviewer is looking for.

2. High-level architecture

3. Component inventory

Component	Concrete choice	Why this one
Parser	Garmin FIT SDK / fitparse, in a worker pool	Binary FIT is compact but fiddly; parsing is CPU-bound and parallel
Spatial index	PostGIS GiST (R-tree) over segment bounding boxes, plus H3 cell tags	Bounding-box overlap is the cheap pre-filter that makes matching possible
Geometry	GEOS / Shapely, or a Rust/C++ inner loop	Fréchet and DTW are hot loops; a Python implementation will not keep up
Time series	TimescaleDB for recent, Parquet on S3 for archive	Streams are append-only, queried by range, and compress extremely well
Leaderboards	Redis sorted sets per segment, durable copy in Postgres	ZADD / ZRANK are O(log n); recomputing a ranking is not
Feed	Fan-out on write, capped	Follower counts here are modest; the Instagram celebrity problem barely applies

4. The toughest parts

4.1 Matching one trace against 30 million segments

Why it's hard. An activity is a polyline of ~5,000 points. A segment is a polyline of ~100 points. Comparing every activity to every segment is 25 billion point-comparisons per activity. Even comparing to every segment in the same country is far too many. And you cannot simply match on start and end points, because riders join a segment mid-way and GPS noise means the traces never coincide exactly.

Solution — a three-stage filter, each stage far cheaper than the next.

def match_segments(activity) -> list[Effort]:
    # STAGE 1 — bounding box overlap. R-tree query, sub-millisecond.
    # 30M segments -> ~200 candidates. This is the 150,000× reduction.
    bbox = activity.bounding_box().buffer(50)              # 50 m tolerance
    candidates = segment_rtree.query(bbox)

    # STAGE 2 — cell coverage. Does the activity actually pass through the
    # segment's cells, in order? Set intersection, microseconds each.
    act_cells = {h3.latlng_to_cell(p.lat, p.lng, 11) for p in activity.points}
    candidates = [s for s in candidates
                  if len(s.cells & act_cells) / len(s.cells) > 0.85]

    # STAGE 3 — true geometric match, only on the ~5-20 survivors.
    efforts = []
    for seg in candidates:
        sub = locate_subtrace(activity, seg)               # sliding window alignment
        if sub is None: continue
        if discrete_frechet(sub.points, seg.points) < 25:  # metres
            efforts.append(Effort(seg, start=sub.t0, end=sub.t1,
                                  elapsed=sub.t1 - sub.t0,
                                  moving=sub.moving_time))
    return efforts

Why Fréchet distance rather than something simpler. Hausdorff distance ignores ordering: an out-and-back route would match a one-way segment. Fréchet is the classic "dog walking on a leash" metric — it respects the order of traversal, so it only matches when the rider actually followed the segment's direction. Discrete Fréchet is O(n·m) with dynamic programming, which is fine for a 5,000 × 100 comparison done a handful of times.

Dynamic Time Warping is the alternative when speeds differ substantially (a walker versus a runner on the same path); it aligns sequences with different sampling rates. Fréchet is usually the better default for "did they ride this road" because it bounds the maximum deviation rather than the average.

locate_subtrace matters and is often overlooked: the rider's activity is 40 km, the segment is 2 km somewhere in the middle. Find the entry point by locating the activity point nearest the segment's start (within tolerance), then walk forward. Handle repeated efforts (hill repeats) by continuing the scan past the first match rather than stopping.

4.2 Saturday morning: 400 uploads/second of 5 MB files

Why it's hard. Uploads are extremely peaked — weekend mornings across Europe produce a spike far above the daily average. Each file needs parsing (CPU-heavy), cleaning, metric computation, and segment matching against an R-tree. Doing this synchronously means a 60-second HTTP request over a phone connection, which will fail.

Solution — accept fast, process asynchronously, and make every stage independently scalable and retryable.

# Upload endpoint: does almost nothing. Returns in under a second.
@app.post("/uploads")
async def upload(file: UploadFile, athlete: Athlete):
    upload_id = uuid7()
    key = f"raw/{athlete.id}/{upload_id}"
    await s3.put(key, file)                                 # direct, or presigned
    await kafka.send("activity.uploaded",
                     {"upload_id": upload_id, "athlete": athlete.id, "key": key})
    return {"upload_id": upload_id, "status": "processing"} # client polls or gets a push

# Pipeline stages as separate consumer groups: each scales on its own lag.
# parse (CPU) -> clean (CPU) -> metrics (CPU) -> match (CPU + R-tree) -> publish
#
# Stage isolation matters: segment matching is by far the most expensive stage,
# so it gets its own autoscaling group. Coupling it to parsing would over-provision
# cheap work to keep up with expensive work.

Three practical points. Autoscale on consumer lag, not CPU — lag is the leading indicator and CPU is the lagging one. Make each stage idempotent keyed by upload_id, so a redelivery reprocesses harmlessly. And publish progressively: show the athlete their distance and map as soon as metrics complete, with segment results appearing seconds later. Perceived latency is set by the first useful output.

Store the parsed stream columnar: a 3-hour ride is ~11,000 samples × 8 channels, which as Parquet with delta and RLE encoding compresses to a small fraction of the FIT file, and supports "give me the power curve" queries without reparsing.

4.3 Leaderboards over 30 million segments

Why it's hard. Every segment has an all-time leaderboard, a yearly one, per-age-group, per-weight-class, and a following-only view. A popular segment has 200,000 efforts. Recomputing a ranking on read is impossible; recomputing on write with a SELECT ... ORDER BY is nearly as bad.

Solution — Redis sorted sets keyed by the leaderboard dimension, with a durable copy behind.

async def record_effort(effort: Effort, athlete: Athlete):
    # Keep only an athlete's BEST effort per board: ZADD GT updates only if better.
    pipe = redis.pipeline()
    boards = [
        f"lb:{effort.segment_id}:all",
        f"lb:{effort.segment_id}:{effort.date.year}",
        f"lb:{effort.segment_id}:age:{athlete.age_group}",
        f"lb:{effort.segment_id}:gender:{athlete.gender}",
    ]
    for b in boards:
        pipe.zadd(b, {athlete.id: effort.elapsed}, lt=True)  # lower time is better
    await pipe.execute()

    # Durable copy for rebuild and for the long tail of cold segments.
    await pg.execute(
        """INSERT INTO efforts (segment_id, athlete_id, elapsed, activity_id, ts)
           VALUES ($1,$2,$3,$4,$5)
           ON CONFLICT (segment_id, athlete_id)
           DO UPDATE SET elapsed = LEAST(efforts.elapsed, EXCLUDED.elapsed)""",
        effort.segment_id, athlete.id, effort.elapsed, effort.activity_id, effort.ts)

# Rank lookup is O(log n); a page of the board is one command.
rank = await redis.zrank(f"lb:{sid}:all", athlete_id)
page = await redis.zrange(f"lb:{sid}:all", 0, 49, withscores=True)

The following-only leaderboard is the interesting case, because it is viewer-specific and therefore cannot be precomputed per segment. Compute it at read time by intersecting: ZINTERSTORE of the segment board with the viewer's following set — cheap when the following set is small (a few hundred), which it almost always is. For the rare athlete following 10,000 people, cap and approximate.

Memory is the constraint at 15B total entries, so only hot segments live in Redis. A segment with no effort in 90 days is evicted and rebuilt from Postgres on first access — a one-time cost of a few hundred milliseconds for a segment nobody is racing.

4.4 GPS and barometric noise: making the numbers trustworthy

Why it's hard. Athletes treat these numbers as training data, so systematic error is a product failure. Raw GPS drifts several metres even when stationary, which accumulates into phantom distance; a 30-second stop at a traffic light can add 50 m of "movement." Elevation is worse: consumer GPS altitude has 10–30 m of error, and naively summing positive differences turns noise into thousands of fictitious metres of climbing.

Solution — smooth, then threshold, and prefer barometric data corrected against a DEM.

def clean_track(points):
    # 1. Drop implausible fixes before they contaminate anything.
    pts = [p for p in points if p.hdop < 5 and p.satellites >= 4]

    # 2. Kalman filter over position and velocity: uses the fact that a human
    #    cannot teleport, so it smooths noise while preserving real movement.
    pts = kalman_smooth(pts, process_noise=0.5, measurement_noise=p.hdop * 3)

    # 3. Moving time: threshold speed, don't just diff timestamps.
    moving = sum(dt for p, dt in pairwise_dt(pts) if p.speed > 0.5)   # m/s

    # 4. Distance: sum only displacements above the noise floor.
    dist = sum(d for d in pairwise_haversine(pts) if d > 1.0)         # metres
    return pts, moving, dist

def elevation_gain(points, dem):
    # Barometric altimeter is far more precise than GPS altitude, but it DRIFTS
    # with weather. Correct the drift against a digital elevation model.
    if points[0].has_barometer:
        series = drift_correct(barometric(points), dem_sample(points, dem))
    else:
        series = dem_sample(points, dem)          # ignore GPS altitude entirely

    # Smooth, then apply a threshold: only count sustained climbs.
    series = savgol_filter(series, window=15, polyorder=2)
    gain, last = 0.0, series[0]
    for h in series:
        if h - last > 3.0:                        # 3 m threshold kills noise
            gain += h - last; last = h
        elif h < last:
            last = h
    return gain

Two points worth making explicitly. Ignore GPS altitude entirely — sample a DEM at the horizontal positions instead, which is both more accurate and consistent between athletes on the same route (two riders should get the same climb for the same hill; otherwise leaderboards are unfair). And the 3 m threshold is a policy decision, not a bug: without it, a flat ride accumulates hundreds of metres of noise gain, and with it, small real undulations are undercounted. Say that you would document the choice and keep it stable, because changing it retroactively changes everyone's historical totals.

4.5 Privacy zones: hiding where you live

Why it's hard. Most rides start and end at home. Publishing the raw trace publishes the athlete's home address — and this has caused real-world harm, including the well-documented case of aggregate heatmaps revealing the layout of military bases. Simply not displaying the first 500 m is insufficient, because the direction of travel and the geometry of the remaining trace let you extrapolate the start point precisely.

Solution — truncate the geometry server-side, with a randomised boundary, and apply it before the data leaves the processing pipeline.

def apply_privacy_zones(track, zones):
    for z in zones:                                # each: centre + radius (200-1000 m)
        # Randomise the actual cut radius per activity, so repeated activities from
        # the same home don't all end at the same circle — the intersection of many
        # identical circles reveals the centre.
        r = z.radius * random.uniform(1.0, 1.35)

        # Trim from the START: drop points until we are outside, then drop a few more.
        i = 0
        while i < len(track) and haversine(track[i], z.centre) < r: i += 1
        # Trim from the END symmetrically.
        j = len(track) - 1
        while j >= 0 and haversine(track[j], z.centre) < r: j -= 1
        track = track[i:j+1]

    # Metrics are computed on the FULL track (the athlete's own data is accurate)
    # but the PUBLISHED geometry is the trimmed one. Two different artefacts.
    return track

Three details that make this actually safe rather than theatrical:

• Randomise the radius per activity. Fixed-radius trimming across 200 activities gives an attacker 200 circle boundaries whose common centre is the home address. Randomisation defeats the intersection attack.
• Trim both ends and the middle. A loop that passes the house mid-ride must be cut there too.
• Separate the athlete's private metrics from the published geometry. The athlete should still see their true distance; only what leaves the account is truncated. Conflating the two either lies to the user or leaks to the world.

Also exclude segment efforts that start or end inside a privacy zone from public leaderboards, or the leaderboard reveals what the map hides.

4.6 Anti-cheat: the 90 km/h cyclist

Why it's hard. Leaderboards create an incentive to cheat, and it is easy: record a car journey and upload it as a ride, edit a FIT file's timestamps, or use a GPS spoofing app. A single fake effort at the top of a popular segment devalues the leaderboard for everyone, and community reporting is slow and unreliable.

Solution — physics-based plausibility checks in the pipeline, plus statistical outlier detection against the athlete's own history.

def validate(effort, athlete, activity) -> Verdict:
    reasons = []

    # 1. Hard physical limits by activity type. Cheap and catches the blatant cases.
    if effort.avg_speed > LIMITS[activity.type].max_sustained_speed:
        reasons.append("speed_implausible")
    if activity.type == "ride" and effort.avg_power_w:
        # Watts per kilogram above world-tour level, sustained: not a real effort.
        if effort.avg_power_w / athlete.weight_kg > 6.5 and effort.duration > 20 * 60:
            reasons.append("power_implausible")

    # 2. Personal outlier: 40% faster than the athlete's own best is suspicious.
    pb = athlete.best_on(effort.segment_id)
    if pb and effort.elapsed < pb * 0.60:
        reasons.append("personal_outlier")

    # 3. Signature analysis: cars accelerate and corner differently from bicycles.
    if acceleration_profile(activity).looks_motorised():
        reasons.append("motorised_signature")

    # 4. Data integrity: an unedited device file has a device signature and
    #    consistent sensor cross-correlation (cadence vs speed vs power).
    if not activity.has_device_signature or sensor_inconsistency(activity) > 0.4:
        reasons.append("file_integrity")

    if len(reasons) >= 2: return Verdict.FLAG_HIDE      # excluded from leaderboards
    if reasons:           return Verdict.FLAG_REVIEW    # visible, queued for humans
    return Verdict.OK

The design principle to articulate: require two independent signals before hiding an effort. A single check will produce false positives — a genuinely exceptional athlete, a tailwind, a new bike — and wrongly erasing a real personal best is a serious harm to the user. Two signals plus a human review queue balances integrity against fairness.

Also detect at the activity level, not just the effort level: someone who drove a route will trip checks on many segments at once, and that correlation is itself the strongest signal.

5. What breaks first

Event	First failure	Mitigation
Saturday morning peak	Segment-matching workers lag	Stage-isolated autoscaling on consumer lag; publish metrics before matches
A new segment is created in a dense city	Backfill against millions of past activities	Backfill asynchronously at low priority; new segments start empty and fill in
Popular event (a gran fondo)	One segment's leaderboard is written by 20k athletes at once	ZADD is O(log n) and Redis handles it; batch writes to Postgres
Redis leaderboard eviction	Cold segment rank lookups slow	Rebuild from Postgres on demand; cache the rebuild
Malformed or huge FIT file	Parser worker OOM	Size caps, streaming parse, per-file timeouts, poison-message quarantine
DEM service unavailable	Elevation wrong or missing	Fall back to barometric-only with a widened uncertainty flag; reprocess later

6. Cheat sheet

• The number: R-tree bounding-box pruning takes 30M segments down to ~200 candidates — a 150,000× reduction and the entire basis of the design.
• Matching: bbox (R-tree) → H3 cell coverage → discrete Fréchet on the survivors. Fréchet because it respects direction; DTW when speeds differ.
• Ingest: accept and return in under a second; stage-isolated Kafka pipeline; autoscale on lag; publish results progressively.
• Leaderboards: Redis sorted sets with ZADD LT for best-effort-only, durable copy in Postgres, ZINTERSTORE for following-only views, evict cold segments.
• Accuracy: Kalman-smooth positions, threshold distance and elevation, use a DEM rather than GPS altitude so the same hill gives the same climb for everyone.
• Privacy: server-side truncation with a randomised radius, both ends plus mid-route, published geometry separate from private metrics.
• Anti-cheat: physics limits + personal outliers + motion signature + file integrity; require two signals before hiding.
• The one-liner: "A geometry problem disguised as a social app — the whole design is a spatial index that turns 30 million polyline comparisons into twenty, and everything else is a streaming pipeline around it."