Design a Search Autocomplete System

1. Problem Statement & Scope Clarification

System Mission

Design a real-time, globally distributed search autocomplete (typeahead) platform (similar to Google Search and Amazon product search autocomplete) capable of returning the Top-5 most relevant, high-frequency query completions as a user types into a search box, achieving sub-10 millisecond global $P99$ read latency at a scale of billions of searches per day.

Functional Requirements

1. Real-Time Prefix Autocomplete: Given a prefix string (e.g., "sys"), return the Top-5 highest-ranked completed search queries matching that prefix within $< 10\text{ ms}$.
2. Relevance & Popularity Ranking: Suggestions are dynamically scored and sorted based on historical query frequency, recency, geographic locality, and personalized user context.
3. Real-Time Trending Ingestion: Sudden viral breaking news or high-velocity searches (e.g., breaking disaster, product launch) must surface in autocomplete within 5 minutes without waiting for nightly batch recalculation.
4. Fuzzy Prefix & Typo Fallback: If a user types a misspelling or an unknown prefix that yields zero hits in the precomputed Trie (e.g., "sytem des"), seamlessly fall back to an approximate fuzzy search engine.
5. Harmful Content Filtering & Blacklisting: Prohibit offensive, hateful, or legally restricted search terms using sub-millisecond in-memory Bloom filters and dynamic remote blacklists.
6. Unicode & Normalization: Support case-insensitive, accent-insensitive, and multi-byte UTF-8 character string matching across international locales.

Non-Functional Requirements (SLAs & SLOs)

• Latency: $P50 < 3.0\text{ ms}$, $P99 < 10.0\text{ ms}$ global read latency. The autocomplete suggestions must render before the user types the next character (average human inter-keystroke interval $\approx 150\text{ ms}$).
• Availability: $99.999\%$ ("five nines") uptime SLA for the online query path.
• Throughput & Scale: Support $1\text{ Billion}$ searches per day, translating to $4\text{ Billion}$ autocomplete keystroke requests daily, with peak query traffic reaching $100,000\text{ QPS}$.
• Data Freshness: Offline batch Trie compilation completed weekly/nightly; streaming trending velocity merged within $\le 5\text{ minutes}$.

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

Traffic & Keystroke Volume

• Daily Searches Initiated: $1,000,000,000\text{ searches/day}$ (1 Billion searches).
• Average Keystrokes per Search Session: A typical user types 4–6 characters before clicking a suggestion or pressing enter. We assume $4\text{ keystroke autocomplete calls}$ per completed search session.
• Total Daily Autocomplete Keystrokes: $\text{Daily Requests} = 10^9\text{ searches} \times 4\text{ keystrokes} = \mathbf{4.0 \times 10^9\text{ requests/day}}$
• Average Read QPS: $\text{Average QPS} = \frac{4.0 \times 10^9\text{ requests}}{86,400\text{ sec}} \approx \mathbf{46,296\text{ QPS}}$
• Peak Read QPS ($2.2\times$ diurnal peak multiplier): $\text{Peak QPS} = 46,296 \times 2.2 \approx \mathbf{100,000\text{ QPS}}$

Trie Memory Footprint Estimation

• Total Unique Search Queries Retained: We retain the top $100,000,000$ ($100\text{M}$) most frequent queries across a 30-day rolling window (any query searched fewer than 50 times in the window is pruned, see Section 8.2).
• Average Query Length: $20\text{ characters}$ ($20\text{ bytes}$ in UTF-8).
• Precomputed Top-5 Radix Node Memory Layout:
  • To achieve $O(1)$ prefix lookups, every intermediate prefix node stores its Top-5 completed suggestions directly.
  • Suggestion record: 5 suggestions $\times (4\text{B Query ID} + 4\text{B Score}) = 40\text{ bytes}$.
  • Structural Radix node overhead (compact double-array or LOUDS tree pointer): $\approx 30\text{ bytes}$.
  • String pool storage: $100\text{M queries} \times 20\text{ bytes} = 2.0\text{ GB}$.
  • Total per prefix node $\approx 70\text{ bytes}$.
  • Assuming an optimized Radix tree produces $\approx 200\text{M}$ prefix nodes for $100\text{M}$ phrases: $\text{[Trie](/components/13-trie-data-structure-and-inverted-index) Memory} = (200 \times 10^6 \times 70\text{ bytes}) + 2.0\text{ GB} \approx 14.0\text{ GB} + 2.0\text{ GB} = \mathbf{16.0\text{ GB RAM}}$
• ElastiCache Redis Cluster Sizing:
  • Hosting the precomputed Top-5 Radix key-value lookup in an Amazon ElastiCache Redis Cluster:
  • With Redis jemalloc allocator overhead ($1.3\times$) and primary + replica pairing ($2\times$): $\text{Total Cache Memory Required} = 16.0\text{ GB} \times 1.3 \times 2 \approx \mathbf{41.6\text{ GB RAM}}$
  • A modest 3-node cluster of cache.r6g.xlarge instances ($26.32\text{ GB RAM}$ each, $78.96\text{ GB}$ total) delivers ample headroom, $500\text{k IOPS}$, and sub-millisecond memory fetches.

Network Bandwidth Sizing

• Average Autocomplete Response Size: JSON payload with 5 suggestions $\approx 350\text{ bytes}$.
• Peak Egress Network Bandwidth: $\text{Peak Egress} = 100,000\text{ QPS} \times 350\text{ bytes} = 35\text{ MB/sec} = \mathbf{280\text{ Mbps}}$
• Edge Cache Offload: Caching top 1-3 letter prefixes at CloudFront edge PoPs offloads up to $40\%$ of global queries: $\text{Origin Shield Ingress QPS} = 100,000 \times 0.60 = \mathbf{60,000\text{ QPS}}$

3. Dual-Path Architecture & AWS Component Mapping

The system utilizes a Dual-Path Architecture: an ultra-low latency Online Query Path delivering sub-$5\text{ ms}$ suggestions, and an Asynchronous Big Data Pipeline performing streaming velocity updates and weekly batch Trie compilation.

Synthesizing vector architecture diagram...

Data Flow Walkthrough

1. Edge Interception: Keystrokes pass through CloudFront. Short 1-3 character prefixes (e.g., "a", "am", "ama") that represent over $40\%$ of all volume hit edge cache with $1-2\text{ ms}$ round-trip times.
2. In-Memory Cache Lookup: Cache misses route to the Typeahead Fleet on ECS. The query service issues two parallel asynchronous queries:
   • Fetches the precomputed baseline Top-5 completions from ElastiCache Redis (trie:en:us:<prefix>).
   • Checks the Redis Fast Ring Buffer for any viral breaking queries matching the prefix.
3. Fuzzy Fallback Execution: If the Redis Trie returns zero matches (due to a typo like "aple ihoen"), the service triggers an asynchronous circuit-breaker-protected fallback call to Amazon OpenSearch Service, querying an edge_ngram index with a Levenshtein edit distance of $1-2$.
4. Asynchronous Telemetry Ingestion: Every keystroke session event is emitted via UDP/fire-and-forget buffer to Amazon Kinesis. Flink aggregates queries over a 10-minute sliding window. Sudden spikes ($> 5\times$ standard deviation above moving baseline) are pushed to the Redis Fast Ring Buffer within minutes.

Concrete Step-by-Step Request Walkthrough: Tracing an Autocomplete Keystroke

4. API Interface Design & Wire Protocol

Typeahead RESTful Query Contract

httpCopy
GET /v1/search/autocomplete?q=system+des&limit=5&country=US&lang=en HTTP/2
Host: autocomplete.production.aws.internal
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7)
Accept: application/json
X-Client-Request-Id: req_984b2c18-4720-4e3a-921a-64119d883b1a

Response: 200 OK
Content-Type: application/json; charset=utf-8
Cache-Control: public, max-age=60, stale-while-revalidate=30
Server-Timing: edge;dur=1.2, redis;dur=0.6, total;dur=2.1

{
  "prefix": "system des",
  "normalized_prefix": "system des",
  "source": "TRIE_PRECOMPUTED",
  "suggestions": [
    {
      "query": "system design interview",
      "score": 98500,
      "category": "Education",
      "highlight": "system des<b>ign interview</b>",
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system design roadmap",
      "score": 84200,
      "category": "Career",
      "highlight": "system des<b>ign roadmap</b>",
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system design cheat sheet",
      "score": 79100,
      "category": "Education",
      "highlight": "system des<b>ign cheat sheet</b>",
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system description example",
      "score": 41200,
      "category": "Engineering",
      "highlight": "system des<b>cription example</b>",
      "type": "HISTORICAL_POPULAR"
    },
    {
      "query": "system design primer github",
      "score": 38900,
      "category": "Software",
      "highlight": "system des<b>ign primer github</b>",
      "type": "HISTORICAL_POPULAR"
    }
  ]
}

OpenSearch Fuzzy Fallback Query (When Trie Misses)

jsonCopy
{
  "query": {
    "bool": {
      "must": [
        {
          "match": {
            "query_text": {
              "query": "sytem des",
              "fuzziness": "AUTO:3,6",
              "prefix_length": 2,
              "max_expansions": 10
            }
          }
        }
      ],
      "filter": [
        { "term": { "status": "APPROVED" } },
        { "term": { "locale": "en_US" } }
      ]
    }
  },
  "sort": [
    { "search_frequency_30d": { "order": "desc" } }
  ],
  "size": 5
}

5. Data Models & Storage Architecture

1. Redis Key Layout & Compact Binary Serialization

To maximize CPU L1/L2 cache locality and minimize memory overhead in ElastiCache Redis, precomputed suggestions are serialized using FlatBuffers into raw byte arrays:

• Redis Key Pattern: trie:<locale>:<prefix_string> (e.g. trie:en-us:sys)

• Redis Data Type: STRING (Raw binary blob containing 5 serialized suggestion entries).

• Binary Payload Structure (per key, 62 bytes total: $8 + 5 \times 10 + 4$):

  Section, in byte order	Size	Contents
  Header	8 bytes	Count (1 byte), then reserved bytes
  5 suggestion slots	10 bytes each, 50 bytes in total	QueryID (4 bytes), Score (4 bytes), Flags (2 bytes)
  Checksum	4 bytes	CRC32C
  The value stores only 32-bit QueryIDs, never the query text. Each Typeahead task loads the $2\text{ GB}$ query string table (Section 2) from the same S3 snapshot into process memory at boot, so resolving an ID to its text is an in-process array index, not a second Redis round trip. This is what keeps the Redis footprint at the $16\text{ GB}$ computed in Section 2 instead of duplicating 20-byte strings into 200M keys.

• Real-Time Trending Ring Buffer:

  • Redis Key: trending:<locale>:10m
  • Redis Data Type: ZSET (Sorted Set)
  • Score: Velocity metric ($\Delta \text{Count} / \text{Baseline}$)
  • Member: UTF-8 Query string

2. Amazon OpenSearch Index Mapping (autocomplete-catalog-v1)

Used as the secondary fuzzy fallback tier when Trie prefix matching yields zero results:

jsonCopy
{
  "settings": {
    "number_of_shards": 6,
    "number_of_replicas": 2,
    "analysis": {
      "analyzer": {
        "autocomplete_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "asciifolding", "edge_ngram_filter"]
        }
      },
      "filter": {
        "edge_ngram_filter": {
          "type": "edge_ngram",
          "min_gram": 2,
          "max_gram": 20
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "query_text": {
        "type": "text",
        "analyzer": "autocomplete_analyzer",
        "search_analyzer": "standard"
      },
      "canonical_phrase": { "type": "keyword" },
      "search_frequency_30d": { "type": "long" },
      "category": { "type": "keyword" },
      "locale": { "type": "keyword" },
      "status": { "type": "keyword" }
    }
  }
}