System Design: Search Autocomplete (Typeahead)

Design the backend for a search box that suggests completions as the user types, with latency under 100ms.

Technical Reference & Key Concepts

The Challenge: Search Autocomplete

Users type into a search box and see suggestions after every keystroke. Traffic is huge, queries are logged continuously, and suggestions must reflect popularity.

Core questions to address:

  1. What data structure or store backs the suggestions, and why?
  2. How is the 'top suggestions' ranking data built and kept fresh?
  3. How do you keep per-keystroke latency under ~100ms at scale?