System design: search autocomplete (typeahead)

Key points

• Precompute. Storing the top k completions at every trie node makes a lookup cost proportional to the prefix length, not the number of suggestions.
• Suggestions come from query logs: normalize, count, decay by age, then filter offensive, private and rare queries before anything is served.
• Every prefix is an independent key, so shard by a hash of the prefix, not by first letter, and cache the short, hot prefixes at the edge.
• Typo tolerance means edit distance. Levenshtein automata make a bounded-distance search over a trie or index fast; search engines expose it as fuzziness.
• The client matters as much as the server: debounce, cancel in-flight requests with AbortController, and implement the combobox keyboard pattern.

Requirements and a latency budget

Autocomplete (typeahead) shows a short list of completions while the user types in a search box. It looks small and is one of the most latency-sensitive features in a product, because it runs on almost every keystroke and a slow list is worse than none: it appears after the user has typed past it.

• Latency: a suggestion list must arrive before the next keystroke makes it stale. Set an end-to-end target per request, for example 100 ms at the 99th percentile from request sent to list painted, and give each stage a share of it.
• Relevance: rank by popularity, adjusted for recency and, where it helps, for the user’s own history and locale.
• Freshness: a new product name or a breaking news term should appear without waiting for a full rebuild.
• Typo tolerance: "pyhton" should still suggest "python".
• Safe suggestions: never suggest offensive text, and never surface a rare query that reveals something private about the one person who typed it.
• Scale and availability: read-heavy, many requests per search, and the search box must still work if suggestions fail.

The core data structure: a trie with top-k per node

A trie stores strings as paths of characters from a root; every string that starts with "pyt" sits under the same node. A naive lookup walks to the prefix node and then searches the whole subtree for the best completions, which is slow for a short prefix like "p" that has millions of strings below it. The standard fix is to store, at every node, the k best completions in its subtree. A lookup then walks the prefix and returns a list that is already there.

def build(scores, k=3):
    """Trie where every node keeps the k best completions below it."""
    root = {"next": {}, "top": []}
    for term, score in scores.items():
        node = root
        for ch in term.lower():
            node = node["next"].setdefault(ch, {"next": {}, "top": []})
            node["top"].append((score, term))
            node["top"].sort(key=lambda item: (-item[0], item[1]))
            del node["top"][k:]
    return root

def suggest(root, prefix):
    node = root
    for ch in prefix.lower():
        node = node["next"].get(ch)
        if node is None:
            return []
    return [term for _, term in node["top"]]

trie = build({"python tutorial": 950, "python dict": 880, "pytorch install": 720,
              "python list comprehension": 610, "pycharm": 400, "pandas dataframe": 990})
print(suggest(trie, "py"))    # ['python tutorial', 'python dict', 'pytorch install']
print(suggest(trie, "pyth"))  # ['python tutorial', 'python dict', 'python list comprehension']
print(suggest(trie, "Pa"))    # ['pandas dataframe']
print(suggest(trie, "rust"))  # []

The comments are the real output of running this file. Lookup cost depends on the prefix length, not on how many suggestions exist. The price is memory: every node holds k references, and a term of length n is referenced from n nodes. Common ways to keep that in check:

• Cap the prefix length you index, for example 20 characters; past that, few users are still typing and the list rarely changes.
• Store suggestion ids at the nodes, not the strings, and keep the strings once in a separate table.
• Compress chains of single-child nodes into one edge (a radix tree), or use a finite-state transducer, which shares suffixes as well as prefixes.
• Treat the structure as read-only and rebuild it offline. Updating top-k lists in place is easy when a score rises and awkward when it falls, because the next-best item below a node is no longer known.

Prefix indexes in a search engine

If you already run a search engine, you may not need your own trie. Two index-time approaches are common, shown here with Elasticsearch and OpenSearch as examples.

• Edge n-grams: at index time, an edge_ngram tokenizer stores the leading fragments of each word, so "quick" is indexed as "q", "qu", "qui" and so on, and an ordinary query on the typed text matches them. The Elasticsearch documentation says to use a different analyzer at search time, so the query is not itself split into fragments, and warns that a search term longer than max_gram may match nothing.
• Completion suggester: a dedicated field type whose suggestions carry an input and a weight. The OpenSearch documentation describes it as a finite-state transducer held in memory and optimized for fast prefix lookups. The Elasticsearch documentation notes that the structures are costly to build, that deleted documents are never shown, and that a single shard performs better for completions.

Edge n-grams match the start of any word, so "fox" finds "Quick Fox"; the completion suggester matches from the start of the input, so it fits query suggestions and titles with a well-known order. Many products use both: query suggestions from logs on top, and matching items or pages below.

Building suggestions from query logs

Suggestions should be things people actually search for and that return results. The source is the search log, processed by a batch job that publishes a new index version when it finishes.

1. Collect: log each submitted search with a timestamp, locale and whether it returned results or got a click. Log submitted searches, not every keystroke prefix, or the counts fill with fragments.
2. Normalize: lowercase, trim, collapse whitespace, apply Unicode normalization, and merge trivial variants so "iPhone 15 " and "iphone 15" count together.
3. Aggregate: count per normalized query, and count distinct users or sessions separately from raw searches, so one script or one very persistent user cannot push a query up.
4. Score with decay: weight recent searches more than old ones, so trends rise and fade without a manual reset.
5. Filter: drop offensive terms, personal data and rare queries (rules below).
6. Build and publish: compute top k per prefix, write a versioned snapshot, load it on the serving nodes, then switch traffic to it. Keep the previous version for rollback.

Exponential decay by age
  score(q) = sum over searches s of q:  0.5 ^ (age_in_days(s) / half_life_days)

  With half_life_days = 7, a search counts:
    today          1.0
    7 days ago     0.5
    14 days ago    0.25
    28 days ago    0.0625

  Shorter half-life: reacts faster to trends, noisier.
  Longer half-life: stable, slow to notice new terms.

Filtering deserves as much care as ranking, because a suggestion is something your product says, not just something a user typed. Use a blocklist of offensive terms and their spellings with numbers and symbols, a classifier for what lists miss, and a manual removal path that takes effect at serving time without a rebuild. Drop queries that look like personal data, such as email addresses, phone numbers and long digit strings. Require a minimum number of distinct users before a query can be suggested at all: a query typed by one person, such as a name next to a medical condition, should never be shown to the next.

Freshness comes from a second, small layer. A streaming job counts the last hour or so of searches, and the service merges its top items with the batch list at query time. The batch index carries stable popularity; the streaming layer carries what is new, behind the same filters.

Serving: precomputed lists, sharding and edge caching

Once every prefix has a precomputed list, serving is a key-value lookup: prefix in, ranked list out. That shapes everything else.

• Sharding: each prefix is answered on its own, so you can shard by a hash of the full prefix string. Sharding by first letter, or by ranges of prefixes, is simple but skewed: far more queries start with "s" than with "x". Consistent hashing lets you add nodes without moving most keys. If the whole index fits in one machine’s memory, replicate it instead and skip sharding.
• Caching: one- and two-character prefixes are few and requested constantly, so cache their responses at the CDN or edge with a short time to live (see what a CDN is). Longer prefixes have a long tail and a lower hit rate; an in-process cache on the service covers the warm middle. The trade-offs are the usual ones from caching strategies.
• Personalization: an edge cache can only hold responses that are the same for everyone. Keep the global list cacheable, fetch a small personal list (recent searches, saved items) separately, and merge them on the server or client. If the personal lookup is slow, drop it rather than delay the global list.
• Locale: key the index by language or market, because popular queries differ, and include that key in the cache key.
• Protection: autocomplete endpoints are cheap per request and called constantly, which makes them easy to abuse. Put a rate limiter in front, keyed by client.
• Failure: if the suggestion service is down, the search box must still accept a query and search. Time out quickly and show nothing.

Typo tolerance: edit distance and Levenshtein automata

The usual measure of a typo is Levenshtein distance: the smallest number of single-character insertions, deletions and substitutions that turn one string into another ("pyhton" to "python" is two substitutions; with transpositions counted as one edit, it is one). Comparing the typed prefix against every indexed term is too slow, so engines bound the distance and search the index directly. Schulz and Mihov showed how to build, in time linear in the length of a word W, a deterministic automaton that accepts exactly the words within distance n of W; walking that automaton and a trie or dictionary automaton together visits only the branches that can still match, which gives a very fast correction method for large dictionaries. Search engines expose this as fuzziness. In Elasticsearch, fuzziness: AUTO allows no edits for terms of one or two characters, one edit for three to five, and two for longer terms, and two is the maximum.

• Keep the first character or two exact. Elasticsearch’s completion suggester does this by default with prefix_length of 1, and returns no fuzzy suggestions for inputs shorter than its min_length of 3.
• Rank exact prefix matches above fuzzy ones; the completion suggester scores suggestions that share a longer prefix with the input higher.
• Fuzzy matching on a two-letter prefix matches almost everything. Turn it on only once the prefix is long enough to mean something.

The client: debouncing, cancelling and keyboard access

The client decides how many requests reach the server and whether the user ever sees a stale list. Three habits matter: wait briefly after a keystroke before sending (debounce), cancel the previous request when a new keystroke arrives, and reuse answers you already have.

const cache = new Map<string, string[]>();
export function createAutocomplete(endpoint: string, render: (items: string[]) => void, delayMs = 150) {
  let timer = 0;
  let controller = new AbortController();
  return function onInput(raw: string) {
    const q = raw.trim().toLowerCase();
    window.clearTimeout(timer);
    controller.abort(); // an older, slower response must never overwrite a newer one
    if (q.length < 2) return render([]);
    const hit = cache.get(q);
    if (hit) return render(hit);
    timer = window.setTimeout(async () => {
      controller = new AbortController();
      const { signal } = controller;
      try {
        const res = await fetch(`${endpoint}?q=${encodeURIComponent(q)}`, { signal });
        if (!res.ok) return;
        const items: string[] = await res.json();
        cache.set(q, items);
        if (!signal.aborted) render(items);
      } catch (err) {
        if ((err as Error).name !== 'AbortError') console.warn('suggest failed', err);
      }
    }, delayMs);
  };
}

This sketch type-checks under TypeScript’s strict mode with the DOM library. The debounce delay is an example; tune it against how fast your users type and how fast your service answers. abort() makes the pending fetch reject with an AbortError, which the code ignores on purpose: the DOM standard asks promise-returning APIs to reject with the signal’s abort reason. Without cancellation, responses can arrive out of order and the list for "pyt" can replace the list for "pyth". In a real client, cap the cache size and clear it when the user signs in or out, so personal suggestions do not leak between accounts.

Keyboard and screen-reader access follow the WAI-ARIA Authoring Practices combobox pattern from the W3C:

• The text input has role="combobox", the popup has role="listbox" and each suggestion role="option". The input carries aria-expanded (true while the list is open), aria-controls pointing to the list, and aria-autocomplete="list" when the suggestions match the typed text.
• DOM focus stays on the input while the user moves through the suggestions. aria-activedescendant on the input names the highlighted option, and that option gets aria-selected="true".
• Down Arrow moves into the list, Up Arrow can move to the last item, Enter accepts the highlighted suggestion and closes the list, Escape closes the list and keeps focus on the input, and Alt plus Down Arrow can open the list without moving focus.
• Give the input a visible label. If nothing is highlighted, Enter should submit what the user typed, not the first suggestion.

A capacity estimate, with illustrative numbers

A back-of-the-envelope estimate tells you whether the problem is memory, throughput or neither. Every number below is an assumption chosen to show the method, not a measurement.

Assumptions (illustrative)
  daily active users              10,000,000
  searches per user per day       5
  suggestion requests per search  4   (after debouncing and client reuse)

Throughput
  requests per day     10,000,000 x 5 x 4 = 200,000,000
  average per second   200,000,000 / 86,400 = about 2,300
  peak (3x average)    about 7,000 per second

Memory
  distinct queries kept after filtering      5,000,000
  stored prefixes (max 20 chars, shared)     about 30,000,000
  bytes per prefix entry (key + 10 ids)      about 60
  prefix table    30,000,000 x 60 B  = about 1.8 GB
  query strings    5,000,000 x 30 B  = about 150 MB

Under these assumptions the whole index fits in one server’s memory, so sharding is not forced by size. The design question is throughput and availability: run several replicas behind a load balancer, let the edge cache absorb the short prefixes, and size the replicas for the peak that reaches them. If your numbers come out ten times larger, sharding by prefix hash becomes the natural next step. Redo the estimate with your own traffic before choosing.

BYD Tech builds web apps and their backends, search included: the code lives in the client’s GitHub from day one, the founders are on the calls, and AI-assisted work is reviewed by an engineer.