System Design: Design Google Search Autocomplete

System Design: Search Autocomplete

Google serves 8.5 billion searches/day with autocomplete appearing within 100ms of the first keystroke.

Architecture

User types → Debounce 300ms → Cancel previous request
    |
    v Load Balancer (sticky by prefix first char)
    |
    v Autocomplete API Cluster (100+ nodes)
         L1: in-process LRU cache (hottest prefixes)
         L2: Redis cluster (warm prefixes, 5min TTL)
         L3: Trie in memory (full lookup, ~10GB)

Data Collection:
  Every query → Kafka → Aggregation service (Flink)
  Score = 0.7 * recent_count + 0.3 * all_time_count
  Update Trie every 15 minutes

Redis-Backed Suggestions

import redis
r = redis.Redis()

def get_suggestions(prefix: str, limit: int = 10) -> list:
    key     = f"suggest:{prefix.lower()}"
    results = r.zrevrange(key, 0, limit-1)
    if results:
        return [r.decode() for r in results]

    suggestions = trie_service.get(prefix, limit)
    if suggestions:
        pipe = r.pipeline()
        for term, score in suggestions:
            pipe.zadd(key, {term: score})
        pipe.expire(key, 300)
        pipe.execute()
    return [t for t, _ in suggestions]