Design a Search Autocomplete System

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 13 — rewritten and condensed for teaching.

When you type "dinner" into Google or Amazon, a list of suggestions appears below the box. This feature goes by autocomplete, typeahead, search-as-you-type, or incremental search. As an interview question, it's also called "design top k" or "design the top k most searched queries."

What you'll be able to do after this lesson:

• Estimate the request rate for typeahead, which sends a request on every keystroke.
• Build a trie that caches the top k results at every node, so lookups take O(1).
• Separate query serving from data gathering: logs, aggregators, workers, Trie DB, and Trie Cache.
• Update and filter the trie correctly, and shard it by prefix based on real traffic distribution.

---

Step 1: Understand the Problem and Establish Scope

Candidate asks	Interviewer answers
Match only at the beginning of a query, or in the middle too?	Only at the beginning
How many suggestions?	5
How do we choose which 5?	Popularity, meaning historical query frequency
Spell check?	No
Language?	English (multi-language if time allows)
Capitals or special characters?	No, lowercase letters only
Users?	10 million DAU

Requirements

• Fast: suggestions must appear while the user types. Facebook's typeahead targets under 100 ms, and anything slower stutters.
• Relevant to the prefix typed.
• Sorted by popularity (or another ranking model).
• Scalable to high traffic.
• Highly available even when parts of the system are offline, slow, or seeing network errors.

Back-of-the-envelope estimation

• 10 M DAU, each making 10 searches per day.
• About 20 bytes per query: ASCII (1 byte per character), 4 words × 5 characters.
• Each keystroke sends a request, so typing "dinner" sends six:

search?q=d
search?q=di
search?q=din
search?q=dinn
search?q=dinne
search?q=dinner

Quantity	Calculation	Result
QPS	10 M users × 10 queries × 20 characters ÷ 86,400 s	≈ 23,000, call it ~24,000
Peak QPS	2 × QPS	~48,000
New data per day	10 M × 10 × 20 bytes × 20% new queries	0.4 GB/day

---

Step 2: High-Level Design

Two services:

• Data gathering service: collects user queries and aggregates them. Real-time aggregation is a starting point, though not practical at scale.
• Query service: given a prefix, returns the 5 most frequently searched queries.

Data gathering (naive)

Keep a frequency table. As users search "twitch", "twitter", "twitter", and "twillo", the table updates:

query	frequency
twitch	1
twitter	2
twillo	1

Query service (naive)

Given a frequency table like this one:

query	frequency
twitter	35
twitch	29
twilight	25
twin peak	21
twitch prime	18
twitter search	14
twillo	10
twin peak sf	8

typing "tw" shows the top 5. In SQL:

SELECT * FROM frequency_table
WHERE query LIKE 'tw%'
ORDER BY frequency DESC
LIMIT 5;

This works for small data, but at scale the database becomes the bottleneck. The deep dive fixes that.

---

Step 3: Design Deep Dive

The trie data structure

A trie (pronounced "try," from retrieval) is a tree that stores strings compactly:

• The root is the empty string.
• Each node holds one character, and in principle has 26 children (empty links aren't drawn).
• Each node represents a prefix. Some nodes are also complete queries.

Here's a trie holding "tree", "try", "true", "toy", "wish", and "win", with frequencies:

flowchart TB
  R(("root")) --> T((t)) & W((w))
  T --> TR((tr)) & TO((to))
  TR --> TRE((tre)) & TRU((tru)) & TRY["try: 29"]
  TRE --> TREE["tree: 10"]
  TRU --> TRUE["true: 35"]
  TO --> TOY["toy: 14"]
  W --> WI((wi))
  WI --> WIS((wis)) & WIN["win: 50"]
  WIS --> WISH["wish: 25"]

Basic top-k lookup. Let p be the prefix length, n the number of nodes, and c the number of nodes in the prefix's subtree.

1. Find the prefix node: O(p).
2. Traverse its subtree to collect every valid query: O(c).
3. Sort and take the top k: O(c log c).

For example, with k = 2 and the prefix "tr": find node "tr", collect [tree: 10], [true: 35], [try: 29], and return true: 35, try: 29.

The total is O(p) + O(c) + O(c log c). In the worst case that means traversing the whole trie, which is too slow. Two optimizations fix it.

Optimization 1: limit the prefix length

Users rarely type long queries. Capping p at, say, 50 turns "find the prefix" into O(1).

Optimization 2: cache the top k at every node

Store the top k queries for each prefix on its node. With k = 5, the "be" node might hold [best: 35, bet: 29, bee: 20, be: 15, beer: 10].

This trades space for time: every node now carries a small list. But fast responses are the top requirement, so the trade is worth it.

After both optimizations:

1. Find the prefix node: O(1).
2. Return its cached top k: O(1).

The whole lookup is O(1).

Practice: a trie with cached top-k

Implement Trie.set(query, freq) and Trie.suggest(prefix):

• Each node has children, freq (set only if the node is a complete query), and top, a list of up to k (query, freq) pairs sorted by frequency descending, then query ascending.
• set creates or updates the query's node, then recomputes top bottom-up along the path from that node to the root. Each node's top is the best k among its own query (if it has one) and the union of its children's top lists.
• suggest(prefix) walks to the prefix node and returns its top, or [] if the prefix doesn't exist.

Rebuilding from the children's cached lists is what keeps this correct when a frequency decreases: a query that wasn't cached before can move up into the list.

Input: line 1 is k, and each remaining line is set <query> <freq> or get <prefix> (use get - for the empty prefix).

The last test is the subtle one. When best drops from 35 to 5, the "b" node must pick up buy: 14, which wasn't in any cached list on that path before. A naive update that only re-sorts the existing cache would miss it. Rebuilding each ancestor from its children's lists finds it.

Data gathering service

Updating the trie on every query is impractical:

• Users enter billions of queries a day, and constant trie updates would slow the query service down.
• Top suggestions don't change much from minute to minute once the trie is built.

How fresh the data must be depends on the product. Twitter needs near-real-time suggestions, while many Google queries barely change from day to day. In both cases, though, the trie is built from analytics and logging data.

flowchart LR
  LOG[(Analytics logs)] --> AGG[Aggregators] --> AD[(Aggregated data)] --> WK[Workers] --> TDB[(Trie DB)]
  TDB -- "weekly snapshot" --> TC[(Trie Cache)]

• Analytics logs: raw, append-only, unindexed records of queries.

  query	time
  tree	2019-10-01 22:01:01
  try	2019-10-01 22:01:05
  tree	2019-10-01 22:01:30
  toy	2019-10-01 22:02:22
  tree	2019-10-02 22:02:42
  try	2019-10-03 22:03:03

• Aggregators: logs are huge and in the wrong shape, so aggregate them. Real-time products aggregate over short windows. Many others are fine weekly. We assume the trie is rebuilt weekly.

• Aggregated data: one row per query per week, where time is the week's start and frequency is that week's count.

  query	time	frequency
  tree	2019-10-01	12000
  tree	2019-10-08	15000
  tree	2019-10-15	9000
  toy	2019-10-01	8500
  toy	2019-10-08	6256
  toy	2019-10-15	8866

• Workers: servers that run asynchronous jobs on a schedule, build the trie, and store it in the Trie DB.

• Trie Cache: a distributed in-memory cache holding the trie for fast reads, refreshed from a weekly snapshot of the DB.

• Trie DB: persistent storage, with two options:

  1. A document store such as MongoDB: serialize each week's trie snapshot and store it.
  2. A key-value store: map each prefix to a key and each node's data to the value. For example, "be" → [best: 35, bet: 29, bee: 20, be: 15, beer: 10]. This is the store from Lesson 6.

Practice: weekly aggregation

Implement aggregate(logs). Each log is a (query, 'YYYY-MM-DD') pair. Group the logs by week start, the Monday on or before the date (date - timedelta(days=date.weekday())), and by query, and count them. Return (week_start, query, frequency) tuples sorted by week, then frequency descending, then query.

Query service

flowchart LR
  U[User] -- "1" --> LB[Load balancer] -- "2" --> API[API servers]
  API -- "3" --> TC[(Trie Cache)]
  TC -. "4: miss → replenish" .-> TDB[(Trie DB)]

1. The query reaches the load balancer.
2. It's routed to an API server.
3. The API server reads trie data from the Trie Cache and builds the suggestions.
4. On a cache miss, for example when a cache server ran out of memory or went offline, the data is replenished from the Trie DB, so later requests for that prefix hit the cache.

More optimizations, because typeahead has to be very fast:

• AJAX requests. Fetch suggestions in the background without reloading the page.

• Browser caching. Suggestions rarely change within minutes, so let the browser cache them. Google caches typeahead results for an hour:

  cache-control: private, max-age=3600

  private means for one user only, so shared caches must not store it. max-age=3600 means 3,600 seconds, one hour.

• Data sampling. Logging every query at this scale is expensive, so log 1 out of every N requests.

Trie operations

• Create: workers build the trie from aggregated data (from the analytics log or DB).
• Update, in one of two ways:
  1. Rebuild weekly and swap the new trie in. This is the preferred approach.
  2. Update individual nodes in place. It's slow, but acceptable for small tries. Because ancestors cache their descendants' top queries, every ancestor up to the root must be updated as well. That's exactly what the exercise's bottom-up recomputation does. For example, setting "beer" from 10 to 30 changes the cached lists at "beer", "bee", "be", "b", and the root.
• Delete: hateful, violent, sexually explicit, or dangerous suggestions must go. Put a filter layer in front of the Trie Cache, so rules can remove results immediately, and delete the data from the database asynchronously, so the next weekly build is clean.

flowchart LR
  API[API servers] --> F[Filter layer] --> TC[(Trie Cache)]

Scaling the storage

When the trie no longer fits on one server, shard by prefix.

• First-level sharding by first letter: with 2 servers, a–m and n–z. With 3, a–i, j–r, s–z. That goes up to 26 shards.
• Deeper sharding by second or third letter. For example, a splits into aa–ag, ah–an, ao–au, av–az.

The catch: far more words start with c than with x, so letter-based shards are uneven. The fix is to analyze the historical distribution and let a shard map manager keep a lookup table of which prefixes live where. If s gets about as much traffic as u–z combined, give s its own shard and put u–z together on another.

flowchart LR
  WS[Web servers] -- "1. which shard for prefix?" --> SMM[Shard map manager]
  SMM -- "2. shard N" --> WS
  WS -- "3. read" --> SH[(Shard N)]

Practice: build a balanced shard map

Implement build_shards(counts, n). counts maps first letters to historical query counts (missing letters count 0). Walk a through z in order, adding each letter's count to the current shard. Close the current shard right after a letter that brings its total to at least total / n, as long as fewer than n - 1 shards have been closed. The last shard runs to z. Return a list of (first_letter, last_letter) ranges.

shard_for(query, shards) returns the index of the range containing the query's first letter.

Input: line 1 is n, line 2 is letter:count pairs, and line 3 lists queries to look up.

Check: autocomplete design

Quiz

Tries, gathering, and scaling

1 / 5

Why cache the top k queries at every trie node instead of computing them per request?

Pick an answer to see if you are right.

---

Step 4: Wrap Up

Follow-up questions an interviewer might ask:

How would you support multiple languages? Store Unicode characters in the trie nodes. Unicode covers every writing system, modern and ancient.

What if top queries differ by country? Build separate tries per country, and serve them from CDNs for speed.

How would you support trending (real-time) queries? The weekly batch can't react to breaking news: the workers aren't scheduled yet, and a full rebuild takes too long anyway. Some ideas:

• Reduce the working set by sharding.
• Change the ranking model to give recent queries more weight.
• Handle streaming data with stream-processing systems such as Hadoop MapReduce, Spark Streaming, Storm, and Kafka. The Derived Data lessons cover these.

---

Key Takeaways

• A request goes out on every keystroke, which gives about 24,000 QPS (48,000 at peak) at 10 M DAU, plus about 0.4 GB of new query data per day.
• Trie + capped prefix length + top k cached per node means O(1) lookups, at the cost of memory.
• Keep gathering (logs → aggregators → workers → Trie DB) separate from serving (API → Trie Cache, with replenish on miss), and rebuild weekly.
• In-place updates must recompute every ancestor, from the children's caches. Deletes go through a filter layer first, then are purged asynchronously.
• Shard by prefix using the historical distribution, not plain letter ranges. AJAX, browser caching (private, max-age), and sampling cut load further.

Previous lesson: Design a Chat System.

Next lesson: Design YouTube — upload and streaming flows, DAG-based transcoding, pre-signed URLs, and long-tail CDN cost savings.

---

Reference Materials

1. The Life of a Typeahead Query — Facebook Engineering
2. How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete
3. Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables
4. MongoDB — Wikipedia
5. Unicode frequently asked questions
6. Apache Hadoop
7. Spark Streaming
8. Apache Storm
9. Apache Kafka