Every Keystroke Is a Query

Typing "autocomplete" into a search box and pressing enter looks like one request. Left alone, the client sends up to twelve: one per character, each racing the next, each needing an answer before the following key lands. Traffic to the suggest endpoint is roughly search traffic multiplied by the number of keystrokes per query, before debouncing and caching claw some of it back.

The latency target is set by people, not by the service. The long-standing usability rule of thumb is that around 100 ms feels instantaneous. A suggestion that arrives after the user has already typed past it is not slow, it is wrong, because it answers a prefix that no longer exists.

The payoff justifies the cost. Google's own figure is that autocomplete cuts typing by roughly a quarter on average, which is why nearly every search surface ships one. The engineering question is how to deliver that benefit without turning a text box into the busiest endpoint in the platform.

Start from the 100 ms perception line and subtract everything the service does not control. Debounce, two network legs, an edge hop and the browser's render pass consume most of it, which leaves the suggest service with a single-digit to low-double-digit millisecond allowance. That number rules out a database query, a fan-out to other services, or anything that touches disk on the hot path.

Two consequences follow. First, the service has to be a pure in-memory lookup whose cost depends on the length of the prefix, not the size of the corpus. Second, the cheapest request is the one that never leaves the browser or the edge, so caching is not an optimisation to add later; it is half of the design.

Four approaches cover most real systems. They differ in what they make cheap: prefix lookups, ranking flexibility, mid-phrase matching, or operational simplicity.

The trie with a precomputed top-k is the clearest way to see why prefix lookups can be constant with respect to corpus size. Each node already knows its best completions, so a lookup is a short walk and a list read. Nothing is sorted at request time and nothing scans the corpus.

Edge n-grams and search_as_you_type (available since Elasticsearch 7.2) are the better fit when users type the middle of a phrase, for example a product name where the second word is the distinctive one. The price is a bigger index and a slower lookup than the FST path, which is an acceptable trade only when mid-phrase matching earns it.

The lab below constructs a real trie in the browser from a small synthetic query log. The scores are invented for the demo. Type a prefix, then flip the lookup strategy and compare what each approach has to touch. Toggle the policy filter to see why takedowns are a build-time concern.

What to notice.

• With the trie, "nodes visited" tracks the length of the prefix you typed. Add queries to the log and it does not move. The naive scan examines every entry on every keystroke; at ten million logged queries, that column is the outage.
• The whole trick is the list stored on each node. It costs memory, because every node holds its own top five, and it buys a lookup with no sorting. That is the same trade as the FST's index-time weights.
• Toggling the policy filter rebuilds the structure, because the cached lists are baked into the snapshot. A takedown that only exists in the next build is too slow, which is why section 8 adds a read-time overlay.

Reads are fast because writes are slow, deliberate and offline. The system never updates a live structure per search. It aggregates logs into counts, filters them, builds an immutable snapshot, and swaps that snapshot in atomically.

• Windowed counts with decay. Raw all-time counts freeze the past in place. Weight recent activity more heavily so a query that is rising overtakes one that is merely old.
• Eligibility thresholds. Require a minimum number of distinct users before a query can be suggested. That one rule filters most manipulation attempts and keeps rare, possibly personal strings (a name, an email address) out of a public dropdown.
• Immutable, versioned snapshots. Each build is a new object. Servers load it beside the live one and flip a pointer, so a rollback is repointing to the previous version.
• A small trending overlay. A full rebuild suits stable catalogues; news-like domains need a fast path that merges a short list of rising queries on top. Rebuild cadence is a product decision, not a technical constant: hours for a catalogue, minutes for anything event-driven.

Short prefixes are the hottest keys in the system and the easiest to cache. Millions of users typing "k" are asking an identical question. The request should be a cacheable GET whose URL fully describes the answer, including which snapshot produced it.

GET /suggest?q=kub&loc=en-IN&v=2026-10-29T06 HTTP/2

200 OK
Cache-Control: public, max-age=60, stale-while-revalidate=300
Content-Type: application/json

{"q":"kub","v":"2026-10-29T06","items":["kubernetes","kubectl cheat sheet","kubernetes pod crashloopbackoff"]}

• Put the snapshot version in the cache key. A new snapshot then invalidates itself, and a half-swapped fleet cannot poison the edge with mixed answers.
• Split shared from personal. The base list is identical for everyone in a locale, so it caches at the edge. Personalised or recent-history suggestions cannot be shared; merge those in the client or in a thin layer after the cache.
• Replicate before you shard. After pruning, an autocomplete index is often small enough to hold whole on every node. Sharding by leading characters creates hot shards, because letter frequency is wildly uneven. Adding identical replicas scales reads without that skew.
• Coalesce misses. After a deploy or a cache flush, thousands of clients ask for the same cold prefix at once. Collapse concurrent identical requests into one origin fetch.

Network responses do not arrive in the order requests were sent. Type "kube" and four requests leave; if the third takes longest, a naive client renders it last and the dropdown shows answers for "kub" under an input that says "kube". Nothing errors and nothing pages. The suggestions are simply wrong. The lab replays that sequence with fixed latencies.

The fix is small and has to exist from day one: tag each request with a sequence number, render only the response that matches the latest keystroke, and abort superseded requests so the network does not carry work nobody will read. The controller below also covers three details that cause most production oddities.

type Suggest = { q: string; items: string[]; v: string };

export function createTypeahead(
  fetchSuggest: (q: string, signal: AbortSignal) => Promise<Suggest>,
  render: (items: string[]) => void,
  { debounceMs = 60, minChars = 1, timeoutMs = 250 } = {}
) {
  const cache = new Map<string, string[]>();  // prefix -> items (clear when the snapshot version changes)
  let timer: ReturnType<typeof setTimeout> | undefined;
  let inflight: AbortController | undefined;
  let seq = 0;
  let composing = false;                        // IME: never query mid-composition

  async function run(q: string, mySeq: number) {
    inflight?.abort();                          // supersede the previous request
    const ctl = (inflight = new AbortController());
    const deadline = setTimeout(() => ctl.abort(), timeoutMs);
    try {
      const res = await fetchSuggest(q, ctl.signal);
      if (mySeq !== seq) return;                // stale: a newer keystroke exists
      cache.set(q, res.items);
      render(res.items);
    } catch {
      // best-effort: fail silent so the search box itself stays usable
    } finally {
      clearTimeout(deadline);
    }
  }

  return {
    onInput(raw: string) {
      if (composing) return;
      const q = raw.trim().toLowerCase().normalize("NFKC");  // must match build-time normalisation
      const mySeq = ++seq;
      clearTimeout(timer);
      if (q.length < minChars) return render([]);
      const hit = cache.get(q);
      if (hit) return render(hit);
      timer = setTimeout(() => run(q, mySeq), debounceMs);
    },
    compositionStart() { composing = true; },
    compositionEnd(raw: string) { composing = false; this.onInput(raw); },
  };
}

The ranking signal is other people's typing, and the output is shown to everyone. That makes the suggestion list a published statement, whether or not anyone intended it to be. Courts, regulators and platform policy have all treated it that way, which turns takedown from a policy topic into an engineering requirement.

Turning that into a design gives a layered filter, none of which is the ranking model:

• Eligibility rules at build time: minimum distinct users, spam and duplicate suppression, category policy checks. This is the filter the lab's checkbox demonstrates.
• A read-time denylist overlay applied after the snapshot lookup, so an approved takedown takes effect in minutes rather than at the next build. Over-fetch a few extra candidates (k plus a margin) so removal does not leave a short list.
• Normalised matching that expands a removal to case, spacing, punctuation and transliteration variants before the denylist is consulted.
• Edge purge on takedown. A removed suggestion cached for sixty seconds is still a published suggestion. Tie the purge to the same workflow that updates the overlay.
• An audit log recording who requested the removal, who approved it and when it reached the edge.

Averages hide this system's failures. A healthy median can coexist with a broken snapshot in one locale or a cache that quietly stopped hitting for two-letter prefixes. These eight indicators cover latency, freshness, quality and the policy path. Targets are illustrative; calibrate them against your own traffic.