Design a Search Autocomplete Service: The Junior, Senior and Staff Answer
When an interviewer asks you to design a search autocomplete service they are looking for three things: how you translate vague latency and scale goals into concrete architecture, how you choose the right data store for prefix look-ups, and how you think about operational concerns like cache eviction and failure modes. The problem is small enough to fit on a whiteboard, but large enough to expose trade-offs at every layer.
Core requirements and driving numbers
| Requirement | Reason | Typical ball-park figure |
|---|---|---|
| Throughput | Users type a character every 0.5-1 s, many queries hit the service simultaneously. | Roughly 10 k queries per second (≈ 864 M per day). |
| Latency | Autocomplete feels instant; UI tolerates only a few hundred milliseconds. | 100 ms tail latency, 20-30 ms median. |
| Data freshness | New items (products, articles) should appear within a minute of being added. | Near-real-time index updates, < 60 s lag. |
| Storage | Prefix index for millions of strings, each a few dozen bytes. | Hundreds of gigabytes, on the order of 200-300 GB. |
These numbers drive the choice of cache size, partitioning scheme, and whether you need a write-ahead log for async updates.
Request path, one hop at a time
- Client → Edge cache (CloudFront) – The user's browser sends a GET
/autocomplete?q=footo CloudFront, which checks its edge cache for the exact prefix. If a hit, it returns the cached suggestion list immediately. - Edge miss → API Gateway – On a miss, CloudFront forwards the request to API Gateway (AWS), which validates the query string and routes it to the application tier.
- Cache miss → Application server – The request lands on an EC2 autoscaling group (or Fargate) that runs the autocomplete logic.
- Server → In-memory cache (ElastiCache Redis) – The server queries Redis for the prefix. Redis holds the hot-prefix set (the most common first-few characters). A hit satisfies the request; a miss triggers the next hop.
- Redis miss → Persistent store (DynamoDB) – DynamoDB stores the full prefix table. The server performs a
Queryon the partition keyprefixand sorts by popularity score. The result is written back to Redis for future hits. - Write path – When a new searchable item is added, the write service writes the record to DynamoDB and publishes an event to an SQS queue. A background worker consumes the event, updates the relevant Redis entries, and optionally pushes a purge to CloudFront.
Data model
- DynamoDB table – Partition key:
prefix(string of first N characters). Sort key:item_id. Attributes:popularity,payload(URL or display text). A Global Secondary Index (GSI) onpopularityallows top-k retrieval per prefix. - Redis – Key:
autocomplete:{prefix}→ sorted set ofitem_idwith scores = popularity. The set is capped (e.g., top 20) to keep memory low. - S3 – Periodic dump of the full index for backup and bulk re-load.
What a complete junior answer covers
- High-level flow as above, with API Gateway, EC2, Redis, DynamoDB.
- Cache hierarchy: edge (CloudFront) → in-memory (Redis) → persistent (DynamoDB).
- Capacity sketch: 10 k QPS × 100 ms ≈ 1,000 concurrent requests; Redis can handle ~50 k ops/sec per node, so a small cluster suffices.
- Basic scaling: Auto-scaling groups for EC2, auto scaling of DynamoDB read capacity, and TTL on Redis entries.
- Simplified failure handling: fallback to DynamoDB if Redis down, and fallback to a static “no suggestions” list if both caches miss.
What a senior answer adds
- Sharding strategy: Prefixes are hashed to multiple DynamoDB partitions; hot prefixes (e.g., ‘a’, ‘e’) are split further using a composite key like
prefix#bucket. - Write pipeline: Use an SQS queue to decouple writes from reads, ensuring the read path never blocks on index updates.
- Cold-prefix handling: For rarely used prefixes, fall back to a full-text search service such as OpenSearch instead of DynamoDB, reducing storage costs.
- Consistency model: Explain eventual consistency of Redis after a write, and why a 30-second window of stale suggestions is acceptable.
- Metrics & alerts: CloudWatch dashboards for cache hit ratio, DynamoDB throttling, and latency percentiles.
What a staff answer adds
- Failure modes: Detailed discussion of cache stampede (many requests miss Redis simultaneously) and mitigation via request coalescing or a “breaker” pattern. Also cover DynamoDB throttling spikes and fallback to a pre-computed static file in S3 served through CloudFront.
- Operational concerns: Deployments using CodeDeploy blue-green, canary testing of new prefix logic, and automated rollbacks. Monitoring of hot-prefix skew and dynamic re-sharding.
- Cost analysis: Estimate DynamoDB read capacity (e.g., 10 k reads/sec of items up to 4 KB is about 864 M read units a day, on the order of a hundred dollars a day on demand if nothing is cached) vs. Redis node cost, and show the trade-off of keeping more prefixes hot in memory.
- Trade-off defense: Argue why a read-heavy workload justifies a larger Redis cluster rather than a more complex inverted index, citing simplicity and lower operational overhead.
- Security: IAM roles for least-privilege access to DynamoDB, encryption at rest for Redis (in-transit TLS), and WAF rules to block abusive query patterns.
Common mistakes that sink the answer
| Mistake | Why it hurts |
|---|---|
| Skipping the cache layer | Direct DynamoDB queries add latency and increase read cost; you’ll miss the 100 ms target. |
| Over-building a full-text index | Autocomplete only needs prefix look-ups; a heavyweight search engine adds unnecessary complexity and cost. |
| Ignoring hot-prefix skew | Not sharding the most common prefixes leads to hot partitions, throttling, and uneven latency. |
| No fallback plan | If Redis or CloudFront fails, the service should still return a reasonable response; otherwise the interview will flag reliability concerns. |
How to practice this
- Start from the practice brief for search autocomplete in the System Design AI library, and read its rubric before you draw anything.
- Draw your own board on the canvas. Start with the request path, then add the data model, and finally annotate each component with the notes you would speak about.
- Run a mock interview with a peer who asks follow-up questions on scaling, failure modes, and cost, or ask the AI coach to review your canvas, then iterate on your diagram.
Questions people ask
What latency should I aim for in an autocomplete service?
Target under 100 ms for the 99th percentile. Users start noticing delays above 200 ms, so design your cache and data store to meet the tighter bound.
Do I need a full-text search engine for autocomplete?
Usually not. Autocomplete is a prefix problem; a key-value store like DynamoDB combined with an in-memory sorted set is sufficient and far cheaper.
How do I handle a sudden spike in traffic for a hot prefix?
Use request coalescing to prevent a cache stampede, autoscale your Redis cluster, and pre-warm the hot prefix in CloudFront edge caches.
What is the simplest way to keep the index fresh?
Write new items to DynamoDB, push an event to SQS, and have a background worker update the Redis sorted set. This gives near-real-time freshness without blocking the read path.