13 - Design a Search Autocomplete

🎁 You've typed three characters and the search box already shows suggestions. The system checked billions of possible completions in under 50 milliseconds. How?

Search autocomplete (typeahead) suggests completions as a user types. "sys" becomes "system design", "system design interview", "system design practice". It must respond in under 100ms (faster than the user types the next character) and surface the most relevant suggestions from billions of past searches.

Search Autocomplete Requirements

Search Autocomplete Functional Requirements

• Return top 5-10 suggestions as the user types each character
• Rank suggestions by popularity (most searched terms first)
• Update suggestions based on trending searches
• Support personalization (user's own search history)

Search Autocomplete Non-Functional Requirements

Search Autocomplete Scope Exclusions

• Full search results (autocomplete only suggests, does not return results)
• Spell correction and typo handling
• Image or product search suggestions

Search Autocomplete Estimation

• Every keystroke from every user → 350K queries/sec
• 5B unique terms × ~20 bytes average = ~100 GB trie (fits in memory)
• Must respond in < 100ms (faster than the user types the next character)

Extreme read QPS but small dataset. In-memory serving is the only option at this latency.

Search Autocomplete High-Level Design

┌────────────────────────────────────────────────────────────────┐
│                    SEARCH AUTOCOMPLETE                         │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  ┌──────────┐     ┌──────────────┐     ┌──────────────────┐    │
│  │  User    │────►│  API Server  │────►│  Trie Service    │    │
│  │  types   │◄────│              │◄────│  (in-memory)     │    │
│  │  "sys"   │     └──────────────┘     │                  │    │
│  └──────────┘                          │  prefix → top-K  │    │
│                                        │  suggestions     │    │
│                                        └────────┬─────────┘    │
│                                                 │              │
│                                                 ▲ (rebuilt     │
│                                                 │  every 15min)│
│                                                 │              │
│  ┌──────────────┐     ┌──────────────┐         │               │
│  │  Search Logs │────►│  Aggregation │─────────┘               │
│  │  (Kafka)     │     │  Service     │                         │
│  └──────────────┘     │  (count by   │                         │
│                       │   prefix)    │                         │
│                       └──────────────┘                         │
└────────────────────────────────────────────────────────────────┘

Two paths:

• Read path (fast): User types → API → Trie lookup → return top-K suggestions (< 100ms)
• Update path (slow): Search logs → aggregate counts → rebuild trie every 15 minutes

Search Autocomplete Deep Dive

Trie Data Structure

A trie (pronounced "try", from retrieval) is a prefix tree that stores strings character by character. Each node represents a prefix:

         root
        / | \
       s   b   ...
      /
     y
    /
   s    ← prefix "sys"
  / \
 t    ...
 |
 e
 |
 m   ← "system" (frequency: 50,000)

Why a trie? Given prefix "sys", traverse to that node and return the top-K most popular completions below it. This is O(prefix_length) to find the node, not O(total_terms).

Optimization: Store top-K at each node. Instead of traversing all children to find the most popular, precompute and cache the top 10 suggestions at every node. Lookup becomes O(prefix_length) with no subtree traversal.

Trie vs Database

SELECT term FROM searches WHERE term LIKE 'sys%' ORDER BY frequency DESC LIMIT 10;

This works at small scale but fails at 350K QPS:

• LIKE with prefix is a range scan, slow on billions of rows
• Can't serve in < 100ms at this QPS from disk
• The trie is in-memory, sub-millisecond lookups

Trie Rebuild Strategy

Updating the trie on every search would require locking (slow). Instead:

1. Log every search to Kafka
2. Aggregation service counts searches per term in 15-minute windows
3. Build a new trie from aggregated data
4. Swap the old trie for the new one atomically (pointer swap)

The trie is immutable during serving. No locks, no contention, maximum read speed.

Caching Layers

Browser cache → CDN → Trie Service

1. Browser: cache "sys" results for 1 hour (user types same prefixes often)
2. CDN: cache short prefixes (1-2 chars) at edge, massive hit rate
3. Trie Service: in-memory trie handles cache misses

Short prefixes ("s", "sy") are queried by everyone, perfect for CDN caching. Longer prefixes are more diverse and served from the trie directly.

Trending and Freshness

A breaking news event should surface in autocomplete within minutes:

• Weight recent searches higher (exponential time decay)
• Half-life of ~3 days: a term trending today dominates; last week's trend fades
• Rebuild every 15 minutes picks up new trends quickly

Key Takeaways

• Tries give O(prefix_length) lookup, independent of dataset size

  5 billion terms, but finding suggestions for "sys" only traverses 3 nodes. Precomputed top-K at each node eliminates subtree scanning.

• Separate the read path from the update path

  Reads hit an immutable in-memory trie (fast, no locks). Updates happen offline: aggregate, rebuild, swap. Never modify the serving trie in place.

• Multi-layer caching handles 350K QPS

  Browser cache (0ms), CDN for popular prefixes (<10ms), in-memory trie for the rest (<50ms). Most requests never reach the trie service.

• Time decay keeps suggestions fresh

  Weight recent searches exponentially higher. Rebuild every 15 minutes. Trending terms rise quickly; stale terms fade naturally.

Want the full design? The example "Search Autocomplete at Scale" covers trie sharding by prefix range, personalization, multi-language support, and filtering offensive suggestions.

🎁 Fifty thousand physical sensors report occupancy changes every second. How do you turn raw hardware signals into a real-time "find parking near me" experience?