Design a trending topics service

One account can invent millions of junk tags. A count-min sketch keeps memory fixed instead.

• How it works. A sketch is a small grid of counters, here 5 rows by 65,536 columns. Each row has its own hash function. To add a key, hash it once per row and add 1 to one counter in each row. To ask for a count, read the same 5 counters and take the smallest.
• Why the smallest. Other topics collide into the same counters and only ever add to them. So every counter is at least the true count, and the smallest one has had the least interference. A sketch can over-count, but it never under-counts.
• The error, in numbers. With 65,536 columns, each added count can inflate another by about 2.718 ÷ 65,536 ≈ 0.0000415, and with 5 rows the bound holds with probability about 99.3%. At the peak a worker sees about 271 events a second and adds 2 counts for each, about 32,500 a minute. One minute over-counts by at most about 1.35 mentions, and 15 minutes by about 20. A topic at the floor of 300 might read 320. A topic with 4,000 mentions reads at most 0.5% high.
• Memory. 65,536 × 5 × 4 bytes is 1.31 MB for a minute, and 60 minute buckets are about 79 MB per worker. It does not grow with the number of topics.

Region and topic together. The key is the region with the topic, and each event also updates the worldwide key. Without a region in the key, a topic surging in one small region would never reach a worldwide list. Doubling the counts doubles the error, so the sketch is twice as wide.

Sliding window. Keep one sketch per minute. The last 15 minutes is the sum of the last 15 estimates, and a sketch is dropped when it is 60 minutes old. Nothing is ever decremented.

Top K. A sketch answers how many for a topic, but it cannot list topics. So each worker also keeps 13 min-heaps, one per region and one worldwide, of the 200 keys with the highest estimated 15-minute count. On each event it updates the sketch and takes the estimate. If the key is in its heap, it updates it. If not, and the estimate beats the heap's smallest entry, it swaps it in. Once a minute it re-estimates the heap's members, because their window has moved.

Merging. The stream is partitioned by topic, so each topic is counted on exactly one worker. The scorer just joins 128 workers' lists, with no double counting. Partition by post or by user instead, and one topic would be split across many workers, each seeing a part, so merging top lists would miss it. The price is that one very hot topic loads one partition.

People want to see what is unusual, so compare the present with what is normal for the topic.

• Baseline. The expected count is the average of the same clock hour on each of the last 7 days, divided by 4 to match the 15-minute window. Each hour, a worker adds its 60 minute sketches into one hourly sketch and saves it. 128 workers × 24 hours × 7 days is 21,504 sketches of 1.31 MB, about 28 GB. To read a baseline, ask only the sketch of the worker that owns the topic, with the region and topic key. Its error bound is the same 20 mentions.
• The score. Use a smoothed ratio: (current + 50) ÷ (expected + 50). The 50 is a smoothing constant.
• Floor. Only a region and topic with at least 300 mentions in the window can be listed, and each region is scored on its own counts. This removes tiny topics before any ratio is taken, and the sketch error of about 20 is small beside 300.

Three topics show what the smoothing does:

• A marathon topic with 4,000 now and 200 expected scores 4,050 ÷ 250 = 16.2.
• A big sport topic with 60,000 now and 55,000 expected scores 60,050 ÷ 55,050 = 1.09. It is large, but it is not unusual.
• A junk topic with 5 now and 0 expected scores 55 ÷ 50 = 1.1. Without smoothing the ratio would be infinite, and it would top the list.

A topic with no history has an expected count of 0, so it can trend only through a large current count: 3,000 now scores 3,050 ÷ 50 = 61. A bigger smoothing constant favours big topics, and a smaller one favours small ones. Tune it by comparing the lists with what editors would pick.

Stable lists. If the list reshuffles every minute it looks broken. Use two thresholds. A topic enters at a score of 3 or more, and stays until it falls below 2. Then a topic hovering near the line does not flicker in and out.

• Dedupe. Count a user once per topic per 15 minutes. The worker keeps a set of hashed user and topic pairs that expire after 15 minutes. At about 271 events a second at the peak that is 244,000 pairs of 16 bytes, about 3.9 MB. A user has one region, so one set covers both keys. The partitioning means the same pair always reaches the same worker, so nothing is shared.
• New accounts. Count mentions in tenths. A new account counts 3 tenths, an established one 10. For the heap topics only, the worker also tracks the share of weight from new accounts. If it passes 60%, the score is cut sharply and the topic goes to review.
• Blocklist. Banned terms are dropped on arrival, and the list is reloaded every minute so a new ban applies within about 60 seconds.
• Hold new topics. A topic that was never seen before and is rising fast is kept off public lists until a classifier or a person has looked at it. A new topic can be a breaking story, but it can also be an attack.

Serving. The scorer builds 13 lists a minute: 12 regions plus worldwide, each from that region's own scores. Each has 50 topics, so the lot is about 65 KB. They go into the cache with a 2-minute TTL, so if one refresh fails the lists are a little stale, not empty. The API only reads the cache. At 14,000 reads a second at the peak, one small cache cluster, or a CDN in front of the API, is plenty. The app can poll once a minute, and no push channel is needed.

If a worker restarts. It rebuilds its sketches by replaying the last 60 minutes from the stream, which keeps events longer than that. Until it catches up, the scorer ignores its list and keeps the previous result for its topics. Use the event's own time, not the arrival time, to pick the minute bucket, so a replay lands in the right place.