Typeahead & Autocomplete

Problem Statement & Requirements

Functional Requirements

• Prefix matching -- as the user types each character, return the top suggestions matching the prefix
• Top-K suggestions -- return the K most popular/relevant suggestions (typically K=5-10)
• Real-time updates -- incorporate trending queries into suggestions quickly (minutes, not days)
• Personalization -- blend user's own search history into suggestions
• Multi-language support -- handle queries in multiple languages and scripts
• Spell tolerance -- handle minor typos in prefix (fuzzy matching)
• Phrase completion -- suggest completions for multi-word queries ("how to b" → "how to bake bread")
• Trending queries -- boost currently trending topics (sports events, breaking news)
• Offensive content filtering -- suppress suggestions for hateful, explicit, or harmful content
• Entity-aware suggestions -- recognize and boost entities (people, places, brands)

Non-Functional Requirements

• Ultra-low latency -- suggestions must appear in < 100 ms (ideally < 50 ms)
• High availability -- 99.99% uptime; degraded suggestions are better than none
• Massive scale -- serve 100K+ suggestion requests per second
• Consistency -- eventual consistency is acceptable (different users may see slightly different suggestions)
• Scalability -- handle billions of unique queries in the corpus
• Bandwidth efficiency -- minimize data transfer (users type fast, requests are frequent)

Scope Boundaries

Scale Estimations

Query & Suggestion Corpus

Traffic

Storage

Bandwidth

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

Send the prefix with language and any allowed personalization context, and return a short ranked list. The client should associate each reply with the prefix that requested it and ignore stale replies. Cancellation saves work, but correctness must not depend on the server receiving a cancellation in time.

Store normalized query candidates, display text, scores, and eligibility metadata separately from the serving index. A prefix index or trie is a derived structure that can be rebuilt. Version its snapshots so a server does not mix nodes and ranking data from different rebuilds.

Trie Data Structure (Core)

Basic Trie Structure

Trie Node Structure

struct TrieNode {
    children: HashMap<char, TrieNode>,   // or array[128] for ASCII
    is_end_of_query: bool,               // marks complete query
    frequency: u64,                       // search frequency count
    top_k: Vec<(String, u64)>,           // precomputed top-K suggestions
                                          // for prefix ending at this node
}

Memory per node:
  - children pointers:  ~256 bytes (hash map) or 1 KB (array)
  - is_end + freq:      9 bytes
  - top_k (10 entries): ~400 bytes (query strings + scores)
  Total: ~700 bytes - 1.5 KB per node

For 500M unique queries × avg 20 chars:
  - Upper bound nodes: 10B (but massive sharing of prefixes)
  - Actual nodes (shared prefixes): ~2-3B
  - Memory: 2B × 1 KB = ~2 TB  ← TOO MUCH for naive trie

Optimized Trie: Compressed Trie (Patricia / Radix Tree)

Further Optimization: Top-K Precomputation

Instead of storing full queries at each node, store only the top-K suggestion IDs:

struct CompactTrieNode {
    children: Vec<(char, u32)>,     // (char, child_offset) - sparse
    top_k_ids: [u32; 10],           // indices into suggestion string pool
    flags: u8,                       // is_terminal, has_children, etc.
}

Separate string pool:
  suggestions: Vec<String>          // all 500M suggestion strings
  scores:      Vec<u32>             // corresponding popularity scores

Memory per node: ~60 bytes
Total nodes: ~500M
Total trie structure: ~30 GB  ← fits in memory!
String pool: ~10 GB
Total: ~40-50 GB per replica

Top-K Propagation Algorithm

Building the trie with top-K at each node:

1. Insert all (query, frequency) pairs into the trie
2. Bottom-up traversal:

   For each node N:
     candidates = []
     if N.is_terminal:
       candidates.append((N.query, N.frequency))
     for child in N.children:
       candidates.extend(child.top_k)
     N.top_k = heapq.nlargest(K, candidates, key=frequency)

Example:
  Node "app" has top_k:
    [("apple", 50K), ("apple pie", 30K), ("app store", 25K),
     ("apple music", 20K), ("application", 15K), ...]

Query time: O(L) where L = prefix length
  - Walk the trie character by character: O(L)
  - Return precomputed top_k: O(1)
  - Total: O(L) ← typically L < 20, essentially O(1)

Query Flow (Online Serving)

Keystroke-to-Suggestion Flow

Client-Side Optimizations

Data Collection & Aggregation Pipeline

Query Log Collection

Frequency Scoring Formula

Score(query) = Σ  count(query, day_i) × decay(day_i)
              i=1..30

Where:
  decay(day_i) = e^(-λ × age_in_days)
  λ = 0.1 (tunable decay rate)

Example for "apple pie":
  Day 0 (today):  5000 searches × e^(0)    = 5000
  Day 1:          4800 searches × e^(-0.1) = 4342
  Day 7:          3000 searches × e^(-0.7) = 1489
  Day 30:         2000 searches × e^(-3.0) = 100
  Total score: 5000 + 4342 + ... + 100 = weighted sum

Why exponential decay?
  - Recent popularity matters more than historical
  - Trending queries rise fast, old fads decay
  - Tuning λ controls memory of the system

Trending Query Detection

Trie Building Pipeline (Offline)

Batch Trie Construction

Trie Serialization Format

Caching Strategy

Multi-Layer Cache Architecture

Cache Invalidation

Problem: When trie is updated, cached suggestions become stale.

Strategy: TTL-based expiration (no active invalidation)

  Justification:
  - Suggestions change slowly (hourly trie rebuilds)
  - Slightly stale suggestions are acceptable
  - Active invalidation at CDN scale is expensive and complex
  - 5-15 minute TTL = max staleness of 15 minutes

  Exception: TRENDING queries
  - Bypass CDN cache for trending prefixes
  - Set Cache-Control: no-cache for trending-eligible short prefixes
  - Or: use websocket push to update client cache for trending

Sharding & Replication

Sharding Strategy

Replication

Full Serving Topology

Personalization

User History Blending

User History Storage

Offensive Content Filtering

Multi-Layer Filtering

Multi-Language Support

Language-Specific Challenges

Alternative Data Structures

Trie vs. Alternatives Comparison

Approach: Precomputed Hash Map (for high-QPS systems)

Alternative to trie for extreme QPS requirements:

Precompute ALL possible prefixes → top-K map:

  "a"     → [apple, amazon, apple pie, ...]
  "ap"    → [apple, app store, apple pie, ...]
  "app"   → [apple, app store, apple pie, ...]
  "appl"  → [apple, apple pie, apple music, ...]
  "apple" → [apple, apple pie, apple music, ...]
  ...

Storage: 500M queries × avg 20 chars = 10B prefix entries
         10B × (key + 10 suggestion IDs) = ~200 GB

  TOO MUCH for in-memory!

Optimization: Only precompute prefixes of length 1-6
  (covers ~95% of user typing before they click a suggestion)

  26^1 + 26^2 + ... + 26^6 ≈ 300M prefix entries
  But with actual query distribution: ~50M meaningful prefixes
  50M × 500 bytes = ~25 GB ← feasible!

  For prefixes > 6 chars: fall back to trie lookup

Approach: Inverted Index Style (Elasticsearch)

Instead of a trie, use an inverted index with edge n-grams:

Document: "apple pie recipe"
Index terms (edge n-grams):
  "a", "ap", "app", "appl", "apple"
  "p", "pi", "pie"
  "r", "re", "rec", "reci", "recip", "recipe"

Query: prefix "app" → lookup posting list for "app"
  → returns all suggestions containing a word starting with "app"

Advantages:
  - Leverages existing search infrastructure (Elasticsearch)
  - Easy updates (just index new documents)
  - Built-in relevance scoring, filtering, aggregations

Disadvantages:
  - Higher latency than in-memory trie (~5-10ms vs ~1ms)
  - More complex query for phrase completion
  - Overkill for simple prefix matching

Best for: Medium-scale systems (< 10K QPS) that already use Elasticsearch

Real-Time Updates (Streaming Path)

Near Real-Time Trie Update Architecture

Advanced Topics

Fuzzy Matching (Typo Tolerance)

Problem: User types "aple" but means "apple"

Approach 1: Edit Distance at Query Time
  For prefix "aple", find all trie nodes within edit distance 1:
    "aple" → "apple" (insert 'p')
    "aple" → "able"  (substitute p→b)
    "aple" → "ape"   (delete l)

  Cost: Expensive! For each prefix, explore O(26^d) branches
        where d = max edit distance

  Optimization: BK-tree or Levenshtein automaton
    - Precompute finite automaton for edit distance ≤ 2
    - Intersect automaton with trie in single traversal
    - O(L) time regardless of edit distance

Approach 2: Phonetic Matching
  Soundex / Metaphone encoding:
    "aple"  → A140
    "apple" → A140  (same code!)
  Store phonetic codes in separate index
  Match phonetically, then boost exact prefix matches

Approach 3: Query Log Corrections (most practical)
  When user types "aple" and then reformulates to "apple":
    Store mapping: "aple" → "apple" with confidence score
  At query time: lookup "aple" in correction map
    If found: also search for "apple" and merge results
  Low latency: O(1) hash map lookup
  High quality: based on actual user behavior

Context-Aware Suggestions

Beyond prefix matching — use context for better suggestions:

1. Previous query context:
   Query 1: "python"
   Query 2: "for" → suggest "for loop python", not "ford trucks"

2. Page context:
   User is on a cooking website
   Types "ch" → suggest "chicken recipe", not "chrome download"

3. Time context:
   During NFL season: "sup" → "super bowl" boosted
   Tax season: "h" → "h&r block", "how to file taxes" boosted

4. Device context:
   Mobile: shorter suggestions (screen space limited)
   Desktop: longer, more detailed suggestions

Implementation:
   Context vector + suggestion scoring:
   score(suggestion) = base_score
                     × context_boost(query_history)
                     × time_boost(current_events)
                     × device_factor(screen_size)

Zero-Prefix Suggestions

When user clicks search box but hasn't typed anything:

Show:
  1. User's recent searches (from personalization store)
  2. Currently trending queries
  3. Seasonal / contextual suggestions

Implementation:
  - No trie lookup needed
  - Precomputed list per user segment
  - Cached aggressively (one request per search session)
  - Updated every 15 minutes

This is the "prefetch" request — sent on search box focus

Typing, deleting, and retyping can leave several requests in flight. Display only the response that matches the current input state. Empty prefixes, composed characters, and language-specific normalization also need deliberate handling; a byte prefix is not always the same thing as the characters a person thinks they typed.

Key Tradeoffs

Pre-computed Top-K vs. On-the-Fly Ranking

Pre-computed (chosen for global suggestions):
  + O(L) lookup — walk trie, read pre-stored top-K
  + Extremely fast (< 1 ms)
  + Simple serving logic
  - Stale until trie rebuild (hourly)
  - Can't easily incorporate real-time personalization into top-K
  - Rebuild cost: hours of compute for 500M queries

On-the-fly ranking:
  + Always fresh
  + Easy to blend personalization, trending, context
  - Slower: must traverse subtree, score, sort at query time
  - For popular short prefixes, subtree can have millions of entries
  - Latency unpredictable (depends on subtree size)

Hybrid approach (Google's / production systems):
  Pre-compute top-K for global suggestions → fast base
  Merge with personalization + trending at query time → fresh blend
  Total cost: O(L) trie walk + O(K) merge = still very fast

Trie Rebuild Frequency

Frequent rebuilds (every 15 min):
  + Fresher suggestions
  + Trending queries appear faster
  - Higher compute cost
  - More deployment risk (more frequent swaps)
  - Diminishing returns (most queries don't change in 15 min)

Infrequent rebuilds (daily):
  + Lower compute cost
  + Stable, well-tested suggestions
  - Stale: trending topics delayed by hours
  - New queries don't appear until next rebuild

Chosen: Hourly batch rebuild + real-time overlay
  - Best of both: stable base + fresh trending
  - Overlay is small (100K-1M entries) — cheap to update
  - Merge at query time is O(K) — negligible cost

Global vs. Regional Tries

Single global trie:
  + Simpler architecture
  + One build pipeline
  + Global trends visible everywhere
  - "pizza near me" suggestions are same in Tokyo and New York
  - Wastes memory on irrelevant suggestions per region

Per-region/locale trie:
  + Region-specific suggestions ("weather tokyo" boosted in Japan)
  + Smaller per-region trie (less memory)
  + Better relevance for location-dependent queries
  - More complex build pipeline (one per locale)
  - ~50 languages × ~10 regions = 500 tries to maintain
  - Trending detection harder (smaller per-region signal)

Hybrid:
  - Global trie for universal queries (brands, tech terms)
  - Regional overlay for location-specific queries
  - Merge at query time based on user's locale/location

Memory vs. Disk for Trie Storage

Chosen: Memory-mapped (mmap) trie file

• OS handles paging — hot paths stay in RAM
• Cold paths (rare prefixes) loaded on demand from SSD
• Best cost/performance ratio at scale
• Cold start: instant (just mmap the file, no deserialization)

Precision vs. Recall in Suggestions

High precision (fewer, more relevant suggestions):
  + Users trust suggestions more
  + Less visual noise
  + Lower risk of offensive/irrelevant suggestions
  - May miss niche queries user actually wants
  - Less "discovery" of new queries

High recall (more diverse suggestions):
  + Users discover queries they didn't think of
  + Better for exploratory search
  - More irrelevant suggestions → user ignores autocomplete
  - Higher risk of showing offensive content
  - More visual noise

Chosen: High precision (K=5-8 suggestions)
  - Quality over quantity
  - Users want THE suggestion they're looking for
  - Offensive content risk minimized with fewer suggestions
  - Can show "more suggestions" button for users who want recall

Fault Tolerance & Reliability

Failure Scenarios & Handling

Health Checking & Monitoring

High-Level Architecture

Detailed Architecture

Serving Infrastructure

Global Deployment

Latency Budget

Add a new phrase that becomes popular in an hour. Decide how it enters suggestions without rebuilding the entire index, and how it later fades. Then add a removal request: safety and privacy corrections should not have to wait for the normal popularity-decay schedule.

System Design Interview Tips

What Interviewers Look For

1. Trie fundamentals — can you explain how a trie works and why it's the right data structure?
2. Scale reasoning — how much data, how many requests, how much memory?
3. Top-K at each node — this is the key insight that makes prefix lookup O(L)
4. Data pipeline — how do you collect query frequencies and build the trie?
5. Caching strategy — multi-layer caching is critical for 100K+ QPS
6. Real-time trending — how do you surface breaking news quickly?
7. Tradeoff reasoning — rebuild frequency, precision vs recall, global vs regional

Common Follow-Up Questions

Suggested 45-Minute Interview Structure

 0-5  min:  Clarify requirements (search suggestions? K=? latency?)
 5-10 min:  Scale estimations (QPS, corpus size, memory)
10-18 min:  Core data structure (trie, compressed trie, top-K precomputation)
18-28 min:  System architecture (serving path, data pipeline, caching)
28-35 min:  Deep dive: pick ONE
            - Option A: Real-time trending pipeline
            - Option B: Sharding & replication
            - Option C: Personalization strategy
35-42 min:  Tradeoffs (rebuild frequency, trie vs alternatives, global vs regional)
42-45 min:  Monitoring, failure handling, fuzzy matching