You type "how to" into a search box, and before your finger leaves the key, ten suggestions appear. Type "how to m" and they change. That's typeahead, or autocomplete. It feels like a tiny feature, but it's one of the highest-traffic services a search company runs, because it fires on keystrokes, not searches.
The whole design comes down to a latency budget. You have about 100 ms from keystroke to suggestions on screen, and the network eats half of it. This lab works out where the other half goes.
The brief
You're building search suggestions for a search engine, like the box on Google Search. As the user types, show the 10 most popular completions of what they've typed so far.
Who uses it?
- Searchers type queries on phones and laptops, often on slow mobile networks.
- The search team wants suggestions that reflect what people actually search for, including breaking news within the hour.
- Trust and safety needs to remove offensive or harmful suggestions quickly.
In scope: prefix completion of whole queries, ranked by popularity, refreshed regularly, with a fast path for trending queries and a blocklist.
Out of scope: spelling correction ("did you mean"), personalised suggestions based on your own history, multiple languages beyond noting where they'd plug in, and the search results page itself.
Requirements
Functional
- Given a prefix, return up to 10 suggested queries that start with it, ranked by popularity.
- Suggestions reflect searches from the last few weeks, weighted towards recent ones.
- A query that suddenly trends shows up within about 15 minutes.
- Blocked queries disappear from suggestions within minutes of being added to a blocklist.
Non-functional
- Fast: under 100 ms from keystroke to render for most users. That leaves the server ~10 ms.
- Highly available: if suggestions fail, search still works, but users notice.
- Scales to every keystroke at peak.
- Eventually consistent: suggestions can be minutes or hours stale. Nobody needs strict freshness here.
- Private: never suggest a query that only a handful of people have searched.