← Back to all questions
Senior / StaffSearchCaching

Design a Search Autocomplete System

A Senior/Staff walkthrough of a search autocomplete system that returns ranked suggestions in under 100ms at roughly 700K peak QPS, built on an in-memory compressed trie with pre-computed top-K and fed by a streaming log pipeline. The interesting tension is freshness versus latency: a 15-minute batch rebuild keeps the trie clean while a real-time fast path injects trending queries within minutes, all absorbed by a four-layer cache. Follow it top to bottom, or jump to any step.

Level
Senior / Staff
Category
Search · Low-Latency Systems
Interview time
45 min
100% free · No login required
WHAT THIS QUESTION TESTS
·Compressed (Patricia) trie with pre-computed top-K at every node
·Four-layer cache: browser → CDN edge → Redis → in-memory trie
·Trending detection via sliding-window velocity, injected ahead of batch rebuild
·Multi-signal ranking blending frequency, recency, trending, and personalization
★ STAFF-LEVEL SIGNALS
★Traces how each cache layer sheds load to keep the trie at only ~29K QPS
★Rebuilds from 100M phrases in the background and atomically blue-green swaps the trie
★Splits global popularity (baked into the trie) from per-user personalization overlaid at query time for privacy
★Chooses a trie over Elasticsearch because keystroke latency outweighs query flexibility
1

Requirements

Functional Requirements

  • Real-time suggestions: Show top 5-10 suggestions as user types each character
  • Ranking: Suggestions ranked by popularity (frequency), recency, and personalization
  • Multi-language support: Handle queries in any language
  • Trending queries: Surface trending/breaking topics quickly
  • Spell correction: Handle minor typos in prefix

Non-Functional Requirements

  • Latency: < 100ms per keystroke (must feel instantaneous)
  • Availability: 99.99% — autocomplete is part of core search
  • Scale: 5B searches/day, each averaging 4 keystrokes = ~20B autocomplete requests/day
  • Freshness: Trending queries appear within minutes; general popularity updated hourly

Constraints

  • Must filter offensive/sensitive suggestions
  • Privacy: don't leak other users' queries in suggestions
  • Mobile vs desktop: different display constraints
2

Back-of-envelope estimation

Metric
Estimate
DAU
1B
Searches/day
5B
Autocomplete requests/day
20B (avg 4 keystrokes × 5B searches)
Autocomplete QPS
20B / 86,400 ≈ ~230K QPS
Peak QPS
~700K QPS
Unique query prefixes
~100M (for top suggestions)
Average suggestion data per prefix
500 bytes (10 suggestions × 50 bytes each)
Total trie data
~50 GB (fits in memory)
Search log data/day
5B × 100 bytes = 500 GB/day
3

API design

GET /api/v1/autocomplete?q={prefix}&lang={lang}&limit=10&user_id={id}
Response: {
suggestions: [
{ text: "how to cook rice", score: 0.95, type: "trending" },
{ text: "how to cook pasta", score: 0.89 },
{ text: "how to cook chicken breast", score: 0.85 }
]
}

Key considerations:

  • No authentication required (fast path, no user lookup on critical path)
  • user_id is optional — used for personalization if available
  • Results cached aggressively at CDN/edge
4

Data model

Trie (In-Memory): Primary data structure

Trie node structure:
{
children: { char → TrieNode },
is_end_of_word: bool,
top_suggestions: [ // pre-computed top-K for this prefix
{ text: "...", score: float },
...
]
}

Search Logs: Kafka → Aggregation Pipeline

Event: { query: "how to cook rice", timestamp, user_id (hashed), country }

Aggregation Storage: Redis (for real-time counts)

Key: query_count:{query_hash}:{hour_bucket}
Value: count
TTL: 7 days

Phrase Database: PostgreSQL (source of truth for periodic trie rebuild)

CREATE TABLE query_phrases (
phrase_hash VARCHAR(64) PRIMARY KEY,
phrase TEXT,
frequency_7d BIGINT,
frequency_30d BIGINT,
trending_score FLOAT,
is_blocked BOOLEAN DEFAULT FALSE,
language VARCHAR(10),
last_updated TIMESTAMP
);
5

High-level architecture

┌──────────┐ ┌─────────┐ ┌──────────────────┐
│ Client │────▶│ CDN │────▶│ Autocomplete │
│ │ │ (Edge │ │ Service │
└──────────┘ │ Cache) │ │ (Trie in-memory) │
└─────────┘ └──────────────────┘
│
┌───────┴───────┐
│ Trie Builder │
│ (periodic) │
└───────┬───────┘
│
┌───────────┼───────────┐
│ │ │
┌─────┴────┐ ┌────┴─────┐ ┌──┴────────┐
│ Query Log│ │ Trending │ │ Blocked │
│ Aggreg. │ │ Detector │ │ Phrases │
└─────┬────┘ └────┬─────┘ └───────────┘
│ │
┌─────┴────┐ ┌────┴─────┐
│ Kafka │ │ Redis │
│ (logs) │ │ (counts) │
└──────────┘ └──────────┘

Data Flow: Autocomplete Request

1. User types “how t” → client debounces (50ms) then sends request

2. CDN checks cache for prefix “how t” → cache hit serves immediately

3. On cache miss, routes to Autocomplete Service

4. Service looks up “how t” in in-memory trie → returns pre-computed top-10

5. If user is logged in, overlay personalized results (recent searches, user interests)

6. Response cached at CDN with short TTL (5-15 min)

Data Flow: Trie Update Pipeline

1. Every search query logged to Kafka

2. Stream processor aggregates query counts per time window (1hr, 24hr, 7d)

3. Trending detector identifies queries with abnormal velocity (spike detection)

4. Trie Builder runs every 15 minutes:

  • Reads aggregated counts from DB
  • Merges trending queries with boosted scores
  • Filters blocked/offensive phrases
  • Builds new trie with pre-computed top-K per prefix
  • Atomically swaps new trie into Autocomplete Service (blue-green)
6

Deep dives

WHERE STAFF IS WON

Deep Dive 1: Trie Data Structure and Optimization

Basic trie stores one node per character. For 100M phrases, this is memory-intensive.

Optimization 1: Compressed trie (Patricia trie)

  • Merge single-child chains: "h-o-w- -t-o" becomes a single edge "how to"
  • Reduces node count by ~60%

Optimization 2: Pre-computed top-K at each node

  • Store the top 10 suggestions at every trie node
  • On query: O(prefix_length) lookup, no need to traverse subtree
  • Tradeoff: More memory but O(1) suggestion retrieval

Optimization 3: Two-level trie

  • First 2 characters → hash map (fast lookup for 676 possible bigrams)
  • Remaining characters → compressed trie
  • Reduces average lookup depth

Memory estimation:

  • 100M phrases × 500 bytes per phrase (with top-K) ≈ 50 GB
  • Fits in a single high-memory server (256 GB RAM)
  • Replicated across multiple servers for availability and throughput

Alternative: Sorted array with binary search

  • Store all phrases sorted, use binary search for prefix
  • Less memory than trie, but slower for prefix matching
  • Better for disk-based systems

Our choice: Compressed trie with pre-computed top-K, replicated across serving fleet.

Deep Dive 2: Ranking Algorithm

Scoring formula:

score = w1 × frequency_7d_normalized
+ w2 × recency_decay(last_search_time)
+ w3 × trending_boost
+ w4 × personalization_score
+ w5 × language_match

Components:

Signal
Weight
Description
Frequency (7-day)
0.4
How often this query is searched
Recency
0.2
Boost recently popular queries
Trending
0.2
Spike detection boost (breaking news)
Personalization
0.15
Based on user's search history, location
Language match
0.05
Prefer user's language

Trending detection (key for breaking news):

  • Track query frequency in sliding windows (1hr, 6hr, 24hr)
  • Compute velocity: current_window / historical_average
  • If velocity > 5x, flag as trending
  • Fast path: trending queries injected into trie within minutes (not waiting for periodic rebuild)

Personalization:

  • User's recent searches (last 100) stored in session/cookie
  • Overlay personal suggestions on top of global suggestions
  • Privacy: personalization happens at query time, not stored in global trie

Deep Dive 3: Caching Strategy

Multi-layer caching is critical for 700K peak QPS at < 100ms:

Client cache (browser) → CDN edge → Application cache (Redis) → Trie (in-memory)

Layer 1: Client-side cache

  • Browser caches recent prefix results
  • If user types "how t" then "how to", client can filter locally
  • Reduces ~30% of requests

Layer 2: CDN edge cache

  • Popular prefixes (top 10K) cached at CDN
  • TTL: 5-15 minutes (balance freshness vs hit rate)
  • Hit rate: ~70% of remaining requests
  • Key: autocomplete:{lang}:{prefix}

Layer 3: Application-level Redis cache

  • Store computed results for medium-popularity prefixes
  • TTL: 1 hour
  • Hit rate: ~80% of CDN misses

Layer 4: In-memory trie

  • Handles remaining cache misses
  • Direct memory lookup: < 1ms

Effective hit rates:

  • Client: 30% → 700K × 0.7 = 490K to CDN
  • CDN: 70% of 490K → 147K to app servers
  • Redis: 80% of 147K → 29K to trie
  • Trie handles ~29K QPS (easily manageable)
7

Bottlenecks & tradeoffs

Bottlenecks

1. Trie rebuild latency: Building a new trie from 100M phrases takes minutes

  • Mitigation: Build in background, atomic swap; incremental updates for trending

1. Hot prefixes: “how”, “what”, “why” get massive traffic

  • Mitigation: CDN caching handles this; these prefixes have very stable results

1. Long-tail prefixes: Rare prefixes have no good suggestions

  • Mitigation: Fall back to fuzzy matching or spell correction

1. Offensive content: New offensive phrases can emerge quickly

  • Mitigation: Real-time blocklist checked at serving time; async content moderation pipeline

Key Tradeoffs

Decision
Option A
Option B
Choice
Data structure
Trie (fast prefix lookup)
Elasticsearch (flexible, harder to tune)
Trie (latency is paramount)
Trie location
In-memory per server
Shared Redis
In-memory (lowest latency)
Update frequency
Real-time per query
Periodic batch (15 min)
Batch + real-time for trending
Personalization
Global only (simple)
Per-user (complex, better UX)
Global + lightweight personalization
Cache TTL
Short (1 min, fresh)
Long (1 hr, efficient)
Tiered: 5 min at CDN, 1 hr at Redis

Monitoring & Alerting

  • Autocomplete latency p99 — alert if > 200ms
  • CDN cache hit ratio — alert if < 60%
  • Trie rebuild duration — alert if > 30 min
  • Suggestion quality (click-through rate on suggestions) — track weekly
  • Blocked phrase bypass rate — alert on any offensive suggestion getting through
  • QPS per service instance — capacity planning

Failure Modes

  • Trie server failure: Requests routed to other replicas; no impact with 3+ replicas
  • CDN failure: Traffic hits app servers directly; may need to shed load
  • Kafka lag (search logs): Trie becomes stale; trending queries delayed
  • Redis failure: More traffic hits trie directly; slightly higher latency
  • Trie rebuild failure: Keep serving old trie; alert for manual intervention
★

Rubric — Senior vs Staff

Dimension
Senior signal
Staff signal
Data structure
Uses a trie for prefix lookup with top-K stored at each node.
Picks a compressed trie, justifies it against sorted-array and Elasticsearch, and sizes it to ~50 GB in RAM.
Latency budget
Serves from memory and fronts it with a CDN cache.
Layers client/CDN/Redis/trie caches and shows hit rates dropping serving load to ~29K QPS at the trie.
Freshness
Rebuilds the trie periodically from aggregated query logs.
Pairs a 15-min batch rebuild with a real-time trending fast path and atomic blue-green swaps.
Ranking
Ranks suggestions primarily by popularity.
Combines frequency, recency, trending velocity, personalization, and language into a weighted score.
Safety & privacy
Filters offensive phrases with a blocklist.
Checks blocklists at serve time plus async moderation, and keeps personalization out of the shared trie.

Related questions

★ MORE WALKTHROUGHS

Want more breakdowns like this?

Join free early access for upcoming RAG, LLM eval, agents, and AI infrastructure walkthroughs.

Join Free Early Access →