Designing a Search Autocomplete System

Autocomplete predicts search queries as users type, providing fast and relevant suggestions.

Requirements

• Return top 5 suggestions within 100ms
• Handle 10M daily active users
• Update suggestions based on trends

Data Structure: Trie

A trie stores strings in a tree where each node represents a character prefix.

       root
      /    \
     a      b
    / \      \
   p   r      i
   |   |      |
   p   t      g

System Design

User types → API Gateway
                ↓
          Cache (Redis)
          ↓ (miss)
    Trie Service
          ↓
    Persistent Store

Trie Optimization

• Store top-K frequent searches at each node to avoid full traversal
• Compress nodes with single children (Patricia trie)

Data Collection

1. Log all user searches with frequency
2. Batch process (daily) to update trie weights
3. For trending topics, use streaming (Kafka + Flink)

Caching Strategy

Cache responses by prefix:

Redis: GET autocomplete:"app" → ["apple", "application", "app store"]

Cache hit rate: ~90% for common prefixes.

Scaling

• Shard trie by first 2 characters
• Replicate for read scalability

Conclusion

Autocomplete is a read-heavy system. Trie with prefix caching and async updates provides sub-100ms suggestions at scale.