Search Autocomplete

1. Requirements

Functional:

1. Given a prefix, return top 10 completions in <100 ms.
2. Rank by query frequency with recency decay + trending boost.
3. Personalisation: user's own history up-weighted (with opt-out).
4. Support typos (1-edit tolerance on prefixes ≥ 4 chars) + locale/language segmentation.
5. Filtering: adult/spam suppression list, safe-search modes.

Non-functional:

Out of scope:

• Full search retrieval/ranking (downstream consumer).
• Voice/handwriting input.
• Real-time personal index sync across devices (<1 min is fine).

2. Capacity Estimation

Assumptions: 2B searches/day; ~5 prefix requests per search after debounce (client waits ~100 ms idle); avg suggestion payload 2 KB; peak 2.5× avg.

3. API Design

GET /api/v1/suggest?q=iph&locale=en-US&limit=10&safe=moderate
X-User-Id: 8123            // for personalisation; anonymous allowed

200 OK
{ "prefix": "iph",
  "suggestions": [
    { "text": "iphone 16", "score": 0.98, "source": "trending" },
    { "text": "iphone 16 case", "score": 0.91, "source": "global" },
    { "text": "iphone repair near me", "score": 0.84, "source": "personal" }
  ],
  "took_ms": 12 }

• Debounce client-side (~100–150 ms) + cancel in-flight: cuts ~60% of naive per-keystroke QPS. Say this early — interviewers love it.
• Cache-Control: public, max-age=300 on global layer; personal merges marked private.

4. Data Model & Storage

// Redis hot entry: sug:en:iph
{ "v": 1742,                                   // index version (for cutover)
  "items": [["iphone 16", 98213], ["iphone 16 case", 77120]],
  "updated_at": 1726400000 }
// Cassandra: query_daily_counts ((locale, query_hash), day) -> count, trend_score

• Normalise before keying: lowercase, trim, collapse spaces, strip diacritics — " iPh" and "iph" hit one entry.
• Shard the full index by 2-letter prefix routing: hash(first 2 chars) spreads better than first-char (avoids the giant s/t shards), at the cost of scatter for 1-char queries (fan out to all shards, merge top-K — acceptable, they're few and edge-cached hardest).

5. High-Level Design

Read path: keystroke (debounced) → browser cache → CDN/edge (global, 5 min) → suggest service → Redis hot (hit ~90%) → ES tail on miss → merge personal layer → respond. Write path: logs → Kafka → (a) nightly Spark job: aggregate → rebuild full index + hot snapshot; (b) Flink streaming: top-K deltas for spikes → Redis + ES partial update.

• Edge/CDN: absorbs the most repeated prefixes (global layer); key excludes user-id.
• Suggest service (stateless): normalise → parallel fetch (Redis hot + personal) → merge → filter → respond.
• Hot cache (Redis): 10M prefixes, version-stamped for atomic cutover on rebuild.
• Tail index (ES edge-ngram): long-tail + typo-tolerant path, ~10% of traffic.
• Update pipeline: Spark batch (correctness) + Flink deltas (freshness) — lambda pattern.
• Feedback loop: selections re-enter as weighted counts (position-bias corrected).

6. Deep Dives

6.1 Trie vs precomputed prefix index vs n-grams

Production answer: hot cache of precomputed top-K (covers ~90%) + n-gram index for the tail. The trie lives in interviews and in-device keyboards — say that line, then move on. Shard hot entries by full-prefix hash (uniform); replicate the top-100k prefixes to every suggest host's local LRU to kill cross-rack hops.

6.2 Ranking: frequency + recency + personalisation

Score = w1·log(freq_30d) + w2·trend_spike + w3·personal_affinity − w4·spam_prior, recomputed per locale. Trend spike = count_1h / E[count_1h from 7-day baseline] (z-score-ish); gate on minimum support (≥500/h) so noise can't crown a joke query. Personal layer: last 200 user queries in a profile store, matched by prefix, merged after the global fetch and capped at 3 of 10 slots (diversity guard). Position-bias correction on feedback (a click on rank 8 > rank 1 signal). Weights tuned offline (NDCG on held-out selections), shipped as config — never hard-code.

6.3 Update pipeline: batch correctness + streaming freshness

• Batch (nightly Spark): dedup → normalise → filter (spam/adult/classifier) → aggregate counts → rebuild ES index (blue/green alias swap) → snapshot hot top-10M → bulk-load Redis under new version stamp → flip current_version → old keys expire. Full rebuild bounds drift from the streaming path.
• Streaming (Flink, minute-level): sliding-window counts → detect spike (z > 6, support gate) → push delta docs to ES + patch Redis entries (bump scores, insert trend item at rank ≤3 with source: trending). Deltas carry the batch version; rebuild wipes them — idempotent by (prefix, query, version).
• Thundering-herd guard: version cutover is a single atomic pointer; suggest hosts keep serving old version mid-load; rollback = flip pointer back.

7. Bottlenecks, Trade-offs & Monitoring

First bottleneck at 10x: Redis hot-shard skew on 1–2 char prefixes (a, s, th get disproportionate traffic) → replicate top-100k prefixes into per-host local cache + edge TTL bump for short prefixes. Next: ES tail latency under miss storms → circuit-break to global-only suggestions.

Interview one-liners

• Q: Trie? / A: Only for small corpora — at web scale the root nodes become unshardable hot spots; precompute prefix→top-K and serve O(1) from cache.
• Q: How do trends appear in minutes? / A: Flink spike-detector patches hot entries directly; the nightly batch rebuild keeps it honest.
• Q: Biggest QPS saver? / A: Client debounce + edge caching of the anonymous global layer — most keystrokes never reach origin.

Related

• Cache Patterns and Eviction — hot-prefix + edge layering
• Partitioning — prefix-hash sharding, hot-shard handling
• MongoDB vs Cassandra — counter store choice
• Stream Processing and Kafka vs RabbitMQ — delta pipeline
• Rate Limiter case — throttling expensive tail queries per IP