Code10x
Search & rankingSenior

Autocomplete, where the latency budget is a keystroke

Every design choice here is downstream of one constraint: the answer must arrive before the user types the next character.

The brief

As a user types into a search box, suggest completions ranked by popularity.

Suggestions come from what people actually searched for, so the corpus changes continuously.

Requirements

Functional

  • Return the top suggestions for a prefix
  • Rank by popularity, not alphabetically
  • Reflect newly popular queries within a reasonable delay
  • Never suggest something that must not be suggested

Non-functional

  • A suggestion arriving after the next keystroke is a suggestion nobody sees
  • Slightly stale rankings are fine; a slow response is not
  • The write path is enormous and entirely offline; the read path is tiny and entirely online

Back-of-envelope

Assume

  • 10 million searches a day
  • 20 characters typed per search, with a request per keystroke after the third
  • Top 10 suggestions per prefix

Therefore

  • Prefix requests: 1e7 × 17 ≈ 1.7e8 a day ≈ 2,000 per second — about seventeen times the search traffic itself.
  • That ratio is the entire point: autocomplete is not a feature on top of search, it is a system an order of magnitude busier than search.
  • Distinct prefixes worth precomputing are bounded by short lengths. Storing the top 10 for every prefix up to a few characters is small enough to hold in memory; going deeper grows fast and returns less.

Debouncing on the client changes the 17 in that first line, and it is the cheapest optimisation available. Establishing the number before proposing the fix is what makes the fix arguable rather than reflexive.

The interface

GET /suggest?q=<prefix>&limit=10 → [{ text }]No cookies, no user id, no personalisation — which is what makes the response identical for every visitor and therefore cacheable at the edge. The latency budget is met by that property more than by anything in the serving layer.
The response carries a snapshot versionSo a bad suggestion can be traced to the build that produced it. Without it, 'when did this appear?' is answered by guessing at build times.
POST /blocklist { term } → applied within seconds, no deployThe probe asks how fast something can be removed. If the answer involves a build or a deploy, the answer is hours, and this endpoint is what makes it seconds.

What is stored

prefix → top-k (the serving snapshot)prefix (up to N characters) → [{ text, score }] × 10, held in memory
The read is a map lookup, never a search. N and k are the two memory knobs, and both belong in the design rather than in a config file nobody revisits — raising N by one multiplies the map.
query_logsappend-only: query · timestamp · whether a result was clicked
The batch job's only input, and never read online. Keeping it append-only is what lets the ranking be recomputed differently later without having lost anything.
blocklistexact terms and patterns — small enough to hold everywhere
Read at build time AND at serve time, so it has to be small enough that a serving node can hold all of it. That size constraint is what makes serve-time filtering affordable at 2,000 requests a second.

The design

The offline aggregationA batch job over query logs, counting and ranking. This is where popularity is computed, minutes or hours behind live. Nothing on the read path counts anything.
The prefix structureA trie whose nodes carry their own top-k, or a precomputed prefix → top-k map. Either way the read is a lookup, never a search.
The serving layerIn memory, replicated, read-only. Updated by swapping in a newly built snapshot rather than mutating in place, so a serving node is never half-updated.
The filterA blocklist applied at build time AND at serve time. Build-time alone means a bad suggestion is live until the next build, which on an hourly build is an hour.

The decisions

Each of these could go the other way. The choice, the reason, and what it costs — a design that lists only what it chose teaches the choice; one that lists what it gave up teaches the judgement.

Precompute top-k per prefix, or search at query time?Chose — PrecomputeBecause — The read budget is tens of milliseconds and the corpus barely changes between builds. Ranking at query time spends the budget on work whose answer was the same an hour ago.Freshness is bounded by the build interval. A query that becomes popular in the next ten minutes will not be suggested until the next build — which is why breaking news gets special handling in real systems, and why that is a separate design.
Update in place, or swap snapshots?Chose — SwapBecause — A serving node mid-update is a node serving a mixture of two rankings. Swapping makes the update atomic from a reader's point of view.Double the memory during the swap, and a rebuild is all-or-nothing — you cannot patch one popular query in without a full build. That is the argument for a small live override layer on top.
Personalise the suggestions?Chose — Not in this designBecause — Personalisation destroys the shared cache: the top-k for a prefix is no longer one answer but one per user, and the precomputation that made the latency budget achievable no longer applies.Suggestions are worse for users with unusual intent. A common compromise is a small personal history list merged client-side with the shared result — which keeps the shared cache intact and is worth proposing.

What breaks first

In order. Each names what you would actually observe, and each fix carries its cost.

The 17× ratio, which makes the network the costSymptom — Origin CPU is comfortable and the bill is not. Two thousand requests a second of tiny responses is a connection and bandwidth problem long before it is a compute one.Fix — Serve from the edge with a short TTL — the response is identical for everyone, which is what the API section bought.Removing a suggestion now means purging every edge, so the fastest path in the system becomes the slowest thing to correct. That is the wrong way round for the one operation with a deadline attached.
Memory per serving node, as prefix depth growsSymptom — Someone raises N from four characters to five to improve long-prefix quality, and nodes start being killed for memory in an unrelated deploy.Fix — Cap the depth and fall back to a real search for longer prefixes, which are rarer and have a looser budget because the user has committed to typing.Two code paths and a latency cliff at the boundary, where one extra character makes the response visibly slower.
The snapshot swapSymptom — The node is comfortable at steady state and at double memory for the duration of the swap. It does not fail under load; it fails during a deploy, which is when everyone assumes the load was the cause.Fix — Size nodes for the swap, not for steady state, and swap one node at a time.Roughly half the fleet's memory sits unused most of the time, bought entirely for the few minutes an update takes.

When something fails

The build job fails and keeps retryingNothing breaks. Suggestions quietly get older, and every dashboard stays green because the serving layer is perfectly healthy. Alert on snapshot AGE, not on job failure — a job that fails and retries forever looks like a job that is running.
One serving node is left on an old snapshotA fraction of users see different suggestions, which reads as randomness rather than as a fault and is almost never reported. Exporting snapshot version per node is what turns it into something you can see.
The suggest endpoint is downThe search box must still accept typing and still submit. Autocomplete is an enhancement, and a search page that blocks on it has made a suggestion service into a dependency of search itself.
Something that must not be suggested is being suggestedServe-time filtering removes it now; the build-time list stops it coming back. With build-time filtering alone the exposure is one full build interval, which on an hourly build is an hour of a problem everyone can see.

Scaling it

Each step is triggered by a number, not a feeling — and carries what it costs.

10× trafficMove — More read-only replicas and more edge locations — the serving tier is stateless between swaps, so this is the easy direction.More places holding a stale snapshot, and a longer purge when something has to be removed everywhere at once.
A second and third languageMove — Key the map by (locale, prefix) and build a snapshot per locale.Memory multiplies by locale count, and the blocklist becomes per-locale — which is a staffing problem rather than a technical one, because someone has to be able to read each list.
Freshness in minutes rather than hoursMove — A small live override layer, merged over the snapshot at read time.The atomic swap stops being the whole truth: there are now two sources at read time and you must define which wins, per key. Everything the swap decision bought is spent here, deliberately, and only for the queries that need it.

What gets probed

The design is the easy half. These are where the conversation goes, and each has a defensible answer above.

  • A user types the fourth character. What is the deadline for your response, and what happens if you miss it?
  • A query becomes popular in the last ten minutes. When does it show up, and who decided that delay is acceptable?
  • Something is suggested that must not be. How fast can you remove it, and does that path need a deploy?
  • How would you measure whether the suggestions are any good?