How Google autosuggest works: from keystroke to trie to serving fleet.

You type one letter into Google's search box, and before your finger has left the key, ten suggestions appear. Do it a hundred times and it feels free, instant, obvious. It is none of those things. Behind that dropdown sits one of the tightest latency budgets in consumer software, a data structure held in memory across thousands of machines, and an offline pipeline chewing through a firehose of query logs to keep it all fresh. This is a walk through the whole thing, from the keystroke to the machines and back, with the parts that usually get hand-waved drawn out in full.

The mental model to hold the entire time: the fast online path only ever reads precomputed structures, and it does so on a budget measured in single-digit milliseconds. Everything expensive (counting, ranking, model training, index building) happens on a slow offline path and gets shipped to the serving fleet on a schedule. Almost every design decision below falls out of that one split.

01The client is doing more than you think

The suggestion box is not a dumb text field that forwards keystrokes. It is a small state machine optimizing for one thing: perceived latency. Three tricks carry most of the weight.

Firing and cancelling. A naive implementation fires one request per keystroke and renders whatever comes back. That breaks the moment responses arrive out of order: you type sea then seat, but the slower response for sea lands last and clobbers the dropdown with stale content. The fix is to tie every request to a monotonic sequence number, or better, to actively cancel the in-flight request when a newer keystroke supersedes it.

let controller = null;

async function onKeystroke(prefix) {
  controller?.abort();                     // cancel the previous in-flight request
  controller = new AbortController();
  try {
    const res = await fetch(`/complete/search?q=${encodeURIComponent(prefix)}`,
                            { signal: controller.signal });
    render(await res.json());
  } catch (err) {
    if (err.name === 'AbortError') return;  // expected: a newer keystroke won
    throw err;
  }
}

The decision to cancel and the act of cancelling both live in your JavaScript. The browser does not infer that request #2 supersedes request #1, it has no concept of that relationship. What the browser does handle is translating .abort() into the right wire behavior, and that behavior is worth understanding because it explains why cancelling is cheap.

Connection reuse. Every request goes to the same origin over a connection that was opened once, at page load, and kept alive. The expensive parts of setting up a secure connection (the TCP handshake, then the TLS handshake) are a one-time cost, not a per-keystroke cost.

Local caching. Backspacing from seattle to seattl is common (you are reconsidering), so the client keeps a small in-memory map of prefix → last response and serves the shorter prefix from cache instead of round-tripping. This cache is per page load, never persisted, because suggestions are time-sensitive.

02Edge routing and the latency budget

The request leaves the browser and hits the nearest Google Front End through anycast: the same IP address is advertised from many locations, and the network delivers your packets to whichever one is closest. TLS terminates there, close to you, so the handshake round trips are short. Only then does the request travel (over Google's internal backbone, not the public internet) to a regional suggestion service.

Why go to this trouble? Because autosuggest sits on the critical path of typing. The whole thing has to feel like it is keeping up with your fingers, which means the perceived round trip needs to stay under roughly 100ms. Subtract network time and you are left with a brutally small server-side budget.

The lesson buried in those numbers: the server-side work (normalize, look up, rank, filter) has maybe 10-15ms total. That single constraint is why the suggestion service can't run heavy NLP, can't call a large model per keystroke, and can't scan anything at request time. Everything it returns must already have been computed. It only reads.

03Query understanding, without the heavy machinery

Before any lookup, the raw prefix is normalized: lowercased, trimmed, accents folded (café → cafe), Unicode canonicalized, and language / script detected. This is deliberately cheap. There is no room in the budget for a real parser on a two-character prefix.

One thing that gets deeper as you type more: understanding is progressive. A one-letter prefix gets almost no interpretation. A long, complete-looking query gets more (entity recognition, "did you mean" correction), because by then it looks finished and the extra work is justified.

And a subtlety worth its own section: spelling.

04Typos: why "correct then look up" is the wrong model

The intuitive design is a pipeline: take the typed string, autocorrect it, feed the corrected string to the index. This breaks on the defining property of autosuggest: the input is incomplete by definition. Is seattl a typo of seattle, or a correct prefix of it that you haven't finished typing? They are identical. Aggressively "fixing" every prefix would mean constantly second-guessing a user mid-thought.

So tolerance is not a separate stage. It is fused into the matching itself. Two mechanisms do the work.

Mechanism 1: fuzzy matching baked into retrieval

Start with what actually happens on a real typo. Suppose you type explian. A literal, character-by-character trie walk does not wander off to a wrong-but-complete word. Trie nodes only have children for letters that continue a real indexed word, so the walk simply dies at the first character with no matching child.

The trick (the SymSpell approach) is to precompute, offline, every string reachable by deleting up to N characters from each dictionary word, and store a reverse index from those delete-variants back to the real words. At query time you generate the delete-variants of the typed string too, and look for overlap. Overlap means the two strings are a small edit apart.

Two variants (explan and explin) collide. That overlap flags explain as a candidate. A cheap verification step then runs real Damerau-Levenshtein distance only on this tiny shortlist, confirms the true edit is a single transposition of a and i, and pulls completions from explain's subtree (explain this, explain this to me, and so on). No rewrite-and-rewalk, no separate correction service, no extra network hop.

# OFFLINE: build reverse index {delete_variant -> [(word, freq), ...]}
def generate_deletes(word, max_edits=2):
    seen, frontier = {word}, [word]
    for _ in range(max_edits):
        nxt = []
        for w in frontier:
            for i in range(len(w)):
                v = w[:i] + w[i+1:]
                if v not in seen: seen.add(v); nxt.append(v)
        frontier = nxt
    return seen

# ONLINE (hot path): same deletes on the typo, then intersect + verify
def fuzzy_candidates(typed):
    hits = []
    for v in generate_deletes(typed, max_edits=1):   # tighter budget online
        hits += delete_index.get(v, [])
    return sorted(set(hits), key=lambda x: -x[1])   # by frequency

Mechanism 2: correction that falls out of popularity

A lot of what looks like autocorrect is not explicit logic at all. Type recieve email and the index space around that prefix has vastly more historical traffic for the correctly-spelled receive email…, so the correct completions simply outrank the misspelled ones. It is fuzzy retrieval plus frequency ranking, not a "did you mean" rule.

The genuine, heavier spell-correction model (a noisy-channel or small neural model) is reserved for complete queries, post-submit, where the budget is looser. All of it is trained on the single most valuable signal Google has here: query reformulation logs, the millions of sessions where someone typed recieve, paused, and retyped receive. That pairing captures phonetic and keyboard-adjacency errors that raw edit distance never could.

05Candidate generation: the trie, and why it must be sharded

Now the core data-structure problem: given a prefix, return the top-k completions, fast. The classic answer is a trie (prefix tree) where each node stores its own precomputed top-k completions. Walking to the node for a prefix is O(length of prefix), and the answer is sitting right there. No scan.

struct TrieNode {
  std::unordered_map<char, TrieNode*> children;
  std::vector<Completion>             top_k;  // precomputed OFFLINE, e.g. top 10
};

std::vector<Completion> Lookup(TrieNode* root, const std::string& prefix) {
  TrieNode* node = root;
  for (char c : prefix) {
    auto it = node->children.find(c);
    if (it == node->children.end()) return FuzzyFallback(prefix);
    node = it->second;
  }
  return node->top_k;   // O(prefix length), no runtime scan of the subtree
}

That precomputed top_k is the whole game. It is what lets a lookup touch exactly one node and stop. Without it you would have to explore the entire subtree under a prefix at request time and merge, which no latency budget allows.

The problem: this index (hundreds of millions of prefixes across every language, each node carrying its top-k) does not fit on one machine, and one machine could never serve global keystroke QPS anyway. So it has to be partitioned. The real design question is how to split a tree without breaking the "one lookup touches one place" property.

Why the obvious split fails

Shard by first letter (a-m here, n-z there) and you get wildly uneven load. English query traffic is enormously skewed by starting letter: prefixes under s, t, c, w dwarf x, q, z. One shard melts while another idles.

Two-tier routing, balanced by measured traffic

The fix is a small, fully-replicated router holding just the first few characters of prefix space, with shard boundaries assigned by observed query frequency (a greedy bin-packing) rather than by the alphabet. A shard might own the unrelated set {th, qz, vk} purely because that combination balances load. This is much closer to weighted consistent hashing than to an alphabetical cut.

Each shard's machines hold the full deep subtree for whatever shallow prefixes they own, with the precomputed top-k on every node. A request for seattle routes on se to shard 7, lands on any one of shard 7's replicas, walks the local trie, and returns. That the answer is pre-aggregated per node is what keeps this to a single hop.

When one prefix is too big: hierarchical routing

Sometimes a single shallow prefix (th for the, this, that; ho for how to…) is so large or so hot that its subtree alone won't fit on one machine. The fix is to make the routing key length variable: go deeper only where needed.

// Most prefixes stop at 2 chars. Hot ones recurse to 3+.
routing_table["qz"] = 3;               // small: bundled onto shard 3
routing_table["th"] = ROUTE_TO_SUBROUTER;   // too hot: don't stop here
    subrouting_table["the"] = 12;
    subrouting_table["tha"] = 13;
    subrouting_table["thi"] = 14;

The invariant survives (still one request, one shard). Only the cut depth adapts per branch.

Absorbing spikes and skew

• Replica count tracks live QPS. A prefix that explodes on breaking news doesn't trigger a re-shard. The load balancer just spins up more replicas of that shard; the router still points at "shard 3."
• A separate, tiny, globally-replicated trending index sits alongside the main lookup to catch spikes that the multi-hour rebuild can't. It is small enough to copy everywhere because "what's trending right now" is a minuscule slice of all prefixes.
• Edge caching for the head of the distribution. Traffic is Zipfian: a handful of prefixes (facebook, weather, youtube) dominate. An LRU cache at the edge serves those without ever hitting a backend.

Merging multiple candidate sources

The global trie is only one source. The real response fans out to a small, fixed number of sources in parallel and merges them at ranking. Fixed matters: the fan-out scales with the number of signal types (about four), not with the size of the dictionary.

async def get_candidates(prefix, ctx):
    results = await asyncio.gather(
        global_trie_lookup(prefix),                 # sharded, as above
        trending_lookup(prefix),                    # small, replicated everywhere
        personalization_lookup(ctx.user, prefix),  # keyed by user
        geo_lookup(prefix, ctx.location),           # local places / businesses
    )
    return rank_and_merge(results)

06Ranking: the cheap first pass and the sharp second pass

The top_k stored in each trie node is really a coarse first-pass ranking, mostly raw frequency, frozen at index-build time. Once candidate generation has merged ~50-200 candidates from all four sources, a second pass re-scores them with richer signals that weren't available when the trie was built.

double Score(const Candidate& c) {
  if (!c.passes_safety) return -INFINITY;   // hard exclude
  // Illustrative blend. Production trains a small GBDT / LambdaMART over
  // these features — affordable because the candidate set is already tiny.
  return 0.35*c.ctr_given_prefix + 0.20*c.global_freq
       + 0.15*c.trending    + 0.15*c.personalization
       + 0.10*c.geo         + 0.05*c.language_match;
}

std::vector<Candidate> RankAndDiversify(std::vector<Candidate> cands, int k) {
  for (auto& c : cands) c.score = Score(c);
  std::sort(cands.begin(), cands.end(), by_score_desc);
  std::vector<Candidate> out;
  for (auto& c : cands) {                     // MMR-style dedup
    if (out.size() >= k) break;
    if (!TooSimilarToAny(c, out)) out.push_back(c);
  }
  return out;
}

That final diversity pass matters more than it looks. Without it, one hot entity crowds the list with near-duplicates (weather, weather today, weather tomorrow, weather now) and starves you of distinct options. A greedy maximal-marginal-relevance selection trades a little raw score for variety in what's actually shown.

07The filtering layer nobody sees

Before anything is returned, candidates pass a policy gate: safety classes (violence, self-harm, adult, harassment), spam and scraper-generated suggestion removal, legal takedowns (right-to-be-forgotten style suppression), and near-duplicate dedup. This is a real, heavily-staffed engineering surface. Autosuggest has been publicly criticized for surfacing offensive completions, so an entire moderation pipeline lives here, with both offline review and fast online suppression.

08The offline pipeline: a two-speed machine

Everything above only reads. Building what it reads is the larger system, and it runs at two speeds: a thorough batch pipeline that rebuilds the main index every few hours, and a fast, approximate streaming pipeline that exists solely to catch what batch is too slow for.

The batch side: aggregate with decay

Count every (prefix → completion) occurrence, but weight recent activity more heavily so a completion that was hot six months ago doesn't outrank what's current. This is a distributed reduce over the full log corpus, sharded by prefix hash.

// One pass over a window of scrubbed, sampled logs.
std::unordered_map<AggKey, double> Aggregate(const Logs& logs, Time now) {
  std::unordered_map<AggKey, double> score;
  for (const auto& e : logs) {
    double age_days = DaysBetween(e.ts, now);
    double decay = std::exp(-kDecayRate * age_days);  // exponential time decay
    score[{e.prefix, e.completion}] += decay;
  }
  return score;   // → feeds top-k selection per trie node
}

The streaming side: spikes against a seasonal baseline

The batch cadence is fundamentally too slow for a term that goes from zero to huge in twenty minutes. Streaming maintains a rolling count per candidate and compares it to an expected baseline. The critical detail: the baseline must be seasonality-aware. A flat average would constantly misfire, because dinner recipes spikes every evening and nfl scores spikes every Sunday. Those cycles are expected, not trends. So the baseline is learned per time-of-day / day-of-week bucket, and only deviation from that counts.

bool IsTrending(const TrendState& s) {
  if (s.total_volume < kMinVolume) return false;   // 2→10 searches isn't a trend
  double z = (s.current - s.baseline) / std::sqrt(s.baseline + 1.0);
  return z > kZThreshold;
}
// Baseline updates per time-of-day / day-of-week slot, so "Sunday 4pm"
// is learned separately from "Tuesday 4pm".
void UpdateBaseline(TrendState& s, double observed) {
  s.baseline = kAlpha * observed + (1 - kAlpha) * s.baseline;   // EWMA
}

09The parts that usually get skipped

The eight sections above are the spine. These are the pieces that separate a textbook answer from someone who has actually thought about running this.

Privacy is a first-class constraint, not an afterthought

Suggestions are built from other people's queries, which means a careless pipeline could surface someone's private search as a public suggestion. The guardrails: aggregate only, never raw logs; a k-anonymity threshold so a completion is only eligible if enough distinct users searched it (rare, potentially-identifying queries are dropped); and differential-privacy-style noise on the counts. This is also why you sometimes see fewer suggestions than you'd expect for an unusual prefix. The candidates existed but didn't clear the anonymity bar.

Zero-prefix suggestions

Before you type anything, the box often already shows suggestions: recent searches, trending topics, sometimes context from the page. This is a different code path (no prefix to match) driven almost entirely by personalization and trending, and it is a deliberate product surface, not a side effect.

Multi-language, IME, and transliteration

A huge share of the world types one language using another's alphabet: Hindi or Arabic or Japanese entered in Latin characters, then transliterated. Autosuggest has to complete and transliterate at once (namas → नमस्ते), which means script detection and a transliteration model sit in the query-understanding path for those locales, and the trie effectively indexes across scripts.

Entity awareness

Many suggestions aren't raw historical query strings, they are entities from the Knowledge Graph: people, places, movies, products. That is why suggestions can carry a little thumbnail or descriptor, and why a brand-new movie can be suggested well before enough people have searched its exact title, the entity exists in the graph even if the query log is thin.

Everything here is an experiment

Ranking weights, the diversity threshold, how aggressively to trend, how many suggestions to show, all of it is continuously A/B tested. The metrics are not "did they click a suggestion" in isolation but downstream: did using a suggestion lead to a successful search session, or did the user have to reformulate anyway? A suggestion that gets clicked but leads nowhere is a bad suggestion.

Compressing the index

A plain pointer-based trie is memory-hungry, and memory is the binding constraint on how much you can serve per machine. Production systems lean on succinct structures (FSTs / minimal-acyclic finite-state automata, LOUDS-encoded tries) that store the same prefix set in a fraction of the space by sharing suffixes and encoding structure as bit vectors. Less memory per machine means fewer machines, means lower latency and cost. It is not a detail. It is often the difference between fitting in RAM and not.

10The tensions, in one place

That is the whole loop: a client optimizing perceived latency, an edge that terminates close to you, a suggestion service that only reads precomputed structures on a 10-millisecond budget, a sharded in-memory trie with fuzzy matching fused into it, a light second-pass ranker, a safety gate, and behind all of it a two-speed offline pipeline keeping the structures fresh without ever slowing down the read. Every choice traces back to one line drawn on day one: the fast path reads, the slow path writes, and the two only meet at deploy. Thanks for reading ✦