Design Typeahead / Autocomplete: Ranked Tries and Precomputed Top-K

Build the suggestion service behind a search box: as a user types a prefix, return the top few completions ranked by popularity. Typing car should show car rental, cardigan, cards (the most-searched continuations), not random matches. K is the list size (usually 5–10); top-K means the K highest-ranked completions of a prefix.

In scope: top-K completions of a prefix, ranking by popularity, and ingesting the search and click signals popularity comes from. Out of scope: the results page, the search engine itself, spell correction and per-user personalization (the last two return as variants).

Clarifying questions

What makes this problem distinctive

A normal endpoint can do work per request. Typeahead can't: a suggestion is only useful before the next character, one user fires a burst of requests while typing one word, and the answer must be the few most popular completions from a corpus far too big to scan and sort on demand. The naive approach (find every match, sort, return the top few) does work that grows with the corpus while the per-keystroke budget stays fixed. The fix is to move ranking off the request path: popularity changes slowly but is read constantly, so precompute the ranked answer for every prefix, keep it in memory, and make each keystroke a lookup. Rank when data changes, not when it is read. See pre-computing.

Key concepts

The trie

A trie (prefix tree) has one character per edge, and each node represents the prefix spelled from the root. Queries sharing a prefix share its path: to complete car, walk root → c → a → r (three steps) and everything below is a completion. The walk costs one step per prefix character, independent of how many queries the trie holds.

Precomputed top-K per node

The subtree under a short prefix can hold millions of queries, so each node also stores its top-K completions, already sorted. A lookup walks to the prefix node and returns that list: no subtree scan, no sort.

Key idea: autocomplete is a prefix index with the ranking already done. Precompute top-K for every prefix offline, hold it in memory, and each keystroke is a cache hit rather than a computation.

1. Requirements

• Suggest: given a prefix, return its top-K completions (default K = 10) ranked by popularity.
• Rank by popularity: ordering reflects how often each completion is searched, refreshed over time to track demand.
• Ingest signals: take in search and click events that popularity is computed from. Log completed searches and clicks, not every keystroke, which is noisy.

• Latency: near-instant p99 per keystroke (about 100 ms end to end at most, or it feels laggy), the headline constraint.
• Read-heavy: suggestions vastly outnumber changes: build offline, serve from memory.
• Availability: degrade gracefully; slightly stale or fewer results beat an error. A blank suggestion box is fine; a failed page is not.
• Scalability: grows linearly by adding prefix shards and serving replicas.

The binding constraint is the per-keystroke latency budget, which rules out per-request ranking or disk access. The non-negotiable property is ranked relevance: any completion is easy, the most popular ones are the point. Precomputing the ranking satisfies both.

2. Back-of-the-envelope

• Query volume: ~100K searches/s at peak; each search fires several suggest calls even after the client trims duplicates, so ~500K suggest requests/s for the serving tier and caches.
• Corpus and memory: ~100M distinct popular queries averaging ~20 characters; a trie with a small top-K per node lands at a few to tens of GB: large but RAM-resident, sharded if one machine can't hold it. Radix compression shrinks it further. Conclusion: the hot path never touches disk.
• Build cost: aggregating billions of daily events into scores is a scheduled batch or streaming job: heavy, but off the serving path.

State the arithmetic: if users type 6 characters per search and debouncing halves requests, 10,000 searches/s become about 30,000 suggest requests/s, and a hot-prefix cache absorbs a large share of those. See measuring load.

3. API

Design checkpoint: should ranking happen inside suggest on each request, or before it in an offline build? Before it. The API shape encodes the inversion: suggest only reads, logEvent only writes, on entirely separate paths.

4. Data model

Many events roll up into one score; many scores fill one node's top-K. The event stream and the heavy build sit on the other side of a boundary from the keystroke path, so they never contend.

5. High-level design, one fix at a time

Naive: on each keystroke, query a database with a prefix match and ORDER BY popularity. It fails the budget immediately: a prefix match plus a sort, per keystroke, over a growing table on disk.

1. Precompute the ranked answer in memory: aggregate popularity offline, build a trie whose nodes hold sorted top-K, keep it in RAM. A keystroke walks to the node and returns the list.
2. Shard the trie by prefix: when the corpus outgrows one machine, split by leading characters and route each request to the one shard owning that subtree; a lookup still touches exactly one shard. See sharding and consistent hashing.
3. Cache hot prefixes and debounce the client: short prefixes like a or th are hugely popular with stable answers, so a cache (and the CDN/browser, since responses are cacheable per prefix) answers them without a walk. The client waits tens of milliseconds after the last keystroke (~100–200 ms pauses are typical) and cancels superseded requests, so typing car sends about one request instead of three.
4. Build the index offline: events flow through a pub/sub log into an aggregation job that computes popularity, builds a fresh ranked trie and loads it onto the serving tier on a schedule.

Every component defends the latency budget: the trie removes the sort, memory removes the disk, sharding removes the size ceiling, the cache removes repeat walks, and the offline pipeline removes the build from the request path.

6. Deep dives

Building the ranked trie

A prefix like c may have millions of completions; how do you compute its top-K without scanning them all? First aggregate the log into a score per query with time decay, so old fads fade: with a factor of 0.5 per day, 1,000 searches today count 1,000 but 1,000 searches three days ago count 1,000 × 0.5³ ≈ 125. A query that spiked last week sinks below one rising today, even with a bigger all-time total.

Then build top-K bottom-up from children's top-K, never from whole subtrees: each child already holds a sorted list of K; a parent takes the union of its children's lists plus any query ending exactly at the parent, sorts, and keeps K. Merging a handful of short lists is cheap, and one leaves-first pass fills every node. For car with K = 3, children card, care and cart hand up their lists and the parent keeps the best three.

import heapq

K = 3

class Node:
    __slots__ = ("children", "score", "top_k")
    def __init__(self):
        self.children, self.score, self.top_k = {}, None, []   # score set if a query ends here

def decayed_score(daily_counts: list[int], decay: float = 0.5) -> float:
    """daily_counts[0] is today; 1,000 searches 3 days ago count as 1,000 * 0.5**3 = 125."""
    return sum(c * decay ** age for age, c in enumerate(daily_counts))

def build(popularity: dict[str, float]) -> Node:
    root = Node()
    for query, score in popularity.items():            # 1. insert every query
        node = root
        for ch in query:
            node = node.children.setdefault(ch, Node())
        node.score = score

    def fill(node: Node, prefix: str) -> list[tuple[float, str]]:   # 2. bottom-up top-K
        candidates = [(node.score, prefix)] if node.score is not None else []
        for ch, child in node.children.items():
            candidates += fill(child, prefix + ch)       # each child returns only K items
        node.top_k = heapq.nlargest(K, candidates)
        return node.top_k
    fill(root, "")
    return root

def suggest(root: Node, prefix: str) -> list[str]:      # hot path: walk + read, no ranking
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return []
    return [q for _, q in node.top_k]

popularity = {"car rental": 9.1e6, "cardigan": 4.3e6, "cards": 2.0e6,
              "carpet": 1.1e6, "cat food": 3.0e6, "care bears": decayed_score([1000, 0, 0, 1000])}
trie = build(popularity)
print(suggest(trie, "car"))     # ['car rental', 'cardigan', 'cards']
print(suggest(trie, "ca"))      # ['car rental', 'cardigan', 'cat food']
print(decayed_score([0, 0, 0, 1000]))   # 125.0

Two production refinements:

• Radix compression: most trie nodes have one child (the unique tail of a word), each costing memory and a pointer hop. Collapse single-child chains into one edge labeled with the whole substring: cardigan/cardigans becomes one cardigan edge plus a branch for s, instead of eight chained nodes. Lookups match against edge labels (finding card stops partway along the cardigan edge). Real tails are mostly unique, so this removes most nodes. Lucene's suggesters use a related compressed structure, finite state transducers.
• Atomic swap: readers reach the trie through one pointer. The builder constructs the next version off to the side as an immutable structure, then flips the pointer: in-flight reads finish on version A, new reads use version B. Nothing mutates a live structure, so no read ever takes a lock or sees a half-built trie.

Serving within the latency budget

With the trie in RAM and immutable between builds, a read is a lock-free pointer walk: no disk, no database, no contention. What's left is volume and skew:

• Debounce and cancellation first: the cheapest fix (no server work) and the biggest traffic cut.
• Hot-prefix cache: a few short prefixes take a large share of traffic; serve them without a walk.
• Skew-aware sharding: traffic is uneven across the alphabet, so split busy ranges like s* and t* across more shards than rare ones like z*. The router keeps a boundary table (s-a…s-m on one shard, s-n…s-z on another, all of z* sharing one), so no shard becomes a hot spot. See hot partitions.
• Degrade, don't error: serving replicas are read-only copies of an immutable index, so a dead replica's traffic moves to others; a failed build keeps the last good trie (stale, not unavailable); if a shard is briefly unreachable, return what you have: a shorter list is acceptable, an error isn't. See graceful degradation.

Freshness and trending

Precomputed top-K is stale by up to one rebuild cycle: a term that started trending an hour ago won't appear until the next build. Usually fine, but state it. When near-real-time trending matters, don't rebuild on every event. Keep a small, fast-updating structure of recently popular queries over a short window (fed by the same stream, e.g. counted in a streaming job) and blend at query time: union the precomputed top-K with the real-time list for the prefix, dedupe, give real-time entries a recency boost, re-sort and keep K. It's a cheap merge of two short lists.

7. Variants

• Personalization: keep the shared trie and add a thin per-user re-rank, or blend per-user and per-segment signals at query time. Per-user tries don't scale.
• Fuzzy / typo tolerance: allow a bounded number of edits during the walk, or add an n-gram index, at higher compute cost; a deliberate add-on, not the base case. Search engines offer this built in (see full-text search).
• 10× scale: more read-only replicas (the trie replicates freely), finer prefix sharding for skew, tiered caching of hot prefixes; the build pipeline scales independently.

The transferable pattern and a 30-second answer

Typeahead is precompute-and-cache taken to the limit: anticipate the reads, precompute ranked answers, serve them from memory, refresh asynchronously. The same shape fits materialized feeds, leaderboards, recommendation candidate sets and any latency-critical lookup over a slowly changing corpus.

1. Store completions in a trie and cache each node's top-K, sorted by popularity.
2. A keystroke walks to the prefix node and returns its list; no ranking at request time.
3. Build the trie offline from query and click logs and swap in each new immutable version.
4. Serve from RAM; debounce on the client and cache hot prefixes to hold the latency budget.
5. Shard by prefix when the trie outgrows one machine, splitting busy ranges more finely.
6. Accept rebuild-cycle staleness, and patch in surging terms with a small real-time layer.