Skip to content
System Design Lab
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

QuantityAssumptionResult
Searches50 M per day, ~20 characters each~1 B keystrokes/day ≈ 12,000/s (peak ×3)
With debouncingOne request per typing pause (~4 per search)~2,300/s
Index size10 M popular queries, top-10 per prefixTens 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

  1. Collect search logs (query, timestamp, region) into a stream or warehouse.
  2. Aggregate counts per query over a sliding window (e.g. last 7 days, decayed) — a batch or pipes and filters job.
  3. For every prefix of every popular query, keep the top-k queries by score.
  4. Publish a new immutable index version; suggest servers load it and switch atomically.
Client: debounce and cancel stale requests
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

BenefitsCosts
Precomputed indexMillisecond lookups regardless of data size.Suggestions lag behind trends until the next build.
Edge cachingPopular prefixes answered next to the user.Only for non-personalised responses.
DebouncingCuts 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