Skip to content

02. Search Autocomplete — Low-Level Design

~20 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)

The HLD named the boxes. This file opens the three that carry the design's weight — the prefix trie with precomputed top-k, the ranking and top-k propagation that fills it, and the serve-time merge with the trending layer — and pins down the data, the algorithms, and the concurrency corners where a typeahead system actually breaks.

Data models

The base index is a trie whose every node stores the precomputed top-k completions of the prefix that reaches it. In memory it is a node structure; the fields below are what each node holds.

TrieNode {
    children   : map<char, TrieNode*>   # or a compact edge array
    top_k      : [ (query_id: u32, score: u32) ] × k   # precomputed, sorted desc
    is_terminal: bool                    # true if this prefix is itself a full query
}

# String dictionary, separate from the trie to keep nodes small:
QueryDict {
    query_id (u32)  →  text (string)     # 100M entries, ~2 GB
}

Two deliberate choices. First, top-k is stored on every node, not just leaves — that is what makes a lookup a single node read instead of a subtree traversal at request time; it is the precompute that buys the latency. Second, suggestions are stored as query_id references, not inline strings, so a node holds 10 × 8 = 80 bytes of pairs rather than ten full strings; the text is resolved once at the end from the dictionary. That keeps the ~300M-node trie near 39 GB instead of several times larger.

The batch job's input is an aggregated frequency table, not raw events:

CREATE TABLE query_frequency (
    query_id     BIGINT PRIMARY KEY,
    text         TEXT    NOT NULL,
    frequency    BIGINT  NOT NULL,   -- aggregated count over the log window
    lang         CHAR(2) NOT NULL,
    region       CHAR(2) NOT NULL,
    last_seen    TIMESTAMP NOT NULL
);

The trending layer keeps only ephemeral window state, never a durable table:

WindowCounts {
    (query_id) → count      # counts over the trailing ~10 min, in stream state
}
TrendingTopK {
    (prefix)   → [ (query_id, surge_score) ]   # derived, refreshed every ~10 s
}

Component internals

Component 1 — The prefix trie (lookup and structure)

Responsibility: given a prefix, return its precomputed base top-k in a single walk, at single-digit milliseconds.

class TrieShard:
    def lookup(prefix: str) -> list[(query_id, score)]   # walk + read node.top_k
    def owns(prefix: str) -> bool                         # routing check
    def swap_index(new_root: TrieNode) -> None            # atomic version swap

def lookup(self, prefix):
    node = self.root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return []            # no completions: return empty, never error
    return node.top_k            # already sorted, already trimmed to k

The lookup does no ranking and no sorting — both were done offline. The walk is O(len(prefix)) character steps (≤ ~30 for any real prefix) plus one array read, which is why even a cold cache miss resolves in a few milliseconds. A missing edge means no query starts with this prefix; returning an empty list rather than an error keeps the client's dropdown simply closing.

Compression matters for the memory budget. A plain trie has one node per character; a radix (compressed) trie or FST collapses non-branching chains — the run n-e-w-s under a single-child path becomes one edge labeled "ews" — cutting node count and, with an FST, sharing suffixes too. This is the concrete mechanism behind the memory-vs-latency tradeoff: compression is what lets the index stay in RAM.

Component 2 — Top-k propagation (the batch ranking build)

Responsibility: turn the flat query_frequency table into a trie where every node's top_k is the k most frequent queries that pass through it.

The build is bottom-up. Insert every query as a leaf carrying its frequency, then propagate top-k from children to parents so each node's list is the merge of its children's lists trimmed to k.

def build(queries: list[(text, frequency, query_id)]) -> TrieNode:
    root = TrieNode()
    for (text, freq, qid) in queries:
        insert_leaf(root, text, qid, freq)   # mark terminal, set leaf score
    propagate_topk(root)                      # post-order DFS
    return root

def propagate_topk(node) -> list[(query_id, score)]:
    # Collect this node's own terminal entry (if any) plus children's top_k.
    candidates = []
    if node.is_terminal:
        candidates.append((node.query_id, node.score))
    for child in node.children.values():
        candidates.extend(propagate_topk(child))   # child already trimmed to k
    node.top_k = heap_nlargest(k, candidates, key=score)  # keep top k by score
    return node.top_k

Because each child returns at most k entries, a node with c children merges at most c·k + 1 candidates and keeps k. The work is linear in the number of nodes times a small k, so a full build over 100M queries is bounded and finishes in the ~1-hour window the freshness floor assumes. Ranking here is popularity = aggregated frequency, optionally time-decayed (score = frequency × 0.5^(age_days / halflife)) so a query popular last year does not outrank one popular this month.

Responsibility: combine the stable base top-k with real-time surges and an optional per-user re-rank, cheaply, per request.

def suggest(prefix, user_ctx) -> list[str]:
    base     = cache.get(prefix) or shard.lookup(prefix)   # ~10 (query_id, score)
    trending = trending_layer.top_for(prefix)              # ~few surging candidates
    merged   = blend(base, trending)     # union by query_id, blended score
    if user_ctx:
        merged = rerank_by_history(merged, user_ctx.recent)  # reorder ≤20 items
    return [ query_dict[qid] for (qid, _) in merged[:k] ]

def blend(base, trending):
    by_id = { qid: score for (qid, score) in base }
    for (qid, surge) in trending:
        by_id[qid] = by_id.get(qid, 0) + surge   # additive boost
    return sorted(by_id.items(), key=score, reverse=True)

The merge operates on ~10–20 candidates, so it costs microseconds, not a re-search. Crucially, personalization re-ranks this tiny set and is never cached under the user — the shared base is what gets written to the prefix cache, preserving the 95% hit ratio. This is the re-ranking-not-re-indexing resolution made literal.

Walk the threaded scenario through the freshness path. A news event breaks at 14:00; users start typing and submitting a query whose completion did not previously rank in the top-10 for the prefix el (say "election results live"). Track how it appears within minutes without a trie rebuild.

  1. 14:00:00 — spike begins. Submitted searches for "election results live" jump from a background trickle to thousands per minute. Each submission is a query_event on the bus.
  2. 14:00–14:02 — the trending layer counts. The Flink job increments this query's count in the trailing 10-minute window. Within ~2 minutes its window count has crossed the surge threshold (e.g. rate-of-change over baseline), and TrendingTopK["el"] now includes (election_results_live, surge_score), refreshed every ~10 s.
  3. 14:02 — serve-time merge picks it up. A user types el. The suggest service reads base = shard.lookup("el") — the top-10 from the last trie build at, say, 12:00, which does not contain the new term. It reads trending.top_for("el"), which now does. blend() adds the surge score, and the term jumps into the merged top-10.
  4. Cache freshness bounds the lag. The only thing between the trending layer and the user is the prefix cache's TTL. With a 30-second TTL on el's cached entry, the freshly merged list replaces the stale one within 30 s of the trending layer flagging it. Total time from spike to visible: ~2 min of counting + ≤30 s of cache TTL ≈ under 3 minutes — inside the "within minutes" requirement.
  5. ~16:00 — the base absorbs it. The next batch build reads the accumulated frequency, bakes "election results live" into top_k["el"] permanently, and the trending layer's additive boost decays. The term now ranks from the base index alone, and if the story fades its frequency (with time-decay) drops it back out on a later build.

The number that makes this work is the split of responsibilities: the base trie owns the 99.9% of prefixes whose rankings are stable for hours, and the trending layer owns only the small, fast-moving tail — so the expensive rebuild runs on a slow cadence while freshness rides a cheap merge.

Client        Suggest svc     Prefix cache    Trie shard      Trending layer
  │  GET ?q=el     │                │              │                 │
  ├───────────────▶│  get("el")     │              │                 │
  │                ├───────────────▶│  (miss)      │                 │
  │                ├─ lookup("el") ─┼─────────────▶│  walk e→l       │
  │                │◀──────────────┼──────────────┤  base top_k     │
  │                ├─ top_for("el") ┼──────────────┼────────────────▶│
  │                │◀───────────────┼──────────────┼─────────────────┤ surges
  │                ├─ blend + rerank (≤20 items, in-process)         │
  │                ├─ set("el", base_list, ttl=30s) ─▶│              │
  │◀── top-10 ─────┤                │              │                 │

The base list — not the personalized one — is what is written back to the cache, so the next user's el request is a hit and the shared answer stays reusable.

Concurrency and edge cases

  • Atomic index swap. A rebuild must never expose a half-built trie. The build job constructs the new root fully off to the side, then swap_index flips a single pointer under the shard's read lock (or a lock-free atomic pointer swap). In-flight lookups finish against the old root; new lookups see the new one. No lookup ever walks a partially wired tree.
  • Cache stampede on swap. As covered in the HLD, an index swap can invalidate many cached entries at once, and at 100k QPS the resulting simultaneous misses can jump shard load 20×. Guard it with single-flight coalescing keyed on prefix — the first miss for a prefix walks the shard while the rest wait for its result — plus staggered swaps across replicas so the cache warms in waves rather than all at once.
  • Trending / base double-count. After a base rebuild bakes a term in, the trending layer may still be boosting it, briefly over-ranking it. Handled by having the trending boost decay on its own window and by capping the additive surge, so the worst case is a popular term sitting one slot too high for a few minutes — cosmetic, not incorrect.
  • Stale-but-consistent reads. A lookup that races a swap may return the pre-swap top-k; that is acceptable, because suggestions are advisory and the two versions differ only in ranking, never in correctness. There is no read-your-writes hazard: a user does not expect their just-submitted query to instantly rank.
  • Debounce and cancellation. The client fires a request only after a ~100 ms typing pause and cancels in-flight requests when a newer keystroke arrives, so el → ele does not leave two responses racing to fill the box. The server treats each request independently; there is no server-side session state to corrupt.
  • Empty and pathological prefixes. A prefix with no completions returns [] (closing the dropdown), never an error. A very long or high-cardinality prefix still costs only O(len) steps, so a user pasting a 500-character string does one bounded walk that dead-ends quickly rather than triggering any scan.
  • Poisoned-term races. A blocklist is applied both at build time (the term never enters top_k) and at serve time (a final filter over the merged list), so a term added to the blocklist between builds is suppressed immediately at serve time even though it still sits in the base trie until the next rebuild.