Katkat
Back

Design a Top-K trending items service

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a high-throughput, distributed system that maintains a real-time ranking of the most popular items across a massive global user base.

Problem Statement

Design a service that tracks and returns the Top-K trending items (e.g., product IDs, hashtags, or news articles) based on the number of clicks or views in the last hour. The system must support millions of concurrent users and handle high-volume write traffic.

Functional Requirements

  • record_click(item_id): Registers a view for a specific item.
  • get_top_k(k): Returns the top K most clicked items within the sliding 60-minute window.

Non-Functional Requirements

  • Low latency for both reads and writes.
  • High availability and fault tolerance.
  • Scalability: The system must handle 100,000 requests per second.
  • Accuracy: It is acceptable to have a small margin of error (approximate Top-K) if it significantly improves system performance.

Deliverables

  • High-level architecture diagram or description.
  • API design.
  • Data schema and storage choices.
  • Strategy for handling the sliding time window.
  • Discussion on trade-offs between consistency and performance.

Examples

  • If k=3 and items [A, B, C, A, D, B, A] are clicked, get_top_k(3) should return [A, B, D] or similar ordered list.
  • Assume item IDs are 64-bit integers.

Hints

Hint 1

Consider using a distributed streaming platform like Kafka to buffer incoming click events and decouple ingestion from aggregation.

Hint 2

Think about using a Count-Min Sketch or similar probabilistic data structures to maintain frequency estimates in memory if the number of unique items is extremely large.

Hint 3

For the sliding window, consider partitioning time into smaller buckets (e.g., 1-minute intervals) and aggregating these buckets to form the hour-long view.

Follow-up questions

  • How would you handle a 'hot key' problem where a single item receives a massive, disproportionate percentage of traffic?
  • If the requirement changed from 'last hour' to 'all-time', how would your storage strategy change?
  • How would you ensure the system remains accurate if one of the aggregator nodes crashes during the calculation?