Case study: Typeahead / autocomplete
Design a sub-50 ms search typeahead system: in-memory radix tries with precomputed top-k completions per node, front-tier prefix caching, and asynchronous stream aggregation.
35 min9 steps
By the end you can
- Estimate keystroke QPS, compiled trie memory footprint, and query-log sampling rates
- Explain why caching top-k completions at every trie node turns subtree scans into O(L) lookups
- Separate the sub-50 ms read path from asynchronous query-log aggregation and trie snapshot swaps
- Predict system behaviour during breaking-news hotspots, cache restarts, and aggregator pauses
Pin down what you are building
Top 5-10 completions
- Rank popularity/recency; log completed queries; block unsafe phrases
Server p99 <50ms
- Round trip <100ms; eventual popularity; fast safety updates
Work out the numbers
Keystroke reads/s
350k
5B / 6 / 86,400; ~700k peak
Query writes/s
58k
5B/day; ~5,800/s at 10% sample
Compiled trie
25 GB
50M prefixes / 500 B; RAM replicas
Design the API
GET /v1/suggest?q={prefix}&limit=10&lang=en
- Cap prefix ~50 chars; max-age=60
POST /v1/queries
- query, locale, ts; debounce 50ms; cancel obsolete requests; session cache
Model the data
Naive trie
- O(L) prefix walk + O(V) descendant scan/sort
Materialised top-k
- Every node/pfx:key holds winners; O(L) trie or O(1) hash; radix compression
Draw the high-level architecture
Order the steps that turn completed user searches into updated typeahead suggestions.
- 1The user presses Enter on a completed search query
- 2Stream aggregators accumulate time-decayed query frequencies over tumbling windows
- 3The API publishes the sampled query event to the query log queue and returns 200 immediately
- 4In-memory trie shards load the updated prefix entries without blocking concurrent readers
- 5The trie builder recomputes top-k lists for affected prefixes and applies the safety blocklist
Deep dive: time decay, trending overlays, and shard balance
Fresh ranking
- score = old / 0.95 + window count; hourly snapshot + trending overlay
Balanced serving
- Replicate short prefixes; hash longer ones; serving-time safety blocklist
Evaluate alternatives
typeahead-scan
- Saturates; <85% fixture goodput
SQL LIKE prefix
- Still scans unless top-k materialised
Local history
- Free repeat suggestions; merge with global winners
Run the failure scenarios
Inject
trending-event: 40%
Observe
Hot prefix requests coalesce
Result
prefixcache sustains >99% fixture goodput
Inject
cache-flush: 300ms
Observe
Fixture requests fail during kill
Result
Empty cache rapidly refills Zipf head
Inject
aggregator-down: 1s
Observe
querylog queues completed searches
Result
Cached/trie reads stay available; rankings age
Wrap up and self-assess
Trade
- Memory for bounded lookup; async aggregation for freshness lag
Safety
- Serving-time blocklist bypasses slow snapshot cycle
Answer this step to continue.