Design Google Typeahead / Autocomplete

Trie Data Structure: The Core Algorithm

Standard Trie:

A trie node stores a character, a count of how many times the full path forms a top query, and child pointers. For the prefix "sy", the path traverses root → s → y and exposes completions like:

• "system": count 50,000
• "system design": count 20,000
• "system architecture": count 5,000

Each node caches its top-3 completions so a prefix lookup is O(prefix length), not a subtree traversal. On write, the counts propagate upward and the cached top-3 lists are refreshed asynchronously.

Root
└── s
    └── y
        └── s
            └── t
                └── e
                    └── m (★ "system" count=50000)
                        └── d → e → s → i → g → n (★ "system design" count=20000)
                        └── a → r → c → h (★ "system architecture" count=5000)

Optimization 1: Store Top-K results at each node: At each trie node, pre-compute and cache the top 10 most popular completions. When user types "sys" → go to node 's' → 'y' → 's' → return pre-cached top 10. Avoids traversing the entire subtree at query time → O(prefix_length) lookup.

Node 'sys':
  top_10: [
    ("system design", 20000),
    ("system architecture", 5000),
    ("system requirements", 3000),
    ...
  ]

Optimization 2: Compressed Trie (Radix Tree / Patricia Trie): Merge nodes with single children: s → y → s → t → e → m becomes "system" as one node. Reduces memory by 50-70%.

Optimization 3: Trie Serialization: Serialize trie as a flat byte array for compact storage and fast loading. Use memory-mapped files for instant startup.

Offline Data Pipeline

• Search Logs: Every search query logged with timestamp, user_id (anonymized), location
• Kafka: Buffers search events
• Flink/Spark Aggregation: Count query frequency in sliding windows (hourly, daily, weekly). Apply decay function: score = Σ (count_i × decay^(age_in_hours)). Recent queries weigh more than old ones. Filter: Remove queries with < 5 occurrences (noise), profanity, PII. Output: query_string → popularity_score to Aggregated Query DB
• Trie Builder: Read aggregated query-score pairs. Build trie in memory. At each node, compute top-K descendants. Serialize to binary blob → upload to S3. Frequency: Rebuild every 15 minutes (trending) or hourly (stable)

Autocomplete Service

• Stateless: Each server loads the trie blob into memory on startup
• Trie refresh: New trie blob published to S3 → servers poll every N minutes → atomically swap old trie with new trie (double-buffering)
• Lookup: trie.search(prefix) → returns pre-cached top 10 suggestions in O(prefix_length)
• Scaling: Horizontally scale by adding servers (each holds a full copy of the trie). For very large tries: shard by first character(s) of the query

CDN Caching

• Popular prefixes ("how to", "what is", "why") are cached at CDN edge
• TTL: 1 hour (popularity is relatively stable for common prefixes)
• Cache key: autocomplete:{prefix}
• Impact: 30-50% of autocomplete requests served from CDN

Client-Side Optimizations

• Debouncing: Only send request after 100-200 ms of no typing (reduces 70% of requests)
• Local cache: Cache previous responses. "syst" → "syste" → reuse results from "syst" client-side
• Prefetch: After showing suggestions for "sys", prefetch "syst", "sysa", etc. in background