Design trending topics / top-K over a sliding window

01The design, in the six-step framework

1. Requirements

Functional

• Show the top 10 hashtags (or songs, searches, videos) by count over the last hour, updated every few seconds, globally and per region.
• Also answer "top 10 over the last day" and "the count of a given tag in the last hour".
• Out of scope: personalised trends, spam and coordination detection beyond simple filters.

Non-functional

• Events: 1 billion hashtag mentions a day (12,000/s average, 100,000/s at peak); 100 million distinct tags a day, heavy-tailed.
• The displayed list lags real time by under 10 s; the list is read 1 million times a minute and must be served from memory.
• Counts in the top list are accurate to within a few percent; exact counts available for the day in batch.
• No single machine holds the whole stream; a machine failure costs at most a few seconds of a region's counts.

2. Core entities

• Event: tag, timestamp, region, source (post id or query id), user or device id.
• Minute bucket: (region, minute) → counts by tag for that minute (exact map of tags seen, or a sketch) plus that minute's local top-K.
• Window result: (region, window) → ordered top-K with counts and the time it was computed.

3. API

• GET /trending?window=1h|24h&region=&k=10 → list of (tag, approximate count, rank change).
• GET /tags/{tag}/count?window=1h → approximate count.
• Internal: POST /events batches from the posting and search services onto the stream.

4. High-level design

From a hashtag in a post to the trending list:

1. The posting service extracts tags and publishes one event per tag to the stream, partitioned by tag so all events for one tag reach one counter.
2. Each counter keeps, per region, a ring of 60 one-minute buckets; it adds the event to the current bucket and maintains a running sum per tag for the sliding hour (add the new minute, subtract the minute that fell out).
3. Every 5 seconds each counter sends its local top 100 for each window to the merger, which merges 20 partition lists into the global top 10 per region and writes it to the results store.
4. The API serves the results from memory; the daily batch computes exact 24-hour tops from the archive.

5. Deep dives

Sliding window versus tumbling window, and why minute buckets

A tumbling hour (reset at the top of the hour) shows an empty list at 10:01, which is useless. A sliding hour needs counts that both enter and leave: subtracting old events requires remembering them. Minute buckets make that cheap: keep 60 per-minute tag maps and a running total per tag; each minute, drop the oldest bucket by subtracting its counts. The error is a minute of granularity, acceptable for "last hour". For "last 24 hours", keep 24 hourly buckets built by rolling up minutes. This is standard windowed stream processing; late events (a post whose event arrives two minutes late because of a slow producer) are added to the bucket of their event time if it is still in the ring, else dropped and counted only by the batch.

Exact maps or sketches?

Choice: exact maps per partition at this scale, because 100 MB per bucket across 20 partitions is cheap and exactness simplifies debugging; mention the sketch as the answer when the key space is a billion (unique URLs, IPs) and memory would not fit. The merger needs each partition's top 100, not top 10, because a tag that is 11th on every partition could be 1st globally; sending the top 100 makes that error negligible and is still a tiny message.

Partitioning by tag: hot tags and the global merge

Partitioning by tag gives each counter the complete count for its tags, so the partition-local top-K is exact for those tags and the merge is a simple k-way merge. The risk is a tag so hot that its partition cannot keep up (a world event at 50,000 events a second on one tag). Two mitigations: pre-aggregate in the producers (a posting service batches events for a second and sends counts rather than events), and split a known-hot tag across sub-partitions whose counts are summed by the merger. The merger itself is per region and is tiny: 20 lists of 100 entries every 5 seconds.

Failure, replay and freshness

A counter that crashes loses its in-memory buckets. Recovery is replay: it rewinds its stream partition by one hour and rebuilds the ring, which at 5,000 events a second takes a minute or two of catching up, during which the merger uses the last good list for that partition. To shorten that, counters checkpoint their buckets every minute to a store. Freshness is set by the 5-second merge cadence and the stream lag; the results store carries a computed-at timestamp so the API can show "updated 6 seconds ago" and alert when the lag grows. Abuse filtering (a minimum number of distinct users per tag, blocklisted tags) sits in the merger, where it is cheap and central.

Ranking by rise, not just by size

A list ranked by raw count in the last hour is dominated by evergreen tags that are always large. Products usually rank by acceleration: the count in the current window divided by the expected count from the previous window or the same hour last week, with a minimum absolute count so noise does not rise. That needs one more number per tag (the previous window's count), which the bucket ring already has, and a baseline table built by the daily batch. Say that the score is a product decision and that the pipeline exposes both numbers so the ranking formula can change without touching the counting.

6. What a strong answer sounds like

• Explain sliding versus tumbling windows and the bucket ring with running sums; that is the core idea.
• Do the memory arithmetic for exact maps and for a sketch, then choose with a reason.
• Partition by tag, send partition top-100 lists to a central merger, and handle the one tag that is too hot.
• Describe recovery by replay and checkpointing, and where the freshness number comes from.
• Expect follow-ups on per-city trends (a region dimension in the bucket key), on ranking by acceleration instead of count (store the previous window and rank by ratio), and on exact daily results.
• Common mistake: a database query with GROUP BY tag ORDER BY count over the last hour on every request.

02Where this question was reported

• Hello Interview · Commonly asked L5
• Hello Interview · Commonly asked L6
• PracHub · 'Twitter hashtag metrics aggregator', Dec 2025
• Blind · Top-K over a sliding window