system-design · intermediate

Design Search Autocomplete — Typeahead Suggestions

Start here

Search autocomplete (typeahead) shows suggestions while the user types:

in → instagram, invoice template, india news

Requirements: very low latency, high QPS, results that feel relevant/popular, and eventual updates as trends change.

What you will learn

1. Clarify personalization vs global popularity MVP.
2. Model prefix → top-k queries.
3. Use tries or prefix indexes.
4. Cache hot prefixes at the edge/app.
5. Build offline/online update pipelines.
6. Rate-limit and abuse-protect.

Words you need before we begin

Requirements

Functional

• Given prefix, return ≤10 suggestions
• Case normalization, basic Unicode note
• Optional: user recent searches

Non-functional

• p95 latency tens of ms
• High read QPS
• Eventual freshness of rankings (minutes–hours OK)

High-level design

flowchart LR
  Client --> API
  API --> Cache[(Prefix cache)]
  API --> Idx[Prefix index service]
  Logs[Search logs] --> Batch[Aggregator]
  Batch --> Idx

Step-by-step design

Step 1 — Normalize

Lowercase, trim, maybe remove punctuation—document rules.

Step 2 — Data model

prefix → [(query, score)… top 10] materialised for common prefixes, or trie nodes storing top-k.

Step 3 — Query path

1. Normalize input
2. Check cache
3. Lookup prefix index
4. Return list

Step 4 — Ranking

Score ≈ frequency with time decay; maybe personalization as second phase.

Step 5 — Building the index

Stream search logs → aggregate counts → rebuild top-k per prefix offline every N minutes → atomic swap.

Step 6 — Caching

Cache empty and hot prefixes; short TTL; CDN rarely for personalized results.

Step 7 — Shard

Shard trie/index by first character(s) or hash of prefix for scale.

Failure modes

Trade-offs

Common mistakes

1. SELECT … LIKE 'pre%' on primary DB at typeahead QPS.
2. Perfect ML ranking first.
3. No rate limits.
4. Updating trie on every keystroke write path.
5. Ignoring Unicode/normalization.

Check your understanding

1. What is stored for a prefix in the fast path?
2. Why offline aggregation?
3. How to handle hot prefixes?
4. Min prefix length trade-off?
5. Why cache empty results carefully?

Practice

1. Estimate QPS if 10M users type 5 chars avg.
2. Design trie node content for top-10.
3. Sketch batch pipeline from logs to index swap.
4. Add “remove unsafe suggestions” control.
5. Mock interview.

Deeper production notes

Privacy

Search logs are sensitive—retention and access controls matter.

Multilingual

Tokenization differs by language; start with simple prefix for MVP and note evolution.

Additional teaching scenarios

Scenario A — 10× peak

Scenario B — dependency down 30 minutes

Scenario C — five-sentence wrap

Revision summary

• Typeahead is a prefix → top-k read path.
• Precompute + cache; update via pipelines.
• Protect with rate limits and spam filters.
• Shard and cache hot prefixes.

Glossary

Abbreviations and terminology

• QPS — Queries per second
• TTL — Time to live
• p95 — 95th percentile latency

What to learn next

1. Caching 101
2. Rate limiting
3. Design URL shortener

Extra teaching notes

When you apply this lesson, write the user-visible success metric first, then the failure mode you fear most. Design the smallest mechanism that protects that metric under partial failure. Prefer explicit timeouts, idempotency, and ownership over adding more infrastructure boxes.

In interviews or design reviews, narrate assumptions, request paths, and trade-offs out loud. A correct-enough design with clear failure handling beats a buzzword diagram without numbers. Revisit the worked example and restate it for a different domain to prove you own the ideas, not the template wording.

Extra teaching notes

When you apply this lesson, write the user-visible success metric first, then the failure mode you fear most. Design the smallest mechanism that protects that metric under partial failure. Prefer explicit timeouts, idempotency, and ownership over adding more infrastructure boxes.

In interviews or design reviews, narrate assumptions, request paths, and trade-offs out loud. A correct-enough design with clear failure handling beats a buzzword diagram without numbers. Revisit the worked example and restate it for a different domain to prove you own the ideas, not the template wording.

Extra teaching notes

When you apply this lesson, write the user-visible success metric first, then the failure mode you fear most. Design the smallest mechanism that protects that metric under partial failure. Prefer explicit timeouts, idempotency, and ownership over adding more infrastructure boxes.

In interviews or design reviews, narrate assumptions, request paths, and trade-offs out loud. A correct-enough design with clear failure handling beats a buzzword diagram without numbers. Revisit the worked example and restate it for a different domain to prove you own the ideas, not the template wording.

Extra teaching notes

When you apply this lesson, write the user-visible success metric first, then the failure mode you fear most. Design the smallest mechanism that protects that metric under partial failure. Prefer explicit timeouts, idempotency, and ownership over adding more infrastructure boxes.

In interviews or design reviews, narrate assumptions, request paths, and trade-offs out loud. A correct-enough design with clear failure handling beats a buzzword diagram without numbers. Revisit the worked example and restate it for a different domain to prove you own the ideas, not the template wording.

Extra teaching notes

When you apply this lesson, write the user-visible success metric first, then the failure mode you fear most. Design the smallest mechanism that protects that metric under partial failure. Prefer explicit timeouts, idempotency, and ownership over adding more infrastructure boxes.

In interviews or design reviews, narrate assumptions, request paths, and trade-offs out loud. A correct-enough design with clear failure handling beats a buzzword diagram without numbers. Revisit the worked example and restate it for a different domain to prove you own the ideas, not the template wording.

Interview and production field guide for this topic

Use this section as deliberate practice, not filler. Rewrite the worked example for a second domain you know well—fintech, education, logistics, or media. Keep the same skeleton: requirements, estimates, high-level diagram, request path, data model, scale lever, failure modes, and trade-offs. If you cannot fill every section without copying buzzwords, you do not yet own the design.

Numbers to force yourself to state

Always speak order-of-magnitude figures: peak QPS, storage growth per day, fan-out factor, connection counts, or queue depth. Wrong numbers that are explicit beat silent hand-waving. Correct the numbers when the interviewer or teammate challenges them; that is collaboration, not failure.

Failure minute

Set a timer for sixty seconds and list only failures: timeouts, duplicates, hot keys, dependency outages, bad deploys, and data corruption paths. For each, name detection and first mitigation. Designs that only describe the happy path are incomplete for production and weak in interviews.

Ownership and operability

Name the dashboard, the alert, the runbook section, and the team that pages. If any are blank, the system will train you during an incident. Prefer progressive delivery: canaries, flags, and rollback notes written before the change lands.

Consistency and retries

State whether the design assumes at-least-once delivery, whether handlers are idempotent, and where unique constraints live. Retries without idempotency are how double charges, double messages, and duplicate fan-out jobs appear. Timeouts without bounds are how thread pools die.

What good looks like in a review

A strong design review or interview answer clarifies scope, makes assumptions audible, draws a minimal path, deepens one or two bottlenecks, and closes with trade-offs and evolution. Use that bar on design-search-autocomplete round 0 every time you revisit it.

Interview and production field guide for this topic

Use this section as deliberate practice, not filler. Rewrite the worked example for a second domain you know well—fintech, education, logistics, or media. Keep the same skeleton: requirements, estimates, high-level diagram, request path, data model, scale lever, failure modes, and trade-offs. If you cannot fill every section without copying buzzwords, you do not yet own the design.

Numbers to force yourself to state

Always speak order-of-magnitude figures: peak QPS, storage growth per day, fan-out factor, connection counts, or queue depth. Wrong numbers that are explicit beat silent hand-waving. Correct the numbers when the interviewer or teammate challenges them; that is collaboration, not failure.

Failure minute

Set a timer for sixty seconds and list only failures: timeouts, duplicates, hot keys, dependency outages, bad deploys, and data corruption paths. For each, name detection and first mitigation. Designs that only describe the happy path are incomplete for production and weak in interviews.

Ownership and operability

Name the dashboard, the alert, the runbook section, and the team that pages. If any are blank, the system will train you during an incident. Prefer progressive delivery: canaries, flags, and rollback notes written before the change lands.

Consistency and retries

State whether the design assumes at-least-once delivery, whether handlers are idempotent, and where unique constraints live. Retries without idempotency are how double charges, double messages, and duplicate fan-out jobs appear. Timeouts without bounds are how thread pools die.

What good looks like in a review

A strong design review or interview answer clarifies scope, makes assumptions audible, draws a minimal path, deepens one or two bottlenecks, and closes with trade-offs and evolution. Use that bar on design-search-autocomplete round 1 every time you revisit it.

FAQ from first-time learners

Q: Elasticsearch for autocomplete?
A: Valid; still discuss prefix structures, edge n-grams, and caching—do not stop at product name.

Q: Personalization required?
A: Mention as phase 2 unless interviewer insists.

Track: Distributed Systems

Previous: Design Instagram — Photos, Feed, and Fan-Out

Next: Design Uber — Matching Riders and Drivers

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab