Design a system that returns the top 5–10 query suggestions as the user types, ranked by popularity, updated as search trends change.

• 10B queries/day → ~120k QPS for the search backend; autocomplete calls ≈ 5–8× that → ~700k QPS, mostly cached.
• Distinct queries: 200M × avg 20 chars ≈ 4 GB raw; a trie with top-k cached per node ≈ 3–4× → ~15 GB, fits in memory on a few nodes, sharded by prefix.
• Popularity aggregation: 10B events/day = 116k/s into a stream processor; hourly batch produces ~200M counts.

GET /v1/autocomplete?q=how+to&limit=8&locale=en-IN
→ { "suggestions": ["how to tie a tie", "how to cook rice", ...] }

Client debounces (~100 ms) and cancels in-flight requests when the prefix changes.

Trie node: {children, topK: [(query, score)]}, topK precomputed. Persisted as a serialised snapshot in object storage; served from memory. Popularity source: query_counts(query, window, count) in a wide-column store.

1. Data collection: search service logs queries to Kafka; a stream/batch job aggregates counts per query per hour and writes to query_counts. Filter out low-frequency and unsafe queries.
2. Trie builder (offline, hourly/daily): reads aggregated counts, builds a trie where every node stores its top-k completions (computed bottom-up by merging children). Serialised and shipped to serving nodes.
3. Serving: nodes hold the trie in memory; sharded by first 1–2 characters with hot-prefix awareness (e.g. 'a…' gets more shards than 'x…'). A request routes to the shard, walks to the prefix node, returns its cached top-k — O(prefix length).
4. Caching: CDN/edge cache and browser cache for short popular prefixes (TTL minutes). Most requests never reach the trie.
5. Personalisation (optional): merge global top-k with the user's recent searches client-side or in a thin layer.

Why precompute top-k: walking a subtree at query time is O(subtree) — too slow; storing top-k per node makes lookup O(L). The cost is rebuild time and memory, paid offline.

Freshness vs cost: hourly rebuilds for trending terms; a small 'trending' overlay merged at serve time gives minute-level freshness for breaking news.

Sharding: naive first-letter sharding is skewed; use a shard map built from prefix frequency so each shard carries similar QPS.

Filtering: profanity/PII filter applied at build time; a blocklist checked at serve time for urgent removals.

• Serving node down: LB routes to replicas of the shard; snapshots reload in minutes.
• Aggregation pipeline delay: serve the last good snapshot; alert if a snapshot is > 2 hours old.
• Bad snapshot (corrupt/offensive): keep the previous snapshot and roll back atomically.
• Edge cache serving stale after a takedown: purge by prefix key; keep TTLs short for sensitive locales.