Design a Search Autocomplete System

1. The problemCopy Anchor Link

Type "tw" into a search box → before you finish, a dropdown shows 5 completions. Suggestions must appear while you type → a latency budget of tens of milliseconds, hit on nearly every keystroke by every user.

Autocomplete is two systems: a slow one that decides what the answers are, and a fast one that just looks them up.

• Query service (fast, online) — returns a precomputed answer for a prefix. Never computes top-k at request time.
• Data gathering service (slow, offline) — counts what people search, rebuilds the precomputed answers periodically.

Links to earlier notes: the news feed precomputed each user's feed; this precomputes each prefix's answer. The feed needed a celebrity fast path; this needs a trending fast path (§10).

2. Requirements (extract these)Copy Anchor Link

Non-functional: fast (≤ ~100 ms per keystroke), relevant, sorted, scalable, highly available.

Senior questions to ask unprompted — each changes the design:

3. EstimationCopy Anchor Link

  10M DAU × 10 searches × 20 chars (4 words × 5) → a request per character
  = 2×10⁹ requests/day ÷ 86,400 s           ≈ 24,000 QPS     peak ×2 ≈ 48,000 QPS
                                             (÷10⁵ shortcut → 20,000; same decision)
  new data: 10M × 10 × 20 B × 20% new        ≈ 0.4 GB/day

Every number ends with a decision:

• 0.4 GB/day is tiny → storage isn't the problem; don't lead with sharding.
• 24k–48k QPS in 100 ms → every request must be a memory lookup; the cheapest request is the one never sent.
• 20 requests per search is mostly waste → the client is part of the design (§7).

4. Naive version — and breaking itCopy Anchor Link

SELECT query FROM frequency_table
WHERE query LIKE 'tw%' ORDER BY frequency DESC LIMIT 5;

• Scans and sorts on every keystroke — LIKE 't%' matches millions, sorted to keep 5, 48k times/sec.
• Short prefixes are the most common AND the most expensive — everyone types the first letter; it matches the most rows.
• An index on query finds matches but not the top 5 by frequency — still sorts the whole match set.

Fix = a prefix data structure + precompute the answer so nothing sorts at request time.

5. The trie and the optimization that mattersCopy Anchor Link

Trie = prefix tree: root is empty string, each child adds one character, a path spells a prefix; every query starting with "tw" lives under node "tw".

Naive top-k on a trie:

1. walk to prefix node — O(p)
2. traverse whole subtree to collect completions — O(c)
3. sort, take top k — O(c log c)

Steps 2–3 are still the problem (subtree under "t" = millions).

Book's two optimizations:

5.1 Senior insight: at serving time the trie collapses to a hash mapCopy Anchor Link

Once every node stores its answer, serving never walks an edge — hash the prefix straight to its list:

  "t"  → [true, try, toy]      "tr" → [true, try, tree]     "to" → [toy]
  "w"  → [win, wish]           "wi" → [win, wish]

• Book's two storage options: serialized trie snapshot in a document store, or KV store: prefix → node data ("prefix hash table"). KV's con: loses the parent–child relationship between levels.
• That relationship matters at build time: compute each node's top-k bottom-up by merging its children's lists — far cheaper than scanning all queries per prefix.

The trie is the build-time algorithm; prefix → top-k map is the serving format.

5.2 The "buy" option — FSTsCopy Anchor Link

Elasticsearch completion suggester: in-memory finite-state transducer (compressed trie relative), per-suggestion weight for ranking, fuzzy support for typos; costly to build, held in memory, rebuilt periodically. Handles distribution, replication, failover. Mention it, then design the build-it version — the interviewer wants the mechanics.

6. High-level designCopy Anchor Link

Data gathering (offline)Copy Anchor Link

Query service (online)Copy Anchor Link

Client → regional LB → stateless API server → in-memory lookup of the prefix → filters (§9) → 5 strings. Miss → read trie DB, fill cache (rare: the map usually fits in RAM, §8).

7. Making the query path fast — mostly on the clientCopy Anchor Link

8. Scaling the storage — and when not toCopy Anchor Link

8.1 Do the memory math first (the most valuable senior move)Copy Anchor Link

  keep ~10M distinct queries (drop the long tail), ~20 chars avg
  distinct prefixes  ≤ 10M × 20, heavily shared   → ~50M prefixes
  value              5 × ~25 B + overhead          ≈ ~150 B
  key                                              ≈ ~20 B
  total              50M × ~170 B                  ≈ ~8.5 GB → fits in one server's RAM

→ No sharding. Full copy on every serving node; replicas for throughput + availability. Read-only between rebuilds → every replica loads the same snapshot → trivially consistent; no routing, no shard map, no hot shards.

"At this scale the index fits in memory, so I replicate it fully. I shard only when it stops fitting — many languages, per-region indexes, or Google-scale vocabulary."

8.2 When it doesn't fit — book's progressionCopy Anchor Link

• Range vs hash: ranges keep related prefixes together and split exactly where volume is; hashing a fixed-length prefix spreads load but can't split one hot range. Volume-aware map is the book's answer.
• Rebuild the shard map with each snapshot from the same aggregated data.
• Hot shard → more replicas, not more shards (read-only scales by copying); Redis/CDN response cache absorbs the hottest prefixes.

9. Trie operations: create, update, deleteCopy Anchor Link

Create — workers from aggregated data (§6).

Update

Delete — harmful suggestions must vanish now, not next week:

• Filter layer between API servers and trie cache checks a blocklist on the way out → a newly blocked phrase disappears in seconds.
• Physically removed from the index at the next rebuild.

Manipulation defense (raise unprompted) — bots searching a phrase a million times would promote it under naive counting:

• count distinct users per query, not raw searches,
• cap per-user / per-IP contribution to a count,
• minimum distinct-user threshold before a query is eligible.

10. Ranking beyond raw frequency, and trendingCopy Anchor Link

10.1 Time decayCopy Anchor Link

Weight recent periods more: each period's count × a factor that shrinks with age → a two-year-old fad stops outranking this week. Changes aggregation only; serving untouched.

10.2 Trending — the weekly snapshot is too slowCopy Anchor Link

Bar: a viral query should appear within minutes. Can't rebuild the whole index every minute → a second, small, fast path (same idea as the news feed's celebrity merge).

• Stream search events (Kafka) → stream processor (Flink / Spark Streaming) counts over short windows (15 min, 1 h).
• Billions of unique strings → no exact per-query counts. **Count-Min Sketch
  • min-heap of size K**: sketch = approximate counts in fixed memory; heap = current top K. Sketch can overestimate, never underestimate — the safe direction for heavy hitters.
• Detect acceleration, not volume: recent rate ≫ usual rate. "weather" is always popular, not trending.
• Publish a tiny trending overlay: prefix → a few hot queries, refreshed ~every minute (only thousands trend at once).

10.3 PersonalizationCopy Anchor Link

Per-user data inside the shared index destroys caching (every response unique). Personalize at the API layer, not in the trie. Better still: keep recent searches on the device and merge client-side → server response stays fully global and cacheable.

10.4 Request-time blendingCopy Anchor Link

• Heavy part stays global + cacheable — snapshot + trending is the same for everyone in a region → CDN with a short TTL (~1 min) so trending stays fresh.
• Personal part small + private (or on-device).
• Filter runs last, over everything — trending is the source an attacker can push fastest; nothing bypasses the blocklist.
• ⚠️ Cache headers must follow the blend. Google's private, max-age=3600 (§7) fits a personalized response. Here the server response is global (personal merge on device) → public, max-age=60: CDN can cache it, and trending is at most a minute stale. A 1 h browser cache would freeze the overlay — and delay a blocklisted phrase leaving the dropdown by up to an hour.

10.5 Other signals / extensionsCopy Anchor Link

All change aggregation/build; serving stays lookup + merge.

11. Failures and consistencyCopy Anchor Link

Autocomplete is allowed to be slightly wrong — yesterday's list is fine, a missing suggestion is fine, the user can just type.

Degrade, never fail. Fall back to the last good snapshot; if even that is gone, the search box still works without suggestions.

12. End-to-end trace (narrate, then break)Copy Anchor Link

  user types "tw"
  client   debounce 120 ms → browser cache miss → GET /autocomplete?q=tw  (request #7)
  edge     CDN miss → regional LB → API server
  server   in-memory snapshot "tw" → [twitter, twitch, twilight, twin peaks, twitch prime]
           trending overlay "tw" → breaking-news query (entered 4 min ago)
           merge + rerank → trending takes slot 3 → safety filter passes all 5
           → Cache-Control: public, max-age=60 (global response; §10.4)
  client   response is #7 and input still "tw" → render; merge 2 on-device recent searches
  submit   search appended to analytics log → sampled → stream window counts
           → this week's aggregates → next week's snapshot

  BREAK 1  "tw" pause → "twitch"; "tw" response arrives after the "twitch" request
           → stale prefix → dropped; dropdown never flickers backward
  BREAK 2  bot campaign pushes a defamatory "tw…" phrase → huge volume, few distinct users
           → never eligible; even if it were, blocklist removes it from every response in seconds
  BREAK 3  weekly build crashes → nothing visible: old snapshot serves, trending keeps it fresh,
           rerun in the morning

13. Interview scriptCopy Anchor Link

  1. clarify      prefix-only · 5 results · frequency ranking · English · 10M DAU · <100 ms
                  FRESHNESS? PERSONALIZED? HARMFUL-SUGGESTION FILTER? locales? typos?  ← unprompted
  2. estimate     24k QPS (peak 48k) · 0.4 GB/day → storage tiny, latency + request count are the problem
  3. framing      two systems: fast lookup path, slow build path — never top-k at request time
  4. naive        LIKE + ORDER BY → scans & sorts per keystroke, worst on short prefixes
  5. trie         → cap prefix length → cache top-k per node (space + duplication)
  6. collapse     trie = build algorithm; prefix → top-k map = serving format; FST = buy option ← senior
  7. high level   logs → aggregators → aggregated → workers → trie DB → trie cache; client → LB → API
  8. client       AJAX · browser cache max-age · debounce · min prefix · drop stale · CDN · regions
  9. storage      MEMORY MATH FIRST → replicate fully if it fits; else first-char → volume shard map ← senior
 10. operations   blue-green weekly swap + rollback · in-place update costs ancestors · live filter
 11. ranking      time decay · trending stream (CMS + heap, acceleration) · personalization off-index
                  · merge at request time · filter last                                    ← senior
 12. abuse        distinct users · contribution caps · eligibility threshold              ← unprompted
 13. failures     degrade, never fail
 14. walk it      "tw" end to end, then break it three ways

Steps 6, 9, 11 and 12 separate a pass from a strong pass.

14. The lines that earn the mostCopy Anchor Link

1. "Autocomplete is two systems: a fast path that only looks things up and a slow path that decides the answers — never compute top-k at request time."
2. "Short prefixes are both the most frequent and most expensive requests, which is why the answer has to be precomputed."
3. "Caching top-k at every node trades space and ancestor-update cost for O(1) lookups — and then the trie collapses to a prefix → top-k map; the trie is the build algorithm."
4. "The client is part of the design: debounce, browser cache with max-age, minimum prefix length, and drop out-of-order responses."
5. "I do the memory math before sharding: ~8.5 GB fits in RAM, so I replicate fully; volume-based sharding only when it doesn't fit."
6. "New snapshots swap in atomically with rollback; harmful suggestions are removed by a live filter, not the next rebuild."
7. "Trending is the celebrity merge of autocomplete: a small streaming overlay — Count-Min Sketch plus a heap, detecting acceleration — merged at request time."
8. "Personalization stays out of the shared index so the global response stays cacheable — ideally merged on the device."
9. "Count distinct users, cap per-user contribution — otherwise a bot can write your suggestions."
10. "Autocomplete is allowed to be slightly wrong: degrade, never fail."

15. Numbers to rememberCopy Anchor Link

16. Common follow-upsCopy Anchor Link

17. When NOT to go deepCopy Anchor Link

Inside a bigger question ("design Google Search" / "design a marketplace"):

"Typeahead is served from an in-memory prefix → top-k map rebuilt offline from aggregated query logs, with a streaming trending overlay merged at request time, a live blocklist filter, and client debounce plus browser caching."

Go deep only when autocomplete IS the question, or the interviewer pushes on freshness, ranking or scale.

18. Glossary (A–Z, one line each)Copy Anchor Link