Back to System design

Design Typeahead / Search Autocomplete

medium
Scale: <100 ms p99; 1M QPS at search scale Storage: Trie ~10-100 GB sharded; per-shard fits in RAM Google, Amazon, Meta
Case StudySearchTrie

Search autocomplete (typeahead) returns top query completions as the user types, in under 100 ms. The tension: pre-compute completions per prefix in a trie (fast lookup) vs query-time scoring (flexible). Production combines both.

Scale<100 ms p99; 1M QPS at search scale
StorageTrie ~10-100 GB sharded; per-shard fits in RAM

Key Concepts

1
1. Trie-based serving. Build a trie where each node is a character and stores the top-K completions for that prefix. User typing face walks 4 edges, returns the stored list. Pre-aggregation: nightly Spark over query logs counts queries by frequency, takes top-K per prefix. Trie sharded by first 1-2 characters; replicated for serving. Total size for English search at Google scale: tens of GB across the fleet.
1. Trie-based serving.face
2
2. Streaming updates for freshness. When a news event breaks, queries should surface within minutes, not next batch. Flink job processes the query log in near real time, computes deltas over baseline, pushes updates to trie nodes every few minutes. Trending boost is the hardest piece to get right without breaking the static top-K.
2. Streaming updates for freshness.
3
3. Personalization at the edge. Server returns top-K global candidates with metadata. Client or edge function reranks with per-user history (you searched kubernetes), session context (you clicked a cooking recipe), category (Amazon's autocomplete differs by department). Personalization at the edge cuts latency to single-digit ms.
3. Personalization at the edge.kubernetes
4
4. Fuzzy matching for typos. Edit distance lookup on a trie is expensive. Production trick: build a common misspellings redirect table from query logs (youtub → youtube, whatsap → whatsapp). Cheap and correct for the long tail of typos.
4. Fuzzy matching for typos.youtub → youtubewhatsap → whatsapp
5
5. Data structures and references. Double-array trie or FST (Finite State Transducer) for memory efficiency — used in Lucene's completion_suggester. References: Google (personalized + trending), Amazon (per-category facets), Elasticsearch (FST-based), Wikipedia (frequency-based on Lucene), LinkedIn (contextual with mutual connections).
5. Data structures and references.completion_suggester

Related Problems

Implement Trie (Prefix Tree)mediumDesign Add and Search Words Data StructurehardWord Search IIhardMap Sum PairsmediumDesign a URL Shortener (TinyURL / bit.ly)medium

High-level design

Offline batch: query logs → Spark aggregator → top-K per prefix → trie builder → trie store.
Streaming: query logs → Flink → delta updates → push to trie (every few minutes).
Serving: user prefix → trie lookup → top-K candidates → edge rerank for personalization → response.
Misspelling: separate lookup; replace prefix with corrected form before trie walk.

Components

  • Query log aggregator (Kafka + Spark).
  • Trie builder (batch + incremental).
  • Serving fleet (in-memory trie shards, sharded by first 1-2 chars).
  • Edge cache (CDN) for short prefixes (huge hit rate).
  • Personalization service (per-user history, session context).
  • Streaming pipeline for trending detection.
  • Misspelling correction service.
  • Feedback logging — which suggestion the user picked, for ranking refinement.

Data structures

Trie: classic. Each node stores top-K. Compact representation via double-array trie or FST.

FST (Finite State Transducer): compressed trie with shared suffixes; used in Lucene's completion suggester.

Sorted array + binary search: simple, works for small datasets.

Aho-Corasick for multi-pattern match (less common for typeahead).

Distributed trie: shard by first character; each shard fits in RAM; replicate for load.

Trade-offs

Precomputed trie: 1-5 ms latency, rebuild cost.

Query-time from inverted index: 10-50 ms, flexible scoring.

Daily batch: cheap, stale.

Streaming update: fresh, expensive.

Hybrid: batch + streaming overlay. Standard production answer.

Fuzzy matching: 10-100x more expensive than exact; cap to candidate set after exact-prefix returns.

Real-world references

  • Google: heavily personalized; freshness within minutes for trends.
  • Elasticsearch: completion_suggester (FST-based).
  • Amazon: per-category facets, query log + product catalog.
  • Wikipedia: simple frequency-based, Lucene-backed.
  • LinkedIn: peer typeahead is contextual (mutual connections, company).