Module 12 · Lesson 03
Design typeahead / autocomplete
Ten keystrokes, ten queries, and a 100 ms budget. Precompute almost everything.
What you will be able to do
- Choose between a trie, a prefix table and a search engine
- Bound the work per keystroke with precomputed top-k
- Handle updates and trending queries without full rebuilds
- Design the cache and shard keys
Requirements and estimates
- Functional: top 10 suggestions for a prefix, ranked by popularity, filtered for unsafe terms, updated as queries trend.
- Non-functional: p99 under 100 ms, 10k queries/s, works for 10M distinct queries.
- Assumption: users type ~5 characters before choosing, and the client debounces 100-150 ms.
10k qps server-side (after debounce) prefixes: 10M queries x avg 8 chars = ~80M prefix entries store top 10 per prefix: 80M x 10 x ~20 B = ~16 GB -> shardable, cacheable, mostly read-only
Data structures
| Approach | Read cost | Update cost | Verdict |
|---|---|---|---|
| Trie in memory | O(prefix length) walk | Rebuild or heavy mutation | Fast, memory-hungry |
| Prefix table (DB/Redis) | One key lookup | Batch upsert | Default choice |
| Search engine completion suggester | Index query | Reindex segments | Good when already using search |
| Compute on demand | Scan candidates and rank | None | Fails the latency budget |
The prefix table wins on operability: key s:wea maps to ten ranked suggestions. Reads are a single lookup, and updates are batch writes of changed prefixes, which is what a rebuild pipeline produces anyway.
Keeping it fresh
Log queries
Append every search to a stream with a timestamp; no per-keystroke logging, only submitted queries.
Aggregate per window
Hourly job counts queries per prefix and applies a decay so yesterday's hit does not rank forever.
Rebuild top-k
Merge counts with a curated denylist, write the top 10 per prefix, and swap in batches.
Serve trend separately
A small fast pipeline for breaking trends, merged into results with a cap so it cannot dominate.
Personalisation is a multiplier
If suggestions depend on the user's history, the precomputed table is only the candidate set. Rank the ten candidates per user at request time — cheap — instead of precomputing per user.
Read path
Client debounces, cancels stale requests, and sends the prefix plus a session id. The edge caches popular prefixes for a few seconds. The service reads the prefix key from Redis, applies a lightweight per-user rerank, filters blocked terms, and returns. A miss falls back to a database lookup and populates the cache.
Two sentences that cover it
"Suggestions are precomputed top-10 per prefix from hourly aggregates with decay, served from Redis and cached at the edge. Personalisation is a rerank of those ten candidates, not a different index."
Worth remembering
- Serving from a precomputed prefix-to-top-k table turns a ranking problem into a lookup.
- A trie in memory is fast but expensive at huge vocabularies; a prefix table on disk or in Redis is easier to operate.
- Debounce and cancel in-flight requests at the client; the server should not see every keystroke.
- Trending suggestions need a separate, quickly-refreshed pipeline.
Checkpoint
Answer all 3 questions to finish the lesson.
1. Why precompute top-k per prefix instead of ranking at request time?
The latency budget is 100 ms across ten keystrokes. Precomputing moves ranking into a batch job.
2. What prevents the server from processing every keystroke?
Debounce collapses typing into fewer queries, and cancellation stops responses for prefixes the user has moved past.
3. Why apply decay to query counts?
Popularity should reflect recent intent. Without decay, old trends dominate the suggestions indefinitely.