#08HardSearch, Autocomplete & Big Data

Design Typeahead Suggestion/Autocomplete

ASKED IN INTERVIEWS AT:MetaGoogleExpediaBloomberg

EXECUTIVE SUMMARY & PROBLEM STATEMENT

Build a real-time search autocomplete system that returns the top 5-10 query suggestions in under 30ms as the user types each keystroke.

SCALE ESTIMATION & TRAFFIC ENVELOPE

DAILY ACTIVE USERS / TPS5 Billion searches/day = ~25 Billion autocomplete keystroke queries/day
READ / WRITE TRAFFIC RATIORead-intensive (Keystrokes streamed live)
5-YEAR STORAGE CAPACITYTrie compressed in RAM ~ 50 GB per instance

FUNCTIONAL REQUIREMENTS

  • [1]Provide top 5-10 relevant completions for user search prefix
  • [2]Rank suggestions based on historical query frequency

NON-FUNCTIONAL REQUIREMENTS

  • •Response latency < 30ms
  • •High availability (99.99%)
  • •Freshness: reflect trending searches within hours

CORE ARCHITECTURAL COMPONENTS

Keystroke Aggregator
In-Memory Trie Cluster
Offline Aggregation Pipeline (Spark/Flink)
ZooKeeper Cluster Coordinator
Browser Cache / Debouncer

DATA SCHEMA & PERSISTENCE

PrefixTrie in RAM: Node { children: Map, topSuggestions: List<{query, score}> }

DISTRIBUTED TRADE-OFFS & FAILURE MODES

  • ⟡Pre-computing top suggestions at each node increases Trie memory by 4x but avoids runtime Trie tree traversal.