Case Studies
Design Search Autocomplete
Suggest completions while the user types — within a keystroke's time. Why querying the database per keystroke fails, how a precomputed prefix index answers in milliseconds, and how debouncing and edge caching cut the load.
Intermediate 4 min read· Updated 2026-11-18
What you will learn
- Estimate keystroke traffic and the latency budget.
- Build a prefix index with precomputed top-k suggestions.
- Update suggestions from search logs without slowing reads.
- Reduce load with debouncing, client and edge caching.
Before you start
Requirements
- Functional: as the user types, show the top 5–10 completions for the current prefix, ranked by popularity (optionally personalised and localised).
- Non-functional: suggestions within ~100 ms end to end, so they keep up with typing; tolerate being minutes or hours out of date.
- Scale: every keystroke of every user is a potential request.
Back-of-the-envelope estimates
| Quantity | Assumption | Result |
|---|---|---|
| Searches | 50 M per day, ~20 characters each | ~1 B keystrokes/day ≈ 12,000/s (peak ×3) |
| With debouncing | One request per typing pause (~4 per search) | ~2,300/s |
| Index size | 10 M popular queries, top-10 per prefix | Tens of GB — fits in memory on a few nodes |
Evolve the design
Stage 1 of 3
Query the database per keystroke
- Current architecture
- Each keystroke runs
WHERE name LIKE 'pre%' ORDER BY popularity LIMIT 10. - Limitation
- Each query sorts many matching rows; keystroke traffic is huge.
- Bottleneck
- Database connections: half the requests fail and the rest arrive too late to be useful.
- Improvement
- Precompute the answer for every prefix.
- Performance impact
- ~50% failures, p50 ≈ 430 ms.
- Complexity & operational cost
- No new components.
- Trade-off
- Always fresh, unusable at typing speed.
Loading simulation…
Building the index
- Collect search logs (query, timestamp, region) into a stream or warehouse.
- Aggregate counts per query over a sliding window (e.g. last 7 days, decayed) — a batch or pipes and filters job.
- For every prefix of every popular query, keep the top-k queries by score.
- Publish a new immutable index version; suggest servers load it and switch atomically.
let timer: ReturnType<typeof setTimeout> | undefined;
let inflight: AbortController | undefined;
input.addEventListener('input', () => {
clearTimeout(timer);
timer = setTimeout(async () => {
inflight?.abort(); // the user typed on: drop the old answer
inflight = new AbortController();
const prefix = input.value.trim().toLowerCase();
if (prefix.length < 2) return;
const res = await fetch(`/suggest?q=${encodeURIComponent(prefix)}`, { signal: inflight.signal });
render(await res.json());
}, 150);
});Trade-offs
| Benefits | Costs | |
|---|---|---|
| Precomputed index | Millisecond lookups regardless of data size. | Suggestions lag behind trends until the next build. |
| Edge caching | Popular prefixes answered next to the user. | Only for non-personalised responses. |
| Debouncing | Cuts requests several times. | Adds a short delay before the first suggestion. |
Interview checklist
- Estimate keystroke QPS and the latency budget first.
- Explain the trie / prefix → top-k structure and how it is built offline.
- Reduce traffic: debounce, minimum prefix length, client and CDN caching.
- Mention filtering offensive suggestions, localisation and trending queries.
Further reading
Related topics
Design to Scale
Database Indexing
Why the same query gets slower every day as a table grows, how a B-tree index turns a full scan into a few page reads — and why every extra index makes writes pay.
Design to Scale
Caching Strategies
Put a cache in front of a struggling database: how cache-aside works, what drives the hit ratio, how to keep data fresh, and how to survive the moment the cache goes cold.
Design to Scale
Content Delivery Network (CDN)
Cache content at edge locations close to users, so most requests never cross an ocean or touch your origin — and design pages so they can actually be cached.
Microservice Patterns
Pipes and Filters
Break a multi-step processing job into independent filters connected by queues (pipes), so each step can be scaled, deployed and diagnosed on its own — and a slow step is visible as a growing queue in front of it.
Microservice Patterns
Rate Limiting
Cap how many requests a client may make per unit of time to protect services from bursts and abuse — and pick the algorithm whose behaviour at the edges you can live with.