These are the notes for System Design episode 36. Rohan wants to make chai for his guests. He types three letters into the search box, h, o, w, and before he types the next one a list drops down: how to make chai, how to book tatkal. Today you design the system behind that list: you'll write the requirements (top suggestions per prefix, ranked, in about 0.1 s, on every keystroke), turn Google's "more than 5 trillion searches" a year into 1.6 million suggestion requests a second, find that scanning every past search costs 1,000,006 checks per keystroke and build a trie instead (44 nodes for "how to"), find that the single letter "h" still visits 100,083 nodes and keep the top 3 in every node instead (1 node), cut 16 requests per search to 3 with debouncing, see that caching just 1% of prefixes answers 62% of requests, and catch tonight's cricket match with a fresh layer that last night's build missed. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). Rohan, the searches and their counts are made up; the 10 letters per search, the 250 ms debounce wait, the 1/rank popularity curve and the trend weight of 3 are our own assumptions; the real-world facts come only from the sources at the end. The design here is ours, a textbook design for learning; it is not a description of how Google builds its autocomplete.
Autocomplete (also called typeahead) is a search box feature that suggests whole searches while you are still typing. Example: you type how and the box offers how to make chai.
The problems
| Problem | What it teaches |
|---|---|
| Rohan types "how to" | Requirements: top suggestions per prefix, ranked by popularity, trending, about 0.1 s, every keystroke |
| The scale | 5 trillion searches a year → 1.6 million suggestion requests a second |
| Scan every search | 1,000,006 checks per keystroke → a trie (prefix tree) |
| Short prefixes are slow | "h" visits 100,083 nodes → keep the top 3 in every node: 1 node |
| A request for every key | 16 requests → debounce: 3 |
| The same prefixes, again | Cache 1% of prefixes → 62% of requests answered |
| Missing today's trend | A nightly build plus a fresh layer, merged with a weight |
| Put it all together | Browser, CDN / cache, sharded and replicated suggest service, builder, filter |
Problem 0: Rohan types "how to" (requirements)
Rohan types h, o, w. Before the fourth letter, suggestions drop down, the most popular searches that start with what he typed. He taps one and he's done. Google says autocomplete "reduces typing by about 25 percent" and "saves over 200 years of typing time per day" (The Keyword, 2018).
A few words first:
- A prefix is the beginning of a word or phrase: the letters typed so far. Example:
how,how tandhow toare all prefixes ofhow to make chai. - A suggestion is one whole search offered for a prefix. Example:
how to make chaifor the prefixhow. - A keystroke is one key press. Typing
how to make chaiis 16 keystrokes (the spaces count). - A search log is the record of the searches people have made. Google says its predictions come from "the real searches that happen on Google".
- A count here is how many times a search was made; the higher the count, the more popular the search. Example (made up):
how to book tatkal: 9900.
Functional requirements (what the system does):
- Given a prefix, return the top suggestions: a few, say 3.
- Ranked by how popular each search is.
- Include what's trending today. Google says its predictions show common and trending searches, adjusted for things like location and previous searches.
Non-functional requirements (how well it does it):
- Fast: about 0.1 second, on every keystroke. Nielsen Norman Group says response times "should be either 0.1, 1.0, or 10 seconds"; 0.1 s is the tightest of the three.
- Huge: millions of requests a second (see below).
And an unusual rule: fast beats perfect. If a suggestion arrives after Rohan has typed the next letter, it's useless. A slightly less perfect list on time is better than the perfect list too late.
- Latency is the time between asking and getting the answer. Example: Rohan types
w, the list appears 80 ms later: a latency of 80 ms. - A millisecond (ms) is a thousandth of a second, so 0.1 s = 100 ms.
The scale
Google, quoted by Search Engine Land in March 2025: "We already see more than 5 trillion searches on Google annually." And every letter typed asks for suggestions. We assume 10 letters per search; that's our own guess.
searches_per_year = 5 * 10**12 # Google, 2025: "more than 5 trillion"
per_second = searches_per_year / (365 * 24 * 3600)
letters = 10 # letters typed per search (our guess)
print(f"searches per second: {per_second:,.0f}")
print(f"suggestion requests per second: {per_second * letters:,.0f}")
print("and each answer must arrive in about 0.1 s")
Output:
searches per second: 158,549
suggestion requests per second: 1,585,490
and each answer must arrive in about 0.1 s
- 5 trillion ÷ 31,536,000 seconds in a year = 158,549 searches a second.
- × 10 letters = 1,585,490 suggestion requests a second, about 1.6 million, each answered in about 0.1 s.
- A request is one message from the browser asking the server for something; here, "suggestions for this prefix, please".
Keep that number in mind. Every idea below has to survive it.
Problem 1: scan every search (a trie)
The obvious way first. Keep every past search with its count: six popular ones, plus a million rarer ones. For each keystroke, look at every search, keep the ones that start with the prefix, and return the top three.
searches = {"how to make chai": 9500, "how to book tatkal": 9900,
"how to lose weight": 8800, "how to learn python": 7600,
"hotstar ipl live": 9000, "hotel near me": 8000}
for i in range(1_000_000): # plus a million rarer ones
searches[f"search number {i}"] = 1
def suggest(prefix):
checked, found = 0, []
for q, count in searches.items(): # look at EVERY search
checked += 1
if q.startswith(prefix):
found.append((count, q))
return checked, [q for c, q in sorted(found, reverse=True)[:3]]
checked, top = suggest("how to")
print("suggestions:", " | ".join(top))
print(f"searches checked for ONE keystroke: {checked:,}")
print(f"at 1.6 million keystrokes a second: "
f"{checked * 1_585_490 / 1e12:.1f} trillion checks a second")
Output:
suggestions: how to book tatkal | how to make chai | how to lose weight
searches checked for ONE keystroke: 1,000,006
at 1.6 million keystrokes a second: 1.6 trillion checks a second
- The suggestions are right: the three most popular searches starting with
how to. - But one keystroke checked 1,000,006 searches. At 1.6 million keystrokes a second, that's 1.6 trillion checks a second. And a real search log has far more than a million searches.
- Why so slow? The searches starting with
how toare mixed in with everything else, so we have to look at all of them. This is a scan: reading every item, one by one.
Real life: finding a word in a dictionary
| A paper dictionary | Autocomplete |
|---|---|
| Jump to the H section: skip A to G | Root → h: one step per letter |
| Then HO, then HOW: narrower each step | h → o → w: walk down the prefix |
| Every word starting HOW sits together | The subtree below w: all the completions in one place |
The fix: a trie (prefix tree)
- A trie (from the word retrieval), also called a prefix tree, is a tree where each step down is one letter, so every search that shares a prefix shares the same path. Example:
how to make chaiandhotstar ipl liveshare the pathh→o, then split. - A node is one point in the tree; here, one letter on a path. The root is the empty starting node; a node's children are the nodes one letter below it. Example: the
onode is a child of thehnode. - A subtree is a node plus everything below it. Example: the subtree below
how toholds every search that starts withhow to. - In our code,
"$"marks the end of a whole search and stores its count.
searches = {"how to make chai": 9500, "how to book tatkal": 9900,
"how to lose weight": 8800, "how to learn python": 7600,
"hotstar ipl live": 9000, "hotel near me": 8000}
for i in range(100_000): # plus many rarer searches
searches[f"hindi song {i}"] = 1
trie = {} # each node: letter -> child
for q, count in searches.items():
node = trie
for ch in q:
node = node.setdefault(ch, {})
node["$"] = count # "$" marks a whole search
def suggest(prefix):
node = trie
for ch in prefix: # 1. walk down the prefix
node = node[ch]
found, stack, visited = [], [(node, prefix)], 0
while stack: # 2. visit EVERY node below
n, text = stack.pop(); visited += 1
for ch, child in n.items():
if ch == "$": found.append((child, text))
else: stack.append((child, text + ch))
return visited, [q for c, q in sorted(found, reverse=True)[:3]]
for p in ["how to", "h"]:
visited, top = suggest(p)
print(f"{p!r}:", " | ".join(top), f"\n nodes visited: {visited:,}")
Output:
'how to': how to book tatkal | how to make chai | how to lose weight
nodes visited: 44
'h': how to book tatkal | how to make chai | hotstar ipl live
nodes visited: 100,083
- Building: for each search, walk down letter by letter, creating a child node for each new letter (
setdefault), and put the count under"$"at the end. - Suggesting: (1) walk down the prefix, one node per letter; (2) visit every node in the subtree, collect the whole searches, sort by count, keep three.
how to: the right three, and only 44 nodes visited instead of a million checks.- But the single letter
h: 100,083 nodes! A short prefix has a huge subtree below it (here, every search starts withh), and the first letter is exactly what everyone types first. The trie fixed long prefixes, but not short ones.
Problem 2: short prefixes are slow (the top K in every node)
Real life: the bestseller shelf
| In a bookshop | In the trie |
|---|---|
| Thousands of books in a section: too many to look through | A big subtree: 100,083 nodes under h |
| A small bestseller shelf at the front of each section, worked out in advance | The top 3 stored in each node |
| Customers just grab from the shelf | Walk the prefix, return that node's list: done |
- Top K means the K best items by some score; here, the K most popular searches below a node, with K = 3. Example: the top 3 for
harehow to book tatkal,how to make chai,hotstar ipl live. - To precompute is to work out an answer in advance, before anyone asks, so the read is instant. Example: the bestseller shelf is arranged before the shop opens.
searches = {"how to make chai": 9500, "how to book tatkal": 9900,
"how to lose weight": 8800, "how to learn python": 7600,
"hotstar ipl live": 9000, "hotel near me": 8000}
for i in range(100_000): # plus many rarer searches
searches[f"hindi song {i}"] = 1
trie = {} # node: letter -> child
for q, count in searches.items():
node = trie
for ch in q:
node = node.setdefault(ch, {})
top = node.setdefault("top", []) # every node keeps its
top.append((count, q)) # best 3, ready to serve
top.sort(reverse=True); del top[3:]
def suggest(prefix):
node, visited = trie, 0
for ch in prefix: # walk down the prefix...
node = node[ch]; visited += 1
return visited, [q for c, q in node["top"]] # ...and that's it
for p in ["how to", "h"]:
visited, top = suggest(p)
print(f"{p!r}:", " | ".join(top))
print(f" nodes visited: {visited:,}")
Output:
'how to': how to book tatkal | how to make chai | how to lose weight
nodes visited: 6
'h': how to book tatkal | how to make chai | hotstar ipl live
nodes visited: 1
- While building, every node we pass keeps a list called
top: add the new search, sort, keep only three (del top[3:]). suggestnow just walks down the prefix and returns that node'stop. No searching below at all.how to: 6 nodes, one per letter.h: 1 node (down from 100,083), with the same right answers.- The work moved from reading time to building time. The price: more memory (every node stores up to three searches; Practice 9 counts them) and an update can touch many nodes (every node on the search's path). That's fine: reads happen millions of times a second, and we rebuild offline.
- Offline here means in the background, separately from answering users, so it can take its time. Example: rebuilding the trie at night from the day's search logs.
This is a top-K trie: a trie where every node stores its top K suggestions.
Problem 3: a request for every key (debouncing)
Now the browser. Rohan types how to make chai: 16 keys, typed fast (120 ms apart), with short pauses (400 ms) after how and after to. The simple app sends one request for every key.
- To debounce is to wait until the input has been quiet for a set time and only then act, so a burst of events becomes one. Example: a lift that waits a moment for more people before it closes its doors. Here: send the request only after the typing pauses for 250 ms (our own choice).
typed = "how to make chai"
gaps = [120] * len(typed) # ms between keys: a fast typist
gaps[3] = gaps[6] = 400 # short pauses after "how" and "to"
times, t = [], 0
for g in gaps:
t += g; times.append(t) # when each key was pressed
naive = len(typed) # one request per keystroke
WAIT = 250 # debounce: send only after 250 ms quiet
sent = [typed[:i + 1] for i in range(len(typed))
if i == len(typed) - 1 or times[i + 1] - times[i] >= WAIT]
print("requests, one per key:", naive)
print("requests with debounce:", len(sent), sent)
Output:
requests, one per key: 16
requests with debounce: 3 ['how', 'how to', 'how to make chai']
timesholds when each key was pressed. A prefix is sent only if the next key came at leastWAITms later (or it's the last key).- One per key: 16 requests. With debounce: 3: at the two pauses (
how,how to) and at the end. - Most of those 16 answers would have been thrown away before Rohan saw them, because he'd already typed the next letter.
- The wait is a trade-off: too short and nothing is saved, too long and Rohan sees nothing while typing (Practice 2 and the mistakes table).
Problem 4: the same prefixes, again (caching)
Millions of people type the same few prefixes: how, what, ipl, weather. A few prefixes are very common, most are rare. Our demo models that with a curve where the prefix ranked r is asked 1/r as often as the most popular one (prefix 2 half as often, prefix 10 a tenth as often). That curve is our assumption.
- A cache is a small, fast store of answers that were already worked out, kept close to where they're needed (episode 7). Example: the answer for
howkept in memory, so the trie isn't asked again. - A cache hit is a request the cache can answer; a miss is one it can't. The hit rate is hits ÷ all requests. Example: 62 hits out of 100 requests is a 62% hit rate.
- A lakh is 100,000 (an Indian number word); ten lakh is a million.
import random
random.seed(1)
prefixes = [f"prefix{r}" for r in range(1, 100_001)] # 1 lakh prefixes
weights = [1 / r for r in range(1, 100_001)] # a few are VERY common
requests = random.choices(prefixes, weights, k=1_000_000)
cache = set(prefixes[:1000]) # keep the top 1,000 prefixes' answers
hits = sum(p in cache for p in requests)
print(f"cache holds {len(cache) / len(prefixes):.0%} of prefixes")
print(f"...and answers {hits / len(requests):.0%} of requests")
Output:
cache holds 1% of prefixes
...and answers 62% of requests
- Ten lakh requests over one lakh prefixes, drawn with the 1/r weights (
random.seed(1)makes the run repeatable). - We cache only the top 1,000 prefixes: 1% of the prefixes answers 62% of the requests.
- So the answers for popular prefixes are cached at three places: in the browser, at a CDN near the user, and in memory in front of the trie servers. They take most of the load off the trie.
- A CDN (content delivery network) is a set of servers spread around the world that keep copies of answers close to users (episode 21). Example: a CDN server in Mumbai answers
howfor users in Mumbai without asking the main servers. - In memory means in the computer's RAM, which is much faster to read than a disk.
Problem 5: missing today's trend (a fresh layer)
Building a top-K trie takes time, so say we rebuild it every night from the search logs. Tonight, India plays Australia, and everyone suddenly searches for the live score. Last night's trie has never seen it.
- Trending means suddenly much more popular than usual, right now. Example:
india vs australia liveduring the match. - A layer here is one source of counts; we keep a big one built slowly (nightly) and a small one updated every few minutes (fresh). A weight is the number each layer's counts are multiplied by before they're added up, so one layer can count for more. Example: with weight 3, 4,000 recent searches score 12,000.
- To merge layers is to add up each search's weighted counts from all of them.
weekly = {"indigo flight status": 9000, "india gate": 6000, # built
"indian railway": 8000} # last night
recent = {"india vs australia live": 4000} # last 15 minutes only
def suggest(prefix, tables):
score = {}
for table, weight in tables: # merge the layers
for q, count in table.items():
if q.startswith(prefix):
score[q] = score.get(q, 0) + count * weight
return sorted(score, key=score.get, reverse=True)[:3]
print("nightly only:")
print(" ", "\n ".join(suggest("ind", [(weekly, 1)])))
print("with a fresh layer (weight 3, our choice):")
print(" ", "\n ".join(suggest("ind", [(weekly, 1), (recent, 3)])))
Output:
nightly only:
indigo flight status
indian railway
india gate
with a fresh layer (weight 3, our choice):
india vs australia live
indigo flight status
indian railway
weeklyis last night's build;recentholds only the last 15 minutes of searches.- Nightly only: no sign of the match.
- With the fresh layer: 4,000 × 3 = 12,000 beats 9,000, so
india vs australia livecomes first. The weight of 3 is our own choice; with weight 1 the trend wouldn't even make the top 3 (Practice 7). - Two layers: a big one rebuilt slowly, and a small one updated every few minutes. Google says its predictions show common and trending searches.
The full design
browser CDN / cache suggest service builder
─────── ─────────── ─────────────── ───────
Rohan types "how"
debounce: wait 250 ms
own cache? ── miss ────▶ popular prefix? ── miss ──▶ shard for "h..." (a replica)
top-K trie in memory
+ fresh layer, merged
shows the list ◀──────── cached answer ◀──────────── top 3 (already filtered)
▲
│ nightly: new top-K trie
│ every few minutes: fresh layer
search logs ──▶ count, filter, build
- The browser debounces the typing and keeps its own small cache of recent answers.
- Popular prefixes are answered by a CDN or cache near the user, so most requests never reach the trie.
- The rest go to the suggest service, which keeps a top-K trie in memory and merges in the fresh layer.
- One trie is too big for one machine, so it's split across servers by prefix: sharding (episode 12). Each part has copies, replicas, to share the reads.
- A builder makes the trie from the search logs: a full rebuild nightly, and a fresh layer every few minutes.
- Before anything is served, bad or harmful suggestions are filtered out.
- Sharding is splitting one big set of data across several machines, each holding a part. Example (ours): prefixes starting
atomon one server,ntozon another. - A replica is a copy of the same data on another machine, so reads can be shared and a crashed machine doesn't take the data with it. Example: three servers each holding the
atomshard. - The suggest service is the set of servers that answer "top suggestions for this prefix".
- The builder is the offline job that reads the search logs, counts and filters searches, and builds a new top-K trie.
- A filter here is a check that removes suggestions we must never show. Example (ours): a blocked-words list.
And the big idea: reads are instant because the hard work was done in advance. Precompute, then serve.
The whole chain
- 1,000,006 checks per keystroke → a trie: one step per letter (44 nodes for
how to). hvisited 100,083 nodes → the top 3 in every node: 1 node.- 16 requests per search → debounce: 3.
- 1% of prefixes cached → 62% of requests answered.
- Missed the trend → a fresh layer, merged with a weight.
- Browser, CDN, sharded and replicated trie, builder, filter.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
for q in searches: q.startswith(prefix) |
searches checked for ONE keystroke: 1,000,006 |
Looks at every search on every key | A trie: one step per letter |
| Collect the whole subtree on every request | 'h': ... nodes visited: 100,083 |
Short prefixes have huge subtrees | Store the top K in every node |
| Send a request on every keystroke | requests, one per key: 16 |
Most answers are out of date at once | Debounce, and cache popular prefixes |
node = node[ch] for a prefix nobody searched |
KeyError: 'z' (Practice 8) |
The letter isn't in the trie | Check if ch not in node: return [] |
A debounce wait shorter than the typing gap (WAIT = 100) |
requests with debounce: 16 [...] (Practice 2) |
Every gap (120 ms) is longer than the wait | Pick a wait longer than a fast typist's gap |
A debounce wait far too long (WAIT = 500) |
requests with debounce: 1 ['how to make chai'] (Practice 2) |
No suggestions until he stops typing | Keep the wait short: suggestions must arrive while typing |
| Filter bad suggestions after taking the top 3 | 1. top-K trie: ['how to book tatkal', 'how to make chai'] (Practice 4) |
A blocked search took one of the 3 places | Filter before building the top K |
| Only the nightly build | indigo flight status \| indian railway \| india gate |
The trend started after the build | Merge a fresh layer |
The KeyError traceback, with the file path shortened to main.py (Practice 8 has the code):
'ho': ['how to make chai', 'hotstar ipl live']
Traceback (most recent call last):
File "main.py", line 19, in <module>
print("'zomato':", suggest("zomato"))
~~~~~~~^^^^^^^^^^
File "main.py", line 15, in suggest
node = node[ch] # assumes the letter is there
~~~~^^^^
KeyError: 'z'
Mini project: a tiny autocomplete service
A top-K trie built from a (made-up) search log, inserts and count updates that keep every node's top K right, a prefix cache with hit and miss counts, a debounced browser, a fresh layer merged with a weight, and a filter applied before anything is stored, in under 90 lines:
# Mini project: a tiny autocomplete service. A top-K trie built from a search
# log, count updates, a prefix cache, a debounced browser, a fresh layer for
# trends and a filter for bad suggestions. One process, made-up searches.
K, WAIT, FRESH_WEIGHT = 3, 250, 3 # our own choices
BLOCKED = {"hack"} # words we never suggest (our list)
def allowed(query): # the filter, used before storing
return not BLOCKED & set(query.split())
class Trie:
def __init__(self):
self.root, self.counts = {}, {}
def add(self, query, n=1): # insert a search, or raise its count
if not allowed(query):
return
self.counts[query] = self.counts.get(query, 0) + n
entry, node = (self.counts[query], query), self.root
for ch in query:
node = node.setdefault(ch, {})
top = [e for e in node.setdefault("top", []) if e[1] != query]
top.append(entry)
top.sort(reverse=True)
node["top"] = top[:K] # every node keeps its best K
def top(self, prefix):
node = self.root
for ch in prefix: # one step per letter
if ch not in node:
return []
node = node[ch]
return node["top"]
class Service:
def __init__(self, nightly):
self.trie, self.recent, self.cache = nightly, {}, {}
self.hits = self.misses = 0
def record(self, query): # a fresh search: last few minutes
if not allowed(query):
return
self.recent[query] = self.recent.get(query, 0) + 1
for i in range(1, len(query) + 1): # its prefixes' cached answers are old
self.cache.pop(query[:i], None)
def suggest(self, prefix):
if prefix in self.cache:
self.hits += 1
return self.cache[prefix]
self.misses += 1
score = {q: c for c, q in self.trie.top(prefix)}
for q, c in self.recent.items(): # merge the fresh layer
if q.startswith(prefix):
score[q] = score.get(q, 0) + c * FRESH_WEIGHT
answer = sorted(score, key=score.get, reverse=True)[:K]
self.cache[prefix] = answer
return answer
def debounce(typed, gaps): # which prefixes the browser sends
times, t = [], 0
for g in gaps:
t += g; times.append(t)
return [typed[:i + 1] for i in range(len(typed))
if i == len(typed) - 1 or times[i + 1] - times[i] >= WAIT]
nightly = Trie() # last night's build from the logs
for q, n in {"how to make chai": 9500, "how to book tatkal": 9900,
"how to lose weight": 8800, "how to hack wifi": 9700,
"india gate": 6000, "indian railway": 8000,
"indigo flight status": 9000}.items():
nightly.add(q, n)
svc = Service(nightly)
print("1. top-K trie:", svc.suggest("how"))
nightly.add("how to learn python", 9950) # a new search
nightly.add("how to make chai", 500) # an old one, searched 500 more times
svc.cache.clear() # the new build replaces old answers
print("2. after an update:", svc.suggest("how"))
gaps = [120] * 16; gaps[3] = gaps[6] = 400
sent = debounce("how to make chai", gaps)
print(f"3. debounce: 16 keys -> {len(sent)} requests {sent}")
svc.hits = svc.misses = 0
for user in range(1000): # a thousand people type the same
svc.suggest("how" if user % 2 else "ind")
print(f"4. cache: hits {svc.hits}, misses {svc.misses}")
print("5. before the match:", svc.suggest("ind"))
for _ in range(4000):
svc.record("india vs australia live")
print(" 15 minutes later: ", svc.suggest("ind"))
Output:
1. top-K trie: ['how to book tatkal', 'how to make chai', 'how to lose weight']
2. after an update: ['how to make chai', 'how to learn python', 'how to book tatkal']
3. debounce: 16 keys -> 3 requests ['how', 'how to', 'how to make chai']
4. cache: hits 999, misses 1
5. before the match: ['indigo flight status', 'indian railway', 'india gate']
15 minutes later: ['india vs australia live', 'indigo flight status', 'indian railway']
- 1.
how to hack wifi(9,700) would be second, butallowedkeeps it out of the trie, so all three places go to good suggestions. - 2. Insert and update.
addremoves the search's old entry from each node'stopon its path, adds the new count, sorts and keeps K. The new searchhow to learn python(9,950) enters;how to make chaigoes from 9,500 to 10,000 and moves to first;how to lose weightdrops out. This simple update is correct when counts only go up; a count that goes down could need a search from deeper in the subtree to fill its place, which is one reason real builders rebuild the trie offline. - 3. The browser's debounce sends 3 of 16 prefixes, as in the episode.
- 4. A thousand requests for two prefixes:
howwas already cached by step 2,indmisses once, then everything is a hit: 999 hits, 1 miss. - 5. The cached
indanswer is served before the match. Eachrecordremoves the cached answers for the search's prefixes (i,in,ind, ...), so the next request recomputes and the trend shows up first: 4,000 × 3 = 12,000. Removing out-of-date entries like this is called cache invalidation.
Try extending it: make the fresh layer forget searches older than 15 minutes (store a time with each one); then split the trie into two shards, a to m and n to z, and send each prefix to the right one.
Practice
- Homework: in the TOPK demo, keep the top 5 instead of 3.
- Homework: in the DEBOUNCE demo, try
WAIT = 500. How many requests? Is that better? - Homework: in the CACHE demo, cache only 100 prefixes.
- Homework (comment): how would you filter bad suggestions?
- In the SCALE demo, assume 5 letters per search instead of 10.
- In the CACHE demo, cache 10,000 prefixes (10%). Is it ten times better than 1%?
- In the FRESH demo, give the fresh layer weight 1 instead of 3. What happens, and why?
- In the TOPK demo, call
suggest("zomato"). What happens? Fix it. - The top-K trie costs memory. Count its nodes and saved suggestions.
- Why is it fine that the top-K trie is slow to build?
1. Homework: in the TOPK demo, keep the top 5 instead of 3.
Solution
Change the two lines that keep the list (the comment too):
top.append((count, q)) # best 5, ready to serve
top.sort(reverse=True); del top[5:]
Output:
'how to': how to book tatkal | how to make chai | how to lose weight | how to learn python
nodes visited: 6
'h': how to book tatkal | how to make chai | hotstar ipl live | how to lose weight | hotel near me
nodes visited: 1
Still 6 and 1 nodes: the read cost doesn't depend on K. how to shows only 4, because only four searches start with it. The price is memory: up to 5 saved suggestions per node instead of 3.
2. Homework: in the DEBOUNCE demo, try WAIT = 500. How many requests? Is that better?
Solution
Change one line:
WAIT = 500 # debounce: send only after 500 ms quiet
Output:
requests, one per key: 16
requests with debounce: 1 ['how to make chai']
Fewer requests, but worse: Rohan's pauses (400 ms) are shorter than the wait, so he sees no suggestions at all until he has typed the whole search, which is the whole point of autocomplete lost. The opposite mistake, WAIT = 100, shorter than his 120 ms gaps, saves nothing:
requests, one per key: 16
requests with debounce: 16 ['h', 'ho', 'how', 'how ', 'how t', 'how to', 'how to ', 'how to m', 'how to ma', 'how to mak', 'how to make', 'how to make ', 'how to make c', 'how to make ch', 'how to make cha', 'how to make chai']
The wait must be longer than the gap between fast keystrokes, and short enough that a natural pause shows suggestions.
3. Homework: in the CACHE demo, cache only 100 prefixes.
Solution
Change one line:
cache = set(prefixes[:100]) # keep the top 100 prefixes' answers
Output:
cache holds 0% of prefixes
...and answers 43% of requests
The "0%" is rounding: 100 of 100,000 is 0.1%, and :.0% shows no decimals. With :.1% in the first print:
cache holds 0.1% of prefixes
...and answers 43% of requests
A tenth of a percent of the prefixes still answers 43% of the requests (under our 1/r assumption): the most popular prefixes carry a huge share of the traffic.
4. Homework (comment): how would you filter bad suggestions?
Solution
One simple way (ours): a list of blocked words, checked for every suggestion.
suggestions = ["how to make chai", "how to hack my friend's account",
"how to book tatkal", "how to lose weight"]
blocked = {"hack"} # words we never suggest (our list)
def safe(q):
return not any(word in blocked for word in q.split())
print([q for q in suggestions if safe(q)][:3])
Output:
['how to make chai', 'how to book tatkal', 'how to lose weight']
Where you filter matters. Filter in the builder, before the top K is chosen, as the mini project does. If you filter after taking the top 3 (in the mini project, delete the two if not allowed(query): return lines in add and add answer = [q for q in answer if allowed(q)] after the sort in suggest), the first line becomes:
1. top-K trie: ['how to book tatkal', 'how to make chai']
The blocked how to hack wifi took one of the three places, so only two suggestions are left. A word list is only a start; it misses harmful searches written without those words, so it's one layer among several, plus a way for people to report bad suggestions.
5. In the SCALE demo, assume 5 letters per search instead of 10.
Solution
letters = 5 # letters typed per search (our guess)
Output:
searches per second: 158,549
suggestion requests per second: 792,745
and each answer must arrive in about 0.1 s
Half the letters, half the requests: still about 800,000 a second. Debouncing has the same effect: fewer requests per search.
6. In the CACHE demo, cache 10,000 prefixes (10%). Is it ten times better than 1%?
Solution
cache = set(prefixes[:10_000]) # keep the top 10,000 prefixes' answers
Output:
cache holds 10% of prefixes
...and answers 81% of requests
No: 10 times the cache took the hit rate from 62% to 81%, not 10 times higher. The first few prefixes give most of the benefit; after that each extra cached prefix helps less. Under our 1/r curve: 0.1% → 43%, 1% → 62%, 10% → 81%.
7. In the FRESH demo, give the fresh layer weight 1 instead of 3. What happens, and why?
Solution
print("with a fresh layer (weight 1):")
print(" ", "\n ".join(suggest("ind", [(weekly, 1), (recent, 1)])))
Output:
nightly only:
indigo flight status
indian railway
india gate
with a fresh layer (weight 1):
indigo flight status
indian railway
india gate
The trend doesn't even make the top 3: 4,000 recent searches score 4,000, below india gate's 6,000. But those 4,000 came in 15 minutes, while the nightly counts built up over a much longer time, so comparing them one-to-one undervalues the trend. The weight makes up for that; 3 is our choice, and choosing it is a trade-off between catching trends quickly and letting a short burst push out searches that are popular every day.
8. In the TOPK demo, call suggest("zomato"). What happens? Fix it.
Solution
A smaller trie shows it (two searches, same suggest idea):
searches = {"how to make chai": 9500, "hotstar ipl live": 9000}
trie = {}
for q, count in searches.items():
node = trie
for ch in q:
node = node.setdefault(ch, {})
top = node.setdefault("top", [])
top.append((count, q))
top.sort(reverse=True); del top[3:]
def suggest(prefix):
node = trie
for ch in prefix:
node = node[ch] # assumes the letter is there
return [q for c, q in node["top"]]
print("'ho':", suggest("ho"))
print("'zomato':", suggest("zomato"))
Output (file path shortened to main.py):
'ho': ['how to make chai', 'hotstar ipl live']
Traceback (most recent call last):
File "main.py", line 19, in <module>
print("'zomato':", suggest("zomato"))
~~~~~~~^^^^^^^^^^
File "main.py", line 15, in suggest
node = node[ch] # assumes the letter is there
~~~~^^^^
KeyError: 'z'
Nobody has searched anything starting with z, so there's no z child: a KeyError (Python's error for looking up a key that isn't in a dictionary). The fix: no node means no suggestions.
searches = {"how to make chai": 9500, "hotstar ipl live": 9000}
trie = {}
for q, count in searches.items():
node = trie
for ch in q:
node = node.setdefault(ch, {})
top = node.setdefault("top", [])
top.append((count, q))
top.sort(reverse=True); del top[3:]
def suggest(prefix):
node = trie
for ch in prefix:
if ch not in node: # nobody ever searched this
return [] # no suggestions, no crash
node = node[ch]
return [q for c, q in node["top"]]
print("'ho':", suggest("ho"))
print("'zomato':", suggest("zomato"))
Output:
'ho': ['how to make chai', 'hotstar ipl live']
'zomato': []
9. The top-K trie costs memory. Count its nodes and saved suggestions.
Solution
searches = {"how to make chai": 9500, "how to book tatkal": 9900,
"how to lose weight": 8800, "how to learn python": 7600,
"hotstar ipl live": 9000, "hotel near me": 8000}
for i in range(100_000):
searches[f"hindi song {i}"] = 1
trie = {}
for q, count in searches.items():
node = trie
for ch in q:
node = node.setdefault(ch, {})
top = node.setdefault("top", [])
top.append((count, q))
top.sort(reverse=True); del top[3:]
nodes, stored, stack = 0, 0, [trie]
while stack: # count every node below the root
n = stack.pop()
for ch, child in n.items():
if ch == "top": continue
nodes += 1; stored += len(child["top"])
stack.append(child)
print(f"searches: {len(searches):,}")
print(f"nodes: {nodes:,}")
print(f"saved suggestions (3 per node at most): {stored:,}")
Output:
searches: 100,006
nodes: 100,083
saved suggestions (3 per node at most): 120,117
100,006 searches made 100,083 nodes, and the nodes store 120,117 saved suggestions: more entries than there are searches. (In Python each entry is a reference to the same string, not a copy, but it still takes space.) That's the price of instant reads, and one reason the full trie is sharded across machines.
10. Why is it fine that the top-K trie is slow to build?
Solution
Because building happens offline and rarely (nightly, plus a small fresh layer every few minutes), while reads happen about 1.6 million times a second and must take about 0.1 s. Spending more time once, in the background, to make every one of those reads walk just one node per letter is a very good trade. The users never wait for the builder; they only wait for the read.
Quick quiz
prefix 'h'
subtree below it: 100,083 nodes
answer needed in about 0.1 s
Why does each node in our trie store its top 3 searches?
- A. To save memory
- B. To make a read one node per letter
- C. To make building faster
- D. To sort the searches by letter
Answer
B. Each node already has its best answers, so a read only walks down the prefix, one node per letter (h: 100,083 nodes → 1). It actually costs more memory and building time, not less, so A and C are wrong.
Interview questions: "Design search autocomplete / typeahead"
1. Clarify requirements. How many suggestions per prefix? Ranked by what (popularity, freshness, the user's location or history)? Must trends appear, and how quickly? Expected traffic? Latency target? Do we need to filter harmful suggestions? Then state: top 3 to 10 suggestions per prefix, ranked by popularity, trends within minutes, about 0.1 s per keystroke, millions of requests a second, and fast beats perfect.
2. Estimate. "More than 5 trillion searches a year (Google, 2025) is about 158,000 a second; with about 10 letters per search (my assumption), about 1.6 million suggestion requests a second before debouncing and caching."
3. Components.
- Browser: debounce, a small local cache.
- CDN / cache: answers for popular prefixes, close to users.
- Suggest service: a top-K trie in memory, sharded by prefix, with replicas; merges the fresh layer.
- Builder: reads the search logs, counts, filters, builds a new trie nightly; a fresh layer every few minutes.
- Filter: removes bad or harmful suggestions before they are stored and served.
4. The hard parts. Short prefixes (the top K in every node); the request rate (debounce plus caching); freshness (the two layers and their weights, and invalidating cached answers); memory (K entries per node, sharding); filtering.
5. Scale and reliability (general knowledge). Shard by prefix, but watch for uneven shards (far more searches start with some letters than others), so split busy ranges further; several replicas per shard behind a load balancer; if the suggest service is slow or down, show no suggestions rather than block the search box, since fast beats perfect.
Common follow-ups:
- Why not a database query like
LIKE 'how%'on every keystroke? (It still has to find and rank every match for short prefixes at 1.6 million requests a second; precomputing the top K makes each read a few steps.) - How do you update counts? (Collect them from the search logs and rebuild offline; apply the fresh layer for the last few minutes instead of changing the big trie live.)
- How do you personalise? (Merge another small layer, such as the user's own recent searches, with its own weight; same idea as the fresh layer.)
- How long should the debounce wait be? (Longer than the gap between fast keystrokes, shorter than a natural pause; ours is 250 ms.)
- What if a cached answer is out of date when a trend starts? (Short expiry times for cached answers, or invalidate the prefixes of a fast-rising search.)
Glossary
| Term | Meaning |
|---|---|
| Autocomplete / typeahead | Suggesting whole searches while the user is still typing |
| Prefix | The beginning of a word or phrase: the letters typed so far, e.g. how |
| Suggestion | One whole search offered for a prefix, e.g. how to make chai |
| Keystroke | One key press; how to make chai is 16 |
| Request | One message from the browser asking the server for something |
| Search log | The record of the searches people have made |
| Count / popularity | How many times a search was made; higher means more popular |
| Functional requirement | What the system must do, e.g. return the top suggestions |
| Non-functional requirement | How well it must do it, e.g. within 0.1 s |
| Latency | The time between asking and getting the answer |
| Millisecond (ms) | A thousandth of a second; 0.1 s = 100 ms |
| Response time limits | Nielsen Norman Group's 0.1, 1.0 and 10 seconds; 0.1 s is the tightest |
| Scan | Reading every item one by one to find the matches |
| Trie / prefix tree | A tree where each step down is one letter, so shared prefixes share a path |
| Node | One point in the tree; here one letter on a path |
| Root | The empty starting node of the trie |
| Child | A node one letter below another |
| Subtree | A node plus everything below it: all completions of a prefix |
"$" marker |
Our code's mark for the end of a whole search, holding its count |
| Top K | The K best items by a score; here the K most popular searches below a node (K = 3) |
| Top-K trie | A trie where every node stores its top K suggestions |
| Precompute | Work out an answer in advance so the read is instant |
| Offline | In the background, separately from answering users |
| Rebuild | Building a fresh trie from the search logs, e.g. nightly |
| Builder | The offline job that counts, filters and builds the trie |
| Debounce | Wait until input has been quiet for a set time, then act once |
| Cache | A small, fast store of answers already worked out |
| Cache hit / miss | A request the cache can / can't answer |
| Hit rate | Hits ÷ all requests, e.g. 62% |
| Cache invalidation | Removing cached answers that are out of date |
| In memory | In the computer's RAM, much faster than disk |
| CDN | Content delivery network: servers near users that keep copies of answers |
| 1/r popularity curve | Our assumption: the prefix ranked r is asked 1/r as often as the top one |
| Lakh | 100,000; ten lakh is a million |
| Trending | Suddenly much more popular than usual, right now |
| Layer | One source of counts: the big nightly one or the small fresh one |
| Fresh layer | A small table of the last few minutes' searches |
| Weight | The number a layer's counts are multiplied by before adding up (ours: 3) |
| Merge | Adding up each search's weighted counts from all layers |
| Suggest service | The servers that answer "top suggestions for this prefix" |
| Sharding | Splitting one big set of data across machines, e.g. by prefix |
| Replica | A copy of the same data on another machine, to share reads and survive crashes |
| Filter | A check that removes suggestions we must never show |
| KeyError | Python's error for looking up a key that isn't in a dictionary |
Summary
- Autocomplete must return the top few suggestions for a prefix, ranked by popularity, including trends, in about 0.1 s on every keystroke; here fast beats perfect.
- Google's "more than 5 trillion searches" a year, at our assumed 10 letters each, is about 1.6 million suggestion requests a second.
- Scanning every search costs 1,000,006 checks per keystroke; a trie walks one node per letter (44 nodes for
how to). - A short prefix still has a huge subtree (
h: 100,083 nodes); storing the top K in every node makes the read 1 node: the work moves from reading to building. - Debouncing turns 16 requests into 3; caching the top 1% of prefixes answers 62% of requests (under our 1/r assumption), in the browser, at a CDN and in memory.
- A nightly build misses today's trend; a fresh layer, merged with a weight (ours: 3), puts
india vs australia livefirst. - The full design: browser → CDN / cache → a sharded, replicated suggest service with a top-K trie in memory → a builder fed by the search logs, with bad suggestions filtered out. Reads are instant because the work was done in advance.
Next episode: your OTP arrives in seconds, your order update a minute later, and offers never at 3 am. Design a notification system.
Sources: Google, The Keyword, "How Google autocomplete works in Search" (Danny Sullivan, 20 Apr 2018): autocomplete "reduces typing by about 25 percent"; "saves over 200 years of typing time per day"; predictions come from "the real searches that happen on Google", common and trending, adjusted for location and previous searches. Search Engine Land, Mar 2025, quoting Google: "We already see more than 5 trillion searches on Google annually." Nielsen Norman Group, "The 3 Response Time Limits in Interaction Design": response times "should be either 0.1, 1.0, or 10 seconds"; 0.1 s is the tightest. The 10 letters per search, the 250 ms debounce wait, the 1/rank popularity curve, the trend weight of 3, the blocked-words list, the shard ranges and all searches and counts in the demos are our own stated assumptions; tries, top-K lists, debouncing, caching, sharding and replicas are general textbook knowledge, and the design is ours, not a description of Google's system.