Design Search Autocomplete
A full case study of typeahead suggestions, covering tries with cached top-k lists, offline index builds, caching and sharding by prefix.
Requirements
Autocomplete (also called typeahead) shows suggested searches while you type. Typing ca might show car insurance, cat videos, cake recipe.
Functional:
- For a typed prefix, return the top 5 suggested queries, ranked by popularity.
- Suggestions reflect real past searches.
Non-functional:
- Very fast: under about 100 ms end to end, since it runs on every keystroke.
- Highly available; stale suggestions are fine, slow ones are not.
- Updates can lag by hours for ordinary queries.
- Never suggest offensive or banned terms.
1 of 11