Designing a Search Autocomplete System

When you type into Google, Amazon, or YouTube, suggestions appear within milliseconds. Behind that simple dropdown is a system that indexes billions of queries, ranks them by relevance and popularity, and serves results faster than you can type the next character. This post breaks down how to design one.

Requirements

Functional requirements:

• Return top 5-10 suggestions as the user types each character
• Suggestions ranked by popularity, recency, and relevance
• Support personalization (user’s recent searches)
• Handle 500 million daily search queries
• Multi-language support

Non-functional requirements:

• Response time under 50ms (p99)
• High availability (99.99%)
• Suggestions update within hours of trending changes
• Graceful degradation under load

The trie data structure

A trie (prefix tree) is the foundation of most autocomplete systems. Each node represents a character, and paths from root to marked nodes form complete words or phrases.

class TrieNode:
    def __init__(self):
        self.children: dict[str, TrieNode] = {}
        self.is_end: bool = False
        self.frequency: int = 0
        self.top_suggestions: list[tuple[str, int]] = []

class AutocompleteTrie:
    def __init__(self, max_suggestions=10):
        self.root = TrieNode()
        self.max_suggestions = max_suggestions
    
    def insert(self, phrase: str, frequency: int = 1):
        node = self.root
        for char in phrase.lower():
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.frequency += frequency
        
        # Update top suggestions for all prefix nodes
        self._update_suggestions(phrase.lower(), node.frequency)
    
    def _update_suggestions(self, phrase: str, frequency: int):
        node = self.root
        for char in phrase:
            node = node.children[char]
            # Update this node's top suggestions
            existing = [s for s in node.top_suggestions if s[0] != phrase]
            existing.append((phrase, frequency))
            existing.sort(key=lambda x: -x[1])
            node.top_suggestions = existing[:self.max_suggestions]
    
    def search(self, prefix: str) -> list[tuple[str, int]]:
        node = self.root
        for char in prefix.lower():
            if char not in node.children:
                return []
            node = node.children[char]
        return node.top_suggestions

# Usage
trie = AutocompleteTrie()
trie.insert("how to learn python", 50000)
trie.insert("how to learn javascript", 45000)
trie.insert("how to learn rust", 20000)
trie.insert("how to cook rice", 35000)
trie.insert("how to tie a tie", 30000)

results = trie.search("how to l")
# [("how to learn python", 50000),
#  ("how to learn javascript", 45000),
#  ("how to learn rust", 20000)]

Why store top suggestions at each node

The naive approach is to reach the prefix node, then do a DFS to find all completions and sort by frequency. For popular prefixes like “how”, this could mean traversing millions of nodes.

By pre-computing and storing the top K suggestions at each prefix node during insertion, lookups become O(prefix length) regardless of how many completions exist.

High-level architecture

┌───────────┐     ┌──────────────┐     ┌──────────────────┐
│  Browser  │────▶│  API Gateway │────▶│  Autocomplete    │
│           │     │  + CDN Cache │     │  Service          │
└───────────┘     └──────────────┘     └────────┬─────────┘
                                                │
                                    ┌───────────┼───────────┐
                                    ▼           ▼           ▼
                              ┌─────────┐ ┌─────────┐ ┌─────────┐
                              │  Trie   │ │  Redis  │ │  User   │
                              │  Server │ │  Cache  │ │  History│
                              │  Cluster│ │         │ │  Store  │
                              └─────────┘ └─────────┘ └─────────┘

     Data Pipeline (offline):
┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│  Query Logs  │────▶│  Aggregation │────▶│  Trie Builder│
│  (Kafka)     │     │  (Spark/     │     │              │
│              │     │   Flink)     │     │              │
└──────────────┘     └──────────────┘     └──────────────┘

Ranking suggestions

Raw frequency is not enough. A good autocomplete system considers multiple signals.

import math
from datetime import datetime, timedelta

class SuggestionRanker:
    def __init__(self):
        self.time_decay_half_life = timedelta(days=7)
    
    def score(
        self,
        query: str,
        frequency: int,
        last_searched: datetime,
        user_history: list[str] | None = None,
    ) -> float:
        # Base score from frequency (log scale to prevent domination)
        base_score = math.log10(frequency + 1) * 100
        
        # Time decay: recent queries score higher
        age = datetime.utcnow() - last_searched
        decay = 0.5 ** (age / self.time_decay_half_life)
        time_score = base_score * decay
        
        # Personalization boost
        personal_boost = 0
        if user_history:
            for past_query in user_history:
                if query.startswith(past_query) or past_query.startswith(query):
                    personal_boost += 50
                if self._same_category(query, past_query):
                    personal_boost += 20
        
        return time_score + personal_boost
    
    def _same_category(self, q1: str, q2: str) -> bool:
        categories = {
            "programming": ["python", "javascript", "react", "code"],
            "cooking": ["recipe", "cook", "bake", "food"],
        }
        for cat, keywords in categories.items():
            q1_match = any(k in q1 for k in keywords)
            q2_match = any(k in q2 for k in keywords)
            if q1_match and q2_match:
                return True
        return False

Caching strategy

Autocomplete has a perfect caching profile: a small number of popular prefixes account for most requests.

class AutocompleteCache:
    def __init__(self, redis_client):
        self.redis = redis_client
        self.ttl_popular = 3600    # 1 hour for popular prefixes
        self.ttl_normal = 300      # 5 minutes for others
        self.popular_threshold = 1000  # queries per hour
    
    async def get_suggestions(self, prefix: str) -> list[str] | None:
        cached = await self.redis.get(f"ac:{prefix}")
        if cached:
            return json.loads(cached)
        return None
    
    async def set_suggestions(
        self, prefix: str, suggestions: list[str], is_popular: bool
    ):
        ttl = self.ttl_popular if is_popular else self.ttl_normal
        await self.redis.setex(
            f"ac:{prefix}",
            ttl,
            json.dumps(suggestions)
        )
    
    async def warm_cache(self, popular_prefixes: list[str]):
        """Pre-populate cache with top prefixes."""
        for prefix in popular_prefixes:
            suggestions = await self.trie_service.search(prefix)
            await self.set_suggestions(prefix, suggestions, is_popular=True)

Browser-side caching

The client should also cache locally to avoid hitting the server for every keystroke.

class ClientAutocompleteCache {
  private cache = new Map<string, { results: string[]; timestamp: number }>();
  private ttl = 60_000; // 1 minute

  get(prefix: string): string[] | null {
    const entry = this.cache.get(prefix);
    if (!entry) return null;
    if (Date.now() - entry.timestamp > this.ttl) {
      this.cache.delete(prefix);
      return null;
    }
    return entry.results;
  }

  set(prefix: string, results: string[]): void {
    this.cache.set(prefix, { results, timestamp: Date.now() });
  }
}

Data collection pipeline

Every search query feeds back into the system to update frequencies and discover new trending terms.

from pyspark.sql import SparkSession
from pyspark.sql import functions as F

def aggregate_queries(spark: SparkSession, date: str):
    # Read raw query logs
    logs = spark.read.json(f"s3://query-logs/{date}/*.json")
    
    # Clean and normalize
    cleaned = (
        logs
        .filter(F.length("query") >= 2)
        .filter(F.length("query") <= 100)
        .withColumn("query", F.lower(F.trim(F.col("query"))))
        .filter(~F.col("query").rlike("[<>{}]"))
    )
    
    # Aggregate frequencies
    aggregated = (
        cleaned
        .groupBy("query")
        .agg(
            F.count("*").alias("frequency"),
            F.max("timestamp").alias("last_searched"),
            F.countDistinct("user_id").alias("unique_users"),
        )
        .filter(F.col("unique_users") >= 5)
    )
    
    aggregated.write.parquet(
        f"s3://aggregated-queries/{date}/",
        mode="overwrite"
    )

Update frequency

The trie cannot be rebuilt on every query. Practical systems use a tiered update strategy:

• Real-time layer: A small in-memory structure for trending queries from the last few minutes. Merged with the main trie at query time.
• Near-real-time: Aggregate queries every 15-30 minutes. Update the trie incrementally.
• Full rebuild: Rebuild the entire trie from aggregated data once per day during low traffic.

class TieredAutocomplete:
    def __init__(self):
        self.main_trie = AutocompleteTrie()      # Rebuilt daily
        self.recent_trie = AutocompleteTrie()     # Updated every 15 min
        self.trending = {}                         # Real-time counter
    
    def search(self, prefix: str, limit: int = 10) -> list[str]:
        main_results = self.main_trie.search(prefix)
        recent_results = self.recent_trie.search(prefix)
        trending_results = [
            (q, count) for q, count in self.trending.items()
            if q.startswith(prefix)
        ]
        
        # Combine and deduplicate
        all_results = {}
        for query, score in main_results:
            all_results[query] = score
        for query, score in recent_results:
            all_results[query] = all_results.get(query, 0) + score * 2
        for query, count in trending_results:
            all_results[query] = all_results.get(query, 0) + count * 5
        
        sorted_results = sorted(
            all_results.items(), key=lambda x: -x[1]
        )
        return [query for query, _ in sorted_results[:limit]]

Filtering and safety

Autocomplete systems must filter out offensive, dangerous, and legally problematic suggestions.

class SuggestionFilter:
    def __init__(self):
        self.blocked_terms = set()
        self.blocked_patterns = []
        self.load_blocklists()
    
    def filter_suggestions(self, suggestions: list[str]) -> list[str]:
        return [s for s in suggestions if self._is_safe(s)]
    
    def _is_safe(self, suggestion: str) -> bool:
        lower = suggestion.lower()
        if lower in self.blocked_terms:
            return False
        for pattern in self.blocked_patterns:
            if pattern.search(lower):
                return False
        return True

Performance optimizations

Trie sharding: Partition the trie by first character (or first two characters) across multiple servers. The prefix determines which shard to query.

Prefix pruning: Do not return results for single-character prefixes. Wait until the user types at least 2-3 characters to reduce load by 50-70%.

Request debouncing: The client should debounce requests (wait 100-200ms after the last keystroke before sending).

function useAutocomplete(debounceMs = 150) {
  const [query, setQuery] = useState("");
  const [suggestions, setSuggestions] = useState<string[]>([]);

  useEffect(() => {
    if (query.length < 2) {
      setSuggestions([]);
      return;
    }

    const timer = setTimeout(async () => {
      const cached = clientCache.get(query);
      if (cached) {
        setSuggestions(cached);
        return;
      }

      const results = await fetch(
        `/api/autocomplete?q=${encodeURIComponent(query)}`
      );
      const data = await results.json();
      clientCache.set(query, data.suggestions);
      setSuggestions(data.suggestions);
    }, debounceMs);

    return () => clearTimeout(timer);
  }, [query]);

  return { query, setQuery, suggestions };
}

The autocomplete system is a study in trade-offs: freshness vs latency, accuracy vs speed, personalization vs privacy. Start with a simple trie plus caching, measure what your users actually type, and add complexity only where the data tells you it matters.