Design Search Autocomplete
Answers in a few milliseconds come from top-k completions precomputed per prefix, not from running a search on every keystroke.
ZRANGE sg:<prefix> 0 9 REV // same result as the older ZREVRANGE sg:<prefix> 0 9; REV added in Redis 6.2Autocomplete looks like search and is not. Search runs once per submitted query and may take 200 ms; autocomplete runs on every keystroke, has to answer within the gap between two of them, and returns ten rows that millions of people request identically. That shape — read-dominated, prefix-keyed, top-k, heavily skewed — is why the whole design is precomputation.
Prefix structures
The textbook answer is a trie with the top k completions cached at every node, so answering a prefix is a walk plus a read rather than a traversal of the subtree below it. In production this is usually a finite state transducer: the Elasticsearch completion field type builds one and keeps it on the heap, which is both why it is fast and why it is memory-bound. The flat alternative is one key per prefix in Redis holding a sorted set of candidates scored by popularity — no tree, no traversal, one command per request.
Ranking and freshness
Score comes from the query log, not the corpus: how often a completion was chosen, decayed over time so last month's story stops leading. A batch job aggregates the log and rewrites the prefix keys; a streaming path nudges scores between rebuilds with ZINCRBY. Serving is then a bounded range read.
What trips people up
Traffic is Zipfian — a few thousand short prefixes cover most of it — so cache those at the edge with a short TTL and the origin barely sees load. Personalisation destroys that, so apply it as a re-rank of the cached list rather than a per-user query. And anything you index will be suggested: the blocklist runs at build time, not at read time.
Example
// Build and serve top-10 completions per prefix in Redis. All the ranking work
// happens in the nightly build; the read path is one command.
import { createClient } from 'redis';
const redis = createClient({ url: process.env.REDIS_URL });
await redis.connect();
const TOP_K = 10;
const MAX_PREFIX = 20; // past this, hand off to the real search index
// rows comes from an aggregate over yesterday's query log:
// [{ phrase: 'noise cancelling headphones', hits: 41_207, lastSeenDays: 0 }, ...]
export async function buildPrefixIndex(rows) {
for (const { phrase, hits, lastSeenDays } of rows) {
// 30-day half-life: a phrase people stopped choosing stops ranking, without
// anyone having to delete it.
const score = hits * Math.pow(0.5, lastSeenDays / 30);
// MULTI batches the round trips for one phrase into a single reply.
const tx = redis.multi();
for (let i = 1; i <= Math.min(phrase.length, MAX_PREFIX); i++) {
const key = `sg:${phrase.slice(0, i)}`;
tx.zAdd(key, { score, value: phrase });
// Trim to the top K by rank. Without this, 'a' accumulates the whole
// corpus and the memory bill is O(corpus x prefix length).
tx.zRemRangeByRank(key, 0, -(TOP_K + 1));
tx.expire(key, 60 * 60 * 36); // rebuilt daily; 36h survives a late run
}
await tx.exec();
}
}
export async function suggest(rawPrefix) {
const prefix = rawPrefix.trim().toLowerCase().slice(0, MAX_PREFIX);
if (prefix.length < 2) return []; // 1-char prefixes are noise and pure cost
// REV is Redis 6.2 and later. On an older server the longhand is a separate
// command, ZREVRANGE sg:<prefix> 0 9, with identical results.
return redis.zRange(`sg:${prefix}`, 0, TOP_K - 1, { REV: true });
}
// Between rebuilds, a chosen suggestion nudges its own score so a term that
// starts trending at 09:00 does not wait for tonight's batch.
export async function recordSelection(phrase) {
const tx = redis.multi();
for (let i = 1; i <= Math.min(phrase.length, MAX_PREFIX); i++) {
tx.zIncrBy(`sg:${phrase.slice(0, i)}`, 1, phrase);
}
await tx.exec();
}When to use it
- Returning suggestions under a search box within the time between two keystrokes.
- Ranking suggestions by what people actually clicked rather than by corpus frequency.
- Getting a newly launched product or a trending term into suggestions within minutes.
- Cutting autocomplete request volume by an order of magnitude without touching the backend.
More examples
The Elasticsearch completion suggester
Shows the managed version of the same idea: multiple inputs map to one suggestion, weight is the precomputed popularity, and fuzziness buys typo tolerance for real CPU. Reach for it when you already run Elasticsearch and the suggestion set fits comfortably in heap. Prefer the Redis layout instead when the set is large, when you want suggestions updated continuously, or when you need the prefix keys cached at the edge.
// Mapping. The completion type builds an FST at index time and holds it on the
// JVM heap, which is where both the speed and the memory ceiling come from.
PUT /suggestions
{
"mappings": {
"properties": {
"suggest": {
"type": "completion",
"analyzer": "simple", // the default for this type
"preserve_separators": true, // false would match "foof" to "Foo Fighters"
"preserve_position_increments": true, // false lets "b" match "The Beatles"
"max_input_length": 50 // default, in UTF-16 code points
}
}
}
}
// A document carries its own weight, so ranking is decided at index time by the
// build job rather than at query time by a scoring function.
POST /suggestions/_doc
{
"suggest": {
"input": ["noise cancelling headphones", "headphones noise cancelling"],
"weight": 41207
}
}
// Query. _source: false because only the suggestion text is wanted.
POST /suggestions/_search
{
"_source": false,
"suggest": {
"completions": {
"prefix": "noise can",
"completion": {
"field": "suggest",
"size": 10,
"skip_duplicates": true, // costs more; dedupes across shards
"fuzzy": { "fuzziness": 1 } // one edit, so "noize can" still matches
}
}
}
}Why the top-k is cached at every trie node
Worth reading once even if you never ship it, because it explains the cost model behind every production option: precomputing top-k per node trades memory for a read that does no work. Reach for an in-process structure like this when the suggestion set is small and fixed (country names, ticker symbols, an internal admin tool) and a network hop would dominate the latency budget.
// The structure that makes the Redis layout above make sense. Each node keeps
// the best completions in its own subtree, so answering never walks downward.
class SuggestTrie {
constructor(k = 10) {
this.k = k;
this.root = { children: new Map(), top: [] }; // top: [{ phrase, score }]
}
// Build-time only. Insert walks the prefix once and merges the phrase into
// each node's top-k on the way down - O(prefix length x k), not O(subtree).
insert(phrase, score) {
let node = this.root;
this._merge(node, phrase, score);
for (const ch of phrase) {
if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), top: [] });
node = node.children.get(ch);
this._merge(node, phrase, score);
}
}
_merge(node, phrase, score) {
node.top.push({ phrase, score });
node.top.sort((a, b) => b.score - a.score);
if (node.top.length > this.k) node.top.length = this.k; // bounded memory
}
// Read-time: walk the prefix, return the cached list. No subtree traversal,
// no sorting, no scoring. This is the property the design is bought with.
suggest(prefix) {
let node = this.root;
for (const ch of prefix) {
node = node.children.get(ch);
if (!node) return [];
}
return node.top.map((e) => e.phrase);
}
}
// Without the cached lists, 'ne' would mean visiting every descendant and
// sorting - milliseconds per request becomes tens of milliseconds, on the
// shortest and most popular prefixes.Edge caching and client debouncing
Half the capacity planning for autocomplete lives in these two snippets. Reach for them before scaling the backend: debouncing cuts request volume several-fold, and because short prefixes are both the most requested and the most expensive to answer, a 60-second shared cache absorbs most of what remains. The Vary header is the trap — adding Cookie there gives every user a private cache entry and the hit rate collapses.
// Origin side. Suggestions for a given prefix are the same for everyone, which
// makes them perfectly cacheable - the single biggest lever on this service.
app.get('/api/suggest', async (req, res) => {
const prefix = String(req.query.q ?? '');
const results = await suggest(prefix);
// s-maxage is the shared-cache TTL (CDN); max-age=0 keeps browsers honest so
// a fix propagates. stale-while-revalidate means a rebuild never stalls a
// request - the CDN serves the old list and refreshes behind it.
res.set('Cache-Control', 'public, max-age=0, s-maxage=60, stale-while-revalidate=300');
res.set('Vary', 'Accept-Language'); // NOT Cookie: that would fragment the cache
res.json({ prefix, results });
});
// Client side. One request per keystroke turns "headphones" into ten requests.
// Debouncing plus cancellation is what keeps measured QPS near the sized QPS.
let timer;
let inFlight;
function onInput(value) {
clearTimeout(timer);
timer = setTimeout(async () => {
inFlight?.abort(); // a superseded request is wasted capacity
inFlight = new AbortController();
try {
const r = await fetch(`/api/suggest?q=${encodeURIComponent(value)}`, {
signal: inFlight.signal,
});
render(await r.json());
} catch (err) {
if (err.name !== 'AbortError') throw err; // aborts are expected, not errors
}
}, 120); // ~120ms: below typical inter-keystroke time, above a fast typist's burst
}
Discussion