Design typeahead suggestions

Suggest completions as the user types into a search box, within tens of milliseconds, ranked by popularity and fresh with trending queries.

We are building the autocomplete service behind a search box: as each keystroke arrives, return the top 10 completions for the typed prefix in tens of milliseconds, ranked mostly by how often people search them and boosted for queries that are trending right now.

Functional requirements

• Given a prefix (and locale), return up to 10 ranked query completions.
• Ranking blends long-term popularity with recent velocity, so a breaking-news query appears within minutes, not the next day.
• Every submitted search (and accepted suggestion) feeds back into the counts.
• Trust and safety can block a query or term (offensive, legal takedown, self-harm) and it disappears from suggestions within a minute.
• Out of scope for the core: spell correction and per-user personalization (covered as extensions).

Non-functional requirements

• p99 under 50 ms server side; the client fires a request per keystroke, so anything slower than typing speed feels broken.
• Very high availability; a stale suggestion list is fine, an empty one is not. Serve last good data on any pipeline failure.
• Eventual consistency for counts: a few minutes of lag for trending, hours for the long-tail popularity table.
• Read-dominated: reads outnumber writes by roughly 5:1 (keystrokes vs. submitted searches), and writes never touch the serving path synchronously.

Back-of-the-envelope estimation

• 1B searches/day, ~6 keystroke requests per search after client debounce → 6B suggestion requests/day ≈ 70K QPS average, ~200K QPS peak.
• Distinct queries over 30 days: ~5B, but the long tail is noise. Keep queries seen ≥ 5 times in the window: ~200M candidates.
• Average query 25 bytes. A trie over 200M queries with top-10 lists cached at each node: ~1B nodes worst case, compressed (radix) to ~300M nodes × ~60 B (edge label, child offsets, top-k ids) ≈ 20 GB, plus a 200M × 25 B ≈ 5 GB string table. Too big for one box comfortably, so shard or trim per locale.
• Ingestion: 1B searches/day ≈ 12K events/s, peaks 50K/s, ~200 bytes each ≈ 200 GB/day of raw logs.
• Prefixes of length 1–3 are a tiny set (for English, at most ~18K) but take a large share of traffic; they are the cache sweet spot.

GET /v1/suggest?q=how%20to%20ma&locale=en-US&limit=10&session=abc123
200 OK
Cache-Control: public, max-age=60
{
  "prefix": "how to ma",
  "suggestions": [
    {"text": "how to make pancakes", "score": 0.91, "kind": "query"},
    {"text": "how to make money online", "score": 0.88, "kind": "query"}
  ],
  "version": "en-US/2026-10-12T10:00Z+d17"
}

• q is normalized server side (lowercase, Unicode NFKC, collapse whitespace) before lookup, so the cache key is stable.
• The client debounces (~50 ms), cancels in-flight requests on the next keystroke, and keeps a local LRU of recent prefixes; backspace hits the local cache.
• Supporting surfaces:
  • POST /v1/events {query, accepted_suggestion, position, locale, ts} — logs a submit or click; fire and forget into the event bus.
  • POST /v1/admin/blocklist {pattern, match: "exact"|"token"|"prefix", locale, reason} → {rule_id, effective_at} — trust and safety removal.
  • GET /v1/admin/suggest-debug?q=... — shows raw scores and which rules filtered what, for on-call.

Core invariants:

• Every trie node stores the top-k (k = 10–15) completions of its subtree, precomputed. A lookup never walks the subtree at request time.
• Snapshots are immutable and versioned; a server only ever serves one complete version per shard, never a half-built one.
• Blocked text never leaves a server, whatever the snapshot says: the filter runs at serve time as well as at build time.

Storage shape: a precomputed trie (O(prefix length) lookup, large memory) vs. a plain prefix → top-k hash map for all prefixes up to length N (fastest lookup, but duplicates lists for every prefix and explodes past ~20 chars). The trie with cached top-k wins; for prefixes beyond the trie's depth limit (say 30 chars) we fall back to the deepest node and filter by the full prefix.

flowchart LR
  U[Search box] --> CDN[CDN edge cache]
  CDN --> LB[Load balancer]
  LB --> AGG[Suggest aggregator]
  AGG --> PC[Prefix cache]
  AGG --> TS1[Trie server shard A]
  AGG --> TS2[Trie server shard B]
  AGG --> TR[Trending overlay]
  U -. search events .-> EV[Event bus]
  EV --> STR[Stream aggregator]
  STR --> TR
  EV --> LAKE[Query stats lake]
  LAKE --> BLD[Batch trie builder]
  BLD --> SNAP[Snapshot store]
  SNAP -. pull new version .-> TS1
  SNAP -. pull new version .-> TS2
  BL[Blocklist service] -. push rules .-> AGG
  BL -. push rules .-> BLD

1. Prefix query serving. The keystroke request hits the CDN; short and popular prefixes are answered there (60 s TTL). On a miss, the aggregator normalizes the prefix, checks its in-process prefix cache, then calls the trie shard that owns the prefix. The shard walks the trie (a few hundred nanoseconds per character) and returns the cached top-k. The aggregator merges in the trending overlay's candidates for that prefix, re-scores, drops anything matching the blocklist, and returns 10. Total server time: ~5 ms on a miss, sub-ms on a cache hit.
2. Signal ingestion and periodic aggregation. Search events go to Kafka. A stream job (Flink) keeps 5-minute tumbling counts per query and computes velocity against a baseline; queries with a spike are pushed to the trending overlay every minute. A separate sink writes events to the lake; a daily (or 6-hourly) batch job computes decayed popularity, builds new trie shards, and publishes them. Trie servers load the new version beside the old one and swap a pointer.

Aggregation pipeline and trie rebuild. Score each query as S = Σ_days count_d × 0.5^(age_d / 7) (one-week half-life), plus a click-through bonus. The batch job: filter queries with count ≥ 5 and not blocked, normalize, group by locale, sort by key, then build the trie bottom-up so each node's top-k is a merge of its children's top-k and its own terminal score; this is a single linear pass over sorted keys, about 30 minutes for 200M queries on a modest Spark cluster. Output is a flat array layout (nodes in DFS order, children as offsets) that servers mmap directly, so loading a 10 GB shard takes seconds and needs no deserialization. Rollout: canary 1% of servers, compare suggestion click rate and error rate for 15 minutes, then roll out; the manifest keeps the last three versions for one-step rollback.

Freshness is a two-tier problem, not a reason to rebuild constantly:

The overlay is built by expanding each trending query into its prefixes (a 25-char query gives 25 entries), keeping top-5 per prefix: 100K × 25 ≈ 2.5M entries, a few hundred MB, replicated to every aggregator. Final score = base_score + w × velocity, where velocity is count_last_15m / expected_15m_from_baseline, capped so one bot burst can't dominate. Bots are filtered upstream: count each query at most once per user or IP per hour.

Hot-prefix caching and distributed serving. Traffic is heavily skewed: the 1–3 character prefixes are a few thousand keys taking ~30% of requests. Three cache layers: CDN (60 s TTL keyed by locale + prefix, hit rate ~50%), aggregator in-process LRU (~1 GB, catches most of the rest of the head), then trie servers. Sharding the trie:

Each shard holds ~5 GB and is replicated 3+ times per region; the aggregator routes by binary search over split points. Short prefixes whose subtree spans several shards (e.g. "s" split into "s–sh" and "si–sz") are answered from a small "head table" built alongside the trie that every server holds: the top-k for every prefix of length ≤ 3. Replicas scale with QPS, shards scale with data size, independently.

Content suppression without a full rebuild. A takedown must take effect in under a minute, but rebuilds are daily. So filtering happens at serve time: the blocklist service pushes rules to every aggregator (pub/sub plus a 30 s poll as backup), compiled into an exact-match hash set plus an Aho–Corasick automaton for token rules. The aggregator asks the trie for k = 15 rather than 10 so it can drop blocked items and still fill 10; if more than 5 are dropped (a prefix like an offensive word), it returns fewer rather than walking the subtree. CDN entries for affected prefixes are purged by prefix on rule creation. The next batch build applies the rules permanently so the over-fetch buffer is not consumed day after day. Suppression is audited: every rule records who, why, and when, and the debug endpoint shows which rule removed what.

Trie memory and compaction. A naive pointer trie is ~10× the size of its strings. Reductions that matter: radix (path) compression merges single-child chains, cutting nodes by ~3×; store top-k as 4-byte ids into a string table instead of strings; delta-encode scores in 2 bytes; succinct (LOUDS) encoding for the tree structure if memory is still tight, at some CPU cost; prune nodes whose best completion scores below a threshold. Together these take a 60 GB naive trie down to ~10–15 GB per locale.

Personalization and languages (extensions). Personalization layers on top: the aggregator fetches the user's recent queries (a small per-user store, last 100 queries, ~5 ms budget) and blends matches that share the prefix above global results; personal results never enter the shared cache, so the cache key stays global. Languages: one trie per locale; normalize with NFKC and case folding, strip diacritics for a match key while displaying the original; for CJK, index by character, and for Japanese also index the kana reading so romaji or kana input matches kanji queries; right-to-left scripts need no trie changes, only display handling.

• Precomputed top-k at every node gives O(prefix) lookups at the cost of memory and a heavy build; the alternative (walk the subtree at query time) is cheap to store but fails latency for short prefixes.
• Daily rebuild + streaming overlay keeps the main structure immutable and simple, but trending ranking is approximate and adds a merge step to every request.
• Serve-time blocklist filtering is near-instant but costs over-fetch and a filter on every request, and can return fewer than 10 items.
• CDN caching with a 60 s TTL absorbs half the load but means trending items and removals lag by up to a minute unless purged.
• Range sharding avoids scatter-gather but needs rebalancing every build and a separate head table for short prefixes.
• Dropping queries with fewer than 5 occurrences shrinks the trie and protects privacy (a rare query can leak someone's personal search), at the cost of long-tail coverage.

Mid-level (L4)

• Proposes a trie with top-k cached per node and explains why walking the subtree per request is too slow.
• Separates the read path from the logging/aggregation path; offline rebuild, not per-search writes.
• Mentions client debounce and caching of short prefixes.

Senior (L5)

• Sizes the trie and QPS, picks a sharding scheme that keeps one shard per lookup, and handles skewed short prefixes.
• Designs freshness as base snapshot plus trending overlay, with a concrete decay and velocity formula.
• Handles takedowns at serve time with over-fetch, plus versioned, atomically swapped snapshots with rollback.

Staff (L6+)

• Drives the memory layout (mmap'd flat arrays, string table, radix compression) and the build/canary/rollback pipeline end to end.
• Addresses abuse and privacy: bot filtering, count thresholds that keep rare personal queries out, audited suppression.
• Plans extensions without breaking the cache model: personalization blended outside shared caches, per-locale tries and normalization for CJK and diacritics.