Design search autocomplete (typeahead) for an e-commerce site with 50,000 queries per second at peak.
Short answer
Precompute top suggestions per prefix from query logs and catalog data into an in-memory structure (trie or prefix map) served from many replicas and edge caches, update it in batches, personalize lightly at request time, and keep latency under ~50 ms with aggressive caching and debouncing on the client.
Detailed answer
- Data: aggregate query logs (frequency, recency, conversion) and catalog terms; filter offensive or zero-result terms.
- Offline build: compute top-k suggestions per prefix (e.g. up to 10 characters) in a batch job (Spark) hourly/daily; publish as a versioned snapshot.
- Serving: in-memory prefix map/trie per node, loaded from snapshots; replicate widely; cache at CDN for short prefixes (very hot).
- Online blending: trending terms from a streaming job; light personalization (recent searches) merged client-side or in the service.
- Client: debounce keystrokes (e.g. 100–150 ms), cancel stale requests.
- Alternatively use search engine completion suggesters (OpenSearch/Elasticsearch completion fields) for smaller scale.
Follow-up questions
- How do you handle typos? (Fuzzy matching with edit distance on the server or a spell-correction layer.)
- Multi-language support? (Separate indexes per locale; normalization.)
What the interviewer expects
Offline precomputation, low-latency serving, caching, update strategy and client-side optimizations.
Common mistakes to avoid
Running LIKE 'prefix%' queries against the product database on every keystroke.