Design search autocomplete
Design search autocomplete. Start with a database query, let the keystroke budget force offline counts and a trie with the answer at every node, held in every server, then stress it with breaking news, the client, removals, thirty languages and hot prefixes, with interview prompts and code.
- Read first
- EstimationCaching
- Scaling patterns
- Hot keys and hot partitionsCQRS and materialized views
- Related
- Top-k heavy hitters
“Design the autocomplete for a search box. As the user types, show the top suggestions.”
The hard part is the clock. Every keystroke is a request, so the suggestion service gets several times the traffic of search itself. And an answer that arrives after the next keystroke is useless.
So this page starts with the obvious answer, a database query, and lets the clock break it. Step by step, we end with answers computed ahead of time and held in memory. Then we test that design against breaking news, slow phones, urgent removals and hot prefixes.
The answer in one minute
Section titled “The answer in one minute”If you only have a minute, this is the design. The rest of the page explains each part.
- Compute every answer ahead of time. A daily job counts what people searched. It builds a trie, a tree of prefixes, with the top 15 suggestions stored at every prefix. A lookup is just a walk down a few letters.
- Hold the whole trie in every server’s memory. About 35 GB. No database and no disk on the request path, so a lookup takes about a millisecond.
- Add a fast lane for news. A stream job spots queries that suddenly spike. It adds them on top of the daily trie within about 90 seconds.
- Check a blocklist on every response. A suggestion that must go is gone within a minute, without waiting for a rebuild.
- Keep the client honest and the edge busy. The browser cancels stale requests and reuses answers. One- and two-letter prefixes, the busiest of all, are cached at the CDN.
Scope it
Section titled “Scope it”A few questions decide what we complete, how fast, and how fresh.
Design the autocomplete for a search box. As the user types, show the top suggestions.
Whether you ask about volume, speed and freshness, and name privacy and removal as promises.
These four questions matter most:
- What are we completing? Search queries, ranked by what other people searched. Completing products or people would make the candidates a catalog instead.
- How many searches? 1 billion a day.
- How fast must it feel? Suggestions on screen within 100 ms of the request, on broadband.
- How fresh? Daily for most queries. Breaking news within 5 minutes.
From these answers we make five promises:
- Fast. Under 10 ms of server time for 99% of requests. A fast typist leaves about 150 ms between keystrokes, so a slower answer is already stale.
- Fail quietly. Up 99.9% of the time, and when it fails, the search box still works, just with no suggestions.
- Fresh. The main ranking at most 36 hours old. Trending queries within 5 minutes.
- Removable. A suggestion flagged as offensive or legally blocked disappears from new answers within 1 minute.
- Private. A query is only suggested if at least 50 different people searched it. One person’s search for their own phone number never becomes a suggestion.
We leave out the search results themselves, spelling correction, and ads. Personalized suggestions and more languages come later.
Go deeperMore questions, and what each changes1 min
| Question | We assume | If the answer were different |
|---|---|---|
| Personalized? | Not on the server in v1 | Server-side personalization defeats CDN caching |
| Languages? | One market first, about thirty later | Many markets multiply memory, and the market becomes the first split |
| Ten times more? | Not yet | Short prefixes go to the CDN from day one |
| A 300 ms budget? | No, 100 ms | A key-value read per keystroke would fit, and no in-memory trie |
The numbers that decide it
Section titled “The numbers that decide it”Now we work out the numbers. Each one should change a decision.
- Searches a day
- 1 billion
- Suggestion requests per search
- 6
- Peak over average
- 3×
- Candidate queries kept
- 100 million
- New prefixes each query adds
- 10
- Suggestions stored per prefix
- 15
- Answered by browser or CDN
- 0%
1 billion searches a day is 12,000 a second, 36,000 at peak. People type about 12 characters per search, and about half of those keystrokes reach us: 6 requests per search.
So we this serves six times more requests than search's own front door.
The 100 ms budget minus a round trip of 40 to 60 ms on broadband, and 100 ms or more on mobile.
So we no database query and no disk read. Answers are computed ahead of time and held in memory.
Billions of different queries, most typed once. Keeping those searched by at least 50 people in 28 days leaves about 100 million.
About 200 million trie nodes, each with its top 15 as IDs and scores: 200 million × 160 bytes plus 3 GB of query text ≈ 35 GB.
So we a full copy fits in every server's memory.
About 200 bytes per search event.
So we count it with a batch job over files, never with queries against a database.
At 20,000 requests a second per server, the peak needs only 11 to 18 servers. The system isn’t limited by CPU. The bill is memory × copies × regions. Try the calculator: triple the candidate queries and the trie passes 100 GB, which is when it must be split.
- Searches, average
- 12,000/s
- Suggestion requests, average
- 69,000/s
- Suggestion requests, peak
- 210,000/s
- Past what a key-value cluster serves at a low p99: hold the table in every server’s memory.
- Suggest servers at peak
- 18
- Each server takes about 20,000 requests/s and runs near 60% busy. Set stage 6’s edge share (about 40%) to see the saving.
- Trie nodes (radix trie: under 2 per query)
- 200 million
- Trie in memory
- 35 GB
- Fits in one server’s RAM: every server holds a full copy.
- Flat prefix table (every prefix a key)
- 450 GB
- Each prefix repeats its suggestions in full: many times the trie, and every key rewritten on every build.
- Search log a day
- 200 GB
- Input for a batch job, not a database: aggregate it with Spark into daily counts.
- Response bandwidth, peak
- 210 MB/s
- About 1 KB a response with headers. Not a design driver.
Build the design
Section titled “Build the design”We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs.
Step 1. Query a database
Section titled “Step 1. Query a database”The simple version runs SELECT query ... WHERE query LIKE 'wea%' ORDER BY count DESC LIMIT 8, and
adds one to a count on every search.
Stage 1: One server, one table
Stage 1 of 6
One server, one table
Why this stage
Nothing yet.
This is the smallest design that returns suggestions.
What we add
A suggest service that runs a prefix query against a Postgres table of query counts, and adds one to a count on every search.
What it costs
A range scan and a sort on every keystroke, a contended write on every search, and no redundancy.
At 210k suggestion requests per second, Snapshots is 10500% busy. Stage 2 is the fix.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
It manages about 2,000 queries a second, and it’s slowest on the shortest prefixes, like “s”, which match millions of rows. Short prefixes are also the most common requests. And 36,000 count updates a second pile onto the hottest rows.
But the answer for “wea” is the same for everyone in a market, and it changes slowly. So we compute it once, ahead of time.
Step 2. Count offline
Section titled “Step 2. Count offline”The search front end writes every search to a log in Kafka. A daily batch job reads the last 28 days and gives each candidate query a score:
score(q) = Σ over the last 28 days of distinct_users(q, day) × 0.5 ^ (age_in_days / 7)Last week counts more than last month, because each day’s weight halves every 7 days. And it counts different people, not searches, so a bot searching one phrase a million times counts once. The 50-person rule and filters for phone numbers and emails run before scoring.
Stage 2: Precompute every answer
Stage 2 of 6
Precompute every answer
Why this stage
At 210,000 requests/s, Postgres manages about 2,000 prefix queries/s, and "s" alone matches millions of rows.
Counting 36,000 searches/s in place is a second wall.
What we add
Searches go to a Kafka log.
A daily batch job turns them into scores and writes every prefix with its top 15 into a key-value table.
Stateless suggest servers read one key per keystroke.
What it costs
Suggestions are up to a day old, every keystroke pays a network hop, and a billion keys are rewritten every day.
At 210k suggestion requests per second, Snapshots is 175% busy. Stage 3 is the fix.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
Go deeperWhat the daily counting job does1 min
At 36,000 searches a second, the log holds about 3 billion searches a day, and 28 days of it is the input. A batch job, in Spark or a similar engine, reads it in four passes.
- Clean. Lowercase each query, trim spaces, and drop anything that looks like a phone number, an email address or a card number.
- Count people, not searches. For each market, query and day, count distinct users. An exact count would need every user ID in memory. So each query keeps a small HyperLogLog sketch. It’s a few KB, and it estimates distinct users within about 1%.
- Filter. Drop any query fewer than 50 people searched, and anything on the blocklist.
- Score and build. Apply the 7-day half-life, sort by score, and insert into the trie from the top.
The job takes a few hours, which is why freshness needs the separate overlay in step 5.
Step 3. A trie with the answer at every node
Section titled “Step 3. A trie with the answer at every node”A trie stores strings by their letters: “w”, then “we”, then “wea”, each a node. The textbook version finds suggestions by visiting every query below the node, then sorting. That’s fine for “weather in os”, and hopeless for “s”, which has tens of millions of queries below it.
So we store the answer at the node. Each node keeps its own top 15. A lookup walks down the letters of the prefix, and the answer is already there. “s” costs the same as “weather in oslo”.
Building it is simple, with one trick: insert queries from highest score to lowest. Then the first 15 queries that pass through any node are exactly its top 15. No node ever sorts anything.
// The serving structure: a trie in which every node keeps its own best completions, so a// lookup is one walk down the prefix and never a search of the subtree below it.// Production stores it as flat arrays, collapses chains of single-child nodes (a radix trie)// and keeps query ids instead of strings: about 120 bytes a node.final class SuggestTrie { private static final class Node { final Map<Character, Node> children = new HashMap<>(); final List<String> top = new ArrayList<>(); // best first, at most k entries }
private final int k; private final Node root = new Node();
// Built offline from the batch scores, then never changed: servers swap in a whole new // trie instead of editing this one, so concurrent reads need no locks. SuggestTrie(Map<String, Long> scores, int k) { this.k = k; List<Map.Entry<String, Long>> best = new ArrayList<>(scores.entrySet()); // Ties broken by text, so two builds from the same input are byte-for-byte identical. best.sort(Map.Entry.<String, Long>comparingByValue().reversed() .thenComparing(Map.Entry.comparingByKey())); for (Map.Entry<String, Long> e : best) insert(e.getKey()); }
// Inserting best first means the first k queries through a node are exactly its top k. // No node ever sorts or evicts, so the whole build is one pass over every character. private void insert(String query) { Node node = root; for (char c : query.toCharArray()) { node = node.children.computeIfAbsent(c, x -> new Node()); if (node.top.size() < k) node.top.add(query); } }
// Costs the length of the prefix, whatever the prefix: "s" costs the same as // "weather in osl", although millions of queries start with "s". List<String> lookup(String prefix) { Node node = root; for (char c : prefix.toCharArray()) { node = node.children.get(c); if (node == null) return List.of(); // nobody has searched anything starting with this } return Collections.unmodifiableList(node.top); }}# The serving structure: a trie in which every node keeps its own best completions, so a# lookup is one walk down the prefix and never a search of the subtree below it.# Production stores it as flat arrays, collapses chains of single-child nodes (a radix# trie) and keeps query ids instead of strings: about 120 bytes a node.class SuggestTrie: class _Node: __slots__ = ("children", "top")
def __init__(self) -> None: self.children: dict[str, SuggestTrie._Node] = {} self.top: list[str] = [] # best first, at most k entries
def __init__(self, scores: dict[str, int], k: int) -> None: # Built offline from the batch scores, then never changed: servers swap in a whole # new trie instead of editing this one, so concurrent reads need no locks. self._k = k self._root = SuggestTrie._Node() # Ties broken by text, so two builds from the same input are byte-for-byte identical. for query in sorted(scores, key=lambda q: (-scores[q], q)): self._insert(query)
def _insert(self, query: str) -> None: # Inserting best first means the first k queries through a node are exactly its top # k. No node ever sorts or evicts, so the build is one pass over every character. node = self._root for ch in query: node = node.children.setdefault(ch, SuggestTrie._Node()) if len(node.top) < self._k: node.top.append(query)
def lookup(self, prefix: str) -> list[str]: # Costs the length of the prefix, whatever the prefix: "s" costs the same as # "weather in osl", although millions of queries start with "s". node = self._root for ch in prefix: node = node.children.get(ch) if node is None: return [] # nobody has searched anything starting with this return list(node.top)// The serving structure: a trie in which every node keeps its own best completions, so a// lookup is one walk down the prefix and never a search of the subtree below it.// Production stores it as flat arrays, collapses chains of single-child nodes (a radix trie)// and keeps query ids instead of strings: about 120 bytes a node.sealed class SuggestTrie{ private sealed class Node { public readonly Dictionary<char, Node> Children = new(); public readonly List<string> Top = new(); // best first, at most k entries }
private readonly int _k; private readonly Node _root = new();
// Built offline from the batch scores, then never changed: servers swap in a whole new // trie instead of editing this one, so concurrent reads need no locks. public SuggestTrie(IReadOnlyDictionary<string, long> scores, int k) { _k = k; // Ties broken by text, so two builds from the same input are byte-for-byte identical. var best = scores.OrderByDescending(e => e.Value).ThenBy(e => e.Key, StringComparer.Ordinal); foreach (var (query, _) in best) Insert(query); }
// Inserting best first means the first k queries through a node are exactly its top k. // No node ever sorts or evicts, so the whole build is one pass over every character. private void Insert(string query) { var node = _root; foreach (char c in query) { if (!node.Children.TryGetValue(c, out var child)) node.Children[c] = child = new Node(); node = child; if (node.Top.Count < _k) node.Top.Add(query); } }
// Costs the length of the prefix, whatever the prefix: "s" costs the same as // "weather in osl", although millions of queries start with "s". public IReadOnlyList<string> Lookup(string prefix) { var node = _root; foreach (char c in prefix) { if (!node.Children.TryGetValue(c, out node)) return Array.Empty<string>(); // nobody has searched anything starting with this } return node.Top.AsReadOnly(); }}// node is one prefix. Every node keeps its own best completions, so a lookup is one walk// down the prefix and never a search of the subtree below it.type node struct { children map[rune]*node top []string // best first, at most k entries}
// SuggestTrie is built offline from the batch scores, then never changed: servers swap in a// whole new trie instead of editing this one, so concurrent reads need no locks.// Production stores it as flat arrays, collapses chains of single-child nodes (a radix trie)// and keeps query ids instead of strings: about 120 bytes a node.type SuggestTrie struct { root *node}
func BuildTrie(scores map[string]int64, k int) *SuggestTrie { queries := make([]string, 0, len(scores)) for q := range scores { queries = append(queries, q) } // Ties broken by text, so two builds from the same input are byte-for-byte identical. sort.Slice(queries, func(i, j int) bool { if scores[queries[i]] != scores[queries[j]] { return scores[queries[i]] > scores[queries[j]] } return queries[i] < queries[j] })
t := &SuggestTrie{root: &node{children: map[rune]*node{}}} // Inserting best first means the first k queries through a node are exactly its top k. // No node ever sorts or evicts, so the whole build is one pass over every character. for _, q := range queries { n := t.root for _, r := range q { child, ok := n.children[r] if !ok { child = &node{children: map[rune]*node{}} n.children[r] = child } n = child if len(n.top) < k { n.top = append(n.top, q) } } } return t}
// Lookup costs the length of the prefix, whatever the prefix: "s" costs the same as// "weather in osl", although millions of queries start with "s".func (t *SuggestTrie) Lookup(prefix string) []string { n := t.root for _, r := range prefix { if n = n.children[r]; n == nil { return nil // nobody has searched anything starting with this } } // Capped at its length, so a caller's append copies instead of writing into the shared trie. return n.top[:len(n.top):len(n.top)]}// The serving structure: a trie in which every node keeps its own best completions, so a// lookup is one walk down the prefix and never a search of the subtree below it.// Production stores it as flat arrays, collapses chains of single-child nodes (a radix trie)// and keeps query ids instead of strings: about 120 bytes a node.interface TrieNode { children: Map<string, TrieNode>; top: string[]; // best first, at most k entries}
class SuggestTrie { private readonly root: TrieNode = { children: new Map(), top: [] };
// Built offline from the batch scores, then never changed: servers swap in a whole new // trie instead of editing this one, so a request never sees half an update. constructor( scores: Map<string, number>, private readonly k: number, ) { // Ties broken by text, so two builds from the same input are byte-for-byte identical. const best = [...scores].sort(([qa, a], [qb, b]) => b - a || (qa < qb ? -1 : qa > qb ? 1 : 0)); for (const [query] of best) this.insert(query); }
// Inserting best first means the first k queries through a node are exactly its top k. // No node ever sorts or evicts, so the whole build is one pass over every character. private insert(query: string): void { let node = this.root; for (const ch of query) { let child = node.children.get(ch); if (!child) node.children.set(ch, (child = { children: new Map(), top: [] })); node = child; if (node.top.length < this.k) node.top.push(query); } }
// Costs the length of the prefix, whatever the prefix: "s" costs the same as // "weather in osl", although millions of queries start with "s". lookup(prefix: string): readonly string[] { let node: TrieNode | undefined = this.root; for (const ch of prefix) { node = node.children.get(ch); if (!node) return []; // nobody has searched anything starting with this } return node.top; }}The code builds a plain trie to keep the idea clear. The real one is a radix trie, which merges chains of single-child nodes into one. That keeps it under 2 nodes per query: 35 GB instead of a billion nodes.
Go deeperWhy a radix trie stays small1 min
A plain trie over 100 million queries has about a billion nodes, one per distinct prefix. Most of them are long chains inside one query’s unique ending, like the letters after “weather in osl”. Each holds the same one-item list. A radix trie merges each chain into a single edge. Then every inner node either has at least two children, or marks the end of a query. So n queries make at most about 2n nodes.
A prefix that stops partway along a merged edge, like “weath” inside “weather”, is answered by the node at the end of that edge. Its list is the same, because nothing branches in between.
Step 4. The trie in every server’s memory
Section titled “Step 4. The trie in every server’s memory”The batch job writes the trie as a snapshot, a versioned file in Amazon S3. Every suggest server loads the current version into memory and answers from it. Any server can answer any prefix, and if S3 is down, servers keep serving what they have.
Stage 3: The table in every server
Stage 3 of 6
The table in every server
Why this stage
At the 210,000/s peak the prefix table cluster (about 120,000 reads/s) is past its limit, and its tail adds 5 to 10 ms.
The data is read-only for a day and fits in about 35 GB.
What we add
The batch job builds a compact trie with the top 15 cached at every node and publishes it as a versioned snapshot to object storage.
Every suggest server loads it into memory.
What it costs
About 35 GB of RAM per server, a few minutes to load each new version, and two versions live side by side during a rollout.
At 210k suggestion requests per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
A new snapshot never goes live everywhere at once. A bad build, like a scoring bug, would be a global incident in seconds. So it’s checked against a fixed set of prefixes, tried on two canary servers, then rolled out in waves of 10%. Each server swaps one pointer, so a request sees the old version or the new one, never a mix. The old version stays in memory for an hour, so rollback is a pointer flip.
Go deeperThe snapshot rollout, step by step1 min
- Color key
- Service
- Database
- Background worker
Why not update the trie live on every search? At 36,000 searches a second, each search would update the lists of about 20 nodes, on every server, under locks that block readers. It would be easy to game, and a bad update would be live everywhere with no rollback. Building offline and swapping whole versions gives lock-free reads, checks before going live, and one-step rollback.
Step 5. Fresh news and fast removal
Section titled “Step 5. Fresh news and fast removal”The daily trie is a day old by design. Two small additions fix that without touching it.
- Trending. A stream job (Flink) reads the log and spots queries searched far more than usual. For each prefix of a trending query, it writes a short list to a Redis overlay. Servers pull the overlay every 30 seconds and merge it with the trie’s answer.
- Removal. A blocklist of exact queries and single words is pulled by every server every 10 seconds, and checked on every response. Nothing is rebuilt.
Stage 4: Fresh and safe
Stage 4 of 6
Fresh and safe
Why this stage
News breaks in minutes, not days.
A court order or an offensive suggestion must disappear within a minute, without waiting for tomorrow’s build.
What we add
A stream job that spots trending queries with decayed counts and publishes a small overlay to Redis, and a blocklist every server checks on every request.
What it costs
Two more moving parts, and trending lists are noisier and easier to game than the daily batch.
At 210k suggestion requests per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
Follow one keystroke through the design:
Trace a request: Keystroke to suggestions
Keystroke to suggestions: step 1 of 5
Users to Prefix router
The user paused 50 ms after typing "wea". The browser sends GET /v1/suggest?q=wea over an HTTP/2 connection it opened when the search box got focus, so there is no TCP or TLS handshake. About 25 ms each way to the nearest region on broadband; this hop counts the round trip.
- Users → Prefix router50 ms
- Prefix router → Suggest shards1 ms
- Suggest shards → Trend cacheasync
- Suggest shards → Blocklistasync
- Response
Server time is about 1 ms. The other 50 are network. Each server reads its three inputs (trie, overlay, blocklist) once per request, and a background refresher swaps each one whole:
// The request path on a suggest server after the trie lookup: blend in trending queries,// drop anything removed, return the best eight. Everything here is in memory.record Scored(String text, double score) {}
interface PrefixIndex { List<Scored> lookup(String prefix); // the daily trie, best first}
final class Suggester { private static final int SHOW = 8;
// Three inputs that change at different speeds. A background refresher replaces each one // whole, so a request never sees a half-applied update and never takes a lock. volatile PrefixIndex index; // daily: a new snapshot volatile Map<String, List<Scored>> trending = Map.of(); // every 30 s: prefix -> trending queries volatile Set<String> blockedQueries = Set.of(); // every 10 s: removals land here, volatile Set<String> blockedTerms = Set.of(); // with no rebuild of anything
Suggester(PrefixIndex index) { this.index = index; }
List<String> suggest(String raw) { String prefix = normalize(raw); // The trie keeps 15 per prefix although we show 8, so removals still leave a full list. List<Scored> merged = new ArrayList<>(index.lookup(prefix)); merged.addAll(trending.getOrDefault(prefix, List.of())); // The overlay builder puts trending scores on the batch scale, so one sort ranks both. merged.sort(Comparator.comparingDouble(Scored::score).reversed());
Set<String> queries = blockedQueries, terms = blockedTerms; // one consistent version Set<String> out = new LinkedHashSet<>(); // a query in both lists appears once for (Scored s : merged) { if (out.size() == SHOW) break; if (queries.contains(s.text()) || hasBlockedTerm(s.text(), terms)) continue; out.add(s.text()); } return List.copyOf(out); }
// Term matching catches new variants of a removed phrase that no exact list would hold. private static boolean hasBlockedTerm(String text, Set<String> terms) { for (String word : text.split(" ")) if (terms.contains(word)) return true; return false; }
// Lowercase and collapse runs of spaces, but keep a trailing space: "new " is a different // prefix from "new". Real systems also apply Unicode NFKC and per-language folding. static String normalize(String raw) { return raw.toLowerCase(Locale.ROOT).replaceAll("\\s+", " ").stripLeading(); }}@dataclass(frozen=True)class Scored: text: str score: float
class PrefixIndex(Protocol): def lookup(self, prefix: str) -> list[Scored]: ... # the daily trie, best first
# The request path on a suggest server after the trie lookup: blend in trending queries,# drop anything removed, return the best eight. Everything here is in memory.class Suggester: SHOW = 8
def __init__(self, index: PrefixIndex) -> None: # Three inputs that change at different speeds. A background refresher replaces each # one whole (a single reference assignment), so a request never sees a half-applied # update and never takes a lock. self.index = index # daily: a new snapshot self.trending: dict[str, list[Scored]] = {} # every 30 s: prefix -> trending queries self.blocked_queries: frozenset[str] = frozenset() # every 10 s: removals land here, self.blocked_terms: frozenset[str] = frozenset() # with no rebuild of anything
def suggest(self, raw: str) -> list[str]: prefix = normalize(raw) # The trie keeps 15 per prefix although we show 8, so removals still leave a full list. merged = self.index.lookup(prefix) + self.trending.get(prefix, []) # The overlay builder puts trending scores on the batch scale, so one sort ranks both. merged.sort(key=lambda s: s.score, reverse=True)
queries, terms = self.blocked_queries, self.blocked_terms # one consistent version out: dict[str, None] = {} # insertion ordered; a query in both lists appears once for s in merged: if len(out) == self.SHOW: break if s.text in queries or _has_blocked_term(s.text, terms): continue out[s.text] = None return list(out)
def _has_blocked_term(text: str, terms: frozenset[str]) -> bool: # Term matching catches new variants of a removed phrase that no exact list would hold. return any(word in terms for word in text.split(" "))
def normalize(raw: str) -> str: # Lowercase and collapse runs of spaces, but keep a trailing space: "new " is a different # prefix from "new". Real systems also apply Unicode NFKC and per-language folding. return re.sub(r"\s+", " ", raw.lower()).lstrip()// The request path on a suggest server after the trie lookup: blend in trending queries,// drop anything removed, return the best eight. Everything here is in memory.record Scored(string Text, double Score);
interface IPrefixIndex{ IReadOnlyList<Scored> Lookup(string prefix); // the daily trie, best first}
sealed class Suggester(IPrefixIndex index){ const int Show = 8;
// Three inputs that change at different speeds. A background refresher replaces each one // whole (Volatile.Write), so a request never sees a half-applied update or takes a lock. public IPrefixIndex Index = index; // daily: a new snapshot public IReadOnlyDictionary<string, IReadOnlyList<Scored>> Trending = // every 30 s new Dictionary<string, IReadOnlyList<Scored>>(); public IReadOnlySet<string> BlockedQueries = new HashSet<string>(); // every 10 s: removals public IReadOnlySet<string> BlockedTerms = new HashSet<string>(); // land here, no rebuild
public IReadOnlyList<string> Suggest(string raw) { string prefix = Normalize(raw); // The trie keeps 15 per prefix although we show 8, so removals still leave a full list. var merged = Volatile.Read(ref Index).Lookup(prefix) .Concat(Volatile.Read(ref Trending).GetValueOrDefault(prefix) ?? Array.Empty<Scored>()) // The overlay builder puts trending scores on the batch scale, so one sort ranks both. .OrderByDescending(s => s.Score);
var queries = Volatile.Read(ref BlockedQueries); // one consistent version per request var terms = Volatile.Read(ref BlockedTerms); return merged .Where(s => !queries.Contains(s.Text) && !HasBlockedTerm(s.Text, terms)) .Select(s => s.Text) .Distinct() // a query in both lists appears once, at its best position .Take(Show) .ToList(); }
// Term matching catches new variants of a removed phrase that no exact list would hold. static bool HasBlockedTerm(string text, IReadOnlySet<string> terms) => text.Split(' ').Any(terms.Contains);
// Lowercase and collapse runs of spaces, but keep a trailing space: "new " is a different // prefix from "new". Real systems also apply Unicode NFKC and per-language folding. public static string Normalize(string raw) => Regex.Replace(raw.ToLowerInvariant(), @"\s+", " ").TrimStart();}// Scored is one candidate with its ranking score.type Scored struct { Text string Score float64}
// PrefixIndex is the daily trie: best first.type PrefixIndex interface { Lookup(prefix string) []Scored}
// inputs are three things that change at different speeds: the index daily, the trending// overlay every 30 s, the blocklists every 10 s. A refresher builds a new inputs value and// swaps the pointer, so a request never sees a half-applied update and never takes a lock.type inputs struct { index PrefixIndex trending map[string][]Scored // prefix -> trending queries blockedQueries map[string]bool // removals land here, with no rebuild of anything blockedTerms map[string]bool}
// Suggester is the request path on a suggest server after the trie lookup: blend in// trending queries, drop anything removed, return the best eight. All in memory.type Suggester struct { current atomic.Pointer[inputs]}
const show = 8
func (s *Suggester) Suggest(raw string) []string { prefix := Normalize(raw) in := s.current.Load() // one consistent version for the whole request // The trie keeps 15 per prefix although we show 8, so removals still leave a full list. merged := append(slices.Clone(in.index.Lookup(prefix)), in.trending[prefix]...) // The overlay builder puts trending scores on the batch scale, so one sort ranks both. sort.SliceStable(merged, func(i, j int) bool { return merged[i].Score > merged[j].Score })
out := make([]string, 0, show) seen := map[string]bool{} // a query in both lists appears once for _, c := range merged { if len(out) == show { break } if seen[c.Text] || in.blockedQueries[c.Text] || hasBlockedTerm(c.Text, in.blockedTerms) { continue } seen[c.Text] = true out = append(out, c.Text) } return out}
// hasBlockedTerm catches new variants of a removed phrase that no exact list would hold.func hasBlockedTerm(text string, terms map[string]bool) bool { for _, word := range strings.Split(text, " ") { if terms[word] { return true } } return false}
var spaces = regexp.MustCompile(`\s+`)
// Normalize lowercases and collapses runs of spaces, but keeps a trailing space: "new " is a// different prefix from "new". Real systems also apply Unicode NFKC and per-language folding.func Normalize(raw string) string { return strings.TrimLeft(spaces.ReplaceAllString(strings.ToLower(raw), " "), " ")}// The request path on a suggest server after the trie lookup: blend in trending queries,// drop anything removed, return the best eight. Everything here is in memory.interface Scored { text: string; score: number;}
interface PrefixIndex { lookup(prefix: string): readonly Scored[]; // the daily trie, best first}
class Suggester { private static readonly SHOW = 8;
// Three inputs that change at different speeds. A background refresher replaces each one // whole, and JavaScript runs one callback at a time, so a request never sees half an update. trending = new Map<string, Scored[]>(); // every 30 s: prefix -> trending queries blockedQueries = new Set<string>(); // every 10 s: removals land here, blockedTerms = new Set<string>(); // with no rebuild of anything
constructor(public index: PrefixIndex) {} // daily: a new snapshot
suggest(raw: string): string[] { const prefix = normalize(raw); // The trie keeps 15 per prefix although we show 8, so removals still leave a full list. const merged = [...this.index.lookup(prefix), ...(this.trending.get(prefix) ?? [])]; // The overlay builder puts trending scores on the batch scale, so one sort ranks both. merged.sort((a, b) => b.score - a.score);
const out = new Set<string>(); // a query in both lists appears once for (const s of merged) { if (out.size === Suggester.SHOW) break; if (this.blockedQueries.has(s.text) || this.hasBlockedTerm(s.text)) continue; out.add(s.text); } return [...out]; }
// Term matching catches new variants of a removed phrase that no exact list would hold. private hasBlockedTerm(text: string): boolean { return text.split(' ').some((word) => this.blockedTerms.has(word)); }}
// Lowercase and collapse runs of spaces, but keep a trailing space: "new " is a different// prefix from "new". Real systems also apply Unicode NFKC and per-language folding.function normalize(raw: string): string { return raw.toLowerCase().replace(/\s+/g, ' ').trimStart();}One cacheable request
Section titled “One cacheable request”The API is one plain GET, so browsers and the CDN can cache it by URL:
GET /v1/suggest?q=wea&market=en-US&limit=8
200 OKCache-Control: private, max-age=300
{ "q": "wea", "suggestions": [ { "text": "weather" }, { "text": "weather tomorrow" } ], "complete": false }The prefix is normalized on both sides, so Wea and wea share one cache entry. An unknown prefix
returns 200 with an empty list, never 404, because an empty answer can be cached too.
complete: true means the list holds every completion that exists, which the client stress test
uses.
This is enough for a mid-level answer. Offline counting. A trie with the top k at every node, in memory on every server. Plus a trending overlay and a blocklist. The stress tests are what make it a senior answer.
Go deeperOther ways to answer a prefix2 min
| Option | Lookup cost | Memory for 100M queries | Fits here? |
|---|---|---|---|
SQL LIKE 'p%' ORDER BY score |
A scan, slowest on short prefixes | A 10 GB table | No: about 2,000 a second |
| Plain trie, search below the node | The whole subtree | About a billion nodes | No: “s” has tens of millions below it |
| Trie with top k at every node | Prefix length only, microseconds | About 35 GB | Yes: built offline, served from memory |
| A key-value table, prefix → top 15 | One network read, about 1 ms | About 450 GB | Fine if the budget allowed a network hop |
| Finite state transducer (Lucene) | Prefix walk plus a small search | Several times smaller | The upgrade when memory becomes the limit |
The key-value table is a natural middle step: every prefix as a key, its 15 answers as the value, in Cassandra or DynamoDB. It works up to about 120,000 reads a second. But it adds 5 to 10 ms to a 10 ms budget, and rewriting a billion keys a day is its heaviest load. Data that’s read-only for a day and fits in 35 GB belongs in memory.
Memory tricks. Production layouts are a few large arrays loaded straight from the snapshot file. They aren’t 200 million objects, which would spend more on object headers and garbage collection than on data. Scores can be squeezed to 2 bytes. And nodes with fewer than 15 queries below them need no list of their own.
Go deeperHow the overlay merges with the trie1 min
The stream job compares each query’s searches in the last 10 minutes with what is normal for that time of day. A query searched 20 times more than usual is trending. The job then writes it into the overlay for every prefix of the query, with a boost score. Entries expire after 6 hours unless the job keeps refreshing them, so a story that fades drops out by itself.
On each request, the server takes the trie’s 15 answers and the overlay’s few. It sorts them together by score, and removes duplicates and anything on the blocklist. Then it keeps the top 8. That is a few microseconds of work, on lists that are already in memory.
The overlay stays small: a few thousand trending queries, each written under a dozen or so prefixes. So servers can pull the whole thing every 30 seconds without strain. The blocklist is even smaller, and it is checked last, so a trending query that is also blocked never shows.
Stress it
Section titled “Stress it”The design is complete. Now we test it against what autocomplete is known for: breaking news, a slow phone, a legal removal, thirty languages, and one hot prefix. The last two add boxes.
Ranking and breaking news
Section titled “Ranking and breaking news”How do you decide which queries rank highest, and how do you balance stable rankings against breaking news?
Whether you balance stable rankings against news, and keep bots and personal data out.
How fresh the pipeline is, is a choice with its own cost:
| Approach | Freshness | Cost and risk |
|---|---|---|
| Daily batch only | Up to 36 hours | Cheapest, stable, checked before going live; misses news |
| Hourly batch | 1 to 2 hours | 24 rollouts of 35 GB a day, and still too slow for news |
| Streaming only | Seconds | Every change goes live unchecked; jumpy lists; easy to game |
| Daily batch plus trending overlay | About 90 s for spikes | Two pipelines, but the fast one touches a few thousand queries |
The trending signal asks a different question from the score. Not “how big is this query?”, but “how much bigger than usual?”. A query trends when its recent count is at least 5 times what its daily rate predicts, and above a minimum count.
// The trending path: a decayed count per query, fed by the stream of search events. Old// searches fade smoothly, so there is no window edge where a burst suddenly drops out.// The stream job partitions events by query, so each worker holds only its slice of keys.final class TrendDetector { private record Decayed(double value, long atMillis) {}
private final double halfLifeMillis; // 30 minutes: how fast a burst fades once it stops private final double minCount; // a handful of searches is noise, not news private final double minLift; // how many times its normal rate a query must reach // Idle keys are evicted after a few half-lives; a count-min sketch can cap memory further. private final Map<String, Decayed> counts = new HashMap<>();
TrendDetector(double halfLifeMillis, double minCount, double minLift) { this.halfLifeMillis = halfLifeMillis; this.minCount = minCount; this.minLift = minLift; }
// The real job counts distinct users per query (a HyperLogLog per key), so one script // repeating a query cannot make it trend. void record(String query, long nowMillis) { counts.put(query, new Decayed(current(query, nowMillis) + 1, nowMillis)); }
// Decay is applied lazily, when a key is read or written, so idle keys cost nothing. double current(String query, long nowMillis) { Decayed d = counts.get(query); if (d == null) return 0; return d.value() * Math.pow(0.5, (nowMillis - d.atMillis()) / halfLifeMillis); }
// normalPerHour comes from the batch counts. A query searched at a steady rate settles at // rate x halfLife / ln 2, so the baseline is put on that scale before comparing. boolean isTrending(String query, double normalPerHour, long nowMillis) { double count = current(query, nowMillis); double expected = normalPerHour / 3_600_000.0 * halfLifeMillis / Math.log(2); return count >= minCount && count >= minLift * expected; }}# The trending path: a decayed count per query, fed by the stream of search events. Old# searches fade smoothly, so there is no window edge where a burst suddenly drops out.# The stream job partitions events by query, so each worker holds only its slice of keys.class TrendDetector: def __init__(self, half_life_ms: float, min_count: float, min_lift: float) -> None: self._half_life_ms = half_life_ms # 30 minutes: how fast a burst fades once it stops self._min_count = min_count # a handful of searches is noise, not news self._min_lift = min_lift # how many times its normal rate a query must reach # query -> (value, at_ms). Idle keys are evicted after a few half-lives; a # count-min sketch can cap memory further. self._counts: dict[str, tuple[float, int]] = {}
def record(self, query: str, now_ms: int) -> None: # The real job counts distinct users per query (a HyperLogLog per key), so one # script repeating a query cannot make it trend. self._counts[query] = (self.current(query, now_ms) + 1, now_ms)
def current(self, query: str, now_ms: int) -> float: # Decay is applied lazily, when a key is read or written, so idle keys cost nothing. entry = self._counts.get(query) if entry is None: return 0.0 value, at_ms = entry return value * 0.5 ** ((now_ms - at_ms) / self._half_life_ms)
def is_trending(self, query: str, normal_per_hour: float, now_ms: int) -> bool: # normal_per_hour comes from the batch counts. A query searched at a steady rate # settles at rate x half_life / ln 2, so the baseline is put on that scale first. count = self.current(query, now_ms) expected = normal_per_hour / 3_600_000 * self._half_life_ms / math.log(2) return count >= self._min_count and count >= self._min_lift * expected// The trending path: a decayed count per query, fed by the stream of search events. Old// searches fade smoothly, so there is no window edge where a burst suddenly drops out.// The stream job partitions events by query, so each worker holds only its slice of keys.sealed class TrendDetector(double halfLifeMs, double minCount, double minLift){ // halfLifeMs: 30 minutes, how fast a burst fades once it stops. // minCount: a handful of searches is noise, not news. // minLift: how many times its normal rate a query must reach. private readonly record struct Decayed(double Value, long AtMs);
// Idle keys are evicted after a few half-lives; a count-min sketch can cap memory further. private readonly Dictionary<string, Decayed> _counts = new();
// The real job counts distinct users per query (a HyperLogLog per key), so one script // repeating a query cannot make it trend. public void Record(string query, long nowMs) => _counts[query] = new Decayed(Current(query, nowMs) + 1, nowMs);
// Decay is applied lazily, when a key is read or written, so idle keys cost nothing. public double Current(string query, long nowMs) => _counts.TryGetValue(query, out var d) ? d.Value * Math.Pow(0.5, (nowMs - d.AtMs) / halfLifeMs) : 0;
// normalPerHour comes from the batch counts. A query searched at a steady rate settles at // rate x halfLife / ln 2, so the baseline is put on that scale before comparing. public bool IsTrending(string query, double normalPerHour, long nowMs) { double count = Current(query, nowMs); double expected = normalPerHour / 3_600_000.0 * halfLifeMs / Math.Log(2); return count >= minCount && count >= minLift * expected; }}type decayed struct { value float64 at time.Time}
// TrendDetector is the trending path: a decayed count per query, fed by the stream of search// events. Old searches fade smoothly, so there is no window edge where a burst suddenly// drops out. The stream job partitions events by query, so each worker holds only its slice.type TrendDetector struct { halfLife time.Duration // 30 minutes: how fast a burst fades once it stops minCount float64 // a handful of searches is noise, not news minLift float64 // how many times its normal rate a query must reach // Idle keys are evicted after a few half-lives; a count-min sketch can cap memory further. counts map[string]decayed}
func NewTrendDetector(halfLife time.Duration, minCount, minLift float64) *TrendDetector { return &TrendDetector{halfLife, minCount, minLift, map[string]decayed{}}}
// Record adds one search. The real job counts distinct users per query (a HyperLogLog per// key), so one script repeating a query cannot make it trend.func (t *TrendDetector) Record(query string, now time.Time) { t.counts[query] = decayed{t.Current(query, now) + 1, now}}
// Current applies decay lazily, when a key is read or written, so idle keys cost nothing.func (t *TrendDetector) Current(query string, now time.Time) float64 { d, ok := t.counts[query] if !ok { return 0 } return d.value * math.Pow(0.5, float64(now.Sub(d.at))/float64(t.halfLife))}
// IsTrending compares against normalPerHour from the batch counts. A query searched at a// steady rate settles at rate x halfLife / ln 2, so the baseline is put on that scale first.func (t *TrendDetector) IsTrending(query string, normalPerHour float64, now time.Time) bool { count := t.Current(query, now) expected := normalPerHour / time.Hour.Seconds() * t.halfLife.Seconds() / math.Ln2 return count >= t.minCount && count >= t.minLift*expected}// The trending path: a decayed count per query, fed by the stream of search events. Old// searches fade smoothly, so there is no window edge where a burst suddenly drops out.// The stream job partitions events by query, so each worker holds only its slice of keys.class TrendDetector { // Idle keys are evicted after a few half-lives; a count-min sketch can cap memory further. private readonly counts = new Map<string, { value: number; atMs: number }>();
constructor( private readonly halfLifeMs: number, // 30 minutes: how fast a burst fades once it stops private readonly minCount: number, // a handful of searches is noise, not news private readonly minLift: number, // how many times its normal rate a query must reach ) {}
// The real job counts distinct users per query (a HyperLogLog per key), so one script // repeating a query cannot make it trend. record(query: string, nowMs: number): void { this.counts.set(query, { value: this.current(query, nowMs) + 1, atMs: nowMs }); }
// Decay is applied lazily, when a key is read or written, so idle keys cost nothing. current(query: string, nowMs: number): number { const d = this.counts.get(query); return d ? d.value * 0.5 ** ((nowMs - d.atMs) / this.halfLifeMs) : 0; }
// normalPerHour comes from the batch counts. A query searched at a steady rate settles at // rate x halfLife / ln 2, so the baseline is put on that scale before comparing. isTrending(query: string, normalPerHour: number, nowMs: number): boolean { const count = this.current(query, nowMs); const expected = ((normalPerHour / 3_600_000) * this.halfLifeMs) / Math.LN2; return count >= this.minCount && count >= this.minLift * expected; }}The code keeps a decayed count: one number and one timestamp per query. It fades smoothly over time, instead of dropping off a cliff at a window’s edge. A brand-new query has no normal rate, so only the minimum count applies. That’s how a never-seen “earthquake tokyo” trends in its first minute.
Abuse lives on the fast path. Organized groups push phrases about a person or a brand. So trending counts people spread across networks, and runs the same filters as the batch. It also limits how high an unreviewed trending entry can rank on short prefixes.
Go deeperHow long does news take, step by step?1 min
| Step | What happens | Delay |
|---|---|---|
| Search to Kafka | The search front end batches events | Up to 1 s |
| Trend worker | Compares counts with normal rates once a minute | Up to 60 s |
| Overlay to Redis | Writes a short list for every prefix of the query | About 1 s |
| Servers pull it | Every 30 s; the next keystroke merges it | Up to 30 s |
| Total | Worst case, inside the 5-minute promise | About 92 s |
One- and two-letter prefixes, cached at the edge, can take up to 5 minutes longer.
The keystroke budget on the client
Section titled “The keystroke budget on the client”The server answers in a millisecond, but users on phones say autocomplete feels laggy. What can the client do?
On mobile, the round trip alone is 100 ms or more. So most of the budget belongs to the client. Five habits do the work:
- Wait briefly. Wait about 50 ms after a keystroke, so a fast burst becomes one request. This is called a debounce.
- Cancel what’s stale. When the user types past a prefix, abort its wait or its request.
- Paint only the latest. Answers can arrive out of order, so drop any answer that isn’t for the current text.
- Reuse complete answers. If “wea” came back with
complete: true, “weat” is just a filter of that list, with no request. - Warm the connection. Open it when the box gets focus, so the secure handshake never lands on a keystroke.
- Color key
- Service
// The client side of the latency budget: wait for a short pause in typing, cancel whatever// the user has typed past, never paint an answer for an old prefix, and skip the network// when an earlier answer already holds everything.record Result(List<String> items, boolean complete) {} // complete: every completion that exists
interface Fetcher { CompletableFuture<Result> fetch(String prefix); // HttpClient.sendAsync underneath}
final class SuggestClient { private static final long DEBOUNCE_MS = 50; // merges bursts; 300 ms would spend the budget waiting
private final Fetcher fetcher; private final BiConsumer<String, List<String>> render; private final Map<String, Result> cache = new HashMap<>(); // this session only; guarded by this private long latest; // the newest keystroke's number private CompletableFuture<Result> inFlight;
SuggestClient(Fetcher fetcher, BiConsumer<String, List<String>> render) { this.fetcher = fetcher; this.render = render; }
synchronized void onInput(String raw) { String prefix = raw.toLowerCase(Locale.ROOT).replaceAll("\\s+", " ").stripLeading(); long seq = ++latest; // every older wait and answer is now stale if (inFlight != null) inFlight.cancel(true); // the user typed past it
List<String> local = fromCache(prefix); if (local != null) { render.accept(prefix, local); // backspace, or a complete shorter answer return; } CompletableFuture.delayedExecutor(DEBOUNCE_MS, TimeUnit.MILLISECONDS) .execute(() -> load(prefix, seq)); }
private synchronized List<String> fromCache(String prefix) { Result exact = cache.get(prefix); if (exact != null) return exact.items(); // If "wea" came back complete, every completion of "weat" is in that list already: // the next keystroke is a filter, not a request. for (int n = prefix.length() - 1; n > 0; n--) { Result shorter = cache.get(prefix.substring(0, n)); if (shorter != null && shorter.complete()) return shorter.items().stream().filter(s -> s.startsWith(prefix)).toList(); } return null; }
private synchronized void load(String prefix, long seq) { if (seq != latest) return; // another keystroke came within 50 ms: no request at all inFlight = fetcher.fetch(prefix); inFlight.thenAccept(result -> { synchronized (this) { cache.put(prefix, result); // Answers can arrive out of order; only the newest keystroke is ever painted. if (seq == latest) render.accept(prefix, result.items()); } }); // a failed fetch shows nothing new: autocomplete must never block search }}@dataclass(frozen=True)class Result: items: list[str] complete: bool # the server sent every completion that exists, not just the top 8
# The client side of the latency budget: wait for a short pause in typing, cancel# whatever the user has typed past, never paint an answer for an old prefix, and skip the# network when an earlier answer already holds everything. Runs on one asyncio loop.class SuggestClient: DEBOUNCE = 0.05 # 50 ms merges bursts; 300 ms would spend the whole budget waiting
def __init__(self, fetch: Callable[[str], Awaitable[Result]], render: Callable[[str, list[str]], None]) -> None: self._fetch = fetch self._render = render self._pending: asyncio.Task | None = None self._cache: dict[str, Result] = {} # this session only
def on_input(self, raw: str) -> None: prefix = re.sub(r"\s+", " ", raw.lower()).lstrip() # One task covers the wait and the request: cancelling it stops either one. if self._pending: self._pending.cancel() local = self._from_cache(prefix) if local is not None: self._render(prefix, local) # backspace, or a complete shorter answer return self._pending = asyncio.get_running_loop().create_task(self._load(prefix))
def _from_cache(self, prefix: str) -> list[str] | None: if prefix in self._cache: return self._cache[prefix].items # If "wea" came back complete, every completion of "weat" is in that list already: # the next keystroke is a filter, not a request. for n in range(len(prefix) - 1, 0, -1): shorter = self._cache.get(prefix[:n]) if shorter and shorter.complete: return [s for s in shorter.items if s.startswith(prefix)] return None
async def _load(self, prefix: str) -> None: await asyncio.sleep(self.DEBOUNCE) # a keystroke within 50 ms cancels us here try: result = await self._fetch(prefix) # cancellation closes the HTTP request too except Exception: return # failed: show nothing new. Autocomplete failing must never block search self._cache[prefix] = result # A cancelled task never reaches this line, so an old prefix is never painted. self._render(prefix, result.items)// The client side of the latency budget: wait for a short pause in typing, cancel whatever// the user has typed past, never paint an answer for an old prefix, and skip the network// when an earlier answer already holds everything.record SuggestResult(IReadOnlyList<string> Items, bool Complete); // Complete: every completion that exists
sealed class SuggestClient( Func<string, CancellationToken, Task<SuggestResult>> fetch, Action<string, IReadOnlyList<string>> render){ static readonly TimeSpan Debounce = TimeSpan.FromMilliseconds(50); // 300 ms would spend the budget waiting // Called on the UI thread, and awaits resume there, so these fields need no locks. private readonly Dictionary<string, SuggestResult> _cache = new(); private CancellationTokenSource? _pending;
public async Task OnInputAsync(string raw) { string prefix = Regex.Replace(raw.ToLowerInvariant(), @"\s+", " ").TrimStart(); // One token covers the wait and the request: cancelling it stops either one. _pending?.Cancel();
var local = FromCache(prefix); if (local is not null) { render(prefix, local); // backspace, or a complete shorter answer return; }
var cts = _pending = new CancellationTokenSource(); try { await Task.Delay(Debounce, cts.Token); // a keystroke within 50 ms ends us here var result = await fetch(prefix, cts.Token); // the token aborts the HTTP request _cache[prefix] = result; // Answers can arrive out of order; only the newest prefix is ever painted. if (!cts.IsCancellationRequested) render(prefix, result.Items); } catch (OperationCanceledException) { } catch (HttpRequestException) { } // show nothing new: autocomplete must never block search }
private IReadOnlyList<string>? FromCache(string prefix) { if (_cache.TryGetValue(prefix, out var exact)) return exact.Items; // If "wea" came back complete, every completion of "weat" is in that list already: // the next keystroke is a filter, not a request. for (int n = prefix.Length - 1; n > 0; n--) { if (_cache.TryGetValue(prefix[..n], out var shorter) && shorter.Complete) return shorter.Items.Where(s => s.StartsWith(prefix, StringComparison.Ordinal)).ToList(); } return null; }}// Result is one answer from the server.type Result struct { Items []string Complete bool // the server sent every completion that exists, not just the top 8}
// SuggestClient is the client side of the latency budget: wait for a short pause in typing,// cancel whatever the user has typed past, never paint an answer for an old prefix, and skip// the network when an earlier answer already holds everything.type SuggestClient struct { fetch func(ctx context.Context, prefix string) (Result, error) render func(prefix string, items []string)
mu sync.Mutex cancel context.CancelFunc // one context covers the wait and the request cache map[string]Result // this session only}
func NewSuggestClient(fetch func(context.Context, string) (Result, error), render func(string, []string)) *SuggestClient { return &SuggestClient{fetch: fetch, render: render, cache: map[string]Result{}}}
const debounce = 50 * time.Millisecond // merges bursts; 300 ms would spend the budget waiting
var spaces = regexp.MustCompile(`\s+`)
func (c *SuggestClient) OnInput(raw string) { prefix := strings.TrimLeft(spaces.ReplaceAllString(strings.ToLower(raw), " "), " ") c.mu.Lock() defer c.mu.Unlock() if c.cancel != nil { c.cancel() // stops the previous wait or request, whichever it is in } if items, ok := c.fromCache(prefix); ok { c.render(prefix, items) // backspace, or a complete shorter answer return } ctx, cancel := context.WithCancel(context.Background()) c.cancel = cancel go c.load(ctx, prefix)}
func (c *SuggestClient) fromCache(prefix string) ([]string, bool) { if r, ok := c.cache[prefix]; ok { return r.Items, true } // If "wea" came back complete, every completion of "weat" is in that list already: // the next keystroke is a filter, not a request. for n := len(prefix) - 1; n > 0; n-- { if r, ok := c.cache[prefix[:n]]; ok && r.Complete { var items []string for _, s := range r.Items { if strings.HasPrefix(s, prefix) { items = append(items, s) } } return items, true } } return nil, false}
func (c *SuggestClient) load(ctx context.Context, prefix string) { select { case <-time.After(debounce): case <-ctx.Done(): return // another keystroke came within 50 ms: no request at all } res, err := c.fetch(ctx, prefix) // ctx aborts the HTTP request if the user types on if err != nil { return // failed or cancelled: show nothing new; autocomplete must never block search } c.mu.Lock() defer c.mu.Unlock() c.cache[prefix] = res // Checked under the lock, so a newer keystroke cannot slip in between check and paint. if ctx.Err() == nil { c.render(prefix, res.Items) }}// The browser side of the latency budget: wait for a short pause in typing, cancel whatever// the user has typed past, never paint an answer for an old prefix, and skip the network// when an earlier answer already holds everything.interface Result { items: string[]; complete: boolean; // the server sent every completion that exists, not just the top 8}
type Fetch = (prefix: string, signal: AbortSignal) => Promise<Result>;
class SuggestClient { private static readonly DEBOUNCE_MS = 50; // merges bursts; 300 ms would spend the budget waiting private pending?: AbortController; private readonly cache = new Map<string, Result>(); // this page only; HTTP caching does the rest
constructor( private readonly fetchSuggestions: Fetch, private readonly render: (prefix: string, items: string[]) => void, ) {}
onInput(raw: string): void { const prefix = raw.toLowerCase().replace(/\s+/g, ' ').trimStart(); // One controller covers the wait and the request: aborting it stops either one. this.pending?.abort();
const local = this.fromCache(prefix); if (local) return this.render(prefix, local); // backspace, or a complete shorter answer
const ctrl = (this.pending = new AbortController()); setTimeout(() => void this.load(prefix, ctrl.signal), SuggestClient.DEBOUNCE_MS); }
private fromCache(prefix: string): string[] | undefined { const exact = this.cache.get(prefix); if (exact) return exact.items; // If "wea" came back complete, every completion of "weat" is in that list already: // the next keystroke is a filter, not a request. for (let n = prefix.length - 1; n > 0; n--) { const shorter = this.cache.get(prefix.slice(0, n)); if (shorter?.complete) return shorter.items.filter((s) => s.startsWith(prefix)); } return undefined; }
private async load(prefix: string, signal: AbortSignal): Promise<void> { if (signal.aborted) return; // another keystroke came within 50 ms: no request at all try { const result = await this.fetchSuggestions(prefix, signal); // abort cancels the HTTP request this.cache.set(prefix, result); // Answers can arrive out of order; only the newest prefix is ever painted. if (!signal.aborted) this.render(prefix, result.items); } catch { // Aborted or failed: show nothing new. Autocomplete failing must never block search. } }}Go deeperWhy the complete flag exists, and phones on bad networks1 min
Filtering locally is only safe when the list is known to be whole. A list shorter than 8 proves
nothing, because the blocklist may have removed entries. Only the server knows how many completions
sit below the node, so it says so with complete.
A mobile app can go further. It ships a small built-in list for single letters and the empty box, refreshed daily. So the first keystrokes never need the network. It uses short timeouts, and drops late answers. It keeps a bigger local cache than a browser tab, because people repeat the same searches in an app.
Removing a suggestion in under a minute
Section titled “Removing a suggestion in under a minute”A suggestion pairs a person’s name with a defamatory phrase, and legal wants it gone now. Where does it live?
The suggestion lives in many copies, each built and cached at a different speed. Each needs its own way out:
| Where it lives | How it is removed | Time limit |
|---|---|---|
| Server answers | The blocklist check on every response | Under 1 minute |
| CDN edge | Purge every cached short prefix of the phrase | About 1 minute |
| Browsers | Can’t be purged; limited by max-age=300 |
5 minutes |
| Trending overlay | The stream job checks the blocklist before writing | Next minute |
| The daily trie | The next build leaves it out | Next build |
Three details make this hold up. Servers store 15 and show 8, so the list stays full after removals. Single words can be blocked, not just exact queries, because people type endless variants. And if the blocklist store is down, an entry can be pushed to every server as a configuration change.
Go deeperA legal removal, end to end1 min
- Color key
- Background worker
- Cache
- Service
- Database
Build-time filters, like personal-data patterns and the 50-person rule, are the first line. But they can’t meet a one-minute promise, and they never see the trending path. “Eventually consistent” without a time limit isn’t a promise anyone can test. Ranking may be a day old. Removal has a legal clock, so it gets its own fast path.
Thirty languages: splitting the trie
Section titled “Thirty languages: splitting the trie”We launch thirty languages, and traffic grows ten times. Does every server still hold everything?
More traffic alone is easy: every server has a full copy, so we add servers. The limit is the size of that copy. English worldwide, with three times the candidates, passes 100 GB. That’s too much memory per server, and too slow to load on every deploy.
The first split is free: the market. Markets share nothing, so each one’s trie loads only on its own servers. Within a market too big for one machine, we split by prefix range:
| Split by | One shard per request? | Problem |
|---|---|---|
| Prefix range | Yes | The range holding “s” and “a” is hot |
| Hash of the prefix | Yes, but the trie breaks apart | One row per prefix, about 13 times the memory |
| Hash of the query | No: ask every shard and merge | Every keystroke waits for the slowest shard |
Ranges aren’t one per letter. The builder picks boundaries from subtree sizes and traffic. So “s”
might split into s to sh and si to sz, while x, y and z share one range. A prefix
router reads the q parameter, and forwards each request to the group that owns it. The builder
computes every top 15 on the whole trie before cutting it, so each shard’s lists are still right.
Stage 5: Shard by prefix range
Stage 5 of 6
Shard by prefix range
Why this stage
A requirement, not request load: thirty languages and a larger candidate set push the biggest market’s trie past 100 GB, so one server can no longer hold a full copy.
What we add
Each market’s trie is cut into prefix ranges balanced by size and traffic.
A prefix router sends each request to the replica group that owns its range.
What it costs
A routing hop, and the ranges holding the most common first letters take far more traffic than the rest.
At 210k suggestion requests per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
Now drag the slider to 2.1 million requests a second. The group holding the most common first letters takes 15% of all traffic, and turns red. The next stress test fixes that.
Go deeperKeeping the range map safe1 min
Ranges are over prefixes in sorted order. The completions of “s” itself span both of its ranges. So “s” belongs to the range that starts with it, and that range still holds the full answer for “s”.
The range map changes only on a deliberate rebalance, never on a daily build. A router and a shard that disagree about a boundary would send prefixes to the wrong place. A rebalance loads the new range on a fresh group, switches the router entry, then retires the old group. The router adds about 1 ms, and holds only a few hundred entries.
The hot prefix
Section titled “The hot prefix”One shard group holds “s”, and it is melting. Do we add more replicas?
More replicas would work, but each is a full copy of a large range, paid for to serve a few dozen keys. Look at those keys instead. Prefixes of one or two characters are about a quarter of all requests. There are fewer than 2,000 of them per market. Their answers are the same for everyone, and change slowly. They are the most cacheable responses in the system.
So short prefixes are cached at the CDN and in the browser for 5 minutes. The router also keeps their answers in memory, a few MB, so even a CDN outage never sends a single letter to a shard.
Stage 6: Short prefixes at the edge
Stage 6 of 6
Short prefixes at the edge
Why this stage
At 10× (2.1 million requests/s), the replica group that owns the most popular first letters is at 300%.
Prefixes of one or two characters are a quarter of all requests but only a few thousand keys.
What we add
Answers for prefixes of up to two characters are cached at the CDN and in the browser, and the prefix router keeps those few thousand answers in memory too.
Every region runs the serving tier from the same snapshots.
What it costs
Removals must also purge the CDN, and a browser can show a removed suggestion for up to its 5 minute max-age.
At 210k suggestion requests per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
Trace a request: Short and long prefixes at the edge
Short and long prefixes at the edge: step 1 of 4
Users to CDN edge
The user types "s". Prefixes of one or two characters are the same for everyone in a market, so the CDN edge 8 ms away answers from cache: about 16 ms round trip, and that request ends here. The next request, "spa", is longer than two characters and passes through.
- Users → CDN edge16 ms
- CDN edge → Prefix router40 ms
- Prefix router → Suggest shards1 ms
- Response
Browsers and the CDN now answer about 40% of requests before they reach a region. The busiest group falls from 15% of traffic to about 3%. The cost: trending news reaches “e” up to 5 minutes later than “earthq”, and a removed suggestion can linger in one browser for 5 minutes.
Go deeperPersonalization and new languages2 min
| Option | How it works | Cost |
|---|---|---|
| Blend on the device | The device keeps recent searches and puts matches on top | Free for servers, private, keeps caching |
| Tries per area | Separate snapshots per market and region | More memory, still cacheable |
| Rerank on the server | Read the user’s history, then reorder the 15 stored answers | 1 to 2 ms more; breaks CDN caching for signed-in users |
| A trie per user | Each user gets their own | Far more memory than the whole system; never |
We start with the device and per-area tries. We add a server rerank only for signed-in users, on prefixes longer than two characters. That keeps the edge cache for everyone else.
Languages change more than the data. Each market has its own normalizer. French folds accents, so “cafe” matches “café”. Japanese users type kana that the keyboard turns into kanji. So the client waits until that finishes, and the trie indexes readings as well as written forms.
When things break
Section titled “When things break”The batch job has been producing garbage for a day and nobody noticed. What protects you?
Whether you name checks before publishing, canaries and one-step rollback.
Nothing on the request path talks to a database or a pipeline. So every pipeline failure makes suggestions staler, never missing. If the batch job fails, servers keep yesterday’s trie. If the stream job fails, news waits for the next build. If the blocklist store is down, servers keep their last copy.
The real risk is a bad build: a scoring bug, or a filter that silently let personal data through. That’s why builds are checked against a fixed set of prefixes, and tried on canaries. They roll out in waves, with the previous version one pointer flip away. And we watch how often people pick a suggestion, per market. A bad build shows up there within an hour, even if every check passed.
Click any box to break it and see what users would notice:
Break it: what fails, who notices, what users see
Failure: click any box to break it
Snapshots (a bad build) goes down
What breaks
The store itself rarely fails; the real risk is a build that publishes a broken or polluted trie.
How we notice
Validation before publish: size within 10% of yesterday, a golden set of prefixes, and an offensive-term scan.
Canary servers compare answers with the old version.
What users see
Nothing, if validation catches it.
Otherwise odd suggestions until rollback, minutes at most.
What we do
Servers keep the previous version in memory or on disk, and a version pointer rolls the fleet back.
If the store is down, servers keep serving what they have.
Every region runs its own serving tier, with snapshots copied to it, while the pipeline runs in one place. Suggestions never cross an ocean. If a region fails, DNS sends users to the next one, and the search box works without suggestions for about a minute. Under overload, shed personalization first, then the trending merge. The plain trie lookup goes last.
Go deeperEvery failure, and what users see2 min
| Part | Failure | What users see | What we do |
|---|---|---|---|
| Suggest server | Crash | A few keystrokes without suggestions | 3 or more copies per range; a new one loads fast |
| Router or region | Down | No suggestions for a minute; search works | Stateless routers; DNS to the next region |
| Snapshots | A bad build | Odd suggestions, if checks miss it | Waves; roll back to the last version |
| Batch builder | Fails | Suggestions a day staler | Rerun from the 7-day log; keep the last good one |
| Trend worker | Fails | News waits for the next build | Restart; overlays expire after 30 minutes |
| Blocklist store | Down | Nothing; new removals wait | Servers keep their copy; emergency config push |
| CDN edge | Down | First keystrokes 20 to 40 ms slower | The router serves short prefixes from memory |
Go deeperRunning it: alerts1 min
Wake someone up when:
- in-browser timing shows 95% of suggestions taking more than 150 ms from request to screen, for 15 minutes in any market
- server p99 passes 10 ms
- the snapshot is more than 36 hours old
- the trending overlay is more than 5 minutes old
- any server’s blocklist is more than a minute old
A removal that silently stopped spreading is a legal incident.
Abuse. Scrapers harvest what people search, so limit requests per address and session. Manipulation targets the trending path.
Wrap up
Section titled “Wrap up”The whole design
Section titled “The whole design”Here is everything we built, in the order we built it. Use the buttons to step through it.
The full design, stage by stage
Stage 6 of 6
Short prefixes at the edge
Why this stage
At 10× (2.1 million requests/s), the replica group that owns the most popular first letters is at 300%.
Prefixes of one or two characters are a quarter of all requests but only a few thousand keys.
What we add
Answers for prefixes of up to two characters are cached at the CDN and in the browser, and the prefix router keeps those few thousand answers in memory too.
Every region runs the serving tier from the same snapshots.
What it costs
Removals must also purge the CDN, and a browser can show a removed suggestion for up to its 5 minute max-age.
At 210k suggestion requests per second, every part has headroom. Raise the traffic until something turns red.
The numbers behind the busy bars
What one machine can do
- One suggest server handles about 20,000 requests a second. HTTP handling is the cost; the lookup takes microseconds.
- Postgres handles about 2,000 prefix queries a second and 5,000 count updates.
- A key-value cluster for the prefix table serves about 120,000 reads a second at a low tail latency.
- Kafka takes about 1 million events a second.
The hot replica group
- From stage 5, the suggest box shows the busiest replica group: 5 replicas, 100,000 requests a second.
- It takes 15% of all traffic until short prefixes move to the edge, then about 3%.
Logging
- About one search is logged for every 6 suggestion requests.
The decisions, and what each one costs
Section titled “The decisions, and what each one costs”| Decision | We chose | We gave up | We’d choose differently if |
|---|---|---|---|
| Data structure | Radix trie, top 15 at every node | Smaller structures; live updates | Memory dominated the bill (FST) |
| Where it lives | In memory on every server, from snapshots | Instant updates; small servers | The budget allowed a network hop (key-value table) |
| Freshness | Daily batch plus trending overlay | Fully live rankings | The product were news search |
| Ranking | Decayed counts of different people | Raw popularity | Completing a catalog (sales, ratings) |
| Removal | Blocklist on every response, CDN purge | Longer browser caching | No legal removals ever applied |
| Splitting | Market, then prefix range | An even hash spread | Prefixes were a flat key-value table |
| Hot prefixes | CDN, browser and router for 1 to 2 characters | Trending freshness on single letters | Every user saw a personal list |
How to spend 45 minutes
Section titled “How to spend 45 minutes”- 0 to 4. Volume, speed and freshness. Name privacy and removal as promises.
- 4 to 9. 210,000 requests a second because keystrokes multiply searches, a 10 ms budget, 35 GB of trie.
- 9 to 20. Build it: why not a database, offline counting, top k at every node, snapshots in memory, overlay and blocklist. A mid-level answer can stop here.
- 20 to 32. The stress tests: trending, then the client, then removals, as the interviewer leads.
- 32 to 40. Splitting by prefix range, then the hot prefix at the edge.
- 40 to 45. A bad build, then your own questions.
Never skip the latency budget, the top k at every node, or how a removal reaches every cache.
Follow-up questions
Section titled “Follow-up questions”Interviewer asksHow would you support fuzzy matching, so 'wether' suggests 'weather'?
As a fallback, not on the main path. When the exact prefix returns few results, look up a table of common misspellings mined from the logs. These are people who typed “wether” and then picked “weather”. It’s cheap, and catches most real errors.
Interviewer asksWhat do you return for an empty search box?
The user’s recent searches from the device. Then the market’s top or trending queries, which is one response cached at the CDN, like a short prefix. It’s often the most viewed list of all, so it gets its own quality review.
Go deeperMore follow-up questions1 min
The candidate set grows to 5 billion queries. What changes? First shrink the bytes: a transducer layout, smaller scores, lists only where needed. Then split into more ranges. Also ask whether 5 billion is the goal: most are almost never shown, and a higher threshold may lose nothing users notice.
A new suggest server starts. How long until it serves? It downloads its ranges of the current snapshot, tens of GB, in under a minute inside the region. It maps the file into memory and passes a check on a fixed set of prefixes. Until then the router sends it nothing. Mapping the file lets it serve before every page is read in, at a slightly slower tail.
A trending query is a hoax. How do you stop it spreading? Block it like any removal, and it leaves responses within a minute. Then fix the cause. Trending entries about people and events go to a review queue, with a cap on how high an unreviewed one can rank on short prefixes.
Further reading
Section titled “Further reading”- Caching, CDNs, partitioning and probabilistic structures on this site, and the top-k problem, which shares the counting pipeline.
- How Google autocomplete works in Search, Google: where predictions come from, why they are not just popularity, and the removal policies.
- Using Finite State Transducers in Lucene, Mike McCandless: the compact structure behind Lucene’s suggesters, and the upgrade path from a trie.
The designbeyondcode digest, every Saturday
New deep dives, interview tips and site news in one short email. Free. Leave with one click.
We never sell or share your email. We only use it to send this newsletter.