Typeahead Search System Design

The prompt sounds like a data-structures homework problem: "Design the typeahead for a web search engine, like the autocomplete in Google Search. As a user types into the search box, show them the ten most likely completions of what they're typing, updated on every keystroke, fast enough that it feels instant."

Most candidates hear "prefix" and reach for a trie, and the trie is the right instinct. It is also about a tenth of the answer. One search is about eight requests, because every keystroke asks again, so five billion searches a day become forty billion suggestion requests and a peak near a million a second. Each answer has to land before the next keystroke does, roughly 200 milliseconds later. The suggestions have to know that the marathon happening this morning matters more than last year's. And every one of them is the platform speaking, not the user, so a suggestion that leaks one person's private search or repeats a defamatory rumour is a real-world harm with your company's name on it.

The Trap Built Into a Familiar Question

Two failures show up again and again:

• The Whiteboard Trie: draws a beautiful trie, walks the subtree under the prefix to find the most popular completions, and stops. The prefix a has millions of descendants, and the walk that felt instant on ten words takes seconds on a hundred million. Nobody asked where the counts come from, how the trie gets rebuilt, or how a new version replaces the old one while a million requests a second keep arriving. Signal: knows the data structure but hasn't thought about the system around it.
• The Live-Updating Index: wires every search straight into the serving trie so that it's "real-time", then adds locks, then shards it by first letter, then discovers that the shard for s is on fire. Signal: optimised for freshness nobody measured, at the cost of the read path that every user feels on every keystroke.

The passing performance splits the problem in two. The serving path is a read-only, in-memory index of about 20 GB, small enough to replicate on every node instead of sharding, with the top fifteen completions precomputed at every node so a lookup costs microseconds. Most short prefixes never reach it, because the per-keystroke request carries no user identity and the CDN can answer 60% of them. The data path learns from searches offline: logs, a daily rebuild over a 30-day window with time decay, a validation gate, and an atomic snapshot swap. A streaming fast path carries breaking queries into suggestions within ten minutes. A policy layer runs on both: a privacy threshold of fifty distinct users, build-time filters, and a serve-time blocklist that honors a takedown within the hour.