Q70 — Design a search autocomplete system

What the system must do

As a user types in a search box, the system returns the top N suggested completions for the current prefix — in under 100ms. "wir" → ["wireless headphones", "wireless earbuds", "wireless charger", "wire transfer", "wireless mouse"]. Suggestions are ranked by popularity (most searched completions first).

Requirements:

Return top 5–10 suggestions for a given prefix
P99 latency < 100ms (the box must feel instant)
Suggestions ranked by query frequency / popularity
Update suggestions based on recent search trends (hourly or daily)
Scale: millions of users typing simultaneously, billions of historical queries

The core data structure: the Trie

A Trie (prefix tree) is the natural data structure for prefix lookups. Each node represents a character. The path from the root to any node spells a prefix. Each node stores the top N completions for that prefix (pre-aggregated at build time).

code

         (root)
        /     \
       w       b
      / \       \
     i   o       l
    /     \       \
   r       r       u
  /         \       \
 e           d       e
  \           \
   l           "word"
    \
     e
      \
       s → "wireless", score: 9500000
      \
       s → "wireless headphones", score: 8100000

At each node, pre-store the top-5 completions with their scores. A query for "wir" traverses to the "wir" node and returns its precomputed top-5 list immediately — O(L) time where L is the prefix length, no further traversal needed.

The trie is built offline from query log aggregates: "what are the top-5 completions for every possible prefix?"

Why the trie is fast enough (when in memory)

Traversal to a node is O(L) — at most 10–15 character lookups for any realistic prefix. Once at the node, return the precomputed list — O(1). The entire operation is a few dozen memory accesses.

With a 26-character alphabet and an average of 3 children per node (most nodes have few children), a trie of 10 million unique queries takes roughly 1–2GB of memory — fits in RAM on a single server.

At query time, the trie is fully in-memory. No disk I/O, no database queries. This is why autocomplete can respond in under 5ms.

The scale problem: trie doesn't fit on one machine

10 million queries is manageable on one machine. But a system like Google has billions of unique queries. At that scale, the trie must be distributed.

Sharding by prefix: partition the trie by the first two characters of the prefix. All queries starting with "wi" go to shard "wi". All queries starting with "wo" go to shard "wo". A routing layer maps the first two characters of the user's input to the correct shard and forwards the request.

Each shard hosts a complete trie for all prefixes starting with its assigned characters. This distributes both memory and query load.

Problem: prefix distribution is skewed. "the", "and", "in", "to" are searched far more than "xz", "qv". You need to rebalance shards by query frequency, not alphabetically.

Building and updating the trie

The trie is not built from raw query logs in real time — that would be too expensive. It's built in a periodic offline batch pipeline:

Collect: every search query is logged to Kafka. A stream processor (Spark or Flink) aggregates query counts over a rolling 7-day window.
Rank: for every prefix P, compute the top-N completions (full query strings that start with P) by 7-day query count.
Build: construct the trie from the ranked completions. Store the top-N at each node.
Serialize: serialize the trie to a binary blob, upload to distributed storage (S3).
Deploy: autocomplete servers periodically download the new trie (e.g., hourly) and hot-swap in-memory. During the swap, the old trie continues serving — zero downtime.

This gives freshness of 1 hour. For rapidly trending queries (a celebrity news story breaks), there's a lag before the trie reflects it. Acceptable for most use cases. Real-time trie updates are possible but significantly more complex.

Handling the HTTP path — why it matters

Every character the user types triggers a new request. Typing "wireless" sends 8 requests: "w", "wi", "wir", "wire"... This creates a high-volume, latency-sensitive request path.

Debounce on the client: don't send a request on every keystroke — wait 100ms after the user stops typing. This reduces requests by ~80% with no noticeable UX impact.

Cancel in-flight requests: if the user types faster than responses arrive, cancel the previous pending request before sending the new one. Users see only the result for their latest prefix.

CDN caching: autocomplete results for common prefixes ("the", "in", "ap") can be cached at the CDN edge. The same query from millions of users returns the same result — extremely high cache hit rate for popular prefixes.

Connection persistence: use HTTP/2 or keep-alive connections so each keystroke doesn't pay TCP handshake overhead.

Personalization

Google's autocomplete is not purely global popularity — it incorporates:

Your recent search history ("wir" might suggest "wire transfer" if you've searched it recently)
Geographic region ("soccer" vs "football" completion by country)
Language

Personalization is a second layer on top of the trie: the base layer returns globally popular completions, and a personalization layer re-ranks or injects completions based on user context. This personalization layer runs at query time (not pre-baked into the trie) using user history data from a fast key-value store (Redis or Cassandra keyed by user_id).

The mental model

code

Core data structure: Trie (prefix tree)
  Each node = one character; path from root = prefix
  Each node stores pre-computed top-N completions with scores
  Query: traverse to prefix node → return pre-stored top-N → O(L) time

In-memory for speed:
  10M queries trie ≈ 1–2GB RAM → single server
  Zero disk I/O at query time → <5ms latency easily achievable

Scaling (billions of queries):
  Shard by first 2 characters of prefix → distributed tries
  Routing layer: "wi..." → shard "wi" → return results
  Rebalance shards by query frequency (not alphabetically)

Build pipeline (offline, periodic):
  Raw queries → Kafka → stream aggregation (7-day rolling counts)
  Top-N completions per prefix → build trie → serialize → upload to S3
  Servers hot-swap trie hourly → zero-downtime update
  Freshness: ~1 hour lag for trending queries

Request optimization:
  Client debounce (100ms after last keystroke) → 80% fewer requests
  Cancel in-flight requests → always show latest prefix result
  CDN cache popular prefixes → very high hit rate for common starts
  HTTP/2 persistent connections → no per-request TCP overhead

Personalization (second layer):
  Base: global popularity trie (batch-built)
  Personal: user history + location → re-rank at query time (Redis lookup)

The key insight:
  Precompute the answer at every node at build time
  At query time, just traverse + return — no computation
  This is the "move work to write time" principle applied to tries

Autocomplete is a case where the data structure choice (trie with precomputed top-N at every node) completely determines the system's performance characteristics. Everything else — sharding, offline build pipeline, CDN caching, debouncing — is infrastructure built to serve that core data structure efficiently at scale.