Typeahead / autocomplete

Product surface

• Real-time suggestions as user types
• Top K suggestions (e.g., 10 per keystroke)
• Personalized suggestions based on user history
• Support trending queries and recency
• Multi-language and Unicode support
• Filter inappropriate suggestions

Scale targets

• Latency <100ms (p99)
• 5B searches/day
• 10 suggestions per keystroke
• High availability 99.99%
• Handle 10M+ unique query prefixes

Prefix Tree

A trie groups strings by shared prefixes. Inserting “car”, “card”, and “cat” creates a shared path for “ca”, then separate branches. To answer “ca”, follow two character transitions and read a precomputed list of its best completions. Without that list, the service would have to explore the entire subtree and rank all matching strings on every keystroke.

With bounded transition lookup and precomputed lists, traversal takes O(prefix length), followed by O(K) to return K suggestions. Storing K suggestions at every node improves reads but duplicates suggestion references throughout the index. Account for that memory cost, and use sparse child maps or compressed paths where most possible characters are absent.

struct TrieNode {
  children: Map<char, TrieNode>
  isEnd: bool
  frequency: int
  topSuggestions: List<Suggestion>
}

Memory Optimization

Flow

Search queries → aggregate frequency → update trie offline. Do NOT update trie on every query (too slow). Batch with MapReduce.

• Log search queries to stream log
• MapReduce: aggregate (query, count) per day
• Trie Builder: rebuild trie from aggregated data
• Deploy new trie every N hours (e.g., 6–24h)

Why Offline

Offline rebuilding is a choice for predictable serving latency, not a claim that tries cannot be updated online. A query event can change counts for many prefixes and force their top-K lists to be recomputed. Aggregating these events into a new immutable index separates that work from user requests and makes rollback straightforward.

For example, publish a full index every six hours and keep a small streaming overlay for fast-moving trends. Merge the overlay with the base index at read time. This gives popular breaking queries a path into suggestions without continuously mutating the entire serving structure.

Factors

• Frequency: how often query was searched
• Recency: recent queries boost
• Personalization: user history overlay
• Trending: spike in last hour/day
• Location: geo-specific suggestions

Implementation

Compute global suggestion scores from normalized frequency and recency, then keep a larger candidate set than the final ten suggestions. At request time, merge a bounded set of personal-history and trending candidates, deduplicate them, filter policy violations, and select the final K. Keeping exactly K before filtering can produce a short or empty list when several candidates are removed. Evaluate ranking changes by locale and prefix length, because an overall click-through increase can hide worse behavior for smaller languages.

Offline Pipeline

Query logs → stream log → MapReduce → Trie Builder → Deploy to Typeahead servers. Blue-green deployment for zero-downtime trie updates.

Prefix Range

Shard by first char: a-f on server 1, g-m on server 2, n-s on server 3, t-z on server 4. Client or LB routes by prefix.

Consistent Hashing

Hashing materialized prefix records can distribute ownership more evenly than assigning the entire letter “s” to one server. A record maps a normalized prefix and locale to a precomputed suggestion list, so the query routes to one shard. This is different from hashing complete query strings: the completions for “ca” would then be spread across many shards and require a fan-out query. Hot prefixes still need replication or caching because hashing cannot divide one record’s traffic.

Browser

Cache the global result under the normalized prefix, locale, index version, and any other input that changes its contents. Choose a TTL from freshness requirements; one hour may suit stable catalog names but miss a rapidly emerging news query. Browser history-based suggestions contain personal data and should use private storage and clear retention rules rather than shared HTTP caches.

Content Delivery Network (CDN)

Cache popular prefixes at edge. Cache at multiple prefix lengths (1, 2, 3+ chars).

Application

in-memory cache store for hot prefixes. Trie is already in-memory; in-memory cache store for personalization overlay.

Unicode Trie

Use Unicode code points for children. Support CJK, emoji, etc. Separate tries per language or unified with language tag.

Personalization

User history overlay: merge trie suggestions with user:{user_id} recent queries from in-memory cache store. Boost user's past queries. A/B test personalization weights.