Back to Notes

Design Typeahead / Search Autocomplete

1. Problem & Real-World Context

Design the suggestion dropdown that appears as a user types into a search box (Google-style): given a prefix, return the top-K most likely completions, fast enough to update on every keystroke. The defining tension: the naturally correct data structure (a trie) makes prefix lookup trivial, but naive top-K-per-query requires a DFS over every completion under that prefix — at real QPS, this DFS-per-keystroke cost is the actual problem to solve, not prefix matching itself.

2. Requirements

Functional: given a prefix, return the top-K (typically 5–10) most popular completions, ranked by historical query frequency; update rankings as new queries come in (not necessarily instantly).

Non-functional: latency budget is brutal — this fires on every keystroke, so p99 needs to be well under 100ms, ideally under 20-50ms, or the UI visibly lags. Eventual consistency is fine for ranking freshness (a trending query doesn't need to appear in suggestions within milliseconds of first occurring).

3. Capacity Estimation

  • If this serves a search engine with, say, 100K queries/sec, and each query is typed character-by-character (a query of length 10 fires ~10 autocomplete requests as the user types) → ~1M autocomplete requests/sec is the real load the system serves, an order of magnitude above the underlying search QPS itself. This is the number that justifies aggressive caching (§6) rather than computing rankings live per request.
  • Trie size: with ~10M distinct historical queries, average length ~20 characters, a naive trie (one node per character) could reach hundreds of millions of nodes — memory becomes a real constraint, motivating the compressed/cached-top-K approach in §5 rather than a plain trie.

4. API Design

GET /v1/autocomplete?prefix=syst&limit=5
→ { "suggestions": ["system design", "systemd", "system32", "systematic review", "system administrator"] }

Read-only, no auth complexity, cacheable at the edge for popular prefixes — a genuinely simple API surface, which is why the system behind it (not the endpoint) is where the interview complexity lives.

5. The Core Data Structure: Trie with Cached Top-K per Node

A trie (prefix tree) makes "does this prefix exist, and where" an O(prefix length) walk — but naively finding the top-K completions under a node still requires a DFS over its entire subtree at query time, which is far too slow at the QPS in §3.

The fix: pre-compute and cache the top-K completions at every node, during trie construction (offline/batch), not at query time.

flowchart TD
    Root --> S["s<br/>top-K cached: [system design, systemd, ...]"]
    S --> SY["sy<br/>top-K cached: [system design, systemd, ...]"]
    SY --> SYS["sys<br/>top-K cached: [system design, systemd, ...]"]

Every prefix node already knows its own top-K answer — a query-time lookup becomes "walk to the node for this prefix (O(prefix length)), return its cached list (O(K))," with zero DFS at request time.

from dataclasses import dataclass, field

@dataclass
class TrieNode:
    children: dict[str, "TrieNode"] = field(default_factory=dict)
    top_k: list[tuple[str, int]] = field(default_factory=list)   # (query, frequency), pre-sorted

class Trie:
    def __init__(self, k: int = 5):
        self.root = TrieNode()
        self.k = k

    def insert(self, query: str, frequency: int) -> None:
        node = self.root
        self._update_top_k(node, query, frequency)
        for ch in query:
            node = node.children.setdefault(ch, TrieNode())
            self._update_top_k(node, query, frequency)

    def _update_top_k(self, node: TrieNode, query: str, frequency: int) -> None:
        node.top_k = [(q, f) for q, f in node.top_k if q != query]
        node.top_k.append((query, frequency))
        node.top_k.sort(key=lambda x: -x[1])
        node.top_k = node.top_k[: self.k]        # keep only top K per node — bounds memory per node

    def search(self, prefix: str) -> list[str]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []                          # no completions exist for this prefix at all
            node = node.children[ch]
        return [q for q, _ in node.top_k]

Why cache top-K at every node, not just leaf/word-end nodes: a query for prefix "sys" needs the answer at that exact node, not at wherever the matching words happen to terminate — caching at every node along every inserted word's path is what makes the O(prefix length) walk sufficient on its own, with no further traversal needed.

6. High-Level Architecture

flowchart LR
    C[Client] --> LB[Load Balancer] --> AS[Autocomplete Service]
    AS --> Cache[(Redis Cache<br/>hot prefixes)]
    AS --> Trie[In-memory Trie<br/>replicated per instance]
    LOG[Search Query Logs] --> AGG[Batch Aggregation<br/>Job - hourly/daily]
    AGG --> TB[Trie Builder]
    TB -->|new trie snapshot| Trie

Read path: client → Autocomplete Service checks Redis for the prefix first (a small, extremely hot working set — a handful of characters covers a huge fraction of real traffic) → on cache miss, walks the in-memory trie directly (still fast — O(prefix length), no disk I/O) → caches the result for subsequent identical prefix requests.

Write path (offline, not on the request hot path): raw search query logs are aggregated in batch (hourly or daily, not real-time) into query-frequency counts → a trie builder job constructs a fresh trie snapshot from these aggregated counts → the new snapshot is distributed to (and atomically swapped into) every Autocomplete Service instance's in-memory trie.

Why the write path is batch, not real-time: rebuilding/updating a trie live, per-query, under 1M req/sec of read traffic would create contention between readers and a constantly-mutating structure. Accepting that trending queries take, say, an hour to appear in suggestions is a deliberate trade for keeping the read path (the actual latency-critical path) completely decoupled from ingestion — the same eventual-consistency reasoning as [[CAP Theorem & Consistency Models]] applied concretely.

7. Distributing the Trie at Scale

A single trie for a truly massive query corpus may not fit comfortably in one instance's memory, or may need read-throughput beyond one instance's capacity.

  • Sharding by first character(s) of the prefix: instance A serves prefixes a–m, instance B serves n–z (or a finer split) — the Autocomplete Service's front-end routes each request to the right shard based on the prefix's leading characters, similar in spirit to [[Consistent Hashing]]'s partitioning logic, though here partitioned by a natural key range rather than a hash.
  • Full replication instead of sharding: since the trie is read-mostly and rebuilt in batch (not continuously mutated), replicating the entire trie to every instance and load-balancing reads round-robin is often simpler and perfectly viable if the trie fits in memory per instance — sharding is the fallback specifically when it doesn't fit, not the default.

8. Caching Strategy

Even with an O(prefix length) trie walk, a Redis layer in front (§6) squeezes out the very hottest single-character and two-character prefixes — a query for "a" or "th" is asked constantly and benefits from being served without even touching the trie. This is the same cache-hit-rate reasoning as [[Latency vs Throughput]]: short, extremely common prefixes have a very high hit rate, making the cache layer's cost clearly worth it here (unlike a long-tail access pattern where caching can be a net loss).

9. Personalization (a common follow-up)

Global top-K by raw frequency is the baseline; a stronger version blends in a user's own recent search history:

def get_suggestions(prefix: str, user_id: str, k: int = 5) -> list[str]:
    global_suggestions = trie.search(prefix)
    personal_suggestions = get_user_recent_matching(user_id, prefix, limit=2)
    merged = personal_suggestions + [s for s in global_suggestions if s not in personal_suggestions]
    return merged[:k]

Personal history is a small, per-user, recency-weighted list (not another trie) — cheap to maintain and merge, and it's what makes autocomplete feel personalized without rebuilding the shared global structure per user.

10. Deep Dives / Follow-ups

  • Typo tolerance: out of scope for a pure trie (which requires an exact prefix match) — typically handled by a separate fuzzy-matching layer (edit-distance-bounded lookup, or a separately trained model) in front of or alongside the trie, not by the trie itself.
  • Trending/real-time spikes (a breaking-news query suddenly surging): the batch-rebuild cadence in §6 is too slow for this specifically; a common hybrid is a small, frequently-refreshed "trending" overlay checked before falling back to the batch-built trie, rather than trying to make the whole trie real-time.
  • Multi-language support: separate tries per language/locale, selected by request context, rather than one trie mixing scripts and ranking signals that don't compare meaningfully across languages.

11. Interview Drill Questions

  1. Why not just DFS the trie subtree under a prefix at query time to find the top-K? — At real QPS (potentially ~1M autocomplete requests/sec), a DFS per request over a potentially large subtree is far too slow — pre-computing and caching top-K at every node during batch construction moves that cost entirely off the read path, leaving only an O(prefix length) walk plus an O(K) return.
  2. Why update the trie in a batch job instead of incrementing frequencies in real time as searches happen? — Real-time mutation of a structure serving ~1M reads/sec would create read/write contention on the hot path; batching decouples ingestion from serving entirely, at the acceptable cost of trending queries taking up to the batch interval (e.g., an hour) to surface — an explicit, reasonable eventual-consistency trade for this domain.
  3. The trie doesn't fit in memory on one instance. What are your options? — Shard by prefix range across multiple instances (route by leading characters, similar to how [[Consistent Hashing]] partitions by key), or reduce cached top-K's per-node footprint; sharding is the answer specifically when full replication no longer fits, not the default starting design.
  4. A user searches for a prefix with zero historical matches (a genuinely novel query). What does the system return? — Trie.search returns an empty list when the prefix path doesn't exist at all — the client-side UI simply shows no suggestions, which is the correct behavior rather than trying to force some multiplication of unrelated results.
  5. How would you incorporate personalization without a full per-user trie? — Maintain a small per-user recent-query list (not a trie) and merge it with the global trie's top-K at request time — cheap because personal history is small and doesn't need the trie's prefix-matching machinery at that scale.

Cross-links

[[Caching & Redis]] · [[Consistent Hashing]] · [[CAP Theorem & Consistency Models]] · [[Latency vs Throughput]] · [[Database Replication & Sharding]]