Design Search Autocomplete

Intermediate · 24 min read · High-Level Design, Case Studies: Core

Tries, top-k precomputation, freshness and personalisation.

Design search autocomplete (typeahead): as a user types "how to", suggest the top completions — "how to tie a tie", "how to lose weight" — ranked by popularity, within the time between keystrokes. It's a classic because the latency budget is brutal, the read volume is enormous, and the elegant answer is precomputation.

1. Clarify the problem

2. Requirements

Functional: return top-k suggestions for a prefix; update rankings from search logs; support blocklisting.

3. Capacity estimation

So: reads dominate completely. Precompute top-k per prefix offline so serving is a single lookup; shard the long tail; cache short prefixes everywhere.

4. API

5. Data model

The core structure is a trie (prefix tree), where each node represents a prefix:

6. High-level design

Serving: client debounces keystrokes (e.g., 100–150 ms), requests the prefix; the CDN serves popular prefixes; misses go to a suggest server that holds its shard of the prefix map in memory and returns the list.

7. Deep dives

Each shard is replicated for availability and read throughput.

8. Failure modes

9. Trade-offs summary

10. What interviewers look for

Interview questions

  • Why store the top-k at each trie node instead of computing it on the fly?
  • How would you make a breaking-news query appear in suggestions within minutes?
  • Personalised suggestions break CDN caching. How do you handle that?

Practice

Write your answer before opening the suggested one. Anything you mark "Partly" or "Missed it" comes back in your review deck.

Further reading

Key takeaways

  • Autocomplete is extremely read-heavy with a tight latency budget: precompute, don't compute.
  • Store top-k completions at each trie node, or flatten to a prefix → top-k map.
  • Separate the offline build pipeline (batch + streaming) from the in-memory serving tier; swap versioned snapshots.
  • Shard by load-aware prefix ranges or hash; replicate and edge-cache hot short prefixes.
  • Debounce and cache on the client; filter unsafe suggestions at build time with a real-time kill switch.

Previous: Design a Notification System · Next: Design a Web Crawler