Design Top K YouTube Videos

Heavy Hitters System Design

Overview

"What are the top 100 most-viewed videos right now?" sounds like one ORDER BY count DESC LIMIT 100. At YouTube scale it is one of the harder streaming problems there is. Views arrive as a firehose — on the order of a million events a second — spread across hundreds of millions of distinct videos, and you want the current top K (K is small: 100, maybe 1,000) over several time windows at once: trending this hour, top today, most-viewed of all time. The naive plan — keep an exact counter per video and sort them — dies twice over: you cannot hold a billion counters in the memory of a streaming job, and you cannot sort a billion rows on every query.

This is the heavy hitters problem: out of a near-infinite stream of keys, find the few that dominate, using memory bounded by K and a small sketch — not by the number of distinct videos. It is labeled "Hard" because the right answer is not a bigger database; it is accepting approximation in the live path (a count-min sketch plus a min-heap), while running a slower batch layer that recomputes exact counts from the raw view log for the rankings that have to be right (creator payouts, the official "most-viewed of all time" board).

This walkthrough deliberately does not re-derive per-key streaming counting, out-of-order/late data, watermarks, or exactly-once — the ad-click aggregator covers all of that and this design reuses it. Here the center of gravity is different: selecting the top K under a hard memory limit when you cannot afford to count every key exactly.

In this walkthrough you'll scope the system, size it, model the data, design the API, draw the ingest / serve / batch paths, then go deep on approximate top-K with a count-min sketch and heap, time-windowed top-K and the shard-merge trap, and the exact-vs-approximate reconciliation and serving layer.

Out of scope (say so): what counts as a "view" (the de-dup / anti-fraud rules that decide a view is legitimate — assume a clean, already-validated view event arrives), the recommendation ranking that personalizes a home feed, and video storage / transcoding / CDN delivery. We own counting views and answering top-K, not deciding which video to autoplay.

Functional requirements

• Ingest a view. Record every counted view as an event carrying the video_id and when it happened.
• Top-K over a window. Return the K most-viewed videos over a time window — trending this hour, top today, top this week, most-viewed all-time. K is small (≤ ~1,000).
• Multiple windows at once. The same firehose must feed several windows simultaneously (hourly, daily, all-time), not one hard-coded window.
• Approximate live ranking. The trending list may be approximate and a few seconds stale — it is a discovery surface, not an invoice.
• Exact official ranking for finalized windows. For payouts and the official all-time board, a window's ranking must be exactly correct once it closes, reconciled from the raw view log.

Out of scope (state it): defining/validating a legitimate view, recommendation personalization, and the video delivery pipeline. This system turns a view firehose into top-K lists and serves queries over them.

Non-functional requirements

• Firehose write volume. ~1M views/sec average, multiples of that at peak. Ingest must absorb it without dropping events and without a per-event database write.
• Bounded memory, independent of video count. The live top-K must run in memory sized by K and a fixed sketch — not proportional to the hundreds of millions of distinct videos. This is the whole game.
• Approximate is acceptable for live/trending. A trending list that is slightly off in the tail, or names #97 where the true rank is #101, is fine. Nobody audits "trending."
• Exact is required for official rankings. Payout-grade and "official most-viewed" rankings must be exactly correct and reproducible from the raw log.
• Low-latency top-K reads. The top-K list is tiny and read constantly — it must be a cached O(1)/O(log N) read, never a scan or a sort over all videos.
• Handle skew / viral videos. A single video can take a huge share of the firehose (a hot key); one viral video must not pin a single ingest partition or counter.

Estimations

State assumptions; the goal is to justify why exact-count-and-sort is impossible and what the sketch buys you — not to be exact.

Rounded assumptions

• Views/day: ~100B (aggressive, to stress the firehose). ÷ 86,400 s ≈ ~1.15M → ~1M views/sec average; peak spikes (premieres, live events) to ~3–5M/sec.
• Distinct videos viewed/day: ~500M, out of an all-time catalog in the billions. K is tiny by comparison: 100–1,000.
• Exact all-video count table (the thing to avoid). ~500M–1B live counters × ~64–100 bytes (id + count + hash overhead) ≈ ~50–100 GB per window, and you'd keep one per window (hour, day, all-time). Worse, answering top-K over it means sorting ~1B rows — per window, per refresh.
• Count-min sketch (the thing to use). A sketch of width w = 2²⁰ (~1M columns) × depth d = 5 rows × 4-byte counters ≈ ~20 MB — fixed, regardless of whether 10M or 1B distinct videos flow through it. Plus a min-heap of K entries (~tens of KB). That is the memory win: ~20 MB instead of ~100 GB, per window. (The width sets the error, not just the memory: overcount ≈ total-views ÷ w, so a high-view window — a full day at ~100B views — needs a wider w, or per-minute slices summed as in deep dive 2, to keep that error small next to the K-th video's count. Treat 20 MB as illustrative for a shorter, lower-N window.)
• Raw view log. ~100B/day × ~50 bytes/event ≈ ~5 TB/day — far too big to scan per query, retained for the batch exact-recompute path, not for serving reads.

How the numbers affect the design

Core entities / data model

Four things are stored: the raw view event (immutable source of truth), the approximate top-K state (sketch + heap, the streaming structure), the exact aggregate (batch-computed counts for finalized windows), and the serving store (the small top-K list clients read).

The raw ViewEvent is the single source of truth — immutable, append-only, archived to cheap durable storage (a partitioned log, then a data lake) so exact counts can always be recomputed. Everything else is derived from it and rebuildable.

The TopKState is the streaming structure and the heart of the design: a fixed-size count-min sketch that estimates any video's count, and a min-heap holding the current K strongest candidates. It is not a per-video table — it is bounded memory (~20 MB + K entries) no matter how many videos flow through. One TopKState exists per active window.

The ExactWindowCount is produced by the batch layer for windows that must be exact. You do not keep an exact count for every one of a billion videos live — you compute exact counts and pick the exact top-K only for finalized windows, on a cadence. Note it recomputes from the full log (not just the candidates the stream surfaced): the whole reason the exact pass exists is to catch a true top-K video the approximate layer missed, so restricting it to stream candidates would inherit the very blind spot it's meant to fix.

The serving store holds only the answer: the K winners per window with their counts and ranks. Because that is a tiny sorted list (≤1,000 entries), a Redis sorted set (ZSET) per window serves top-N in O(log N) — the exact structure the gaming leaderboard uses. The crucial difference: the leaderboard can afford a sorted set over all members; here you cannot, so the heavy-hitters layer selects the small winning set first, and only that set goes into the sorted set.

API design

Three operations carry the system: ingest a view, read the top-K for a window, and (optionally) read one video's approximate standing.

Ingest a view

POST /api/views
Body: { "video_id": "v_8f3a", "event_time": "2026-07-17T18:04:07Z" }
202 Accepted
Returns: { "accepted": true }

Record one counted view. Returns 202 — the view is durably appended to the ingest log and processed asynchronously; the caller never waits for it to be counted. event_time rides on the event so windowing is by event-time (mechanics in the ad-click aggregator).

Top-K for a window

GET /api/top?window=1h&k=100
200 OK
Returns: {
  "window": "1h",
  "as_of": "2026-07-17T18:05:00Z",
  "approximate": true,
  "videos": [ { "rank": 1, "video_id": "v_8f3a", "count": 4820133 }, … ]
}

Return the K most-viewed videos in the window, ranked. Served from the maintained per-window top-K list (a cached sorted set), never by sorting all videos. approximate: true flags the live streaming answer; the same endpoint with a finalized window returns the exact, reconciled ranking (approximate: false).

One video's approximate standing (optional)

GET /api/videos/{video_id}/rank?window=1d
200 OK
Returns: { "video_id": "v_8f3a", "window": "1d", "estimated_count": 4820133, "in_top_k": true }

Return a single video's estimated count for a window from the sketch, and whether it is currently in the top-K. Note the honest limitation: the sketch gives a good count estimate for a heavy hitter, but a precise rank for a mid-tail video is not something the top-K structure knows — it only tracks the K winners, so a video outside the heap has no maintained rank.

High-level architecture

Three paths matter: a streaming top-K path (views → log → per-window sketch + heap → top-K list), a serving path (clients read the cached top-K), and a batch exact path (raw log → exact recompute → reconcile). We'll walk each, then combine.

1. Streaming top-K path (ingest + heavy hitters)

Views land in a durable log; a stream processor updates a per-window sketch and heap, and publishes the top-K list.

flowchart LR
    Client["View event<br/>(player / app)"] -->|"POST /views"| GW["Ingest Service"]
    GW -->|"append (partition by video_id)"| Log[["Durable view log<br/>(partitioned stream)"]]
    Log --> SP["Stream processor<br/>per-window: count-min sketch + min-heap"]
    SP -->|"publish top-K list"| Serve[("Top-K serving store<br/>(ZSET per window)")]
    Log -.->|"archive raw events"| Lake[("Raw view store<br/>(data lake)")]

1. A view hits the Ingest Service, which appends it to a durable, partitioned view log. Partitioning by video_id keeps one video's views together on one partition, which matters for the merge step (deep dive 2); viral videos get sub-sharded so they don't pin a partition.
2. Every raw event is also archived to the data lake so exact counts can be recomputed later.
3. The stream processor consumes the log and, for each active window, updates that window's count-min sketch (bump the estimate) and its min-heap of top-K candidates.
4. As the heap changes, the processor publishes the current top-K list into the serving store.

The rule that keeps this feasible: memory is bounded by K and the sketch size, not by the number of videos. The processor never holds a counter per video.

2. Serving path (top-K reads)

Reads serve the tiny maintained list, never a scan.

flowchart LR
    Reader["Trending page / API client"] -->|"GET /top?window&k"| Query["Query Service"]
    Query -->|"read top-N (cached)"| Serve[("Top-K serving store<br/>(ZSET per window)")]
    Serve -.->|"on miss / refresh"| SP["Stream processor<br/>(current heap)"]
    Query -->|"ranked list"| Reader

1. The client asks the Query Service for a window's top-K.
2. The service reads the maintained top-K list — a Redis sorted set of at most K entries per window, so top-N is an O(log N) range read (the gaming leaderboard serving pattern). The list barely moves second-to-second, so it is heavily cached.
3. It returns the ranked list. All from a tiny derived structure — no per-video scan, no sort of the catalog.

3. Batch exact path (reconciliation)

A slower batch job recomputes exact counts from the raw log for windows that must be exact, and overwrites the served list.

flowchart LR
    Lake[("Raw view store<br/>(data lake)")] --> Batch["Batch job (MapReduce/Spark)<br/>exact count per video → exact top-K"]
    Batch -->|"exact top-K for finalized window"| Serve[("Top-K serving store")]
    Batch -->|"exact counts (payouts, official board)"| Exact[("Exact aggregate store")]

1. On a cadence (and when a window finalizes), the batch job reads the archived raw views and computes exact counts per video.
2. It selects the exact top-K for the finalized window and overwrites the approximate served list, flipping approximate to false.
3. It writes exact counts into the exact aggregate store for payout-grade uses and the official all-time board.

4. Combined architecture

flowchart LR
    Client["View event"] -->|"POST /views"| GW["Ingest Service"]
    GW -->|"append (partition by video_id)"| Log[["Durable view log"]]
    Log --> SP["Stream processor<br/>per-window sketch + min-heap"]
    SP -->|"publish top-K"| Serve[("Top-K serving store<br/>(ZSET per window)")]
    Log -.->|"archive"| Lake[("Raw view store")]
    Lake -.->|"exact recompute"| Batch["Batch job"]
    Batch -.->|"reconcile / overwrite finalized window"| Serve
    Batch -.->|"exact counts"| Exact[("Exact aggregate store")]
    Reader["Trending page"] -->|"GET /top"| Query["Query Service"]
    Query -->|"read cached top-K"| Serve

The view log is the buffer that decouples the spiky firehose from steady processing; the raw store is the authoritative record; the streaming path gives near-real-time approximate top-K; the batch path gives exact rankings for finalized windows; the serving store is a tiny derived list clients read. Ingest, serving, and batch are decoupled — a viral spike hits the log and the sketch, never the read path.

Deep dives

1. Approximate top-K over a firehose — count-min sketch + min-heap

The core decision is how to find the top K without counting every video exactly. Walk the options worst to best.

Why exact-count-and-sort is infeasible. To sort videos you first need a count per video. Hundreds of millions of live counters is ~50–100 GB per window in the streaming job's memory, and the top-K query is a full sort of ~1B rows. Both scale with the number of distinct videos — exactly the quantity that is enormous and that you do not care about, since you only want the tiny head of the distribution.

The reframe: heavy hitters. You do not need every count. You need the few videos whose counts tower over the rest, plus a way to estimate a candidate's count in tiny, fixed memory. That is the count-min sketch (frequency estimate, memory independent of key count) paired with a size-K min-heap (the running top-K).

distinct videos this hour: ~200,000,000
map memory: 200M × ~64 B ≈ ~12.8 GB (per window, in the streaming job)
top-100 query: sort 200,000,000 entries → O(N log N) ≈ billions of comparisons
  … per refresh, per window (hour + day + all-time)

1M views/sec → count ~10K/sec; estimate = counted × 100
heavy hitters (millions of views) → sampled count is large, error small
tail videos (a few views) → sampled 0 or 1 → estimate wildly wrong or missed

on view(video_id):
  1. for each of d rows r: sketch[r][ hash_r(video_id) ] += 1
  2. est = min over rows r of sketch[r][ hash_r(video_id) ]   # the "min" in count-min
  3. if video_id already in heap: update its key to est, sift
     else if heap has < K entries: push (video_id, est)
     else if est > heap.min().est:  pop the min, push (video_id, est)

flowchart LR
    V["view(v_8f3a)"] -->|"d=5 hashes"| CMS["count-min sketch<br/>w=2^20 cols × d=5 rows<br/>~20 MB fixed"]
    CMS -->|"est = min of 5 cells"| Est["estimated count"]
    Est -->|"est &gt; heap-min?"| Heap["min-heap size K=100<br/>current top-K"]
    Heap -->|"publish"| Serve["top-K list"]
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class CMS,Heap good

2. Time-windowed top-K — tumbling, sliding, and the shard-merge trap

Trending is inherently temporal: "top this hour" must forget last hour; "most-viewed today" accumulates and resets at midnight; "all-time" never forgets. And the firehose is sharded, so each window's answer must be merged across shards — where the subtle bug lives.

Tumbling vs sliding windows. A tumbling window is a fixed non-overlapping bucket — the 17:00 hour, the July-17 day. Each has its own sketch + heap; when it closes you finalize it and start a fresh one. A sliding window — "trending over the last 60 minutes, refreshed each minute" — overlaps, so you cannot keep one monolithic sketch and subtract expiring events (a count-min sketch cannot delete cleanly).

Exploit sketch additivity for sliding windows. The count-min sketch is linear: the sketch of two event sets summed cell-by-cell equals the sketch you'd get by feeding both sets into one sketch. So keep per-slice mini-sketches (one small sketch per minute), and build any sliding window by summing the slices in range:

per-minute sketches:  S(17:00) S(17:01) … S(17:59) S(18:00) …
last-60-min window @ 18:00  =  S(17:01) + S(17:02) + … + S(18:00)   (sum 60 slices, cell-wise)
next minute @ 18:01         =  drop S(17:01), add S(18:01)          (slide by swapping one slice)

Sliding by one minute is "add the new slice, drop the expired slice" — no per-event deletion, no unbounded state. The heap does not sum the same way, so after summing the slice sketches you rebuild the heap by re-querying the summed sketch for a candidate set. Keep that candidate set bounded: use the union of the per-slice heaps, over-provisioning each slice to top-K′ (K′ > K) to catch videos sitting just below a slice's cutoff — that's O(#slices × K′), not "every video observed in the window," which would be the O(distinct videos) blowup the whole design exists to avoid. The honest residual: a video hot in aggregate but top-K in no single slice appears in no slice heap, so the streaming rebuild can miss it — the time-dimension twin of the shard-merge trap below, and exactly what the batch exact pass (deep dive 3) corrects. Per-hour and per-day tumbling windows are the same idea at coarser slice sizes; all-time is one ever-growing sketch (or coarse daily slices summed).

The shard-merge trap — why merging local top-K lists misses globally-hot videos. The firehose is processed by many shards in parallel. If each shard keeps its own sketch + heap and you merge by taking each shard's top-K list and combining them, you can miss a globally-hot video:

flowchart LR
    A["shard A top-K<br/>… #100 cutoff = 50k<br/>v_hot = 48k (rank 101, dropped)"] --> M["merge local<br/>top-K lists"]
    B["shard B top-K<br/>… #100 cutoff = 47k<br/>v_hot = 46k (rank 101, dropped)"] --> M
    C["shard C top-K<br/>… #100 cutoff = 52k<br/>v_hot = 49k (rank 101, dropped)"] --> M
    M --> R["v_hot MISSED<br/>global = 48k+46k+49k = 143k<br/>(truly top-K, never in any local list)"]
    classDef warn fill:#fef9c3,stroke:#ca8a04,color:#713f12;
    class R warn

v_hot sits at rank #101 on every shard — just below each local cutoff — so it appears in no shard's top-K list, yet its summed global count (143k) is comfortably in the true top-K. Merging local top-K lists lost it. Three ways to handle it, worst to best:

flowchart LR
    A["shard A sketch + candidates"] --> S["sum sketches (cell-wise)<br/>union candidate sets"]
    B["shard B sketch + candidates"] --> S
    C["shard C sketch + candidates"] --> S
    S -->|"query global sketch<br/>per candidate"| G["global top-K<br/>v_hot scored at 143k → included"]
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class S,G good

3. Exact-vs-approximate reconciliation and serving

The live top-K is approximate; some rankings must be exact. This is the ad-click aggregator's lambda/kappa tension in a new costume — reuse its machinery (exactly-once, watermarks, reconciliation) and focus here on who needs exactness and how the two layers meet.

Who tolerates approximate, who demands exact.

• Trending / discovery (approximate). "Trending this hour" is a soft signal. If the sketch names a video at rank 8 that is truly rank 11, no harm — it is served fast and cheap from the streaming layer.
• Official rankings / payouts (exact). "Most-viewed video of all time," creator monetization tied to view thresholds, and any externally-cited leaderboard must be exact and reproducible. Approximate counts that overcount by collisions are indefensible when money or public records ride on them.

The batch exact layer. Over the archived raw view log, a batch job (MapReduce/Spark) computes the exact count per video for the window, then the exact top-K. At billions of rows the top-K itself is distributed — but with exact counts, the safe merge from deep dive 2 applies: partition the aggregation by video_id so each reducer holds a video's full count, emit each reducer's local top-K, and merge — exact because no count is split. This is the same computation the "avoid" option in deep dive 1 described, now run where it belongs: a batch cluster that is not memory-bound per node and runs on a cadence, not per query.

How the two layers reconcile.

flowchart LR
    Log[["Raw view log<br/>(authoritative)"]] --> Stream["Streaming layer<br/>sketch + heap · approximate · seconds"]
    Log --> Batch["Batch layer<br/>exact counts · reproducible · hours"]
    Stream -->|"live top-K (approximate: true)"| Serve[("Top-K serving store")]
    Batch -->|"finalized top-K (approximate: false)"| Serve
    Serve --> Reader["clients: live now,<br/>exact once finalized"]
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    class Batch good

While a window is open, the serving store holds the streaming top-K, flagged approximate: true. When the window closes and the batch pass completes, the batch layer overwrites that window's list with the exact ranking and flips the flag to approximate: false. Trending stays live; finalized boards become exact and auditable. Both read from the same authoritative raw log, so they cannot diverge in a way batch can't settle.

Make the overwrite an atomic swap, not an in-place edit. Write the finalized list under a new immutable version key (topk:{window}:v2) and then atomically repoint the window's pointer from v1 to v2 (a single SET/RENAME, or a versioned row swap) — so a reader either sees the whole approximate list or the whole exact one, never a half-rebuilt board mid-update. The approximate flag travels with the version, and keeping the prior version briefly lets in-flight readers finish and makes rollback trivial if a batch run is later found wrong.

Serving the selected top-K. Once selection has produced the K winners (streaming or batch), serving is the gaming leaderboard problem in miniature: put the K entries in a Redis sorted set (ZSET) per window (score = count), and top-N is an O(log K + page) range read, heavily cached because the list changes slowly. As the core-entities section framed it, the selection step is what's hard here — the leaderboard can hold all members; you can't, so heavy-hitters picks the K winners first and only they reach the sorted set.

Tradeoffs & bottlenecks

• Approximate sketch vs exact table. The count-min sketch bounds memory at ~20 MB regardless of video count and answers heavy-hitters tightly, at the cost of one-sided overcounting and no usable tail accuracy; an exact table is precise but O(distinct videos) in memory and O(N log N) to sort — infeasible in the live path, natural in batch.
• Sketch width/depth: memory vs accuracy. Wider sketches shrink collision error (ε ∝ 1/w); more rows raise confidence (∝ e^{-d}). Both cost memory — tune to the smallest sketch whose error is negligible relative to the K-th video's count.
• Tumbling vs sliding windows. Tumbling windows are simple (one sketch per bucket, finalize and reset) but coarse; sliding windows are smoother but need per-slice sketches summed by additivity and a heap rebuilt from the summed sketch.
• Shard-merge: local lists vs summed sketches. Merging local top-K lists is cheap but misses split-but-globally-hot videos; partition-by-video_id (plus hot-key sub-sharding) or merging summed sketches is exact/robust at higher merge cost.
• Live approximate vs batch exact (lambda/kappa). Streaming gives near-real-time trending; batch gives exact, reproducible official rankings; running both costs a second pipeline but delivers responsiveness and auditability. (Mechanics: ad-click aggregator.)
• Hot video skew. A viral video is a hot partition/counter under video_id partitioning — sub-shard just the hot keys and sum partials; the long tail stays on a single partition.

Extensions if asked

Add only the extension that changes the design discussion:

• Trending ≠ most-viewed (velocity & decay). "Trending" should weight recent acceleration, not raw totals, or old megahits dominate forever. Add time-decay (exponentially weighted counts) or rank by view rate / rate-of-change over recent slices — a scoring change on top of the same sketch-per-slice structure.
• Top-K per dimension. Top videos per country / per category / per language is a top-K per group — a sketch + heap per key (or a single sketch keyed by (dimension, video_id)), trading memory for cardinality of dimensions.
• Space-Saving / Lossy Counting. Alternative heavy-hitters algorithms that track a bounded set of counters with eviction, giving deterministic error bounds — mention them as peers of count-min + heap and note the tradeoff (tighter guarantees, different memory profile).
• De-duplicating views. Counting unique viewers rather than raw views turns each counter into a cardinality-estimation problem (HyperLogLog per video) — a different sketch, same architecture.

What interviewers look for & common mistakes

What interviewers usually reward:

• Reframing to heavy hitters — recognizing that exact-count-and-sort is infeasible because it scales with distinct videos, and that top-K wants a structure bounded by K and a sketch.
• Count-min sketch + min-heap, and explaining why it works: the sketch never undercounts and is tight for heavy hitters (whose counts dwarf collision noise), sloppy only in the tail you don't care about.
• Naming the sketch's error levers — width for magnitude, depth for confidence — and that it overcounts, never undercounts.
• Time-windowing via additive slice sketches for sliding windows, and separate sketches per tumbling window.
• Catching the shard-merge trap — that merging local top-K lists misses a globally-hot-but-locally-borderline video, and fixing it with partition-by-video_id (plus hot-key sub-sharding) or summed-sketch merges.
• Two layers — approximate streaming for trending, exact batch for official/payout rankings — and reconciling by overwriting finalized windows from the raw log.

Before you finish, do a quick mistake check:

• Did you reject exact-count-and-sort and reach for a count-min sketch + min-heap, bounding memory by K and the sketch, not by video count?
• Did you state that the sketch overcounts but never undercounts, and that heavy hitters are accurate while the tail is not (which is fine)?
• Did you handle multiple/sliding windows with additive per-slice sketches rather than one un-deletable sketch?
• Did you catch that merging shard-local top-K lists misses globally-hot videos, and fix it (partition by video_id / merge summed sketches)?
• Did you keep a batch exact layer for official rankings and reconcile it against the approximate live list?
• Did you serve the selected top-K from a small sorted set (leaderboard-style) rather than sorting the catalog — and note that selection, not serving, is the hard part?
• Did you reuse rather than re-derive the streaming counting mechanics (exactly-once, event-time, hot keys) from the ad-click aggregator?