System Design : Search Autocomplete at Scale

You type “face” into Google’s search box.

Before your finger leaves the keyboard, you already see: “Facebook,” “facial recognition,” “face masks.” In under 50 milliseconds. Across billions of concurrent users. With suggestions ranked by your personal search history, regional trends, and global query frequency , all updated continuously.

This is not a simple feature. It is one of the more interesting system design problems because it combines an elegant data structure (the Trie) with a real-time serving challenge (sub-50ms globally) and a data freshness problem (how do suggestions update when a news story breaks?).

The reason this appears in senior interviews is that it has a clear probe , the Trie data structure and its distributed form , and it reveals whether candidates understand read-heavy system optimization, pre-computation, and the latency constraints of real-time user interaction.

This post covers the complete design , from the Trie data structure to the distributed serving layer, the Kafka aggregation pipeline, CDN prefix caching, and the one decision that makes the difference between a “hire” and a “strong hire” answer.

Functional requirements:

• Return top 5 suggestions as the user types each character

• Suggestions ranked by query frequency and recency

• Suggestions updated as search trends change

• Support filtering , no offensive or banned suggestions

• Handle multiple languages and regional trends

Non-functional requirements:

• Latency under 50ms end-to-end

• Highly available , suggestions failing is not catastrophic but visibility matters

• Eventual consistency is acceptable , suggestions can lag by hours

• Read-heavy by a large margin , billions of queries per day, writes are aggregated offline

Scale:

Daily active users:        1 billion
Queries per day:           10 billion (10 avg per user)
Peak QPS:                  ~120,000 queries/sec
Distinct popular queries:  ~100 million
Average query length:      ~20 characters
Suggestions per response:  5
Target latency:            < 50ms (CDN hit < 10ms)

The number that shapes the design: assume around 100 million distinct popular query strings, averaging about 20 characters. A trie with a small top-K cached per node lands in the range of a few to tens of gigabytes - large, but RAM-resident on the serving tier, and split across shards if one machine cannot hold it.

The critical read:write insight: users query autocomplete on every keystroke. A user typing “facebook” generates 8 queries - “f”, “fa”, “fac”, “face”, “faceb”, “facebo”, “faceboo”, “facebook”. Write updates happen offline in batch. This is an extremely read-heavy system. Optimize reads above everything else.

A trie is a tree-like data structure. The root represents an empty string. Each node stores a character and has 26 children, one for each possible character. Each tree node represents a single word or a prefix string.

Here is why the Trie is the natural structure for autocomplete and not a hash map or a database:

With a hash map, you could store "facebook" → 9.2B searches. But to find all queries starting with “face”, you would need to scan every key in the map. At 100 million entries, that is too slow.

With a Trie, all queries sharing a prefix share the path from the root to that prefix node. Finding everything that starts with “face” means walking root → f → a → c → e - four steps regardless of how many queries the trie holds - then reading everything in the subtree below.

The walk from root to “face” costs exactly 4 steps , one per character in the prefix. Query time is O(len(prefix)) ,just traverse down the trie.