Design trending topics (top-K heavy hitters)

If you rank by raw count, the list never changes: #goodmorning, #cricket and #bollywood would trend every day. Trending is about acceleration. A simple, explainable score compares the current rate with an expected rate: score = (current_count - expected) / sqrt(expected + c), a z-score-like value, where current_count is distinct users in the last 10 minutes and expected comes from an EWMA baseline for the same topic, ideally for the same hour of the day and day of week. The constant c and a minimum volume threshold stop a topic going from 1 to 5 mentions from scoring infinitely. Use distinct users, not posts, so one account spamming 1,000 posts counts once. Add decay so a trend that peaked an hour ago slides down even if counts stay high. For brand-new topics with no baseline, use a category-level prior. Tune parameters by replaying past days and checking whether real events (a wicket, an election result) surface within a few minutes.

With partitioning by (topic, region), exact counts in Flink keyed state are often fine: 50M keys per hour spread over 20+ tasks is a few GB in RocksDB. Sketches matter when memory per task is limited or keys are truly unbounded. A Count-Min Sketch is a 2D array of counters (depth d hash functions x width w); each event increments one counter per row and the estimate is the minimum across rows. It never undercounts and overcounts by at most about e/w x total events with high probability, using a few MB. A CMS alone cannot list the top items, so pair it with a min-heap of size K: after each update, if the estimated count beats the heap minimum, insert it. Space-Saving (Misra-Gries family) is an alternative that directly keeps K counters and has error bounds. In the interview, say you would start exact with partitioned state and move to CMS + heap or Space-Saving for the long tail, and that approximate counts are acceptable because users see '25K posts'.

Keying the counter job by topic means a single topic like #INDvsPAK during a final can send 50k events/s to one task, which then falls behind and delays every trend in that partition. The fix is two-stage aggregation. Stage one: each extraction task pre-aggregates locally for a short time (e.g. 1-5 seconds) and emits (topic, region, partial_count, partial_HLL) instead of one event per post; this alone cuts traffic by 100-1,000x for hot topics. Alternatively, salt the key ((topic, salt 0-15)) so a hot topic spreads across 16 tasks, then a second stage combines the 16 partial counts. HyperLogLogs merge cleanly, which is why they work for distinct users across stages. Top-K follows the same pattern: each task computes a local top-K, and one merger task combines them; this is correct as long as each topic's full count lives in exactly one task after the second stage.

Trends are a target: political campaigns, crypto spam and bot farms try to push hashtags. Defences are layered. At input, weight events by account trust (age, verified phone, past behaviour) and drop known bots. In scoring, count distinct users and look at diversity: a topic driven by 2,000 accounts created last week that all follow each other is suspicious; network-diversity features can down-rank it. Duplicate-text detection catches copy-paste campaigns. At output, run a policy classifier on trend names, check a blocklist, and give trust & safety a tool to remove a trend with an audit log. In India, also handle region-specific legal takedown orders. Store the score history so you can explain why a topic trended during an appeal or audit.

Exact counts are simple to explain and debug and fit in partitioned state at moderate scale. Sketches (CMS, Space-Saving, HLL) save memory and network but add error. Use HLL for distinct users always; use CMS/Space-Saving for the long tail only if memory demands it.

True sliding windows are expensive. Use 1-minute tumbling buckets and sum the last N buckets for a 'sliding' view; it is cheap and accurate to one minute.

A batch job every 5 minutes on the data lake is simpler but misses the 2-minute freshness target and wastes work re-reading data. Streaming with Flink keeps state incrementally; Kafka retention allows replay if the job needs a fix.

Pull with short caching is enough: trends change once a minute and are the same for everyone in a region, so a CDN/Redis cache absorbs reads cheaply.

Single key overload in the counting job. Local pre-aggregation and key salting with a second merge stage, as above.

Each post counts in city, state, country and global scopes, multiplying events by ~4. Compute only for regions with enough users; roll up smaller cities into states.

Everyone opens the app when a match ends. Trends are identical per region, so serve from CDN with a 30-60 s TTL; Redis sees only cache misses.

Flink restores state from the last checkpoint (every ~30 s) in S3 and replays Kafka from the stored offsets, so counts stay consistent. Meanwhile Redis keeps serving the last published trends with their generated_at timestamp.

Trends get stale. Alert on lag and freshness; the scoring job uses event time with watermarks so late events are counted in the right minute bucket. Drop events later than a few minutes rather than block.

Trust & safety blocklist takes effect on the next read via the Trends API filter, without waiting for the pipeline. All removals are logged.