Design a Search Autocomplete System

1. Problem Statement & Scope Clarification

System Mission

Design a real-time, globally distributed search autocomplete (typeahead) system (similar to Google Search and Amazon product typeahead) capable of returning the Top-5 most relevant, high-frequency query completions as a user types into a search box, achieving sub-10 millisecond latency at massive planetary scale.

Functional Requirements

1. Real-Time Prefix Completion: Given a search prefix (e.g., "sys"), return the Top-5 highest-ranked completed search phrases within 10ms.
2. Dynamic Relevance & Frequency Ranking: Rank suggestions based on historical query frequency, recency, location, and user personalization.
3. Trending & Breaking News Ingestion: Surface sudden viral search spikes within 5 minutes without waiting for nightly batch re-indexes.
4. Content Filtering & Safety: Filter out profanity, hate speech, and sensitive personal information using a high-speed blacklist filter.
5. Multi-Lingual & Unicode Support: Support accent-insensitive, case-insensitive, and multi-byte UTF-8 string prefix matching.

Non-Functional Requirements (SLAs & SLOs)

• Ultra-Low Latency: $P50 < 3.0\text{ ms}$, $P99 < 10.0\text{ ms}$ globally. Autocomplete must render before the user types the next character ($\approx 150\text{ ms}$ human typing speed).
• High Availability: $99.999\%$ uptime SLA.
• Scalability: Support $> 100,000\text{ QPS}$ at peak.
• Data Freshness: Batch models refreshed daily; trending query velocity merged within 5 minutes.

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Ingest & Query Volume

• Daily Searches: $1,000,000,000\text{ queries/day}$ (1 Billion searches/day).
• Average Keystrokes per Search: 4 autocomplete queries per completed search.
• Total Daily Autocomplete Requests: $10^9\text{ searches} \times 4\text{ keystrokes} = \mathbf{4.0 \times 10^9\text{ requests/day}}$
• Average QPS: $\text{Average QPS} = \frac{4 \times 10^9}{86,400\text{ sec}} \approx \mathbf{46,296\text{ QPS}}$
• Peak QPS ($2.2\times$ peak multiplier): $\text{Peak QPS} \approx \mathbf{100,000\text{ QPS}}$

Trie Memory Footprint Estimation

• Total Unique Search Queries Retained: $100,000,000$ ($100\text{M unique queries}$).
• Average Query Length: 20 characters ($20\text{ bytes}$).
• Optimized Radix Tree / FST (Finite State Transducer) Node Layout:
  • Precomputing Top-5 suggestions at every node eliminates tree traversal during runtime.
  • 5 suggestions $\times$ 20 bytes $= 100\text{ bytes}$ per node.
  • Pointer and Trie structural overhead $\approx 40\text{ bytes}$.
  • Total per prefix entry $\approx 140\text{ bytes}$.
• Raw Trie Memory Footprint: $\text{[Trie](/components/13-trie-data-structure-and-inverted-index) Memory} = 100,000,000\text{ entries} \times 140\text{ bytes} \approx \mathbf{14.0\text{ GB RAM}}$
• Multiplexing across an Amazon ElastiCache Redis Cluster with $3\times$ replication requires only $\approx 42\text{ GB RAM}$, fitting comfortably on a modest multi-node cluster.

3. Dual-Path Architecture & AWS Component Mapping

The architecture splits into an Ultra-Low Latency Online Query Path and an Asynchronous Big Data Analytics Pipeline.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. API Interface Design & Wire Protocol

Typeahead Query REST/HTTP API

httpCopy
GET /v1/search/autocomplete?q=sys&limit=5&country=US&lang=en
Host: autocomplete.production.aws.internal
Accept: application/json

Response: 200 OK
Cache-Control: public, max-age=60, stale-while-revalidate=30
Content-Type: application/json

{
  "prefix": "sys",
  "suggestions": [
    {
      "query": "system design interview",
      "score": 98500,
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system design roadmap",
      "score": 84200,
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system down outage today",
      "score": 79100,
      "type": "REALTIME_TRENDING"
    },
    {
      "query": "system 32 error fix",
      "score": 64300,
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system architecture patterns",
      "score": 52100,
      "type": "HISTORICAL_POPULAR"
    }
  ],
  "server_timing_ms": 1.42
}

5. Storage Engine & Trie Serialization Schema

1. Radix Trie Node Structure with Precomputed Top-$K$

Storing the Top-$K$ (Top 5) completions directly on every intermediate prefix node converts the query time complexity from $O(\text{Prefix} + \text{Tree Traversals} + K \log K)$ down to a pure $O(1)$ memory lookup:

textCopy
Trie Root
├── "s" [Top-5: "spotify", "slack", "system design", "steam", "salesforce"]
│   └── "y" [Top-5: "system design", "system down", "synonym", "syntax", "sync"]
│       └── "s" [Top-5: "system design", "system down", "sysco", "sysadmin", "system32"]

2. Redis Key Layout & Binary Serialization Format

To optimize memory cache lines, precomputed suggestions are serialized using FlatBuffers and stored under compressed Redis keys:

• Redis Key: trie:en:us:<prefix_sha1_or_string> (e.g. trie:en:us:sys)
• Redis Value: Binary FlatBuffer byte array containing 5 compressed query ID pointers and integer relevance scores.
• TTL: 86,400 seconds (Refreshed daily via snapshot deployment).