Designing Search Autocomplete

Like explaining to a 5-year-old: When you start spelling a word and your friend finishes it for you — that’s autocomplete. But how does the computer know which words to suggest? It keeps a list of all the words people have typed before, and when you type “ca”, it looks at that list and says “lots of people typed ‘cat’, ‘car’, and ‘cake’ after ‘ca’, so let me suggest those.” The more people type a word, the higher it ranks.

Search autocomplete feels magical — as you type “how to bo”, Google instantly suggests “how to boil eggs” and “how to boost metabolism.” Underneath, it’s a real-time prefix-search problem that must answer in < 100ms while reflecting the search trends of billions of users.

Requirements

Functional

• Return top 5-10 suggestions as the user types each character
• Suggestions ranked by search frequency
• Support for trending queries (recent surge counts more)
• Personalization optional (suggestions vary by user history)

Non-Functional

• Latency: suggestions in < 100ms (ideally < 50ms)
• Scale: 10B searches/day → ~5B autocomplete calls/day (~60K/sec at peak)
• Freshness: trending topics appear in suggestions within 10-15 minutes
• Availability: 99.9% — a slow autocomplete box is very visible

The Core Data Structure: Trie

The phone tree analogy: Imagine a company’s phone directory as a tree. First you press 1 for Sales, 2 for Support… then within Sales you press 1 for East, 2 for West… You narrow down by each character. A trie works the same way: each level of the tree is one character, and following a path from root to a node spells out a word.

A trie (prefix tree) stores strings in a tree where each edge represents one character:

             root
            / | \
           c  h  w
          /   |   \
         a    o    o
        / \   |     \
       t   r  w      r
      (3) (5) |      |
           (the)    l
                    |
                    d
                   (2)

Numbers in parentheses = frequency. To find top suggestions for prefix “ca”:

1. Traverse root → c → a
2. DFS from the “a” node
3. Return the nodes with highest frequency: “car” (5), “cat” (3)

Time complexity: O(p + n) where p = prefix length, n = nodes in subtree.

Problem: for long prefixes with huge subtrees, this DFS is slow. Solution: cache top-K results at every trie node.

@dataclass
class TrieNode:
    children: dict[str, 'TrieNode'] = field(default_factory=dict)
    is_end: bool = False
    frequency: int = 0
    # Cached top-K at this node — updated on each insert
    top_suggestions: list[tuple[str, int]] = field(default_factory=list)

def get_suggestions(prefix: str) -> list[str]:
    node = root
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
    return [query for query, _ in node.top_suggestions[:5]]  # O(1) lookup!

With cached top-K at each node, suggestions are O(p) — just traverse the prefix, then read the cache.

Updating the Trie

The trie can’t be updated on every single search — that’s 60K/sec of concurrent writes to a shared data structure.

Solution: batch updates with a pipeline.

Raw search logs → Kafka → Aggregation workers → Trie update service

Aggregation worker (runs every 10 min):
  1. Count search frequencies from last batch
  2. Filter: only queries with > 5 occurrences (noise reduction)
  3. Merge with existing frequencies (decay old counts)
  4. Push top queries to Trie Update Service

Trie Update Service:
  1. Build a new trie snapshot from updated frequencies
  2. Serialize to file
  3. Push to CDN / distribute to all autocomplete servers
  4. Atomic swap: old trie → new trie (no downtime)

The trie is essentially read-only at serving time. It’s rebuilt periodically and swapped atomically.

System Architecture

User types "ca..."
        │
        ▼ HTTP GET /autocomplete?q=ca
API Gateway (with aggressive caching)
        │ cache miss
        ▼
Autocomplete Service (stateless, reads trie from memory)
        │
        ▼
In-memory Trie (loaded from S3 on startup, refreshed every 10min)
        │
        └──▶ ["car", "cat", "california", "camera", "candy"]

Meanwhile, search query logged to:
        │
        ▼
Kafka stream
        │
        ▼
Aggregation Service (counts, trends)
        │
        ▼
Trie Builder (rebuilds every 10-15 min)
        │
        ▼
S3 (trie snapshot)
        │
        ▼
Autocomplete Servers (hot-reload new trie)

Caching the Cache

The trie query itself is fast, but at 60K requests/second you still want a cache in front:

# Cache key: "autocomplete:{prefix}"
# Cache value: JSON array of suggestions
# TTL: 60 seconds

def get_suggestions_cached(prefix: str) -> list[str]:
    cache_key = f"autocomplete:{prefix.lower()[:10]}"  # truncate to 10 chars
    if cached := redis.get(cache_key):
        return json.loads(cached)

    suggestions = trie.get_suggestions(prefix)
    redis.setex(cache_key, 60, json.dumps(suggestions))
    return suggestions

Cache hit rate is very high: most users type common prefixes. Top 1K prefixes account for ~40% of all autocomplete traffic.

Trending Queries

Search trends can spike suddenly (breaking news, viral moment). The aggregation pipeline must handle this:

def calculate_score(query: str, window_counts: dict) -> float:
    # Exponential time-decay weighting
    score = 0
    for minutes_ago, count in window_counts.items():
        decay = math.exp(-0.01 * minutes_ago)  # recent = higher weight
        score += count * decay
    return score

A query with 10K searches in the last 10 minutes scores higher than one with 1M total historical searches but none recently.

Handling Scale: Partitioning

One trie server can handle ~5K req/sec. For 60K/sec:

Load Balancer
    │
    ├──▶ Autocomplete Server A (handles prefixes a-f)
    ├──▶ Autocomplete Server B (handles prefixes g-m)
    ├──▶ Autocomplete Server C (handles prefixes n-s)
    └──▶ Autocomplete Server D (handles prefixes t-z)

Each server loads only the subtrie for its prefix range — 4x smaller memory footprint.

But first-character distribution is uneven (“s” has far more queries than “x”). Better: partition by query hash % N, with all replicas holding the full trie. This distributes load evenly.

Filtering and Safety

Autocomplete can surface inappropriate, offensive, or legally sensitive content. The pipeline includes:

def is_safe_suggestion(query: str) -> bool:
    if query in BLOCKLIST:
        return False
    if any(word in query for word in SENSITIVE_WORDS):
        return False
    if PROFANITY_REGEX.search(query):
        return False
    return True

suggestions = [s for s in raw_suggestions if is_safe_suggestion(s)]

Google and Bing have entire teams dedicated to this — it’s not a solved problem.

Personalization

Global autocomplete serves the same suggestions to everyone. Personalized autocomplete blends:

• Global top suggestions (90% weight)
• User’s personal search history (10% weight)

def personalized_suggestions(prefix: str, user_id: str) -> list[str]:
    global_suggestions = get_global(prefix)[:10]
    personal_suggestions = get_from_user_history(prefix, user_id)[:5]

    # Re-rank: boost personal suggestions that overlap with global
    merged = rank_with_personal_boost(global_suggestions, personal_suggestions)
    return merged[:5]

Personal suggestions are stored per user in a small sorted set in Redis.

Trade-offs & Decisions

Decision	Choice	Reason
Data structure	Trie with cached top-K	O(prefix_length) lookup; no DFS traversal at serve time
Update strategy	Batch rebuild every 10-15 min	Avoids concurrent write contention; atomic swap = zero downtime
Freshness	Exponential decay weighting	Trending queries surface quickly without flooding out evergreen results
Partitioning	Hash-based across replicas	Even load distribution regardless of prefix letter frequency
Safety	Blocklist + regex filter	Fast; ML-based filtering runs in the offline pipeline not the hot path

---

Search autocomplete is a deceptively rich problem: it’s a data structure problem (trie), a distributed systems problem (60K/sec across many servers), a data freshness problem (trends update every 10 minutes), and a content safety problem — all at once. The trie-with-cache design is the core insight; everything else is engineering around scale.