Design Search Autocomplete System Design Interview Guide

← System Design Interview Preparation

This guide walks through Design Search Autocomplete the way you would in a backend or Java interview. The numbers are interview estimates. They help you show your thinking. They are not a production capacity plan.

1. Problem

Autocomplete shows a few suggestions while the user is still typing.

Example:

• User types ja
• UI shows java, java interview, javascript
• User types jav
• List tightens to Java-related phrases

This is prefix search with tiny latency, not the full search results page. Ranking is usually popularity, with optional personalization. Typos and language are follow-ups.

If this API is slow, the dropdown feels broken. Cache and an in-memory prefix index exist for that reason.

2. Functional Requirements / FR

Out of scope: the full search engine, ads in the dropdown, voice input.

3. Non-Functional Requirements / NFR

Interview line: this is a cache + prefix index problem, not a SQL LIKE 'ja%' problem at scale.

4. Back-of-the-Envelope Calculation

Traffic assumptions

• 100 million search users per day
• Each user types an average of 20 keystrokes that fire autocomplete
• Read/write ratio: almost all reads. Ranking jobs are periodic.

QPS

100,000,000 users × 20 = 2,000,000,000 autocomplete calls/day
2,000,000,000 / 86,400 seconds = around 23,150 QPS

If peak is 5×, design for around 116,000 QPS.

That is why every keystroke cannot hit a disk-based search cluster without a cache.

You can cut QPS:

• Debounce 30–50 ms in the client
• Minimum 2 characters
• Cancel in-flight requests when the next key arrives

Say debounce + min length cuts traffic in half. Still design the backend for ~50,000–100,000 peak QPS.

Storage

Query log: 2 billion events/day is too much to store raw forever. Sample, or keep aggregates.

Unique queries: say 100 million distinct strings. Average 20 bytes + counts ≈ 40 bytes:

100,000,000 × 40 bytes ≈ 4 GB

A trie with compressed nodes might be tens of GB. That still fits in a memory-heavy service.

Cache / memory estimate

Hot prefixes: a, ja, java, how to, etc.

Assume 5 million hot prefixes, each storing 10 suggestions × 40 bytes ≈ 400 bytes:

5,000,000 × 400 bytes ≈ 2 GB

Redis or local cache on each autocomplete node can hold this. Local cache is faster (no extra hop). Redis is shared. Many designs use both: local Caffeine + Redis. See distributed cache.

Server estimate

If a cached prefix lookup is 0.2 ms of CPU, one core can do thousands per second. Be conservative: 5,000 QPS per server because of JSON and network.

100,000 peak / 5,000 ≈ 20 servers

About 25–30 with headroom. Ranking workers are a small separate pool.

These are interview estimates, not exact production numbers.

5. APIs

GET /api/autocomplete?q=jav&limit=8

Optional: locale=en-IN, userId from the session cookie (do not put PII in query logs carelessly).

Success:

{
  "q": "jav",
  "suggestions": [
    { "text": "java", "score": 0.98 },
    { "text": "javascript", "score": 0.91 },
    { "text": "java interview", "score": 0.74 }
  ]
}

Rules:

• q trimmed, lowercased, max length 50
• If q.length < 2, return empty list
• Always ≤ limit
• Cache-Control for anonymous hot prefixes (short TTL)

POST /api/search on the full search page is not this API. It can log the final submitted query for ranking.

Errors: 400 empty after sanitize, 429 if a bot hammers keystrokes.

6. Data Model

In-memory / index (the live structure)

For each prefix, store top K queries. This can be:

• A trie where each node holds top 10
• An inverted prefix index in something like Elasticsearch / Redis Search

suggestion_stats (offline)

prefix_topk

Materialized: prefix, locale, rank, query, score.

This table (or a snapshot file) is what servers load.

blocklist

term, match_type (exact/prefix). Applied at serve time and at index build.

Query logs

Not a SQL row per keystroke if you can avoid it. Sample 1% of autocomplete, keep 100% of submitted searches. Queue → ranking worker.

Personalization: user_recent_queries in Redis with TTL, size 20. Optional.

7. High-Level Design

Hot prefixes never leave RAM if you can help it.

Components:

• User types in the search box.
• API Gateway: TLS, rate limiter, routing.
• Autocomplete Service: normalize query, check cache, then index.
• Hot Prefix Cache: Redis or local memory for popular prefixes (java, how).
• Prefix / Search Index: trie or search engine for the long tail.
• Queue: sampled keystrokes + completed searches.
• Ranking Worker: recompute top K, push a new index snapshot.

Read path:

1. Normalize JaV → jav
2. If blocked or too short → empty
3. Cache ac:en:jav
4. On miss, query prefix index, fill cache
5. Optionally merge user recents at the end (small list)

Write path is offline. Do not update the trie on every keystroke.

8. Deep Dives

Trie / prefix index

A trie is easy to explain: edges are characters, node stores top suggestions. Memory can grow. In practice you might:

• Keep a trie for prefixes up to 20 characters
• Spill rare prefixes to a search index

Elasticsearch prefix or edge_ngram is an acceptable alternative if you say cache in front.

Ranking by popularity

Score ≈ count in last 7 days, with a little time decay so last year's meme dies. Rebuild every 15–60 minutes. Faster is rarely needed.

Personalization (optional)

Blend: 0.8 * global + 0.2 * user_recent_match. If Redis is down, serve global only. Do not fail the request.

Updating suggestions

Query logs → Kafka → worker → new prefix_topk snapshot → autocomplete nodes reload. Atomic swap so clients never see a half-built trie.

Typos (brief)

For length ≥ 4, optionally run a fuzzy lookup (edit distance 1) if exact prefix has few results. This is expensive. Only on cache miss, and never on 2-letter prefixes.

Regional / language support

Key the cache and index by locale. pa in India vs Mexico is not the same language guess. Do not mix all locales into one top-10.

9. Bottlenecks

• QPS from first character a or s
• In-memory index rebuild that pauses requests
• Hot Redis key for prefix a
• Ranking job that scans unsampled raw logs
• Personalization adding a Redis RTT to every call

Mitigations: min length, client debounce, local cache, copy popular keys, sample logs, make personalization optional and async-batch.

10. Tradeoffs

Pick: hot cache + prefix index, batch popularity, optional recents.

11. Failure Modes

Empty suggestions are better than a 5-second spinner.

12. Interview Answer in 10 Minutes

"Autocomplete is a low-latency prefix service, not full search.

Assume 100 million users and 20 keystroke calls each. That is 2 billion calls a day, about 23,000 QPS, around 100,000 QPS at 5× peak. I would debounce on the client and ignore 0–1 character queries. Storage for 100 million unique queries is only a few gigabytes. A 2 GB hot prefix cache covers the common case.

API is GET with the prefix. Normalize, blocklist, then look up a hot cache. On miss, hit a prefix index or trie and fill the cache. Return top 8.

Ranking is offline. We log completed searches, maybe a sample of prefixes, and a worker refreshes popularity. Personalization is an optional merge with recent user queries in Redis.

I would not run LIKE queries on Postgres for this. I would not update ranking on the request path.

If cache fails, use the index. If ranking fails, keep yesterday's snapshot."

Practice this until it is under 10 minutes.

13. Interview Talking Points

• Keystroke QPS is the design driver.
• Cache first, index second.
• Trie is a teaching tool; a snapshot file plus cache is production-shaped.
• Batch ranking, not per-keystroke writes.
• Fail open with empty or stale lists.
• Locale keys.
• Metrics: p99 latency, cache hit ratio, empty-result rate, rebuild time.
• Caching background: distributed cache, caching concept.

14. Follow-up Questions

How do you keep the trie in sync across servers?
Build immutable snapshots, push to object storage, each node loads and atomic-swaps. Do not gossip per query.

How do you handle Unicode?
Normalize Unicode, decide grapheme vs code-point prefix rules, test Hindi and CJK. Separate locale indexes.

SQL vs Elasticsearch vs trie?
SQL is fine for a prototype. Elasticsearch is fine with a cache. Trie/snapshot is the latency story.

Personalization privacy?
Keep recents on-device or short TTL in Redis. Do not dump them into public query logs.

Java implementation?
Spring Boot service, Caffeine local cache, Redis, Kafka consumer for ranking. Java and Spring Boot tags have more on this stack.

15. Internal Links

Related JavaThoughts reading:

• System Design Interview Preparation
• Design a Distributed Cache
• Design a Rate Limiter
• Java
• Spring Boot
• Kafka
• Microservices
• Distributed Systems
• API Gateway
• Caching
• Event-driven architecture
• 20 system design concepts

Next in this series: Design Ride Booking like Uber.