SysPad › Examples › Search autocomplete
Search autocomplete
API servers read from an in-memory Trie Cache (falling through to a Trie DB); every query is logged and periodically re-aggregated into a rebuilt trie by an offline, scheduled Trie Builder.
A very high-QPS read path decoupled from a slow, periodic trie-rebuild pipeline fed by the same query stream - the reads never wait on the rebuild.
- Load: 20,000 req/sec
- First to saturate: Query Logs
- Estimated cost: $19k/mo
How it works
- Trie Cache
- The prefix trie held in memory. Autocomplete is read almost every keystroke, so a ~97% hit rate here is what keeps the design affordable at tens of thousands of QPS.
- Query Logs
- Every query is appended here. The read path fire-and-forgets onto this stream; it is the raw material the trie rebuild is computed from.
- Log Aggregator
- A scheduled batch job that rolls the query logs into prefix frequencies: the "rebuilt periodically" step, run offline so it never touches the query latency.
Request flows
Get suggestions
- Client
- DNS
- Load Balancer
- API Servers
- Trie Cache
- Trie DB
Log query
- Client
- DNS
- Load Balancer
- API Servers
- Query Logs
Rebuild trie
- Rebuild Schedule
- Log Aggregator
- Trie Builder
- Trie Cache
Lessons for this architecture
- Modelling users and traffic entry points
- How Route 53 works
- How Application Load Balancer works
- How ECS Fargate works
- How Amazon ElastiCache works
- How DocumentDB works
- How Kinesis Data Streams works
- How Amazon EMR works
- How AWS Lambda works
Worked step by step
The same interview question, built up one twist at a time, with a simulation at each stage.