Typeahead / Autocomplete

Search suggestions

Design the suggestion list under a search box: as someone types, show the ten most likely completions of what they have typed so far, within a fraction of a second, updated as searches change.

Overview

Typeahead (autocomplete) is the list that appears under a search box while you type. Type 'wea' and it offers 'weather', 'weather tomorrow' and so on; pick one and you skip the rest of the typing. Google reported in 2018 that its autocomplete cut typing by about 25% on average.

The difficulty is time. People type several characters a second, and a list that arrives after the next keystroke is useless. So the answer for each prefix has to be ready before anyone asks: the design moves almost all the work into an offline job that reads the search logs and precomputes the best completions for every prefix, and keeps the online path to a lookup.

Questions to ask first

What is being completed? — Search queries, from the log of past searches
How many suggestions? — 10 on desktop, fewer on mobile
How fast? — The list for a keystroke arrives within 100 ms at p99 (a target we chose)
How much traffic? — 500 million searches a day, about 6 suggestion requests per search after debouncing
How fresh? — Rising searches appear within about 10 minutes; the rest may be a day old
Personalized? — Lightly: the user's own recent searches can be added
Languages and regions? — One index per language and region

What you will be able to do

Size the request rate and the index, and show that the index fits in memory.
Explain a trie that stores the top completions at every node, and why lookups then cost only the prefix length.
Build the index offline from search logs with time decay, and add rising searches with a small overlay.
Cut requests with debouncing and caches, and meet a latency budget.
Decide between replicating and sharding the index, and handle personalization and harmful suggestions.

Key concepts

Prefix trie
Top-k per node
Offline index build
Time decay
Trending overlay
Debouncing
Edge caching
Replicate before sharding
Suggestion filtering

Functional requirements

Return up to 10 completions for a prefix, best first
Rank by how often and how recently people searched each completion
Show a rising search within minutes
Optionally add the user's own recent searches
Never show completions that break the content policy

Non-functional requirements

p99 latency under 100 ms end to end (a target we chose); the server's own share under 10 ms
About 35,000 requests a second on average, 104,000 at peak
Highly available: if suggestions fail, the search box still works
An index rebuild never interrupts serving

Interview questions

Which data structure would you use, and what does a lookup cost?
How do you rank completions?
How do you handle 100,000 requests a second under 100 ms?
How do new and trending searches get into the suggestions?
Would you shard the trie? How?
How do you personalize suggestions without breaking caching?
How do you keep harmful suggestions out?
How would you measure whether typeahead is working?