Design Real-Time Search Autocomplete with Top-10 Popularity-Ranked Prefix Suggestions

Design a search autocomplete (typeahead) service. As the user types, the client sends the current prefix, and the service returns up to 10 suggested queries that start with exactly that prefix, ranked by search popularity. Suggestions must stay fresh in near real time. When a sudden event makes a new query popular, such as a goal in a World Cup match, completions for that query should appear almost immediately. Start by assuming the data fits on one machine, then scale the design out. ### Constraints - Scale given by the interviewer: 1 billion users, each making about 10 searches per day. - Matching is exact prefix matching. Spelling correction and fuzzy matching are not required. - Suggestions are ranked by search popularity, with at most 10 per prefix. - Freshness is a core requirement. It cannot be met by a daily rebuild alone. ### Clarifying Questions - How many autocomplete requests does one search generate? Is a request sent on every keystroke, or are keystrokes debounced? - Over what time window is popularity measured, and should recent searches count more than older ones? - How quickly must a newly trending query appear: within seconds or within minutes? - Are suggestions global, or do they vary by language or region? ### Part 1 — Core Design on One Machine Design the data structure and the serving path that return the top 10 suggestions for a prefix. Why use a trie instead of a plain key-value mapping from each prefix to its precomputed top-10 list? ```hint Compare the two structures under updates Think about what has to change in each structure when one query's popularity count changes, and how much memory each needs to cover every prefix. ``` #### What This Part Should Cover - How the top-10 lists are stored or computed for each prefix, and what a lookup costs. - The memory and update costs of a trie compared with a store that maps each prefix to a list. - How popularity counts are collected from search logs. ### Part 2 — Freshness: Batch Rebuilds and Real-Time Updates How often would an offline job rebuild the suggestion data? The offline job may take hours. If you swap in the newly built trie when it finishes, aren't the real-time updates from those hours lost? What exactly is the difference between offline batch processing and pure streaming here? How much does accuracy matter in this system? ```hint Think about what the batch output represents Ask which point in the event stream the batch snapshot corresponds to, and what would have to be replayed on top of it. ``` #### What This Part Should Cover - How the batch and streaming paths combine without losing the updates that arrive during a rebuild. - The trade-offs between batch recomputation and pure streaming in cost, correctness, and recovery. - Where exact counts matter and where approximate popularity is good enough. ### Part 3 — Scaling Out: Sharding, Hot Shards, and Replicas What if the data no longer fits on one machine, or the query rate is too high for it? Prefixes are unevenly distributed: queries starting with "a" far outnumber those starting with "z". How do you shard? The distribution also changes over time. If a small shard suddenly becomes hot, how do you handle it dynamically? Walk through it step by step, including how a new node is warmed up and how routing is switched over. Finally, if the trie is small but the query rate is very high, how do replicas stay in sync with the leader? ```hint Separate the split from the cutover A hot shard can be split or replicated only once the new nodes hold correct, current data. Think about the order in which the data copy, the catch-up, and the routing change must happen. ``` #### What This Part Should Cover - A sharding key and a way of choosing shard boundaries that handles skew between prefix ranges. - A step-by-step rebalancing procedure that never serves cold or stale data during cutover. - Read replicas, how they receive updates from the leader, and how stale they are allowed to be. ### What a Strong Answer Covers - A back-of-the-envelope load estimate from the given user and search numbers, including how many prefix requests each search produces. - A serving data structure with a bounded lookup cost for top-10 results. - A freshness path that combines batch and streaming without dropping updates that arrive during a rebuild. - Sharding, hot-spot mitigation, replication, and caching that follow from the load estimate. - Failure handling and monitoring for stale or missing suggestions. ### Follow-up Questions 1. How would you stop a single user or bot from pushing a query into the suggestions by searching for it repeatedly? 2. How would you remove a suggestion that must be taken down immediately from every shard and replica? 3. How would caching popular prefixes on the client or at the edge interact with the freshness requirement?