Case study

Design Typeahead / Autocomplete

Return top-5 query suggestions within 50ms as users type on a search box with 10M+ terms.

trieprefix searchranking

Requirements

Functional: given prefix (≥ 2 chars), return top 5 suggestions ranked by popularity
Support multiple locales; optional personalized ranking
Non-functional: p99 latency < 50ms; 50K QPS peak
Freshness: trending queries reflected within 5 minutes
Scale: 10M unique terms; 500M searches/day

Back-of-envelope Estimation

Metric	Calculation	Result
Search/day	500M	Given
Typeahead QPS	500M × 5 keystrokes / 86,400	~29K/sec avg
Peak QPS	2× avg	~50K/sec
Trie size (10M terms × 20 chars)	Compact trie ~ 100 MB	Fits in memory per node
Bandwidth	50K × 500 B response	~25 MB/sec

API Design

Endpoint	Description
GET /v1/suggest?q=app&limit=5&locale=en	Returns [{ term, score, category }]
POST /v1/events/search	Log selected query for popularity aggregation (async)
Internal: rebuild index	Triggered hourly from aggregated counts

Data Model

Store	Content
query_counts	term, locale, count_24h, count_7d (ClickHouse)	Aggregation source
trie_snapshot	Serialized trie with top-K at each node	Served from memory
personal_history	user_id → recent queries (Redis)	Optional personalization boost

High-level Design

Suggest path

Client ──► CDN/LB ──► Suggest Service (in-memory trie per locale)
                              │
                    Hourly: Analytics ──► Index Builder ──► deploy new trie snapshot
                              │
                    Real-time: Kafka ──► trending boost overlay (Redis)

Deep Dive: Trie with Top-K

Each trie node stores the top 10 terms in its subtree by global frequency. Lookup walks prefix in O(k) chars, returns precomputed top-5 — no traversal of full subtree. Rebuild trie offline; hot-swap atomically via double buffering.

Alternative: Elasticsearch completion suggester

ES works for moderate scale. Custom in-memory trie wins at 50K QPS with predictable sub-10ms latency.

Bottlenecks at Scale

Prefix 'a' or 's' — extremely wide nodes; cap by min prefix length (2–3 chars)
Trending spike ('election') — real-time overlay layer merges with static trie
Memory per locale × region — shard suggest servers by locale
Stale suggestions after viral event — 5-min streaming update path for top 1000 terms

Failure Modes & Monitoring

SLO	Target
Suggest p99	< 50ms
Availability	99.9%
Index freshness	< 5 min for trending

Degrade to cached popular queries if trie reload fails. Monitor empty-result rate, latency by prefix length, index build duration.

System Design