System Design HLD Example: Search Autocomplete (Google/Amazon)

Scenario context

Search autocomplete must respond in sub-10ms to feel "instant." The core trade-off is Latency vs. Data Freshness: we use an offline pipeline (Spark) to pre-calculate prefix-to-suggestion mappings and store them in Redis Sorted Sets (or a specialized Trie) for near-instant retrieval, while sacrificing real-time updates for most queries.

Imagine you are typing in a search bar: "best res..." You expect the sys…

This walkthrough focuses on The "Keystroke" Performance Gap.

Before making a design choice, clarify:

• Imagine you are typing in a search bar: "best res..." You expect the system to suggest "best restaurants" before you even finish the word "restaurants." An average person types at about 60-80 words per minute, which mea…
• In a poorly designed system, every keystroke triggers a SQL query: SELECT query FROM search logs WHERE query LIKE 'best res%' ORDER BY count DESC LIMIT 5 .
• Under the weight of 100,000 concurrent users, this LIKE query will crush your database.

Concepts in play: caching, tree-data-structures, database-indexing, system-design-hld-architectures

Stage 1 — Search Autocomplete: Use Cases & Requirements

• Actors - Search User: Expects instant, relevant suggestions as they type.
• • Data Scientist / Analyst: Fine-tunes ranking algorithms based on click-through rates.
• • Admin: Manages blacklists for inappropriate or harmful suggestions.
• Functional Requirements - Prefix Matching: Given a prefix (e.g., "ap"), return the top 5-10 most popular suggestions (e.g., "apple", "amazon").

Observable outcome: Functional Requirements - Prefix Matching: Given a prefix (e.g., "ap"), return the top 5-10 most popular suggestions (e.g., "apple", "amazon").

Stage 2 — Basics: The Trie Data Structure

• At the heart of most autocomplete systems is a Trie (Prefix Tree).
• A Trie is a tree-like data structure where each node represents a character.
• • To find suggestions for "app", you traverse the tree: a - p - p .
• • Every node can store the top 10 most popular queries that pass through it.

Observable outcome: - Every node can store the top 10 most popular queries that pass through it.

Stage 3 — Mechanics: Distribution & Frequency Aggregation

• We don't compute suggestions on-the-fly.
• Instead, we use a Data Ingestion Pipeline : 1.
• Log Collection: Every time a user submits a full search, we log it to a message queue (Kafka).
• Aggregation: A background job (Spark/Flink) aggregates these logs hourly/daily to calculate the "Frequency" of each query.

Observable outcome: Aggregation: A background job (Spark/Flink) aggregates these logs hourly/daily to calculate the "Frequency" of each query.

Stage 4 — Estimations & Design Goals

• The Math of Search - Daily Active Users (DAU): 100 Million.
• • Total Autocomplete Requests: 100M 10 20 = 20 Billion per day .
• • Average QPS: 20B / 86,400 $\approx 230,000$ requests per second.
• Design Goal: The system must be stateless and horizontally scalable .

Observable outcome: Design Goal: The system must be stateless and horizontally scalable .

Stage 5 — High-Level Design: The Two-Path Architecture

• The system is split into the "Fast Path" (Serving) and the "Slow Path" (Analytics).
• The diagram shows the two-path architecture clearly.
• The Fast Path (top) serves user keystrokes directly from the Redis Sorted Set cache with a single ZREVRANGEBYSCORE call — the entire backend lookup completes in under 2ms.
• The Slow Path (bottom) records completed searches to Kafka asynchronously, aggregates frequency counts in Spark on an hourly or daily schedule, and rebuilds the suggestion index in Redis.

graph TD
    User((User)) --> LB[Load Balancer]
    LB --> AS[Autocomplete Service]

    subgraph Serving_Fast_Path
        AS --> RC[(Suggestion Cache: Redis)]
    end

    subgraph Ingestion_Slow_Path
        AS --> MQ[Kafka]
        MQ --> Agg[Aggregation Service: Spark]
        Agg --> PDB[(Search History: Postgres)]
        Agg --> IB[Index Builder]
        IB --> RC
    end

Observable outcome: The Slow Path (bottom) records completed searches to Kafka asynchronously, aggregates frequency counts in Spark on an hourly or daily schedule, and rebuilds the suggestion index in Redis.

Stage 6 — Real-World Autocomplete Systems: Google, Amazon, and Elasticsearch

• Google Suggest operates at 230,000 QPS with suggestions updated within 15 minutes of trending events.
• Google's implementation uses a distributed Trie sharded by geographic region and query language.
• Each Trie shard serves a subset of the prefix space (e.g., all prefixes starting with characters A–M in English for the US West Coast region).
• This limits Trie size to under 10GB per shard while achieving sub-1ms traversal latency within the data center.

Observable outcome: This limits Trie size to under 10GB per shard while achieving sub-1ms traversal latency within the data center.

End-to-end outcome

Imagine you are typing in a search bar: "best res..." You expect the system to suggest "best restaurants" before you even finish the word "restaurants." An average person types at about 60-80 words per minute, which means there are only about 100-150 milliseconds between keystrokes.

Alternatives considered

The three hardest engineering problems in search autocomplete are choosing the right data structure for sub-10ms prefix lookup, handling typos without a full-text index, and personalizing results without violating the latency budget.

The three hardest engineering problems in search autocomplete are choosing the right data structure for sub-10ms prefix lookup, handling typos without a full-text index, and personalizing results without violating the latency budget.

Internals: Trie vs. Redis Sorted Set — When Each Wins

A Trie (prefix tree) stores suggestions in a tree where each node represents a character.

Performance Analysis: Offline Aggregation Pipeline and Index Freshness Budget

The serving latency of under 2ms is achievable only because the suggestion index is pre-computed offline .

Decision Guide: Serving Strategy by System Scale

Typo tolerance should never be in the critical serving path.

Failure and degraded modes

Trade-offs and Failure Modes in Search Autocomplete Design

• Detection: Zero-Result Prefix: When a user types a prefix that has no matching entry in the suggestion index (either because it is genuinely rare or because the index hasn't been updated yet), the system must g…
• User or operator impact: Zero-Result Prefix: When a user types a prefix that has no matching entry in the suggestion index (either because it is genuinely rare or because the index hasn't been updated yet), the system must g…

Lessons Learned from Autocomplete Failures at Scale

• Detection: A Single Hot Key Took Down the Suggestion Service During a Product Launch.
• User or operator impact: A Single Hot Key Took Down the Suggestion Service During a Product Launch.