Top-K Shared Articles

What is being asked

Users share articles all day. Design the service that returns the top K articles by share count for sliding time windows, updated within a minute or so.

Requirements

Functional

• Record a share event: article id and time.
• Return the top K (say 10 to 100) for the last hour, 24 hours and 7 days, optionally per country.

Non-functional

• Tens of thousands of events per second.
• Results a minute old are fine; small errors in counts far down the list are acceptable.
• Reading the list must be very fast, since it sits on a home page.

Design

1. The share endpoint validates the request and writes an event to a log, partitioned by article id so all events for one article reach the same worker.
2. A stream processor counts shares per article per one-minute bucket and stores the buckets.
3. A window is the sum of its buckets: the last hour is 60 buckets. Every minute the newest bucket is added and the bucket that slid out is subtracted, so nothing is recounted.
4. Each worker keeps a small heap of its local top K; a merger combines them into a sorted set per window in Redis.
5. The read API returns the sorted set's top entries, which is a single cheap command.

Key decisions and trade-offs

• Exact or approximate. Exact counts for every article cost memory. A count-min sketch with a heap gives the top K with a small, bounded error and a fraction of the memory.
• Bucket size. One-minute buckets make the hourly window smooth; daily and weekly windows can use hourly buckets to save space.
• Late events. A watermark accepts events a few minutes late and drops or separately counts older ones.
• Per-partition top K must be larger than K, since an article just outside one worker's list may be in the global top after merging.

Follow-up questions

• How would you stop bots from pushing an article into the list?
• How do you recover the counts after a processor crashes?
• How would you add top K per topic or per country without multiplying the cost?
• What if K must be 10,000?