Cruxly › System design › Design Exercises

Search Autocomplete (HLD)

the index has to be wrong on purpose, because right-but-slow loses every time

Prompt: design the autocomplete/typeahead for a search box — as the user types, suggest up to 10 completions, ranked by relevance, in under 100ms, updating on every keystroke.

40 minutes first. The ranking is not the hard part; the hard part is that "under 100ms" rules out almost every honest way to compute relevance.

Applying the four moves: Scope — up to 10 ranked completions per keystroke under 100ms; spelling correction and personalisation are named follow-ups, not the base design. Estimate — every keystroke is a query, so query rate is a multiple of search rate, and the 100ms budget leaves no room to compute relevance at request time. Sketch — a prefix structure (trie) where each node precomputes and caches its own top completions, served from memory. Deep dive — the hard part the prompt names: honest relevance scoring is too slow online, so ranking is computed offline and pushed into those caches, and the real question becomes how stale suggestions are allowed to get.

Scope and the number that dominates everything

In scope: prefix-based suggestions, ranked by a popularity/relevance signal, updated with reasonably fresh data (minutes to hours old, not seconds), personalisation is a stretch goal not the core. Out of scope: full-text search over documents (a different system, usually an inverted index like Elasticsearch — mention it, don't design it), typo tolerance/fuzzy matching as a first-class requirement (name it as a follow-up), spell-correction.

Estimate. Say 1 billion searches/day, and each search triggers roughly one keystroke event per character typed before the user hits enter or clicks — call it 5 requests per search on average.

Autocomplete requests: 5 x 10^9 / 10^5 s ≈ 50,000 requests/s average, ~150,000 peak.
The dominating number is not throughput, it's latency. 100ms end-to-end, and that has to include network round trip, meaning the actual server-side budget is closer to 20-50ms. That number, stated early, is what disqualifies most designs — it rules out anything that scans, joins, or scores at request time.

What the numbers say. This is not a "big data" problem in the volume sense — the query volume is moderate. It's a latency-budget problem, and the entire architecture is downstream of one fact: the read path must do the least possible amount of work, which means the interesting computation has to happen offline, ahead of time.

The budget looks generous until the network is subtracted — what's left is barely enough for a handful of pointer dereferences.

The trie, and why it alone is not the answer

The obvious structure is a trie: each node is a character, and each node caches its own top-K completions (precomputed, not computed by walking the subtree at read time). A request for prefix "san" walks three trie edges and returns the cached top-10 at that node — three pointer dereferences and a return, comfortably inside budget.

Why cache top-K at every node instead of computing it on read: walking the subtree under "san" to find its best completions on every request means the request cost scales with how many completions exist below that prefix — potentially thousands. Precomputing it means the request cost is constant, regardless of how popular or rare the prefix is. This is the single design decision the whole system hangs on, and it directly costs freshness: the top-K at a node is only as current as the last time it was recomputed.

Every trie node stores its own precomputed top-K, so answering "san" costs three edge traversals plus a cache read regardless of how many words start with "san" exist below it.

Building it. Offline, batch job over query logs: count query frequency, decay older counts (a query popular last month but not this week should fade), and for every prefix of every popular query, propagate that query into the prefix's top-K if it's high-scoring enough to displace what's there. This is the expensive part, and it's expensive offline, which is exactly where you want expensive work to live.

Serving at scale — sharding, caching, and freshness

One trie does not fit on one machine past a certain vocabulary size, especially with rich metadata per node. Shard by prefix range (a-f, g-m, ...) so a query for "san" always routes to the same shard, and replicate each shard for read throughput and availability — this is a straightforward read-replica problem once sharded, not a novel one.

A load balancer or thin routing tier maps the first character(s) of the query to a shard, then that shard's replicas serve the read. The mapping is small and nearly static, so it can be cached at every routing node with a long TTL and a simple invalidation-on-resharding path.

Cache in front of the trie, keyed by prefix. Even though the trie read is already fast, the most popular prefixes ("a", "the", "how") are hit disproportionately, and serving them from an in-memory cache in front of the trie shaves off even the trie-walk cost for the hottest keys — classic hot-key behaviour, handled the same way it's handled everywhere else in this track.

Freshness is a deliberately loose SLA. Rebuilding the whole trie every few hours (or incrementally updating hot prefixes more often, cold ones less) is fine, because "what's trending in the last 10 minutes" and "a stable top completion" are different products. If real-time trending is a requirement (a breaking-news search spiking in the last few minutes), that needs a separate, smaller, faster-updating structure layered on top — a hot-trending overlay checked before falling back to the base trie — rather than trying to make the whole multi-gigabyte structure update in real time. Naming that split, instead of promising the impossible ("the whole index updates instantly"), is the signal.

Personalization, if pushed on: the base ranking stays global and precomputed; a thin per-user re-ranking pass (boost the user's own search history matches to the top, if any exist) runs at read time over the already-small candidate set (10-20 candidates from the trie), which keeps it inside the latency budget because it's re-ranking a handful of items, not searching from scratch.

The overlay isn't a hack bolted onto the trie — it's a separate, much smaller structure that gets checked first precisely because it can update far faster than a multi-gigabyte index ever could.

Failure modes and the honest edge cases

Cold/rare prefixes. A prefix nobody has searched has an empty or thin top-K. Falling back to a broader signal (a spell-correction-adjacent "did you mean" or just showing nothing) is fine — an empty autocomplete result is a legitimate, common case, not a bug to route around at cost.

A shard goes down. That range of prefixes serves degraded (no suggestions, or stale replica data) rather than the whole system failing — this is the direct payoff of sharding by prefix range: the blast radius of one shard's outage is exactly the prefixes it owns, nothing else.

Popularity drift and abuse. A coordinated bot campaign searching a phrase repeatedly could inject it into top-K. Worth naming: the ingestion pipeline needs the same kind of rate-limiting-per-source and anomaly detection that any user-generated-ranking-signal system needs (the same principle as review-bombing or upvote manipulation elsewhere) — this is a real production concern that a from-scratch design conversation often skips, and naming it unprompted is exactly the kind of thing that reads as having operated a system like this.

Case, unicode, and locale. Prefix matching on raw bytes breaks for anything beyond ASCII case-folding. Normalize (lowercase, strip diacritics per a defined locale rule) at both index-build time and query time, consistently — a mismatch between how the index was built and how a query is normalized silently returns nothing, which is a bug that only shows up for non-English users and is easy to miss if the interview (and the interviewer) defaults to English examples.

Sharding by prefix range doesn't just distribute load — it also contains failure, which is worth stating as a deliberate second benefit of the same decision.

How to say it in the interview

"The 100ms budget is the whole design. It rules out querying a live index at read time for anything expensive, which means the ranking has to be computed ahead of time and the read path has to be almost embarrassingly simple — a prefix lookup into something precomputed."

Checklist

Identified the latency budget, not query volume, as the number that determines the whole architecture
Chose to precompute top-K at every trie node rather than compute it from the subtree on read
Put the expensive ranking computation offline, in a batch job over query logs
Sharded the trie by prefix range and replicated each shard
Added a prefix-keyed cache in front of the trie for the hottest queries
Named freshness as a deliberately loose SLA rather than promising real-time updates
Proposed a separate small fast-updating overlay for real trending, layered on the base trie
Kept personalization as a thin re-rank over the small candidate set, not a per-user index
Named ranking-signal abuse (bots inflating a phrase's popularity) as a real production concern
Flagged normalization consistency between index-build time and query time

Practice this interactively