Why not query Elasticsearch or the database directly for each keystroke?

Budget. After network time, the server has roughly 10 ms, and autocomplete traffic runs at several times search QPS since it fires per keystroke. A general-purpose query engine can answer prefix queries, but not reliably in single-digit milliseconds at that rate. Purpose-built in-memory structures with precomputed answers turn each request into a pointer walk, which is why even Elasticsearch built a separate in-memory suggester rather than reusing its main index.

How do trending queries appear quickly if the trie rebuilds nightly?

Through a separate streaming path. A stream processor counts queries over minutes-long windows, detects velocity spikes against each term's baseline, and maintains a small trending set rebuilt every few minutes. The serving layer merges this set with the batch trie's results at request time, so the big structure stays immutable while fresh queries surface within minutes.

Where does typo tolerance fit into this design?

Not in the trie, which matches exact prefixes only. Practical systems get most of the value cheaply: the offline pipeline aggregates common misspellings from logs and can index them as alias entries pointing at the corrected suggestion. Full fuzzy matching per keystroke (edit-distance search over an FST) exists in engines like Elasticsearch but costs meaningful latency, so it is usually reserved for the final search, not every keystroke.

Common Designschapter 5 of 8 · 3 lessons

Search Autocomplete

Return top-k ranked suggestions for a prefix in real time (< 100ms).

← All chapters View in cheatsheet

Somebody types p, then i, then z. Between each keystroke you have about 100 milliseconds to show them five suggestions, and once the network takes its share your server has roughly 10.

Ten milliseconds rules out asking a database. It rules out ranking anything. Whatever you show has to be sitting in memory, already sorted, already chosen.

Then count the traffic. Autocomplete fires per keystroke rather than per search, so a product doing 10 million searches a day makes 60 million autocomplete requests, which is more than any other endpoint you run.

The trie gets all the attention in interviews. The constraint that actually shapes the design is those 10 milliseconds.

Lessons

3 in this chapter

Requirements and EstimationEvery keystroke is a request, so autocomplete traffic is a multiple of search traffic.3 min
The Trie and the Serving PathPrecompute the top 5 at every trie node, and a query becomes a single pointer walk in memory.3 min
The Offline Pipeline and Trending QueriesA batch job builds the trie from logs; a streaming layer keeps it honest during breaking news.3 min