Design a Search Autocomplete System

Design a real-time search autocomplete feature like Google's search bar. As the user types, show the top 5 matching suggestions within 100ms. Suggestions should be ranked by query popularity.

Capacity Estimation

• Read QPS: 100M users × 10 keystrokes × 10 searches/day / 86400 = ~115K QPS (suggestions)
• Write QPS: 1B queries/day / 86400 = ~11.5K QPS (query log events)
• Trie size: top 10M queries × avg 30 chars = ~1.5 GB — fits in memory
• Cache: prefix cache. Most traffic is top 10K prefixes — fit in Redis (<1 GB)

Architecture

[User types in search box]
        ↓ (every keystroke, debounced 100ms)
[Autocomplete API]
        │
        ├── Redis Cache ──→ HIT: return cached top-5
        │
        └── MISS: query Trie Service
                    │
              [Trie Service] → in-memory Trie
                    │
             top-5 → cache in Redis (TTL: 1 hour)
                    │
               return to client

[Background]
[Query Logger] → Kafka → [Frequency Aggregator]
                                    │
                            hourly batch → update Trie weights

Why a Trie beats naive substring search at scale

A naive approach — scanning every stored query string to check if it starts with the user's typed prefix — is O(n * m) per keystroke (n = number of stored strings, m = average string length), and gets slower as the dataset grows, with no way to bound latency as query volume scales. A Trie makes prefix lookup O(m) — proportional only to the LENGTH of the typed prefix, completely independent of how many total strings are stored — because each character typed simply walks one level deeper into the tree structure, arriving at the relevant subtree directly rather than scanning anything. This is exactly why sub-100ms autocomplete latency at scale is achievable with a Trie and effectively impossible with naive substring scanning once the dataset is large.

API Design

GET /autocomplete?q=java&limit=5&userId=optional

Response:
{
  "suggestions": [
    { "text": "java interview questions", "frequency": 1500000 },
    { "text": "java stream api",          "frequency": 980000 },
    { "text": "java 21 features",         "frequency": 750000 },
    { "text": "java concurrency",         "frequency": 680000 },
    { "text": "java spring boot",         "frequency": 590000 }
  ]
}

Trie Data Structure

Root
  └── 'j'
       └── 'a'
            └── 'v'
                 └── 'a'  ← TrieNode { topSuggestions: ["java interview...", "java stream api", ...] }
                      ├── ' '  → 'i' → 'n' → ...
                      └── 's'  → 'c' → ...

Optimisation: store top-K suggestions at each node to avoid traversal on read:

class TrieNode {
    Map<Character, TrieNode> children;
    List<Suggestion> topK; // pre-computed top-5 at this node
}

This makes read O(P) where P = prefix length (not O(subtree size)).

Storage: Serialize trie to disk (protobuf). Load into memory on service start.

Scaling Strategy

Trie updates (write path)

We cannot lock and rebuild the trie on every query. Strategy:

1. Log raw queries to Kafka
2. Hourly batch job aggregates query frequencies
3. Rebuild trie from scratch weekly with full dataset; apply incremental updates hourly
4. Blue-green trie swap: build new trie in background, swap atomically

Cache strategy

Top-K prefixes by request volume are cached in Redis with a 1-hour TTL. The top 1000 prefixes serve 80% of traffic — these fit in <10 MB of Redis.

Sharding the trie

If trie is too large for one node: partition by first character (26 shards, or by first 2 characters for 676 shards). Route prefix to correct shard.

• Pre-computed top-K vs dynamic traversal: pre-computing top-K at each node makes reads O(prefix length) but makes updates O(n) when a query's rank changes. The hourly batch update is the right tradeoff.
• Global vs personalized: global suggestions are simple; personalized requires user query history lookup on every keystroke (adds ~20ms latency). Use global as base + rerank with user recency signal.
• Trie vs inverted index: Tries are optimised for prefix matching; inverted indexes (Elasticsearch) support fuzzy search but add latency. Tries win for autocomplete latency requirements.

• Trie rebuild: takes ~5 minutes for 10M queries. Blue-green swap hides this.
• Cache invalidation: when a query trends (COVID, World Cup), cache becomes stale in minutes. Solution: streaming aggregation with Flink updates the trie incrementally.
• Hot prefix: 'a' is prefixed by millions of queries. Cache aggressively; pre-warm on deploy.

• Trie Service down: fall back to cached suggestions only. 95%+ of traffic served from Redis cache anyway.
• Redis down: fall back to Trie Service directly. Latency increases from <5ms to ~30ms — acceptable.
• Bad trie data: version trie snapshots. Roll back to previous hourly snapshot on detection.