Courses › System Design › Question Breakdowns

Design Top-K (Trending)

Counting at scale with windows, heaps, and approximate sketches.

Design a service that returns the top K most-viewed videos (or most-searched queries, most-played songs…) over several time windows. It tests stream processing, windowing and when to accept approximate answers.

Requirements

Functional

  • Return the top K videos by view count for the last hour, last day, last month and all time
  • K is at most ~1,000

Out of scope: per-region or per-category top lists (discuss as an extension), personalization.

Non-functional

  • Ingest ~700k view events/second at peak
  • Freshness: results may be up to 1 minute stale
  • Low-latency queries (< 100ms)
  • Accurate counts (approximations acceptable only if bounded and explained)

Core Entities

  • View event — video ID, timestamp, (user ID)
  • Top-K list — window, generated at, ordered (video ID, count) pairs

API

GET /v1/top-videos?window=1h&k=100
→ { "window": "1h", "generatedAt": "...", "videos": [{ "videoId": "v1", "views": 1830012 }, ...] }

High-Level Design

Clients -> [View Ingest] -> {Kafka: views (by videoId)} -> [Stream Aggregators] -> (Counts Store)
[Stream Aggregators] -> [Top-K Merger] -> (Top-K Cache)
Client -> [Top-K API] -> (Top-K Cache)
  • View events are written to Kafka, partitioned by video ID so each video's counts are owned by exactly one aggregator.
  • Aggregators (Flink) maintain per-video counts in 1-minute buckets.
  • Every minute, each aggregator emits its local top K per window; a merger combines them into a global top K.
  • Results are written to a cache; the API serves them directly.

Deep Dives

1. Why local top-K merging works

Because partitioning is by video ID, every video's full count lives on one aggregator. The global top K must therefore be among the union of the local top Ks — merging N lists of K is cheap.

[!WARNING] Partitioning by something else breaks this If a video's views were spread across aggregators, a video could rank 1,001st everywhere locally yet be #1 globally. Partition by the key you're ranking.

2. Windows

  • Tumbling windows (fixed, non-overlapping) are simple but jumpy.
  • Sliding windows — "the last 60 minutes, updated every minute" — are what users expect. Keep 1-minute buckets; the hourly count is the sum of the last 60 buckets. Maintain it incrementally: add the newest bucket, subtract the one that just expired.
  • For day and month windows, roll minute buckets up into hourly and daily buckets to keep memory bounded.
  • All time: a running counter per video.

3. Memory and approximation

Tracking exact counts for hundreds of millions of videos per window takes a lot of memory. Options:

  • Count-Min Sketch + min-heap — a fixed-size probabilistic counter (overestimates slightly, never underestimates) plus a heap of the current top K. Memory is constant regardless of the number of videos.
  • Lossy counting / Space-Saving — tracks only likely heavy hitters.

A robust design uses streaming (possibly approximate) results for freshness, and a batch job over raw events (in S3 or a warehouse) to compute exact counts for longer windows and reconcile.

4. Hot videos

A viral video can overwhelm its single partition. Pre-aggregate on ingest servers (count locally for a second, then emit one event with a count), which cuts event volume dramatically.

5. Late and duplicate events

Use event time with watermarks so late events land in the right bucket; drop events beyond an allowed lateness. Dedup by event ID if the client can retry.

What's expected at each level

  • Mid-level: a working pipeline: ingest → count → compute top K → serve.
  • Senior: partitioning by video ID, local/global top-K merging, sliding windows with buckets.
  • Staff: approximation trade-offs (Count-Min Sketch), lambda-style reconciliation, hot-key mitigation, late data.