Design a Service for the Top K Most-Visited URLs over a Sliding Time Window

Design a system that reports the top K most-visited URLs over a recent time window. Every page visit or link click produces an event that names the URL, and clients ask the system for the current top K list. The list should stay reasonably fresh as traffic changes. The interviewer expected you to clarify the requirements first, then present an end-to-end design, and then go deep on hot keys and skew, late or out-of-order events, and exact versus approximate counting. ### Constraints and Clarifications - Traffic volume, the number of distinct URLs, K and the freshness target are not given. Ask for them or state your assumptions. - Assume visit events are already emitted by the services that serve the pages; collecting them in the browser is out of scope. ### Clarifying Questions - Which window: the last hour, the last 24 hours, or both? A sliding window, or fixed periods such as each full hour? - How fresh must the results be: updated every few seconds, every minute, or every hour? - Must the counts and the ranking be exact, or are approximate counts acceptable? - What are the read and write volumes: visit events per second, and top-K requests per second? - Is K fixed and small, or can callers ask for any K? - Do repeated visits by the same user count every time, and must bot traffic be excluded? ### Part 1 — End-to-end design Design the path from visit events to a top-K answer: how events are ingested, how per-URL counts are kept for the window, how the global top K is computed, and how clients read it. ```hint Two very different paths Decide what work happens when a visit event arrives and what happens when a client asks for the list. Ask which of the two must stay fast no matter what the other is doing. ``` ```hint Combining partial results If counting is split across many workers, think about what each worker must hold so that combining their outputs still yields the correct global top K. ``` #### What This Part Should Cover - Ingestion through a durable, partitioned event stream, and the choice of partition key - Per-URL counting over the window, including how counts leave the window as time moves - Computing a global top K from per-worker results, and the condition under which that merge is exact - A serving layer that answers reads without touching the counting path ### Part 2 — Hot keys and skew A single URL goes viral and receives a large share of all visits. What breaks in your design, and how do you fix it? ```hint Follow the viral URL Trace which partition and which worker receive every event for that URL, and ask whether one worker can absorb that load. ``` #### What This Part Should Cover - Why the partitioning scheme concentrates a hot URL on one partition and one worker - Spreading or pre-aggregating a hot URL's events, and the extra combine step that follows - Detecting hot keys, and how splitting a URL's count affects the correctness of the top-K merge ### Part 3 — Late and out-of-order events Events can arrive late or out of order, for example after a client reconnects or a producer retries. How do you assign them to windows, and what does that do to the top-K results? ```hint Which clock Decide whether an event belongs to the window in which it happened or the window in which it arrived, and what you need to know before treating a window as complete. ``` #### Clarifying Questions for this Part - How late can an event arrive and still be counted? - May a top-K result that was already served be revised afterwards? #### What This Part Should Cover - Event time versus processing time, and how the system decides that a window is complete - What happens to events that arrive after their window has been finalized - Duplicate events from retries and restarts, and their effect on counts ### Part 4 — Exact versus approximate counts Memory for exact per-URL counts grows with the number of distinct URLs. When would you accept approximate counts, how would you produce them, and what do you give up? ```hint Only the head matters The ranking needs accurate counts only for URLs that could plausibly be in the top K, not for the long tail of rarely visited pages. ``` #### What This Part Should Cover - Rough memory for exact counts compared with a compact approximate structure - How approximation error can change which URLs appear near the K-th place - Combining a fast approximate path with a slower exact one when exact results are still needed ### What a Strong Answer Covers - Requirements and rough estimates that drive the window, freshness and accuracy choices - A pipeline whose partitioning and merge step produce a correct global top K - Sliding-window maintenance in which counts both rise and expire - Concrete handling of hot keys, late events and duplicates - Explicit accuracy, memory and freshness trade-offs, with failure handling and monitoring ### Follow-up Questions - How would you serve several windows, such as the last 5 minutes, the last hour and the last 24 hours, without a separate pipeline for each? - Product also wants the top K per country. What changes in partitioning and storage? - A stream worker crashes and restarts. How do you avoid losing or double-counting events? - How would you stop a bot from pushing a URL into the top K?