Walkthrough: Search Autocomplete

Search autocomplete ("type 'we', see 'weather'") looks tiny and hides a beautiful architecture: a read path that must answer in tens of milliseconds on every keystroke, and an offline pipeline that continuously rebuilds what the read path serves. If you did the trie module in the DSA track, this is that data structure meeting production traffic.

Step 1: Requirements

Functional:

1. Given a prefix, return the top 5–10 most popular completions.
2. Suggestions reflect what people actually search (driven by query logs).
3. Trending queries show up reasonably fresh (within, say, an hour).

Non-functional:

• Under 100ms per suggestion request — it runs on every keystroke, so latency is the product.
• Extremely read-heavy: reads outnumber log-driven updates by orders of magnitude.
• Suggestions may lag reality — freshness is a tunable, not a consistency requirement.

Step 2: Estimation

10M DAU × ~20 keystrokes across searches ≈ 200M suggestion requests/day ≈ ~2,300 QPS average, several thousand at peak. Modest — the challenge is latency, not throughput. And note what a keystroke means: every character typed is a request, which is why the client debounces (waits ~100–200ms of typing pause before firing) and caches results per prefix locally.

Step 3: Core entities

Query log entry (what was searched, when), Suggestion set (prefix → ordered top-k completions). That's the whole data model — the interesting part is how the second is derived from the first.

Step 4: API

GET /v1/suggestions?q=we   -> { suggestions: ["weather", "web series", ...] }

One endpoint. Spend your time on what's behind it.

Step 5: High-level design — two ways to serve a prefix

Option A — walk a trie at query time. A trie (prefix tree — one node per character, shared prefixes share paths) holds all queries with frequency counts. On request: walk to the prefix node, explore the subtree, collect completions, rank by count, return top k. Correct, but exploring a big subtree ("a" has millions of descendants) busts the 100ms budget.

Option B — precompute top-k per prefix. Notice the query never needs the subtree — only the top k. So compute the answer for every prefix ahead of time and store it in a key-value store:

"w"   -> ["weather", "walmart", ...]
"we"  -> ["weather", "web series", ...]
"wea" -> ["weather", "weather radar", ...]

Serving becomes a single Redis GET: ~1ms. You can keep the trie mentally as the structure you're flattening — each stored key is a trie node with its top-k cached at the node. This trades storage and freshness for latency, which is exactly the right trade here. Lead with Option B; name Option A as the thing it optimizes.

Storage math to defend it: storing top-10 for prefixes (say up to 10 chars) of the ~100M distinct popular queries is on the order of tens of GB — one Redis cluster, easily sharded by prefix. Cap suggestion length and k to keep it bounded.

Step 6: The offline pipeline

Where do the top-k lists come from? An aggregation pipeline over query logs:

1. Every search appends to a log (via Kafka or batched files).
2. A periodic batch job (hourly, for our freshness target) aggregates counts per query — typically weighted toward recent windows so trends surface and stale queries decay.
3. A builder computes top-k per prefix from the aggregated counts.
4. The result is loaded into the serving store.

The hot-swap matters: never mutate the live keys in place while serving. Build the new suggestion set under versioned keys (or a fresh cluster), verify it, then flip a version pointer atomically — readers see wholly old or wholly new data, never a half-updated mix, and rollback is just flipping the pointer back.

Deep dives to expect

Freshness vs cost. Hourly batch satisfies "trending within an hour". If the interviewer pushes to minutes ("breaking news"), describe the streaming upgrade: a stream processor maintains counts over sliding windows and patches hot prefixes' top-k incrementally, while the batch job remains the periodic source of truth. Batch is the mid-level answer; knowing the streaming step exists is upside.

Hot prefixes. Single-character prefixes ("t", "a") are requested overwhelmingly often — classic hot keys. They're also few: cache the top few hundred hottest prefixes in each API node's local memory with a short TTL, and let the CDN cache suggestion responses briefly too. Staleness of seconds is invisible here.

Filtering and personalization. Profanity/blocklist filtering runs in the pipeline (never serve it, rather than filter at read time). Personalization at mid-level: a light client- or server-side merge of the user's own recent searches over the global list — don't build a per-user trie.

Wrap-up

Recap: the read path is a debounced client hitting a Redis lookup of precomputed top-k per prefix — comfortably under 100ms; the write path is an hourly log-aggregation pipeline rebuilding suggestions and atomically swapping versions; hot prefixes get local caching; freshness is tunable from hourly batch down to streaming patches. With more time: per-locale suggestion sets and spell-tolerant matching.