Designing Search Autocomplete / Typeahead

Simulate this design Draw it from memory

Difficulty: Intermediate Topics: Trie, Prefix Matching, Ranking, Caching, Real-time Trending Asked at: Google, Amazon, Microsoft, LinkedIn, Uber, Flipkart Prerequisites:Caching, Database Indexing, and Scalability

1. Understanding the Problem

Search autocomplete predicts what a user is about to type and suggests completions in real-time as they press each key. It powers the dropdown under every search bar — Google, Amazon product search, YouTube, LinkedIn people search. The core challenge: return the top-k most relevant suggestions for any prefix in under 100ms, while continuously learning from billions of new queries to keep suggestions fresh and trending-aware.

Real examples: Google Search Suggestions, Amazon product typeahead, YouTube search, LinkedIn search, Spotify song search.

1.5. Naive First Cut

flowchart LR
    USER["User types prefix"]:::client
    API["API Server"]:::service
    DB[("SQL DB<br/>all queries + counts")]:::data

    USER --> API
    API -->|"SELECT WHERE query LIKE 'pre%'<br/>ORDER BY count DESC LIMIT 10"| DB

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Store every query with its count in a SQL table. On each keystroke, run a LIKE prefix query ordered by count.

Why this breaks:

LIKE ‘prefix%’ on billions of rows is too slow even with B-tree indexes (full scan for short prefixes like “a”)
A keystroke fires every 50-100ms - SQL can’t keep up at millions of concurrent users
No real-time trending - counts only update in batch, so today’s viral topic won’t surface for hours
Single DB becomes the bottleneck - no horizontal scaling for read-heavy prefix lookups
No personalization - everyone sees the same suggestions regardless of context
Network round-trip to DB on every keystroke adds unacceptable latency

The rest of the doc evolves this into a Trie-based service with in-memory prefix lookups, async count aggregation, and a caching layer that serves most requests without hitting the data tier.

1.7. Prior Art We’re Drawing From

Google Autocomplete - Uses a combination of query popularity, freshness, and user context. Suggestions update in real-time for trending queries using a streaming pipeline separate from the batch popularity index. (Google Blog)
LinkedIn Typeahead - Built a distributed Trie service called “Galene” that serves prefix-based entity search (people, companies, jobs) with sub-50ms P99. Uses a two-level architecture: coarse-grained sharding by prefix + fine-grained in-memory Tries per shard. (LinkedIn Engineering)
Facebook Unicorn (Social Graph Search) - Typeahead over a social graph combines prefix matching with social proximity scoring (friends-of-friends rank higher). The ranking signal isn’t just popularity but personalized affinity. (Facebook Engineering)
Elasticsearch Completion Suggester - Uses FST (Finite State Transducer) data structure internally for prefix lookups with weighted suggestions, serving sub-5ms responses from an in-memory structure. Common choice for product search typeahead.

Technology Choices

Tier	Purpose	Stores	Access Pattern	Primary Pick	Alternatives
Prefix index	In-memory prefix lookups	Top-k completions per prefix node	Point lookup by prefix string	Custom distributed Trie service	Elasticsearch Completion Suggester / Redis sorted sets
Query log store	Raw query event stream	Every search query with timestamp	Append-only writes	Kafka / Kinesis	Pulsar / Redpanda
Aggregation	Count queries over time windows	Query frequency per time bucket	Streaming aggregation	Flink / Kafka Streams	Spark Structured Streaming
Popularity store	Aggregated query counts	query -> count + trend score	Batch read for Trie rebuild	Cassandra / DynamoDB	Postgres (if scale is moderate)
Cache	Hot prefix results	prefix -> top-10 suggestions	Key-value lookup	Redis / Memcached	Cloudflare Workers KV
Analytics DB	Historical query analytics	Long-term query logs	OLAP queries	ClickHouse / BigQuery	Redshift / Snowflake

Why a custom Trie over Elasticsearch? For pure prefix completion at massive scale (100K+ QPS), an in-memory Trie with pre-computed top-k at each node is 10-50x faster than ES Completion Suggester because it avoids serialization and network hops. ES is the right call if you also need fuzzy matching, typo correction, and faceted search alongside autocomplete.

2. Functional Requirements

Core (Top 3)

Return top-k suggestions for a prefix - as the user types each character, return the 10 most relevant completions in under 100ms
Rank by popularity and freshness - suggestions reflect both historical popularity and real-time trending queries
Update suggestions with new queries - when users search for something new (a breaking event, a new product), it should appear in suggestions within minutes, not hours

Below the Line

Personalized suggestions (based on user history)
Spell correction / fuzzy matching
Multi-language support
Offensive content filtering
Category-aware suggestions (products vs pages vs people)

3. Non-Functional Requirements

Core

Low latency: P99 < 100ms (users expect instant response on each keystroke)
High availability: 99.99% - autocomplete is on the critical search path
Scale: 100K+ prefix lookups per second; 10B+ queries/day feeding the popularity model
Freshness: Trending queries surface within 5-15 minutes

Below the Line

Eventual consistency is acceptable (a few minutes stale is fine)
Multi-region serving (CDN-friendly for static prefix results)
Graceful degradation under load (return cached stale results rather than fail)

4. Core Entities

Query - a search string submitted by a user (the raw event)
PrefixNode - a node in the Trie representing a character in a prefix path
Suggestion - a complete query string with its popularity score and metadata
TrendingQuery - a query whose recent velocity exceeds its historical baseline
QueryAggregate - a time-bucketed count for a query string (used for ranking)

5. API / System Interface

GET /v1/suggestions?prefix=<string>&limit=10
Authorization: Bearer <token> (optional - for personalization)

Response:
{
  "prefix": "how to des",
  "suggestions": [
    {"text": "how to design a url shortener", "score": 9842},
    {"text": "how to design distributed systems", "score": 7231},
    {"text": "how to design uber", "score": 6890}
  ],
  "trending": ["how to design ai agents"]
}

POST /v1/queries (internal - logs a completed search)
Body: {"query": "how to design uber", "userId": "u123", "timestamp": 1720000000}

Response: 202 Accepted

Security notes: rate-limit prefix lookups per IP/session to prevent scraping the full suggestion index. Filter offensive and legally restricted terms server-side before returning suggestions.

6. High-Level Design

FR1: Return top-k suggestions for a prefix

We need a data structure that can look up any prefix and instantly return the top-k completions. This is the Trie — a tree where each node represents a character, and paths from root to leaves spell out complete queries.

flowchart LR
    USER["User Browser"]:::client
    LB["Load Balancer"]:::edge
    TRIE["Trie Service<br/>(in-memory)"]:::service
    CACHE["Redis Cache"]:::data

    USER -->|"1. GET /suggestions?prefix=how"| LB
    LB -->|"2. Forward to trie svc"| TRIE
    TRIE -->|"3. Lookup prefix in cache"| CACHE

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#38bdf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Color	Meaning
Purple	Client
Blue	Edge / Load Balancer
Green	Application Service
Yellow	Data Store

New components:

Trie Service: Holds the entire prefix Trie in memory. Each node stores the top-k completions for that prefix (pre-computed). A lookup is O(L) where L = prefix length — typically 5-20 characters, so effectively O(1).
Redis Cache: Caches the most popular prefix results (the top 1000 prefixes handle ~80% of requests). Avoids hitting the Trie service for hot prefixes.

Flow:

User types “how” — browser sends GET request to load balancer
Load balancer routes to a Trie service instance (any replica works - stateless lookups)
Trie service checks Redis cache for prefix “how”
Cache hit → return cached top-10 suggestions directly
Cache miss → traverse Trie to node “h→o→w”, read pre-computed top-10 from that node
Store result in Redis with short TTL (5-15 min) and return to user
Total latency: 5-20ms (cache hit) or 20-50ms (Trie lookup)

FR2: Rank by popularity and freshness

Before we can rank suggestions, we need to know how popular each query is — and how that popularity is changing. This means processing billions of search events into aggregated counts, and detecting when a query’s velocity spikes.

flowchart LR
    USER["User Browser"]:::client
    LB["Load Balancer"]:::edge
    TRIE["Trie Service"]:::service
    CACHE["Redis Cache"]:::data
    QLOG["Query Logger"]:::service
    STREAM["Kafka"]:::async
    AGG["Stream Aggregator"]:::async
    POPDB[("Popularity Store<br/>Cassandra")]:::data

    USER -->|"1. Type prefix query"| LB
    LB -->|"2. Forward to trie svc"| TRIE
    TRIE -->|"3. Lookup prefix in cache"| CACHE
    USER -->|"4. Search submitted"| QLOG
    QLOG -->|"5. Publish query event"| STREAM
    STREAM -->|"6. Aggregate popularity"| AGG
    AGG -->|"7. Update popularity store"| POPDB

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#38bdf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3a2a4c,stroke:#c084fc,color:#e2e8f0

Color	Meaning
Purple (nodes)	Async processing

New components:

Query Logger: Lightweight service that captures every completed search query and publishes to the event stream. Fire-and-forget, doesn’t affect search latency.
Kafka (event stream): Durably stores the raw query event stream. Decouples ingestion from processing — if Flink falls behind, events queue up safely.
Flink Aggregator: Consumes query events and computes time-windowed counts (last 1 hour, 24 hours, 7 days). Detects trending queries by comparing current velocity against historical baseline.
Popularity Store (Cassandra): Stores the aggregated counts per query. The Trie rebuild job reads from here to determine which completions rank highest.

Flow:

User completes a search → Query Logger publishes event to Kafka
Flink consumes events in micro-batches (every 30 seconds)
Flink updates sliding-window counts: query_counts[query][1h] += 1
Every 5 minutes, Flink writes updated counts to Cassandra
A periodic Trie Rebuild job (every 15 min) reads top-k queries per prefix from Cassandra
Trie Rebuild produces a new immutable Trie snapshot
Trie Service hot-swaps to the new snapshot (zero-downtime reload)

When something goes viral (a breaking news event, a product launch), we can’t wait 15 minutes for the next Trie rebuild. We need a fast path that injects trending queries into suggestions within minutes.

flowchart TD
    USER["User Browser"]:::client
    LB["Load Balancer"]:::edge
    TRIE["Trie Service"]:::service
    CACHE["Redis Cache"]:::data
    QLOG["Query Logger"]:::service
    STREAM["Kafka"]:::async
    AGG["Stream Aggregator"]:::async
    POPDB[("Popularity Store")]:::data
    TREND["Trending Detector"]:::async
    HOTCACHE["Trending Cache<br/>(Redis Sorted Set)"]:::data

    USER -->|"1. Type prefix query"| LB
    LB -->|"2. Forward to trie svc"| TRIE
    TRIE -->|"3. Lookup prefix in cache"| CACHE
    TRIE -->|"4. Check trending cache"| HOTCACHE
    USER -->|"5. Submit full search"| QLOG
    QLOG -->|"6. Publish query event"| STREAM
    STREAM -->|"7. Aggregate popularity"| AGG
    AGG -->|"8. Update popularity store"| POPDB
    STREAM -->|"9. Detect trending spikes"| TREND
    TREND -->|"10. Refresh trending cache"| HOTCACHE

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#38bdf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3a2a4c,stroke:#c084fc,color:#e2e8f0

New components:

Trending Detector: A Flink job that specifically watches for velocity spikes. If a query’s count in the last 5 minutes exceeds 3x its hourly average, it’s marked as trending.
Trending Cache (Redis Sorted Set): Stores currently trending queries with their scores. The Trie Service merges trending results with static Trie results at query time.

Flow:

A breaking event causes thousands of users to search “earthquake delhi” simultaneously
Trending Detector sees the velocity spike within 2-3 minutes
Detector writes “earthquake delhi” to the Trending Cache (Redis sorted set by prefix)
When a user types “earth”, Trie Service fetches static top-10 from Trie AND trending matches from Trending Cache
Merges and re-ranks: trending queries get a boost multiplier in the final score
User sees “earthquake delhi” in suggestions within 3-5 minutes of the event
Trending entries auto-expire (TTL 2-4 hours) — if they persist, the next Trie rebuild incorporates them into the static index

6.5. Core Flows

Flow 1: Prefix Lookup (read path)

sequenceDiagram
    participant U as User Browser
    participant LB as Load Balancer
    participant TS as Trie Service
    participant RC as Redis Cache
    participant TC as Trending Cache

    U->>LB: GET /suggestions?prefix=earth
    LB->>TS: route to any replica
    TS->>RC: GET cache key "earth"
    alt Cache Hit
        RC-->>TS: top-10 suggestions
    else Cache Miss
        RC-->>TS: null
        TS->>TS: Traverse Trie to node e-a-r-t-h and read pre-computed top-10
        TS->>RC: SET "earth" with 10min TTL
    end
    TS->>TC: ZRANGEBYSCORE prefix match "earth*" LIMIT 5
    TC-->>TS: trending matches
    TS->>TS: Merge static + trending and re-rank
    TS-->>LB: top-10 merged suggestions
    LB-->>U: JSON response in 20-50ms

Browser debounces keystrokes (100-150ms) to avoid flooding the server
Request hits any Trie Service replica (stateless — all hold the same snapshot)
Redis cache absorbs ~80% of traffic for popular prefixes
On cache miss, Trie lookup is O(prefix_length) — effectively constant time
Trending Cache merge ensures fresh viral queries appear without waiting for rebuild
Response includes both static and trending results, clearly labeled

Non-obvious failure path: If the Trending Cache (Redis) is down, the Trie Service gracefully degrades — it returns only static Trie results. Suggestions are slightly stale but never unavailable.

Flow 2: Query Ingestion and Count Update (write path)

sequenceDiagram
    participant U as User Browser
    participant QL as Query Logger
    participant K as Kafka
    participant FA as Flink Aggregator
    participant PS as Popularity Store
    participant TB as Trie Builder
    participant TS as Trie Service

    U->>QL: POST /queries (search completed)
    QL->>K: publish query event
    K->>FA: consume batch (every 30s)
    FA->>FA: Update windowed counts
    FA->>PS: Write updated counts every 5min
    TB->>PS: Read top-k per prefix (every 15min)
    TB->>TB: Build new immutable Trie snapshot
    TB->>TS: Hot-swap to new snapshot

Query Logger is fire-and-forget — doesn’t block the search response
Kafka provides durability; if Flink lags, events buffer safely
Flink maintains in-memory state of windowed counts, flushes periodically
Trie Builder runs every 15 minutes, reads aggregated counts, produces a new snapshot
Hot-swap means the Trie Service atomically switches pointers — no downtime, no partial state

Non-obvious failure path: If Flink crashes mid-window, it replays from Kafka offset (exactly-once semantics via checkpointing). Counts may temporarily lag by one window but never lose data.

7. Deep Dives

Deep Dive 1: Trie Data Structure at Scale

The problem: A Trie stores all possible search queries as a tree where each node is a character. For Google with 5B+ unique queries searched historically, a single Trie would need ~200-500GB of RAM. No single machine has that. Plus, one machine can serve ~50K QPS max — Google needs 500K+.

How a Trie works (simple version):

Insert: "system", "systems", "sync", "syntax"

Root
 └── s
      └── y
           ├── s → t → e → m [✓ "system", popularity: 50000]
           │                └── s [✓ "systems", popularity: 12000]
           └── n
                ├── c [✓ "sync", popularity: 8000]
                └── t → a → x [✓ "syntax", popularity: 3000]

Lookup "sy": walk root → s → y → return top-k children:
  ["system" (50K), "systems" (12K), "sync" (8K), "syntax" (3K)]

The key optimization: Pre-compute top-k at each node.

Without pre-computation: lookup “s” → must traverse ALL children (millions of words start with “s”) → too slow.

With pre-computation: at build time, store the top 10 suggestions directly at each node:

Node "sy" stores: top_10 = ["system design", "system", "systems", "sync", "syntax", ...]

Lookup "sy" → jump to node → read pre-computed list → return immediately. O(L) where L = prefix length.
No traversal of children needed at query time.

Bad: Store all queries in a single in-memory Trie on one machine. Works for a dictionary of 1M queries, but with 1B+ unique queries the Trie exceeds available RAM on any single node.

Good: Shard the Trie by first 1-2 characters of the prefix. Prefix “a” goes to shard 1, “b” to shard 2, etc. Each shard fits in memory (~50-100GB) and handles a subset of traffic. The load balancer routes based on the first character.

Great: Pre-compute the top-k suggestions at each Trie node during the build phase (not at query time). This means a lookup doesn’t need to traverse all children to find the best completions — they’re already stored at the prefix node. Combined with sharding, this gives O(L) lookup with zero fan-out.

How the Trie is built (offline, not real-time):

1. Aggregation Job (every 15 min):
   - Reads completed searches from Kafka
   - Counts: {"system design": 50000, "system": 35000, "sync": 8000, ...}

2. Trie Builder:
   - Creates fresh Trie from the counted queries
   - At each node, computes and stores top-10 suggestions sorted by popularity
   - Serializes to a binary format

3. Deploy:
   - Push new Trie snapshot to all shard replicas (blue-green swap)
   - Old Trie keeps serving until new one is loaded
   - Atomic switch: old → new (zero downtime)

Why offline build, not live updates?

Trie is a complex tree — concurrent writes cause locking and fragmentation
Pre-computing top-k at every node requires a full traversal — can’t do incrementally
Read performance is critical (<10ms). Live writes would add locks and slow reads.
15-minute freshness is fine for autocomplete (trending handles real-time separately)

LinkedIn’s Cleo system uses this exact pattern to serve sub-50ms P99 at 100K+ QPS.

flowchart LR
    REQ["prefix: 'sys'"]:::client
    ROUTER["Prefix Router<br/>(route by first char)"]:::edge
    S1["Shard 's'<br/>Trie in memory"]:::service
    NODE["Node s-y-s<br/>top-10 pre-computed"]:::data

    REQ -->|"1. Send prefix"| ROUTER
    ROUTER -->|"2. Route to shard"| S1
    S1 -->|"3. Walk trie to node"| NODE

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#38bdf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

The problem: When breaking news happens (India vs Australia match, earthquake, celebrity news), millions of people start searching for it immediately. If autocomplete only recomputes query counts in hourly batches, trending searches won’t appear as suggestions for up to an hour — users miss the most relevant suggestions during peak interest.

The core question: How do you distinguish “trending right now” from “always popular”? “Weather” is searched 300 times/hour EVERY day — that’s not trending. “India vs Australia score” is normally 100/hour but just spiked to 5000/5min — THAT’S trending. Trending = fast-rising velocity, not high volume.

Bad: Recompute all query counts every hour in batch. Breaking events won’t surface in suggestions for up to an hour — unacceptable for a product like Google.

Good: Sliding window counts in Flink with 5-minute granularity. Compare current-window count against the 24-hour average. If current > 3x average, mark as trending. Latency: ~5 minutes. This works but detection only happens at window boundaries — if a spike starts at minute 2, you don’t know until minute 5.

Great: Use an exponential moving average (EMA) with a decay factor. Each new search event updates the EMA incrementally — no windows to maintain, no batch boundaries. A sudden spike causes the EMA to diverge sharply from the long-term average, triggering a trending alert within seconds.

How EMA works with a concrete example:

Suppose “india vs australia” is normally searched ~100 times/hour (≈0.03/sec baseline).

EMA formula: new_score = α × current_rate + (1 - α) × previous_score
α = 0.3 (decay factor — higher = more responsive to spikes)

Normal day (no match):
  Score hovers around 0.03 — stable, no spike.

Match starts, people start searching:
  Second 1:  5 searches → score = 0.3×5 + 0.7×0.03 = 1.52
  Second 2:  8 searches → score = 0.3×8 + 0.7×1.52 = 3.46
  Second 3: 15 searches → score = 0.3×15 + 0.7×3.46 = 6.92
  Second 4: 20 searches → score = 0.3×20 + 0.7×6.92 = 10.84

  Normal score: 0.03
  Current score: 10.84
  Ratio: 10.84 / 0.03 = 361x above baseline → TRENDING after just 4 seconds!

Why “weather” doesn’t falsely trigger:

"weather" — 300 searches/hour every day (≈0.08/sec baseline):
  Normal score: ~0.08
  Today's score: ~0.08 (same as always)
  Ratio: 0.08 / 0.08 = 1x → NOT trending (no spike, just steady volume)

Why EMA beats sliding windows:

No fixed window boundaries → detects trends in seconds, not at 5-min intervals
Captures velocity (how FAST searches are rising), not just total count
Automatically decays — once the spike subsides, the EMA drops back to normal and the query is un-trended
This is what Twitter uses for its Trends feature

How it integrates with the architecture:

User searches "india vs australia" → logged to Kafka
    ↓
Trending Detector (Flink consumer):
  - Reads every search event from Kafka
  - Updates EMA for that query: score = 0.3 × rate + 0.7 × old_score
  - Compares to 24-hour baseline
  - If score / baseline > 3x → TRENDING
  - Writes to Trending Cache (Redis Sorted Set):
      ZADD trending_queries <score> "india vs australia score"
    ↓
Next user types "ind" in the search bar:
  - Trie returns standard suggestions: ["india population", "india news", ...]
  - Trending Cache returns: ["india vs australia score" (score: 10.84)]
  - MERGE: trending results get boosted to the top of suggestions
  - User sees: "india vs australia score" as first suggestion ✅

Deep Dive 3: Caching Strategy and Cache Stampede Prevention

The problem: Users type fast. Each keystroke triggers a suggestion request. “system design” = 13 keystrokes = 13 requests in 3 seconds from ONE user. With 100K concurrent users typing, that’s 500K+ requests/sec hitting the Trie service. Even with sharding, this is expensive.

Why caching helps: Most prefixes are repeated constantly. “how”, “what”, “why”, “best” are typed thousands of times per second by different users. If we cache these results, 80%+ of requests never hit the Trie service.

Bad: No caching — every keystroke hits the Trie service. Works at low scale but at 100K QPS, even an O(L) lookup per request means high CPU across many shards.

Good: Cache the top 10K prefixes in Redis with a 10-minute TTL. ~80% of lookups hit the cache. But when a hot key expires, thousands of requests simultaneously miss and slam the Trie service (cache stampede).

Concrete example of cache stampede:

Time 0:00 — "how" is cached in Redis (TTL = 10 min)
Time 9:59 — 5000 users type "how" per second, all served from cache. Trie service idle.
Time 10:00 — TTL expires. Redis key "prefix:how" disappears.
Time 10:00.001 — 5000 requests arrive. ALL miss cache. ALL hit Trie service simultaneously.
                  Trie service: 50 QPS normal → sudden 5000 QPS spike → overloaded, timeouts.

Great: Use probabilistic early expiration (cache stampede protection):

Each cached entry stores: { suggestions: [...], expiresAt: 10:00:00 }

Request arrives at 9:59:45 (15 seconds before expiry):
  - Generate random number: rand() = 0.85
  - Threshold: (time_remaining / TTL) = 15/600 = 0.025
  - 0.85 > 0.025 → serve from cache normally (99% of requests)

Request arrives at 9:59:55 (5 seconds before expiry):
  - Generate random number: rand() = 0.02
  - Threshold: 5/600 = 0.008
  - 0.02 > 0.008... but close! Some requests will trigger early refresh.

ONE lucky request gets selected → fetches fresh data from Trie → updates cache with new TTL
All other requests continue serving stale (but valid) data during this refresh.

Result: cache never expires for everyone simultaneously. One request refreshes proactively.

Additionally — request coalescing (single-flight):

If cache is empty and 100 requests arrive for “how” simultaneously:

WITHOUT coalescing: 100 requests all hit Trie service → 100 duplicate lookups
WITH coalescing: first request goes to Trie, other 99 wait for that ONE response, all get the same result

Implementation (Go's singleflight / Java's CacheLoader):
  lock = mutex_per_key["prefix:how"]
  if lock.tryAcquire():
      result = trie.lookup("how")
      cache.set("prefix:how", result, TTL=10min)
      lock.release()
  else:
      result = lock.waitForResult()  // wait for the one ongoing fetch
  return result

Deep Dive 4: Handling Short Prefixes (Hot Partition Problem)

The problem: When you shard the Trie by first character, some shards get crushed. In English, words starting with “s” are 3x more common than words starting with “x” or “z”. The “s” shard gets 3x the traffic — it’s a hot partition.

Concrete data (English word frequency by first letter):

Letter: s → 12% of all queries
Letter: c → 8%
Letter: p → 7%
Letter: a → 7%
...
Letter: x → 0.2%
Letter: z → 0.3%

If you shard A-Z (26 shards), the “S” shard handles 12% of ALL traffic while “X” handles 0.2%. That’s 60x imbalance.

Bad: Shard by first character. The prefix “s” gets 10x more traffic than “x” because common words disproportionately start with certain letters. Shard “s” becomes a hot partition.

Good: Shard by first 2 characters (“sa”, “sb”, …, “sz”). More even distribution (676 possible combinations), but still some skew — “st” (start, stop, store, stock, stream…) is hotter than “sx”.

Great: Weighted consistent hashing based on observed traffic per prefix range:

Control Plane monitors QPS per shard:
  "sa-sf" shard: 8000 QPS (hot — lots of "search", "service", "system")
  "xa-xz" shard: 200 QPS (cold)

Action: split the hot shard further:
  "sa-sc" → Shard A (with 3 replicas)
  "sd-sf" → Shard B (with 3 replicas)
  "xa-xz" → Shard C (with 1 replica — doesn't need more)

The router's routing table updates:
  prefix "sa..." → Shard A (any of 3 replicas)
  prefix "se..." → Shard B (any of 3 replicas)
  prefix "xi..." → Shard C

Result: hot prefixes get more shards AND more replicas. Cold prefixes share resources.

Key insight: The routing isn’t static. A control plane continuously monitors QPS per shard and rebalances by splitting hot ranges or adding replicas. This is how Google’s Bigtable tablets auto-split on hot keys.

Deep Dive 5: Data Collection and Privacy

The problem: To build autocomplete suggestions, you need to know what people search for. But search queries are deeply personal — medical conditions, financial problems, relationship issues. Logging everything with user identity creates a privacy liability.

The tension: You NEED aggregate counts (“how many people searched for X?”) to rank suggestions. But you DON’T need to know WHO searched for WHAT.

Bad: Log every keystroke with full user identity. Privacy nightmare (GDPR requires deletion on request, you’d have to find and purge individual keystrokes across petabytes) and generates 10x more data than needed (most keystrokes are partial, only completed queries matter).

Good: Only log completed queries (when the user hits Enter or clicks a suggestion). Anonymize after 24 hours by stripping user IDs and keeping only aggregate counts:

Raw log (first 24 hours):
  { userId: "user_123", query: "diabetes symptoms", timestamp: "..." }

After 24 hours (anonymized):
  { query: "diabetes symptoms", count: 4521 }  ← no userId, just aggregate

Why keep userId for 24 hours? To deduplicate (same user searching same thing 10 times = count as 1).
After dedup, you don't need the userId anymore.

Great: Differential privacy at the aggregation layer — add calibrated random noise to query counts before they’re used for ranking:

True count for "depression help": 847 searches today
Noise added: random(±50)
Published count used for ranking: 847 + 23 = 870 (or 847 - 31 = 816)

Why this matters:
  - If count = exactly 1, you can infer ONE specific user searched it
  - With noise, count=1 might actually be 0 (noise added) → can't determine if anyone searched it
  - At high counts (1000+), noise is negligible → rankings stay accurate
  - At low counts (1-10), noise dominates → individual privacy protected

Apple’s approach (local differential privacy):

Noise is added ON THE USER’S DEVICE before sending to the server
Server never sees the true query — only a “noisy” version
Used for emoji suggestions, QuickType keyboard
Even stronger guarantee: server literally cannot know what any individual searched

GDPR compliance checklist:

Right to be forgotten → delete userId from raw logs on request (within 24h of anonymization, there’s no userId left anyway)
Data minimization → log only completed queries, not keystrokes
Purpose limitation → counts used only for suggestion ranking, not advertising
Retention limits → raw logs deleted after 24h, aggregates kept for ranking

7.5. Design Self-Audit

Dedicated search index? The Trie IS the search index — purpose-built for prefix lookups. No need for a general-purpose search engine for this specific use case.
Stale reads after writes? Yes — a newly searched query takes 3-15 minutes to appear in suggestions. Acceptable trade-off documented in FR3 (trending path reduces this to 3-5 min for viral queries).
Single points of failure? Trie Service is replicated (multiple shards, each with replicas). Redis Cache has replicas. Kafka is multi-broker. Flink uses checkpointed state. No single-machine SPOF.
Dead-letter / reconciliation? Kafka consumer offset tracking + Flink checkpoints. If processing fails, events replay from last checkpoint. No silent data loss.
Cost at scale? The Trie is in-memory — at 1B unique queries with top-k pre-computed, expect 200-500GB total across shards. At cloud memory pricing (~$10/GB/month), that’s $2K-5K/month for the Trie tier. Affordable for any company running a search product at scale.

8. Final Architecture

flowchart TD
    USER["User Browser"]:::client
    CDN["CDN<br/>(static prefix cache)"]:::edge
    LB["Load Balancer"]:::edge
    TRIE["Trie Service<br/>(sharded replicas)"]:::service
    CACHE["Redis Cache<br/>(hot prefixes)"]:::data
    HOTCACHE["Trending Cache<br/>(Redis Sorted Set)"]:::data
    QLOG["Query Logger"]:::service
    STREAM["Kafka"]:::async
    AGG["Stream Aggregator"]:::async
    TREND["Trending Detector"]:::async
    POPDB[("Popularity Store<br/>Cassandra")]:::data
    BUILDER["Trie Builder<br/>(periodic)"]:::async

    USER -->|"Type prefix query"| CDN
    CDN -->|"Cache miss"| LB
    LB -->|"Forward to trie svc"| TRIE
    TRIE -->|"Lookup prefix in cache"| CACHE
    TRIE -->|"Check trending cache"| HOTCACHE
    USER -->|"Submit full search"| QLOG
    QLOG -->|"Publish query event"| STREAM
    STREAM -->|"Aggregate popularity"| AGG
    STREAM -->|"Detect trending spikes"| TREND
    AGG -->|"Update popularity store"| POPDB
    TREND -->|"Refresh trending cache"| HOTCACHE
    BUILDER -->|"Rebuild trie from data"| POPDB
    BUILDER -->|"Push new trie version"| TRIE

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#38bdf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
    classDef async fill:#3a2a4c,stroke:#c084fc,color:#e2e8f0

How it works end-to-end (query path):

User types a prefix — keystroke sent to CDN (static prefix cache for top queries)
CDN cache miss — request routed through Load Balancer to the Trie Service (sharded replicas)
Trie Service looks up suggestions — checks Redis Cache for hot prefixes, falls back to in-memory trie traversal
Trending Cache checked — Redis Sorted Set injects trending/breaking queries that haven’t aged into the main trie yet
Top-K suggestions returned — ranked by popularity score, served in <50ms

How it works end-to-end (update path):

Query Logger captures searches — every completed search published to Kafka
Stream Aggregator tallies counts — rolling window aggregation updates Cassandra (Popularity Store)
Trending Detector identifies spikes — velocity detection flags sudden surges, updates Trending Cache in real-time
Trie Builder rebuilds periodically — batch job reads Popularity Store, constructs new trie version, swaps into Trie Service (blue-green)

Written by SystemCraft Interview Prep Platform

Free system design, LLD, and DSA resources built by engineers who went through the interview grind at Indian and international tech companies.

Designing Search Autocomplete / Typeahead

1. Understanding the Problem

1.5. Naive First Cut

1.7. Prior Art We’re Drawing From

Technology Choices

2. Functional Requirements

Core (Top 3)

Below the Line

3. Non-Functional Requirements

Core

Below the Line

4. Core Entities

5. API / System Interface

6. High-Level Design

FR1: Return top-k suggestions for a prefix

FR2: Rank by popularity and freshness

FR3: Update suggestions with new trending queries

6.5. Core Flows

Flow 1: Prefix Lookup (read path)

Flow 2: Query Ingestion and Count Update (write path)

7. Deep Dives

Deep Dive 1: Trie Data Structure at Scale

Deep Dive 2: Real-time Trending Detection

Deep Dive 3: Caching Strategy and Cache Stampede Prevention

Deep Dive 4: Handling Short Prefixes (Hot Partition Problem)

Deep Dive 5: Data Collection and Privacy

7.5. Design Self-Audit

8. Final Architecture

Discussion