System design interview: design search autocomplete

1. Clarify the requirements

Autocomplete sounds small, so interviewers use the scoping questions to see whether you notice the hard parts: latency, freshness and what must never be suggested.

• Functional: as the user types, return up to 5 to 10 completions ranked mainly by popularity; filter offensive and unsafe suggestions; optionally blend in the user's own recent searches; support several languages.
• Non-functional: about 100 ms from sending a request to showing the list, measured at the 99th percentile; very high availability, but failure can be quiet (no dropdown is better than a slow one); suggestions may lag real search behavior by minutes or hours.
• Out of scope unless asked: spelling correction and fuzzy matching, the search results page, and ads in the suggestion list.

2. Estimate the scale

Requests come from keystrokes, not searches, which multiplies traffic. The numbers below are assumed for illustration.

A 50 GB index fits on one large machine, but not comfortably with room to build the next version beside it, and a single machine cannot serve 70,000 requests a second with headroom. So the index is split into a few shards, each replicated several times. The 100 ms budget is mostly network: a mobile round trip can take 50 ms or more, which leaves the server roughly 10 to 20 ms.

3. Define the API

GET /v1/suggest?q=how%20to%20m&lang=en&limit=8
  returns: 200
  Cache-Control: public, max-age=300
  { "prefix": "how to m",
    "suggestions": [ { "text": "how to make pancakes" },
                     { "text": "how to meditate" } ] }

GET /v1/suggest/recent?q=how%20to%20m      (signed in, Cache-Control: private)
  returns: 200 { "suggestions": [ { "text": "how to migrate postgres" } ] }

Normalize the prefix before using it as a cache key: lowercase, collapse whitespace, apply Unicode normalization. Otherwise "How to m" and "how to m" are cached separately.

4. Sketch the data model

A popular alternative to a custom trie is a flat table from prefix to its top k list, stored in a key-value store and capped at, say, 20 characters. It is the same idea with the tree flattened out: more duplication, but trivial to shard, cache and operate.

5. Make each lookup one short walk

The central decision is how much work happens per keystroke. Compare the options against the latency budget.

Build top k bottom-up: a node's list is the best k of its children's lists plus the query that ends at the node itself. Each merge is small, so a full build is linear in the number of nodes times k. Rank by a decayed score, for example each day's count multiplied by 0.9 for every day of age, so last month's spike fades without disappearing overnight.

6. The architecture

1. 1TypeThe client waits for a short pause in typing, cancels any request still in flight, and ignores a response whose prefix no longer matches the input.
2. 2ServeEdge cache first; on a miss, the service walks the owning shard's trie to the prefix node and returns its top k after filtering.
3. 3LogEach completed search, and whether a suggestion was chosen, goes onto the log stream.
4. 4BuildEvery day (or hour), aggregate counts, apply the blocklist, build a fresh trie and write it as a snapshot.
5. 5SwapShards load the new snapshot beside the old one and flip a pointer, keeping the previous one for rollback.

7. Scale it

• Shard by prefix range, weighted by traffic. Splitting by first letter is uneven: far more queries start with "s" than "x". Choose ranges from query volume ("a" to "ap", "aq" to "b", and so on) and keep the small range map in the router. See sharding for the general pattern.
• Serve the shortest prefixes separately. One- and two-character prefixes are the hottest and there are only a few thousand of them per language. Precompute their lists, hold them on every server and at the CDN.
• Cache at every layer. The CDN key is the normalized prefix plus language and region, with a lifetime of a few minutes. The browser caches responses too. A caching layer only works here because public suggestions are the same for everyone.
• Debounce, but carefully. A 100 ms debounce on top of a 100 ms request makes the box feel slow. Use a short pause (tens of milliseconds) or fire on every keystroke and cancel the previous request. While waiting, the client can filter the list it already has for the shorter prefix as a placeholder, knowing it may be incomplete.
• Sample the logs. Counting 1 in 10 searches keeps popular queries' ranking accurate, drops rare queries that would be pruned anyway, and reduces the personal data the pipeline handles.
• Freshness in layers. A daily full rebuild plus a streaming job that counts the last 15 minutes of queries and serves a small trending list, merged at request time. Only build the streaming layer if the freshness answer in section 1 required it.

8. What breaks, and what you do about it

9. Trade-offs to discuss

• Freshness or cost. Hourly rebuilds and a streaming layer cost far more than a nightly batch; many products never need them.
• Memory or latency. Storing top k at each node multiplies memory but removes all per-request searching. In a 100 ms budget, memory is the cheaper resource.
• Personalization or cacheability. A personalized list cannot be cached at the CDN. Keep the public list cacheable and fetch or merge a small personal list separately.
• Popularity or safety. Pure popularity surfaces whatever people type most, including harmful text. Filtering costs some relevance and needs human review of edge cases.

10. How to talk through it in the interview

• Say early that there are two systems, serving and building, and draw them separately.
• Spend the latency budget out loud: network, server, rendering.
• Mention filtering before the interviewer does.

Practicing this design with Natively

Run this as a mock interview, with someone else playing the interviewer or with you reading the prompt aloud and answering. Natively transcribes the conversation live and can suggest talking points for each question as it comes in; comparing them with what you said is a quick way to spot gaps such as snapshot validation or why personalized lists cannot be cached. A screenshot of your trie sketch can be captured and explained. The transcript and notes remain afterwards, so you can review where the latency budget discussion went off course.