Appearance
11.11 — Search Autocomplete
Someone types l, then o, then n, then d. Four keystrokes, roughly 400 milliseconds apart, and after each one a list of suggestions has to be on screen before the next letter lands. If it takes 300 milliseconds the suggestions are always one letter behind, which is worse than showing nothing at all, because the user watches a list flicker into the answer to a question they have already stopped asking.
That is the whole constraint. Every keystroke is a request, the end-to-end budget is 100 milliseconds at the 99th percentile, and about 40 of those milliseconds are spent on the network before your code runs. Thirty milliseconds of server time is not enough to search anything. It is only enough to look something up.
So this is the purest study of precomputation in the book: the answer has to already exist before the question is asked.
1. Requirements
Functional. Given a prefix, return the top five to ten completions ranked by popularity. Include the user's own recent searches. Tolerate common typos. Surface trending terms within minutes of them trending.
Non-functional, with numbers.
- p99 under 100 ms end to end, including the network.
- Roughly ten times the request volume of actual searches, because a twenty-character query can produce many prefix requests.
- Suggestions may be minutes stale. This is the admission that makes the whole design possible, and it should be extracted explicitly rather than assumed.
Out of scope today: the search itself (11.12), meaning-based suggestions (11.22), and spelling correction of the final submitted query.
The clarifying questions, and what each answer changes
"How stale may a suggestion be?" If the answer is "instantly current", precomputation is impossible and there is no design that meets the latency budget. Minutes of staleness buys everything. Ask it first.
"Are suggestions personal, or the same for everyone?" A response that differs per user cannot be cached, and losing cacheability at 3,000 requests a second changes the cost model completely. Section 6.4 shows how to get the personalisation users actually notice without giving up a shared cache.
"How many distinct things can be suggested?" Ten million search phrases and fifty million product names are different problems. The first fits in memory as one structure; the second needs sharding and, more importantly, needs suggestions filtered for validity because a product can go out of stock.
"Is this a publishing surface?" It is, and asking makes that explicit early. Whatever the system displays is attributed to the company, so moderation is a requirement rather than a later feature — section 6.6 and the staff question both turn on this.
"What should happen when the service is slow?" The right answer is "show nothing and let the user keep typing", and getting that agreed in the requirements phase is what licenses the aggressive timeouts in section 8.
2. Estimation
Request volume. 10 million searches a day, and with client-side debouncing roughly five prefix requests per search = 50 million autocomplete requests a day ≈ 600 a second average, ~3,000 at peak. What that forces: modest volume, which is a relief, because none of the difficulty here is throughput. Note also what debouncing is worth: without it, a twenty-character query is twenty requests instead of five, so the client-side behaviour in section 6.7 is a four-fold reduction in traffic before any server work is done.
The latency budget, which is the only number that matters. 100 ms total, minus roughly 40 ms of network round trip on a typical connection, minus a few milliseconds of client rendering, leaves about 30 ms of server time — and that is a p99, so the typical case must be far under it. What that forces: no database query, no ranking at request time, no sorting, no scoring. Thirty milliseconds at p99 with 3,000 requests a second means the request path must be a single memory lookup with no allocation of consequence. Everything else in this design follows from that sentence.
Vocabulary and memory. About 10 million distinct phrases worth suggesting. If you materialised the top ten completions for every prefix of every phrase — 10M phrases × ~20 prefixes each × 10 suggestions × ~30 bytes — that is roughly 60 GB. What that forces: too large for one node's memory as a flat table, and a strong argument for a structure that shares prefixes rather than repeating them. A trie storing the vocabulary once and hanging a small list off each node is dramatically smaller, and what remains can be sharded by first letter.
Build cost. Rebuilding that structure from a day of query logs is a batch job over tens of millions of rows, running in minutes to an hour. What that forces: a rebuild cadence measured in hours, which is exactly why section 6.3's fast-moving overlay exists — a trending term cannot wait for the next full build.
The head of the distribution. Query prefixes follow a steep power law: single characters and two-character prefixes account for a large share of all requests, and there are only a few thousand of them. What that forces: the cheapest possible optimisation. Cache the top few thousand prefixes at the edge with a short lifetime and most of the traffic never reaches your servers at all.
3. API
http
GET /suggest?q=lond&limit=10&lang=en®ion=GB
→ 200 OK
Cache-Control: public, max-age=60
{ "prefix": "lond",
"suggestions": [
{ "text": "london weather", "score": 0.94, "type": "query" },
{ "text": "london underground", "score": 0.81, "type": "query" },
{ "text": "london zoo", "score": 0.55, "type": "trending" } ],
"snapshotVersion": "2026-07-31T06:00Z" }One endpoint, and it is deliberately boring: no request body, no authentication on the common path, no user identifier in the query string. Every one of those absences is what makes the response cacheable, and cacheability is what lets the edge absorb the head of the distribution.
type is on every suggestion, because a client must be able to render a trending item, a personal item and a sponsored item differently. Section 8's drill shows why the sponsored case makes this a contractual requirement rather than a nicety.
snapshotVersion is there for debugging, and it earns its place the first time somebody reports a suggestion that "should have disappeared" — you immediately know whether they were served a stale snapshot or whether the build is wrong.
Half of this design lives in the client, and it is worth writing down as part of the contract:
Debounce, waiting 50 to 100 milliseconds after the last keystroke before sending. This collapses a burst of typing into one request and cuts traffic by more than half.
Cancel in-flight requests when a new keystroke arrives (3.6.8). The response to lon is worthless once the user has typed lond, and leaving it running wastes a connection.
Discard out-of-order responses. If lon was requested first and lond second, but lon's response arrives last, a naive client overwrites the correct list with the stale one. This is a real bug that ships regularly, and it looks to the user like the suggestions are randomly going backwards. The fix is to tag each request with its prefix and ignore any response whose prefix is not the current input.
4. Data structure
ts
type TrieNode = {
children: Map<string, TrieNode>;
top: Suggestion[]; // (1) precomputed, sorted, ready to return
};
function suggest(prefix: string, root: TrieNode): Suggestion[] {
let node = root;
for (const ch of prefix) { // (2)
const next = node.children.get(ch);
if (!next) return []; // (3)
node = next;
}
return node.top; // (4)
}(1) the entire point of the design is this field. The list is not computed, filtered or sorted at request time; it was written into the node hours ago and is returned as-is. (2) one map lookup per character of the prefix. A four-character prefix is four hops, which is a few hundred nanoseconds. (3) an unknown prefix returns nothing, instantly. There is no fallback search, because a fallback search is exactly the unbounded work the budget forbids. (4) no allocation, no copy, no ranking. The response is serialised straight from a structure that already existed.
The build is the mirror image of the serve. An offline job aggregates the query logs over a window, scores each term, inserts every term into a trie, and then propagates the top-k lists upward from the leaves: each node merges its children's lists and keeps the best ten. Because each node only ever merges a handful of ten-item lists, the whole propagation is linear in the size of the trie rather than quadratic. The result is serialised into an immutable file that serving nodes load into memory.
5. Architecture
Serving nodes are stateless and identical. Each holds a snapshot in memory and answers from it. There is no shared state between them, no database connection on the request path, and nothing to coordinate — so scaling is adding copies, and losing a node costs nothing.
Snapshots are immutable and swapped atomically. A node loads the new trie into memory alongside the old one, verifies it, then flips a single pointer. Requests in flight finish against the old structure and new requests use the new one. There is no lock on the read path, no rebuild pause, and rollback is flipping the pointer back — which is the fastest incident response available anywhere in this book.
Sharding by first character is available when memory demands it, with a router sending q=lon to the shard that owns l. The load across letters is very uneven, so rare letters are grouped together and common ones may be split further — this is a per-letter capacity decision, not an even split.
6. Deep dives
6.1 The build pipeline, and what it computes
The offline job does four things, and the third is the one that makes the design work.
Aggregate. Count occurrences of each completed query over a window, weighted so that recent days count more than old ones. Weighting by recency is what stops a term that was enormous two years ago from permanently occupying a slot.
Score. Frequency is the base, but the strongest signal is click-through on the suggestion itself. A phrase that gets shown constantly and clicked rarely is a bad suggestion no matter how often people type it, and demoting it is something only impression data can tell you.
Propagate. Insert every term into the trie, then walk from the leaves upward, and at each node merge the children's top-k lists and keep the best ten. Because every merge is over small fixed-size lists, the total work is proportional to the number of nodes.
Serialise and verify. Write the structure to an immutable file, then run a canary: query a fixed panel of prefixes against the new snapshot and compare with the previous one. A snapshot whose results move wildly, or that violates policy on a sensitive prefix, is blocked from promotion. Section 8 explains why this check is not optional.
6.2 Why this cannot be a database query
The temptation is SELECT term FROM queries WHERE term LIKE 'lond%' ORDER BY score DESC LIMIT 10, and it is worth being precise about why it fails rather than just asserting that it does.
The work grows as the prefix shrinks. For lond% an index range scan touches a manageable number of rows. For l% it touches a large fraction of the entire vocabulary — millions of rows — and then has to sort them by score before taking ten. And short prefixes are the most common requests, because everybody types the first letter and only some people get to the fourth.
Caching does not rescue it, because the variety of prefixes is high and the long tail of prefixes is exactly the part a cache cannot hold.
The tail is unpredictable, which is the real killer at p99. Even a well-tuned index will occasionally hit a slow path, and this endpoint runs at 3,000 requests a second with a 30 ms budget where p99 is the number being graded.
The general lesson worth extracting: when the latency budget is smaller than the computation, the only remaining move is to have done the computation already. Every "how is this so fast?" system in this Part is an instance of that same answer.
6.3 Getting trends in within minutes
The base trie rebuilds every few hours, which is fine for the stable vocabulary and useless for something that started happening at 14:02.
The answer is a second, tiny, fast-moving structure merged at query time. It is built from a short sliding window over the live query stream (10.8.1), refreshed every minute or two, and it holds thousands of terms rather than millions — small enough to distribute to every serving node constantly.
The signal is rate of change, not volume. If the overlay ranked by raw volume it would simply repeat the head of the distribution the base trie already covers. What makes a term trending is that its rate is far above its own historical baseline, and computing that requires keeping the baseline as well as the current window.
Three details that make it work rather than merely sound right. It needs a minimum distinct-user threshold, or a handful of automated queries can manufacture a trend. It needs the same moderation path as the base, because trending content is exactly where harmful suggestions appear fastest and with the least review. And the merge must be a bounded list union with a comparison, not a re-ranking pass, because the 30 ms budget applies to the merged path too.
The pattern has a name worth recognising: a slow complete base plus a fast small delta. It recurs throughout this Part — a materialised view with a recent-changes overlay, a batch-computed model with online features in 11.20 — and it is the general answer whenever full recomputation is too slow to be fresh but freshness only matters for a small, identifiable subset.
6.4 Personalisation without losing the cache
A response that differs per user cannot be shared, and losing sharing here is expensive: the edge cache stops working, the hit ratio collapses, and every request reaches a serving node.
The resolution is to merge on the client. The global suggestions come from the shared, highly cacheable service. The user's own recent searches are stored on their device and merged into the displayed list locally. This costs nothing on the server, exposes nothing about the user to anyone, and delivers the personalisation people actually notice — seeing their own past searches — with no server involvement at all.
If server-side personalisation is genuinely needed — cross-device history, or suggestions informed by account state — it is a small per-user overlay fetched once per session, not per keystroke. The per-keystroke version is what destroys both the latency and the cost model, and it is the version people reach for first.
6.5 Typos, assessed honestly
Full approximate matching over a trie — finding every term within one or two edits of the prefix — is expensive, and it is expensive in exactly the wrong place, at the top of the funnel with a 30 ms budget.
The practical approach is to index common misspellings as terms in their own right. The logs already contain the evidence: sessions where a user typed X, got nothing useful, and immediately typed Y. Those pairs give you the misspellings people actually make, and adding them to the trie as terms pointing at the correct completion handles the frequent cases with a plain lookup and no algorithmic cost at all.
Save real fuzzy matching for the search step (11.12), where the budget is 300 milliseconds rather than 30 and where getting it wrong costs a worse result page rather than a laggy text box.
6.6 Suggestions are a publishing surface
Ranking here is not neutral. The system chooses what to display, and what it displays is attributed to the company and shapes what people search next.
That makes three things requirements rather than features. A blocklist applied at serve time, so a term can be suppressed in seconds without rebuilding anything. Minimum distinct-user thresholds, so a term must be searched by many different people rather than many times by a few — which is the cheapest and most effective defence against manipulation. And a manual override path with an audit trail, because some suppressions are judgement calls that someone must own.
Treating autocomplete as a pure popularity function has produced real and well-documented harm. The honest design names moderation as a requirement in section 1 rather than discovering it in an incident.
6.7 The client is half the system
Three rules, and each one prevents a specific failure.
Debounce, 50 to 100 milliseconds. Without it, a fast typist generates a request per character; with it, a burst of typing produces one. This is a four-fold traffic reduction that costs three lines of code.
Cancel in-flight requests on a new keystroke. The answer to lon is worthless once lond has been typed, and an uncancelled request holds a connection and may still arrive.
Discard out-of-order responses. If the response to lon arrives after the response to lond, a naive client overwrites the correct list with the stale one, and to the user the suggestions appear to go backwards at random. Tag each request with its prefix, compare against the current input on arrival, and drop anything that no longer matches.
7. Decision Ledger
| Decision | Alternatives | Why this | What it costs |
|---|---|---|---|
| Trie with top-k stored at every node | subtree traversal; LIKE 'p%' on a database | one hop per character, microseconds, nothing computed at request time | memory duplication up every path; a rebuild cycle; minutes of staleness |
| Immutable snapshots swapped atomically | mutate the structure in place | no locking on the read path; rollback is a pointer flip | a full rebuild per cycle, and two copies briefly in memory |
| Base trie plus a fast overlay | one rebuild cadence | trends appear in minutes without rebuilding 60 GB | merge logic on the request path; two structures to reason about |
| Merge personal history on the client | personalise on the server | the shared response stays cacheable, and nothing personal leaves the device | no cross-device history without an explicit sync feature |
| Misspellings indexed as terms | approximate matching over the trie | handles the common cases inside the budget with a plain lookup | never catches a novel typo; needs log-derived pairs |
| Debounce, cancel and order-check in the client | fetch naively per keystroke | more than halves traffic; removes flicker and stale overwrites | client complexity that must exist in every client |
| Show nothing on failure | retry, or show a stale list | a 50 ms timeout with silence beats a correct answer at 400 ms | the feature disappears rather than degrading visibly |
| Edge-cache the hot prefixes | serve everything from origin | the steep head of the distribution never reaches your servers | up to 60 seconds of extra staleness on the most-seen suggestions |
8. Scale and failure
Failure here is cheap, and the design should exploit that. Autocomplete is an enhancement. If it fails, the correct behaviour is to show nothing and let the user carry on typing — which means a hard client-side timeout of about 50 milliseconds with silent failure gives a better experience than a correct answer at 400 milliseconds. That makes this service an unusually good candidate for aggressive load shedding: under pressure, reject immediately rather than queueing (10.9).
At 10×, shard the trie by prefix, push the top thousand prefixes to the edge with a 60-second lifetime, and consider shipping a small static structure for the first one or two characters inside the client application. A request that never leaves the device is the fastest possible request, and the first two characters are the largest share of the traffic.
| What breaks | Blast radius | How you find out | What keeps it running | Recovery |
|---|---|---|---|---|
| Bad snapshot promoted | everyone, immediately | canary comparison before promotion; suggestion click-through drop | the canary blocks promotion; versioned snapshots | flip the pointer back — seconds, not a deploy |
| Log pipeline broken | suggestions freeze, silently | snapshot age alarm | stale suggestions are wrong-ish, not broken | fix the pipeline; the next build catches up |
| Overlay pipeline stalled | trends stop appearing | overlay age | the base trie still answers everything | restart; the window refills in minutes |
| Hot prefix floods | one shard | requests per prefix | edge cache absorbs the head almost entirely | none needed if the cache is in place |
| Serving node dies | nothing — it holds no state | node count | stateless identical replicas | replace it; it loads the current snapshot |
| Manipulated term surfaces | reputation, publicly | distinct-user ratio; a spike with low user diversity | distinct-user threshold; serve-time blocklist | suppress in seconds, then purge edge caches |
| Service slow or down | the feature disappears | client-side timeout rate | client shows nothing and the user types on | shed load; do not queue |
The row that deserves its own sentence is the bad snapshot. It is the only failure here that is instantly visible to every user, and the mitigation is not a rollback procedure but a gate: a canary that queries a fixed panel of prefixes against the new snapshot, compares the results with the previous one, and refuses to promote anything that moves too far or that violates policy on a sensitive prefix. That gate costs a few seconds per build and it is the difference between a bad build being a non-event and a bad build being the news.
And the one that is invisible: a broken log pipeline produces no errors at all. Suggestions simply stop changing, which nobody notices for days. Alarm on the age of the current snapshot, because it is the only signal that distinguishes "working" from "frozen" (10.10).
What the interviewer will push on
"Why not just query the database with a LIKE prefix match?" They want the mechanism, not the assertion. The work grows as the prefix gets shorter, and short prefixes are the most common requests — l% touches a large fraction of the vocabulary and then has to sort it. Add that caching cannot rescue it because prefix variety is high, and that the p99 tail is what is being graded. The tell is naming that the cheap case and the common case are opposites here.
"What exactly is stored at each trie node, and who computes it?" The node's own top-k list, computed offline by propagating merged lists from the leaves upward, where each node merges its children's small lists and keeps the best ten. The follow-up that separates understanding from recall is why that propagation is affordable: every merge is over fixed-size lists, so the whole pass is linear in the number of nodes rather than quadratic in the vocabulary.
"A term starts trending at 14:02. When does it appear?" Within a minute or two, from a separate small overlay merged at query time — not from the base trie, which rebuilds on a scale of hours. Then volunteer the two details: the signal must be rate of change relative to a baseline, or the overlay just repeats the popular head, and it needs a distinct-user threshold or it becomes trivially manipulable.
"Add personalisation." The trap is to say "include the user identifier in the request", which makes every response unique and destroys the cache. The strong answer keeps the global response shared and merges the user's own history on the device, which costs nothing, exposes nothing, and delivers the personalisation people actually perceive. Server-side personalisation, if truly needed, is a per-session overlay rather than a per-keystroke one.
"Your service is having a bad day and p99 is 400 ms. What should the user see?" Nothing. A 50-millisecond client timeout with silent failure beats a correct answer that arrives after the user has moved on. Getting this agreed in the requirements is what licenses shedding load aggressively rather than queueing — and a candidate who proposes a retry here has not understood that the value of a late suggestion is negative.
"An offensive suggestion is showing for a common prefix and it is in the news. What do you do in the first sixty seconds?" Suppress it at serve time through a blocklist that does not require a rebuild, then purge the edge caches — because a suppressed term still visible at the edge for ten minutes is, publicly, not suppressed. Only then investigate whether it was organic, manipulated, or a scoring bug, because those three have different fixes and the distinction is visible in the distinct-user counts.
Volunteer this, because nobody asks: autocomplete is not a mirror, it is a publisher. The system chooses what to show, that choice is attributed to the company, and it changes what people search next. So "the algorithm just reflects what people search" is both technically wrong — ranking is a choice, the thresholds are choices, the corpus is a choice — and indefensible in public. What follows is concrete: a serve-time suppression mechanism that works in seconds, an audit trail with owners and reasons, an appeals path for false positives, and a named owner for suggestion policy who is not the same person optimising click-through, because those two objectives conflict and an unowned conflict always resolves in favour of the metric that has a dashboard.
Next: 11.12 — the suggestions have to point at something. The next study builds the index behind them: fetching billions of pages politely, storing them once, and answering an arbitrary query in a few hundred milliseconds.
Recall
- Every keystroke is a request, so after ~40 ms of network the server has ~30 ms at p99. That forbids querying, sorting or ranking at request time — the answer must be a single memory lookup.
- The structure: a trie where every node stores its own top-k, computed offline by propagating merged lists from leaves to root. Each merge is over fixed-size lists, so the pass is linear in nodes.
- Why not
LIKE 'p%': the work grows as the prefix shortens, and short prefixes are the most common request. Caching cannot help because prefix variety is high, and the p99 tail is what is graded. - Immutable versioned snapshots, swapped by a pointer flip. No locks on the read path, rollback in seconds, and a canary over a fixed prefix panel gates promotion.
- Slow base plus fast delta: the full trie rebuilds in hours; a tiny trending overlay rebuilds in minutes and is merged at query time. The trending signal is rate of change against a baseline, never raw volume, and it needs a distinct-user threshold.
- Personalisation merges on the client from device-local history — the shared response stays cacheable and nothing personal leaves the device. Server-side personalisation is per-session, never per keystroke.
- Typos: index the misspellings people actually make, learned from logs. Save real fuzzy matching for search, where the budget is ten times larger.
- Client rules: debounce 50–100 ms, cancel in-flight requests, discard out-of-order responses (otherwise suggestions visibly go backwards).
- Failure = show nothing. A 50 ms timeout with silence beats a correct answer at 400 ms, which licenses shedding rather than queueing. Alarm on snapshot age, because a frozen pipeline produces no errors at all.
- Suggestions are a publishing surface: serve-time blocklist, distinct-user thresholds, audit trail, and an owner who is not optimising click-through.
Self-test: Why can this not be a database query? What is stored at each node and how is it built? How does a term trending at 14:02 appear by 14:05? Where does personalisation happen and why there? What are the three client rules, and what does each one prevent?
Quiz Bank
FoundationalWhy can't autocomplete be a database query, and what replaces it?
The budget forbids it. A 100 ms end-to-end p99, minus roughly 40 ms of network round trip and a few milliseconds of rendering, leaves about 30 ms of server time, and that is the 99th percentile rather than the average.
Now consider what the query would have to do. SELECT term FROM queries WHERE term LIKE 'lond%' ORDER BY score DESC LIMIT 10 needs an index range scan whose size grows as the prefix gets shorter. For lond% that might be thousands of rows. For l% it is a large fraction of the entire vocabulary — millions of rows — which then have to be sorted by score before ten are taken. And short prefixes are not the rare case, they are the most common case: everybody types the first letter, and only some of those people reach the fourth.
Caching does not rescue it. The variety of distinct prefixes is high, and the long tail of prefixes is exactly the part a cache cannot hold — so the cache absorbs the head, which was already cheap, and the misses are the expensive ones.
And the tail is unpredictable, which is fatal when p99 is the number being graded. Even a well-tuned index occasionally takes a slow path, and this endpoint runs at 3,000 requests a second.
What replaces it is precomputation. A trie stores the vocabulary with shared prefixes, and — the essential move — each node caches its own top-k completions, computed offline by merging children's lists from the leaves upward. Serving then walks one pointer per character and returns a list that already exists: no scan, no sort, no scoring, no allocation of consequence. The work is measured in microseconds and the p99 is dominated by the network rather than by anything you control.
The trade, stated rather than hidden: read speed is bought with build cost (a full rebuild every few hours), memory (top-k lists repeated up every path), and staleness (minutes). All three were agreed in the requirements, which is why "suggestions may be minutes stale" is not a throwaway line but the assumption the entire design rests on.
The generalisable lesson: when the latency budget is smaller than the computation, the only remaining move is to have computed it already. Every "how is this so fast?" system in this Part is an instance of the same answer.
InterviewHow do trending terms appear in suggestions within minutes if the trie rebuilds every few hours?
With a second structure, small and fast-moving, merged at query time.
The base trie is a large immutable snapshot rebuilt on a slow cadence. That is correct for the stable vocabulary: most suggestions do not change from hour to hour, and rebuilding sixty gigabytes every few minutes would be both expensive and pointless.
Alongside it runs a trending overlay, computed from a short sliding window over the live query stream (10.8.1). It holds thousands of terms rather than millions, is rebuilt every minute or two, and is cheap enough to push to every serving node continuously. At query time the server looks the prefix up in both structures and merges, applying a boost so that a genuinely breaking term can outrank a historically popular one.
The signal has to be rate of change, not volume. If the overlay ranked by raw counts it would simply reproduce the head of the distribution that the base trie already covers, and nothing would ever appear to trend. What makes a term trending is that its current rate is far above its own historical baseline, which means the pipeline has to carry that baseline as well as the current window.
Three details that make it work rather than merely sound plausible. It needs a minimum distinct-user threshold, or a small number of automated or coordinated queries can manufacture a trend — volume alone is precisely the wrong signal for the same reason it is the wrong ranking key. It needs the same moderation path as the base index, because trending content is where harmful suggestions surface fastest and with the least human review. And the merge must be a bounded list union with a comparison, not a re-ranking pass, because the 30 ms budget applies to the merged path just as much as to the base path.
The pattern worth naming: a slow complete base plus a fast small delta. It appears repeatedly in this Part — a materialised view with a recent-changes overlay, a batch-trained model with online features in 11.20 — and it is the general answer whenever full recomputation is too slow to be fresh, but freshness only matters for a small and identifiable subset of the data.
StaffAn offensive suggestion is showing for a common prefix and it is in the news. Respond as the owner.
Minute one: remove it. Do not investigate first. There must be a blocklist applied at serve time — a small structure checked on the response path — so a term can be suppressed globally within seconds without rebuilding the trie, redeploying, or waiting for any pipeline. If that mechanism does not exist, building it is the incident response, and its absence is the first finding of the post-mortem.
Then verify the suppression everywhere. Edge caches will still be serving the old response, so purge them explicitly. A term you have suppressed that is still visible at the edge for ten minutes is, publicly, not suppressed.
Hour one: identify the class, not just the instance. There are three possibilities and they have completely different fixes. Organic popularity — real people really do search this. Manipulation — coordinated queries gaming the volume signal. A ranking defect — a scoring bug surfacing a term far above its true frequency. The logs answer this: look at distinct-user counts, geographic and temporal distribution, and the ratio of impressions to clicks. Manipulation shows as high volume with low user diversity and tight temporal clustering, which is exactly what the minimum distinct-user threshold exists to prevent — so if that is the answer, the finding is that the threshold was missing or misconfigured.
Day one: fix the class. Enforce distinct-user thresholds. Add automated screening over the candidate set at build time, which is cheap because it runs offline over a bounded vocabulary rather than in a 30 ms request. Route sensitive prefix categories — identity, health, elections, anything involving minors — through stricter policy, which is widely adopted precisely because pure popularity ranking on those prefixes reliably produces harm. And add the canary suite to the build pipeline: a fixed panel of prefixes queried against every new snapshot, blocking promotion when results violate policy.
The framing leadership needs, and the thing a staff engineer has to say plainly: autocomplete is not a mirror, it is a publisher. The system chooses what to display, the choice is attributed to the company, and it shapes what users search next. "The algorithm just reflects what people search" is technically incomplete — the ranking function is a choice, the thresholds are choices, the corpus is a choice — and it is indefensible in public.
What follows from that framing is concrete: a suppression capability measured in seconds, an audit trail of suppressions with owners and reasons, an appeals path for false positives, and a named owner for suggestion policy who is not the person optimising click-through. Those two objectives conflict, and an unowned conflict always resolves in favour of whichever metric has a dashboard.
Flashcards
FlashWhy precompute
~30 ms of server budget after network. A prefix query's work grows as the prefix shortens, and short prefixes are the most common. So each trie node stores its own top-k, built leaf-to-root offline.
FlashSnapshot discipline
Immutable versioned trie, atomic pointer swap, canary over a fixed prefix panel before promotion, rollback by flipping back. Alarm on snapshot age — a frozen pipeline produces no errors.
FlashSlow base plus fast delta
Base trie rebuilt in hours, trending overlay rebuilt in minutes, merged at query time. The trending signal is rate of change against a baseline, never raw volume, with a distinct-user threshold.
FlashWhere personalisation goes
Merge device-local history on the client. Keeps the global response cacheable, keeps personal data on the device, costs zero server work. Server-side personalisation is per-session, never per keystroke.
FlashThe three client rules
Debounce 50–100 ms (traffic) · cancel in-flight requests (waste) · discard out-of-order responses (otherwise suggestions visibly go backwards). All three are part of the contract, not optimisations.
FlashFailure behaviour
Show nothing. A 50 ms timeout with silence beats a correct answer at 400 ms, which is what licenses shedding load rather than queueing. A late suggestion has negative value.
Scenario Drill
DrillExtend autocomplete to an e-commerce catalogue: 50 million products, results must respect stock and regional availability, and the business wants sponsored suggestions. What changes?
The trie survives. What changes is the validity of an answer. A trie of popular search phrases still serves the head of the distribution perfectly well. But e-commerce introduces a second class of suggestion — specific products, brands and categories — whose correctness depends on mutable state: is it in stock, does it ship here, is it still listed? A precomputed list that suggests an out-of-stock product is worse than no suggestion, because it turns a helpful feature into a dead end that the user only discovers after clicking.
Three changes, in order of importance.
One: split the index by validity class. Phrase suggestions like "running shoes" are region-agnostic and stable, so they stay in the fast precomputed path unchanged. Product suggestions are precomputed per region — regional availability is coarse and slow-moving, so a handful of tries rather than one per user — and then filtered at serve time against a compact set of currently-unavailable product identifiers, refreshed every minute. This is the same read-time filtering as the tombstone set in 11.8, for exactly the same reason: filtering a small answer is cheap, rebuilding a large index is not. Over-fetch the top twenty so that filtering still leaves ten.
Two: ranking gains business signals. Conversion rate, margin and inventory depth join query frequency in the score. That changes the build from a log aggregation into a feature pipeline, and it changes the scoring function from an engineering detail into a product decision that needs an owner and an evaluation harness — offline replay against held-out sessions first, then a live experiment.
Three: sponsored suggestions are a different problem, and should be named as one. They need eligibility (which advertisers match this prefix), an auction (which candidate wins and at what price), budget pacing (so a day's budget is not spent by 9am), and billing accuracy (a click recorded exactly once, which is an idempotency and reconciliation requirement with money attached — 11.14). None of that fits a precomputed trie lookup.
So the architecture becomes a fast organic path plus a bounded sponsored path, merged at serve time with a strict timeout. If the advertising service does not answer within its slice of the budget, the organic results ship alone. That timeout is not a performance optimisation, it is the structural guarantee that monetisation can never degrade the core experience — and it is worth writing into the design document in those words, because the pressure to relax it will arrive within a quarter.
And one requirement that is not negotiable: sponsored suggestions must be visibly distinguished and labelled. That is a legal obligation in most jurisdictions and a trust obligation everywhere, and it belongs in the API contract as type: "sponsored" so that no client can render it ambiguously by accident.
The sentence for the design document: e-commerce autocomplete is two systems sharing a text box — a precomputed organic index filtered at read time for validity, and a real-time auction bounded by a timeout — and the only reason it stays both fast and trustworthy is that the second can always be dropped without affecting the first.