System design interview · Medium · about 35 minutes

Design search autocomplete

Design search autocomplete: as someone types into a search box, show the 5 most popular searches that start with what they've typed so far.

triecachingdata pipeline

Practise it in the interview simulatorDraw your design on a canvas, stress test it with real traffic, and get a scored report. Or watch this answer build itself, step by step.

1. Clarify the requirements

Before drawing anything, ask questions. These are the answers an interviewer would typically give:

How many users?: 10 million daily active users, each searching about 10 times a day.
What kind of matching?: Prefix matching only, lowercase English letters. No spell-checking.
How many suggestions?: Top 5, ranked by how often each query was searched.
How fast?: Within 100 ms, or typing feels laggy.
How fresh?: Updating suggestions weekly is fine here; trending searches are a nice extension.
Requests per query?: A query is about 20 characters, and the client asks for suggestions on every keystroke.

2. Estimate the scale

Assumptions: 10M DAU, 10 searches per user per day, 20 characters per search (one request per character), 20% of searches are new queries each day, 20 bytes per query.

Suggestion requests per second: about 23K requests/s10M × 10 × 20 ÷ 86,400 ≈ 23K requests/s.
Peak requests per second (2×): about 46K requests/s2 × 23K ≈ 46K requests/s.
New query data per day: about 0.4 GB10M × 10 × 20 bytes × 20% = 0.4 GB/day.

3. The high-level design

The reference design. Dashed arrows are asynchronous.

A fast query serviceAs the user types, the browser asks a stateless query service for the top suggestions (debounced, and cached in the browser).
A trie in memorySuggestions come from a trie whose nodes store their top 5 queries, so a lookup is just a walk down the prefix.
Learn from what people searchQueries are logged asynchronously; aggregators count them every week and build a new trie that replaces the old one.
Watch it in productionMetrics and alerts close the loop: suggestion p99 and trie build time.

4. The components and what each one does

Users (search box) Client (web): Debounce keystrokes; cache suggestions in the browser.
Load balancer Load balancer: Spreads requests over the stateless servers behind it, health-checks them and routes around a dead one. Rate limits abusive clients.
Query service App servers: Returns the top 5 suggestions for a prefix.
Trie cache Cache: In-memory trie; each node keeps its top 5 queries.
Trie store NoSQL / KV store: Serialized trie snapshots; sharded by prefix; replicas with failover.
Query logs Message queue: Every search, logged asynchronously.
Aggregators Workers: Weekly counts → build a new trie snapshot.
Metrics & alerts Metrics & alerts: Dashboards and alerts on p99 latency, error rate, queue depth and cache hit ratio, so a bottleneck shows up before it becomes an outage.

5. Deep dive: fast prefix lookups

How do you return the top 5 suggestions for a prefix in a few milliseconds? Design the data structure, how it's built from search logs, and how it's served and updated.

A trie (prefix tree) where every node also stores its top 5 queries makes a lookup a walk down the prefix.
Build the trie offline from aggregated search logs (say weekly), then swap it in. Don't update it on every search.
Shard by prefix, balanced by traffic; cache results in the browser; filter out unwanted suggestions.

6. What interviewers listen for

Suggestion APIGET /v1/suggestions?prefix=din returns 5 queries.
A trie that stores the top queries at each nodeKeeping the top-k at each node turns a lookup into a walk down the prefix: milliseconds instead of a scan.
Rebuild periodically instead of on every searchUpdating the trie on every search is far too slow; rebuild from aggregates and swap.
Browser caching of suggestionsSuggestions rarely change; let the browser cache them for an hour.
Shard the trie by prefixShard by prefix, balanced by historical traffic rather than by the alphabet.
Filter unwanted suggestionsA filter layer keeps offensive or dangerous suggestions out.
Trending searches (extension)Weekly rebuilds miss breaking news; a streaming path can boost recent searches.
Database replication and failoverA single database is a single point of failure. Replicas give redundancy and read capacity; failover promotes a replica when the primary dies.
Partition (shard) data as it growsOne machine eventually can't hold the data or the write load. Say how you'd split it and by which key.

7. Follow-up questions

Every keystroke sends a request. How do you cut that load without making suggestions feel slower?
Huge news breaks and everyone searches a brand-new phrase. Your weekly trie has never seen it. What do you do?
Far more searches start with 's' than with 'x'. What happens to your shards?

Answer them in the simulator

The key points for each follow-up, your scored report and the stress test are part of Pro: ₹299 a month or ₹1,999 a year.

See Pro

The design in a nutshell

Browser (debounced, cached) → load balancer → stateless query service → in-memory trie cache → trie database on a miss.
Each trie node stores its top 5 queries, so a lookup is a walk down the prefix: O(prefix length).
Search logs → aggregators (weekly counts) → workers rebuild the trie → trie database → swapped into the cache.
Shard by prefix using historical traffic; a filter layer removes unwanted suggestions; a streaming path handles trending searches.