YouTube Top K

Interview scope and guarantees

Return the most-viewed videos over explicit windows such as the last hour and day. Decide whether the answer must be exact or approximate and how late events change published results. A view definition must distinguish retries, bots, and legitimate repeat watching.

Capacity worksheet

Assume 1 billion view events/day: 11,574/s average and 57,870/s at 5× peak. At 100 bytes/event the raw stream is 100 GB/day. A count for each of 100 million videos at 16 logical bytes is 1.6 GB before window buckets and storage overhead; a heap alone does not store all counts.

Concrete API contract

POST /view-events {eventId,videoId,eventTime,sessionId}
GET /trending?window=1h&region=...&k=100
Response includes asOf, windowStart, completeness and algorithmVersion.

Data model and access paths

events(event_id,video_id,event_time,region)
counts(window_bucket,video_id,region,count)
topk(window,region,generation,rank,video_id,count)
watermarks(partition,event_time)

Evolve a solution and explain each change

Figure — Three architecture decisions for YouTube Top K, including the pressure each introduces.

Step 1: Count exact events

Aggregate validated views per video and time window. A full scan for every leaderboard is expensive.

Step 2: Maintain partition summaries

Partition counting and periodically emit local top-K candidates. Pruning too early can miss globally popular videos.

Step 3: Merge with error policy

Merge sufficiently rich summaries or exact counts with watermark and revision rules. Late events, skew, and approximation change the meaning of rank.

Responsibility overview

Figure — Connected responsibilities for YouTube Top K. Trace the authoritative and derived paths separately.

Worked end-to-end scenario

Video X receives 100 views on each of ten partitions but is not in any partition top-10 because ten local videos each have 101. Globally X has 1,000 views while those local videos may have only 101 each. Taking only local top-10 lists misses X. Hashing all events for one video to its owner avoids that particular split-count problem; otherwise retain enough candidate information or use an approximation with stated error. Publish a leaderboard for a defined closed window and revise or discard late events according to policy. A client must know whether it sees provisional or finalized results.

Why these access paths matter

Deduplicate event IDs within a defined retention window; aggregate by video and window. Store leaderboard versions by window start, duration, and revision. Sliding windows need bucket expiry or another explicit rolling computation, not a forever counter. A view eligibility definition should exclude known fraud before ranking, with correction events if classification changes.

Build the baseline first

1. View stream → per-video counters → window totals.
2. Counter snapshot → top-K heap → result table.
3. Trending API → cached published generation.

Evolve the design under load

1. Video-key partitions → local exact top K.
2. Coordinator → union of shard winners → global top K.
3. Late-event corrections → revised versioned results.

Defend the hardest decision

If every video belongs to exactly one shard and each shard computes exact scores for the same window, the union of each shard’s local K contains the global K. That statement is false when one video’s count is split across shards before aggregation. A Count-Min Sketch estimates frequencies with collision overestimation and still needs a candidate strategy. Time windows require expiring old contributions, not simply incrementing an all-time counter.

Failure and recovery analysis

A mobile client uploads yesterday’s views after reconnecting. Event-time windows use watermarks and an allowed lateness policy; arrivals beyond the policy go to correction or audit processing. An at-least-once source can inflate counts unless event IDs or source-offset transactions protect updates. Deduplication retention must match the replay horizon.

Security and privacy boundary

Protect event ingestion from fabricated views and avoid storing unnecessary user identifiers in ranking state.

Interview follow-ups with reasoning

Question: What if K changes from 100 to 10,000?

Question: How do sliding windows work?

Question: How do you test a sketch?

Operate and verify the design

Watermark lag, duplicate-event rate, correction count and ranking error versus exact samples.

Replay a window with duplicated and late events and compare the resulting published generation.

A second scenario to test transfer

Three workers each see partial counts. Video A has 900, 850, and 20 views; video B has 600, 600, and 600. A local top-one from only one worker can favor A, but merged totals are 1,770 versus 1,800. Merge candidate identities and counts before selecting global winners, or choose a summary algorithm with a stated recall/error property.

How can a video absent from every partition’s local top 10 still enter the global top 10 after merge?

Compare alternatives

A design-changing exercise

Can the union of local top-K lists always produce the global top-K?

Design workshop: exact windows before candidate pruning

Core requirement is top videos by eligible views over chosen windows, with ties by video ID and explicit provisional/final status. Fraud classification is upstream; ranking consumes its eligible/correction events. Choose one-minute refresh and two-minute allowed lateness as interview assumptions. A view event has eventId, videoId, eventTime and eligibilityVersion.

For an exact rolling hour, keep 60 minute buckets per video, a rolling sum and a per-owner ordered ranking structure. An admitted event increments its event-time bucket once. As minute M leaves the window, subtract that bucket and remove it. A heap with stale entries needs version checks and bounded cleanup; an ordered tree or rebuilt heap gives clearer memory bounds. Late events within policy update the historical bucket and publish a new leaderboard revision; events outside policy enter reconciliation or are rejected explicitly.

on_event(e):
    if not durable_dedup(e.event_id): return
    minute = floor(e.event_time / 60)
    if minute not in accepted_window: return late_policy(e)
    buckets[e.video_id][minute] += e.delta
    totals[e.video_id] += e.delta
    ranking.update(e.video_id, totals[e.video_id])
on_tick(new_minute):
    for video, count in expired_bucket(new_minute - 60):
        totals[video] -= count
        ranking.update(video, totals[video])

Deduplication, state changes and input checkpoint must recover consistently; the sketch is logical behavior, not a claim that separate dictionary writes and a log commit are atomic. Use a stateful streaming engine with checkpointed state or transactional aggregate revisions. Corrections can have negative deltas, but counts must remain consistent with the authoritative eligibility history.

Figure — A global winner absent from every local top-10.

If every video's entire window total belongs to one owner, union of owners' local K contains the global K: an omitted video has at least K videos ahead of it on its own owner, so cannot be globally top K under the same tie ordering. With split counts this proof fails. A hot video can be salted upstream only if its partial counts merge to one logical video total before candidate pruning. Salted local top lists are not enough.

Figure — Publish one coherent window revision.

At ten million active videos, 60 buckets of an illustrative eight bytes are 4.8 GB for counters alone; sparse event-time buckets reduce waste but add map/index overhead. Count-Min Sketch uses width about e/epsilon and depth ln(1/delta) for its usual nonnegative-frequency guarantee. For epsilon=0.001 and delta=0.01, choose width 2,719, depth 5; about 13,595 counters. It estimates frequencies with overcount and still needs candidate enumeration. Signed corrections require an algorithm supporting that update model; do not reuse insertion-only guarantees blindly.

Owner snapshots carry input watermarks. A coordinator that lacks an owner returns stale-but-complete last publication or explicit partial results; it does not silently treat a missing shard as zero. Store revisioned immutable leaderboards for comparison and replay validation.

Exercise: X has [100,100], A has [101,0], B has [0,101]. What is global top one and what does local-top-one pruning produce?

Technical references

Kafka processing and external-sink boundaries.

PostgreSQL transaction isolation and concurrent updates.