Design Search Autocomplete — Cheat Sheet

Search autocomplete (typeahead) displays ranked query suggestions as a user types. Every keystroke triggers a prefix lookup that must return the top-K most popular matching queries in under 100ms. The system must handle massive query volumes, keep suggestion frequencies fresh, and remain highly available — all while serving a latency-sensitive, user-visible feature.

• ✓Given a typed prefix, return the top-5 most popular matching query suggestions
• ✓Suggestions must reflect actual search popularity, updated at least daily
• ✓Support all alphanumeric characters and spaces in queries
• ✓Return results within 100ms at p99 for a good user experience
• ✓Real-time or near-real-time frequency updates when query volume shifts dramatically
• ✓Google scale: ~10B searches/day → ~115,000 QPS peak

• ✓Autocomplete QPS (peak): ~575,000 req/sec (5 keystrokes × 115K search QPS)
• ✓Trie nodes (top 50B queries × avg 20 chars): ~50B nodes → ~1 TB RAM (naïve), pruned to ~10 GB
• ✓Unique prefixes cached in Redis: ~100M prefixes × 200 bytes/entry ≈ 20 GB per Redis shard
• ✓Query log ingestion rate: 115,000 queries/sec → ~1 TB of raw logs per day
• ✓Top-K list per prefix (K=5): ~1 KB per prefix → 100M prefixes ≈ 100 GB total

• ✓Browser / Client — Debounces keystrokes (300ms) before firing the autocomplete API request. Caches results per prefix in a local JS Map for the session to avoid redundant network calls. Cancels in-flight requests when a newer keystroke arrives.
• ✓API Gateway — Terminates TLS, applies rate limiting per IP (protect against scraping), and routes GET /autocomplete?q={prefix} to the Autocomplete Service. Returns cached responses from CDN for popular prefixes.
• ✓Autocomplete Service — Stateless application tier. Checks Redis Sorted Set cache for the prefix first. On a miss, queries the Trie Service. Assembles the top-K list and returns it. Also asynchronously publishes the raw query to the Query Logger.
• ✓Redis Sorted Set (Cache) — Stores prefix → top-K suggestions as a sorted set scored by frequency. ZRANGEBYLEX for prefix scanning, ZINCRBY for frequency bumps. Acts as the primary fast-path — handles the majority of reads without touching the Trie.
• ✓Trie Service — In-memory Trie augmented with a top-K min-heap at every node. Serves cache-miss requests. Rebuilt or incrementally updated from the frequency store. Partitioned by first character (or consistent hash of prefix) across multiple nodes.
• ✓Query Logger — Receives every submitted search query (not every keystroke — only the final submitted query). Writes to Kafka topics partitioned by query term. Buffers locally to avoid blocking the search path.

• ✓Trie (in-memory) vs Redis Sorted Sets for autocomplete → Both — Redis as primary cache, Trie as fallback: Redis Sorted Sets are mutable (frequencies can be incremented without a rebuild), horizontally scalable, and operationally simpler. The Trie handles cache misses and provides a complete ranked view rebuilt from the full frequency corpus daily. Using only the Trie requires a full rebuild on every update; using only Redis requires storing every possible prefix upfront.
• ✓Real-time (Flink streaming) vs batch (Spark daily) frequency updates → Batch for baseline, streaming for trending spikes: Batch is operationally simple and consistent — the full frequency corpus is recomputed on a known schedule. Pure streaming is complex and can amplify transient spikes (a bot query). The hybrid approach uses streaming only to surface genuinely trending queries above a high threshold, keeping the batch job as the authoritative source of truth.
• ✓Store top-K at every Trie node vs compute on query → Pre-compute top-K at every node (offline): On-the-fly DFS over a subtree can visit millions of nodes for short prefixes like "a". Pre-computing drops query latency from O(subtree) to O(L). The trade-off is higher memory (O(nodes × K)) and the need for offline rebuilds, but both are manageable at Google scale with pruning.
• ✓Exact prefix match vs fuzzy / typo-tolerant matching → Exact prefix match (with normalisation): Fuzzy matching (edit distance, n-gram index) dramatically increases complexity and latency. Normalisation (lowercase, trim) catches the most common user inconsistencies. Full typo tolerance is better implemented as a separate spell-check layer (like Google's "Did you mean?") which runs in parallel with the exact autocomplete — not inside the hot path.

• ✓Always open by clarifying scale. "How many DAU? How many keystrokes per search?" changes your design from a single Redis node to a sharded cluster with a CDN layer.
• ✓Explain why you log submitted queries only (not keystrokes) — it shows you understand data quality and avoiding artificial frequency inflation for partial queries.
• ✓Interviewers frequently ask "how do you keep suggestions fresh?" Have a crisp answer: daily Spark batch for baseline, optional Flink streaming for trending, with Redis ZINCRBY as the update primitive.
• ✓When asked about the Trie, proactively mention the subtree-traversal problem and explain the pre-computed top-K solution using post-order DFS and a min-heap — this is what separates strong candidates from average ones.
• ✓Mention client-side debounce (300ms) and request cancellation early — it demonstrates awareness that autocomplete performance is a full-stack problem, not just backend.
• ✓If pushed on edge cases, discuss: what happens when a new trending topic appears in the last hour (streaming pipeline), how you handle offensive/spam query suppression (a blocklist checked before returning results), and how you protect user privacy (minimum frequency threshold before a query enters suggestions).