Design a Search Autocomplete System

Design a search autocomplete system for 10 million daily active users. As a user types each character, the system returns the top 5 most frequently searched queries that match the typed prefix. Responses must arrive within 100 milliseconds — any slower and the suggestions feel laggy and users stop relying on them.

Scale: 10M users × 10 searches/day × 20 characters/search = ~24,000 queries per second. Peak QPS is roughly double: ~48,000. Each character typed generates one autocomplete request.

A relational database cannot efficiently answer "find the top 5 most popular queries that start with 'din'" at 48,000 QPS. A trie (prefix tree) is the right data structure.

A trie is a tree where each node represents a character. The root is the empty string. To find all words with a given prefix, traverse the tree character by character to the prefix node, then explore all descendants. Each terminal node (end of a complete word) stores the query frequency.

Naive algorithm to find top k queries for prefix p: (1) traverse to prefix node — O(p); (2) explore all descendants to find valid queries — O(n in subtree); (3) sort by frequency — O(n log n). This is too slow at high QPS.

Two optimizations make trie queries O(1):

Optimization 1 — Limit prefix length: users almost never type more than 50 characters in a search box. Cap the prefix length at 50. The traversal to the prefix node is bounded at O(50) = O(1).

Optimization 2 — Cache top k at each node: store the top 5 (or top k) most popular queries at every trie node. When a user types "din", the system simply returns the cached top 5 at the "din" node — no subtree traversal needed. Lookup is O(p) which is O(1) with bounded prefix length.

The tradeoff: storing top k at every node consumes significant memory — O(nodes × k × avg_query_length). For a production system with millions of unique prefixes, this is tens of gigabytes. But the speed improvement makes it worth the cost for a system serving billions of searches.

The trie must reflect the most popular queries, which change over time as search trends evolve. Rebuilding the trie on every search event is infeasible at billions of searches per day.

Architecture: (1) Raw analytics logs capture every search query with a timestamp. (2) An aggregator (batch job, Spark, or similar) runs periodically — say, weekly — and computes the frequency of each query across all logs. (3) The result is a table of (query, frequency) pairs. (4) Workers build a new trie from scratch using this aggregated data. (5) The new trie is serialized and stored in a trie database (e.g., MongoDB for document storage or a key-value store mapping each prefix to its top k results). (6) The trie cache is updated with the new trie.

Weekly rebuilds work for most use cases. For trending queries (breaking news), a shorter cycle (hourly) can be implemented with more limited data — only aggregate the most recent hour's logs rather than all historical data.

Architecture for serving autocomplete requests at low latency:

The client sends each keystroke as an AJAX request: GET /autocomplete?q=din. The request hits a load balancer, which routes to an API server. The API server looks up "din" in the trie cache (an in-memory distributed cache holding the full serialized trie or prefix-to-top-k mapping). Returns the top 5 results as JSON.

Browser caching: autocomplete results for a given prefix rarely change within an hour. The API response includes Cache-Control: private, max-age=3600. The browser caches the result for that prefix — if the user types "din" again within the hour, the browser serves the cached result without making a network request.

Data sampling: not every search needs to be logged for the aggregation pipeline. Logging 1 in every 100 searches is sufficient to capture trends accurately while reducing logging infrastructure costs by 100×.

When the trie grows too large for a single server, shard it. A natural sharding key is the first character of the prefix: all queries starting with "a" go to shard 1, "b" to shard 2, etc. This gives 26 shards for English-only queries.

The problem: character frequency is uneven. "s" and "c" prefixes are far more common than "x" and "z". The "s" shard becomes a hotspot.

Solution: analyze historical query distribution and shard non-uniformly. Instead of one shard per letter, create shards based on data volume: "a-g" on one shard (all less-common letters), "s" alone on another shard (due to high volume). A shard map database stores the routing logic. API servers consult the shard map to route each autocomplete request to the correct shard.

For multi-language support: store Unicode characters (not ASCII bytes) in trie nodes. For country-specific popularity (top searches differ by region), build separate tries per country and store them in CDN nodes closer to each region.