Design top-K trending

Open a video app during an IPL final and the trending tab is a live scoreboard of attention. A hashtag nobody used at 7 pm can be the most-posted tag in India by 7:40; a 20-second clip of the winning six can collect millions of views before the trophy is lifted; “rain in Mumbai” can top searches in Maharashtra while barely registering anywhere else. Behind that tab sits a question that sounds trivial — which K items got the most events in the last 5 minutes, hour or day? — asked of a stream of a million events a second and a billion distinct keys, almost all of which appear only a handful of times. You cannot afford an exact counter for everything, you cannot add up each server’s top-10 list, and the biggest items are not the ones rising fastest. This problem is about counting at scale with bounded memory and an honest error bar, and about the difference between “top” and “trending”.

Understand the problem

Pin down three things first: top by what, over which window, and how exact. “Most viewed in the last hour” on a home-screen widget and “the most-viewed video in India on 24 May” printed in a press release look like the same query, but the first can be a fraction of a percent off and seconds stale, while the second must be exact and defensible. Most of this design is about the first; a smaller, slower path serves the second.

Functional requirements

1. Users should be able to see the top K items for a time window — most-viewed videos, most-used hashtags, most-searched terms — over the last 5 minutes, hour, 24 hours or all time. K goes up to 1,000; the app usually shows 10 or 50.
2. Users should be able to see those lists globally or for their country or region, such as India or Maharashtra.
3. Users should be able to see a “trending now” list: items rising unusually fast compared with their own normal level, not simply the biggest.
4. The charts team and creators should be able to get exact daily rankings and counts, so “#1 video in India on 24 May” is a number you can defend.

Non-functional requirements

• Ingest scale. About 300k events a second on average and 1M a second at peak (an IPL final), roughly 26B events a day, spread over about 1B distinct items a day — videos, hashtags and normalised search queries.
• Freshness. The 5-minute lists at most about 30 seconds behind real time; the 1-hour, 24-hour and trending lists within 2 minutes.
• Read latency and volume. Around 75k list reads a second at peak, p50 under 10 ms and p99 under 50 ms at the API.
• Accuracy. Live lists may be approximate, with every count within a stated bound (about 26k views on the global daily list, 0.0001% of its total). Daily charts are exact.
• Availability. 99.95% for reads. If the pipeline falls behind, serve the last good list with its timestamp rather than an error or an empty tab.
• Abuse resistance. A few thousand coordinated accounts must not be able to push a hashtag into the trending list.
• Retention. Raw events kept 30 days so any day can be recomputed; daily charts kept forever.

Out of scope

• Personalised trending and recommendations. Ranking for one user is a different system; see design a recommendation feed.
• Billing-grade counting. Counts that move money need an auditable pipeline; see design ad click aggregation.
• Autocomplete. It also uses query counts, but needs prefix lookups; see design typeahead.
• Event collection and playback. We assume the apps already emit view, hashtag and search events; the video side is covered in design YouTube.
• Content classification. We consume a safety blocklist; we do not build the classifier.

The set-up

Plan the approach

Meet the four requirements with the simplest design — one counter, one store — then spend the interview in the deep dives, because every hard part is about scale: counting a billion keys, splitting the work without wrong answers, sliding windows, defining “trending”, serving, and exact numbers. Say the shape early: “an event stream, a counting job keyed by item, small precomputed lists, and a batch path for the truth.”

Core entities

• Event. event_id, type (view, hashtag_use, search), item key (video ID, normalised hashtag or query), user_id, event time, country and region.
• Item. The thing being ranked. Its title, thumbnail and creator live in the catalogue; the pipeline carries only IDs.
• Scope. Global, a country such as IN, or a region such as IN-MH.
• Window. A length and a refresh rate: 5 minutes refreshed every 10 seconds; 1 hour, 24 hours and all time refreshed every minute.
• Count bucket. The count for one (item, scope) in one minute or one hour.
• Top list. For one (type, scope, window): a version, an as_of time and up to 1,000 entries of item and count.
• Trend score. For one (item, scope): current rate, baseline rate, score, and when it peaked.

API

Three surfaces: event ingest, list reads, and exact daily charts.

Ingest. Apps batch events every few seconds. Each carries an event_id so retries can be de-duplicated; the server works out country and region from the IP address or profile instead of trusting the client.

POST /v1/events
Content-Type: application/json

{
  "events": [
    { "event_id": "e_7Hq2", "type": "view", "item": "v_9f3a",
      "user": "u_51c0", "ts": "2026-05-24T19:41:07.120+05:30" },
    { "event_id": "e_7Hq3", "type": "hashtag_use", "item": "#iplfinal",
      "user": "u_51c0", "ts": "2026-05-24T19:41:09.004+05:30" }
  ]
}

The reply is 202 Accepted: the event is durable in Kafka, not yet counted.

Top lists and trending. Read-only, the same for every user in a scope, and therefore cacheable.

GET /v1/top?type=video&scope=IN&window=1h&k=50

{
  "type": "video", "scope": "IN", "window": "1h",
  "as_of": "2026-05-24T19:42:00+05:30",
  "approximate": true,
  "items": [
    { "rank": 1, "item": "v_9f3a", "count": 3104220, "change": "+2" },
    { "rank": 2, "item": "v_1c77", "count": 2877105, "change": "-1" }
  ]
}

GET /v1/trending?type=hashtag&scope=IN-MH&k=20

{
  "as_of": "2026-05-24T19:42:00+05:30",
  "items": [
    { "rank": 1, "item": "#raininmumbai", "score": 0.0053,
      "count_5m": 120, "baseline_5m": 1.5 }
  ]
}

Exact daily charts, published after the batch job finishes:

GET /v1/charts/daily?type=video&scope=IN&date=2026-05-24&k=100

The response looks like a top list with "final": true and no approximate flag.

Back-of-envelope estimates

These numbers decide whether exact counting is possible, how many counting tasks you need and how reads are served. (For the method, see back-of-envelope estimation.)

Events in. 300M daily users producing about 86 events each — views, searches, hashtags — is 300M × 86 ≈ 26B events a day. Spread evenly that is 26B ÷ 86,400 ≈ 300k events/s; an IPL final pushes it about 3.3× to 1M events/s.

Bandwidth and archive. At about 200 bytes per event, the peak is 1M × 200 B = 200 MB/s, about 1.6 Gbit/s. A day of raw events is 26B × 200 B = 5.2 TB, about 1.3 TB after 4× columnar compression, so 30 days of history is about 39 TB in object storage.

Scope fan-out. Every event counts in three scopes — global, country, region — so the counters see 1M × 3 = 3M increments/s at peak.

Exact counting memory. About 1B distinct items a day; with each item seen in the global scope plus 1.5 country or region scopes on average, that is 2.5B (item, scope) pairs. At about 50 bytes per entry in a hash map, one 24-hour window needs 2.5B × 50 B ≈ 125 GB — before keeping any history to make the window slide.

Sketch memory. A count-min sketch with error ε = 10⁻⁶ of the total and failure probability δ = 10⁻³ is e/ε ≈ 2.72M counters wide and ln(1/δ) ≈ 7 rows deep: 19M counters × 4 B ≈ 76 MB, with every estimate within 10⁻⁶ × 26B ≈ 26k views on the global daily window. A Space-Saving summary with 1M counters (about 48 bytes each for item, count, error and links) gives the same worst-case bound, 26B ÷ 1M = 26k, in about 48 MB.

Lists out. 3 types × about 230 scopes (global, about 200 countries, about 30 large regions) × 4 windows = 2,760 top lists, plus 690 trending lists, ≈ 3,450 lists. At 1,000 entries × 40 bytes = 40 KB each, all of them together are 3,450 × 40 KB ≈ 138 MB, small enough for one cache.

Reads. 300M users opening an explore or trending surface about 7 times a day is 2.1B reads ÷ 86,400 ≈ 24k/s, so plan for 75k/s at a 3× peak. At about 10 KB per response that is 750 MB/s, about 6 Gbit/s — a job for a CDN.

Counting fleet. Pre-summing each second (deep dive 2) shrinks the 3M increments to roughly 1M keyed updates/s. With a planning budget of 25k state updates/s per task, that is 40 tasks; use 64 for headroom, matching 64 Kafka partitions.

Warm state. Only items with real traffic get their own counters (deep dive 1). Say 20M (item, scope) pairs are warm on a busy day, each with 60 minute buckets, 24 hour buckets and 168 hourly baseline buckets: 252 × 4 B ≈ 1 KB. That is 20M × 1 KB = 20 GB, about 310 MB per task.

High-level design

Build one requirement at a time; by the end you have a design that works for a mid-sized app and needs the deep dives to survive an IPL final.

Users see the top K for a time window

Start with the smallest thing that works: apps send events to an ingest API, the API writes them to a Kafka topic, and one counter process reads the topic and keeps counts in memory. Kafka is there from day one: it absorbs the post-match spike, lets the counter restart where it stopped, and feeds other consumers such as the archive.

1. The app batches events and posts them; the ingest API checks them and writes them to the events topic.
2. The counter adds each event to a per-minute bucket for its item: count[item][minute] += 1.
3. Every 10 seconds it sums the right buckets for each window and picks the top K with a min-heap of size K, which costs O(n log K) for n items rather than a full sort.
4. It writes each finished list to Redis as one value, such as top:video:global:1h.
5. The top-K API reads the list and returns the first k entries.

Globally and per country or region

A region’s list is not a slice of the global list. The top hashtag in Tamil Nadu might rank 4,000th worldwide, so filtering the global top 1,000 by country would return nothing useful. Each scope needs its own counts.

1. The ingest API resolves country and region from the IP address, or from the profile when the user has set one, and adds them to the event.
2. The counter increments three counts per event: (global, item), (IN, item) and (IN-MH, item).
3. Lists are written per scope: top:hashtag:IN-MH:1h.
4. Small scopes get a minimum count, so a country with little traffic shows a shorter list rather than 1,000 items with two views each.

A “trending now” list

Ranking by count rewards the evergreen: a hashtag like #love is always large and therefore always on top. Instagram’s engineers described a trend as needing popularity, novelty and timeliness — many people, more than usual, right now. Measuring “more than usual” needs each item’s history, so add a trend scorer and a baseline store.

1. A filter step drops events from known bots, repeated views within a short gap, and items on the safety blocklist before anything is counted.
2. Each minute the counter hands the scorer the latest counts for active items.
3. The scorer compares them with the item’s baseline (its typical rate over the past week), computes a score, and keeps the top items by score per scope.
4. The trending lists go to Redis next to the top lists; the same API serves both.

Exact daily rankings

The live lists are allowed to be approximate. A published chart is not. Add a second, slower path that recomputes each day from the raw events — the classic split between batch and stream processing.

1. An archiver consumes the same topic and writes hourly Parquet files to object storage.
2. At 00:30 a Spark job reads the day, applies the same de-duplication and bot rules, and computes exact counts per (type, scope, item).
3. It writes the counts and the exact top lists to the warehouse; the charts API serves them as final.
4. A reconciliation step compares the day’s live lists with the exact ones and alerts if they drift apart.

That is a working design, and it breaks at scale everywhere that matters: one process cannot take 3M increments a second or hold 125 GB, one hashtag can be 20% of all traffic, “last hour” needs history the counter does not keep, and 75k reads a second need more than one Redis. The deep dives fix each of these.

Deep dives

How do we count a billion items in bounded memory?

The estimate gave 125 GB for one exact 24-hour window, and the distribution explains why that is wasteful. Views, hashtags and searches are heavily skewed: a few thousand items take a large share of all events, while hundreds of millions of items get one, two or three. Instagram’s trending team saw the same shape for hashtags — most get no more than three posts an hour — and found that simply not storing counters for them saved more than 90% of memory. Any item that can reach a top-1,000 list is, by definition, large. The question is how to find the large ones without paying for the small ones.

Bad: one exact hash map and a heap. Count everything, then pull the top K with a min-heap. You gain exact answers and simple code. You pay 125 GB for one window on one box, a single thread that cannot apply 3M increments a second, and almost all of that memory spent on items that will never rank. Sharding by item (next deep dive) makes exact counting possible — 125 GB over 64 tasks is about 2 GB each — but it does not make it cheap, and every extra window or scope multiplies it.

Good: a count-min sketch plus a heap of candidates. A count-min sketch is a small grid of counters, d rows by w columns, with one hash function per row. To count an item, hash it once per row and add 1 to that cell in every row. To estimate its count, read the same d cells and take the minimum. Other items that collide in a cell can only add to it, so the sketch never under-counts; taking the minimum keeps the row with the fewest collisions.

The guarantee comes from Cormode and Muthukrishnan’s analysis, worked through step by step in Stanford’s CS168 notes: with w = e/ε columns and d = ln(1/δ) rows, every estimate is within ε·N of the truth with probability at least 1 − δ, where N is the total count in the sketch — no matter how many distinct items there are. For our global daily window that is the 76 MB sketch from the estimates, accurate to 26k views. A sketch alone cannot list items, so keep a min-heap of about 2K candidates beside it: after each increment, estimate the item, and if that beats the heap’s smallest entry, insert or update it.

You gain constant memory and linearity: sketches with the same hash functions add cell by cell (Redis calls it CMS.MERGE) and can be subtracted, which matters for sliding windows. You pay three ways. The error is relative to the whole window, so it swamps small scopes — the Redis documentation says to treat estimates below error × total count as noise. Only the heap remembers which items are large. And collisions can occasionally make a small item look large.

Great: a heavy-hitters summary as a gate, with exact counters for the survivors. Counter-based summaries keep a fixed number of (item, count) pairs and decide on each arrival which item deserves a slot. In Metwally, Agrawal and El Abbadi’s Space-Saving algorithm, with m counters: if the item is tracked, add 1; if not, evict the item with the smallest count, give the newcomer that count plus 1, and record the evicted count as the newcomer’s maximum error.

Three facts from the paper make this practical. The counters always sum to N, so the smallest is at most N/m. Each count over-estimates by at most its recorded error, which is at most that minimum. And any item whose true count exceeds the minimum is guaranteed to be in the summary. With m = 1M counters the bound for the global day is 26B ÷ 1M = 26k — the same as the sketch, in about 48 MB — but now the summary is the candidate list, deterministically, with a per-item interval you can show or hide. Agarwal and colleagues later proved these summaries mergeable: add matching counters, subtract the (m+1)-th largest, and drop anything not positive. Apache DataSketches ships a Misra–Gries variant: 18 bytes per map slot, error at most 3.5/M of the total for a map of size M, and a mode that returns only items whose lower bound clears the threshold, so nothing listed is a false positive.

Now use the summary as a gate. Each counting task keeps a Space-Saving summary (or a sketch) per scope for the current and previous hour. Once an item’s estimate crosses a small threshold — say 20 events in an hour in that scope — the item becomes warm and gets exact minute and hour buckets, seeded with the summary’s estimate. Cold items never cost more than their share of the summary. That is where the 20M warm pairs and 20 GB in the estimates come from, instead of 125 GB per window.

Redis’s ready-made top-K type — HeavyKeeper’s decayed counts plus a min-heap of K, reporting which item each add pushed out — suits one server’s widget. At our scale its single key is a hot spot, and it can neither merge nor answer “exactly the last hour”.

How do we split the counting across machines and still get the right top K?

3M increments a second need about 64 counting tasks. How you route events to them decides whether the answer is right.

Bad: spread events evenly and merge each task’s top K. Round-robin is perfectly balanced and each task can keep a small heap. But the top K of a sum is not the sum of the top Ks: an item that is consistently just below the cut everywhere can be first overall, and no task ever reports it.

Good: partition by item key. Route every event for an item to the same task — in Flink, keyBy(item), which the documentation describes as sending all elements with the same key to the same parallel task. Now each item’s count lives in exactly one place, so a task’s count is the global count. The merge becomes provably correct: any item in the global top K is beaten by fewer than K items overall, so it is also in its own task’s top K, and the union of the task lists contains the answer. Instagram’s trending backend routes the same way, so a hashtag’s counter is never split across machines.

You can also cut merge traffic. Instead of the full top K, each task sends its top K′ (say 200) and its K′-th count as a bound: nothing it held back can be larger. If the merged K-th count is at least every task’s bound, the merged list is exact; if not, the merger asks the short tasks for more. You pay two things for keyed routing: a skewed key lands on one task, and tasks no longer balance automatically.

Great: keyed partitions, local pre-aggregation, and mergeable summaries where keys can’t be routed. During an IPL final, #iplfinal alone might get 200k events a second. Keyed routing sends all of them, times three scopes, to one task.

The arithmetic: 200k events/s × 3 scopes = 600k increments/s against a budget of 25k — 24 times over — and backpressure from that one task slows its upstream tasks and, through them, every partition. Pre-aggregation fixes it at the source: each of the 200 upstream tasks keeps a small map of (type, scope, item) → n and flushes it every second, so 1,000 #iplfinal events per task become one +1000 per scope, and task 17 receives 200 × 3 = 600 messages a second, 2.4% of its budget. It is the MapReduce combiner applied to a stream; you pay up to a second of latency and a bounded buffer. For a key so hot that even that is too much, split it into sub-keys (#iplfinal#0 to #iplfinal#7) with a tiny second stage that sums them. The general pattern is in hot keys, cache stampede and invalidation.

Sometimes you cannot key-partition — for example, each region counts locally and ships results to a global merger. Then ship mergeable summaries, never truncated lists: count-min sketches add cell by cell, and Space-Saving or Misra–Gries summaries merge by adding and pruning with a known error.

How do we answer “last 5 minutes”, “last hour” and “last 24 hours” from one stream?

Windows come in three shapes. A tumbling window has fixed, non-overlapping edges, like “today”. A hopping window — Flink calls it sliding — has a size and a slide, like “the last hour, recomputed every minute”. A decayed count has no edges at all: old events simply matter less. The product promises “last hour”, so you need something that moves smoothly without recounting an hour of events every few seconds.

Bad: one engine-managed sliding window per list. Declare a 24-hour window sliding every 10 seconds and let the stream processor handle it. You gain a one-line declaration. You pay in state: Flink assigns each element to every window it belongs to, so a 24-hour window with a 10-second slide means 86,400 ÷ 10 = 8,640 overlapping windows per key. Even with incremental aggregation, which stores one value per window rather than every element, that is 8,640 partial counts per item — and Flink’s documentation itself warns that a one-day window sliding by one second “might not be a good idea”.

Good: time buckets with running totals. Count each warm (item, scope) into tumbling one-minute buckets, keep the last 60 in a ring, and maintain running totals. When a minute closes, add the newest bucket to the hour total and subtract the bucket that just fell out. The 5-minute total is the sum of the last five buckets. Every hour, the 60 minutes roll up into one hour bucket, and the 24-hour total is the sum of 24 hour buckets.

You gain O(1) work per item per tick and a few hundred bytes per warm pair. You pay in edge precision: the hour list moves a minute at a time, and a 24-hour total built from hour buckets covers the last 24 full hours plus the current partial hour. If that matters, keep 288 five-minute buckets instead (about 1.2 KB per pair). Three more details make the buckets correct:

• Bucket by event time, not arrival time. A phone that was offline for 40 seconds still counts in the minute the view happened. Flink tracks progress with watermarks; give minute buckets an allowed lateness of about 2 minutes — Flink keeps a window until the watermark passes its end plus the allowed lateness — and send anything later only to the batch path.
• The cold tail slides too. For items still behind the gate, keep one count-min sketch per minute. Because the sketch is linear, the hour sketch is the sum of 60 minute sketches, and sliding means adding the newest and subtracting the oldest. Space-Saving summaries merge but cannot subtract, so if you use them, keep one per bucket and merge on demand.
• All time is a sum, not a window. An item’s all-time count is yesterday’s exact batch total plus today’s stream count. The all-time list changes slowly, so rebuild it every few minutes from warm items plus yesterday’s exact top 10,000.

Great: two resolutions for “top”, decay for “trending”. People read “most viewed in the last 24 hours” literally, so top lists keep the buckets. Trending has no literal edge, and there an exponentially decayed count is simpler: one number per item, updated as s ← s × 2^(−Δt/h) + n with half-life h. An hour-long half-life behaves like “recent activity with fading memory”, with no buckets and no edge effects. You gain constant state and smooth rankings; you pay the ability to say “exactly the last hour”. Redis’s Top-K type uses decay internally, and Instagram decays each trend’s peak score with a two-hour half-life so a trend does not vanish the moment the match ends.

How do we find what is trending, not just what is big?

Trending answers a different question: what is unusually active for itself right now? YouTube’s help pages say as much: its trending charts weigh view count together with how quickly views are growing (the “temperature”), the video’s age and how it compares with the channel’s recent uploads, so the most-viewed video of the day may not be first.

Bad: rank by count in the last hour. You gain reuse of the top lists. You pay with a trending tab that never changes: the always-popular items — #love, a perennial hit song, “weather” — win every hour. Instagram’s write-up gives the scale: #love gets more than 100k posts a day, so even 10k extra posts on one day do not make it unusual.

Good: growth against a baseline. Score each item by current rate ÷ baseline rate, where the baseline is its usual rate at this time. #love at 1.1× its normal level drops out; a hashtag at 80× rises. You pay at the small end: a tag that goes from 0 to 3 uses has an infinite ratio. Two fixes are standard: a smoothing floor — Instagram treats any hashtag with no history as if it had three posts an hour, which also let it drop counters for everything below that — and a minimum volume before an item may trend.

Great: popularity times novelty, with decayed peaks. Instagram scores a hashtag h at time t as S = p · ln(p / p̂), where p is its share of all activity in the latest 5-minute window and p̂ is its baseline share. The first factor rewards size, the logarithm rewards surprise, and a share near its baseline scores near zero. For the baseline it took the highest share seen over the past week, keeping 5-minute counters for recent hours and hourly ones for older data — simple, cheap and aggressive at suppressing items that are always noisy.

Work it through. #love: 0.009 × ln(0.009 ÷ 0.008) = 0.009 × 0.118 ≈ 1.06 × 10⁻³. #raininmumbai: 0.0012 × ln(80) = 0.0012 × 4.38 ≈ 5.26 × 10⁻³. A hobby tag with 4 uses against a usual 3 scores 0.00004 × ln(4/3) ≈ 0.012 × 10⁻³ — nowhere. One formula handles the giant, the spike and the noise.

Two refinements finish the score. Decayed peaks: keep each item’s best score and when it happened, decay it with a half-life (Instagram uses two hours), and rank by the larger of the live and decayed scores, so a trend fades gracefully after the final over. Seasonality: for items with a weekly rhythm, such as #mondaymotivation, compare with the same hour of the week, or use a z-score — how many standard deviations above its usual level the item is. Add a little hysteresis so items do not flicker in and out.

Then make the list hard to game, because a trending slot is valuable:

• Count people, not events. Rank by distinct users per item and window, using a HyperLogLog per warm item, so one account posting 500 times counts once.
• Weight by trust. Cap each account’s contribution and give new or low-reputation accounts less weight; coordinated campaigns tend to use young accounts.
• Exclude paid and unsafe traffic. YouTube leaves ad views out of trending and filters mature or disparaging content; do the same with a blocklist checked both before counting and again at serve time.
• Group duplicates. #iplfinal, #iplfinal2026 and #cskvsmi are one story. Instagram clusters tags by co-occurrence, edit distance and topic, and shows one representative.

How do we serve 75k list reads a second and keep them fresh?

The read side has a pleasant shape: few keys, tiny values, identical answers for everyone in a scope. The mistake is to let reads reach the counting machinery.

Bad: compute the list on read. A tempting version is one Redis sorted set per list, ZINCRBY on every event and ZREVRANGE on every read. Each command is cheap — sorted sets are a skip list plus a hash table, so an update is O(log n) — but the global list is one key on one shard receiving every event, 3M increments a second have to go somewhere, and a sorted set holds one score per member, so “last hour” would need a set per bucket. The other version, a GROUP BY item ORDER BY count LIMIT 50 against an analytics store per request, scans millions of rows 75k times a second. Both tie read load to write load.

Good: precomputed lists, swapped atomically. The merger already produces finished lists. Write each one as a single versioned value — top:video:IN:1h:v124 — then move a small pointer key to v124, so readers see either the old list or the new one, never half of each. All lists together are 138 MB, so every region holds a full copy on a few Redis replicas and each read is one GET. If a client needs rank ranges or a member’s rank, build a sorted set under a new name and RENAME it into place; ZRANGE on it costs O(log n + m) for m results.

Great: cache at the edge, filter and hydrate at the API, and never go blank. Lists are not personalised — YouTube’s trending charts are the same for every viewer in a country — so a CDN can cache each response.

• Edge caching. Send Cache-Control: max-age=15, stale-while-revalidate=30. The traffic is concentrated: say 300 hot keys (global and big-country lists at common K values) across 50 edge locations, each refetched once per 15 seconds, is 300 × 50 ÷ 15 = 1,000 requests/s reaching the API instead of 75k.
• Filter at serve time. Check every item against the takedown and safety blocklist on the way out, so a removed video leaves trending within one cache TTL.
• Hydrate. Lists carry IDs and counts; the API adds titles and thumbnails from an item cache.
• Stale beats empty. If the pipeline stalls, keep serving the last good version with its as_of time and alert when it is more than 5 minutes old. An old trending list is a minor embarrassment; a blank tab during the final is an incident.

You gain reads that are independent of the counting pipeline; you pay up to 15 seconds of extra staleness. How fresh is fresh enough is a product call: YouTube updates its trending charts roughly every 30 minutes, while a live-match surface wants seconds.

How do we publish numbers that are exact?

The live numbers are approximate for good reasons: cold items are only estimated, events later than the allowed lateness are dropped from the stream, and bot rules improve after the fact. That is fine for a widget and wrong for “most-viewed video of the day”.

Bad: publish the stream’s numbers, or make the stream exact. Live counts can be off by thousands and cannot be recomputed when a bot farm is discovered on Tuesday; an exact stream pays 125 GB per window for the long tail you designed away.

Good: a batch path beside the stream. This is the Lambda shape: the speed path keeps live lists fresh, and a nightly batch job recomputes each day from the archive, exactly, with all late events present. Charts and all-time totals come only from batch. You pay for two implementations of “what counts as a view”, and they drift: a de-duplication window of 30 seconds in one and 60 in the other, and the two numbers never agree.

Great: one definition, two runtimes, and reconciliation. Put the rules for a countable event — de-duplication, bot filters, scope mapping — in one library both paths use, or run the same stream job in batch mode over the archive (the Kappa-style answer). Replaying from Kafka instead needs the events retained there: 7 days is 5.2 TB × 7 ≈ 36 TB before replication, against 1.3 TB a day in compressed object storage, so the archive is the cheaper source for anything longer than a few days. Then reconcile every day.

Reconciliation asks two questions: how many of the exact top 100 appear in the live top 100, and does every live count sit within its stated bound of the exact one? Alert when more than a couple of items differ or any count falls outside its bound — that is almost always definition drift or a pipeline bug, not sketch error. The exact daily counts then become the next day’s all-time baseline and the trend scorer’s history. This is the same contract as in delivery guarantees: ingest at least once, de-duplicate by event_id, and let the slow path be the source of truth.

The final design

Put it together. Two Flink stages and a merger do the counting; Redis and a CDN do the serving; object storage and Spark keep the truth.

Follow an event and a read through the system:

1. Ingest. Apps batch events with an event_id; the ingest API adds country and region and writes them to a 64-partition Kafka topic.
2. Clean and combine. The first Flink stage drops duplicates and bot traffic, applies the blocklist, tags each event with its three scopes and sums counts per (type, scope, item) for one second. A viral hashtag leaves this stage as 600 messages a second, not 600k.
3. Count and score. The second stage is keyed by item, so each item lives on one of 64 tasks. Cold items sit in a per-scope summary; warm ones get minute and hour buckets with running totals in event time, plus a trend score against their weekly baseline and a distinct-user count.
4. Merge. Every 10 seconds (5-minute lists) or every minute (the rest), each task sends its top K′ per list with a bound; the merger proves the global top K or asks for more.
5. Publish. The merger writes each list as a new version in Redis in every region and flips the pointer.
6. Read. Clients hit the CDN; misses reach the top-K API, which reads Redis, removes blocked items, adds titles and returns the list with its as_of time.
7. Archive. The same Kafka topic is written hourly to object storage as Parquet and kept for 30 days.
8. Recount and reconcile. At 00:30 a Spark job recomputes the day exactly with the shared rules, publishes the daily charts and all-time totals, and checks the live lists against them.

Check it against the requirements. Ingest scales with Kafka partitions and Flink tasks: 1M events a second become 3M scope increments and, after pre-summing, about 1M keyed updates — roughly 16k per task across 64 tasks, under the 25k budget. Memory is bounded by the warm set, about 20 GB in total, because the long tail lives in fixed-size summaries. The 5-minute lists are at most about 30 seconds stale and the rest within 2 minutes. Reads are CDN hits or single Redis GETs, well inside 50 ms at p99, and a stalled pipeline leaves the last good list in place. Live counts carry a stated bound, charts are exact, and trending counts distinct, trusted users, which makes it expensive to fake.

What interviewers look for by level

Follow-up questions

What if trending must be personalised?

Keep the scope lists as the candidate pool and personalise at read time: take a scope’s top 500 trending items and re-rank them by the user’s languages, followed topics and location, using the same features a recommendation feed uses. Cache per segment — language × region, a few thousand combinations — rather than per user, so the CDN still absorbs most reads. You gain relevance; you pay a ranking call on each request, a lower cache hit rate, and a harder story about why something is “trending” for one person and not another.

What if we rank by unique viewers or watch time instead of events?

Watch time is just a weighted increment: pre-aggregation sums seconds instead of ones, and both count-min sketches and Space-Saving accept weighted updates. Unique viewers is harder because distinct counts do not add — 100 viewers in each of 60 minutes is not 6,000 viewers in the hour if the same people watched throughout. Keep a HyperLogLog per warm item per bucket; HyperLogLogs merge, so the hour is the merge of 60 minutes, but they cannot subtract, so rebuild each window from its buckets instead of keeping a running total. Gate the long tail exactly as before.

What if analysts want arbitrary windows and filters?

“Top hashtags in Pune between 2 and 4 pm last Tuesday, Android only” cannot be precomputed: the combinations explode. Write minute-level rollups for warm items — (item, scope, minute, count, plus a few dimensions) — into a columnar analytics store and answer with GROUP BY … ORDER BY count DESC LIMIT 50. Seconds of latency and tens of queries a second are fine for analysts, and the store stays well away from the 75k-a-second product path. See OLTP vs OLAP and columnar storage.

What if we run in several regions?

The simplest answer ships all events to one counting region: the keyed merge stays exact, at the cost of about 200 MB/s of cross-region traffic at peak and a dependency on that region. The more resilient answer counts in each region — country and regional lists usually belong to one region anyway — and builds global lists by merging per-region summaries, never per-region top lists, since the same item is counted in several regions. Serving is easy either way: 138 MB of lists replicate everywhere. More in multi-region and active-active.

What if a trending video is taken down?

The serve-time blocklist hides it within one CDN TTL, and a CDN purge makes that immediate. Add it to the ingest filter so new events stop counting, drop its state, and exclude it from the batch charts. Lists must still have K entries, which is one more reason tasks send K′ with a margin: rank K+1 is already at the merger, ready to move up.

How to say it in the interview

“I’ll design top-K and trending for a big video and social app: about a million events a second at an IPL-final peak, a billion distinct items a day, and lists for the last 5 minutes, hour, day and all time — globally and for about 230 countries and regions — plus a trending list.

The shape is a funnel. Apps post events to an ingest API that writes them to Kafka. A first Flink stage drops duplicates and bots, tags each event with its global, country and region scopes, and sums counts per item for one second, so a viral hashtag becomes hundreds of messages a second instead of hundreds of thousands. A second stage is keyed by item, so each item’s count lives on exactly one of 64 tasks. That matters because the top K of a sum is not the sum of per-server top Ks: an item that is eleventh everywhere can be first overall.

Exact counters for a billion items would cost about 125 gigabytes per window, nearly all of it for the long tail. So each task keeps a fixed-size Space-Saving summary or count-min sketch for cold items — sized for an error of about 26 thousand views on the global daily list — and gives exact minute and hour buckets only to items that cross a threshold. Windows are running sums: add the newest minute, subtract the oldest.

Trending is a different score: the item’s current share times the log of its ratio to its own baseline, with smoothing for tiny items, decayed peaks, and distinct, trusted users so it is hard to game.

Tasks send their top lists to a merger, which writes versioned lists — about 138 megabytes in total — to Redis in every region. Reads go through a CDN with a 15-second TTL, so 75 thousand reads a second become about a thousand at the API, and the 5-minute list is at most about 30 seconds stale.

Finally, a nightly Spark job recounts each day exactly from the archive, publishes the official charts and reconciles them against the live lists.”

Concepts used in this design

• Count-min sketch and HyperLogLog — the sketches that bound memory and count distinct users.
• Bloom filters — the count-min sketch’s simpler cousin, with the same one-sided error.
• Kafka — the durable, replayable event log that feeds both paths.
• Flink and stream processing — keyed state, windows, watermarks and eager aggregation.
• Batch vs stream processing — the live approximate path and the exact nightly path.
• Redis — versioned lists, sorted sets and its built-in sketch types.
• Hot keys, cache stampede and invalidation — why one viral item needs pre-aggregation.
• Backpressure and load shedding — what one overloaded task does to the whole job.
• Content delivery network — absorbing 75k identical reads a second.
• Scaling writes — partitioning and batching a firehose.
• Scaling reads — precomputing the answer and caching it.
• Delivery guarantees — at-least-once ingest with de-duplication by event ID.
• OLTP vs OLAP and columnar storage — where exact charts and ad-hoc questions live.
• Design a live leaderboard — the bounded, exact cousin of this problem.
• Design ad click aggregation — the same pipeline when every count moves money.

References and further reading

1. Approximate Heavy Hitters and the Count-Min Sketch (Stanford CS168 lecture notes, Roughgarden and Valiant)web.stanford.eduHow a count-min sketch updates and answers, why it only over-counts, width e/ε and depth ln(1/δ), and the sketch-plus-heap recipe for heavy hitters.
2. Efficient Computation of Frequent and Top-k Elements in Data Streams (Metwally, Agrawal, El Abbadi)cs.ucsb.eduThe Space-Saving algorithm: replace the smallest counter, record its value as the error, min ≤ N/m, and every item above min is guaranteed to be tracked.
3. Mergeable Summaries (Agarwal, Cormode, Huang, Phillips, Wei, Yi)cs.utah.eduLinear sketches such as count-min merge trivially; Misra–Gries and Space-Saving merge by adding counters and subtracting the (k+1)-th largest.
4. Apache DataSketches: Frequent Items sketches overviewdatasketches.apache.orgA production Misra–Gries variant: 18 bytes per map slot, worst-case error 3.5/M of the total, upper and lower bounds per item, and the no-false-positives query mode.
5. Redis documentation: Top-Kredis.ioHeavyKeeper with exponential decay, a hash table of counts plus a min-heap of K, and TOPK.ADD reporting the item it pushed out.
6. Redis documentation: Count-min sketchredis.ioCMS.MERGE, and the rule that estimates below error × total count should be treated as noise.
7. Redis documentation: Sorted setsredis.ioSkip list plus hash table, O(log n) updates, ZINCRBY, and ZRANGE costing O(log n + m).
8. Apache Flink documentation: Windowsnightlies.apache.orgkeyBy sends a key to one task, sliding windows copy each element into every window (a 1-day window sliding by 1 s is a bad idea), incremental aggregation, allowed lateness.
9. Trending on Instagram (Instagram Engineering)medium.com5-minute counters over 7 days, a popularity-times-novelty score against a baseline, smoothing that saved over 90% of memory, a 2-hour half-life, partitioned scorers.
10. YouTube Help: Trending chartssupport.google.comTrending signals include view count and how fast it grows, charts are the same for everyone in a country, refresh roughly every 30 minutes, and ad views are excluded.