Design typeahead (autocomplete)

For this problem, we'll design query suggestions for a large consumer search box: the kind you see on a web search engine or a big online store. We'll focus on suggesting popular queries, not on searching the catalogue itself (that is Design product search). Interviewers like this one because the read path looks trivial ("it's a prefix lookup") but the real design lives in three places candidates forget: a latency budget measured in tens of milliseconds, an index that is built offline, and short prefixes that are far hotter than everything else.

01Requirements

Let's pin the problem down before drawing anything. Here's the list I'd write on the board.

Functional

• Users should be able to see up to 10 suggestions for the text they have typed so far, updated as they type.
• Users should get suggestions ranked mostly by popularity, with recent spikes ("trending") able to climb quickly.
• Users should never see suggestions that break the content policy (hateful, sexual, dangerous), and the team should be able to remove a suggestion fast.
• Users who are signed in may see a few suggestions from their own recent searches.

Non-functional

• Latency: suggestions should feel instant. I'd set a target of under ~100 ms end to end at p99 (we'll justify the number in the deep dives), which leaves the server itself only around 10 ms.
• Scale: hundreds of millions of searches a day, which turns into tens of thousands of suggestion requests per second (estimated below).
• Availability over consistency: a slightly stale list is fine; an empty drop-down is not. If the suggest service is down, the search box must still work.
• Freshness: popular suggestions update within hours; breaking news should show within roughly 10-15 minutes (our target, agree it with the interviewer).

At this point, ask your interviewer: "Are we suggesting past queries or items from a catalogue? How many languages? Is personalisation in scope? How fresh must trending terms be?" Each answer changes the design. Queries from logs point to a precomputed table; catalogue items point to a search engine with an edge n-gram field.

02Core entities and API

Four things carry the design:

• Query: a normalised search string ("car insurance") with a score.
• Prefix entry: a prefix mapped to its top-K query IDs, already sorted. This is what we serve.
• Search event: one row per executed search (query text, time, locale, optional user ID). This is our raw signal.
• Block rule: a phrase or pattern that must never be suggested.

The API is tiny on purpose. The suggestion call is a plain GET so that browsers and CDNs can cache it.

GET /v1/suggestions?q=car&locale=en-IN&limit=10
200 OK
Cache-Control: public, max-age=300
{ "prefix": "car",
  "suggestions": [ { "text": "cars" }, { "text": "car insurance" }, { "text": "car rental" } ],
  "index_version": "2026-10-20T02:00Z" }

GET /v1/me/recent-searches?prefix=car&limit=3        (signed-in only, never cached publicly)

POST /v1/suggestions/report
{ "prefix": "car", "text": "...", "reason": "offensive" }

Notes worth saying out loud. The Cache-Control header is set only for anonymous, non-personal responses (MDN defines max-age as how long a cache may reuse the response). The personal list is a separate call so it never pollutes a shared cache. Search events are not an endpoint here: the search service already logs every executed search to Kafka, and we read from there.

03Back-of-envelope estimates

These are assumptions to agree with your interviewer, not facts about any real company. The arithmetic is ours and rounded.

The number that drives the design is ~90,000 reads per second under a ~100 ms budget, not storage. Writes are a batch job we control. That tells us to serve from RAM, replicate heavily for read throughput, and only shard if the table stops fitting in one machine's memory. For a refresher on doing this maths fast, see Back-of-envelope estimation.

04High-level design

Let's start with the simplest thing that works: one server holding a map from prefix to top 10, rebuilt every night from the logs. Then we grow it, one requirement at a time.

To show suggestions as the user types, the browser sends GET /v1/suggestions?q=<prefix> after a short pause in typing. The suggest API normalises the prefix (lowercase, trim, collapse spaces, Unicode normalisation), looks it up in the in-memory prefix table on a suggest server and returns the stored list. One lookup, no scoring at request time.

To rank by popularity and freshness, we never rank on the request path. Search events go to Kafka; batch and streaming jobs count them; an index builder keeps the top 10 per prefix and writes a versioned snapshot to blob storage, which suggest servers load in the background and swap in atomically.

To keep bad suggestions out, the builder drops blocked phrases before they reach a snapshot, and the API applies a small serve-time blocklist for urgent removals.

To personalise, a second, private call returns the user's recent matching searches, shown above the global list, which stays cacheable.

To hit the latency target at 90,000 QPS, we add client debounce and caching, a CDN for short prefixes, and read replicas.

05Deep dives

1) How do we look up a prefix fast?

Bad: query the database at request time. SELECT text FROM queries WHERE text LIKE 'car%' ORDER BY score DESC LIMIT 10 works on a B-tree index, because a left-anchored LIKE becomes a range scan. The trouble is short prefixes. c matches millions of rows, and the database must read all of them to sort by score. It falls over exactly on the prefixes people type most.

Good: a trie, searched per request. A trie stores strings character by character, so all queries starting with car live under one node. Walking to that node costs only the prefix length. But you still have to visit the whole subtree below it to find the 10 best, which for a one-letter prefix is most of the tree. Same problem, smaller constant.

Great: precompute the top K at every node. Store the sorted top-10 list on every trie node at build time. Now a lookup walks len(prefix) nodes and returns one list. There's no search at request time at all.

Once every node carries its answer, notice that you don't really need the tree at serve time. A flat hash map of prefix -> top-10 IDs gives the same result with one hash lookup, and it's trivial to shard (deep dive 3). The trie becomes a build-time tool. A Redis sorted set with lexicographic ranges (Redis sorted sets) can prototype prefix lookups, but I'd serve the hot path from the suggest servers' own memory.

When the suggestions are documents, not queries. If you're completing product names or people, a search engine is the natural home. Elasticsearch's completion suggester is built for this: it keeps data structures that are fast to query but "costly to build and are stored in-memory" (Elastic docs). The alternative is an edge n-gram field, which indexes Qu, Qui, Quic, Quick at index time while you search the raw typed text (edge n-gram tokenizer). It's more flexible (it can match words in the middle and combine with filters) and slower than a precomputed list. We cover both in Types of search and the structures underneath in Storage data structures.

My default: a precomputed prefix-to-top-K table, built offline, held in RAM on every suggest server. Reach for Elasticsearch only when the suggestions are entities with filters.

2) How do we build the index, and keep it fresh?

The index is only as good as its scores. Google describes its own predictions as based on real searches, showing "common and trending ones" that also relate to your location and previous searches (How Google autocomplete works). That's the right mental model: popularity plus recency, adjusted per user.

Batch layer (the backbone). Every few hours, a batch job reads the search events from Kafka (or the copy archived in blob storage), normalises each query and counts it per locale. Raw counts favour old evergreen queries forever, so apply time decay: each day's count is multiplied by a factor like 0.9 per day of age (our example, tune it). Drop queries seen by too few distinct users; this removes noise and also stops one person from planting a suggestion. Apply the block rules. Build the trie, fill the top 10 per node, flatten it to a prefix table and write it as a versioned snapshot.

Streaming layer (the freshness). A batch every few hours can't surface breaking news. A streaming job reads the same Kafka topic and keeps counts over short sliding windows (say, the last 15 minutes). When a query's recent rate jumps well above its usual rate, it's trending. The streaming job publishes a small "fresh" table of a few thousand prefixes. At serve time the API merges the fresh list into the main list, so a trending query can appear within minutes without rebuilding the big index.

Swapping safely. Each suggest server downloads the new snapshot, loads it next to the old one, runs a few sanity checks (row count within a few percent of the last version, a handful of known prefixes return results), then flips a pointer. If anything looks wrong, it keeps the old one. The index_version in the response makes "why did suggestions change?" debuggable.

My default: batch every few hours plus a streaming trending layer, merged at serve time. Start with batch only if the interviewer says freshness within a day is fine.

3) How do we hit 100 ms at 90,000 QPS?

First, where does the 100 ms come from? Usability research has long put 0.1 second as the limit for a response to feel instantaneous (Nielsen Norman Group). Facebook's engineers wrote that spending more than 100 msec to retrieve a typeahead result makes it "stutter" (The life of a typeahead query). So 100 ms is the whole budget, and most of it is spent on the network, not in our code.

Layer 1: the client. Debounce: wait until the user pauses for a few tens of milliseconds before sending, which collapses a burst of keystrokes into one call (MDN: Debounce). Cancel in-flight requests that are now stale, and drop out-of-order responses (check that the response's prefix still matches the box). Cache every response in memory for the session, so backspace and retyping cost nothing. Facebook's typeahead went further and preloaded a user's friends and pages into the browser cache as soon as the box got focus.

const cache = new Map();
let timer, controller;
input.addEventListener('input', () => {
  clearTimeout(timer);
  timer = setTimeout(async () => {
    const q = normalise(input.value);
    if (cache.has(q)) return render(cache.get(q));
    controller?.abort();                       // drop the stale request
    controller = new AbortController();
    try {
      const res = await fetch(`/v1/suggestions?q=${encodeURIComponent(q)}`, { signal: controller.signal });
      const body = await res.json();
      cache.set(q, body);
      if (normalise(input.value) === body.prefix) render(body); // ignore late answers
    } catch (e) {
      if (e.name !== 'AbortError') showNothing();               // never block typing
    }
  }, 50);                                      // our starting debounce; tune with A/B tests
});

Layer 2: the CDN. Short prefixes are a tiny keyspace with enormous traffic. With only lowercase a-z, there are 26 one-letter and 676 two-letter prefixes per locale (our arithmetic). Their answers barely change, so let the CDN cache them with a max-age of a few minutes. Most traffic for the hottest keys then never reaches us. See CDNs and edge caching.

Layer 3: replicas and shards. If the table fits in one server's RAM (tens of GB fits on ordinary servers), every suggest server holds a full copy and you scale reads by adding replicas. When it stops fitting, shard it.

• Range by first letter (a-f on shard 0, and so on) keeps neighbours together, but letters are wildly unequal in traffic, so some shards melt.
• Hash of the whole prefix spreads keys evenly. This works only because a request reads exactly one key: we look up car, never "everything under ca". That's a direct win from precomputing top-K in deep dive 1.

Even with hashing, a single key like a is one hot partition. The CDN and client caches are what really protect it; replicas take the rest. We cover the general pattern in Sharding and partitioning and Caching.

My default: client debounce and cache, CDN for prefixes of one or two characters, full replicas until memory forces hash sharding.

4) Personalisation and keeping suggestions safe

Personalisation. The cheap, effective version: the user's own recent searches that match the prefix, shown first. Keep the last 100 or so per user in a small store such as Redis keyed by user ID, or on the device itself. The API (or the client) merges them above the global list and removes duplicates. Heavier personalisation, like location or language, is better done by building separate tables per locale or region, which stay cacheable. Personalising the global list itself per user would destroy the CDN hit rate, so be explicit about that trade-off.

Safety. Google's published policies remove predictions that are sexually explicit, hateful, violent or dangerous, and also ones that are spam or tied to piracy, with the guiding idea that autocomplete "should not shock users" (How Google autocomplete works). Design for it in three places:

1. At build time: block lists and a classifier drop bad candidates before they enter a snapshot. This is where most filtering lives.
2. At serve time: a small, frequently pushed blocklist checked on every response, for removals that can't wait for the next build (legal requests, a fresh incident).
3. Thresholds: require a query to come from many distinct users before it can be suggested, which blunts manipulation campaigns.

My default: recent searches merged from a private call, per-locale global tables, and filtering at build time with a serve-time blocklist for urgent removals.

06What interviewers look for

Green flags: naming the dominant number (QPS under a latency budget), moving ranking off the request path, recognising that one-character prefixes are the hot keys, mentioning debounce and out-of-order responses.

Red flags: a relational query per keystroke, synchronous trie updates on every search, no freshness story, no safety filtering, personalising everything and then putting a CDN in front of it.

07Follow-up questions

What if users make typos, like "carr insurence"?

Typeahead is mostly navigational, so keep the main path exact and cheap. Add a fallback: when the exact prefix returns few results, try a small fuzzy lookup over the prefix table limited to one edit, or route to a search engine field with fuzziness. Elastic's own docs say the completion suggester isn't meant for spell correction, so treat typos as a separate, slower path.

What if a breaking news query needs to show within a minute?

Shorten the streaming window and push the fresh table more often, every 30-60 seconds. The fresh table is small (thousands of prefixes), so pushing it is cheap. The main snapshot doesn't need to change. Gate it with a minimum distinct-user count so a bot can't trend a phrase.

What if legal asks us to remove a suggestion right now?

Add it to the serve-time blocklist, which every API server polls or receives by push within seconds. Purge the CDN entries for the affected prefixes, because cached responses would otherwise live for their full max-age. Then add the rule to the build-time list so the next snapshot never contains it.

What if we support 30 languages?

Build one table per locale, because normalisation is language-specific (case folding, accents, scripts without spaces). Locale becomes part of the cache key and the shard key.

What if a suggest server dies while loading a new snapshot?

Users don't notice: the load balancer's health check takes it out and replicas serve the traffic. On restart it loads the latest good snapshot from blob storage. Snapshots are immutable and versioned, so any server can rebuild its state from storage alone.

What if the suggestions should be products, not past queries?

Then the source of truth is the catalogue, not the logs, and you need filters like category and stock. I'd use a completion or edge n-gram field in the product search index and blend it with query suggestions. That's the territory of Design product search.

08How to say it in the interview