Search Autocomplete at Scale

Step 1: Search Autocomplete Requirements

Search Autocomplete Functional Requirements

• Return top 5 suggestions as the user types each character
• Suggestions ranked by popularity (search frequency)
• Support prefix matching: typing "sys" returns "system design", "system architecture", etc.
• Update suggestions based on new searches (trending terms surface quickly)
• Support multi-language queries

Search Autocomplete Non-Functional Requirements

• Scale: 5 billion searches per day
• Latency: Suggestions appear within 100ms of keystroke
• Throughput: Handle 100K QPS for autocomplete requests
• Consistency: Eventual, new trending terms appear within 15 minutes
• Availability: 99.99% uptime (users expect instant suggestions always)
• Storage: Efficiently store millions of unique query prefixes

Step 2: Search Autocomplete Estimation

QPS Calculation

• 5B searches/day → ~58K searches/second
• Each search averages 6 keystrokes before selection → 6 autocomplete requests per search
• Autocomplete QPS: 58K × 6 = ~350K QPS (peak: ~600K QPS)
• With browser-side debouncing (50ms), effective QPS drops to ~200K

Search Autocomplete Storage

• Assume 5M unique prefixes stored in the trie
• Average prefix length: 15 characters = 15 bytes
• Each node stores top-5 suggestion pointers: 5 × 8 bytes = 40 bytes
• Metadata per node (frequency, timestamp): ~20 bytes
• Per prefix: ~75 bytes
• Total trie size: 5M × 75 bytes = ~375 MB (fits in memory!)

Search Autocomplete Bandwidth

• Each response: 5 suggestions × 50 chars average = 250 bytes + overhead ≈ 500 bytes
• Bandwidth: 350K QPS × 500 bytes = 175 MB/s outbound

Step 3: Search Autocomplete High-Level Design

Architecture Overview

┌─────────────────────────────────────────────────────────────────────┐
│                         READ PATH (fast)                            │
│                                                                     │
│  Client ──→ CDN Cache ──→ API Gateway ──→ Autocomplete Service      │
│   (browser      (popular       (rate         (in-memory trie)       │
│    cache)        prefixes)      limiting)                           │
└─────────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────┐
│                        WRITE PATH (batch/offline)                   │
│                                                                     │
│  Search Logs ──→ Data Collection ──→ Aggregation ──→ Trie Builder   │
│   (Kafka)         Service             Pipeline        (offline)     │
│                                       (Spark/Flink)       │         │
│                                                           ▼         │
│                                                     Trie Snapshot   │
│                                                     (distributed    │
│                                                      to servers)    │
└─────────────────────────────────────────────────────────────────────┘

Key Design Decisions

• Read/write separation: Reads served from in-memory trie (fast); writes batched offline
• No real-time trie updates: Trie rebuilt every 15 minutes from aggregated data
• CDN caching: Popular prefixes (single characters, common 2-letter combos) cached at edge
• Browser caching: Recent user queries cached locally with short TTL (5 min)

Step 4: Search Autocomplete Deep Dive

4.1 Trie Data Structure

The core data structure is a prefix tree (trie) where:

• Each node represents a character in the prefix
• Each node stores the top-K results (precomputed) for that prefix
• Leaf nodes aren't special. Every node along the path has suggestions

Root
├── s
│   ├── y → [system design, system architecture, sync, ...]
│   │   └── s → [system design, system architecture, system call, ...]
│   └── v → [svelte, sveltekit, svg, ...]
├── g
│   └── o → [golang, google, go concurrency, ...]

Storing top-K at each node avoids traversing subtrees at query time → O(prefix_length) lookup.

4.2 Trie Building (Offline Pipeline)

Search Logs → Kafka → Flink Aggregation → Frequency Map → Trie Builder → Snapshot
                         (15-min windows)

1. Collect: Search queries stream into Kafka topics
2. Aggregate: Flink job computes frequency counts in 15-minute tumbling windows
3. Merge: Combine with historical frequencies (apply time decay)
4. Build: Construct new trie with updated top-K at each node
5. Deploy: Serialize trie → distribute snapshot to all autocomplete servers
6. Swap: Servers load new trie in background, atomic pointer swap (zero downtime)

4.3 Ranking with Time Decay

Raw frequency isn't enough. "super bowl" shouldn't rank #1 in July.

Exponential decay formula:

score(query) = Σ frequency_i × decay^(t_now - t_i)

• decay = 0.99 (per hour), halves roughly every 3 days
• Recent searches weighted exponentially higher
• Trending terms rise fast; stale terms fade naturally

Blended score:

final_score = 0.7 × global_popularity + 0.2 × trending_boost + 0.1 × personalization

4.4 Multi-Layer Caching

• Single-character prefixes ("a", "b", ...) account for huge traffic, perfect for CDN
• Browser caching eliminates repeated requests for same prefix within session
• Combined hit rate before reaching app servers: ~50%

4.5 Sharding the Trie

When the trie exceeds single-server memory or QPS capacity:

Shard by prefix range:

• Shard 1: prefixes starting with a-f
• Shard 2: prefixes starting with g-m
• Shard 3: prefixes starting with n-s
• Shard 4: prefixes starting with t-z

Considerations:

• Uneven distribution (more queries start with 's' than 'x')
• Use consistent hashing on first 2 characters for better balance
• Each shard replicated 3× for availability
• API gateway routes to correct shard based on query prefix

4.6 Filtering Inappropriate Content

• Maintain a blocklist of offensive terms (checked during trie build)
• ML classifier flags potentially harmful suggestions before they enter the trie
• Manual review queue for borderline cases
• Country-specific filtering (legal compliance)
• Filter applied at build time (not query time) to keep reads fast

4.7 Personalization

Blend global suggestions with user-specific signals:

• User's recent searches: Boost queries the user searched before
• User's location: "pizza" → "pizza near me" for mobile users
• User's language: Prefer suggestions matching user's locale
• Implementation: Small per-user cache (last 100 searches) stored in Redis
• Personalized re-ranking happens at query time on top of global top-K

Key Takeaways

• Separate read and write paths: reads must be sub-100ms (in-memory trie), writes can be batched offline every 15 minutes
• Precompute top-K at each trie node: eliminates expensive subtree traversal at query time, giving O(prefix_length) lookups
• Time-decay ranking prevents stale queries from dominating. Trending terms surface quickly while old terms fade naturally
• Multi-layer caching (browser → CDN → in-memory trie) reduces effective QPS by ~50% before hitting application servers
• Shard by prefix range when a single trie outgrows one server. Use consistent hashing on first 2 characters for balanced distribution
• Filter at build time, not query time: keeps the hot read path free of expensive checks while still removing inappropriate content