Design Autocomplete for Search

Problem Statement

Design a search autocomplete (typeahead) system that returns the top suggestions as a user types each character. The system must serve suggestions with sub-100ms latency for billions of queries per day, ranking results by popularity, recency, and personalization.

Requirements

Functional

• Return top-k (e.g., 10) prefix-matched suggestions as the user types
• Rank suggestions by popularity, freshness, and optionally user history
• Support multi-language queries and handle typos gracefully
• Update suggestion corpus as new trending queries emerge

Non-Functional

• Latency: <100ms p99 per keystroke
• Availability: 99.99% uptime -- degraded suggestions are better than none
• Scale: 500M daily active users, ~10B queries/day, peak 200K QPS

Core Architecture

1. Trie Service -- In-memory distributed Trie storing top-k suggestions at each prefix node. Each node holds a sorted list of up to 25 candidates with their scores. Tries are partitioned by first two characters across nodes.

2. Ranking Aggregator -- Offline MapReduce pipeline that processes query logs every 15 minutes. Computes popularity scores using exponential time decay: score = count * 0.95^(hours_since_query). Rebuilds Trie snapshots.

3. Sampling Collector -- Logs a sampled subset (1-in-1000) of all queries to avoid overwhelming storage. Feeds into the Ranking Aggregator. Stored in append-only log (Kafka topic).

4. Zookeeper Coordination Layer -- Manages Trie partition assignment across nodes. Handles leader election for Trie rebuild. Coordinates rolling Trie snapshot deployments.

5. CDN/Edge Cache -- Most popular prefixes (a, th, the, wh, ...) are cached at CDN edge nodes with 5-minute TTL. Handles ~30% of all requests without reaching the Trie service.

Database Choice

Trie storage: In-memory data structure (custom or Redis-based) for serving. The Trie is rebuilt offline and serialized as a binary snapshot loaded at startup. Raw query logs are stored in HDFS/S3 for batch processing. Metadata (query-to-score mappings) lives in Cassandra for its write-heavy, append-friendly nature.

Key API Endpoints

GET /api/v1/suggestions?prefix=\{query\}&limit=10&lang=en
  -> Returns: \{ suggestions: ["search term 1", "search term 2", ...], latency_ms: 12 \}

POST /api/v1/queries (internal - from sampling collector)
  -> Body: \{ query: "full search term", timestamp: 1700000000, user_id?: "abc" \}

Scaling Insight

The key scaling trick is two-level caching with prefix partitioning. Short prefixes (1-2 chars) generate massive fan-out and are cached at the CDN edge. Longer prefixes hit the Trie service, which is partitioned by the first two characters of the prefix. This means "go" and "goo" and "google" all hit the same Trie partition. With 26^2 = 676 possible two-char prefixes, you can distribute across ~100 machines with good load balance. Hot prefixes get additional replicas.

Key Tradeoffs

Original DosiBridge notes for Design Autocomplete for Search

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Design Autocomplete for Search is to connect the concept to a retrieval path where users judge quality by relevance, latency, and how quickly updates become searchable. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Core Entity: For Design Autocomplete for Search, decide the core entity before choosing tools; otherwise the design looks clean but fails when autocomplete changes.
• Read/Write Path: For Design Autocomplete for Search, decide the read/write path before choosing tools; otherwise the design looks clean but fails when autocomplete changes.
• Contention Point: For Design Autocomplete for Search, decide the contention point before choosing tools; otherwise the design looks clean but fails when autocomplete changes.
• Abuse Path: For Design Autocomplete for Search, decide the abuse path before choosing tools; otherwise the design looks clean but fails when autocomplete changes.
• Recovery Workflow: For Design Autocomplete for Search, decide the recovery workflow before choosing tools; otherwise the design looks clean but fails when autocomplete changes.

Design Autocomplete for Search correctness boundary

For this problem, separate the user-visible action from background work. The correctness boundary is the smallest state transition that must not be duplicated, lost, or reordered. Naming that boundary makes the solution more original than a stock API/database/cache template.

Design Autocomplete for Search scaling bottleneck

The first bottleneck should be described in the language of this system: a hot timeline, a contested seat, a busy wallet ledger, a media-processing queue, or a search index update delay. That bottleneck decides which component deserves the deepest interview discussion.

Production review question

If Design Autocomplete for Search suddenly receives 10x traffic, which entity becomes contested first, and what queue, lock, shard, or cache protects that entity without hiding correctness bugs?

Practical metric to track

Track autocomplete health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Design Autocomplete for Search, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.

Sources

• Design Autocomplete for Search -- Reference
• Source: System-Design-Overview