Requirements and Scale
Functional: as the user types, return top-10 completions for the current prefix in real time. Suggestions should be ranked by query frequency. Non-functional: latency < 200ms (ideally < 50ms), suggestions update within hours of trending shifts.
Scale: Assume 5B searches per day, each search triggers ~6 API calls (one per character typed). That's 30B suggestion requests/day ≈ 350K requests/sec.
Trie Data Structure
A trie is a tree where each node represents one character. Each path from root to node represents a prefix. At each node, we store the top-10 highest-frequency completions from all queries in its subtree. This allows O(L) prefix lookup where L is the length of the typed prefix.
Storing top-10 at every node avoids traversing the entire subtree on each request — the answer is pre-computed. Each node stores: character, children (26 or more for Unicode), is_end_of_word, query_count (how often this full query was searched), top_k_completions (sorted list of {query, count} pairs).
graph TD Root["Root"] --> C["c"] Root --> D["d"] C --> A["ca"] C --> U["cu"] A --> T["cat 🔵 top-10: [cat, cats, catch]"] A --> R["car 🔵 top-10: [car, care, card]"]
Updating the Trie
Updating the trie on every search would be too slow. Instead, use a two-phase approach: (1) Log all search queries to a distributed log (Kafka). (2) A MapReduce job runs periodically (hourly or daily) and counts query frequencies, then rebuilds or updates the trie in a separate "shadow" trie. (3) Swap the shadow trie to production atomically.
To weight recent searches more heavily, use Exponential Moving Average (EMA): new_count = alpha × current_count + (1 - alpha) × old_count. Alpha (e.g., 0.5) controls how fast the weight decays. This makes trending queries surface faster without over-weighting old popular queries.
Serving the Trie — Partitioning
The trie is too large for one server (billions of unique query prefixes). Partition by prefix range: one server handles 'a'-'d', another 'e'-'m', etc. This is range-based partitioning of the trie. Each partition is replicated for fault tolerance. A trie manager service knows the partition map and routes each request to the correct shard.
Cache the entire trie partition in memory (Redis or in-process) — this is the key to sub-50ms latency. The trie fits in RAM (typically a few GB per partition). On cache miss (first startup), load from persistent storage (S3 or HDFS snapshot).
Handling Special Cases
Personalization: blend global top-10 with user-specific search history. Privacy-sensitive queries: exclude from the global trie (medical, financial). Adult content filtering: maintain a blocklist of query prefixes. Multi-language support: separate tries per language/locale. Ranking signals beyond frequency: CTR (click-through rate), freshness, personalization score. All these can be blended as weighted features in a scoring function applied to the top-10 candidates.