Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 65 ยท Case Studies: Classic Designs

Design Search Autocomplete

Design typeahead suggestions: requirements, a trie with top-K per node, offline aggregation pipeline, caching, sharding, personalization and filtering, with Python.

When you type "how to" into a search box and a list of likely completions appears, that is autocomplete (also called typeahead). Each keystroke fires a request, so the system must answer in tens of milliseconds, for billions of queries a day, and offer suggestions that are both relevant and safe.

Requirements

  • As the user types a prefix, return the top 5 suggested queries, ranked by popularity.
  • Latency under 100 ms end to end (ideally under 50 ms server time), because it must keep up with typing.
  • Suggestions reflect trending queries within minutes to hours, not months.
  • Support multiple languages; filter offensive or illegal suggestions.
  • Scale: 10 billion searches per day. If a user types about 4 characters that trigger a request, that is up to 40 billion suggestion requests per day, roughly 460,000 per second on average.

Reads dominate heavily. Updates to the ranking can be slow and batched; reads must be instant.

Data structure: a trie with top suggestions per node

A trie stores strings by prefix, one character per edge. All queries starting with "be" live under the path b -> e. A naive trie answers "all words under this prefix", but you would have to walk the whole subtree to find the best five, which is too slow for short prefixes like "a".

The fix is to store the top K suggestions at every node. Then a lookup is: walk down the prefix (as long as the prefix, O(L)), read the cached list. Memory grows, but lookups become O(L).

Python A trie with top-K suggestions at each node

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two paths

flowchart LR
    subgraph online["Online path (fast)"]
        U["User types"] --> GW["Gateway"] --> CACHE[("Cache by prefix")] --> TS["Suggestion service (trie)"]
    end
    subgraph offline["Offline path (batch)"]
        LOGS["Search logs"] --> AGG["Aggregate counts"] --> BUILD["Build tries"] --> STORE[("Trie snapshots")]
    end
    STORE --> TS

Reads use a prebuilt, read-only structure; a separate pipeline rebuilds it from logs.

Do not update the trie on every search. Updating nodes under heavy load causes contention, and a single search barely changes the ranking. Instead:

  1. Log every completed search.
  2. Aggregate counts per query in a batch or stream job (hourly, plus a faster path for trending terms with a decay so old counts fade).
  3. Build a new trie (or a sorted index), write it to storage, and have the suggestion servers load it and swap atomically.
Python Aggregating logs into counts with time decay

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Latency tricks

  • Cache by prefix. The prefix "wea" gets asked millions of times; store its response in a CDN or in-memory cache with a short TTL.
  • Debounce in the client. Wait 100 to 150 ms after the last keystroke before sending, and cancel in-flight requests.
  • Prefetch. Return suggestions for the next likely characters, or cache the first few characters on the device.
  • Limit work. Cap prefix length (after about 50 characters stop suggesting) and ignore the first character in low-value cases if load is very high.

Scaling the trie

A trie for billions of queries will not fit on one machine. Options:

  • Shard by first one or two letters, but "s" is far more popular than "x", so shard by measured traffic or hash ranges of prefixes and rebalance.
  • Replicate each shard for throughput and availability; reads are almost fully static, so replicas stay simple.
  • Trim the data: keep only queries above a minimum count, and store at most K entries per node.

Personalization, safety and relevance

  • Blend global popularity with the user's own history, language and location. Compute the base list from the trie, then re-rank a few dozen candidates with user signals.
  • Filter with a blocklist and classifiers at build time, so harmful completions never enter a trie, and keep a fast removal path for emergencies.
  • Handle typos by a fuzzy matching layer (edit distance or phonetic keys) as a fallback when the prefix matches nothing.
  • Track success: how often a suggestion is clicked, and the time saved per search.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why store the top K suggestions at each trie node?

    Precomputed top-K lists turn the lookup into O(length of prefix).
  2. 2. Why not update the trie on every individual search?

    Aggregate in batches, rebuild, and swap the new snapshot in.
  3. 3. What does client-side debouncing do?

    It reduces request volume by skipping requests for characters typed in quick succession.
  4. 4. Why is sharding by first letter alone a weak choice?

    Popular starting letters create hot shards; use traffic-aware ranges instead.

Summary

  • Autocomplete is a read-heavy, latency-critical lookup on prefixes.
  • A trie with top-K lists per node answers a prefix in O(L).
  • Build the data offline from aggregated logs (with decay for trends) and swap snapshots in.
  • Cache by prefix, debounce on the client, shard by traffic and replicate.
  • Filter harmful suggestions at build time and personalize with a light re-rank.

Next: Design a Web Crawler