vault

Typeahead Autocomplete System Design

25 min read

Typeahead Autocomplete System Design

A typeahead autocomplete system returns a ranked list of completion suggestions for the prefix the user has typed, in well under the human-perceptible latency threshold (typically a 50ms server budget so that the total round-trip including network and rendering stays under 200ms). The functional core is a prefix-search problem: given a string s, return the top-K strings in a corpus (search queries, user names, product titles) whose prefix is s, ranked by some popularity-or-relevance score. The canonical data structure is a Trie whose internal nodes carry a precomputed top-K list of completions descending from that node, eliminating the need for a depth-first traversal at query time. At Web scale (Google Search, Twitter mention completion, e-commerce product search) the trie is sharded by prefix prefix (typically the first two characters of the input), trie updates run as a batch refresh once an hour rather than in real time (typeahead doesn’t usually need fresh-second updates), and the trending tail is folded in via a separate fast-path. Personalization layers on top — own-history completions are blended with global completions using a learned re-ranker. This note covers the canonical Trie-based architecture, the precompute-top-K-per-node optimization, the sharding-by-prefix scheme, fuzzy completion via Levenshtein automata (Mihov & Schulz 2004), the offline pipeline that mines popular completions from query logs, abuse / safety filtering, and multilingual handling.

1. Functional and Non-Functional Requirements

1.1 Functional requirements

  • Prefix-based suggestions. Given the user’s current input string, return the top-K strings whose prefix matches.
  • Ranked by popularity. Most-popular completion first; ties broken by recency, personalization, and lexicographic order.
  • Top-K return. Typically 5-10 suggestions; configurable.
  • Multilingual. Per-language indexes / per-language ranking, with language-detection fallback.
  • Personalized. A user’s own past searches surface in their own typeahead.
  • Trending insertion. A surging query (sports event, breaking news) appears in suggestions within minutes.
  • Spell-corrected variants. “kompyt” should suggest “computer” via fuzzy match.
  • Safety filtering. Offensive completions are blocked even if popular.
  • Empty-prefix behavior. When the input is empty, show a default list (recent / trending / personalized).

1.2 Non-functional requirements

  • Latency. Server-side budget ≤ 50ms p99. Total user-perceived (including network, rendering) ≤ 200ms.
  • QPS. ~5-10× the search query rate, because typeahead fires on each keystroke. Google’s search QPS of ~100k/s implies ~500k-1M typeahead requests/sec.
  • Index size. Vocabulary of ~10⁹ unique queries (long tail of search history). Per-language; aggregate ~10⁹-10¹⁰ entries.
  • Freshness. Trending suggestions appear within minutes (5-15 minutes typical). Long-tail completions can lag by hours.
  • Availability. ≥ 99.99% — typeahead failure makes search feel broken.
  • Cost. Typeahead is “free” (no ad revenue) yet runs at higher QPS than search itself; engineering pressure on cost-per-query is significant.

2. Capacity Estimation

2.1 Vocabulary size

  • Distinct queries ever issued: ~10¹¹ over the history of a major search engine.
  • Distinct queries with frequency ≥ 10 (the “indexable” vocabulary): ~10⁹.
  • Per language: ~10⁸ for English, dropping to ~10⁵-10⁷ for less-used languages.
  • Average query length: ~20 characters.

A naive Trie over 10⁹ strings, each averaging 20 chars: 10⁹ × 20 = 2 × 10¹⁰ trie nodes. With pointer overhead (~16 bytes/node), raw memory ~ 320 GB.

Compressed trie (Patricia Trie or DAFSA — Directed Acyclic Finite-State Automaton): collapses common prefixes, typically 5-10× compression → ~30-60 GB. With per-node top-K cached (5 strings × ~20 bytes each = 100 bytes per node), add ~ 10¹⁰ × 100 = 1 TB. That doesn’t fit on one machine — hence sharding.

2.2 Sharding scheme

Shard by the first two characters of the prefix:

  • 26² = 676 shards (English alphabet).
  • Each shard holds ~ 10⁹ / 676 ≈ 1.5M queries with that prefix prefix.
  • Fits comfortably in RAM on a single server.

Per-language extension: prepend the language code → en:co... lands on the English co shard, es:ca... on the Spanish ca shard.

2.3 Latency

  • Shard router lookup: 1ms (consistent-hash table).
  • Network RTT to shard: ~1ms intra-DC.
  • Shard-side trie walk (depth ≤ 20 chars): ~10μs in-RAM.
  • Top-K read from precomputed per-node list: O(K) ≈ 5μs.
  • Network back: 1ms.
  • Shard merge / re-rank with personalization: 5-10ms.
  • Total budget consumed: ~15-20ms p50; p99 with tail effects ≤ 50ms.

2.4 Update rate

  • Query log volume: ~10⁵ queries/sec ingested into the typeahead pipeline.
  • Trie rebuild cadence: hourly batch (3600 × 10⁵ = 3.6 × 10⁸ queries per build cycle).
  • Trending fast-path: separate streaming detector with sub-minute latency, blended at query time.

3. API

3.1 External

GET /complete?q={prefix}&lang={lang}&user={user_id}&n={top_k}&geo={lat,lon}

Response (JSON):

{
  "suggestions": [
    {"text": "facebook", "score": 0.91, "type": "global"},
    {"text": "facetime", "score": 0.62, "type": "global"},
    {"text": "facebook login", "score": 0.34, "type": "personal"}
  ],
  "latency_ms": 12
}

The type field distinguishes global popularity from personal-history boosts.

3.2 Internal RPC (per-shard)

message CompleteRequest {
  string prefix = 1;
  string lang = 2;
  int32  top_k = 3;
  bytes  user_signals = 4;       // for personalization
}
 
message CompleteResponse {
  repeated Suggestion suggestions = 1;
  int32   shard_id = 2;
  float   latency_ms = 3;
}

A given prefix routes to exactly one shard (determined by prefix-prefix), so no scatter-gather — different from search.

4. Data Model

4.1 Trie node (per-shard)

class TrieNode:
    children: dict[char, TrieNode]      # or array indexed by char
    top_k_completions: list[(string, score)]   # precomputed, sorted desc by score
    is_terminal: bool                   # this node ends a valid string
    aggregate_score: float              # for ranking

The top_k_completions list is the heart of the optimization (§7.2): without it, every query would require a depth-first traversal of the subtree rooted at the matching node, which can be O(branching_factor^remaining_depth). With it, the leaf returns the precomputed list in O(K) time.

4.2 Source data — query logs

log_entry:
  query: string
  user_id: bytes      (hashed/anonymized)
  timestamp: int64
  result_clicked: bool
  result_url: string
  language_detected: string
  geo: (lat, lon)

Streamed into the typeahead pipeline. Anonymized — typeahead does not need PII; only aggregated query → frequency suffices for the global side, and per-user-history is stored separately under stricter access control.

4.3 Personal completions

Per-user store of recent searches (last ~100): user_id → list[(query, timestamp)]. Stored in a fast KV (Redis, Memcached, or per-user trie shard). Used at query time to blend with global suggestions.

4.4 Safety / abuse filter

A blocklist of regex patterns + a learned classifier. Applied during the offline build and at query time (defense in depth — a new offensive query could appear between builds).

A separate sliding-window count of (prefix, query_text) → recent_frequency. Updated continuously via a streaming pipeline (Kafka → Flink / Storm). Read at query time and unioned with the trie’s top-K.

5. High-Level Architecture

flowchart LR
    subgraph OfflineBuild[Offline / Batch — hourly]
        QL[(Query Logs)] --> A[Aggregator<br/>count by query]
        A --> R[Rank scoring<br/>frequency + recency + diversity]
        R --> SF[Safety Filter]
        SF --> TB[Trie Builder<br/>per language]
        TB --> SH[Shard by prefix-prefix]
        SH --> SS[(Shard Snapshots<br/>S3 / Colossus)]
    end
    subgraph Streaming[Streaming Trending]
        QL2[(Live Query Stream)] --> CD[Burst Detector<br/>Count-Min Sketch]
        CD --> TT[(Trending Cache<br/>Redis)]
    end
    subgraph Serve[Online Serving]
        U[User typing] --> CL[Client] --> LB[Load Balancer]
        LB --> RT[Router<br/>prefix-prefix → shard]
        RT --> SD[Shard Server<br/>RAM trie]
        SS --> SD
        SD --> RR[Re-ranker<br/>blend global + personal + trending]
        TT --> RR
        PH[(Personal History<br/>Redis)] --> RR
        RR --> CL
    end

What this diagram shows. Three subsystems run in parallel. The offline build (top) consumes the query logs every hour, aggregates by query, applies a safety filter, ranks each query by a popularity score, builds per-language tries, shards them by prefix-prefix, and writes immutable snapshots to a blob store. The streaming trending pipeline (middle) consumes the same logs in near-real-time and detects bursts via a Count-Min Sketch-based heavy-hitter detector; results land in a small Redis cache. The online serving path (bottom) routes each typeahead request to the single shard that owns the requested prefix-prefix; the shard returns the precomputed top-K from its trie; a re-ranker on the same node (or one hop away) blends in the user’s personal history (from a separate KV store) and the trending cache, applies any final safety filter, and returns the suggestions to the client. The asymmetry — one-shard lookup for global completions, one-KV lookup for personal, one-cache lookup for trending — is what keeps the latency budget tight; multi-shard fanout would blow it.

6. Request Flow

sequenceDiagram
    participant U as User
    participant C as Client
    participant LB as Load Balancer
    participant RT as Router
    participant S as Shard Server
    participant T as Trie
    participant TR as Trending Cache
    participant P as Personal History
    participant R as Re-ranker

    U->>C: types "fa"
    C->>LB: GET /complete?q=fa&user=u123
    LB->>RT: HTTP request
    RT->>RT: shard = hash("fa") mod N
    RT->>S: CompleteRequest
    S->>T: walk("fa")
    T-->>S: node + top_K_completions
    S->>R: top_K (global)
    R->>P: get_personal_completions(u123, "fa")
    P-->>R: [past queries with prefix "fa"]
    R->>TR: get_trending("fa")
    TR-->>R: [recent surges with prefix "fa"]
    R->>R: blend(global, personal, trending) + safety filter
    R-->>S: top-N final
    S-->>RT: CompleteResponse
    RT-->>LB: HTTP response
    LB-->>C: JSON
    C-->>U: rendered suggestions

What this diagram shows. The end-to-end path on a single keystroke. Routing is deterministic: the prefix’s first two characters determine the shard, so there is no fanout — one shard, one trie walk, one set of precomputed top-K completions. The re-ranker fans out small parallel lookups (personal history KV, trending cache) and merges everything in-memory. Total in-system time should be ≤ 30ms p99; client-perceived round-trip ≤ 100-200ms with network.

7. Deep Dive

7.1 The trie as the primary data structure

A Trie is the canonical structure for prefix lookup. Each path from the root to a node corresponds to a string prefix; the node represents the prefix and (if terminal) a complete string. To find all strings with prefix s:

  1. Walk down the trie following the characters of s. If at any point the next character has no child, no strings exist with that prefix → empty result.
  2. The node reached after consuming s is the root of the subtree containing all strings with prefix s.
  3. Enumerate the subtree (DFS) and collect terminal-marked strings.

For a trie over 10⁹ strings of average length 20, step 3 alone visits up to ~10⁹ nodes in the worst case (prefix "" returns everything). Even for a 5-character prefix in a popular shard, the subtree may have millions of strings — too slow at 50ms budget.

7.2 Precomputed top-K per node

The optimization that turns this into a constant-time lookup: at every node, precompute and store the top-K most popular completions in the subtree rooted there. Build-time cost: O(N · log K) for N strings (each string contributes to K node-lists from root to its terminal). Query-time cost: O(prefix_length) for the trie walk + O(K) to read the precomputed list. No subtree traversal needed.

Memory cost: each of ~10¹⁰ nodes stores K=10 strings × ~20 bytes = ~200 bytes per node → ~2TB extra per language, dominating the trie’s structural memory. Optimization: store only at nodes where the prefix is “useful” (e.g., depth ≥ 1, branching factor > 1) — this drops the count by a factor of 10.

This precompute-top-K-per-node trick is THE typeahead optimization. Bast & Weber (SIGIR 2006) describe a “succinct index” variant that compresses the structure further; modern Lucene’s AnalyzingSuggester uses an FST-based variant that fuses dictionary and top-K.

7.3 FST / DAFSA representation

For very large vocabularies, plain trie’s pointer overhead dominates. A DAFSA (Directed Acyclic Finite-State Automaton) merges nodes that have the same suffix-tree shape — common suffixes (like ing, tion) share representation. For English Web vocabulary, this gives 5-10× compression vs a plain trie.

FSTs (Finite-State Transducers) generalize the DAFSA by attaching an output value to each transition, so the automaton is no longer just a set membership test but a SortedMap<ByteSequence, Output> — exactly what you want when each completion needs a weight. Mike McCandless’s foundational write-up describes Lucene’s FST building 9.8 million Wikipedia terms into an in-memory structure of just ~69 MB (built under a 256 MB heap), far smaller than a TreeMap, with the trade-off that FST lookup costs more CPU than a hash map but stays negligible against the rest of query execution (McCandless 2010). Elasticsearch’s completion suggester applies this directly: it builds an FST whose transition outputs encode an integer weight (0 to 2³¹), and at query time it walks the graph one input character at a time and then enumerates the reachable endings, returning them sorted by that weight as the score. Crucially the FST is built per segment at index time and written to disk in a format that loads into RAM fast — never built at query time — which is how it scales horizontally and supports near-real-time updates without a full rebuild (Elastic, You Complete Me). This is the production-grade realization of the “dictionary fused with ranking output” idea that the precompute-top-K-per-node trick (§7.2) expresses more naively.

7.4 Sharding by prefix-prefix

Sharding by the first 2 characters of the input (not of any particular completion):

  • For request prefix “facebook” → first two chars “fa” → shard 26 * f + a = 26*5 + 0 = 130.
  • All completions starting with “fa…” live on shard 130.
  • The shard’s trie root is conceptually rooted at “fa” (the first two characters are implicit).

Pros:

  • Single-shard lookup → no scatter-gather.
  • Hot prefixes (like “fa”, “co”) get their own shard, which can be replicated independently.
  • Easy to scale: add capacity by adding replicas of hot shards.

Cons:

  • Skewed load: shard “fa” gets ~5% of English-language traffic; shard “qa” gets ~0.1%. Solve via per-shard replication count proportional to load.
  • The very-short-prefix case (“f”, “fa”) returns an enormous result set — handled with the precomputed top-K (§7.2).

7.5 Personalization

Per-user history is tiny (~100 recent queries) and lives in a fast KV store keyed by user_id. At query time, fetch the user’s history, filter to those starting with the current prefix, and blend with the global top-K via a learned weight:

final_score = α · global_score + β · personal_match_score + γ · trending_score

Where:

  • α + β + γ = 1 — normalized weights (typically α=0.6, β=0.3, γ=0.1).
  • global_score is the precomputed popularity (frequency-based with recency decay).
  • personal_match_score is high if the user has recently issued this query themselves.
  • trending_score is high if this completion is currently surging.

The weights can be tuned per language, per geography, even per query category (informational vs navigational).

A separate streaming pipeline:

  1. Subscribe to the live query stream.
  2. Maintain rolling counts via Count-Min Sketch across multiple time windows (last 1 min, 5 min, 60 min).
  3. For each query, compute recent_rate / long_term_rate. Threshold above K.
  4. The top trending queries by ratio land in a Redis cache, keyed by their prefix-prefix shard for fast retrieval.

The trending list is small (~10K queries globally) and rebuilt every minute.

7.7 Fuzzy / spell-tolerant completions

The user types “kompyt”; we want to suggest “computer”. Two approaches:

Levenshtein automaton (Mihov & Schulz 2004). Construct a finite-state automaton that accepts any string within edit distance k of the target, then intersect it with the dictionary FST (§7.3) so the walk only follows transitions consistent with both — yielding candidate completions whose distance from the input is ≤ k without enumerating the whole dictionary. Lucene’s FuzzySuggester implements exactly this on top of its AnalyzingSuggester: per the Lucene API docs it uses the Damerau–Levenshtein (optimal string alignment) distance by default (treating a transposition as a single edit; pass transpositions=false for classic Levenshtein), and it caps maxEdits at 2 — “higher distances are not supported,” because a distance-2 Levenshtein automaton is the practical ceiling for fast intersection (Lucene FuzzySuggester). A nonFuzzyPrefix parameter requires the first few characters to match exactly (no edits), which both prunes the search and matches user intent — people rarely fat-finger the very first letter.

N-gram index alongside the trie. Index every 3-character n-gram of every query, and for a misspelled input look up its n-grams to find candidate matches. Less precise than Levenshtein but very fast.

A complementary trick used widely in production is to mine misspellings offline from query-log behavior — sequences where a user typed a misspelling, got poor results, then retyped the correct form — and store those misspellings as alternative surface forms pointing at the same canonical completion, so the runtime path needs no fuzzy match at all for the common typos.

Uncertain

Verify: that Google Search specifically implements offline misspelling-expansion of autocomplete entries this way. Reason: this is a well-known industry pattern and consistent with Google’s published “predictions reflect real searches” stance, but Google does not document its autocomplete spell-handling pipeline. To resolve: a Google engineering disclosure. #uncertain

7.8 Safety filtering

The trie is built from query logs; query logs contain offensive content. Mitigations:

  1. Build-time filter. A regex blocklist + ML classifier removes offensive completions before they enter the trie.
  2. Query-time filter. Even if a bad completion slips through, a final query-time filter scrubs it before returning.
  3. Manual review. A team curates the top N completions for sensitive prefixes (politicians, celebrities, news topics) — a known headache for search products historically.

The Cai & de Rijke 2016 survey discusses safety as one of the unsolved problems of QAC.

7.9 Edge caching

For ultra-popular short prefixes (f, fa, ga) the answer rarely changes. CDN edge caches store the response keyed by (prefix, language, geo) with TTL ~minutes. This offloads ~30% of typeahead requests from the origin.

For longer prefixes (≥ 5 characters), edge caching has poor hit rate — the long tail makes most prefixes unique-per-user.

7.10 Why no real-time updates

Unlike search (Twitter Search System Design), typeahead typically does not need real-time updates of the global index. The global index represents aggregate query popularity, and a single new search has negligible impact on its value. Hourly batch rebuilds + a separate fast trending path cover the freshness need without the engineering cost of a real-time updateable trie.

The exception: trending events (sports finals, breaking news) — covered by §7.6’s trending fast-path.

8. Scaling

8.1 Horizontal scaling

  • 26² = 676 shards by prefix-prefix (per language).
  • Hot shards replicated 3-10× depending on traffic skew.
  • Stateless re-ranker — scales linearly.

8.2 Cross-region

Per region: full trie replica (read-only). Updates propagated from a central build cluster via blob-store push.

8.3 Personalization scaling

Per-user history KV — sharded by user_id hash. Read-heavy, write-rare (one write per search) — easy to scale.

Count-Min Sketch-based detector scales linearly with input throughput. Output (~10K trending queries) fits in a single Redis instance per region.

8.5 Cost containment

  • Most clients can client-cache prior responses for the prefix they’ve already typed (typing “facebook” hits the server only on each new character; suffix-extension can be inferred client-side from the previous response).
  • Compress responses (gzip / brotli).
  • Move re-ranking close to the trie shard to avoid network hops.

9. Real-World Example

9.1 Google Search autocomplete

Google publishes the behavior but not the data structures. From Google’s own documentation, the signals are explicit: predictions reflect real searches that have been done on Google (across users — explicitly not merely your own past queries, though signed-in users additionally get personalization), ranked by how common and trending a matching query is, with freshness prioritized when interest in a topic is rising (so breaking-news terms surface quickly), and tailored by the searcher’s language and location (Google, How Google autocomplete predictions work). Google is careful to note autocomplete is not simply “the most common queries,” which is why it differs from Google Trends — there is a relevance and safety layer on top of raw popularity.

Safety is a first-class concern: the 2017 “Project Owl” update introduced a formal published policy for why a prediction may be removed (hateful, sexually explicit, violent, dangerous, etc.) and a user-facing “Report inappropriate predictions” affordance below the search box that feeds algorithm tuning (Search Engine Land on Project Owl). This maps to the build-time-plus-query-time safety filtering of §7.8.

Uncertain

Verify: the internal data structures and the ~500k+ QPS / shard-count figures for Google’s production autocomplete. Reason: Google documents the user-visible signal mix and policies (cited above) but does not disclose the serving architecture or load numbers; the QPS figure in §2 is an order-of-magnitude estimate, and the Trie-with-precomputed-top-K design here is the canonical architecture (consistent with the public behavior and with Lucene/Elasticsearch’s FST suggester), not a confirmed description of Google’s internals. To resolve: an official Google engineering paper or talk on autocomplete serving (none published at this depth). #uncertain

9.2 Twitter mention typeahead

When a user types @, the autocomplete shows usernames the user is most likely to mention. Architecture (per Twitter engineering blog series):

  • Per-user candidate list = (followees + recent mentions + recent DM partners + people who recently mentioned the user).
  • Pre-computed in a batch job; pushed to a per-user KV store.
  • At type time, prefix-filter the per-user candidate list — small enough that a linear scan is fine.

Different from Google-search autocomplete because the candidate set per user is small (~thousands).

9.3 LinkedIn member search typeahead

Similar to Twitter mention: per-user candidate set (1st-degree connections, 2nd-degree weighted) precomputed, scanned linearly at type time.

9.4 E-commerce (Amazon, Etsy)

  • Trie built from product titles and historical search queries.
  • Per-category boosts; product-typeahead also shows product images and prices.
  • Higher freshness needed for new product launches → hybrid batch + streaming.

9.5 Apache Lucene / Elasticsearch Suggesters

This is the fully open, production-grade reference — and the only one whose internals are public. Lucene ships AnalyzingSuggester (exact prefix on an FST), FuzzySuggester (the Levenshtein-automaton variant of §7.7, capped at 2 edits), and FreeTextSuggester (an n-gram language model for next-word prediction). Elasticsearch’s completion field type wraps these: it builds an in-memory FST per Lucene segment at index time, encodes a per-suggestion integer weight as the FST output, walks the graph character-by-character at query time, and returns endings sorted by weight — with benchmarked fuzzy (edit-distance-2) lookups around 0.75 ms (Elastic, You Complete Me). The implication for an interview: when asked “how would you actually build this,” the honest answer for most non-Google-scale products is “use Elasticsearch/OpenSearch completion suggesters” rather than hand-rolling a trie — the FST design already embodies §7.2’s precompute-the-ranking and §7.3’s compression in one structure.

10. Tradeoffs

ChoiceAlternativeWhy this one
Trie + precomputed top-K per nodePlain trie + DFS at query timeDFS is too slow on popular short prefixes; precompute moves the cost offline
Shard by prefix-prefixHash-by-completionPrefix-shard guarantees single-shard lookup (no fanout)
Hourly batch rebuildReal-time trie updatesReal-time tries are hard (concurrency-correct mutation); hourly is good enough for global popularity
Separate trending fast-pathRoll trending into batchTrending needs minute-grain; batch is hour-grain
FST/DAFSA for compressionPlain trie5-10× memory savings at moderate code complexity
Personal completions blended at query timePersonal completions baked into global triePersonal data has different access controls, lifecycle, scale; separate stores
Edge caching for short prefixesNo edge cache~30% offload for trivial cost
Levenshtein automaton for fuzzyN-gram fuzzyLevenshtein is more precise; N-gram is simpler; choose by language and use case
Build-time + query-time safety filterBuild-time onlyDefense in depth; new offensive queries can appear between builds

11. Pitfalls

  1. Precompute-top-K staleness. A query that surges between rebuilds is invisible until the next build. Mitigation: trending fast-path. Without it, products feel stale during news events.

  2. Skewed shard load. Prefix-prefix fa (or co, to) handles 5-10% of all traffic; prefix-prefix qa handles 0.1%. Replicating uniformly wastes resources; replicating by load is operationally complex but necessary.

  3. Empty-prefix special case. When the input is empty, return trending + personal — never the entire global top-K. Otherwise the response is dominated by the same five queries forever.

  4. Personal-completions privacy. Per-user history is sensitive. Store under stricter access controls than the global trie. Anonymize aggressively (hash + bucket). Some products opt out personal completions entirely for privacy.

  5. Multilingual confusion. A user typing “co” in Spanish wants Spanish completions; in English, English. Detect language from request headers + recent search history. Error case: cross-language users get muddled completions.

  6. Top-K diversity. If the top-K is ["facebook", "facebook login", "facebook messenger", "facebook stories", "facebook help"], the suggestions are all variants of “facebook”. A diversity-aware ranker (MMR — Maximal Marginal Relevance, Carbonell & Goldstein 1998) reduces redundancy.

  7. Click feedback loop. Suggesting only popular queries means popular queries get clicked more, reinforcing their popularity. The long tail starves. Mitigations: occasional epsilon-greedy exposure of less-popular queries; learned exploration.

  8. Network instability. Each keystroke fires a request; jitter shows up as suggestion-flickering. Client-side heuristics: only fire after 100ms of no-typing; debounce keystrokes; client-side cache prior response for prefix-extension scenarios.

  9. Build-pipeline data freshness lag. If the offline build cycle takes 90 min, completions are 90 min stale on average. Reduces the value of “yesterday’s news” suggestions; trending pipeline must compensate.

  10. Adversarial inputs. Users discover queries that cause auto-suggest embarrassments (“auto-suggest racism”). Once exposed publicly, the team must scrub the offending completions and audit the safety filter.

  11. Memory pressure from per-node top-K. Storing K=10 strings per node × 10¹⁰ nodes = TBs. Optimizations: store only at internal nodes with branching factor > 1, use FST output values to encode the top-K compactly, accept K=5 instead of K=10.

  12. Cold-cache restart. A shard with a freshly-pushed snapshot must mmap and warm the working set into RAM before serving. Rolling restarts must be slow + monitored to avoid global cache cold-start.

12. Interview Variants

  • Design typeahead for an in-memory dataset of 10K strings. Trivial: keep a list, filter by prefix at query time. No need for a trie at this scale.
  • Design typeahead for autocomplete in a code editor (LSP). Different problem — symbol completion is per-language, per-file, semantically aware. See LSP specs and tree-sitter-based completers.
  • Design typeahead with strict ≤ 10ms p99. Aggressive client caching, edge caching for short prefixes, denser shard packing.
  • Design typeahead with personalization-only (no global popularity). Just a per-user trie; tiny. Used in some private-search products.
  • What changes for an emoji keyboard typeahead? Vocabulary is small (~3K emojis) but with semantic mapping (“happy” → 😀); needs a synonym-augmented trie.
  • What changes for a multi-word prefix? Each word is a separate prefix; top-K must consider whole-string popularity, not per-word. Build the trie over space-joined queries; the prefix walk handles the rest.
  • Implement the trie + top-K precompute on a whiteboard. This is the classic LeetCode 642 “Design Search Autocomplete System”: input is typed character-by-character ending in #, and at each character you return the top 3 historical sentences sharing the typed prefix, ranked by hot-degree (number of past occurrences) with ASCII order as the tie-break, inserting the finished sentence on #. The reference solution is a trie whose nodes carry the candidate sentences plus a global frequency map — the precompute-vs-traverse trade-off of §7.2 in miniature — and reduces to ~50 lines.
  • How do you handle CJK languages with no spaces? Tokenize via dictionary segmenter at build time; store per-character trie nodes. Query-time prefix walks on character boundaries.

13. Open Questions / Uncertain

Uncertain

Verify: the specific ranking-blend weights (the α/β/γ in §7.5) and per-shard QPS/replica counts used by production typeahead. Reason: no major search product discloses its scoring weights or serving topology; these are tuned continuously and treated as competitive. The blend in §7.5 is illustrative of the form (a learned weighting of global popularity, personal match, and trending), not a measured configuration. To resolve: a published engineering paper with concrete weights (none exists at this depth). #uncertain

On LLM-generated suggestions, the picture is no longer blank. As of Google I/O 2025, Google ships “AI-powered question suggestions that go beyond standard autocomplete” — helping users formulate complex, multi-clause questions rather than completing a single popular query — surfaced in a redesigned, expanding search box and tied into AI Mode / AI Overviews (Google I/O 2025 AI Mode update). This is an additional surface layered beside, not a replacement for, the popularity-driven prefix completion described in this note: the trie/FST path still handles the millisecond keystroke-by-keystroke prefix completions, while the LLM path generates fuller candidate questions on a slower cadence.

Uncertain

Verify: how the LLM question-suggestion path is served (model size, latency budget, whether it runs per-keystroke or on debounce, how it is blended with the prefix-trie results). Reason: Google has announced the feature but not its serving architecture or how it co-exists with the sub-50ms prefix path. To resolve: an engineering disclosure on the AI Mode suggestion pipeline. #uncertain

  • Is the precompute-top-K-per-node still optimal at 10⁹+ vocabulary, or does an FST-with-output-values (as in Lucene/Elasticsearch, §7.3) dominate now?
  • How will typeahead architecture change as models like ChatGPT replace single-query search behavior with multi-turn conversations?
  • Is there value in real-time global trie updates for any product (vs the hourly batch + trending fast path)?
  • How do typeahead systems handle bidirectional / RTL languages efficiently?

14. See Also

Graph View

Backlinks