Track Top-K Frequent Elements from an Unbounded Stream

Scenario

Salesforce handles massive volumes of enterprise tenant activities, including API calls, record updates, and user interactions. You are tasked with designing a real-time analytics engine that continuously tracks and surfaces the Top-K most frequent items (e.g., top API endpoints, top active tenant IDs, or most accessed CRM objects) across an unbounded incoming stream.

The system must serve both real-time top-k dashboard queries and historical point-in-time snapshots while surviving node crashes and message re-deliveries.

Requirements

Functional Requirements

• Continuous Tracking: Continuously process events from an unbounded message stream and compute the Top-K elements (e.g., K = 100).
• Windowing Semantics: Support both sliding windows (e.g., top-k in the last 1 hour, updated every 10 seconds) and tumbling windows (e.g., hourly top-k).
• Snapshot & Query API: Allow clients to fetch current top-k rankings with frequency counts, deterministic tie-breaking (e.g., lexical order on element ID), and retrieve point-in-time snapshots.
• Replay & Checkpointing: Support reprocessing from an offset (e.g., during pipeline failures or backfills) without producing duplicated or corrupted frequencies.

Non-Functional Requirements

• Throughput: Sustain high write traffic with low ingestion latency.
• Query Latency: Serve top-k snapshot queries in under 50 ms.
• Scalability & Hot Keys: Gracefully handle severe skew (e.g., a few tenant IDs generate 80% of all events) without partition starvation or out-of-memory errors.
• Accuracy & Guarantees: Articulate clear trade-offs between exact frequency tracking and approximate heavy-hitter algorithms, with provable error bounds.

Scale & Estimations

• Ingestion Rate: 1,000,000 events/second.
• Distinct Keys: Up to 100,000,000 unique entity IDs active per day.
• Event Payload: ~200 bytes per event.
• Top-K: K is typically between 10 and 1,000.

What Your Design Should Cover

1. API Design: Endpoints for querying top-k results and configuring tracking windows.
2. Algorithm & State Model: Comparison of exact storage (distributed key-value + min-heaps) versus approximate heavy-hitters (e.g., Space-Saving, Count-Min Sketch + Min-Heap, or Lossy Counting). Explain how error bounds (epsilon) are configured.
3. Distributed Architecture: Stream ingestion, local aggregation, global merging, and partition strategy.
4. Window Expiration & Eviction: Mechanism to expire old data efficiently in continuous sliding windows.
5. Fault Tolerance & Idempotency: Snapshot persistence, checkpointing intervals, and handling replay offsets.