Picture a public library reference desk staffed by two librarians simultaneously. The first librarian has memorized every question ever asked in every branch across the country and can rank topics by global popularity. The second knows only you - every title you have ever requested, which you finished, which you abandoned, and how long ago. When you begin a question with “py…”, the first librarian is already pulling “Python”, “PyTorch”, and “Python Tutorial” from the national frequency list. The second is whispering “you searched python dataclasses three times last week, put that first.” The challenge is that both librarians must finish arguing and hand you a unified answer in 50 milliseconds - before you type the third character.

That is the personalized typeahead problem. It is harder than standard autocomplete because the same two-character prefix must produce different ranked results for a machine-learning engineer, a Python beginner, and someone who has never typed “py” before. The trie index that drives global suggestions is shared and cacheable. Personal signals are per-user and cannot be cached at the prefix layer without multiplying cache storage by the number of users. Trending queries spike without warning and must appear in suggestions within minutes. All three signals must converge into a single ranked list under a 50ms budget that includes network round-trip time.

Three forces pull in opposite directions. Caching wants to serve the same result for every “py” query regardless of who is asking. Personalization wants to serve different results for every user. Freshness wants to update those results whenever a query spikes in volume. A system that optimizes for any one of these forces at the expense of the others will fail the product requirements. We need to design around all three simultaneously.

Requirements and Constraints

Functional Requirements

• Return the top 10 search suggestions for any typed prefix starting at 2 characters
• The same prefix must return different ranked results for different users based on their search history
• Globally trending queries from the last 5-15 minutes must appear in suggestions when relevant to the prefix
• Support cold-start users who have no personal history - fall back to segment-level preferences
• Support A/B testing of ranking algorithms per user cohort without affecting the core index
• All suggestions must pass a content policy blocklist check before returning

Non-Functional Requirements

• Latency: p99 under 50ms end-to-end including network; p50 under 15ms
• Throughput: 150,000 suggestion requests per second at peak (3-5x the actual search submission rate)
• Availability: 99.99% - typeahead is on the critical interaction path; failure causes perceived slowness even when search itself is up
• Freshness: trending queries must appear in suggestions within 10 minutes of onset; index rebuilds every 24 hours for global scores
• Storage: global index covers 5 billion distinct query strings; personalization state for up to 2 billion active users with up to 500 stored prefixes each

Constraints and Scope

• We are not building spell-correction or semantic intent understanding - those are downstream of suggestions
• Content moderation runs asynchronously; flags are pre-applied to the index and to a real-time Redis blocklist
• User auth tokens arrive on the suggestion request and are used for personalization lookups
• Geographic trending (regional hot queries) is a future extension; architecture must not preclude it

High-Level Architecture

The system has five distinct planes: a client debounce layer that converts keystrokes into throttled HTTP requests, an API gateway for auth and prefix-based routing, a suggestion blender that orchestrates the read path, a prefix cache per user segment that absorbs repeat traffic, and an async trending pipeline that continuously injects freshness signals.

On the read path, a keypress fires a debounced request to the API gateway after 120ms of idle time. The gateway authenticates the user, extracts the prefix, and routes to the correct trie shard based on hash(prefix[0:2]) % num_shards. The Suggestion Blender checks Redis for a cached result keyed by suggest:{prefix}:{user_segment} - a segment-level cache that provides partial personalization without per-user cache explosion. On a miss, the Blender fans out in parallel to the Trie Index Service (global top-50 candidates) and the Personalization Service (user history from Cassandra). The two result sets are merged using decay-weighted scoring, trending boosts are injected from a Redis Sorted Set, the blocklist is checked, and the top-10 are returned. Simultaneously, the query event is published to Kafka for the trending pipeline.

Each service has a single responsibility. The Trie Index Service holds the in-memory prefix tree and returns GetTopK(prefix, 50). The Personalization Service returns a map of {query_text: decay_score} for a given user. The Suggestion Blender does all the merging. The Trending Pipeline (Kafka + Flink + Trie Updater) closes the feedback loop and keeps the index fresh.

The Trie Index Service

The Trie Index Service is responsible for returning the top-50 globally scored completion candidates for any prefix in under 2ms. It is the foundation that both the cached path and the cache-miss path build on.

Think of it like a pre-printed phone book index with thumbtabs. When you flip to “Py”, you instantly see the 50 most-called numbers starting with “Py” - you do not need to scan the full “P” section. The trie achieves this by caching pre-computed top-K lists at every internal node, not just at leaf nodes. When GetTopK("py", 50) arrives, the service traverses 2 trie nodes and reads the cached list. O(prefix_length) time, no subtree traversal.