Design Google Typeahead / Autocomplete

Trie Data Structure: The Core Algorithm

A trie node stores a character, a count of how many times the full path forms a top query, and child pointers. For the prefix "sy", the path traverses root to s, then to y, exposing illustrative completions (truncated to 3 for illustration; concrete production configuration stores top-10):

• "system": count 50,000
• "system design": count 20,000
• "system architecture": count 5,000

Each node caches its precomputed top-10 completions (the general algorithm supports top-K; top-10 is the canonical production setting) so a prefix lookup runs in O(prefix length) time rather than executing a subtree traversal. During offline index construction, frequency scores are propagated upward and the top-10 lists are computed for each node. The resulting trie is published as an immutable snapshot, ensuring serving nodes query the trie with zero lock contention and no in-place mutation overhead.

Root
└── s
    └── y
        └── s
            └── t
                └── e
                    └── m (★ "system" count=50000)
                        └── d → e → s → i → g → n (★ "system design" count=20000)
                        └── a → r → c → h (★ "system architecture" count=5000)

Optimization 1: Store Top-10 results at each node (top-K generalized). Precompute and cache the top 10 most popular completions directly at each trie node. When a user types "sys", the service traverses from node 's' to 'y' to 's' and immediately returns the cached top-10 list. This avoids traversing the entire subtree at query time and guarantees an O(prefix_length) lookup.

node: "sys"
top_10:
  - query: "system design"
    count: 20000
  - query: "system architecture"
    count: 5000
  - query: "system requirements"
    count: 3000

Optimization 2: Compressed Trie (Radix Tree / Patricia Trie). Merge single-child node chains so the sequence from s through y, s, t, e, and m compresses into a single "system" node. This structural compression reduces memory consumption by 50% to 70%.

Optimization 3: Trie Serialization. Serialize the trie into a flat byte array for compact storage and rapid deserialization, utilizing memory-mapped files to achieve instantaneous service startup.

Offline Data Pipeline

The offline data pipeline transforms raw search events into updated, ranked immutable trie snapshots without placing load on the latency-sensitive read path.

• Search Logs: Search logs record every query along with its timestamp, anonymized user identifier, and geographic location.
• Kafka and Data Lake Archive: Kafka buffers incoming search events with a 7-day retention window primarily for streaming replay and pipeline recovery. Concurrently, a sink connector archives sampled search events to durable object storage (data lake) for long-term historical batch processing.
• Flink Streaming Aggregation and Spark Batch Processing: Stream and batch workloads are clearly separated. Apache Flink continuously consumes live Kafka search events across 1-hour sliding windows (sliding every 5 minutes) to evaluate query velocity against a 24-hour baseline, outputting trending terms into Redis prefix buckets. Apache Spark reads historical logs from durable object storage to compute decayed popularity scores across daily and weekly windows, score = Σ (count_i × decay^(age_in_hours)), filtering noise (< 5 occurrences), profanity, and PII. Spark outputs aggregated query-score pairs to the Aggregated Query database.
• Trie Builder: The builder reads aggregated query-score pairs from the Aggregated Query database, constructs the trie in memory, propagates scores upward, and computes the top-10 descendants at each node. It serializes the structure into an immutable binary blob and uploads it to S3. Rebuild Schedule: The core stable trie is rebuilt and published hourly via offline batch processing, while the trending overlay updates continuously on a 5-minute cadence from the streaming aggregation pipeline.

Autocomplete Service

The autocomplete serving fleet handles high-throughput prefix queries with strict sub-50ms latency guarantees.

• Stateless Instances: Each autocomplete server operates statelessly, loading the immutable trie snapshot into local memory upon startup.
• Trie Refresh: When a new hourly trie blob is published to S3, instances poll or receive an invalidation signal and atomically swap active pointers between double-buffered memory slots with zero downtime.
• Prefix Lookup: Invoking trie.search(prefix) on the main immutable trie and trending_trie.search(prefix) on the local trending overlay returns candidate completions in O(prefix_length) time, which are merged, boosted, and deduplicated into the final top 10 suggestions.
• Horizontal Scaling: The canonical baseline organizes 6 shard tiers of ~50 GB each with 3 replicas (~900 GB aggregate serving RAM). For extreme scale, the cluster can expand into 256 to 4,096 fine-grained prefix shards.

CDN Caching

Edge caching is what makes global delivery feasible.

• Edge Caching for Hot Prefixes: High-frequency prefixes such as "how to", "what is", and "why" are cached at edge points of presence.
• Cache Duration and Freshness Interaction: CDN caching is used primarily for stable, global autocomplete responses with a 1-hour time-to-live because popularity distributions for common short prefixes remain stable throughout the day. Responses that depend on the 5-minute trending overlay or personalization use a short TTL (≤5 minutes) or bypass the CDN entirely so that edge caching does not violate the 5-minute trending freshness guarantee.
• Cache Key Structure: Responses are stored under keys formatted as autocomplete:{prefix}.
• Offload Impact: Edge caching absorbs 30% to 50% of total autocomplete query traffic before reaching origin shards.

Client-Side Optimizations

Client applications implement caching and prefetching to eliminate redundant network traffic and provide instantaneous perceived response times.

• Debouncing: Clients wait for 100 to 200 ms of inactivity before dispatching an HTTP request, cutting keystroke query volume by approximately 70%.
• Local Browser Cache: The client caches previous responses so typing from "syst" to "syste" can immediately reuse results client-side without an extra network call.
• Predictive Prefetching: Upon rendering results for "sys", the client asynchronously prefetches likely next prefixes such as "syst" and "sysa" during idle cycles.

Trending Overlay (Flink + Redis + In-Memory Trending Trie)

Pre-computed rankings live here so reads never sort at query time.

• Near-Real-Time Overlay: Because hourly trie rebuilds cannot capture breaking news spikes, a lightweight trending overlay is refreshed every 5 minutes.
• Velocity Detection: Apache Flink consumes search-events and evaluates 1-hour tumbling window frequencies against a 24-hour historical baseline.
• Prefix-Aware Redis Storage: A standard flat Redis sorted set cannot efficiently answer prefix queries such as matching "sys". Redis stores trending queries partitioned into prefix buckets (such as trending:prefix:{prefix_2char}) alongside a global top-trending set with a 1-hour expiration.
• Local Trending Trie: Each autocomplete serving node maintains a lightweight in-memory Trending Trie synchronized from Redis prefix buckets every 5 minutes, allowing sub-millisecond prefix searches on trending terms.
• Result Blending and Deduplication: During query execution, the service queries both main_trie.search(prefix) and trending_trie.search(prefix). It merges the two result sets, boosts trending scores according to freshness weights, deduplicates identical terms, and returns the top 10 results within the 15ms lookup budget.

Event Bus Design (Kafka)

The event bus decouples producers from consumers and buffers traffic spikes.

topic: search-events
partitions: 64
partition_key: normalized_query # preserves per-query ordering for frequency aggregation
retention: 7 days # streaming replay and recovery; long-term data archived to object storage
replication_factor: 3
min_insync_replicas: 2

producer:
  collector: search-log-collector
  sampling_rate: 1-in-10 sampled at API gateway
  schema:
    event_id: string
    query: string
    user_id_hash: string
    timestamp: int64
    country: string
    language: string
    result_count: int32

consumer_groups:
  flink_aggregator:
    window: 1-hour sliding window with 5-minute slide
    sink: Aggregated Query DB (frequency deltas)
  trending_detector:
    metric: velocity compared against 24-hour baseline
    sink: Redis prefix buckets backing in-memory Trending Trie overlay
  trie_builder:
    schedule: hourly batch job (Apache Spark / offline builder)
    action: reads aggregates, rebuilds immutable trie binary blob, and uploads to S3

serving_path:
  loader: Autocomplete Service loads immutable trie snapshot from S3
  merge_strategy: prefix query on main trie union prefix query on trending trie (top-10 combined)

dead_letter_queue:
  topic: search-events-dlq
  max_retries: 3
  alert_condition: Flink consumer lag exceeds 30 minutes (warning alert; lag >2 hours triggers severe incident escalation)