Design Search Autocomplete
Return useful prefix suggestions quickly while refreshing rankings and removing unsafe entries.
Backend and product engineers designing software behavior.
Your approach: Use diagrams, tables or prose for customer contracts, state transitions and data ownership; include APIs only to the depth the question requests.
The problem
Design autocomplete for a public search box that returns ten suggestions after each typed prefix. Explain candidate lookup, popularity ranking and how a new index becomes visible. Handle corrections, language normalization and removed suggestions without exposing raw individual search histories.
- Serve 100,000 prefix lookups/second at peak over 100 million known phrases.
- Popularity updates hourly, while an operator may require an entry to disappear within five minutes.
- Users type, backspace and change language; a response for an older prefix may arrive last.
Work within these constraints
Declare p95 backend lookup latency in a healthy region.
Required target: ≤ 50 milliseconds
Explain how a blocked phrase remains absent across stale caches and index versions.
Use aggregate signals and a stated retention policy rather than publishing rare personal queries.
What to deliver
Lookup and ranking
Define normalized keys, prefix matching, top-k selection and tie-breaking.
Index lifecycle
Show aggregation, index building, validation, version switching and rollback.
Capacity and caches
Estimate index memory and hot-prefix traffic using stated phrase-size assumptions.
Client and removal walkthrough
Trace out-of-order responses and an urgent removal; compare two prefix-index choices.