39. Design Typeahead / Autocomplete

Tests: low-latency suggestions, prefix data structures (trie / FST), ranking, real-time updates, caching.

39.1 Requirements

Functional

• As user types, show top-K suggestions.
• Rank by relevance (popularity, personalization).
• Support multiple languages.
• Real-time-ish: trending queries surface within hours/minutes.
• Spell-correction (optional).

Non-functional

• P99 latency < 50 ms (every keystroke!).
• High availability.
• Massive scale (e.g., Google: 5B+ searches/day → ~50B+ keystrokes/day).

39.2 Estimates

• 1B users × 20 keystrokes/day = 20B requests/day = ~230K req/sec average; peak ~1M/sec.
• Each request: lookup top-K (e.g., 10) suggestions for a prefix.
• Suggestions corpus: ~100M-1B unique queries.

39.3 The core data structure

Trie

Tree where each path from root is a string. Nodes can store top-K completions.

        root
       / | \
      a  b  c
     /|
    p q
    |
    p
   /|
  l e
  |
  e

For prefix "app", traverse to "app" node; return its precomputed top-K.

Improvements

• Compressed trie / radix trie: collapse single-child chains.
• Top-K cached at each node: avoid traversing subtree at query time.

FST (Finite State Transducer)

Compressed structure for keyword suggestion. Used by Lucene's completion suggester.

Ternary search tree

Memory-efficient alternative.

39.4 Architecture

[ Client ]──debounce──→[ Front service ]
                            │
                    [ Edge cache (CDN) ]
                            │
                    [ Suggestion svc ]
                            │
                   in-mem trie / FST
                            │
                  [ Backing store (Redis/SSD) ]
                            │
                  [ Builder pipeline (offline) ]──reads logs from
                  [ Search log (Kafka) ]

39.5 Storage strategy

Option A: in-memory trie per node

Load entire trie into RAM on each suggestion node.

• Top-N completions cached at each node.
• Updates: rebuild periodically (e.g., daily).
• Read latency: microseconds.

Limit: memory. Trie of 1B queries can fit in tens of GB; comfortable on a single box.

Option B: distributed trie (sharded)

Shard by prefix (first 1-2 chars). Each shard holds a trie subtree.

• Routing: based on first chars.
• More memory total.
• Slightly higher latency (network hop).

For most apps, A suffices. For Google-scale, more nuanced.

Option C: backing KV store

For each prefix, store sorted list of top-K completions in Redis.

• Cardinality is bounded (alphabet^prefix_len, but mostly sparse).
• Update via offline pipeline that recomputes top-K per prefix.

39.6 Building the index

Offline pipeline:

1. Ingest user queries from search log (Kafka).
2. Aggregate counts (Flink): per query, total count over time window.
3. Build trie / FST.
4. Distribute new index to suggestion nodes (snapshot swap).

For real-time updates, you can also:

• Maintain a small "delta" trie for recent queries.
• Merge delta + main at query time.
• Periodically compact.

39.7 Ranking

Beyond simple count:

Popularity

Count of query in last 30 days. Most common signal.

Recency-weighted

Decay older counts; trending queries surface.

Personalization

• User's past searches.
• Geographic location.
• Time of day.
• Demographic.

Candidate generation (top-K from popularity) → re-rank with personalization features.

Editorial / safety

• Block offensive completions.
• Boost commercial intent for shopping searches.
• Politically sensitive: explicit handling per region.

39.8 Latency budget

For < 50 ms P99:

• Network RTT: 10-30 ms (depends on user proximity).
• Server-side: < 20 ms.
• Trie lookup: ~µs.
• Heavy work (personalization re-rank): on hot path, must be milliseconds.

Tactics:

• Edge cache common prefixes.
• Local cache in app server.
• Avoid round-trips: trie in-memory.
• Async pre-warm trie on deploy.

39.9 Client-side optimizations

• Debounce: don't fire on every keystroke; wait 50-100ms after typing stops.
• Cache suggestions client-side: same prefix again → reuse.
• Cancel inflight on new keystroke: avoid out-of-order results showing stale.

39.10 Sharding

If trie too big for one node:

• Shard by first character: 26+ shards. Imbalance (some letters dominate).
• Shard by hashed prefix-2: balanced; need routing layer.
• Shard by query-volume: hot prefixes get dedicated shards.

Each shard replicated for HA + read scale.

39.11 Internationalization

• Per-language trie: avoids cross-language pollution.
• Locale detection.
• Different ranking per locale.
• Unicode normalization (NFC).
• Tokenization for languages without spaces (Chinese, Japanese, Korean).

39.12 Spelling correction / fuzzy match

For "appel" → suggest "apple":

• BK-tree (Burkhard-Keller) for edit distance.
• Or: index character n-grams; search by overlap.
• Or: ML model rewriting query.

Mostly applied as fallback when prefix gives no good results.

39.13 Failure modes

• Suggestion svc down: client falls back to no suggestions (degrade gracefully).
• Trie node OOM: smaller trie or shard further.
• Builder pipeline lag: trie stale by hours; OK temporarily.

39.14 Sketch for interview

[Client (debounce)]──→[Edge cache]──→[Suggest svc (in-mem trie)]
                                              │ (per-prefix top-K precomputed)
                                              │
                                       [ Builder pipeline ]
                                              │
                                  [Flink agg from Kafka(query log)]

39.15 What an interviewer wants

• Trie (or FST) with top-K cached at each node.
• Read latency < 50ms; in-memory.
• Offline build pipeline aggregating real query log.
• Personalization layer on top of popularity baseline.
• Client-side debouncing.

39.16 Common pitfalls

• DB lookup per keystroke: way too slow.
• No client debouncing: 10× the QPS.
• No top-K cached at trie nodes: traverse subtree each query.
• Single-region deploy: cross-continent users see 200ms+ latency.

Key takeaways

• Trie in memory with precomputed top-K per node = sub-ms lookup.
• Offline pipeline rebuilds trie from query log; swap snapshots.
• Debounce client-side; cache aggressively.
• Ranking = popularity + personalization + safety filters.
• Sub-50ms P99 is non-negotiable; design every layer for it.