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?