Typeahead / Search Autocomplete

0) Problem Restatement

Design the autocomplete box in a search bar. As the user types "how to", we show the top ~10 suggestions such as "how to tie a tie" and "how to make pancakes", updating on every keystroke. Suggestions come from what people search most, should include trending searches within minutes, and must appear in under 100 ms per keystroke.

1) Requirements

1.1 Functional

• Return the top 10 suggestions for a prefix.
• Rank by popularity, with freshness (trending) and optionally personalization.
• Update suggestions as new searches happen.
• Hide offensive or blocked suggestions.

1.2 Non-Functional

• Very low latency: under 100 ms end to end, ideally about 10 ms on the server.
• Very high QPS: every keystroke is a request.
• Highly available. It's fine if suggestions are a few minutes stale.

1.3 Scale Estimates

• 500M searches/day, ~10 keystrokes each → 5B suggestion requests/day ≈ 60K/sec, peak ~200K/sec.
• Distinct queries worth suggesting: ~100M. At ~50 bytes each plus trie overhead, that's tens of GB. This can be sharded, and the most popular prefixes are small.

1.4 API Design

• GET /v1/suggest?q=how%20to&limit=10&lang=en → ["how to tie a tie", "how to make pancakes", ...]

2) High-Level Architecture

2.1 Overview

• Suggestion Service: looks up the prefix in an in-memory index and returns the top 10.
• Trie index: built offline and loaded into memory on suggestion servers.
• Query log pipeline: every completed search goes to Kafka. A batch job counts queries (e.g., over the last 7 days, weighted toward recent days) and builds a new trie. A streaming job tracks trending queries.
• Caches: the browser caches recent results. The CDN or edge caches very common short prefixes ("a", "ho", "how").

2.2 Architecture Diagram

flowchart LR
    U["Search box"] -->|"prefix"| CDN["CDN / edge cache"]
    CDN --> SS["Suggestion Service - in-memory trie"]
    U -->|"completed searches"| K[("Kafka - query log")]
    K --> BJ["Daily batch - count, build trie"]
    K --> ST["Streaming - trending counts"]
    BJ --> OS[("Trie snapshots")]
    OS -->|"load"| SS
    ST -->|"trending boost"| SS

3) Data Structure: Trie with Top-K

A trie (prefix tree) stores strings letter by letter: the path h → o → w represents "how". To make lookups instant:

• At each node, store the top 10 completions for that prefix, already sorted.
• A lookup walks down the prefix (length L, e.g., 6 steps) and returns the stored list. No searching the subtree.
• Memory trade-off: we store top-10 lists at every node, which is more memory but constant-time answers.

A simpler alternative: a sorted list of all queries, where a binary search finds the range with that prefix. That still needs top-K, so we precompute it for short prefixes.

4) Key Flows

4.1 Serving a keystroke

1. The client waits ~50 ms after typing stops (debounce) to avoid sending a request for every fast keystroke.
2. It checks its local cache (results for "how t" are often reused).
3. The edge cache serves common prefixes. Otherwise, the suggestion server walks the trie and returns the top 10.
4. The server optionally mixes in trending and personal suggestions (recent searches by this user).

4.2 Building the index

1. A daily job counts all queries from the logs, with weights so recent days count more.
2. It removes blocked and unsafe queries and applies minimum-count thresholds (rare queries may contain private info).
3. It builds the trie with top-K lists, writes a snapshot, and servers load it (blue/green: load the new one, then switch).

5) Deep Dive A — Freshness (trending)

The daily build is too slow for breaking news. So:

• A stream job counts queries in 5-minute windows and finds queries whose count jumped compared to normal.
• A small "trending" index (thousands of queries) is pushed to servers every few minutes.
• At lookup time, merge the trie's top-10 with trending matches for the prefix, boosting trending ones.

6) Deep Dive B — Scale and sharding

• Replicate full tries across many servers if they fit in memory (~tens of GB is fine on large machines).
• If too big, shard by prefix: "a–c" on shard 1, and so on. Popular first letters (like "s") need smaller ranges. A router maps the first 1–2 characters to a shard.
• Deterministic ties: when two suggestions have equal scores, sort alphabetically so results don't flicker between keystrokes.
• Personalization: keep each user's recent searches on the client or in a small per-user store, and blend them in at the top.

7) Trade-offs & Alternatives

8) Common Follow-up Questions

• "How do you handle typos?" Add a fuzzy-matching fallback (edit distance of 1) for when the prefix has no results, or learn common misspellings from logs.
• "Privacy?" Only suggest queries typed by many distinct users (e.g., 50+), so personal data never shows up as a suggestion.
• "Other languages?" Build a separate trie per language or market, and normalize text (lowercase, remove accents) before lookup.

9) Wrap-Up

Keep an in-memory trie where each node stores its precomputed top 10 completions, so every keystroke is a short walk down the tree. Rebuild it daily from query logs with filters, blend in a streaming trending index for freshness, and cut load with client debounce and caching plus edge caching of short prefixes. Replicate the trie, or shard it by prefix when it grows too big.