Find Global and Rolling Top-K URLs Under a Memory Limit

Scenario

A large cloud platform processes billions of web requests daily. As part of its observability and security suite, you are tasked with designing an analytics engine that continuously tracks and exposes the most frequently accessed URLs. The system must support two primary metrics: the global (all-time) Top-K URLs and the trailing 24-hour Top-K URLs, operating under strict memory constraints per processing node.

Requirements

Functional Requirements

• GetGlobalTopK(k): Returns the top k most accessed URLs of all time (default k = 100, max 1,000).
• GetRollingTopK(k, window=24h): Returns the top k most accessed URLs in the trailing 24-hour window.
• Ingest Access Events: Ingest a continuous stream of events in the format (url, timestamp, user_agent, client_ip).

Non-Functional Requirements & Constraints

• Throughput: 100,000 requests per second peak (~8.6 billion events per day).
• Cardinality: Up to 500 million unique URLs globally.
• Memory Limit: Worker nodes have limited RAM (e.g., 4 GB per instance) and cannot fit the full URL keyspace in memory.
• Freshness & Latency: Query response time < 100ms. Rolling window result freshness within 1–5 minutes.
• Late Data & Out-of-Order Events: Tolerate up to 15 minutes of out-of-order / late-arriving events.
• Accuracy: State clearly where approximations (sketches) are acceptable versus exact tracking, and provide accuracy guarantees.

What Your Solution Should Cover

1. Data Pipeline & Architecture: End-to-end flow from message broker (e.g., Kafka) to stream processors, persistence, and query serving.
2. Counting Engine (Memory-Bounded):
   • Compare exact disk-backed state stores (e.g., RocksDB/LSM trees with write-ahead logs) versus probabilistic data structures (e.g., Count-Min Sketch + Min-Heap, Space-Saving algorithm).
   • Define how to scale state across partitions without exceeding the per-node RAM budget.
3. Sliding Window Implementation:
   • How the 24-hour rolling window is discretized (e.g., 5-minute or 1-hour time buckets) and expired.
   • How bucket-level sketches or counts are merged deterministically to serve queries.
4. Handling Operational Realities:
   • Mitigating hot partition skew (e.g., viral URLs dominating traffic).
   • Checkpointing, replay, and handling late-arriving events using watermarks.