Autocomplete / Typeahead Architecture, in depth: top-k tries, decayed popularity, trending deltas and the per-keystroke latency budget

What typeahead has to do

Given a prefix such as new y, return the handful of complete queries most likely to be what the user means, for example new york weather and new year holidays, in ranked order. Four properties define the problem.

• Latency. A comfortable target is that suggestions appear within about 100 ms of a keystroke, end to end. Network round trips take a large part of that, which leaves the server a budget of tens of milliseconds at the tail, not the median.
• Volume. Requests scale with keystrokes, not searches. A user who types an eight-character query can produce several requests even after debouncing.
• Ranking. The order matters more than the set. Users mostly pick from the first few rows, so ranking is the product.
• Safety and freshness. Suggestions must not surface abusive, illegal or personally identifying text, and must reflect new events within minutes when something suddenly trends.

A worked sizing estimate

Numbers depend on the product, so treat these as assumptions you replace with your own. Suppose 20 million daily users, 5 searches each, and an average of 4 suggestion requests per search after debouncing. That is 400 million requests a day, about 4,600 per second on average; with a peak-to-average ratio of 3, plan for roughly 14,000 per second.

For the index, suppose you keep the 50 million most popular distinct queries, averaging 25 bytes. The raw strings are about 1.25 GB; trie nodes and cached top-10 lists multiply that to a few gigabytes or low tens of gigabytes per copy, depending on encoding. That still fits in one server's memory, which drives the most important architectural choice below: replicate the whole index rather than sharding it, if you can.

The architecture: two paths that never block each other

The serving path is client, edge cache, a stateless suggest service, and in-memory indexes. It reads only precomputed data. The build path aggregates query logs, scores and filters phrases, builds an index snapshot, and publishes it with a version number. Serving nodes load the new snapshot alongside the old one and swap atomically. Because the serving path never reads logs or databases, a slow or broken build makes suggestions staler, but never slower.

The build runs daily or hourly, too slow for breaking events, so a third, small trending path counts recent queries in a streaming job over a sliding window and maintains a delta index of phrases whose recent rate is far above their baseline. The suggest service merges the base snapshot, the trending delta and per-user history at request time.

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

A trie stores strings by their characters: each edge is a character, and the path from the root to a node spells a prefix. Finding the node for a prefix takes time proportional to the prefix length, which is tiny. The expensive part in a plain trie is what comes next: collecting every completion beneath the node and sorting them. For a one-letter prefix that subtree holds millions of phrases.

The fix is to precompute. At build time, every node stores the K best completions in its subtree. A request becomes: walk down the prefix, return the stored list. That is constant work per request regardless of how many phrases share the prefix, which is exactly the property a per-keystroke service needs.

import heapq

class Node:
    __slots__ = ("children", "top")
    def __init__(self):
        self.children = {}   # char -> Node
        self.top = []        # up to K (score, phrase), best first

K = 10

def build(phrases):
    """phrases: iterable of (phrase, score). Returns the root of a trie whose
    every node caches the K best completions beneath it."""
    root = Node()
    for phrase, score in phrases:
        node = root
        for ch in phrase:
            node = node.children.setdefault(ch, Node())
        node.top = [(score, phrase)]          # terminal entry for the phrase itself
    _fill(root)
    return root

def _fill(node):
    # post-order: a node's top-K is the best K across its own entry and its children's lists
    candidates = list(node.top)
    for child in node.children.values():
        _fill(child)
        candidates.extend(child.top)
    node.top = heapq.nlargest(K, candidates)

def suggest(root, prefix, k=K):
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return []
    return [phrase for _, phrase in node.top[:k]]

The cost is memory and build time: a phrase appears in the top-K list of every ancestor where it ranks highly. Production systems store phrase identifiers instead of strings, collapse single-child chains (a radix tree), or use a sorted phrase array with binary search plus precomputed top-K tables for short prefixes. Lucene-based engines use finite state transducers, which share both prefixes and suffixes and can carry weights. All of these are encodings of the same idea: make the hot read path a lookup, not a search.

Scoring: what makes a suggestion good

The simplest score is how often a query was searched. Raw counts have two problems: they never forget, so last year's news outranks today's, and they reward queries people typed even when the results were useless. A better base score combines several signals with time decay.

import math, time

HALF_LIFE_DAYS = 7.0
LAMBDA = math.log(2) / HALF_LIFE_DAYS

def decayed(counts_by_day, today):
    """counts_by_day: {day_index: accepted_count}. Older days count less."""
    return sum(c * math.exp(-LAMBDA * (today - d)) for d, c in counts_by_day.items())

def score(phrase_stats, today):
    s = decayed(phrase_stats["accepted"], today)          # users picked it from the list
    s += 0.3 * decayed(phrase_stats["typed_full"], today) # users typed it and searched
    if phrase_stats["result_count"] == 0:
        s *= 0.1                                          # suggestions that lead nowhere
    return s

With a seven-day half-life, a phrase must keep being searched to keep its place. Accepted suggestions, where a user picked a row, are a stronger signal than typed queries because they measure what typeahead itself should produce. Queries that return no results are demoted. Curated entities such as new products can be added with a prior so they appear before anyone has searched for them.

Merging at request time

The suggest service is stateless. For each request it pulls a few times K candidates from each source, because filtering removes some and a boost can promote a phrase from eleventh to first, then merges and truncates.

def serve(prefix, user, k=8):
    base = base_index.suggest(prefix, k * 3)          # (phrase, score) from the snapshot
    delta = trending.suggest(prefix, k * 3)           # recent spikes, same scale
    personal = history.recent(user, prefix, limit=3)  # phrases this user searched before

    scores = {}
    for phrase, s in base:
        scores[phrase] = s
    for phrase, s in delta:
        scores[phrase] = max(scores.get(phrase, 0.0), s * TREND_WEIGHT)
    for phrase in personal:
        scores[phrase] = scores.get(phrase, 0.0) + PERSONAL_BOOST

    ranked = sorted(scores.items(), key=lambda kv: -kv[1])
    out = [p for p, _ in ranked if not blocked(p)]
    return dedupe_near_duplicates(out)[:k]

Keep the merge cheap and bounded: fixed candidate counts, no remote calls except to in-process or same-host structures, and a hard deadline. If the personal-history store does not answer within a few milliseconds, serve without it.

Replication, sharding and hot prefixes

If one copy of the index fits in memory, replicate it to every serving node and put a load balancer in front. Every node can answer every prefix, there is no fan-out, and capacity scales by adding nodes. This is the simplest design and usually the right one.

When the index outgrows one machine, typically because of many languages or markets, shard by market or language first, since those boundaries are natural and a request only needs one shard. Sharding by prefix range (a to f, g to m) also works because a request touches exactly one shard, but traffic is badly skewed: short prefixes and common letters are far hotter than others. Range boundaries should be chosen from traffic, not from the alphabet. Avoid hashing whole phrases across shards, because then a prefix request must fan out to all of them and merge, which multiplies tail latency.

The hottest prefixes are the shortest ones. There are only a few thousand one- and two-character prefixes per language, and they receive a large share of requests. Cache them in front of the service, in a CDN or edge cache, keyed by prefix and market with a time to live of a minute or so. That absorbs a large fraction of load with almost no staleness cost. Personalised results cannot be shared at the edge, so let the client blend in local history. Hot-key mitigation covers the general technique, and the caching article covers TTL and invalidation trade-offs.

The client is half the system

Most typeahead load and many of its bugs come from the client. Four rules matter.

1. Debounce. Wait a short pause, often 50 to 150 ms, after the last keystroke before sending, so fast typists do not send a request per character.
2. Cancel. Abort the previous request when a new one starts. This frees connections and server work.
3. Ignore stale responses. Responses can arrive out of order. Tag requests with a sequence number and paint only the newest, or the list will flicker back to suggestions for an older prefix.
4. Reuse locally. Cache responses by prefix. When the user deletes a character, the previous list is already there.

let seq = 0, inflight = null;
const cache = new Map();                 // prefix -> suggestions

input.addEventListener("input", debounce(async () => {
  const q = input.value.trim().toLowerCase();
  if (q.length === 0) return render([]);
  if (cache.has(q)) return render(cache.get(q));

  const mySeq = ++seq;
  inflight?.abort();                     // cancel the previous request on the wire
  inflight = new AbortController();
  try {
    const r = await fetch(`/suggest?q=${encodeURIComponent(q)}`, { signal: inflight.signal });
    const items = await r.json();
    cache.set(q, items);
    if (mySeq === seq) render(items);    // never paint a response older than the newest request
  } catch (e) {
    if (e.name !== "AbortError") render(cache.get(q.slice(0, -1)) ?? []);
  }
}, 80));

The client must also log which suggestion was accepted at which position; without that signal you cannot measure or improve ranking.

Freshness, safety and typos

Trending. The streaming job compares each phrase's count in a short window with its long-run baseline and emits phrases whose ratio crosses a threshold, with a minimum absolute count so that a phrase going from one search to five does not trend. The delta index is small and can be rebuilt every minute.

Filtering. Apply a blocklist and policy classifiers in the build path, and apply the blocklist again at serving time so an urgent removal takes effect in seconds without a rebuild. Trending phrases deserve stricter rules. Never suggest phrases that appear to contain personal data such as email addresses or phone numbers, and require a minimum number of distinct users before a phrase can be suggested at all, so one person cannot inject a suggestion by repetition.

Typos. Prefix lookup fails on nwe york. A misspelling table or an edit-distance-one fallback helps, but fuzzy matching multiplies work per request, so use it only when the exact prefix returns too little.

Failure modes

Operating it

Measure latency at the server and in the client at p99 and p99.9. Alert on snapshot age and trending-delta age, since staleness is the failure the serving path hides. For quality, track acceptance rate, accepted position, keystrokes saved and empty-result prefixes. Keep the last few snapshots for rollback by version pointer, and if a build fails, keep serving the previous one.

The main trade-offs are memory against latency, freshness against safety, and personalisation against cacheability; decide each explicitly. For the main results page behind the box, see Search System Architecture.

What to do next

1. Write down your latency budget per keystroke and subtract measured network time to get the server budget at p99.
2. Estimate request rate from keystrokes, not searches, and estimate one index copy's size; if it fits in memory, plan to replicate rather than shard.
3. Prototype the top-k trie above on a day of your own query logs and measure memory and lookup time.
4. Add acceptance logging in the client, then build a decayed score from accepted and typed queries.
5. Implement debounce, cancellation and sequence-number checks in the client before load testing the server.
6. Add a serve-time blocklist, a distinct-user threshold and alerts on snapshot age before launch.