Every time you type a single character into Google’s search box, a timer starts. You have 50 milliseconds before the user notices lag. In that window, the system must identify the prefix you typed, find the top 10 most relevant completions out of billions of historical queries, weigh in your personal search history, inject any trending signals from the last few minutes, deduplicate near-identical suggestions, and ship a JSON payload back to your browser. Repeat this for 99,000 other users typing simultaneously.

Think of the problem like a librarian who has memorized every book request ever made, knows what’s trending on social media right now, remembers what you personally checked out last week, and still needs to answer your half-finished question in the time it takes to blink. The naive answer - just grep a query log - fails the moment you try to serve millions of users. A full-text search engine is too slow. A simple hash map can’t handle prefix matching. Even a raw trie traversal is too expensive when the tree has hundreds of millions of nodes and you need to score and rank the entire subtree on each keystroke.

Three forces are in direct tension here. Latency demands that results come from memory - no disk reads, no network hops to a single backend. Freshness demands that when “World Cup 2026” starts trending, it appears in suggestions within minutes, which means the in-memory index must be mutable. And personalization demands per-user state that cannot be shared across the cache layer without defeating the purpose of caching. A cold cache for a popular prefix will cascade into thousands of simultaneous trie traversals, which is exactly the thundering herd problem dressed in autocomplete clothes.

We need to solve for O(1) prefix lookup at query time, near-real-time trending signal injection, and per-user result re-ranking simultaneously - while keeping the primary read path under 50ms at p99.

Requirements and Constraints

Functional Requirements

• Return the top 10 completions for any search prefix typed by a user
• Completions ranked by a blend of global query frequency and personalized user history
• Trending queries from the last 5-15 minutes must appear in suggestions when relevant
• Results must be deduplicated - no near-identical suggestions (e.g., “google maps” and “google map directions” should not both appear if space is tight)
• Support at least English; architecture must be extensible to Unicode prefix matching
• Suggestions must filter out queries that violate content policy

Non-Functional Requirements

• Latency: p99 under 50ms end-to-end including network; p50 under 20ms
• Throughput: 100,000 suggestion requests per second at peak; Google processes roughly 8.5 billion searches per day, meaning autocomplete fires 3-5x more often than search submissions
• Availability: 99.99% uptime - autocomplete is on the critical user interaction path
• Freshness: Trending queries injected within 10 minutes of spike onset
• Storage: Index covers top 5 billion distinct query strings; personalization state for 4 billion active users

Constraints and Scope

• We are not building the spell-correction or query understanding layer - those are downstream
• We assume the content moderation pipeline runs asynchronously and flags are pre-applied to the index
• We assume user auth tokens are passed on the suggestion request for personalization lookups
• Geography-based trending (e.g., local trending) is out of scope for v1 but the architecture must support it

High-Level Architecture

The system decomposes into five distinct planes: a client debounce layer that throttles keypress events to reduce request volume, an API gateway handling auth and rate limiting, a suggestion service that orchestrates the read path, an in-memory trie index partitioned by prefix shard, and an async trending pipeline that continuously refreshes the index with real-time frequency scores.

On the read path, a user’s keypress fires a debounced HTTP request to the API gateway. The gateway routes the request to the correct suggestion service instance based on the first two characters of the prefix - this is the fundamental sharding unit. The suggestion service first checks a Redis cache keyed on suggest:{prefix}:{user_id} for a personalized hit, or suggest:{prefix} for the anonymous version. On a cache miss, it fans out concurrently to the trie index service (for global candidates) and the personalization service (for per-user boost signals). Results are merged, re-ranked, deduplicated, and returned. Simultaneously, every query event is published to Kafka, where a Flink streaming job aggregates 5-minute rolling windows and feeds updated frequency scores back to the trie index.

Each component has a single responsibility. The Trie Index Service holds the in-memory prefix tree and exposes a GetTopK(prefix, k) RPC. The Personalization Service reads from a user profile store and returns a map of query strings to boost multipliers. The Suggestion Service merges and ranks. The Cache Layer (Redis cluster) absorbs the read amplification. The Trending Pipeline (Kafka + Flink + Trie Updater) closes the feedback loop.

The Trie Index Service

The trie index service is the heart of the read path - its job is to take a prefix string and return the top-K globally ranked completions in microseconds, not milliseconds.

A library card catalog is the right mental model. If you ask for every book starting with “Ga”, the librarian doesn’t read every card - they walk straight to the “Ga” drawer and pull the pre-sorted top titles. The trie is that catalog, except each drawer (node) already has a pre-sorted list of the most popular entries in its entire subtree. You never need to open child drawers at query time.

The critical insight most engineers miss: a naive trie lets you find all strings with a given prefix in O(subtree_size) time. That’s unacceptable when “go” has hundreds of millions of descendant queries. The solution is cached top-K at every node. Each trie node stores not just its own query data, but a pre-merged sorted list of the top-K completions reachable from that node. When GetTopK("go", 10) arrives, we traverse 2 nodes and read the pre-computed list. O(prefix_length). No subtree traversal.