Typeahead and Autocomplete

Why typeahead is a classic design question, and what it teaches

Typeahead (also called autocomplete) shows suggestions as a user types into a search box. Each keystroke can start a request, the answer must arrive before the next key, and the list must be useful: the most popular or relevant completions of what has been typed so far. It teaches prefix indexes, precomputation, caching and update pipelines.

It gives you two things interviewers always ask about:

• Very low latency: suggestions must appear in a fraction of a second, or they arrive too late to help.
• Scalability: every keystroke of every user is a request, so the read load is huge compared with the number of searches.

Requirements to confirm first:

• Functional: return the top few completions for a prefix, ranked by popularity or personal relevance, optionally fix typos.
• Non-functional: responses in tens of milliseconds, very high request rate, suggestions that follow trends within minutes or hours.

Skip the design, or simplify it, when:

• The list is short (a few hundred items): filter it in the browser.
• You do not need ranking: a simple prefix query on an indexed column is enough.

Try it

A user types "card" one letter at a time. Change how the index works, then change the typing and the data.

Things to try:

• Run the Prefix tree with a request for every keystroke. Each request is cheap, but there are four of them.
• Switch to Scan every stored query and see how much work one request is.
• Choose A new trending query appears and compare which approach sees it.

What to watch (counters at the last step):

• Prefix tree, a request for every keystroke: 4 requests, 10 entries examined (1 + 2 + 3 + 4 nodes visited).
• Prefix tree, with debounce: 1 request, 4 entries examined.
• Scan, with debounce: 1 request, 1,000,000 entries examined.
• Scan, a request for every keystroke: 4 requests, 4,000,000 entries examined.
• Trending query: only the scan shows it ("sees trending term" is yes). Note that this option also waits for a pause before sending, so it makes 1 request, not 4.
• For the prefix tree, "entries examined" counts the nodes visited, which equals the prefix length.

Ways to build the suggestion index

Precompute vs compute on the fly

• Compute on the fly (scan or query when asked) is always fresh, but its cost grows with data size and request rate.
• Precompute the top results for each prefix ahead of time, so a request is a lookup. It is very fast, but only as fresh as the last build, and it uses more memory.

Most systems precompute, because reads far outnumber changes, and refresh the data every few minutes or hours from a log of searches.

How the stored top results get into each node: the build job counts every query, then for each prefix keeps only the best few (for example the top 5) by weighted count, and writes that short list on the node. A request therefore never has to look below the node it reaches. Updating counts in place would mean changing the lists on every ancestor node of every searched query, so most systems rebuild in batches and add a small index of very recent queries for freshness.

How a typeahead request works

1. The client waits for a short pause in typing (debounce, often 100 to 200 ms) so it does not send every keystroke, and it cancels requests that are now out of date.
2. The request reaches a suggestion service through a CDN (a network of edge servers close to users) or load balancer. Personalised answers differ for each user, so they are usually not shared through a CDN. Popular prefixes such as "a" or "wh" are answered from a cache.
3. On a miss, the service looks up the prefix in the index (a trie or sorted set) and returns the stored top results.
4. In the background, search queries are logged, aggregated into counts (with the most recent queries weighted more), and used to rebuild the index periodically.
5. The new index is swapped in without downtime.

Components and what each one does

• Client: debounces keystrokes, cancels out-of-date requests, ignores late answers, and draws the list.
• Cache or CDN: answers common prefixes without touching the index. It does not rank anything.
• Suggestion service: a stateless layer that validates the prefix, reads the index, applies filters and returns a few results. It holds no data of its own, so any copy can answer.
• Prefix index (trie or sorted set): read-only between rebuilds, holds the top results per prefix.
• Log pipeline and build job: collect searches, aggregate counts, build and publish the next index. They never sit on the request path.

Rough capacity estimate

The numbers below are illustrative assumptions chosen for easy arithmetic, not measurements. Replace them with the interviewer's figures.

• Traffic: 10 million daily users, 10 searches each, is 100 million searches a day.
• Requests without debounce: about 10 keystrokes per search gives 1 billion requests a day, which is about 11,600 a second (1,000,000,000 divided by 86,400).
• Requests with debounce: about 4 requests per search gives 400 million a day, about 4,600 a second on average. Assuming a peak of 3 times the average, plan for about 14,000 a second.
• After the cache: if 80 percent of requests hit the cache (an assumption), the index sees about 2,800 a second at peak.
• Index size: assume 50 million trie nodes, each holding 5 result ids of 4 bytes (20 bytes) plus about 20 bytes of overhead, so 40 bytes per node and about 2 GB in total. That fits in memory on one machine, so the first scaling step is replication for read capacity, and partitioning is needed only for much larger vocabularies or for region and language.
• Log volume: 100 million searches at about 100 bytes each is about 10 GB a day of raw logs for the build job.

Typeahead design vs the alternatives

Use a precomputed index when scale demands it. A database query or a client-side filter is enough for small lists.

Avoiding a new single point of failure

• Index servers: replicate the index across many servers, since it is read-only between rebuilds. Losing one costs only capacity.
• Build pipeline: if it fails, keep serving the last good index. Suggestions go stale rather than disappear.
• Cache: fall back to the index if it is down.
• Search itself: typeahead is optional, so the search box must still work if it fails.
• Hot prefixes: a few short prefixes get most of the traffic. If the index is partitioned by first letters, the partitions for popular letters run hotter, so split them further, replicate them more, or rely on the cache for them.
• Cache after a swap: when a new index replaces the old one, cached answers are from the old index. Give cache entries a short lifetime so they expire within a few minutes, and avoid clearing the whole cache at once, which sends every request to the index together.

You accept slightly stale suggestions in exchange for speed and availability.

Common mistakes

• Sending a request per keystroke. Debounce and cancel stale requests.
• Ranking by raw counts only. Old terms dominate. Weight recent searches.
• Scanning all data per request. Precompute top results per prefix.
• Rebuilding in place. Build a new index and swap, so readers never see a half-built one.
• Ignoring bad suggestions. Filter offensive or private terms before they are indexed.
• Treating it as critical. It should degrade quietly.

How to talk about typeahead in an interview

• Ask for scale, latency target, and how fresh suggestions must be.
• Describe the trie with top results at each node, or a sorted set, and the offline pipeline that builds it from search logs.
• Mention debouncing, caching of short prefixes, and swapping in a new index.
• Name the trade-off: a precomputed index is very fast but stale until the next rebuild, so you choose the refresh interval to match how quickly trends matter.