Design Search Autocomplete / Typeahead (Google-scale)

Search autocomplete is the inverse of a payment system — availability and latency dominate correctness. A stale suggestion is a mild annoyance; a 300ms suggestion is a product failure because users type faster than that and the UI feels laggy. Google's public latency bar for autocomplete is sub-100ms p99 end-to-end, including network, and the service itself aims for <30ms server-side. At 10B queries/day (~115K QPS average, ~500K peak), this latency budget changes what data structures are even candidates: no disk reads, no network hops between services, no database lookups per keystroke. The system has to return top-K suggestions for any prefix from tens of millions of candidate queries, and it must do so while also handling personalization, trending, spell correction, and multi-language support. The core insight senior candidates must surface: the entire working set lives in memory, the top-K is precomputed at every prefix node, and the trie is rebuilt offline — never mutated online. Candidates who propose 'query Elasticsearch on every keystroke' fail immediately; at 500K QPS, Elasticsearch would need thousands of nodes and still miss the latency bar. Candidates who say 'use a trie' without addressing how to update it without downtime, how to shard it, and how to attach top-K at each node are incomplete. The interview is testing whether you can hold in your head that typeahead is a read-only hot-path with async rebuild architecture.