The autocomplete must return the top 5 completions for each prefix as the user types, in under 100ms, at ~1M peak requests/sec — every keystroke is a request, so typeahead traffic runs 5-10x normal search traffic. With 250M queries/day and ~5M unique strings, the entire vocabulary fits in RAM on a single beefy node.
The core is a trie with per-node cached top-5 lists. Each node on the path from root to a term stores the 5 highest-frequency terms in its subtree. Lookup walks the prefix — O(prefix length) — and returns the node's cached list: no subtree traversal at request time. The trie is a static, read-only structure: it is rebuilt offline, not mutated online.
Rebuild pipeline: query logs (Kafka) → hourly aggregation job → counts per term → trie builder → the machine swaps the new trie into each serving node behind a pointer swap. During the swap, in-flight requests finish on the old trie; new requests read the new pointer. Serving nodes stay stateless and identical, so the machine scales typeahead by adding nodes behind a consistent-hash or DNS load balancer — cache locality is irrelevant since the whole trie is in RAM.
Data model: (term, count) pairs from aggregation, the trie itself as a compact array-of-children structure (a naive dict-per-node trie wastes 3-5x memory; a compressed representation fits 5M terms in ~1GB). Optionally a Redis cache of hot prefix → top-5 for the most common prefixes, which takes the top 20% of traffic off the trie entirely.
Bottlenecks: rebuild frequency vs. trend latency (hourly is the compromise); memory on one node (shard the trie by first character if it outgrows a node); and abusive spam prefixes (rate-limit typeahead per client, since each keystroke costs a request). Fallback: prefix not in trie returns [].
Query logs → Kafka → hourly aggregator → (term, count) → trie builder
↓
Typeahead request → LB → serving node → trie lookup → top-5 cached list → JSON
(hot prefixes served from Redis)