Design Top K Rankings System (App Store / Amazon Bestsellers)

Stream Processing (Apache Flink): The Core Engine

Approach 1: Exact Count (for small-medium scale)

Flink Pipeline:
  Source(Kafka: ranking-events)
  → KeyBy(item_id)
  → Tumbling/Sliding Window(5 minutes)
  → Aggregate(count per item_id)
  → Top K (min-heap of size K)
  → Sink(Redis sorted set)

Approach 2: Approximate Count (for massive scale): Count-Min Sketch + Heap

When you have millions of unique items, maintaining exact counts for all is expensive.

Count-Min Sketch:

• Probabilistic data structure: d hash functions × w counters (matrix)
• On event for item X: hash with each of d functions, increment d counters
• To query count of X: take minimum of d counter values
• Space: O(w × d): typically 2 MB for < 0.1% error rate
• Error: Always overcounts (never undercounts); error bounded by ε = e/w

Min-Heap for Top K:

// Maintain a min-heap of size K
// For each incoming event:
if heap.size < K:
    heap.add(item)
elif item.count > heap.peek().count:
    heap.poll()
    heap.add(item)

Combined approach:

1. Count-Min Sketch tracks approximate counts for ALL items (memory efficient)
2. Min-Heap of size K maintains the current top K items
3. When a new event arrives:
   • Increment item count in Count-Min Sketch
   • Check if item's new count qualifies it for top K heap
   • If yes → add/update in heap
4. Periodically flush heap to Redis

Time-Windowed Rankings

Rankings needed:
  - Hourly top K  → Sliding window, 1 hour, slide every 5 min
  - Daily top K   → Tumbling window, 24 hours
  - Weekly top K  → Tumbling window, 7 days
  - All-time top K → Cumulative counter (no window)

Exponential Decay for "Trending":

Instead of fixed windows, use exponential time decay:

score = Σ (event_value × e^(-λ × age_in_hours))
# λ = decay rate (e.g., 0.1 → half-life ≈ 7 hours)
# Recent events contribute more than old events

Redis (Ranking Cache)

• Sorted Set per ranking list:

Key:    ranking:{category}:{period}
Type:   Sorted Set
Members: item_id
Scores:  count / score

• ZREVRANGE ranking:games:daily 0 9 → Top 10 games today
• ZREVRANK ranking:overall:weekly item123 → What's item123's rank this week?
• Update atomically: ZADD ranking:games:daily 15432 item123

Batch Pipeline (Spark): Reconciliation

• Hourly/daily Spark job reads raw events from Cassandra/S3
• Computes exact rankings (no approximation)
• Reconciles with real-time rankings in Redis (corrects Count-Min Sketch drift)
• Writes historical rankings to Cassandra for "ranking at time T" queries

Event Bus Design (Kafka)

Topic: top_k_rankings-events
  Partitions: 64 (scale consumers horizontally)
  Partition key: entity_id (user_id / order_id — preserves per-entity ordering)
  Retention: 7 days (compliance) or 24h (high-volume telemetry)
  Replication factor: 3, min.insync.replicas: 2

Producer: idempotent producer enabled (enable.idempotence=true)
Consumer: consumer group "top_k_rankings-processors"
  - At-least-once delivery + idempotent handlers (dedup by event_id)
  - DLQ topic: top_k_rankings-events-dlq (poison messages after 3 retries)
  - Lag alert: consumer lag > 60s → scale workers

Design Top K Rankings System (App Store / Amazon Bestsellers): async side effects MUST NOT block the synchronous API response.
  Sync path: validate → persist source of truth → publish event → return 201
  Async path: consumers update caches, indexes, notifications, aggregates