Design search autocomplete

In 2 minutes

I would treat autocomplete as a precomputed lookup, with a separate offline pipeline that builds it. For serving, the client waits 100 to 200 ms after typing, cancels older requests, and caches answers for the session. The request goes to a suggest API, which checks a small cache of hot prefixes and, on a miss, asks a server that holds its slice of the index in memory. Each prefix already has its top five completions stored next to it, so a lookup is a read, not a search. That is a prefix table or a compressed trie. At 14,000 requests a second at peak, and an index of at most about 8 GB, a few sharded and replicated servers are enough. I would shard by prefix range with boundaries taken from traffic. For the build, every submitted search is logged, a batch job counts queries, drops rare ones, expands each query into its prefixes, keeps the best five per prefix and writes a versioned snapshot. Servers load it and swap in one step, and a bad build never replaces the last good one. A small streaming job adds trending queries. If suggestions fail, search still works.

The question

Clarifying questions

• What ranks a suggestion: overall popularity, recent trends, or the person's own history? Global popularity can be computed ahead of time. Personal results must be merged in at request time.
• How fresh must suggestions be? Does a trending topic need to appear within minutes? Hourly rebuilds are cheap and simple. Minutes-level freshness needs a second, streaming path.
• How many suggestions do we show, and how fast must they appear? A small fixed k, such as 5, lets us store a short list per prefix. The latency budget decides how much work is allowed per keystroke.
• Which languages and scripts are supported? Each locale needs its own index and its own text normalisation, and some scripts have no spaces between words.
• Are there queries we must never suggest? Offensive terms and private data in the logs need a filter before anything is published.

Requirements

Functional

• Return the top 5 completions for any typed prefix.
• Rank by how often people search for a query, favouring recent activity.
• Rebuild suggestions regularly from search logs.
• Filter out blocked and sensitive queries.

Non-functional

• Latency: p99 under 100 ms end to end, so the list keeps up with typing.
• Availability of 99.9%. If suggestions fail, search still works.
• Freshness: popular new queries show up within an hour.
• Handles 14,000 suggestion requests a second at peak.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real product.
• 10 million people use search in a day, with 8 searches each. The client waits briefly after each keystroke, so a search sends about 3 suggestion requests.
• We keep the 10 million most popular queries, averaging 20 characters. Peak traffic is 5 times the average.
• Each trie node stores about 40 bytes: child links plus 5 query IDs. A search log entry takes about 100 bytes.

The arithmetic:

• Suggestion requests per second: 10M × 8 searches × 3 requests = 240M a day ÷ 86,400 s ≈ 2,780 → ≈ 2,800/s on average, about 14,000/s at a 5x peak
• Index size, upper bound: 10M queries × 20 characters = 200M nodes (shared prefixes make it fewer) × 40 bytes → ≤ 8 GB, so it fits in memory on a few machines
• Hot prefix cache: 100,000 hot prefixes × 5 results × 30 bytes → ≈ 15 MB, tiny
• Search log volume: 10M × 8 = 80M searches a day × 100 bytes → 8 GB a day to aggregate

High-level design

The Client waits a moment after each keystroke, then sends the current prefix to the Suggest API. The API checks the Prefix cache first, which holds answers for the most common prefixes. On a miss it asks a Suggest server, which keeps its share of the index in memory and returns the five best completions.

Serving never searches. Each entry in the index already has its top five answers written next to it, so a lookup is a read. That is why it is fast enough to run on every pause in typing.

The index is built offline. Every submitted search is written to a Query log. A Log aggregator counts queries on a schedule. The Index builder turns the counts into a new Suggest index snapshot, and the servers load it and switch over.

How a request flows

A popular prefix

1. The person pauses after typing 'sys'. The client sends that prefix, and cancels any older request.
2. The API checks the prefix cache for an answer to 'sys'.
3. A common prefix is in the cache, so the five suggestions come back in about a millisecond.
4. The client draws the list under the search box.

A rare prefix

1. The person types a less common prefix and pauses.
2. The API asks the prefix cache first.
3. Nothing is cached for this prefix: a miss.
4. The API sends the prefix to the Suggest server that owns that part of the alphabet.
5. The server reads the five precomputed answers stored at that prefix in memory. It never scans queries.
6. The API stores the answer in the cache if the prefix is busy enough, and returns it to the client.

Rebuild the index

1. Each time someone submits a search, the normalised query is appended to the log.
2. On a schedule the aggregator reads a batch of the log and counts each query, ignoring rare ones.
3. The builder expands each query into its prefixes and keeps the five highest-scoring queries for each.
4. It writes a new, versioned snapshot after checking its size and a sample of lookups.
5. Suggest servers load the new snapshot into memory and switch to it in one step. The old one stays for rollback.

Deep dive: a trie with top-k, or a prefix table

A trie is a tree where each step down adds one character, so a path from the root spells a prefix. To find all queries starting with 'sys', walk three steps down. But the subtree under 'sys' may hold millions of queries. Searching it at request time is far too slow.

The fix is to do the work ahead of time. Store the top five completions at every node. Then a lookup is: walk down one step per character of the prefix, and read the list at the end. That is O(length of the prefix), no matter how big the subtree is. Keep query IDs in the node, not the strings, and store each string once. A compressed trie, which merges chains of single-child nodes, saves a lot of memory.

A prefix table does the same job with a hash map. The key is the prefix, such as 'sys', and the value is the list of five answers. The build step writes one row per prefix. Lookup is one key read.

• Trie: compact in memory, and the walk is cheap. Needs custom code to build, serialise and load.
• Prefix table: simple, and it can live in any key-value store, a cache or even static files at a CDN. Prefixes repeat characters, so it uses more space, but you can cap prefix length and skip prefixes that almost nobody types.

I would start with the prefix table because the offline job writes it easily and any store, cache or CDN can serve it. If memory becomes the issue, I would switch the serving layer to a compressed trie without changing the pipeline.

Ranking is a score per query. A good one is a count weighted by age, so last week's searches count for more than last year's. Remove blocked terms at build time so the serving path stays simple.

Deep dive: the offline pipeline

Treat suggestions as a data pipeline, not a database. Each stage is a batch job that can fail and rerun without hurting users.

1. Collect. Append every submitted search, with a timestamp, to a log. Normalise first: lowercase, trim, collapse spaces, and apply Unicode normalisation.
2. Aggregate. Count each query per time window. Drop queries below a threshold. Requiring that a query comes from many different people also keeps private or one-off searches out of the public index.
3. Expand. For each query, emit every prefix of it with its score. Group by prefix, and keep the five highest in each group with a small heap.
4. Publish. Write the result as a new versioned snapshot. Check its size against the last one and run a few known lookups.
5. Switch. Servers load the snapshot into memory, then swap one pointer. The old version stays for rollback.

If a build fails or looks wrong, nothing changes and the last good snapshot keeps serving. That is the main reason to prefer snapshots over editing a live index in place.

A rebuild every hour or day is easy and cheap. It will miss a sudden trend such as breaking news. To cover that, run a small streaming job that counts the last 10 or 15 minutes of searches and keeps a short 'trending now' list per prefix. The server merges that list with the snapshot at request time. Keep the trending path small and optional, since the main index already handles nearly all traffic.

Deep dive: serving at typing speed

Most of the saving comes before a request is made.

• Debounce. The client waits 100 to 200 ms after the last keystroke before it sends anything. A fast typist triggers one request, not six.
• Cancel and ignore stale answers. If the person types another letter, drop the older request. Never show a reply for a prefix that is no longer in the box.
• Cache on the client. Remember the answer for each prefix typed in this session. Pressing backspace costs nothing.
• HTTP caching. Popular prefixes give the same answer to everyone, so they can carry a cache header and be served by the browser or a CDN for an hour.

On the server side, the Prefix cache holds the hot prefixes. Short prefixes such as single letters are the hottest, and a small cache covers most of the traffic. Our estimate puts 100,000 prefixes at about 15 MB.

For the index, shard by prefix. One option is to split the alphabet into ranges and give each range to its own servers. Pick the boundaries from real traffic, because some letters are much busier than others, and re-balance them when the data changes. Keep a few replicas of each shard so that a node failure is invisible. The alternative, sharding by a hash of each query, forces every prefix lookup to ask every shard and merge the results.

Fail quietly. If the suggest service is slow or down, the client shows no list and search still works. Typing must never wait for suggestions.

Trade-offs

• Where the work happens: Precompute the top 5 for every prefix over Search the subtree for each request. A lookup becomes a read in memory and stays fast for any prefix. The cost is more memory and a build step.
• Freshness: Hourly rebuilds plus a small trending list over Update the index on every search. Batch builds are simple, cheap and easy to check and roll back. The cost is that a brand-new trend can take minutes to show up.
• Sharding: By prefix range, with boundaries set from traffic over By hash of each full query. Each lookup goes to one shard. The cost is that busy letters need rebalancing as the data changes.
• Privacy: Publish only queries seen by many different people over Publish every query above a count. Private or personal searches never reach other users. The cost is that real but rare queries are not suggested.

Common follow-up questions

How do you keep offensive or private suggestions out?
Filter at build time with a blocklist, and with patterns that catch things such as email addresses and long digit strings. Require a minimum number of different people per query. Keep a fast path for the support team to remove a suggestion between builds.

How would you add personal suggestions?
Keep a short list of the person's recent searches in their profile or on the device. At request time, merge the matching ones into the global top 5, with the personal ones first. This keeps personal data out of the shared index.

How do you handle a typo in the prefix?
A trie lookup misses on a typo. Fuzzy matching needs a separate structure, such as an index of character n-grams, or a walk of the trie that allows one edit. Treat it as a second phase, and use it only when the exact lookup returns nothing.

How do you support several languages?
Build one index per language or locale, each with its own normalisation. Route the request by the locale the client sends. For scripts without spaces between words, split the text with a language-aware tokenizer, because 'prefix' means something different there.