The contract
Define the contract precisely. Given a prefix, return the top five to ten completions ranked by popularity, updated as somebody types.
Clarify three things that size your offline pipeline: which languages, whether results are personalised, and how fresh a trending query has to be.
Treat speed as the one non-negotiable. The whole round trip has to land inside roughly 100 milliseconds to feel attached to the keystroke, and once you subtract 30 to 60 milliseconds of network, your server gets about 10.
Rule out anything that queries a database per keystroke, because it is dead on arrival. This is a memory-serving problem.
The traffic nobody expects
Do the traffic arithmetic, where candidates usually undershoot. Take a product doing 10 million searches a day, with an average query around 20 characters.
Autocomplete fires per keystroke, not per search, minus whatever your client-side pause and result caching absorb. Call it six effective requests per search, giving 60 million a day, about 700 a second on average and over 2,000 at peak.
Compare that with the search backend behind it, seeing a tenth as much. Autocomplete is routinely the busiest endpoint a search team runs.
Bound your data next. A year of logs might hold 100 million distinct queries, and frequency follows a power law where the tail is one-offs, typos and junk that should never be suggested.
Keep the top ten million by count. At around 20 bytes a query plus counts and structure, your raw material is a few hundred megabytes to a few gigabytes once indexed, which fits comfortably in one machine's memory.
See what that simplifies. You replicate everywhere instead of sharding, and every part of the serving story gets easier.
Write down the two-sided shape before you design anything. A read path measured in microseconds internally, and a write path ingesting query logs that can be hours stale without most people noticing.
Worked example
Deepak owns search at a recipe site doing 2 million searches a day and gets a one-line ticket: add autocomplete like Google. He instruments a prototype on 5 percent of traffic and finds the request multiplier immediately: users average 14 keystrokes per search, and even after 100 ms debouncing, autocomplete fires 8 times per search. Full rollout means 16 million requests a day against a search API built for 2 million, and his first prototype, which ran a prefix query against Postgres, a relational database, on every keystroke, clocks 180 ms at p95, the number its slowest one request in twenty comes in under, and leaves the database 40 percent busy from 5 percent of users. The numbers make his case for him: suggestions move to a precomputed in-memory structure rebuilt nightly, and the database never sees a keystroke again. The prototype's p95 drops to 9 ms.