Skip to main content
Back to Search Autocomplete
MASTERCLASS
Gold-standard deep dive

Search Autocomplete — Masterclass

Three additional artifacts a Staff/Principal candidate should be able to produce for this problem: an Architecture Decision Record, a business-driven design exercise, and a production incident scenario.

1. Architecture Decision Record

The format working architects use to document a decision so future teams understand context, options, and reversal conditions.

ADR 001
Architecture Decision Record

In-process mmap FST shards + prefix-hash sharding + Flink 60s-window trending injection + CDN edge caching for top-1000 prefixes + client-side debouncing + 3-floor server derivation (ingress/query/rebuild) — over Elasticsearch Completion Suggester (L5 pattern), custom Trie, managed Algolia Places, or Google Cloud Autocomplete API.

Context
We are building autocomplete for a multi-tenant B2C marketplace at 300K-800K QPS peak (search box hits every keystroke). Corpus: 500M distinct historical queries growing 5%/month. Latency budget: <20ms p99 end-to-end (browser debounces at 300ms so we get ~3-5 requests per query typed). Reference: Google 3M QPS at sub-5ms p99, Amazon 500K QPS at sub-30ms, Airbnb 200K QPS at sub-15ms. Query mix: 80% baseline top-K from corpus, 15% typo-tolerance (fuzzy match), 5% trending events (news spikes). Team: 4 engineers, 1 with prior Lucene/FST experience. Amara Google 2009 research: every 100ms of latency = 1% revenue lost.
Constraints
  • 300K-800K QPS peak (baseline 150K)
  • 500M distinct query corpus; ~50-100 bytes avg per query
  • p99 latency: <20ms end-to-end (browser → suggestion visible)
  • p99 latency: <10ms server-side (leaves 10ms for network + client render)
  • Trending: 'celebrity death' or 'earthquake tsunami' must surface within 30-60s of viral spike
  • Corpus freshness: nightly rebuild is fine for baseline; trending overlay for real-time
  • Availability: 99.99% (search box is user-facing; degrade to 'no suggestions' on failure, not error)
  • Cost bound: $15K/mo compute at scale (autocomplete is high-QPS but low-per-query cost)
  • Team: 4 engineers, 1 with FST/Lucene experience — critical constraint
  • Privacy: sensitive queries (medical, legal, financial) MUST NOT leak to trending
Options considered

Custom in-process FST + Flink trending + CDN edge (chosen)

Pros
  • Sub-3ms server-side p99 (in-mem FST walk is 1-2ms; trending merge adds 1ms)
  • 5-10x memory efficient vs Trie (FST shares suffix state via finite-state automaton)
  • Flink 60s window catches viral events in 20-30s
  • CDN edge caches top-1000 prefixes for 15s (60-80% QPS bypass origin)
  • 3-floor server derivation isolates blast radius (ingress DDOS ≠ query kill ≠ rebuild kill)
  • Client debouncing kills 60-70% of load with no UX impact
  • Cost ~$12K/mo compute at 500K QPS — well under budget
Cons
  • 3-6 months of custom FST-service engineering before first production traffic
  • Requires 1 engineer with Lucene/FST expertise — scarce hire
  • FST rebuild is 2-4 hours for 500M queries; must be nightly batch not real-time
  • Trending overlay requires Flink infrastructure (Kafka + Flink + Redis)
Cost: ~$12K/mo compute (40 nodes for query, 6 for Flink, 4 for rebuild) + 1.5 engineers ($300K/yr fully loaded)

Elasticsearch Completion Suggester (L5 pattern extended)

Pros
  • Uses Lucene FST internally — same underlying data structure
  • 5-30ms p99 (works fine for <200K QPS; degrades at higher scale)
  • Standard ES ops, no custom FST service to build
  • Built-in fuzzy match, snapshot backup, monitoring via Kibana
Cons
  • 5-30ms p99 is AT OR ABOVE our 20ms budget — no margin
  • Coord + master + JSON serialization overhead adds 5-10ms baseline
  • Cannot use edge PoPs — all queries hit central cluster
  • Adding trending overlay requires custom code anyway
Cost: ~$18K/mo compute (25-node ES cluster) — 50% higher than custom FST for worse latency

Managed Algolia Places / Search

Pros
  • Sub-10ms p99 globally (Algolia has world-class autocomplete)
  • Zero ops burden
  • Excellent DX with instant-search UI kits
Cons
  • Cost: $1.50 per 1000 operations × 800K QPS peak × 86400s × 30d = $3.1M/mo at list; $300-600K/mo at enterprise discount
  • Cost trajectory scales LINEARLY with QPS — becomes prohibitive at growth
  • No custom analyzers, no custom ranking, no trending injection API
  • Vendor lock-in on ranking → we can't tune 'why does query X rank above query Y?'
Cost: $300-600K/mo at our scale — 25-50x more than self-hosted

Google Cloud Autocomplete API

Pros
  • Google's own autocomplete infrastructure — best-in-class
  • Multi-language + world knowledge built-in
  • Sub-5ms p99 globally
Cons
  • Cost: $0.75-$1.50 per 1000 requests × 800K QPS = $1.5-$3M/mo at list
  • Corpus is GOOGLE'S corpus (web search), not OUR corpus (marketplace queries)
  • Cannot inject our own queries into ranking — 'macbook m3' will suggest Google's top-K, not what OUR users searched for
  • Data-residency: queries leave our infrastructure to Google
Cost: $1.5-3M/mo + Google gets our query stream (competitive intelligence concern)

Redis sorted set per prefix (L4 pattern extended)

Pros
  • Simplest possible architecture — SET/GET per prefix
  • Sub-2ms p99 in-Redis latency
  • Team already knows Redis
Cons
  • 5-10x memory footprint vs FST (no shared-suffix compression)
  • No fuzzy match without prefix expansion (which is expensive)
  • Nightly rebuild only — no trending injection
  • Doesn't scale past ~200K QPS on single Redis instance; Redis Cluster adds coordination overhead
Cost: ~$6K/mo compute but memory-hungry at 500M queries — 3-4 r6i.4xlarge Redis nodes
Chosen solution

Custom in-process FST + Flink trending + CDN edge + client debounce + 3-floor derivation

Why
Sub-20ms p99 is the DECISIVE constraint. Only in-process FST hits it. Elasticsearch Completion Suggester is AT OR ABOVE budget with no margin. Algolia and Google Cloud are 25-50x more expensive at our QPS. Redis sorted sets don't scale past 200K QPS. The custom-FST path requires 3-6 months of engineering and 1 Lucene-expert hire, but delivers sub-3ms server-side p99, 5-10x memory efficiency, and full control over trending injection + ranking. Amara's paper (100ms latency = 1% revenue) makes the cost math easy: at $500M annual revenue, 10ms of latency saved = $5M/yr revenue — pays for 15 engineers.
Rejected alternatives (with reasons)
  • Elasticsearch Completion Suggester — 5-30ms p99 too close to budget, no edge deployment
  • Algolia — $300-600K/mo linear scaling with QPS is prohibitive
  • Google Cloud Autocomplete — uses Google's corpus not ours, competitive intelligence leak
  • Redis sorted sets — 5-10x memory waste, no trending injection, doesn't scale past 200K QPS
Trade-offs accepted
  • Accept 3-6 months of upfront custom FST service engineering
  • Accept 1 senior engineer with FST/Lucene expertise as a critical hire dependency
  • Accept nightly baseline rebuild (2-4h) — no real-time corpus updates outside trending overlay
  • Accept Flink operational burden — Kafka + Flink + trending Redis is 3 new operational surfaces
  • Accept custom ranking model that requires ML team to tune — no plug-and-play
Consequences
  • Sub-3ms server-side p99 → sub-20ms end-to-end with browser render
  • 5-10x memory efficiency vs Trie → 500M queries fit in 40 nodes not 200
  • Trending events visible within 20-30s of viral eruption
  • 60-80% of QPS bypasses origin via CDN edge cache
  • Ranking becomes tunable via internal ML team — competitive advantage
  • Autocomplete becomes a first-class internal service that other products can consume
When would we reverse this decision?
  • If FST-expert engineer leaves and no replacement hire → migrate to managed Elasticsearch
  • If corpus shrinks below 50M queries → Redis sorted sets become viable (simpler)
  • If QPS drops sustainably below 100K → Algolia enterprise deal becomes cost-competitive
  • If we open a market in a language whose FST support is poor → dedicated per-locale infrastructure

2. Business constraint exercise

Given real-world constraints (team size, budget, deadline), what architecture do you propose — and how do you push back when leadership asks for the wrong thing? This teaches engineering judgment.

Business constraint exercise

You are engineer #4 at a 4-year-old marketplace startup. CTO messages you Monday: 'Autocomplete is broken. Suggestions take 200-500ms to appear; users type past them. We built it 3 years ago on Elasticsearch main index (not the completion suggester). I want it FIXED in 8 weeks. Two options: (1) rewrite on Elasticsearch Completion Suggester (2 weeks, easy) or (2) hire a Lucene expert and build custom in-process FST (6 months, sub-3ms p99). CTO wants option 1. Board wants a 'best-in-class autocomplete' for the Series C pitch in 12 weeks. Which do we pick and how do you defend it?'

Constraints
  • 18-week deadline from CTO; 12-week board target for Series C pitch
  • 2Current autocomplete: 200-500ms latency (broken — using ES main index instead of completion suggester)
  • 3300K QPS peak, growing to 800K QPS in 18 months
  • 4150M distinct query corpus; ~30% typos or misspellings
  • 53 backend engineers on search team; NONE have FST/Lucene expertise
  • 6$500K annual budget approved for search + autocomplete rebuild
  • 7Existing infra: 12-node Elasticsearch cluster (main index) already running
  • 8CTO preference: rewrite on ES Completion Suggester (2-week sprint)
  • 9Board target: 'best-in-class' autocomplete for competitive differentiation
Your question

What do you recommend? Address: (a) whether ES Completion Suggester meets the 'best-in-class' bar for Series C pitch, (b) whether the 6-month custom-FST timeline fits the 12-week board window, (c) how to sequence a strategy that ships in 8 weeks AND positions us for 'best-in-class' by year-2, and (d) what's the real cost math including Amara-paper revenue impact.

3. Production incident scenario

You are on-call at 3:47am. p99 has spiked. Walk through the investigation, hypothesis, mitigation, and postmortem. This teaches real production reasoning — not just design.

INCIDENT
Trending storm cascade — celebrity death query spikes 4000x baseline in 90 seconds

PagerDuty alert at 8:42am ET. Major celebrity's death breaks on Twitter. Autocomplete QPS for prefix 'jo' jumps from ~500/s to ~2M/s in 90 seconds. Trending Redis is at 100% CPU, evicting entries. FST query nodes are at 95% CPU. p99 latency spiking from 8ms to 340ms. Marketing texting on-call: 'suggestions are stale — showing yesterday's celebs, not the news everyone is searching.'

Metrics
  • autocomplete.qps: 2.1M (baseline 300K — 7x overall)
  • autocomplete.qps.by_prefix.jo: 2M (baseline 500 — 4000x this prefix)
  • autocomplete.qps.by_prefix.j: 1.8M (baseline 8K — 225x this prefix)
  • trending.redis.cpu_percent: 100% (saturated)
  • trending.redis.evicted_keys_per_sec: 45K (was 0 baseline)
  • trending.redis.hit_rate: 32% (was 98% baseline)
  • fst.query_nodes.cpu_percent: 95% (was 40%)
  • autocomplete.p99_latency_ms: 340 (baseline 8)
  • autocomplete.p99_latency_ms.by_prefix.jo: 620 (celebrity-name prefix worst)
  • cdn.edge.hit_rate: 12% (was 78% — CDN can't cache trending-hot prefix efficiently)
  • flink.trending_pipeline.watermark_lag_seconds: 180 (was <10 — pipeline falling behind)
  • elb.5xx_rate: 2.1% (was 0.01% baseline)
Logs
  • 08:42:03 flink log: 'sliding window compute lag detected — watermark 45s behind wall clock'
  • 08:42:15 trending redis log: 'MAXMEMORY-POLICY allkeys-lru evictions starting'
  • 08:43:00 fst-query-node-7 log: 'walkTrie(prefix=jo) latency 34ms (baseline 1.2ms) — thread contention'
  • 08:43:22 flink log: 'trending detection for prefix=jo: 4000x baseline — publishing to trending redis'
  • 08:43:24 trending redis log: 'SET trending:jo EX 60 → OK (delayed 84s from event)'
  • 08:43:45 alert channel: 'watchdog fires: autocomplete_p99 > 100ms for 3 consecutive minutes'
  • 08:45:12 cdn edge log: 'cache-miss rate spike for prefix=j* → origin bypass',
  • 08:47:00 (self-healing attempt) fst-node-3 log: 'auto-scale up: adding 8 nodes to query pool'
  • 08:52:00 flink log: 'watermark caught up — pipeline back to <10s lag'
  • 09:05:00 metrics: 'autocomplete.p99 back to 12ms; trending suggestions live for prefix=jo'
Dependency health
  • Baseline FST shards (40 nodes): DEGRADED — 95% CPU, tail latency spiking
  • Trending Redis: SATURATED — 100% CPU, evicting entries under memory pressure
  • Flink trending pipeline: LAGGING — watermark 180s behind wall clock
  • CDN edge (Cloudflare): DEGRADED — hit rate 12% (was 78%)
  • Kafka query-events topic: HEALTHY (producer side fine)
  • Baseline corpus rebuild (Spark): NOT INVOLVED (last rebuild 6 hours ago, next in 18h)
Your investigation
1

It's 8:44am. Traffic is at 7x baseline overall and 4000x on prefix 'jo'. What's the ONE metric that tells you 'is this a real celebrity spike vs a bot / DDoS'?

Hint: Legitimate traffic and DDoS look similar at the LB. The signature diverges in the queries themselves.
2

You've confirmed it's a real celebrity news spike. Give your top 3 hypotheses for WHY latency spiked, ranked by likelihood given the metrics.

Hint: The trending Redis is saturated, the Flink pipeline is 180s behind, and the CDN edge hit rate collapsed. Which of these is the root cause vs a downstream symptom?
3

Design a 60-second mitigation. Constraint: latency must return to <30ms p99 within 5 minutes. What's your action?

Hint: You can dynamically change TTLs, scale nodes, or reroute traffic. What's the highest-impact single action?
4

Postmortem the next day. Name 3 action items ranked by impact, with 'expected reduction in trending storm impact' quantified.

Hint: Some are technical, some are architectural. Prioritize by risk-adjusted impact.
5

Draft the customer-facing status page update at T+20 minutes (after latency recovers but before all trending updates are live).

Hint: Users saw slow autocomplete for 20 minutes. Marketing is worried about brand perception during a moment of high visibility.
Knowledge graph

Learn these first

  • FST (Finite State Transducer) — shares prefix AND suffix state, 5-10x smaller than Trie
  • Amara Google 2009 paper: 100ms latency = 1% revenue lost
  • Flink sliding-window trending detection (60s window / 10s slide)
  • Differential privacy (Laplace noise, ε=1.0) for trending signal protection

Where this appears in the curriculum

This is the Gold Standard.

Every other system will eventually have a masterclass tab like this one. The pattern proven here — ADR + business exercise + incident scenario — scales to all 50+ problems on the platform.