Handbooks / System Design Case Studies / Chapter 4

Design Search Autocomplete

12 pages · ~16 min✓ Reviewed

Builds on Design a Distributed Key-Value Store. Next up: Design a Notification System.

System Design Case StudiesPage 1

Problem Statement, Scope and Requirements

1. Problem and Scope

Running example: Search Autocomplete (typeahead) for a search box handling 10B searches/day.

Input: a prefix typed so far, e.g. wor
Output: the top 5 ranked completions, refreshed on every keystroke
Ranked by popularity, not alphabetical order

Prefix match on the typed text
Return 5 suggestions per prefix
English only
No personalization in v1
Offensive terms filtered out of results

2. Non-Functional Targets

Property	Target	Meaning
Latency	p99 under 100 ms	End to end, keystroke to dropdown
Availability	99.99%	About 52 min of downtime per year
Consistency	Eventual	New trends visible within 15 min

Stale suggestions are acceptable; a slow or missing dropdown is not
Strong consistency is not needed for suggestions

System Design Case StudiesPage 2

High-Level Architecture

1. Two Paths (Search Autocomplete)

Search Autocomplete splits into a read path that serves prefixes and a write path that rebuilds the trie. They meet only at the snapshot.

	Read path	Write path
Parts	query service, cache, trie	log, aggregate, build trie
Job	prefix → top 5	searches → new trie

System Design Case StudiesPage 3

Trie with Top-K Suggestions

1. Responsibility and the Fix

Maps a typed prefix to its 5 best completions in O(L), L = prefix length (Search Autocomplete).

Naive: walk to the prefix node, then DFS every descendant: O(L + N)
Too slow at ~1M peak QPS: N can be millions of nodes
Fix: store the top-k list on every node, so lookup is O(L) and k = 5 is constant
Cost: ~k x memory per node, paid once at build time

System Design Case StudiesPage 4

Data Collection Pipeline

1. Responsibility and Flow

Turn raw search events into aggregated query counts
Output feeds the trie builder for Search Autocomplete
Kafka is partitioned by query hash, so one query always lands on one aggregator

Write path, event to trie

1Client logone event per search
2Kafkapartition by hash(query)
3Stream aggregator1-min windows
4Hourly / weekly tablescounts per query
5Trie builderrebuild every 15 min

System Design Case StudiesPage 5

Ranking: Frequency and Recency

Running example: Search Autocomplete at 10B searches/day, top 5 completions per prefix.

1. Score and Decay

Score = frequency over a decay window, not a lifetime total
Raw all-time count buries new trends under old giants
Exponential decay: score = sum(count_i x 0.5^(age_i / half-life))
Half-life = 7 days: a search from 7 days ago counts half, 14 days ago a quarter

2. The Blend

System Design Case StudiesPage 6

Suggestion Query Service

1. Responsibility

Running example: Search Autocomplete, ~460K QPS avg, ~1M QPS peak, p99 under 100 ms end to end.

Stateless service: any instance can answer any prefix
Normalizes the prefix: lowercase, trim, collapse spaces
" World CUP " becomes world cup
Queries the right trie shard and returns the top 5

2. Request Flow

Requestraw prefix
Normalizelower, trim, collapse
Local LRUhit: return now
Routefirst 2 characters
Top 5from trie shard

System Design Case StudiesPage 7

Caching at the Edge

1. Responsibility and Layers

Search Autocomplete at ~1M peak QPS: the edge answers the hottest prefixes, so the origin sees only ~150K QPS.

A request falls through four layers

1Browser cachemax-age 300
2CDN edgeTTL 5 min
3Service local LRUin-process
4Trielookup under 1 ms

Browser TTL is capped at 300 s: a CDN purge cannot clear browsers
Most requests stop at the browser or CDN and never reach the origin
Only a miss at every layer reaches the trie

System Design Case StudiesPage 8

Sharding the Trie

Sharding the Trie (Search Autocomplete): split a ~50 GB trie across 10 shards, each served by 3 replicas.

1. Why Shard

Split the ~50 GB trie when one node's RAM or QPS cannot hold it
Memory: ~50 GB / 10 shards = ~5 GB per shard
QPS (est.): ~150K origin QPS / 10 shards = ~15K per shard
One prefix is served by one shard, so its top-5 is precomputed there

2. Picking the Split

System Design Case StudiesPage 9

Filtering Offensive Terms

1. Responsibility and Layers

Search Autocomplete never suggests slurs, adult or harmful terms
A flagged term must disappear within minutes (under 5 min)
Two layers: build-time filter, then serve-time filter on the output
Build-time = blocklist + ML classifier, before queries enter the trie

Search logsraw queries
Build filterblocklist + ML
Trietop-5 per node
Serve filterversioned blocklist
Clientsafe top 5

System Design Case StudiesPage 10

Scaling, Failure Handling, Trade-offs and Interview Questions

1. Scaling and Degradation

Search Autocomplete at ~1M peak QPS: fix each bottleneck with its own lever, and fail soft.

Bottleneck	Lever	Example
Read QPS	Add replicas	3 replicas per shard
Memory	Add shards	~50 GB / 10 shards = ~5 GB each

System Design Case StudiesPage 11

Cheatsheet: Typeahead Numbers and Rules

1. Scale and Trie (Search Autocomplete)

Number	Value
Peak load	~1M QPS (~460K avg x ~2.2)
Latency	p99 under 100 ms end to end
Trie size	~50 GB in memory
Shards	10 shards x 3 replicas = 30 servers
Per shard	50 GB / 10 = ~5 GB each

System Design Case StudiesPage 12

Check yourself

Both 'earth day' (weekly decayed count 500K, 0 in the last hour) and the new 'earthquake today' (weekly 200K, 200K in the last hour) match the prefix 'earth'. With score = 0.7 x weekly + 0.3 x last hour, which is suggested first?

'earth day' scores 0.7 x 500K + 0.3 x 0 = 350K
'earthquake today' scores 0.7 x 200K + 0.3 x 200K = 200K
So 'earth day' ranks first, even though 'earthquake today' is the one trending
The new query overtakes only if its traffic is sustained, since its weekly part keeps growing with each hour

A teammate wants to increment the trie on every search, so trends show instantly. What goes wrong at this scale?

Data	Estimate	Where
Unique queries	100M x 50 B	~5 GB raw
Trie with top-5 per node	~50 GB	In memory, ~10x raw

	Offline rebuild	Online per-query update
Cadence	every 15 min	on every search
Trie writes	none on live nodes	~115K/s avg on live nodes
Read impact	none, swap a pointer	locks contend with ~1M read QPS
Rollback	keep the old snapshot	hard
Freshness	up to 15 min stale	instant

	Naive DFS	Top-k per node
Lookup	O(L + N)	O(L)
Work per request	visits N descendants	reads k = 5 entries
Memory	1x	~k x per node

Metric	Target
Lookup p99	under 1 ms
Trie memory per shard	~5 GB after sharding into 10 shards
Empty-result rate	alert on a rise
Snapshot age	about 15 min (rebuild interval)

	Events/day	Avg rate	Size/day
Raw	~10B	~115K/s	~1 TB
Sampled 1%	~100M	~1.2K/s	~10 GB

Metric	Target
Consumer lag	under 1 min
Events dropped	alert on any sustained rise
Build duration	under 10 min
Pipeline freshness	event to trie within the 15-min rebuild

Query	Weekly	Last hour	Score
world cup	1M	0	0.7 x 1M = 700K
earthquake today (new)	~0	200K	0.3 x 200K = 60K

Hours	0.7 x weekly	+ hourly	Score	vs 700K
1	140K	60K	200K	below
3	420K	60K	480K	below
4	560K	60K	620K	below
5	700K	60K	760K	above

Metric	Target
QPS per instance	~20K
p50 / p99 latency	track both, p99 under 100 ms end to end
Local LRU hit rate	track; misses go to the shard
Error rate	under 0.01%

Metric	Target
Edge hit ratio	above 85%
Origin QPS	~150K
Bytes per response	under 1 KB

Scheme	Locality	Hot prefixes	Verdict
Range by first letters (a-c, d-f...)	good	's' and 'c' far hotter than 'x'	simple, but skewed
Range with measured shard map	good	splittable	preferred
Hash of full prefix	lost	hard to split	avoid

Metric	Target
QPS per shard	~15K (est.), watch hottest
Memory per shard	~5 GB
Skew ratio (max/avg)	under 2x
Replica lag	one snapshot version at most

blocked_terms	Holds
`term`	normalized word or phrase
`category`	slur, adult, harmful
`added_at`	timestamp; drives time-to-block
`source`	user report, ML classifier, human review

Trade-off	Option A	Option B
Freshness vs build cost	15 min: fresh trends, many builds	1 h: cheaper, trends lag
Top-k memory vs lookup speed	Top-5 per node: ~k x memory, O(L)	No top-k: small, DFS O(L + N)
Sampling vs long-tail accuracy	1 in 100: 1 TB to ~10 GB/day	All events: exact tail, huge cost

Layer	TTL	Note
Browser	max-age 300	purge cannot clear it
CDN edge	5 min	hit ratio above 85%
Service LRU	local	then trie, under 1 ms

Design Search Autocomplete

1. Problem and Scope

2. Non-Functional Targets

1. Two Paths (Search Autocomplete)

1. Responsibility and the Fix

1. Responsibility and Flow

1. Score and Decay

2. The Blend

1. Responsibility

2. Request Flow

1. Responsibility and Layers

1. Why Shard

2. Picking the Split

1. Responsibility and Layers

1. Scaling and Degradation

1. Scale and Trie (Search Autocomplete)

3. Scale and Storage

2. Read Path and Write Path

3. Offline Rebuild vs Online Update

4. Latency Budget

2. Node Layout and Compression

3. API

4. Failure and Metrics

2. Log Record and Volume

3. Failure and Metrics

3. Example: world cup vs earthquake today

4. Mistakes and Filters

3. Response and Client

4. Failure and Metrics

2. Skew and Cache Key

3. Failure Handling

4. Metrics

3. Serving Layout

4. Failure and Metrics

2. Blocklist Matching

3. Urgent Removal and Data

4. Failures and Metrics

2. Trade-offs and Personalization

3. Interview Questions

2. Ranking and Pipeline

3. Edge and Safety