# System Design Case Study — Design Search Autocomplete (Typeahead)

Source: https://skills101.in/learn/system-design/system-design-search-autocomplete — Skills101 free tutorial (System Design). Updated 2026-11-21.

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.

| Quantity | Calculation | Result |
|---|---|---|
| Requests / day | 10 M × 10 × 6 | **600 million** |
| Requests / second | 600 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](https://skills101.in/learn-img/system-design/trie-topk.svg)

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.

```python
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)}")
```

```text
'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](https://skills101.in/learn-img/system-design/autocomplete-design.svg)

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 quiz and free certificate: https://skills101.in/learn/system-design/system-design-search-autocomplete