Typeahead / search autocomplete

1 · Clarifying questions

2 · Capacity math

Two numbers dominate. 400k QPS — every dropdown is a server hit (can't cache user-specific results easily). And 85% edge cacheability — short prefixes are repeated billions of times across users.

3 · The index — what actually stores the completions

Three approaches, in increasing sophistication:

Option A — Naive trie with per-node top-k

Build a prefix trie of all queries. At each node store the top 10 completions that pass through this prefix, pre-computed. A lookup is O(prefix_length) — descend the trie, return the top-k stored at the deepest node reached.

Trie node (conceptual, Go):
    type node struct {
        children map[byte]*node    // or [26]*node for ASCII letters
        topK     []completion       // (text, score) tuples, sorted
    }

Lookup("fac"):
    walk: root -> 'f' -> 'a' -> 'c'
    return node['f']['a']['c'].topK
Time: O(prefix_len)

Pro: dead simple, blindingly fast reads. Con: writes are expensive — when a completion's score changes, you have to update every node on its path. Bulk rebuild (every hour or day) is the only sane way to maintain it.

Option B — DAWG / FST (compressed trie)

A directed acyclic word graph compresses common suffixes, cutting memory ~10×. Lucene's Finite State Transducer is the canonical implementation; suggesters like Elasticsearch's "completion suggester" use this. Read latency is the same; build time is slower; memory is dramatically smaller — important when you want to fit a 500M-string index in RAM.

Option C — Key-value lookup (the "boring" choice)

Store completions in a sorted KV (e.g. RocksDB) keyed by the prefix. Per prefix, the value is the precomputed top-10 list. GET "fac" returns the list. No trie traversal — the storage layer does it for you. This is what most production systems actually run, because operationally it's just another KV cluster.

4 · The offline pipeline — where the rankings come from

The interesting part of typeahead is the offline pipeline that turns "raw query logs" into "top-10 completions per prefix". Three stages:

Stage 1 — Aggregate

Stream query events from a Kafka topic into a windowed aggregator (Flink / Spark Streaming / Beam). For each unique normalised query string, accumulate counts by window: last hour, last day, last week. Output: (normalised_query, count_h, count_d, count_w).

Normalisation matters: lowercase, strip punctuation, collapse whitespace, expand emoji to text. Two queries differing only in case are the same query.

Stage 2 — Score

Combine counts with other signals to produce a single score per query:

Stage 3 — Build the per-prefix top-K

For every query in the scored list and every prefix of that query, push into a min-heap of size K (10) keyed on the score. After processing all queries, the heap at each prefix is the top-K completions for that prefix.

For ~10M queries × avg length 20 prefixes each = 200M heap operations. Embarrassingly parallel by first-character (shard the work into 26 buckets); a few hundred mappers finish it in 30–60 minutes.

Stage 4 — Serve

Atomically swap the new index. Two common patterns:

• Versioned key prefix. Index v={timestamp}/fac coexists with v={old}/fac. A pointer key indicates which version is "active". Atomically flip the pointer; the new index serves all reads from the next request.
• Side-load + restart. Each typeahead server holds the index in RAM. Build the new index in a parallel directory; signal servers to re-mmap; old index drops out. Coordinated rollout to avoid all servers reloading at once.

5 · High-level architecture

The online path is short and synchronous: edge cache → typeahead service → personalise → user. The offline pipeline is the heavy lifting and runs every ~15 minutes. The personalisation sidecar is an optional re-ranking layer that reads from a user-history service.

6 · Deep dive — edge caching

85% of all requests are for the top 1000 prefixes. Caching them at edge (CDN-style POPs) drops origin load by 10× and shaves 30–50 ms off the P99.

7 · Personalisation — the optional ML layer

Global top-10 is fine for most users. Personalisation matters for two cases: recent searches (boost queries the user typed in the last week) and interest signal (a user who clicks football news a lot gets "fifa world cup" before "fall season").

The cleanest design: typeahead service returns the global top-30 for the prefix; a re-ranking service applies the personalisation signals and trims to top-10. Re-ranking runs on every uncached miss with a budget of ~5 ms.

8 · Safety & abuse

• Blocklists. A hand-curated set of strings that must never appear (legal threats, doxxing, child-safety). Multiplicative filter at score time — if the query matches a blocklist regex, score becomes zero.
• Classifier. A small ML model that scores each candidate for safety (profanity, harassment patterns). Threshold-gated; below threshold, drop.
• Trending abuse. Real-time pipeline that monitors sudden spikes in low-quality queries (coordinated trolling). Auto-block via a fast feedback loop into the safety service.
• Hand removal. Trust & safety has a button: "remove this suggestion globally". Logged, audited, reversible.
• Personal-name filter. Don't suggest "{person's name} address" or "{person's name} salary" unless the person is a public figure (notability threshold from external knowledge graph).

9 · Failure modes

10 · Cost & operability

The CDN egress bill dominates. Reduce it with shorter responses (just the top-5, not top-30); compress with Brotli; deduplicate the JSON envelope.

11 · Trade-offs & what would change at 10×

Further reading

• Elasticsearch — "Completion Suggester". Production reference for FST-based typeahead. The official guide is small and worth reading once.
• Apache Lucene — Robert Muir, "FSTs in Lucene". The data-structure background for FST/DAWG-based suggesters.
• Google — "How Google Search builds suggestions". A surprisingly candid 2017 SRE blog post on the offline pipeline architecture.
• Bing autosuggest team — "Building autosuggest at scale". Discusses the rank-by-CTR feedback loop and safety filtering.
• LinkedIn — "Building typeahead with three sources". Engineering-blog post on combining global + connection-graph + personal sources.
• Adjacent: LSM trees. The storage engine under most KV-style suggester indexes.
• Adjacent: Trie data structure. The mechanism explainer.
• Adjacent: Top-k / trending. The pipeline shape reuses many ideas.