Design Top-K Trending

A video site has a "Trending" tab: the 100 most viewed videos in the last hour, the last day and the last month. Behind the tab is a question that sounds like a single ORDER BY and is not: billions of views a day, hundreds of millions of distinct videos, windows that slide forward every minute, and a page that millions of people load.

Interviewers like it because it tests whether you do the arithmetic before reaching for a clever structure: sometimes exact counting fits, and sometimes you need a sketch and an honest statement of its error. The steps follow A Framework for Any Design. Try each "Your turn" box before you read on.

#Clarify the problem

• Functional: return the top K (K ≤ 100) videos by views over the last hour, day and month, with their view counts.
• Non-functional: the hour and day lists refresh every minute and the month list every hour; reads return in under 50 ms at any load; a video with clearly more views than the 100th is never missing; counts within about 5% are fine for the month.
• Out of scope: defining a view, fraud filtering, personalised trending, arbitrary time ranges.

#Estimate the scale

The scenario: 5 billion views a day. In a typical hour about 30 million distinct videos get a view, about 150 million in a day and 500 million in a month. A counter entry (video id, count and hash-map overhead) takes about 50 bytes.

• Views: 5 × 10⁹ ÷ 86,400 s ≈ 58,000 a second on average; at 3x peaks, about 175,000 a second.
• Hour window, exact: to slide by the minute, keep one count map per minute (assume 2 million distinct videos a minute) plus running totals: 60 × 2 × 10⁶ × 50 B + 30 × 10⁶ × 50 B = 6 GB + 1.5 GB = 7.5 GB.
• Day window, exact: one map per hour: 24 × 30 × 10⁶ × 50 B + 150 × 10⁶ × 50 B = 36 GB + 7.5 GB = 43.5 GB.
• Reads: say the trending page peaks at 20,000 loads a second. Every one of them asks the same three questions.

#Define the API

GET /v1/trending?window=hour&limit=50
  200 { "window": "hour", "as_of": "2026-11-14T10:06:00Z",
        "items": [ { "video_id": "V7", "title": "...", "views": 48210 }, ... ] }
  400 Bad Request   window is not hour, day or month, or limit > 100
  Cache-Control: max-age=30
 
View events (internal, from the video service to the log):
  { "video_id": "V7", "count": 3, "second": "10:05:12" }   -- pre-summed per server per second

The decision worth arguing is what the API refuses. "Top 50 for 14:00 to 15:30 last Tuesday" turns a lookup into a scan over billions of events. Three windows and K ≤ 100 keep every read to one key; ad hoc ranges belong in a warehouse, a different system.

View events are pre-summed: one event per video per server per second. A viral video watched 20,000 times a second on 500 servers becomes at most 500 events a second.

#Model the data

Counter task state (one task per log partition, 32 partitions)
  minute_buckets : ring of 60 maps   video_id -> views in that minute
  hour_totals    : map               video_id -> sum of the 60 buckets
  hour_buckets   : ring of 24 maps   (same idea for the day)
  day_sketches   : 31 daily count-min sketches + 1 running month sketch
  candidates     : video ids whose month estimate passed a floor
  checkpoint     : state + log offsets, written to object storage every minute
 
Results (key-value store, about 10 KB per value)
  key   "trending:hour" | "trending:day" | "trending:month"
  value { as_of, version, items: [ {video_id, title, thumbnail, views} x 100 ] }

The counting state is a stream processor's keyed state, kept next to the computation and snapshotted for recovery; nothing on the read path touches it. The results are three keys read constantly and written once a minute: a key-value store or an in-memory cache with a durable copy. Titles are attached when the list is built, so a read never joins.

#High-level design

#Deep dives

#Windows: tumbling or sliding

A tumbling window is a fixed block, 10:00 to 11:00. At 10:01 its list is built from one minute of data, and a video that peaked at 9:55 vanishes at 10:00 sharp. A sliding window, the 60 minutes up to now, moves smoothly, but done literally it must forget each view exactly 60 minutes later.

The practical answer is a sliding window built from small tumbling buckets: 60 one-minute buckets for the hour. Each minute, add the newest bucket to the running totals and subtract the oldest; the work is proportional to one minute's distinct videos, not the hour's. For the day, use 24 hourly buckets plus the current partial hour, so the day list also refreshes every minute; its window is 23 to 24 hours long, which nobody notices on a trending page.

#Merging partitions into one top K

Counting is split over 32 partitions. Each finds its local top 100; the merger picks the best 100 of the 3,200. Whether that is right depends entirely on how events were partitioned.

• By video id (our choice): every view of V7 lands in partition 12, so partition 12 holds V7's true total. If V7 is in the global top 100, at most 99 videos anywhere beat it, so at most 99 in its own partition do, and it is in partition 12's local top 100. The merge is exact.
• By server or at random: V7's views are spread over all 32 partitions. It could rank 101st in every one and still be first overall. Merging local top lists is then simply wrong, and you would need to ship every count to the merger or do a second exact pass on candidates.

The cost of partitioning by video is skew: a viral video loads one partition. Pre-summing per server per second cuts that to a few hundred events a second. The ad click aggregator shows the salted two-stage fix for when that is not enough.

#Exact counts or a sketch

For the month, exact counts take 250 GB, mostly the long tail. A count-min sketch trades a small, one-sided error for a fixed amount of memory. It is a grid of counters, d rows by w columns, with one hash function per row. To add a video, hash it once per row and add to that cell in every row. To estimate its count, read those same d cells and take the smallest. Other videos that hash into the same cell can only add to it, so the estimate is never too low; taking the minimum picks the row where collisions hurt least.

The guarantee is precise: with width w and depth d, each estimate is at most the true count plus (e ÷ w) × N, where N is the total of all counts added and e ≈ 2.718, with probability at least 1 − e^−d. Each counter task keeps sketches for its own partition only, since every view of a video lands there. A month is 5 × 10⁹ × 30 = 1.5 × 10¹¹ views, so one task sees N ≈ 4.7 × 10⁹. With w = 2¹⁸ ≈ 262,000 and d = 5, an estimate is high by at most 2.718 ÷ 262,144 × 4.7 × 10⁹ ≈ 48,600 views, with probability 1 − e⁻⁵ ≈ 99.3% for any one video. Assume the 100th video of a month has at least a million views: the error is under 5% of the counts that matter. Each sketch is 5 × 2¹⁸ × 8 B ≈ 10.5 MB.

A sketch answers "how many for this video?" but cannot list the top ones, so pair it with a candidate set and a heap. Each task adds every view to today's sketch and to a running month sketch, then asks the month sketch for that video's estimate. If it passes a fixed floor, here 500,000 (half the assumed 100th place), the video joins the candidates. An estimate is never low, so any video whose true month count passes the floor joined on its last view. At midnight the task subtracts the day that fell out from the month sketch; cells add and subtract one by one when all sketches share hashes and width. Every hour it re-estimates the candidates, drops those under the floor, and sends its best 100, found with a min-heap, to the merger.

#Precomputing so a read is one lookup

20,000 page loads a second ask one of three questions whose answers change once a minute; computing per request would redo the same work 1.2 million times a minute. The merger writes each finished list under one key, and the page reads it through a CDN with a 30-second lifetime. A slow pipeline means a slightly older list, never a slow page.

Each write carries a version (its minute) and succeeds only if newer than the stored one, or a merger that stalls and wakes late overwrites a fresh list with an old one, as in the tracer.

#Bottlenecks and failures

At 10x, 1.75 million views a second and 10x the distinct videos, the hour state grows to 75 GB: go from 32 to 320 partitions, about 234 MB per task. Exact day counts reach 435 GB, the point where the day should move to sketches too. The merger handles 320 lists of 100 a minute easily, and reads do not change at all.

#What a strong answer sounds like

#Follow-up questions

#What changes for the most searched terms?

Normalise queries first. Distinct terms are far more numerous and most appear once, so exact maps are mostly waste: use a sketch plus heap for the day window too.

#Trending should mean rising, not just big. How?

Rank by this hour's views divided by the video's usual hourly rate, with a minimum count so a jump from 2 to 20 does not win. Only the score changes.

#How do you add per-country lists?

Make the bucket key (country, video). Memory grows with the pairs that actually occur, and the results store gets one key per country and window, still a single read each.

#How do you stop people gaming the list?

Count only views that pass upstream checks, cap what one account or device adds per video per hour, and let moderation remove a video from candidates.

#Why not a sorted set in an in-memory store?

For one window it works, as in Design a Leaderboard. Here every view would be a network write at 175,000 a second, and expiring old views from a sorted set still needs per-minute buckets. Counting inside the stream task avoids both.