System Design Lab
Search autocomplete is a read-only top-k prefix lookup on a tight latency budget, fed by a separate aggregation pipeline — not a live write path.
Change keystroke query rate, vocabulary size, how many suggestions you return, the p99 latency budget, how fresh completions must be, and regions. The design moves from one in-memory trie to caching the hottest prefixes, sharding the trie by prefix, a streaming log-aggregation pipeline for freshness, and per-region personalization.
Guided walkthrough
Reason about it one step at a time
Takeaway
Normal evolution scenarios
Click left to right for the intended demo path. Each card changes the workload inputs.
Recommended shape
Current architecture path
Clients
Client fires a prefix lookup on every keystroke and logs the chosen query
Edge / API
API gateway fans prefix lookups to the trie and forwards chosen queries to the log
Prefix cache serves completions for the most common prefixes without touching the trie
Trie service
Trie service walks the prefix tree and returns the top-k stored at the matched node
Trie shards split the prefix tree across nodes so a huge vocabulary fits and scales
Aggregation
Aggregator counts query frequencies and recomputes the top-k written back into the trie
Stream processor incrementally updates counts from the live log so trends surface within minutes
Query log
Query log durably records every chosen query as the source of truth for ranking
Bottlenecks
Lookup vs latency budget
Trie memory
Hot-prefix cache pressure
Update / freshness lag
Shard fan-out
Why this changes
Decision tradeoffs
Source-backed rules
These are the durable system-design claims behind the model. The exact slider thresholds are deliberately labeled as teaching assumptions.
A trie answers prefix queries in time proportional to the prefix length
A trie keys on the characters of the prefix, so a completion lookup is O(prefix length) and independent of how many queries are stored, unlike scanning the vocabulary.
NIST Dictionary of Algorithms and Data StructuresQuery popularity is heavily skewed, so a small cache covers most lookups
Search query streams follow a power-law: a small set of popular queries accounts for a large fraction of traffic, so caching the hottest prefixes absorbs most reads.
Baeza-Yates et al., "The Impact of Caching on Search Engines" (SIGIR)Precompute and store top-k at each node instead of ranking at query time
Maintaining the ranked completions ahead of time (e.g. in a sorted set per prefix) turns a lookup into a read of an already-sorted top-k rather than an on-the-fly aggregation.
Redis Docs — autocomplete with sorted setsStreaming aggregation produces low-latency updates from an unbounded log
A stateful stream processor maintains running aggregates over the query log so updated top-k counts are available within seconds-to-minutes instead of waiting for a batch rebuild.
Apache Flink DocumentationTeaching assumptions
- Completions are modeled as cacheable prefix lookups; cache coverage is approximated from query-popularity skew, not a measured hit rate.
- Single-node read throughput and in-memory trie capacity are conservative teaching numbers, not vendor limits.
- The trie is read-only on the hot path; freshness comes only from the separate aggregation pipeline, so search latency and update lag are independent budgets.