In a search-box autocomplete service, why does one-request-per-keystroke traffic push designs toward precomputed suggestion lists instead of ranking at request time?
answer
- count requests per typed query
- the next keystroke is a deadline
- rank offline, look up online
- prefix maps to a short list
- short prefixes are shared
basics
~20 sEach keystroke can send a request, so autocomplete sees several times the traffic of full search and must answer before the next key. Precomputing ranked suggestions per prefix turns each request into a cheap lookup.
solid answer
~50 sA user typing an eight-character query can send a suggestion request on most of those keystrokes, so the autocomplete endpoint takes **several times** the request rate of the search endpoint itself. Each response is also only useful if it arrives before the next keystroke, which leaves a budget of roughly `100 ms` end to end. Ranking candidates at request time (scanning matches, scoring them, sorting) is too expensive at that rate and latency. So the work moves offline: a batch job reads query logs, scores candidate completions, and stores a short, already-ranked **top-k list per prefix**. Serving then becomes a bounded lookup of `prefix -> list`, and because short prefixes are shared by many users, those lists are also highly cacheable. The price is freshness and flexibility, which a trending overlay and a small request-time rerank can partly buy back.
go deeper
Recall that each keystroke can be a request and that the answer must arrive before the next key. Then state the fix: rank offline, store a top-k list per prefix, look it up at request time.
Explain why request-time ranking is worst for the shortest prefixes, since they match the most candidates and are requested most often, and how a precomputed list makes cost depend on prefix length and k instead.
Show you can estimate the traffic multiplier with stated assumptions, and name what precomputation costs in production: stale suggestions, weak personalization, and memory growth with k.
Frame precomputation as moving cost from the hot path to a build pipeline, and discuss how much request-time reranking to allow before the latency and cacheability benefits erode.
## What an autocomplete service serves **Autocomplete** (also called **typeahead**) is the dropdown of suggested queries that appears under a search box while the user types. Each suggestion is a whole query the system believes the user probably means, such as `running shoes` for the typed text `run`. The typed text is the **prefix**; the suggestions are **completions** of it. The server side of this feature has an unusual shape compared with ordinary search: - the input is tiny (a few characters), - the output is tiny (usually 5-10 strings), - but the request rate is very high and the latency budget is very tight. ## Why the load is extreme Full search runs once per submitted query. Autocomplete can run once per **keystroke**. An illustrative estimate, with the assumptions stated: 1. Assume a site peaks at **5,000 submitted searches per second**. 2. Assume the average query is 8 characters long, and the client, after its own throttling, sends a suggestion request on about **5** of those keystrokes. 3. Suggestion traffic is then about 5,000 x 5 = **25,000 requests per second** - five times the search load, for a feature that returns ten short strings. On top of the rate, each answer has a deadline. If the suggestions for `ru` arrive after the user has already typed `run`, they are useless. Interactive-feel guidance puts that budget near **100 ms** end to end, and the network round trip consumes a large part of it before the server even starts work. ## Precompute instead of compute There are two broad ways to produce the list for a prefix: | Approach | Work per request | Freshness | Flexibility | |---|---|---|---| | **Rank at request time** | find all matching candidates, score each, sort, cut to k | immediate | high: filters, personalization, any scoring | | **Precomputed top-k per prefix** | one lookup of an already-sorted short list | as fresh as the last build or refresh | lower: ranking fixed at build time | Ranking at request time means the cost grows with the number of candidates under the prefix. A one-letter prefix can match millions of past queries, so the shortest prefixes - which are also the most frequently requested - would be the most expensive. That is the worst possible combination. Precomputation flips it. An offline **batch job** reads the query logs, counts how often each query was issued (often with a time decay so old popularity fades), and for every prefix stores the best **k** completions in order. At serving time the work is: 1. locate the entry for the prefix (a walk down a **trie**, or a key lookup in a prefix-to-list map); 2. return the stored list, optionally after a light filter or rerank over those few items. The cost now depends on the prefix length and on k, not on how many queries share the prefix. ## Side benefits of precomputation - **Cacheability.** The set of short prefixes is small (26 + 676 + 17,576 = 18,278 strings of one to three lowercase Latin letters), and most typed queries pass through them, so their lists can be cached close to users. - **Predictable latency.** Every request does roughly the same amount of work, which keeps tail latency flat. - **Offline quality control.** Unsafe or low-quality suggestions can be removed during the build, before anyone sees them. ## What precomputing gives up Precomputation is a trade, not a free win: - **Freshness.** A term that becomes popular this morning is missing until the next build, which is why production designs add a **trending refresh** path. - **Personalization and filters.** A single global list per prefix cannot reflect one user's history or a selected category. A common compromise is to precompute a slightly longer list (say 20 items when 8 are shown) and rerank or filter those few at request time. - **Storage.** Every stored prefix carries its own list, so memory grows with the number of prefixes times k. ## Summary Per-keystroke traffic multiplies the request rate, and the next keystroke sets a hard deadline. Moving the ranking offline and serving a stored top-k list per prefix makes each request cheap and uniform, at the cost of freshness and flexibility that the rest of the design then has to recover.
- What does a precomputed suggestion list give up compared with ranking at request time?Freshness, because new terms appear only after the next build or a trending refresh; flexibility, because one global list per prefix cannot reflect a user's history or an active filter; and memory, because each prefix stores its own list. Designs recover some of this by storing a slightly longer list and reranking those few items per request, plus a small overlay for trending terms.
- Why store more suggestions per prefix than the dropdown shows?Request-time steps such as removing a suggestion that is blocked for a region, or reranking by a user signal, discard or reorder items. If exactly the displayed number were stored, any removal would leave the dropdown short. Storing, for example, 20 for an 8-item dropdown leaves headroom, and memory grows only linearly with that k.
A coffee shop that pre-brews its three best-selling drinks before the morning rush can hand them over instantly, while made-to-order drinks would stall the queue. The trade-off is that a drink nobody expected is not ready.
saying these in an interview costs you the question
- Autocomplete load equals search load, since it is one request per query.
- Running the full search query on every keystroke is fine at scale.
- Precomputing means storing every string a user could possibly type.
- Short prefixes are cheap to rank at request time because they are short.
- Precomputed suggestions cannot be refreshed until a full daily rebuild.