Skip to content

00. Design Search Autocomplete / Typeahead

~20 min read · Level: intermediate · Part 1 of 4 (Overview → HLD → LLD → Q&A)

Problem

Search autocomplete is the dropdown that appears under a search box as you type: you press n, e, w, and the box already offers "new york times," "news," "netflix." This is the product behind Google's search suggestions, the App Store search bar, and the autocomplete in every large e-commerce site. The job is narrow and specific — given a prefix the user has typed so far, return the handful of most likely complete queries, ranked so the one they actually want is near the top, and do it fast enough that the list keeps up with their fingers.

What makes it a real system-design question rather than a data-structures exercise is the traffic and the freshness demand pulling in opposite directions. Every keystroke is a query, so request volume dwarfs the number of searches actually submitted. The ranking has to reflect what the whole world is searching for right now — a breaking news term should appear within minutes, not after tomorrow's batch job — yet the fastest way to answer a prefix is to have precomputed the answer hours ago. Holding both at once is the whole game.

To keep the reasoning concrete, thread one scenario through the entire design: the system must serve 100,000 prefix queries per second, return the top-10 suggestions for each in under 100 ms end to end, and surface a newly trending term within minutes of it spiking. Those three numbers — 100k QPS, 100 ms, minutes-to-trend — will test every decision below.

Functional requirements

  • Prefix suggestions: given a prefix string, return the top k (default 10) complete query suggestions.
  • Popularity ranking: order suggestions by how often the full query is searched, so common intents float to the top.
  • Trending freshness: reflect surging queries within minutes, not on a daily cadence.
  • Multi-language / locale: suggestions respect the user's language and region.
  • Light personalization: nudge results toward a user's own recent searches without rebuilding an index per user.

De-scoped for this round, and worth naming so the interviewer hears it as a choice: full spell-correction and fuzzy matching, semantic ("did you mean") rewrites, rich result previews (images, entities), and voice input. These are real features but they layer on top of the core prefix-lookup engine without changing its shape.

Non-functional requirements

The dominant constraint is tail latency under extreme read volume. Everything else bends to keep the 99th-percentile response inside the 100 ms budget while absorbing 100k QPS.

  • Latency: under 100 ms end to end at p99, which after a ~40–60 ms network round trip leaves the service roughly 30–50 ms of internal budget. The list must feel like it is already there.
  • Throughput: 100,000 prefix queries/second sustained, with headroom for spikes, because keystrokes generate far more requests than submitted searches.
  • Freshness: base rankings can lag by hours; trending terms must appear within minutes. This split is the crux of the design.
  • Availability: high, but a suggestion is advisory — if autocomplete fails, the user can still submit a raw query. A brief stale-but-up beats fresh-but-down.
  • Relevance: suggestions must be genuinely popular completions, not arbitrary prefix matches, or the feature is noise.

Scale estimation

Start from the threaded numbers and reconcile them. At 100,000 prefix queries/second, note first that these are keystrokes, not searches. A user typing a 15-character query, even with client-side debouncing that fires a request only after a ~100 ms typing pause, still emits on the order of 5–8 requests per search. So 100k autocomplete QPS corresponds to roughly 15,000–20,000 submitted searches/second — the request amplification from keystrokes is exactly why the read path must be cheap.

The saving grace is that prefix popularity is brutally skewed (Zipfian). A tiny set of short, common prefixes — a, th, wh, new — absorbs most of the traffic, and the same prefix from a million users deserves the same answer. That is what makes a front cache devastatingly effective: cache the top-10 for the hottest ~1 million prefixes and you serve about 95% of the 100k QPS from memory, leaving only ~5,000 QPS to reach the ranking engine. Sizing that cache is trivial: 1M entries × (a short prefix key + ten suggestions at ~40 bytes each) ≈ 1M × ~450 B ≈ 450 MB. It fits on one node with room to spare.

The index itself is the memory story. Suppose we index the top 100 million distinct historical queries, averaging 20 characters. A prefix tree (trie) with prefix sharing collapses those ~2 billion characters into roughly 300 million nodes. If each node caches its own precomputed top-10 as (query_id: 4 B, score: 4 B) pairs plus structural overhead — call it ~130 bytes/node — the trie is 300M × 130 B ≈ 39 GB, plus a ~2 GB string dictionary. That does not fit on one box comfortably, so we shard it across ~8–12 machines at 3–5 GB each, with headroom for the real-time layer. The point of the arithmetic: this is a memory-bound system, not a storage one — the entire useful index lives in RAM on a handful of machines.

Bandwidth is minor. A top-10 response is ~10 strings plus scores, on the order of 500 bytes, so 100,000 × ~500 B ≈ 50 MB/s outbound at peak — comfortably served from cache and CDN edge.

API sketch

GET /autocomplete?q=<prefix>&limit=10&lang=en&region=US
  200: { "suggestions": [
           { "text": "new york times", "score": 98213 },
           { "text": "news",           "score": 87102 }, … ] }
  200: { "suggestions": [] }        # no completions; empty, never an error

# Internal / offline contracts
POST /internal/build-trie          # batch job: rebuild base trie from query logs
  body: { "log_window": "2026-07-02", "min_frequency": 50 }

STREAM query_events                # every submitted search → Kafka topic
  { "query": "…", "ts": …, "lang": "en", "region": "US" }

Solutioning

Read the constraints together and the shape appears. The answer to a prefix is small (ten strings) and, for the vast majority of prefixes, identical across all users and stable across seconds. So the first move is to precompute the answer and cache it, not to compute it per request. At each node in a prefix tree we store the top-10 completions of that prefix, aggregated ahead of time from query-frequency logs. A prefix query then becomes: walk to the node for that prefix and read its precomputed list — no search, no ranking at request time. The reframing that carries the design: a prefix query is not a search problem; it is a lookup of a precomputed answer. Once you see it that way, the two hard questions become "how do we keep that precomputed answer fresh?" and "how do we keep it in fast memory at scale?"

That surfaces the defining tradeoff: freshness versus precompute cost. Building the full 39 GB trie from a day of query logs is a heavyweight batch job — reading billions of events, aggregating frequencies, propagating top-k up the tree — that takes on the order of an hour. You cannot run it every minute, so a purely batch design can never surface a trending term "within minutes." The resolution is a two-tier index: a stable base trie rebuilt every few hours, plus a lightweight real-time layer that counts queries over a sliding window (say the last 10 minutes) from the event stream and merges its trending candidates into results at serve time. The merge adds ~1–2 ms per query; in exchange, a term that spikes shows up within minutes instead of never. Trending, in other words, is not a trie-rebuild problem; it is a streaming-merge problem.

The second tension is memory versus latency. Keeping the whole trie in RAM across a dozen machines gives single-digit-millisecond lookups that fit the 30–50 ms internal budget. Pushing the trie to SSD to save ~10× on memory cost turns each lookup into random disk I/O of 10–20 ms, and once you add network fan-out and the merge step, p99 blows past 100 ms. The load pattern makes RAM the only defensible choice, so we pay for memory and shard by prefix to keep each shard's slice small.

The third tension is personalization versus cache hit rate, and it resolves the same way every time. A globally cached prefix result is shared by everyone, which is what buys the 95% hit ratio and the 20× load reduction from 100k to 5k QPS. The instant you rank per user — reorder by this person's history — every result becomes unique, the cache hit ratio collapses toward zero, and all 100k QPS slam the backend. So personalization must stay cheap: fetch the globally cached top-k candidate set, then re-rank that small set against the user's recent searches in a thin per-user step, rather than maintaining a per-user index. Personalization is not a re-indexing problem; it is a re-ranking problem applied to a shared, cached candidate list.

The result is a system whose read path is a cache lookup backed by an in-memory sharded trie, whose freshness comes from a streaming layer merged in at serve time, and whose personalization is a light re-rank that never touches the shared cache. The following files take each decision down to components (HLD) and then to schemas, algorithms, and edge cases (LLD).