Search Autocomplete and Typeahead: The Engineering Behind Instant Suggestions

How Google Handles 65,000 Searches Per Second

Search Autocomplete and Typeahead power the instant suggestions you see every time you type a character into Google's search bar, with results appearing in under 200 milliseconds. With 8.5 billion searches per day (65,000 per second), that means potentially 400,000+ autocomplete requests per second (average ~6 keystrokes per query). Running a full-text search for every keystroke would melt any database. Google's solution: pre-compute the top suggestions for every possible prefix offline, store them in memory, and serve them from edge caches. The result feels instantaneous because it is pre-computed, the work happened hours ago, not when you typed.

The Trie Data Structure

Trie (Prefix Tree) for Autocomplete:

  Root
   |
   s
   |
   y
   |
   s
  / \
 t   t
 |   |
 e   e
 |   |
 m   m
 |    \
 (end) a
  |    |
  d    t
  |    |
  e    i
  |    |
  s    c
  |    (end) -> 'systematic'
  i
  |
  g
  |
  n -> 'system design'

  Query: user types 'sys'
  Trie: traverse s -> y -> s
  Return all completions in subtree:
  ['system', 'system design', 'systematic', 'systems thinking']

  With pre-computed top-K at each node:

  Node 'sys' stores: [
    ('system design interview', 95000),   # search count
    ('system design', 82000),
    ('systems thinking', 12000),
    ('systematic review', 8000),
  ]

  Result: no subtree traversal needed.
  Just return the pre-stored top-10 list.
  Lookup time: O(prefix_length), typically < 1 microsecond.

System Architecture

Autocomplete System Design:

  [User types 'sys'] --> [API Gateway / CDN Edge Cache]
                              |
                         Cache HIT? (95% of requests)
                              |
                         YES: return cached suggestions in <5ms
                              |
                         NO:  [Autocomplete Service]
                              |
                         [Redis / In-Memory Trie]
                              |
                         Lookup prefix 'sys'
                         Return top-10 suggestions
                         Cache result at edge (TTL: 1 hour)

  Data Pipeline (runs daily or hourly):

  [Query Logs]  -->  [Spark/Flink Job]  -->  [Redis/Trie]
  (7 days of          Count frequency        Load updated
   search data)       per prefix             prefix -> suggestions
                      Apply filters:         mapping
                      - Remove profanity
                      - Remove PII
                      - Remove low-frequency
                      - Boost trending

  Client-Side Optimization:
  - Debounce: wait 100-200ms after last keystroke before sending
  - Cache locally: if 'sys' returned results, prefix 'syst'
    can be filtered client-side from those results
  - Abort previous request when new keystroke arrives

Personalization and Trending

Suggestion Blending:

  For prefix 'sys' for User 42:

  Source 1: Global popular (pre-computed)
    ['system design interview', 'system update', ...]

  Source 2: User's recent searches
    ['system design lab', 'systemd service tutorial']

  Source 3: Trending now (updated every 5 min)
    ['system outage AWS today']

  Blended result:
    1. 'system design lab'          (personal - exact recent search)
    2. 'system outage AWS today'    (trending boost)
    3. 'system design interview'    (global popular)
    4. 'system design'              (global popular)
    5. 'systemd service tutorial'   (personal)

  Blending weights:
    Personal match:  2.0x base score
    Trending match:  1.5x base score
    Location match:  1.2x base score
    Global popular:  1.0x base score

  Cold Start (new user, no history):
    Use global popular only + location-aware suggestions

Interview Tip

Autocomplete is a classic system design interview question. The key insight: it is pre-computed, not live. Say: 'I would collect query logs and build a prefix-to-suggestions mapping offline using a Spark or Flink job. The mapping is loaded into Redis sorted sets (prefix as key, suggestions as members with frequency as score). The top-10 suggestions per prefix are served from Redis in <1ms. I would cache popular prefixes at CDN edge nodes for <5ms global latency. Client-side, I would debounce keystrokes at 200ms intervals and cancel in-flight requests when new keystrokes arrive. For personalization, I would blend global popular suggestions with the user s recent searches and trending topics. The data pipeline refreshes daily for general suggestions and every 5 minutes for trending events.'

Key Takeaway

Autocomplete at scale is pre-computed offline from query logs, not computed live. Use tries or Redis sorted sets to map prefixes to ranked suggestions. Cache at CDN edge for <5ms latency. Debounce client-side to reduce request volume. Blend global popular, personal history, and trending topics for relevance. The latency target is under 100ms total including network time.