Design Search Autocomplete for a Product Catalog
Fast recall
Quick revision
Core answer
Prefix-search data structures, latency budget per keystroke, ranking by popularity, and cache strategy for a power-law traffic distribution.
Using `LIKE 'query%'` on a relational DB (doesn't scale past 100K products), or treating it as a generic search problem and bolting on Elasticsearch without a prefix index.
Justify the Redis prefix index for the hot path, edge n-gram tokenization in Elasticsearch for the cold path, popularity-weighted ranking with personalization, typo tolerance via Levenshtein at the second tier, and CDN caching for the head of the prefix distribution.
Interview-ready guide
Interview answer
Clarifying questions I'd ask first
- Suggestion source — product names only or also popular search queries from other users?
- Typo tolerance from day one?
- Personalization (recent searches, location)?
- Multi-locale or single?
- Rich suggestions (image + price) or just text?
Assumptions for this design
10 million products, multi-locale, 30K autocomplete QPS average / 100K peak, sub-50ms p99 server-side, sub-100ms end-to-end. Updates within 5 minutes of catalog changes. Top 10 suggestions returned. Personalization optional.
Quick capacity check
- 100K peak QPS, but power-law distribution means top 10K prefixes drive ~80% of traffic
- CDN with 60s TTL absorbs that 80% — origin sees ~20K QPS
- Redis storage: ~80M unique prefixes per locale at ~500 bytes each = ~40 GB Redis per locale
- Latency budget: Redis 5ms + optional ES 20ms + hydration 10ms + personalization 5ms = under 50ms
The central architectural decision — two-tier index
- Hot tier: Redis sorted set per
(locale, prefix), members are product IDs, scores are popularity — one ZREVRANGE call returns top 10 - Cold tier: Elasticsearch with edge n-gram tokenizer for typo tolerance and richer ranking
- Most queries are served from Redis only; ES kicks in when prefix yields <3 results or query looks like a typo
Why one ZSET per prefix, not a trie
- Trie in Redis would mean multiple node fetches per query — latency killer
- Sorted set lookup is one call, O(log n)
- Cost is storage duplication (each suggestion appears under each of its prefixes), which is acceptable
Why edge n-gram in Elasticsearch
- Indexes every prefix of every token at write time, so prefix queries become term lookups
- Gives us typo tolerance via fuzziness parameter
- Index is larger but query latency is consistent in the 10-20ms range
High-level shape
- Read: browser → CDN → (on miss) Autocomplete Service → Redis prefix ZSET → hydrate top 10 → return
- Read with typo: same path, but if Redis has fewer than 3 results, also query ES, merge, dedupe
- Ingest: Catalog CDC + search-event stream → Kafka → Index Builder expands prefixes and writes to both Redis and ES
- Popularity pipeline: Spark/Flink job runs every 15 minutes, computes scores from clicks/conversions with time decay, updates ZSET scores
Read algorithm step by step
- 1Redis:
ZREVRANGE ac:{locale}:{prefix} 0 9 WITHSCORES - 2If results <3 or typo heuristic: ES
matchquery withfuzziness: AUTO, merge - 3If user_id present: personalization re-rank
- 4Hydrate: pipelined Redis HGETs for product metadata
- 5Return
LLD — clean abstractions
PrefixIndexinterface (RedisPrefixIndex impl; could swap for in-memory FST)FuzzyIndexinterface (Elasticsearch impl; could swap for vector search)TypoDetectordecides whether to consult fuzzy indexPersonalizationRankeris its own collaborator, absent for anonymous callsIndexBuilderandPrefixExpanderhandle the write side
Caching layers
- CDN: 60s TTL with
stale-while-revalidate— absorbs ~80% of QPS - In-process Caffeine on each service instance — 30s TTL on hydrated suggestions
- Hot-prefix sharding: replicate top prefixes across multiple Redis keys, pick randomly
- Negative caching for empty results to defend against prefix bombing
Ingestion pipeline
- Catalog CDC via Debezium on PostgreSQL → Kafka
- Search analytics stream → Kafka
- Index Builder consumes both, tokenizes and expands prefixes, upserts into Redis + ES, trims ZSETs to top 10
- Popularity pipeline runs every 15 minutes — popularity is a smoothed signal, sub-minute updates aren't worth the cost
- Real-time stock events bypass popularity — out-of-stock filter at hydration
Failure handling
- Redis down: fall back to ES directly; latency rises from 30ms to 50ms but service stays up
- ES down: typo path degraded, strict prefix still works for ~95% of queries
- Index Builder lag: catalog still source of truth; alert on >10 min lag
- Out-of-stock bug: hydration filters in real time; doesn't depend on popularity pipeline
- CDN cache poisoning: input sanitization rejects malformed queries before reaching origin
Production extras
- Rate limit per IP at CDN edge (1000 RPS) to prevent prefix-bomb attacks
- Input validation: max 50 chars, locale charset only
- Anonymized analytics for non-personalization features
- PII filter on suggestion strings
- Distributed tracing across CDN → service → Redis/ES
At 10× scale
- Embedded memory-mapped trie (FST) per service instance — eliminates Redis hop
- Per-region indices for geo-proximity
- GPU-accelerated personalization re-ranking
- Vector search for semantic suggestions ("red shoe" → "crimson sneaker")
Recommendation
Two-tier index — Redis prefix ZSETs for the hot strict-match path, Elasticsearch with edge n-grams for typo tolerance — fronted by a CDN with 60-second TTL on anonymous responses, an async ingestion pipeline keeping both in sync, and real-time stock filtering at hydration to avoid suggesting out-of-stock products — the same architecture Amazon, Etsy, and Shopify run for catalog autocomplete.
Design Search Autocomplete for a Product Catalog
Direct Answer
Build a two-tier system: a Redis-backed prefix index (sorted-set per prefix, sorted by popularity) for sub-10ms suggestions on every keystroke, backed by Elasticsearch with edge n-gram tokenization for typo tolerance and richer ranking. Async pipeline ingests catalog updates and search-analytics popularity into both stores. Aggressively cache the top N suggestions per prefix at the CDN/edge since prefix traffic follows a heavy-tailed distribution (a small set of prefixes dominates).
Common Mistakes & Pitfalls
Using LIKE 'query%' on a relational DB (doesn't scale past 100K products), or treating it as a generic search problem and bolting on Elasticsearch without a prefix index.
Check your understanding
Answer these without looking back at the article.
- How would you add semantic search so "red shoe" suggests "crimson sneaker" — walk through the embedding pipeline and serving path.
- How does your design change if the same query needs to scope to a category (e.g., autocomplete within "Electronics" only)?
- Walk through how out-of-stock items are removed from suggestions in under 30 seconds.
- How would you A/B-test a new ranking algorithm without regressing latency or violating the 60s CDN TTL?
Related interview prep categories
1Want a guided curriculum order?
These modules are also sequenced in our flagship backend interview track — open it when you prefer an ordered path instead of browsing by topic.