YouTube Top K / Trending

Real-time Video Trending & Ranking System

Design a system that counts billions of video views a day and keeps a fresh list of the top videos per region and category, ranked by how fast they are growing rather than by total views.

Overview

A trending list answers 'what is taking off right now?' for each region and category. It is a top K problem: out of millions of videos with views in the last day, find the K (say 50) with the highest score, and keep that list fresh.

Two things make it more than a sort. The input is a stream of billions of events, so you cannot re-sort everything on every view; you count in windows and rank the counts. And the score is not total views: a video that went from nothing to 100,000 views in an hour is more 'trending' than one that gets 10,000 views every hour. YouTube's help page for its trending charts says as much: the video with the most views that day may not be first, and signals include how fast views are growing, where they come from, the video's age and how it compares with the channel's other recent uploads.

Questions to ask first

How many views? — 10 billion view events a day, peak 3× average
How many lists? — 100 regions × 15 categories, 50 videos each
How fresh? — Lists recomputed every 5 minutes (a target we chose; YouTube's help page says its charts update roughly every 30 minutes)
Exact or approximate counts? — The ranking may be approximate; the top of the list must be right
Personalized? — No: everyone in a region sees the same list
Abuse? — Invalid and automated views must not count

What you will be able to do

Size a view-counting pipeline and cut its write rate with pre-aggregation.
Find the top K exactly with partitioning and heaps, and approximately with a Count-Min Sketch, and say when each is right.
Score with exponential time decay, and explain why it beats raw counts for trending.
Serve per-region lists cheaply, and keep invalid views from gaming them.

Key concepts

Top K
Heavy hitters
Count-Min Sketch
Min-heap
Time decay
Tumbling windows
Pre-aggregation
Partition by key
Precomputed lists
Invalid traffic

Functional requirements

Record every view with its video, region and time
Show the top 50 trending videos per region and category
Rank by recent growth, not lifetime views
Limit how many videos one channel can place in a list
Exclude invalid, automated and paid (ad) views from the ranking

Non-functional requirements

Absorb about 350,000 view events a second at peak
Lists at most 5 minutes stale (a target we chose)
Trending API under 50 ms at p99 from cache (a target we chose)
A pipeline failure leaves the last good lists in place
Counts may lag during recovery but are not lost or double counted

Interview questions

How do you find the top K from billions of events?
Why is trending not just the most viewed?
How does a Count-Min Sketch work, and when would you use it?
Can you merge per-server top K lists?
How do you stop people from buying their way onto trending?
How do you serve the lists to millions of viewers?