The whole course ▾

System Design · Lesson 33 of 39 · Week 7

Design search autocomplete

Updated 22 Oct 2026 · By Akshay, software engineer, India · 5 min read

Type "piz", and ten suggestions appear before your next keystroke. Billions of queries a day, under a hundred milliseconds. Today: autocomplete.

The video for this lesson is coming soon.

New System Design videos go up at 6 pm. Subscribe on YouTube so you don't miss it.

Got a doubt? Ask in the comments under the video.Subscribe

Faster than you type

Faster than you type
What it must do
Top 10 suggestions for any
prefix
Ranked by how often people
search
Keeps up with new trends
Answers before the next
keystroke
The numbers
5B searches a day × ~5 letters
typed
= 25B requests ÷ 100,000 s =
250,000/s
Peak ~ 750,000 requests/s
Budget: under 100 ms, end to
end
WHAT THE NUMBERS DECIDE
Enormousreadrates,from
datathatchangesslowly:
precomputeeverything,and
answerwithalookup.

In lesson twenty-six, typeahead got one chapter. Today it gets a whole design, at the scale of the biggest search engines, where the answer must arrive before your next keystroke.

The requirements. For any prefix, the letters typed so far, show the ten best completions. Rank them by how often people actually search for them. Keep up with new trends, so a big news story appears in suggestions the same day. And answer before the next keystroke: people type a letter every hundred and fifty milliseconds or so, and late suggestions are useless.

Say five billion searches a day, with about five letters typed before each one is chosen: twenty-five billion suggestion requests a day, which is two hundred and fifty thousand a second, with a peak around three quarters of a million. And the whole round trip, phone to server and back, has a budget of under a hundred milliseconds.

So say what the numbers decide. Three quarters of a million requests a second, each needing an answer in milliseconds, leaves no time to search or rank anything on the fly. But which queries are popular changes slowly, over hours and days. So precompute everything, and make every answer a single lookup.

The trie

The trie
p
top: pizza,
paneer, petrol
pi
top: pizza, pink,
pixel
piz
top: pizza near
me, pizza hut
pizza
top: pizza near
me, pizza recipe
+ i
+ z
+ z, a
Top 10 at every node
1
Each node stores its top 10
completions
2
Answer = find the node, return its
list
3
No searching at request time

The data structure built for prefixes is called a trie: a tree where each step down adds one letter.

Each node of the trie is a prefix. The first letter, p, leads down to p-i after two letters, to p-i-z after three, and on to the whole word, pizza. Every query ever searched is a path from the top. To find completions for p-i-z, you'd walk down to that node, and look at every query below it. But below p, there are hundreds of millions of queries. Walking them on every keystroke is far too slow.

So here's the key trick: each node stores its own top ten completions, worked out in advance. The node for p-i-z holds pizza near me, pizza hut, and eight more, already ranked. Answering a request means: find the node for the prefix, and return its list. A handful of steps down the tree, and no searching or ranking at request time at all.

Built offline

Built offline
Query logs
every search
made
Build job
count, rank,
build
Trie
snapshot
Suggestion
servers
trie in memory
Search
box
count
queries
1
build trie
2
load
3
?q=piz
TWO SPEEDS
Buildingisslowandheavy,
doneoffline;servingisa
memorylookup,done
millionsoftimesasecond.

Storing the top ten at every node makes reading instant, and building expensive. So build it away from the requests.

Every search people make is written to the query logs. Every hour, or every day, a build job counts how often each query was searched, giving recent searches more weight, then builds the trie, with the top ten at every node, and saves it as a trie snapshot. Suggestion servers load the new snapshot into memory, and swap it in. The search box only ever talks to the suggestion servers, which do nothing but lookups.

That split is the whole design. Building is slow and heavy, but it happens rarely, and nobody waits for it. Serving is a memory lookup, happening three quarters of a million times a second. The same pattern appears whenever reads vastly outnumber changes: do the work once, ahead of time.

Fresh, safe and fast

Fresh, safe and fast
Keeping it fresh and safe
->
A small trending layer, every few minutes
->
Merge trending with the daily trie
->
Filter offensive and unsafe suggestions
Serving at scale
->
A full copy of the trie per server
->
Too big? Shard by first letters
->
Cache popular prefixes in the browser
->
Wait a moment between keystrokes

A trie built once a day has two problems: it's a day out of date, and it holds whatever people typed.

For freshness, add a small trending layer: a stream job, reading searches from Kafka, finds queries suddenly rising, and updates a small table of trending completions every few minutes. Suggestion servers merge those with the daily trie's results. And before anything is shown, filter it: offensive, unsafe or private suggestions are removed, because suggesting something is like saying it yourself.

To serve it fast, give every suggestion server a full copy of the trie, if it fits in memory, and add servers as traffic grows. If it's too big, shard it by the first letters of the prefix. Let the browser cache popular prefixes, so typing p-i again hits no server at all. And wait a short moment between keystrokes, so a fast typist sends one request, not six.

Why not just search?
A prefix query each time
Finds every match, every keystroke
Ranks at request time
Too slow at this rate
A precomputed trie
Top 10 stored per prefix
One lookup per keystroke
Fast and predictable
THE PRICE
Precomputingbuysspeed
andpaysinfreshnessand
memory.

A fair question: lesson twenty-six already has a search engine. Why not ask it for queries starting with p-i-z?

A prefix query on a search engine finds every match on every keystroke, then ranks them while the user waits. That's fine for a small app, like QuickBite's dish names. At three quarters of a million requests a second, it's far too slow and expensive. A precomputed trie stores the answer for every prefix, so each keystroke is one lookup, with the same speed every time.

The price: suggestions are as old as the last build, which the trending layer softens, and the trie, with ten completions stored at every node, takes a lot of memory. Limiting prefixes to the first twenty or so characters, and dropping very rare queries, keeps it in check.

In the interview

In the interview
SAY THIS IN THE INTERVIEW
Atriewiththetop10
ateverynode,built
offlinefromquerylogs,
servedfrommemory.
Follow-ups to expect
->
How do new trends appear
quickly?
->
What if the trie doesn't fit?
->
Personal suggestions?
THE COMMON MISTAKE
Searchingandranking
atrequesttime,
insteadofprecomputing
theanswers.

Design autocomplete, or typeahead, is a classic, because it tests precomputation and memory, not boxes.

Say it like this: a trie with the top ten completions stored at every node, built offline from query logs every hour or day, loaded into memory on suggestion servers, plus a trending layer updated every few minutes, and a safety filter. Then mention the client: caching, and waiting between keystrokes.

Then expect these. How do new trends appear quickly? A trending layer from a stream job, merged in. What if the trie doesn't fit in one machine's memory? Shard it by prefix. And personal suggestions, like your own recent searches? Keep a small per-user list, and blend it with the global results on the server.

The common mistake: querying a database or search engine with LIKE p-i-z, percent, on every keystroke. The answers to autocomplete barely change from minute to minute. Compute them once, and serve them a billion times.

Quick check

Quick check
?
Why store the top 10
completions at every trie
node?
So each request is one lookup:
no walking the subtree or
ranking while the user types.
?
A news event makes a new query
explode, but the trie rebuilds
once a day. What's the fix?
A trending layer, updated every
few minutes, merged with the
trie's results.
Remember
A trie, top 10 at every node
Built offline, served from
memory
Trending layer plus a safety
filter
Quick check

Why store the top 10 completions at every trie node?

Show the answer

So each request is one lookup: no walking the subtree or ranking while the user types.

Quick check

A news event makes a new query explode, but the trie rebuilds once a day. What's the fix?

Show the answer

A trending layer, updated every few minutes, merged with the trie's results.

Remember: a trie, with the top ten completions at every node. Built offline from query logs, and served from memory. And a trending layer for freshness, plus a safety filter. Tomorrow, the last design of the week: a notification system.

Practise with flashcardsYour progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.