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.

Client Users DNS Route 53 Load Balancer ALB API Servers Fargate Trie Cache ElastiCache Trie DB DocumentDB AT LIMIT Query Logs Kinesis AT LIMIT Rebuild Schedule EB Scheduler Log Aggregator EMR AT LIMIT Trie Builder Lambda AT LIMIT

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

  1. Client
  2. DNS
  3. Load Balancer
  4. API Servers
  5. Trie Cache
  6. Trie DB

Log query

  1. Client
  2. DNS
  3. Load Balancer
  4. API Servers
  5. Query Logs

Rebuild trie

  1. Rebuild Schedule
  2. Log Aggregator
  3. Trie Builder
  4. Trie Cache

Other interview practice

Open this architecture in SysPad · All examples