The Latency SLA of Autocomplete
Search autocomplete (typeahead) displays the top 5 to 10 suggested queries as the user types each keystroke. Because humans type at ~300ms intervals, suggestions should appear within roughly 100 milliseconds of a keystroke end to end, which leaves the server-side lookup a budget well under 10 ms because network round trips dominate.
Prefix Trie with Pre-Materialized Top-K Suggestions
Under the Hood: Why Naive Tries Fail at Scale
In a textbook Trie, finding matching prefixes requires traversing down to the prefix node and performing a Depth-First Search (DFS) across all descendant nodes to find the highest-frequency suggestions. In a dictionary with 100,000,000 query logs, this DFS takes hundreds of milliseconds.
The Pre-Materialization Pattern: Each Trie node pre-computes and caches the top 5 most popular global search phrases in its node payload. Querying autocomplete traverses the analyzed prefix in O(|prefix|) and then returns a bounded precomputed list. Network and serving latency must be measured; the lookup is not globally constant-time.
Offline Aggregation Pipeline
Search query click logs are streamed to Kafka and aggregated hourly via Apache Flink. Flink calculates weekly query frequency, filters offensive terms, and builds a fresh immutable Trie file. The new Trie is deployed to production Redis instances or local worker memory using zero-downtime pointer swaps.
Worked example: capacity estimate
| Quantity | Assumption | Result |
|---|---|---|
| Searches per day | 5 billion | |
| Suggestion requests per search | About 4 after client-side debouncing of 100 to 150 ms | 20 billion per day |
| Average QPS | 20 billion divided by 86,400 | about 230,000 |
| Peak QPS | 2 to 3 times average | about 500,000 to 700,000 |
| Suggestion index | Top 10 million queries, about 50 million distinct prefixes, about 60 bytes each for key and 10 IDs | about 3 GB, fits in RAM on every server |
Because the whole index fits in memory, each server can hold a full replica and scale horizontally; sharding by prefix is only needed when the index grows much larger or is personalised.
Latency: what actually matters
Users perceive suggestions as instant if they appear within roughly 100 ms of a keystroke. Server lookup is microseconds; the budget is dominated by network round trip. Tactics: serve from the nearest region or edge, cache short prefixes (one or two characters) at the CDN and in the browser, reuse a persistent HTTP/2 connection, and cancel in-flight requests when a new keystroke arrives.
Data pipeline
Trade-offs
| Choice | Benefit | Cost |
|---|---|---|
| Hourly rebuild | Simple, consistent | Misses breaking news for up to an hour |
| Streaming trending layer | Fresh suggestions within minutes | Needs a merge of trending and base lists; abuse risk |
| Personalised suggestions | Higher acceptance rate | Per-user state, privacy obligations |
| Minimum frequency threshold | Blocks rare, possibly private queries | Long-tail coverage drops |
Failure modes
- Manipulation: bots repeatedly searching a phrase to push it into suggestions; count distinct users, not raw searches.
- Stale snapshot: if a build fails, keep serving the previous version rather than an empty index.
- Tail prefixes: prefixes with no precomputed list should return nothing quickly rather than falling back to an expensive scan.