Search Autocomplete

Same startup, same engineer #4. Nineteenth Monday.

Your CTO drops by. "Every product needs autocomplete. URL Shortener search. Instagram hashtags. Ecommerce catalog. Slack channel picker. Time to understand how autocomplete ACTUALLY works — the data structure, the trending logic, the personalization. Ship a design in 12 weeks."

She pauses. "For context — Google autocomplete responds in <50ms at 3M QPS peak from 500M DAU firing every keystroke. Instagram autocompletes hashtags across 2.4B MAU. Every 100ms of latency lost is 1% revenue lost — Google's Amara paper proved it. If you don't understand FST (Finite State Transducer) compression + hot-key handling + trending injection, you'll build slow autocomplete that users abandon."

Here's the paradigm shift:

Distributed Search was scatter-gather across N shards for ranked results. Latency budget is 100-300ms.

Search Autocomplete is fundamentally different:
- Every keystroke fires a request — debouncing helps but doesn't eliminate load. 15 keystrokes per query × 10 queries/user/day = 150 autocomplete requests per user per day.
- Latency budget is 50-100ms end-to-end — including network round-trip. Server budget is <30ms P99. Reference: Nielsen's 100ms perception threshold.
- The data structure is FST, not Trie — Finite State Transducer compresses shared prefixes AND suffixes (like a DAG). 5-10x smaller than Trie. Reference: Lucene FST paper by Michael McCandless.
- Personalization is per-user hot cache — user's recent successful queries are the strongest signal, but must not add latency. Client-side L1 cache is the answer.
- Trending detection is real-time streaming — a news event (earthquake) makes "earthquake tsunami" explode from 0 to 1M QPS in 60 seconds. Corpus rebuild is too slow (nightly). Flink detects trend, injects into serving nodes' L1 cache.

Google's answer (proprietary) uses custom in-memory FST shards. Elasticsearch's answer is the Completion Suggester — Lucene FST-backed, ~5-30ms P99. LinkedIn's answer is Galene — their custom suggestion cache. All three converge on FST as the data structure.

Do NOT say "Google uses Elasticsearch" or "LinkedIn uses Redis" — they use custom in-memory FSTs. This is a common tutorial-parrot mistake.

The real 2024 numbers

• 500M DAU issuing ~10 searches/day, avg 15 keystrokes/query = 75B autocomplete requests/day
• Average QPS: 870K, peak QPS: 3M (typing bursts)
• 50M distinct queries in the corpus, top 10M represent 95% of traffic (Zipfian distribution)
• Trie/FST index ~10 GB in memory (10M queries × ~1 KB metadata) — FST is 5-10x smaller than Trie
• P99 latency budget: 100ms end-to-end, <50ms server-side
• Elasticsearch Completion Suggester: 5-30ms P99 (Elastic docs)
• Custom in-memory FST (Google, LinkedIn): sub-5ms P99
• Nielsen 100ms threshold: below this, users perceive as instantaneous (NN Group)

Interview soundbite: "Autocomplete is 4 primitives: (1) FST (not Trie) in-memory shard sharded by first 2-3 chars, (2) top-K precomputed at each prefix node so runtime lookup is O(1) after FST walk, (3) trending injection via Flink for real-time hot-query boosts, (4) client L1 cache for personalization + Zipf tail. Google does 3M QPS peak at sub-5ms P99. Elasticsearch Completion Suggester is 5-30ms P99. Naming FST + trending injection + 3-floor server derivation signals L6+ preparation."

The whole journey at a glance

Every 10× in QPS surfaces different bottlenecks:

text
    ═══════════ SEARCH AUTOCOMPLETE ACROSS 4 SCALES ═══════════

    L4 (10K QPS)       L5 (100K QPS)      L6 (1M QPS)              L7 (Google 3M QPS peak)
    Trie on 1 node     Elasticsearch      FST shards + trending    Custom in-memory FST
    12 weeks · $500/mo 6 months · $10K/mo 18 months · $500K/mo     ongoing · $10M+/yr

    ┌────────┐         ┌────────┐         ┌── Client apps ─────┐  ┌── Global clients ────┐
    │  App   │         │  App   │         │  debouncing 150ms  │  │  Client L1 cache     │
    │ pods   │         │ pods   │         │  + client L1 cache │  │  (in-process 1ms)    │
    └───┬────┘         └───┬────┘         └─┬──┬──┬──┬─────────┘  └──┬──┬──┬──┬──────────┘
        │                  │                │  │  │  │              │  │  │  │
     ┌──▼───┐           ┌──▼──┐           ┌──▼──▼──▼──▼─────┐    ┌───▼──▼──▼──▼──────────┐
     │Trie  │           │ ES  │           │  Router by      │    │Google/LinkedIn         │
     │ 1    │           │clus │           │  first 2-3 char │    │custom FST shards       │
     │ node │           │Compl│           │  hash → shard   │    │ranked in ms per query  │
     │ 5 GB │           │etion│           └───┬──────┬─────┘    └──┬──┬──┬──┬───────────┘
     │ RAM  │           │Sugg │               │      │              │  │  │  │
     └──┬───┘           └──┬──┘           ┌───▼──────▼───┐        ┌──▼──▼──▼──▼──────────┐
        │                  │              │  FST shards   │       │FST shards            │
        │                  │              │  per prefix   │       │per-prefix sharding    │
        │                  │              │  (sharded by  │       │(sharded first 3 char) │
        │                  │              │  first 3 char)│       │+ top-K precomputed   │
        │              ┌───▼──┐           │  100 nodes    │       │+ trending injection   │
        │              │Redis │           │  c6i.4xlarge  │       └──┬──┬──┬──┬──────────┘
        │              │per-  │           │  30K QPS each │           │  │  │  │
        │              │user  │           └───┬──────────┘         ┌──▼──▼──▼──▼──────────┐
        │              │hot   │           ┌───▼──────────┐         │Ranking pipeline       │
        │              │cache │           │Trending pipe  │         │+ ML rerank            │
        │              └───┬──┘           │Flink real-time│         │+ personalization ML   │
     ┌──▼───┐          ┌───▼─┐            │detect + inject│         │+ multi-region FSTs   │
     │Postgr│          │Postgr│            │hot query boost│         │+ differential priv.  │
     │(quer │          │(quer │            │to serving L1 │         │  on query logs       │
     │y logs│          │y logs│            └───┬──────────┘         └──┬───────────────────┘
     │ trends            │ trends            │                          │
     │)     │          │)     │            │Spark nightly│            │
     │      │          │      │            │FST rebuild  │         ┌──▼──────────────────┐
     │      │          │      │            │+ blue-green │         │Nightly FST rebuild   │
     │      │          │      │            │  swap       │         │+ blue-green swap     │
     └──────┘          └──────┘            └──────────────┘         │+ regional propagation│
                                                                    └──────────────────────┘

    Bottleneck        Bottleneck          Bottleneck                Bottleneck
    Trie fits on      ES Completion       Hot prefix "e" gets       Google 3M QPS peak.
    1 box (5-10 GB).  Sugg maxes ~50K     10x traffic. Trending     Sub-5ms P99. Custom
    Simple.           QPS/node. Need FST  news events explode.      silicon possible.
                      shard for scale.    Client L1 + trending pipe.

   Chapter 5      Chapters 6+6.5      Chapter 7+7.5              Chapter 8
   walks          walks through       walks through trending     walks through Google
   through        Elasticsearch      injection + FST sharding   Amara paper (100ms =
   L4 MVP         Completion Sugg    by first 3 char             1pct revenue) + custom
                                                                  FST + differential priv
                                                                  on query logs

  Key insight: Autocomplete is FST + top-K precompute + trending injection.
  FST beats Trie 5-10x on memory. Elasticsearch Completion Suggester is the L5
  standard (5-30ms). Google + LinkedIn use custom in-memory FST for sub-5ms.
  100 servers at L6 derived from 3-floor: 3M QPS peak / 30K per c6i.4xlarge +
  3 AZs × 34 + 5pct deploy slack. If you name FST + trending + 3-floor derivation
  you're L6+.

The same 4 tiers as clean architecture diagrams

L4 · 10K QPS · Trie on 1 node · $500/mo · 12 weeks:

L5 · 100K QPS · Elasticsearch Completion Suggester · $10K/mo · 6 months:

L6 · 1M QPS · FST shards + trending injection · $500K/mo · 18 months:

L7 · Google 3M QPS peak · custom FST + differential privacy · $10M+/yr:

Why every 10× breaks the architecture

1. FST replaces Trie at L5+. Trie stores each character in a node — 10 GB for 10M queries. FST (Finite State Transducer) shares common prefixes AND suffixes as a directed acyclic graph — 5-10x smaller. Same O(prefix length) lookup. Reference: Lucene FST paper by Michael McCandless.

1. 3-floor server derivation for L6 = 100 nodes. Peak 3M QPS ÷ 30K QPS/c6i.4xlarge = 100 servers (throughput floor). 3 AZs × 34 = 102 (HA floor to survive 1 AZ outage at 66% capacity). 100 × 1.05 = 105 (rolling deploy floor). Max = ~105 nodes. Reference: Elasticsearch Labs shard sizing best practices.

1. Trending injection is the L6+ real-time signal. A news event fires "earthquake tsunami" from 0 to 1M QPS in 60s. Corpus rebuild is nightly (too slow). Solution: Flink detects surge via sliding-window comparison, pushes hot query directly into serving nodes' L1 cache with boosted score. Reference: Flink windowed aggregations docs.

The 3 senior insights before we start Chapter 1

1. FST vs Trie is the L5+ interview probe. Every candidate says "we use a Trie." L5+ candidates explain that FST is 5-10x smaller via suffix-sharing DAG structure — matters at 10M+ queries. Reference: Lucene FST design.

1. Don't say "Google uses Elasticsearch." They use custom in-memory FST for sub-5ms P99. Elasticsearch Completion Suggester is 5-30ms — fine for L5 enterprise, but not Google-scale. This is a common tutorial-parrot mistake. Reference: LinkedIn Galene — proprietary FST-based system.

1. Every 100ms of latency = 1% revenue lost. Amara's 2009 Google research paper proved this. If you don't cite this, you'll miss the "why does this matter?" question. Reference: Amara Google Research paper.

Chapter map for the journey ahead

• Chapter 1 — Requirements (top-K prefix, fuzzy match, i18n, personalization)
• Chapter 2 — Capacity estimation (3M QPS peak, 75B requests/day)
• Chapter 3 — API design (autocomplete GET, feedback POST, corpus refresh)
• Chapter 4 — Data model (query corpus, FST shard, per-user hot cache)
• Chapter 4.5 — FST deep-dive: shared prefix + suffix DAG compression
• Chapter 5 — L4 MVP: Trie on 1 node. Works to 10K QPS
• Chapter 6 — L5: Elasticsearch Completion Suggester. Works to 100K QPS
• Chapter 6.5 — Ranking + Zipf tail: top-K precompute at each prefix node
• Chapter 7 — L6: FST shards + trending injection + 3-floor derivation
• Chapter 7.5 — Trending pipeline: Flink sliding window + hot-key inject
• Chapter 8 — L7: Google-scale custom FST + differential privacy on query logs
• Chapter 9 — Failure modes: trending storm, corpus rebuild fail, personalization leak
• Chapter 10 — Trade-off matrix (FST vs Trie vs inverted index)
• Chapter 11 — Interview masterclass: 45-min mock, questions to ask
• Chapter 12 — Defense: the 20 hardest interview questions on autocomplete

Ready? Chapter 1 next: what did the CTO actually ask for?

The CTO's one sentence ('we need autocomplete that scales') is 95% ambiguity. Autocomplete is deceptively simple — you type, suggestions appear. Under the hood, sub-20ms p99 is DECISIVE and forces every architectural decision downstream.

Functional requirements

FR-1: Top-K prefix completion. User types 'ma' → return top-10 completions ranked by (frequency × recency × click-through-rate). This is the baseline case. 80% of query volume. Latency budget: <10ms server-side.

FR-2: Typo tolerance (fuzzy match). User types 'iphon' → suggest 'iphone', 'iphones'. User types 'macbok' → suggest 'macbook'. Fuzzy match adds edit-distance-1 or edit-distance-2 candidates. Elasticsearch supports fuzzy=AUTO. Cost: 30-50% latency spike. Enable only after user pauses typing (200ms of no keystroke).

FR-3: Trending injection. User types 'ea' → the top result yesterday was 'earbuds', but today's news says 'earthquake tsunami' — trending overlay must inject this within 20-60s of the eruption. Cannot wait for nightly rebuild. Requires real-time pipeline (Flink 60s sliding window).

FR-4: Personalization. Alice types 'ma' → she just watched 'The Matrix' → suggest 'the matrix' at position 1. DEFER TO L7. Personalization at L6 blows the sub-10ms budget when merged with baseline + trending at query time.

FR-5: Localization. User types 'sus' in ja-JP locale → suggest 寿司 (sushi), 数学 (math). Per-locale FST index. Auto-detect user locale + fallback to en-US.

FR-6: Content safety. User types 'how to make a b' → do NOT suggest 'how to make a bomb'. Bloom filter of ~500K-2M banned terms + per-locale policy list. Reject or downrank at query time.

Non-functional requirements

NFR-1: Latency p99 (the DECISIVE constraint). Autocomplete latency budget is 20ms end-to-end (browser → suggestion visible). Server-side budget is 10ms (leaving 10ms for network + client render). Amara paper (Google 2009): every 100ms of latency = 1% revenue lost. At $500M ARR, 10ms saved = $5M/yr recurring. This is the killer citation for the ROI conversation.

NFR-2: Throughput. 300K QPS baseline, 800K QPS peak (planned), 2M+ QPS spike during viral events. Every keystroke potentially fires a request (mitigated by 300ms client debounce → ~3-5 requests per query typed).

NFR-3: Availability. 99.99% (search box is user-facing). Graceful degradation on failure: return empty suggestions list (search box still works, user just doesn't get autocomplete). Never return errors — silent degradation is better UX than error toasts.

NFR-4: Corpus freshness. Baseline: nightly rebuild (2-4h Spark job). Trending: <30-60s from event to visible. Personalization (L7): real-time per user (within seconds of their action).

NFR-5: Cost bound. $15K/mo compute at 500K QPS is achievable with custom FST. Algolia at same scale is $300-600K/mo. Cost math is 25-50x differentiated by architecture choice.

NFR-6: Privacy. Trending signal MUST NOT leak individual user identity. Differential privacy (Laplace noise, ε=1.0) is the industry-standard protection. Apple's QuickType uses this; Google's Chrome autocomplete uses similar.

Why FST not Trie

This is the L6+ insight that separates 'built autocomplete' from 'understood autocomplete':

• Trie: each character is a node with pointers to children. 'apple' + 'application' share prefix 'app' (5 nodes) but diverge — 'apple' has 2 more nodes, 'application' has 8 more. Total: 5 + 2 + 8 = 15 nodes.
• FST (Finite State Transducer): shares prefix AND suffix state. 'apple' + 'application' share prefix 'app'; if both end in '-tion' patterns or common terminal states, those are shared too. For 500M queries corpus, FST is 5-10x smaller than Trie in memory.
• Lucene has FST built-in — Elasticsearch Completion Suggester wraps it. Custom in-process FST service (L6) is Lucene's FST loaded via mmap into a Go/Java service that skips the ES query overhead (JSON serialization, coord round-trip, master state). Saves 5-10ms per query.

Reference: Lucene FST implementation. Read this before an L6 interview.

Shard sizing math

At L6 with in-process FST:

```
corpus = 500M queries × 60 bytes avg = 30 GB raw
FST compressed = 30 GB / 8x = ~4 GB
Per-node FST = 500 MB (target — fits in RAM easily on r6i.4xlarge)
num_shards = 4 GB / 500 MB = 8 primary shards
RF=1 (autocomplete degrades to empty on failure — don't waste memory on replicas)
Total nodes = 8 shards (or 16 for extra headroom on CPU)
```

Prefix-hash sharding: hash(prefix[0:2]) mod num_shards. Guarantees same prefix always lands on same shard — enables in-memory FST optimization. Round-robin sharding would kill this.