System Design

Search Autocomplete

Design a search autocomplete (typeahead) service.

Functional requirements

• As a user types a query, return the top 10 suggested completions for the current prefix, updated on every keystroke.
• Suggestions are ranked by historical query popularity (frequency of past searches).
• The suggestion corpus is continuously updated from the live search query stream so trending queries surface within hours, not weeks.
• Support basic filtering: exclude a maintained blocklist of offensive/prohibited terms from suggestions.
• Support English-language queries; matching is on normalized (lowercased, whitespace-trimmed) prefixes.

Non-functional requirements

• p99 end-to-end suggestion latency under 100 ms (server-side processing budget ~20 ms); this is the dominant design constraint.
• Highly available: it is acceptable to serve slightly stale or degraded suggestions; it is not acceptable to block or slow the search box. Availability over consistency.
• Eventual consistency for popularity data: new/trending queries should appear in suggestions within ~1 hour; exact real-time counts are not required.
• Suggestion data is reconstructible from the query log stream; durability of derived suggestion indexes matters less than durability of the raw query log.
• Blocklist updates must take effect within minutes globally.

Scaling & constraints

• 500 million DAU; an average user performs 6 searches per day.
• Each search generates on average 4 keystrokes that trigger a suggestion request (after client-side debouncing).
• Read (suggestion request) to write (logged completed query) ratio is roughly 4:1.
• Query corpus: ~2 billion distinct historical queries; average query length 20 characters (~30 bytes with metadata per entry).
• Retain 12 months of query popularity history for ranking; traffic grows ~20% year over year.
• Traffic is global with strong diurnal peaks (peak roughly 3x average) and heavy skew toward a small set of popular prefixes.

Out of scope

• Personalized or context-aware suggestions (per-user history, location-based ranking).
• Spell correction, fuzzy matching, and multi-language/CJK tokenization.
• The search results system itself; only the suggestion service.
• Ad-injected or sponsored suggestions.