How would you design search autocomplete?

Assume hundreds of millions of queries per day, a p99 suggestion latency under 100 milliseconds, prefix queries of one to twenty characters, and suggestions that should reflect popular and fresh queries. The read path must be fast and highly available; ranking can lag slightly.

Data structures

• Trie: walks the prefix character by character and returns the top-k completions stored at each node
• Prefix hash map: precompute the top-k list for every prefix, which is fast but memory-heavy
• Search index with edge n-grams: flexible ranking but usually slower than a purpose-built prefix index
• Sharding by prefix range or a hash of the prefix, with replication for availability
• Cache the top prefixes at the edge because the distribution is highly skewed

A trie can be compressed into a radix tree to save memory. Store only the top-k suggestions at each node, where k is small, rather than every descendant. That bounds the response size and makes a lookup proportional to the prefix length plus k, not to the vocabulary size.

Updates come from query logs and content changes. Rebuild or update the index asynchronously, because a write-heavy real-time trie is expensive to keep consistent. Rank by a blend of frequency, recency and personalization. Apply a decay so stale viral queries do not dominate forever, and filter unsafe or policy-violating terms before they enter the index.

Personalization changes the cache key. A shared cache can serve the global top-k, while a per-user layer reranks a small candidate set. If personalization is expensive, keep it off the critical path and return the global result first.