Autocomplete

What the interviewer is asking

"Design autocomplete" (also called typeahead) asks for the list that drops down under a search box while you type: likely searches that start with the letters typed so far. It looks small, but every keystroke of every user is a request, the busiest read in a search system, and each answer must come back in about 100 ms or the list lags behind the typing.

The interviewer watches whether you notice that, size it, and move the expensive work, ranking terms, out of the request and into a job that runs ahead of time. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Suggest terms that start with the prefix typed so far.
• Rank them by popularity: how often people searched them.
• Show the top 5 within about 100 ms of each keystroke, so the list keeps up with typing.

Park the rest: suggestions from your own history, typo fixes, other languages, and terms that trend within minutes (freshness comes back as a deep dive). Parking personalization matters: with one shared list per prefix, the answer for "ca" is the same for everyone, which lets browsers and a CDN cache it later.

2. Data: term counts from the search logs

Every search is already written to a log: when, who, and what. The suggestions need far less: a count per term, totaled from the log every day or hour. Leave out who searched what (a privacy cost with no use in version 1), the time of each search, and the clicked results (ranking by clicks comes later). Drop terms searched only once or twice: mostly typos and one-off text, sometimes private, like a phone number. The example used below:

term   searches, last day (say)
car    900
dog    800
cat    700
cup    600
care   500
card   300

3. The API: one call per keystroke

GET /suggestions?prefix=car
  → 200 OK   ["car", "care", "card"]

Up to 5 terms, most searched first (only 3 in the example start with "car"). Send the whole prefix every time, not just the new letter: if the server had to remember that Ana already typed "ca", every keystroke would have to reach the same server in order, and one lost request would garble the rest. With the whole prefix, any server can answer, and a GET with the prefix in the URL is what browsers and CDNs know how to cache.

4. The busy path: every keystroke

In the simplest design, a suggestion service and a database of term counts, Ana typing "a" after "c" goes:

1. Her browser sends GET /suggestions?prefix=ca.
2. The service asks the database for the terms starting with "ca".
3. The database sorts them by count, and the service keeps the top 5.
4. The browser shows the 5 under the search box.
5. Ana types "r", and it all starts again for "car".

A 6-letter search sends about 6 requests before anyone presses Enter: the path to make fast.

5. The numbers

From the interviewer: 100 million searches a day, about 6 keystrokes each. A day has 86,400 seconds; round it to 100,000 for a quick estimate.

• Suggestion requests: 100 million × 6 = 600 million a day, ÷ 100,000 = about 6,000 a second (about 7,000 with the exact 86,400). Busy hours run about 5× the average: about 30,000 a second (about 35,000 with 86,400).
• Searches: 1,000 a second on average, 5,000 at busy hours: how fast the counts change.
• The latency budget: about 100 ms from keystroke to list. On a phone the network round trip alone can take 50 ms or more (say), and the browser needs time to draw, so the server should take a few milliseconds, even at busy hours.

A disk seek takes about 10 ms, a read from memory about 100 ns: the answer must be ready in memory.

6. Services: rank ahead, read from memory

The simple design sorts the terms starting with the prefix on every keystroke. For "a", that's millions of terms, 30,000 times a second. Read replicas run more such queries side by side, but each is still far too slow; a cache in front of the database helps only repeated prefixes, and every miss still sorts.

Counts barely move from minute to minute, so ranking once an hour gives the same lists as ranking on every keystroke. Split the system in two:

• The build path: every search is written to a log stream (Pub/Sub and Streams). A batch builder reads it every hour, updates the counts, builds the ready-made answers and saves them as a snapshot in storage.
• The read path: suggestion servers load the newest snapshot into memory and only read it. They never write, so you can run as many identical copies as you need behind a load balancer.

7. Scale: cache popular prefixes near users

Every search passes through a one-letter and a two-letter prefix, so a third of the 30,000 requests a second ask for at most 702 different prefixes (26 + 26 × 26 letters), each answer the same for everyone until the next build. Let the reply say to keep it a few minutes (Cache-Control). A CDN edge near the user serves everyone nearby from its copy, which also shortens the network part of the 100 ms, and the browser reuses answers when someone deletes a letter and retypes it. Only misses reach your servers. Don't cache for days: a term you remove from the suggestions (say, an offensive one) must disappear quickly.

Many clients also debounce: they wait for a short pause in typing before sending, so a quick burst of keys sends one request, at the price of a small delay.

8. Deep dive: the trie and its top 5 lists

Inside each suggestion server the terms live in a trie (a prefix tree, as in the classic Implement Trie coding problem): each node stands for a prefix, and each step down adds one letter. Inserting car, cat, card, care, cup and dog gives 12 nodes: the root, then c and d, then ca, cu and do, and so on, each whole term keeping its count. Terms that start alike share nodes.

Finding the terms for "ca" is a walk: root, c, ca, two steps for two letters. Everything below that node starts with "ca": car and cat, and under car also card and care, 4 terms. The d branch is never touched.

To rank them, a plain trie must visit every node below the prefix, and short prefixes have the most: "c" visits 7 nodes, "card" none. In a real trie millions of nodes sit below "a", and even one million memory reads at 100 ns each take 100 ms, the whole budget.

So each node stores its top 5, worked out when the trie is built, bottom up: a node's list is the best of its own term and its children's lists. The example keeps 3 per node:

node   stored top three
car    car, care, card
cat    cat
ca     car, cat, care
cu     cup
c      car, cat, cup
d      dog

Note that "ca" gets care (500) from two levels down, through car's list. A request now walks down its prefix and reads 5 terms: a handful of memory reads, around 1 µs, whether the prefix is "a" or "cardi".

The cost is memory. Say the real trie has 100 million nodes; each list is 5 references of 8 bytes, so the lists take 100 million × 5 × 8 = 4 GB. Copying each term's text (about 20 bytes) into every list instead would take 10 GB, so store each term once and point to it. With the nodes themselves, say 50 bytes each, 5 GB, the whole trie is about 9 GB: it fits in one server's memory (say 64 GB), so every server holds a full copy.

9. Deep dive: keeping counts fresh

Searches keep arriving, 1,000 a second. Updating the live trie on each is costly: a search for "card" can change the lists of c, ca, car and card, so 1,000 searches a second would rewrite lists that 30,000 requests a second are reading, with locks or copies on every write. Letting every server rebuild its own trie repeats the work and lets servers disagree.

Instead, the builder makes a whole new trie every hour from the counts, checks it, and saves a snapshot. Each server loads the new one next to the old (both fit: about 18 GB), then switches over in one step, blue-green style, so no request ever sees a half-built trie; the old one is freed. Keep the last few snapshots so a bad build can be rolled back. For terms that trend within minutes, add a small layer later: recent counts from the log stream, mixed into the top 5 at read time.

10. Deep dive: sharding when it outgrows a server

If you keep far more terms and the trie outgrows one server, split it into shards, each prefix on one shard. One shard per first letter looks natural, but say "s" starts about 11% of requests and "x" about 0.1%: the "s" shard gets about 100× the traffic of the "x" shard.

Split by prefix ranges sized by traffic instead. With 26 shards, each should get about 4%, so "s" alone gets about 3 shards (sa–sh, si–so, sp–sz, say), while quiet letters like "x" share one with their neighbors. A small shard map from range to shard tells the router where each prefix goes, and each shard runs as a few identical copies. Hashing each term to a shard spreads the load too, but then the terms starting with "ca" land on every shard, and each keystroke must ask all of them and merge their lists.

What breaks first

• Breaking news: a term that explodes now waits up to an hour for the next build; the recent-counts layer fixes it.
• A bad build: a bug that drops half the terms reaches every server at once. Check each new trie (size, a few known prefixes) before the swap.
• Unwanted suggestions: offensive or private terms. Filter them with a block list at build time, besides the minimum count.
• A hot shard: add copies of it, and resize the ranges as traffic shifts.

Summary: the order to follow

1. Scope: the top 5 terms for a prefix, by popularity, within about 100 ms.
2. Data: term → count, from the search logs.
3. API: GET /suggestions?prefix=car, the whole prefix every time.
4. Busy path: one request per keystroke.
5. Numbers: about 30,000 requests a second at busy hours, a few ms on the server.
6. Services: a batch builder ranks ahead; suggestion servers read from memory.
7. Scale: browsers and a CDN keep answers for a few minutes.
8. Deep dives: a trie whose nodes store their top 5 (about 9 GB), a new trie swapped in every hour, and prefix ranges sized by traffic once it outgrows a server.

The same shape fits any read far busier than its writes: precompute the answers in a batch, serve them from memory, cache them near the users.