System 12.31 — Typeahead / Search Autocomplete
In one line
Suggest the top completions for every keystroke in under 100 ms: a read-heavy, latency-critical system built on precomputed prefix → top-K lists, fed by an offline aggregation of search logs.
Think of it like this
A librarian who, as you say 'Harry P…', instantly offers the three most-requested titles starting with those letters. She doesn't search the catalogue each time; she keeps a little card per prefix with the popular answers already written down.
Key ideas
- 01
Requirements: top 5–10 suggestions per prefix, ranked by popularity (and freshness, personalisation, language); p99 < 100 ms including network; ~10 keystrokes per search × billions of searches/day → hundreds of thousands of QPS. Freshness within minutes to hours is fine.
- 02
Data structure: a TRIE where each node stores the TOP-K completions for its prefix (precomputed), so a lookup is O(length of prefix), not a subtree walk. At scale, flatten it into a key-value store:
prefix → [top-10 terms]in Redis/a KV store, which is simpler to shard and cache. - 03
Build pipeline: search logs → Kafka → aggregate term counts (stream job for trending, batch job for long-term popularity with time decay) → rebuild prefix → top-K tables → publish a new version atomically (blue/green table swap). The online path only reads.
- 04
Serving: client DEBOUNCES keystrokes (~100–150 ms) and caches recent prefixes; CDN/edge caches for very popular short prefixes; the service reads prefix tables sharded by prefix (watch for hot shards on 1–2 letter prefixes: replicate those or keep them in every node's memory). Filter offensive terms and apply personalisation as a light re-rank on top.
Code & diagrams
Explain without notes
Why precompute top-K per prefix instead of searching the trie subtree on each request?
Practice
Estimate storage: 100 M distinct queries, average 20 chars, top-10 per prefix.
Trade-offs
- ↔
Freshness vs cost: rebuilding tables often keeps trends current but costs compute; blend a fast trending layer with a slower popularity layer.
Run it in production
You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:
Completion checklist
I can present typeahead with the offline build and online lookup paths
I can handle hot short prefixes