Why architecture matters here
Start with the arithmetic that kills the naive design. A search box with 50,000 queries per second becomes 500,000 typeahead requests per second once every keystroke fires one. Serving those from the primary search engine — even a fast one — is a self-inflicted denial of service: a LIKE 'prefix%' against a database or a prefix query against the full search index costs milliseconds to tens of milliseconds each, multiplied by ten times the traffic. The systems that work treat typeahead as its own service with its own index, sized to answer in microseconds, and treat the search engine as something typeahead protects rather than uses.
The latency budget dictates the memory hierarchy. One hundred milliseconds end to end sounds generous until you subtract mobile network round-trip (40-60 ms on a good day), TLS, and client rendering: the service has perhaps 5-10 ms, which rules out disk and rules out fan-out to multiple backends in sequence. Everything the common path touches must be in local RAM. That constraint is also a gift — a well-compressed suggestion index for hundreds of millions of candidates fits in a few gigabytes, so full replication is cheap and every server can answer any query its shard owns without cross-node hops.
Finally, the quality bar shapes the offline system. Suggestion quality is measured in suggestion click-through rate and characters-saved, and it moves the business: users who click a suggestion search more and misspell less. Getting quality right requires mining real query logs (what do people actually type), aggressive normalization and deduplication (casing, whitespace, near-duplicates), spam and bot filtering so a scripted flood cannot manufacture a suggestion, and a scoring model that balances raw frequency against recency and result quality. All of that runs offline, at leisure, in the pipeline — which is why the pipeline, not the server, is where most of the engineering lives.
The architecture: every piece explained
The candidate miner consumes the query-log stream and produces the candidate set: normalized queries with enough volume from enough distinct users to be worth suggesting. Normalization collapses case, punctuation, and whitespace variants; frequency floors and per-user caps stop bots and power users from minting candidates; a language classifier routes candidates to per-locale indexes. The scorer then assigns each candidate a static score — a blend of smoothed historical frequency, recency-weighted trend, and downstream result quality (a query whose results users bounce off gets demoted). The blocklist service applies policy: hate speech, harassment patterns, legally-mandated removals, and per-market rules, evaluated both at build time (drop the candidate) and serve time (belt and suspenders for new rules that cannot wait for a rebuild).
The index builder compiles scored candidates into the serving structure. The classic choice is a finite-state transducer — the same structure Lucene uses for its suggesters — which shares prefixes and suffixes for extreme compression and supports weighted traversal. The crucial addition is precomputation: at each prefix node, the builder stores the top-k highest-scored completions reachable from that node, so serving never walks the subtree. The cost is index size (each node carries k pointers) and rebuild time; the payoff is O(prefix length) lookups with zero variance. Builds emit immutable, versioned snapshots to the index store; servers load the new snapshot beside the old, warm it, and atomically swap — there is no in-place mutation anywhere in the serving path.
Serving is prefix-sharded: the keyspace of first-one-to-two characters is partitioned across server groups so each group holds a fraction of the index in RAM with full replicas for load. In front, an edge cache absorbs the enormously skewed head — the top few thousand prefixes cover a huge share of traffic and their responses are identical for all anonymous users, making them ideal CDN material with TTLs of seconds to minutes. Behind, the rerank layer is where personalization lives: it takes the ten to fifty precomputed candidates and reorders them with per-user features — your own recent queries first, your locale's entities boosted — plus trending-pipeline boosts computed over minutes-old logs for breaking terms. Rerank touches only the short list, so its cost is bounded no matter how fancy the model gets.
End-to-end flow
A user types "mach" into the search box. The client debounces — it fires after a short pause in typing rather than on literally every character — attaches the user's session context, and cancels the still-in-flight request for "mac", because rendering stale suggestions after fresher ones is the classic typeahead UI bug. The request hits the edge: for an anonymous user, "mach" is a hot prefix and the CDN answers in one round trip. For our signed-in user, personalization bypasses the shared cache and the request lands on the prefix shard that owns m.
The shard server maps the request to its mmapped FST, walks four arcs — m-a-c-h — and arrives at the prefix node, where the top-50 completions were precomputed at build time: machine learning, machu picchu, machine gun kelly, and so on, each with its static score. The walk plus the read is microseconds. The server applies serve-time blocklist rules to the list, merges any trending boosts for this prefix (a news event an hour ago pushed a new term into the boost table), and hands the candidates to the rerank layer with the user's feature vector. Rerank sees that this user searched machine learning deployment twice this week, lifts it to position one, and returns the final ten.
The response — ten strings and display metadata, a few hundred bytes — travels back and renders in well under the 100 ms budget; the user sees their likely query before typing the fifth character, arrows down, and hits enter, having typed four characters for a 27-character query. Meanwhile, in the background, the interaction itself becomes training data: the impression and the click flow into the query logs, the candidate miner will count them tonight, and tomorrow's index build will know that machine learning deployment earned its click. The loop from user behavior to ranking closes in hours through the batch pipeline and in minutes through the trending pipeline.
The flow's defining property is that its cost is invariant to corpus size: whether the index holds one million candidates or five hundred million, the request performed four arc traversals, one list read, one bounded rerank. Everything that scales with the corpus — mining, scoring, building — happened offline, hours before the keystroke, on batch infrastructure that can be slow, cheap, and retried without any user noticing.