42. Search Autocomplete / Typeahead

Business context. Search box suggestions. Outcomes: search success/CTR and fewer keystrokes. Every 100 ms of delay lowers usage, so results must arrive faster than the user types (well under 100 ms at the edge).

Requirements. Top-10 suggestions for a prefix; ranked by popularity (and personalization, freshness); filtered for policy (no offensive suggestions); multi-language. 10B queries/day → ~5 keystroke requests each → ~600k req/s at peak.

Design.

Offline: query logs ─▶ aggregate (daily batch + streaming for trends) ─▶ score (frequency, recency decay, CTR)
         ─▶ filter (policy/blocklists) ─▶ build trie with top-K precomputed at every node ─▶ versioned artifact
         ─▶ distribute to serving fleet (sharded by prefix ranges, replicated)
Online:  client (debounce ~50ms, cache prior prefixes) ─▶ CDN/edge cache for short popular prefixes
         ─▶ suggestion servers: trie lookup O(len(prefix)) → precomputed top-K ─▶ merge personalization
            (user's recent searches) + trending (from streaming layer) ─▶ response

Deep dives.

Precompute top-K per node. Traversing a subtree at query time is too slow. Storing the top 10 at each node trades memory for O(prefix length) lookups. See the DSA guide §21 for tries.
Updates: rebuilding the trie daily and swapping it atomically is simple and robust. Trending queries come from a small real-time overlay merged at serve time (a streaming top-K, §44).
Sharding: by first character(s), with uneven splits ("s" is much bigger than "x"). Or replicate the entire trie if it fits in memory, which removes fan-out entirely.
Caching: short prefixes are few and extremely hot, so cache them at the edge with short TTLs.

Strategic lens. The biggest risk isn't latency. It's trust and safety (a defamatory or offensive suggestion becomes a news story). The policy filter and a fast takedown path (block a suggestion globally within minutes, bypassing the daily build) are first-class requirements.

🏗️ Flow: keystrokes to suggestions.

 User types "sys" (debounce 30-50 ms; cancel in-flight request on next key)
   ─▶ client cache: have "sy" results? filter locally while waiting
   ─▶ Edge: cached response for "sys" (TTL 5 min, keyed by locale) ─hit─▶ return
   ─▶ Suggest svc (replica holds full trie for locale en-US in memory):
         node("sys").topK → ["system design", "systemctl", "sysco", ...]
       + trending overlay (last 15 min, streaming top-K): ["sys outage today"]
       + personal history (user's recent queries, from session store)
       → blend & policy filter → top 8
 Offline: logs → daily aggregation → trie build (versioned) → canary → swap pointer atomically
 Takedown: blocklist service pushes updates in seconds → filter at serve time (no rebuild needed)

🌍 How it's built in production.

Facebook typeahead ("The Life of a Typeahead Query", 2010): it pre-fetches the user's friend and connection data into the browser when the page loads, so first results are instant and client-side, while global results come from servers that aggregate several backends.
LinkedIn Cleo (open source, 2012): typeahead built on per-partition prefix indexes plus Bloom-filter tricks.
Search engines combine popularity, freshness (trending), and personalization, with strong policy filtering. Suggestion quality is also a legal and trust surface.

⚠️ Corner cases.

Unicode normalization: "café" typed as e + combining accent vs the precomposed é must match. Normalize (NFC/NFKC) and case-fold per locale (the Turkish dotted/dotless i).
CJK input methods: IME composition fires keystroke events before the user commits a character. Query only on composition end.
Typos: prefix tries don't handle "sytem". Add fuzzy matching (edit distance 1 on short prefixes) or a spelling-correction stage.
Breaking news freshness: the daily trie doesn't know about an event from 10 minutes ago, so the trending overlay is required. Spam campaigns try to game it, so add velocity anomaly detection.
Privacy: personal suggestions shown on shared computers. Respect incognito and history settings, and never surface other users' private queries.