Design search autocomplete

01The design, in the six-step framework

1. Requirements

Functional

• As the user types, show the top 5 to 10 completions for the prefix typed so far, ranked by popularity.
• Completions reflect recent trends (a breaking news term appears within minutes) and are filtered for offensive content.
• Prefix matching on words anywhere in the query is nice to have; personalisation is out of scope.

Non-functional

• Every keystroke is a request: 10 billion queries a day and an average of 5 keystrokes each → 50 billion requests a day.
• Latency under 100 ms end to end, under 20 ms in the service, or the suggestions arrive after the user has moved on.
• Available in every region; a stale list of suggestions is acceptable for minutes, an empty box is not.
• Memory-bound: the whole structure should fit in memory on a modest number of machines.

2. Core entities

• Query string: normalised text, aggregate count over a decayed window, offensive flag.
• Trie node: character, children, top-k list of (query id, score) for the subtree.
• Query log event: query, timestamp, locale (the input to counting).
• Generation: a built trie snapshot with a version and a build time.

3. API

• GET /complete?q=prefix&hl=en&n=8 → ordered list of suggestions; served over a keep-alive connection, response under 1 KB.
• POST /events (internal, from the search front end) → batches of issued queries for counting.
• Build side: build(window) → generation; publish(generation).

4. High-level design

A keystroke, and how the list it shows was made:

1. The browser sends the prefix after a short debounce (a keystroke that is followed by another within 50 ms is never sent). The edge cache answers most short prefixes directly: there are only 26³ three-letter prefixes and they repeat endlessly.
2. On a miss, a suggest server walks the trie to the prefix node and returns its precomputed top-k list in microseconds. Nothing is computed per request.
3. Offline, issued queries flow through a log stream. A daily batch job computes decayed counts over the past weeks and builds a complete trie generation; a streaming job computes counts over the last hour and produces a small delta trie of surging queries.
4. Servers load a new generation next to the old and switch atomically; the edge caches expire within minutes.

5. Deep dives

Why precompute top-k at every node, and what does it cost?

Walking to a prefix node and then searching its whole subtree for the best completions would touch millions of nodes for a one-letter prefix. Storing the top-k list at each node makes a lookup O(prefix length) with no search at all. The cost is memory: every node carries a list, which is why the arithmetic above gives tens of gigabytes rather than a few. It also makes the trie read-only, which is what we want for serving: updates happen by building a new generation. A compact alternative that interviewers like is to store the top-k only at nodes with many descendants and compute on the fly for tiny subtrees; the lists dominate at shallow nodes and are redundant at deep ones.

Freshness: a term explodes in popularity. How soon does it appear?

A daily rebuild gives a day of lag, which fails the requirement. Add a second path: a stream processor counts queries in one-minute windows and keeps an hour of windows per query; queries whose recent rate is far above their long-term rate are collected into a small "trending" trie rebuilt every few minutes. At serve time the list is the merge of the main trie's top-k and the trending trie's entries for that prefix, with recency as a score boost. This keeps the big structure stable and the fast path tiny. The honest caveat: the trending path is also the abuse path (a coordinated group can push a phrase), so trending candidates pass the policy filter and a minimum-distinct-users check before they appear.

Serving 2 million requests a second within 20 ms

Three layers. The browser debounce halves the requests. The edge cache keyed by (prefix, locale) absorbs the short prefixes that dominate traffic with a TTL of a few minutes, which also bounds staleness. The remaining long-tail prefixes hit suggest servers that hold the trie in memory; a full copy per server avoids any cross-machine call, and the fleet is sized from requests per second alone. If the trie outgrows one machine's memory (many languages, longer lists), shard by first character or two and route at the load balancer, accepting that popular first letters need more replicas; the second option is to shard by hash of the prefix with the first-k lists duplicated, which balances better.

Building the trie for 100 million queries

The daily build is a batch job: aggregate logs into (query, decayed count), drop queries below a count floor and those failing policy, sort by query string so that building the trie is a single pass, and compute the top-k lists bottom up (a node's list is the merge of its children's lists plus its own terminal query). The output is serialised as a compact array form (children by offset, lists inline) so a server can memory-map it and start serving without a parse step. Builds are per locale, and generations are kept for a day so a bad build can be rolled back by pointing servers at the previous file.

Locale, language and the long tail

Suggestions are per language and often per country: the same prefix means different things in Mumbai and in Madrid. The simplest correct model is one trie generation per locale, loaded on servers in the regions that serve it, with the locale chosen from the user's settings and the request's region. Scripts without word spaces (Japanese, Chinese) need the trie built on the transliterated input the user actually types, with the final-form query stored as the suggestion. For a prefix that no one has typed before, the trie returns nothing; the service can fall back to a spelling-corrected prefix or to completions of the last word only, which costs one extra lookup and keeps the box from going blank.

6. What a strong answer sounds like

• Open with the request rate (keystrokes, not queries) and the 100 ms human budget, then the memory arithmetic that shows precomputed lists are affordable.
• Draw the two-speed build: a daily full trie and a minutes-level trending delta merged at serve time.
• Explain the debounce and edge cache as the first two tiers of the read path, and when sharding becomes necessary.
• Mention the policy filter and the abuse angle of trending.
• Expect follow-ups on personalisation (a small per-user prefix cache merged client-side), on mid-word matching (an index of word positions), and on multi-language input.
• Common mistake: suggesting a database query with LIKE 'prefix%' per keystroke.

02Where this question was reported

• IGotAnOffer · SWE: 'Design a word predictor for a search engine'
• interviewkickstart.com · 'type-ahead service'; 'autocomplete ... scale to millions of users'
• interviewkickstart.com · Core Q4, 'a common Google system design interview' question
• interviewkickstart.com · Q12 auto-complete (search-as-you-type)
• DesignGurus · 'Google Search Autosuggest', <50 ms latency target
• DesignGurus · 'A signature Google question tied to their core search product', <100 ms
• DesignGurus · 'Typeahead Suggestion'
• Educative · 'Design a typeahead', detailed
• Glassdoor · Design an autocomplete system for a large-scale search engine (review ID from exact-phrase search)
• LeetCode Discuss · Asked within a DSA-style round; interviewer pushed on drawbacks and real-world architecture (search snippet)
• Blind · Google employee confirms questions like design auto-complete / design YouTube for backend roles, not those exact ones
• Educative · Probes fast response, millions of concurrent requests, typos, fast typists.