Design a Top-K System

Reference Answer

For a full example answer with detailed architecture diagrams and deep dives, see our Design Top K guide.

Problem Statement

Design a system that efficiently retrieves the top-K items -- songs, videos, hashtags, products, or any entity -- based on user activity or engagement metrics within configurable time windows. The system must handle real-time data aggregation at massive scale and support queries like "top 10 songs in the last 7 days" or "trending hashtags in the past 24 hours."

At Atlassian, this manifests as surfacing the top-K Confluence pages, Jira issues, or Bitbucket repositories by popularity or engagement. The core challenge is ingesting millions of events per second, maintaining accurate windowed counts despite late-arriving or out-of-order data, and serving ranked results with sub-100ms latency. Interviewers probe whether you can separate the write aggregation path from the read serving path, handle hot keys caused by viral content, and make sensible tradeoffs between freshness, accuracy, and infrastructure cost.

Key Requirements

Functional

• Time-windowed rankings -- retrieve the top K items for fixed windows such as last hour, last day, last 7 days, and all-time, with each window updating independently
• Segmented results -- scope rankings by dimensions like geography, category, product area, or individual user
• Configurable K and tie-breaking -- support variable K values from 10 to 1,000 with stable, deterministic ordering when scores are equal
• Pagination -- allow clients to page through large result sets with consistent snapshots across paginated requests

Non-Functional

• Scalability -- handle 10M+ events per second during peak hours with independent scaling of write throughput and read capacity
• Latency -- p99 read latency under 100ms for top-K queries; write-to-visibility freshness under 10 seconds
• Reliability -- tolerate datacenter failures and node crashes without losing more than a few minutes of ranking history
• Consistency -- eventual consistency is acceptable; rankings should converge within seconds

What Interviewers Focus On

Based on real interview experiences at Atlassian, these are the areas interviewers probe most deeply:

1. Write Path and Event Aggregation

Interviewers want to see how you handle millions of incoming events without creating database hotspots. They test whether you understand stream processing, event deduplication, and the distinction between raw events and aggregated counts.

Hints to consider:

• Use Kafka as a durable buffer between event producers and consumers, partitioned by item ID for ordered processing
• Apply tumbling or sliding windows in Apache Flink with watermarks to handle late-arriving events while still closing windows on time
• Batch writes to the storage layer (flush every few seconds or after accumulating a threshold of events) to reduce write amplification
• Separate the ingestion layer from aggregation so each can scale independently

2. Handling Hot Keys and Skew

Viral content creates massive skew where a single item receives orders of magnitude more events than average. Interviewers assess whether you recognize this and can propose solutions beyond naive sharding.

Hints to consider:

• Implement split counters where hot keys are sharded into N sub-counters and merged periodically by a combiner job
• Use approximate data structures like Count-Min Sketch or HyperLogLog when exact precision is not required
• Apply skew-aware routing where the ingestion layer dynamically distributes hot item events across more partitions
• Separate the frequently-changing "top 10" from the long tail using tiered storage with different update frequencies

3. Serving Top-K Efficiently

Computing top-K by scanning all items on every query is a critical mistake. Interviewers look for pre-computation strategies and cache-friendly designs.

Hints to consider:

• Pre-compute top-K lists per window and segment using Flink windowed aggregations that emit ranked results to Redis sorted sets
• Use min-heaps of size K during aggregation to maintain candidates in O(N log K) instead of fully sorting
• Implement tiered caching: application cache with a 30-second TTL, CDN with a 1-minute TTL, and Redis as the authoritative source refreshed every few seconds
• Store results with versioned keys to enable atomic swaps during recomputation

4. Time Window Management

Different windows have different update cadences and cost profiles. Interviewers probe whether you understand sliding versus tumbling windows and how to balance freshness with infrastructure cost.

Hints to consider:

• Use tumbling windows for fixed-duration leaderboards (daily resets at midnight) and sliding windows for "last 24 hours" that continuously roll forward
• Trade off freshness for cost: update "last hour" every 30 seconds but "last 30 days" only every 5 minutes
• Handle late-arriving events with allowed lateness in your stream processor and emit final window results after the lateness window closes
• Implement window expiration through TTLs on Redis keys or partition-level deletion in the backing store

Suggested Approach

Step 1: Clarify Requirements

Start by confirming the scope. Ask what types of events are tracked (views, likes, clicks), what the expected event volume is, how many windows must be supported simultaneously, and what freshness guarantee matters. Clarify whether users need exact counts or approximate rankings. Establish the query pattern: mostly top-10/top-100, or do users frequently request deeper rankings?

Step 2: High-Level Architecture

Sketch three pipelines: an Ingestion Layer where event producers write to Kafka topics partitioned by item ID; an Aggregation Layer where Flink jobs consume events, maintain per-window counters using stateful processing, and emit top-K candidates; and a Serving Layer where Redis sorted sets store pre-computed rankings per window and segment, served by API servers with application-level caching and pagination support.

Step 3: Deep Dive on Aggregation and Hot Keys

Walk through the write path in detail. Describe how Flink keyed state maintains a counter per (window, segment, item_id) tuple using event-time processing with watermarks. When a window closes, extract top-K items using a min-heap during the reduce phase. Address hot keys explicitly: for items exceeding a threshold, split events across sub-keys and merge periodically. Explain how results flow to Redis sorted sets using pipelined batch writes with versioned keys for atomic updates.

Step 4: Address Secondary Concerns

Discuss fault tolerance through Flink checkpoints to S3 and Kafka replication. Cover deduplication using event IDs and Flink state. Explain monitoring: track write lag, p99 read latency, cache hit rates, and hot key detection. Address cost optimization by recomputing long windows (30 days, all-time) hourly via batch Spark jobs rather than continuous streaming.

Real Interview Quotes

"Asked in Atlassian: give top K Confluence pages. If a user has seen one, do not show it again."

"Design popular K feeds in Confluence. Follow-ups included popularity score calculation strategies, support for querying in windows, and updating dashboards of users in real time."