Design Search Autocomplete

Prompt

"Design the suggestions that appear under the search box as the user types. Every keystroke should show the top ten completions."

Clarifying questions

• What are we completing from? Historical search queries, ranked by popularity. Not a dictionary.
• How many suggestions, and how are they ordered? Ten, ordered by a popularity score. Personalisation is a follow-up.
• How fresh must the data be? New trending queries should appear within an hour or so; it does not need to be real time.
• Prefix only, or also mid-word matches and spelling correction? Prefix match only. Spelling correction is a separate system.
• Languages and character sets? Multiple languages; treat input as Unicode strings. Assume queries are lowercased and whitespace-normalised.
• Latency target? The suggestions must appear before the next keystroke: p99 under 100 ms end to end, meaning under 20 ms in the service.
• Scale? Billions of searches per day. Take a round number.
• Should offensive or private-looking queries be filtered? Yes, a blocklist and a minimum-popularity threshold so one-off queries never appear.

Requirements

Functional

• Given a prefix, return the top 10 completions by score.
• Scores derived from query frequency over a recent window, updated periodically.
• Filter blocked terms and below-threshold queries.

Non-functional

• Very low latency: the service budget is tens of milliseconds, which rules out disk reads on the request path.
• High availability; suggestions failing should degrade to "no suggestions", never to a broken search box.
• Eventual freshness measured in hours is fine.

Back-of-envelope

• Assume 5B searches/day. Each search generates keystrokes; if the average query is 20 characters and the client sends a request per keystroke after the first, that is roughly 20 requests per search → 100B autocomplete requests/day ≈ 1.2M requests/s average, perhaps 3M/s at peak. Client-side debouncing (wait 50-100 ms of idle time) and prefix caching in the browser cut this by a large factor; assume 500K/s average after debouncing, 1.5M/s peak.
• Distinct queries: of 5B daily searches, perhaps 20% are distinct strings → 1B distinct/day, but only queries seen above a threshold matter. Assume the served corpus is 100M queries after thresholding.
• Index size: 100M queries × 30 B average ≈ 3 GB of raw strings. A trie with precomputed top-10 lists at each node roughly triples that. Call the whole serving index 10-15 GB. It fits in memory on a single machine; the problem is request volume and replication, not size.
• Response size: 10 suggestions × ~30 B plus framing ≈ 500 B. 1.5M/s × 500 B ≈ 750 MB/s outbound at peak. Modest.
• Query log ingestion: 5B searches/day × 50 B ≈ 250 GB/day of raw log, aggregated hourly into (query, count) pairs. A batch job, not a serving concern.
• Cache: the distribution of prefixes is extremely skewed (the first two characters of popular queries). A cache of the top 1M prefixes × 500 B = 500 MB serves a large share of traffic per region.