Designing a Search Autocomplete Service – System Design Interview Walkthrough 2026

When an interviewer asks you to design a search autocomplete service, they want to see how you translate a user‑facing feature into a reliable, low‑latency backend. The problem sounds simple—return a list of completions as the user types—but the devil is in the details: handling millions of queries per second, keeping suggestions fresh, and staying within tight latency budgets.

1. Clarify the scope and requirements

Functional requirements

• Given a prefix q and optional context (e.g., user locale, device type), return the top k completions ordered by relevance.
• Support personalization: results may differ per user based on history or preferences.
• Allow the client to request additional metadata (e.g., query popularity, category).

Non‑functional requirements

• Latency: sub‑100 ms for the 99th percentile, ideally under 50 ms for the median.
• Throughput: handle a high QPS burst during peak traffic (think of a popular e‑commerce site during a sale).
• Availability: >99.9 % uptime, graceful degradation if a shard fails.
• Consistency: suggestions should be reasonably fresh (seconds to minutes) but can tolerate slight staleness.
• Scalability: horizontal scaling to add capacity without major re‑architecting.

Ask the interviewer about the expected k (usually 5–10) and whether the service must support multi‑language or just a single locale. Clarify if the autocomplete is for a web search engine, product catalog, or internal knowledge base, because that influences the data source and ranking model.

2. Core entities and data model

The primary storage is a prefix tree (Trie) or a compressed Finite State Automaton (FSA) that maps prefixes to candidate term IDs. The ranking metadata lives in a separate key‑value store that can be quickly joined at query time.

3. API contract

GET /autocomplete?q={prefix}&k={num}&locale={locale}&user={userId}

• Parameters
  • q: the typed prefix (UTF‑8 string).
  • k: number of suggestions (default 5, max 10).
  • locale: optional, defaults to server locale.
  • user: optional, enables personalization.
• Response

{
  "suggestions": [
    {"text": "apple", "score": 0.92, "category": "fruit"},
    {"text": "application", "score": 0.87}
  ]
}

The contract is deliberately minimal; extra fields can be added later without breaking clients.

4. High‑level design

+-------------------+          +-------------------+          +-------------------+
|   Front‑end / UI  |  --->    |   API Gateway     |  --->    |   Router / Load   |
+-------------------+          +-------------------+          +-------------------+
                                                               |
                                                      +-------------------+
                                                      |   Autocomplete    |
                                                      |   Service Layer   |
                                                      +-------------------+
                                                               |
                     +-------------------+   +-------------------+   +-------------------+
                     |   Cache (Redis)   |   |   Trie Store (SSD)|   |   Ranking Store   |
                     +-------------------+   +-------------------+   +-------------------+

• API Gateway handles authentication, rate‑limiting, and request validation.
• Router sharding is based on the first few characters of the prefix (e.g., first two letters). This spreads load evenly because most prefixes start with common letters.
• Cache holds hot prefixes (e.g., "a", "the") with pre‑computed top‑k suggestions.
• Trie Store is a read‑optimized, compressed data structure residing on SSD or NVMe for fast prefix lookup.
• Ranking Store contains scores, personalization vectors, and can be a column‑store like ClickHouse or a key‑value store.

4.1 Data flow for a request

1. API gateway validates the request.
2. Router directs the request to the shard responsible for the prefix.
3. Service checks the cache for the exact prefix; if present, return cached suggestions.
4. If cache miss, traverse the Trie to collect candidate term IDs (limit to a configurable candidate_pool).
5. Pull ranking metadata for those IDs, apply personalization if user is supplied, and sort.
6. Store the top‑k result in cache (with a short TTL) for future hits.
7. Return the response.

5. Deep dive: Hard parts

5.1 Latency budget

Break down the 100 ms budget:

• Network ingress/egress: ~10 ms.
• Cache lookup: ~1–2 ms.
• Trie traversal: ~5–10 ms for a typical prefix length.
• Ranking join: ~15–20 ms (depends on personalization complexity).
• Serialization + response: ~5 ms. Leaving a safety margin for occasional spikes. If any component exceeds its slice, you know where to optimise.

5.2 Hot‑key problem

Certain prefixes (e.g., single letters) receive disproportionate traffic. Mitigate by:

• Pre‑warming the cache with top‑k suggestions for those prefixes.
• Separate hot‑key tier: allocate dedicated nodes with larger memory to serve hot prefixes.
• Adaptive TTL: longer TTL for hot keys, shorter for long-tail prefixes.

5.3 Data freshness vs. performance

Updates come from two sources:

• Batch ingest (e.g., nightly crawl of new terms).
• Real‑time events (user searches, trending topics). Use a dual‑write approach: write to a durable store (e.g., S3 or a relational DB) and asynchronously push updates to the Trie Store. For real‑time popularity, a streaming pipeline (Kafka → Flink) can adjust scores in the ranking store every few seconds.

5.4 Sharding strategy

Sharding by prefix works well because it aligns with query patterns. However, it can lead to uneven distribution if a language has many words starting with the same letter. To balance, you can add a hash suffix: shard = hash(prefix) % N. This spreads load but requires the client to know the mapping (handled internally by the router).

5.5 Scaling reads and writes

• Read scaling: add more cache nodes and replica shards. Use a consistent hashing layer to route reads.
• Write scaling: batch updates, use a write‑ahead log, and apply updates in the background. Writes are less latency‑critical than reads.

6. Trade‑offs and alternatives

Choosing the right point on this spectrum depends on the product’s scale and the team’s expertise.

7. Follow‑up questions interviewers often ask

1. How would you handle multi‑language support? – Store separate Trie instances per locale, share the ranking store, and route based on the locale parameter.
2. What if the client wants fuzzy matching (typos)? – Add a phonetic index (e.g., Soundex) or a n‑gram based fallback that runs after the exact‑prefix lookup.
3. How do you protect against abusive traffic? – Rate‑limit per IP/user, implement a CAPTCHA for suspicious patterns, and monitor QPS spikes.
4. Can you make the service eventually consistent across shards? – Yes, by using a gossip protocol to propagate ranking updates, accepting slight divergence for a few seconds.
5. What metrics would you monitor? – P99 latency, cache hit ratio, QPS per shard, error rate, and freshness lag of ranking scores.

8. Sample answer snippet (45‑90 seconds)

"The core of an autocomplete service is a fast prefix lookup combined with a relevance ranking. I’d start with a two‑layer design: a hot‑key cache (Redis) that stores pre‑computed top‑k suggestions for common prefixes, and a read‑optimized Trie stored on SSD for the rest. The API receives a prefix, optional locale, and user ID. The request is routed based on the first two characters of the prefix, which spreads load evenly. If the cache hits, we return instantly; otherwise we traverse the Trie, fetch ranking metadata, apply personalization, and sort. Updates flow through a batch pipeline that writes to durable storage and asynchronously refreshes the Trie. This architecture meets sub‑100 ms latency, scales horizontally, and tolerates stale data for a few seconds, which is acceptable for autocomplete."

How to practice this

1. Sketch the diagram on paper – start from the API contract, then add cache, storage, and routing layers. Explain each component in under a minute.
2. Run a mock interview – use Call Assistant to record yourself answering, then replay to check for clarity and pacing.
3. Stress‑test the design – pick a few “what‑if” scenarios (e.g., hot‑key overload, multi‑language) and argue how you’d adapt the architecture.

---

FAQ

• What is the simplest data structure for prefix lookup? A compressed Trie or a Finite State Automaton provides O(length) lookup and can be stored efficiently on SSD.
• Do I need a separate personalization service? For a basic design you can embed personalization vectors in the ranking store; a dedicated service becomes useful only at massive scale.
• How important is cache hit ratio? Very important – a high hit ratio (often >80 %) keeps latency low and reduces load on the Trie layer.
• Can I use a managed search service instead of building my own? Yes, managed services simplify operations but may limit fine‑grained latency tuning and custom ranking logic.