Katkat
Back

Design a Top-K Ranking Service

LinkedInSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a distributed, low-latency system capable of maintaining and serving a real-time 'Top-K' list of items (e.g., trending hashtags) across a massive stream of incoming data.

Problem: Real-time Trending Hashtag Service

Design a service that processes a high-volume stream of hashtags from a global social media platform and serves the 'Top 10' trending hashtags at any given moment. The system must be highly available and provide low-latency reads for the Top-K dashboard.

Functional Requirements:

  1. ingest(hashtag): Record that a hashtag has been used.
  2. getTopK(k): Return the top k most frequent hashtags in the last hour.

Non-Functional Requirements:

  • Scale: Handle 100,000 requests per second (RPS) of incoming hashtag data.
  • Latency: getTopK should return in under 200ms.
  • Accuracy: Minor approximation in counts is acceptable if it significantly improves system performance.

Design Guidelines:

  • Describe the ingestion pipeline (e.g., message brokers, stream processing).
  • Define the storage strategy for handling high-frequency updates.
  • Explain how you would handle sharding if the number of unique hashtags exceeds the memory capacity of a single machine.
  • Propose an approach to handle the 'sliding window' requirement (last 60 minutes).

Hints

Hint 1

Consider using a heavy-hitter algorithm like Count-Min Sketch to estimate frequencies with a fixed memory footprint.

Hint 2

Think about using a distributed streaming framework like Apache Kafka to decouple ingestion from processing.

Hint 3

For the sliding window, consider maintaining multiple smaller time-bucket counters that aggregate into a global view.

Follow-up questions

  • How would you handle a scenario where a few 'viral' hashtags receive 90% of the total traffic (hot keys)?
  • If we need strictly accurate counts instead of approximations, how would your architecture change?
  • How would you implement the cache invalidation strategy if the top-k results are cached at the edge?