Design Search Autocomplete

Search autocomplete — the "design top k" problem — is the little list of suggestions that pops up while you type in a search box. It looks simple, but interviewers love it because the hard parts are hidden: you have to rank suggestions by how popular they are, answer in under 100 ms (so the box does not feel laggy), and handle about 48,000 searches per second without crushing your database. The key trick is to stop using a normal database for reads and use a trie instead (more on what that is below).

Step 1: Ask questions and estimate the scale

Before designing anything, nail down exactly what you are building. Here are the standard answers for this problem:

• Match only the start of what the user typed (a "prefix match", not a search-anywhere match).
• Return the top 5 suggestions, ranked by how often each one has been searched before (its popularity).
• No spell check or autocorrect.
• Only lowercase English letters — no capitals, no symbols.
• 10 million daily active users (people who use it each day).

The non-functional requirements are really the whole point here. The system must be: fast (Facebook aims to show results within 100 ms, or the box feels laggy), relevant, sorted by popularity, able to grow (scalable), and rarely down (highly available).

Quick back-of-the-envelope math

Users                 = 10,000,000 per day
Searches per user/day = 10
Characters per query  ≈ 20   (about 4 words × 5 letters; 1 letter = 1 byte → 20 bytes)
Requests per query    ≈ 20   (one request for EACH character typed)

So typing dinner actually sends six requests: d, di, din, dinn, dinne, dinner.

Requests/sec      = 10,000,000 × 10 × 20 / 24 / 3600  ≈ 24,000 per second
Peak requests/sec = above × 2                          ≈ 48,000 per second
New data per day  = 10M × 10 × 20 bytes × 20% new      = 0.4 GB per day

Two numbers shape every later choice. First, 48,000 requests per second at peak — a normal database simply cannot sort the top results for every keystroke that fast, so we need a trie plus a cache. Second, only 0.4 GB of truly new searches per day — the data barely changes, so we can build the trie in the background (offline) instead of live.

Step 2: The high-level design

Split the system into two parts, right along the line the math drew:

The simplest version of the query service keeps a (query, frequency) table in a normal SQL database and answers each keystroke like this:

SELECT query, frequency
FROM   frequency_table
WHERE  query LIKE 'tw%'
ORDER  BY frequency DESC
LIMIT  5;

This is fine for a tiny dataset and a nice way to state the problem. But at 48,000 requests per second it breaks: every keystroke makes the database scan for matches and sort them. The deep dive fixes this.

Step 3: Deep dive — the trie

A plain trie stores words like tree, try, true, toy, wish, win as shared letter-paths. To rank them, we store a search count at the end of each word. Here is the basic lookup, where p = how long the prefix is and c = how many words sit under that prefix:

That works, but in the worst case it scans every word under the prefix on every single keystroke — way too slow for a 100 ms budget. Two fixes solve it:

1. Cap the prefix length. People rarely type very long queries, so limit a prefix to, say, 50 characters. Now finding the prefix spot is basically instant (it goes from O(p) to O(1)).

2. Store the top 5 at every spot, ahead of time. Instead of searching the words under a prefix, precompute the top 5 for each spot and store them right there. Answering a prefix becomes just reading that little list — no searching, no sorting.

spot "be" → [best:35, bet:29, bee:20, be:15, beer:10]

With both fixes, the whole lookup becomes O(1) (constant time, no matter the data size):

This trades more memory for more speed — every spot now carries a top-5 list — but for a feature whose entire job is to answer in under 100 ms, that trade is worth it.

Step 4: Deep dive — building the trie in the background

Updating the trie on every one of billions of daily searches would crush the live service, and the top suggestions barely move from day to day. So the data gathering service runs in the background, in batches:

Search Logs → Aggregators → Counted Data → Workers → Trie DB → Trie Cache

• Search Logs — raw records of every search, only ever added to (never edited), and not indexed.
• Aggregators — roll that flood of logs up into a popularity count. How often they run depends on how fresh the data must be: fast-moving products (like Twitter) count in short windows; for most cases once a week is enough. We assume the trie is rebuilt weekly.
• Workers — background servers that build the trie from the counted data and save it to the Trie DB.
• Trie DB — where the trie is stored on disk. Two options:
  • Document store (e.g. MongoDB): save the whole weekly trie as one big blob.
  • Key-value store: use each prefix as a key and that spot's data as the value.
• Trie Cache — an in-memory copy of the trie for fast reads; it takes a weekly snapshot from the DB.

Step 5: Deep dive — the query service and extras

Here is the improved live read path:

1. The request hits the load balancer (the traffic director).
2. It sends the request to an API server.
3. The API server reads the trie data from the Trie Cache and builds the suggestion list.
4. If the cache is missing the data (it crashed or ran out of memory), the server reads from the Trie DB and refills the cache, so every later request for that prefix is a fast hit.

A few extra ways to make the read path faster:

• AJAX requests — fetch the suggestions without reloading the whole page.
• Browser caching — suggestions change slowly, so let the browser remember them. Google tells the browser to keep them for one hour, for that one user only.
• Data sampling — at huge scale, logging every keystroke is wasteful, so log only 1 out of every N requests.

Trie operations

Scaling the storage

When the trie grows too big for one server, split it across several (this is "sharding"). The naive split is by first letter (a–m on server 1, n–z on server 2; split finer for more servers, up to 26). The catch: far more words start with c than with x, so this gives an uneven split. The fix is a shard-map manager that looks at real search volume and groups letters by load — for example, one server just for s, and one server for u–z together if their totals are similar.

Wrap-up

Search autocomplete is all about moving work off the hot path (the part that runs on every keystroke). A SQL LIKE … ORDER BY … LIMIT can describe the problem but cannot serve 48,000 requests per second in 100 ms, so we precompute. A trie with the top 5 stored at every spot makes reads O(1); building it in the background, weekly keeps the heavy work off the live path; and a cache, browser caching, and sampling trim the rest.

Common follow-up questions and the one-liners that answer them:

Practice

Try these to check you understood how autocomplete is served.