Search Autocomplete — Trie-Based Suggestions

Search autocomplete is one of the most commonly asked system design interview questions at companies like Google, Amazon, and Microsoft because it tests a candidate's ability to combine data structures, caching, and real-time streaming into a cohesive low-latency system. The core challenge seems straightforward — return relevant query suggestions as the user types — but the constraints at production scale transform it into a deeply nuanced problem that touches on prefix indexing, ranking algorithms, freshness guarantees, and sub-millisecond lookup requirements.

At Google's scale, the autocomplete system handles hundreds of thousands of requests per second, with each keystroke generating a new query. Users expect suggestions to appear instantly — any latency above 100ms feels sluggish and degrades the search experience. The system must serve suggestions from a corpus of over one billion unique queries, ranked by a combination of global popularity, personal search history, and real-time trending signals. When a major news event breaks, trending queries must surface in suggestions within minutes, not hours.

The problem becomes especially interesting when you consider the data structure trade-offs. A naive approach of scanning all stored queries for prefix matches is O(N) per request and completely infeasible at scale. A trie (prefix tree) reduces lookup to O(prefix_length), but storing one billion queries in a trie requires careful memory optimization. Pre-computing top-K suggestions at each trie node eliminates the need for real-time sorting but increases memory consumption and rebuild time. Candidates must reason about these trade-offs and design a system that balances lookup speed, memory footprint, and data freshness.

This template models the complete autocomplete architecture: an API gateway for rate limiting, a load balancer distributing across stateless service pods, an in-memory trie with pre-computed top-K suggestions, a Redis cache for trending boosts, a DynamoDB store for aggregated query counts, and a Kafka-based streaming pipeline that processes search logs and periodically rebuilds the trie. The simulation reveals how trie size affects pod memory requirements, how the streaming pipeline impacts suggestion freshness, and how the two-layer approach of static trie plus dynamic trending boosts balances stability with real-time responsiveness.

The autocomplete architecture follows a two-layer design: a static in-memory trie for fast prefix lookups and a dynamic trending layer in Redis for real-time freshness. The data flow begins when a user types a character in the search box. The TypeaheadClient sends a GET request through the API Gateway, which handles authentication and per-user rate limiting to prevent scraping. The MainLB distributes requests via round-robin across 20 AutocompleteService pods, each of which holds a complete copy of the trie in memory.

The AutocompleteService performs the core lookup by traversing the in-memory trie from the root to the node matching the user's prefix. Each trie node stores the pre-computed top-10 suggestions for its prefix, so the lookup completes in O(prefix_length) time — typically under one millisecond with no sorting required at query time. For prefixes that match active trends, the service also queries the TrieCache (Redis) for trending boost scores and merges them with the static trie rankings, re-ranking the combined candidates before returning the final top-N results.

The freshness pipeline runs in parallel. Every completed search query is logged to SearchLogStream (Amazon MSK / Kafka). TrieRebuildWorker pods consume these logs, aggregate per-prefix query counts across sliding time windows (one-minute, one-hour, one-day), and write updated counts to QueryDB (DynamoDB). Every five minutes, the worker triggers a full trie rebuild: it reads all query counts from DynamoDB, constructs a new trie with pre-computed top-K at each node, and pushes trending boost scores to TrieCache. AutocompleteService pods periodically reload the rebuilt trie via an atomic pointer swap — the old trie is replaced by the new one in a single operation, ensuring zero downtime during refresh.

This architecture deliberately separates the hot read path (in-memory trie, zero network dependency) from the write path (Kafka, DynamoDB, periodic rebuild). The trie itself never changes during a serving window, which eliminates the need for concurrent read-write locking. The trending boost layer in Redis provides near-real-time responsiveness for breaking queries between full trie rebuilds, giving the system the best of both worlds: stable, fast prefix lookups with timely surfacing of trending content.