Skills101

AdvancedSystem Design · Lesson 16 of 19 · Updated ·

System Design Case Study — Design Search Autocomplete (Typeahead)

Type "jav" into a search box and, before you finish the word, it suggests "java tutorial", "javascript", "java interview questions". This is autocomplete (also called typeahead). The interview question is: return the top 5 most popular searches that start with what the user has typed — on every keystroke, within about 100 ms.

The interesting part is that the answer must be ready before the request arrives. Let's design it.

Step 1 — Requirements

Functional

  • For a typed prefix, return the top 5 suggestions, ranked by popularity.
  • Suggestions come from what users have searched before.
  • Only prefix matching (no spelling correction in the first version).

Non-functional

  • Very fast: the whole round trip should feel instant, so the server should answer in a few milliseconds.
  • Highly available: if autocomplete fails, search still works, but the product feels broken.
  • Suggestions can be a little out of date — refreshing popularity every hour or every day is fine.
  • Filter offensive or unsafe suggestions.

Step 2 — Estimates

Assume 10 million daily active users, 10 searches each per day, about 6 typed characters per search before they pick a suggestion — each character is a request.

QuantityCalculationResult
Requests / day10 M × 10 × 6600 million
Requests / second600 M ÷ 86,400≈ 6,944 (peak maybe 2–3×)

That is a lot of tiny requests, each wanting an answer in milliseconds. A database query like SELECT ... WHERE query LIKE 'jav%' ORDER BY count DESC LIMIT 5 on billions of rows will not keep up. We need a data structure built for prefixes.

Step 3 — The trie

A trie (prefix tree) stores strings character by character. Each node represents a prefix; its children add one more character. All searches that start with "ja" live under the node for "ja".

A trie for the searches java, javascript, jam and joy: the root branches to j, then a and o; the node for "ja" stores its top suggestions javascript 900, java 700 and jam 50, so a lookup for "ja" walks two nodes and returns the stored list

A plain trie still has a problem: to find the top 5 under "j", you would have to visit every word below it — maybe millions. The standard fix is to store the top-k suggestions at every node when the trie is built. A lookup then only walks down the prefix (a few nodes) and returns the list already stored there.

class Node:
    def __init__(self):
        self.children = {}
        self.top = []                     # best (count, query) pairs for this prefix

class Autocomplete:
    def __init__(self, k=3):
        self.root, self.k = Node(), k

    def add(self, query, count):
        node = self.root
        for ch in query:
            node = node.children.setdefault(ch, Node())
            node.top.append((count, query))
            node.top.sort(key=lambda p: (-p[0], p[1]))   # highest count first, then A-Z
            del node.top[self.k:]                       # keep only the top k

    def suggest(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return [q for c, q in node.top]

searches = {"java": 700, "javascript": 900, "java interview questions": 400,
            "jam": 50, "joy of python": 120, "python": 1500, "pytorch": 300}
ac = Autocomplete(k=3)
for q, c in searches.items():
    ac.add(q, c)

for prefix in ["j", "jav", "java ", "py", "x"]:
    print(f"{prefix!r:8} -> {ac.suggest(prefix)}")
'j'      -> ['javascript', 'java', 'java interview questions']
'jav'    -> ['javascript', 'java', 'java interview questions']
'java '  -> ['java interview questions']
'py'     -> ['python', 'pytorch']
'x'      -> []

Cost of a lookup: walk len(prefix) nodes and return a stored list — O(length of prefix), no matter how many searches exist. The price is memory: every node keeps k entries. With k = 5 and short strings, that is acceptable, and it is what makes millisecond answers possible.

Step 4 — Where the counts come from: an offline pipeline

Updating the trie on every single search would mean millions of writes to a structure that must stay fast for reads. Instead, separate the write path from the read path:

Autocomplete design: search logs flow into a queue and an aggregation job that counts queries per hour or day; a builder creates a new trie snapshot and loads it into the suggestion servers, which answer prefix requests from memory behind a cache and CDN

  1. Every search is written to a log (through a queue such as Kafka).
  2. A batch job (hourly or daily) counts queries — often weighting recent days more, so trending searches rise.
  3. It removes unsafe or blocked terms and very rare queries.
  4. A builder creates a fresh trie with top-k at each node and saves a snapshot.
  5. Suggestion servers load the new snapshot into memory and swap it in, while still answering from the old one until the switch.

Reads never wait for writes. For breaking news, a smaller real-time pipeline can boost a few trending terms between full rebuilds.

Step 5 — Scaling the read path

  • Replicate: each suggestion server holds a full copy of the trie in memory; add servers behind a load balancer as traffic grows.
  • Shard when the trie is too big for one machine: split by first letters (a–f on shard 1, g–m on shard 2…). Prefixes are uneven — far more searches start with "s" than "x" — so balance shards using the real query counts, not the alphabet.
  • Cache aggressively: short prefixes like "j" or "py" are requested constantly and change only when the trie is rebuilt. Cache them in the server, in a CDN, and even in the browser with a short TTL.
  • Fewer requests from the client: wait about 100–200 ms after the last keystroke before sending (called debouncing), and reuse earlier results — the suggestions for "java" are a subset of those for "jav" when the list is long enough.

Step 6 — Extras interviewers like

  • Personalisation: blend global suggestions with the user's own recent searches on the client side.
  • Languages: support Hindi and other scripts by building the trie over Unicode characters; also handle transliteration ("namaste" vs "नमस्ते") as a separate mapping.
  • Safety: a blocklist applied when building, and a fast kill switch to remove a bad suggestion without waiting for the next rebuild.

Common mistakes

  • Running LIKE 'prefix%' with ORDER BY count on the main database for every keystroke.
  • Storing only words in the trie and searching the whole subtree for the top results on each request.
  • Updating counts in the serving trie on every search, so reads compete with millions of writes.
  • Sharding by first letter without checking how uneven the letters are.

Quick recap

  • About 6,944 requests per second of tiny, latency-critical reads.
  • A trie with the top-k suggestions stored at every node answers in O(prefix length).
  • Build the trie offline from aggregated search logs; swap snapshots into in-memory servers.
  • Replicate, shard by prefix using real counts, cache short prefixes, debounce on the client.
  • Filter unsafe suggestions at build time and keep a kill switch.

Practice what you learned

📝 Quiz: Design Search Autocomplete5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →