Design Search Autocomplete (Typeahead)

- Return the top 5-10 completions for a typed prefix                           - p99 < 100 ms end to end (users type fast)
- Rank by popularity (optionally recency/personalisation)                      - Very high availability; stale suggestions are acceptable
- Filter offensive or blocked terms                                            - 5 B searches/day; each query triggers several prefix requests
- Suggestions update as trends change                                          - Read-heavy; updates can be hourly or near-real-time

Deep dives p. 58

• Data structure: a trie where every node stores its top-k completions (with scores), so a lookup is O(length of prefix), with no subtree traversal. Memory is reduced with compressed (radix) tries and by pruning rare queries.
• Sharding: partition by prefix (first 1-2 characters, balanced by traffic) or replicate the whole trie on every server (5 GB fits) and just load-balance; replication is simpler.
• Freshness: rebuild the trie hourly/daily from aggregated logs (weekly counts with time-decay) and swap atomically (blue/green). For breaking trends, a small real-time overlay (stream-aggregated recent top queries) is merged at query time.
• Latency tricks: debounce keystrokes, cancel in-flight requests, cache responses per prefix at the CDN (TTL minutes), pre-fetch likely next prefixes, keep the connection warm (HTTP/2).
• Quality: normalise (lowercase, trim), handle typos with fuzzy matching or edit-distance fallback, filter profanity and legal blocks, de-duplicate near-identical suggestions, and personalise by re-ranking with user/location/history signals.
• Experimentation: log impressions and selections; measure suggestion acceptance rate and keystrokes saved with A/B tests.