Search Autocomplete

Clarifying the requirements

Start by pinning down what autocomplete actually has to do, because the scope is narrower than candidates assume. The functional core is three things: return the top-k completions for a given prefix, rank those completions by popularity and recency, and update those rankings from real query traffic. You are not building general search; you are returning a short ranked list of strings for a string prefix. Establish k early. Ten suggestions is typical, and capping k is a real lever because it bounds payload size and index node fan-out.

Now separate the read path from the write path, because they have nothing in common. The read path is every keystroke: enormous volume, latency-critical, strictly read-only. The write path is learning which queries are popular: it aggregates query logs and is allowed to be minutes or even an hour stale. Stating this split out loud is half the interview, because it is what lets you precompute. The requirement that suggestions only need to be eventually fresh is a gift; it means ranking never has to happen on the request path.

Then nail the non-functional targets, and put numbers on them. End-to-end latency must sit well under 100ms, the threshold where a UI stops feeling instantaneous; the simulator enforces a server-side p99 of 80ms, leaving the rest of the 100ms budget for the client network round trip. The system must carry massive read volume: a 15,000 requests-per-second baseline that the simulator pushes to 30,000 at peak. It must stay available at 98% or better while individual nodes die, and it must keep replicas spare enough that peak saturation stays at or below 0.9 so nothing redlines. Suggestions can be eventually consistent. There is no per-user write path on the hot route at all.

• Functional: top-k completions for a prefix, ranked by popularity and recency, learned from query traffic.
• Non-functional: server-side p99 under 80ms, 15,000 rps sustained (30,000 at peak), availability at or above 98%, saturation at or below 0.9.
• The read path is gigantic and read-only; the write path (ranking) is offline and may be minutes stale.
• Decisions to surface: k (about 10), minimum prefix length, debounce interval, and rebuild cadence for the index.

Back-of-the-envelope estimation

Begin with request rate, because it drives everything. The baseline is 15,000 completion requests per second. Over a day that is roughly 15,000 times 86,400, about 1.3 billion requests per day. The simulator's workload curve multiplies the baseline by 1.6 at a lunchtime spike and by 2.0 when a query trends, so you must provision for a peak near 30,000 requests per second, not the average. Always size for the peak; the trending-query stage is where naive designs fall over.

Notice where that request count comes from: keystrokes. A search query averages roughly 15 to 20 characters, so if every keystroke fired a request, a single 20-character query would generate 20 requests. Client-side debounce (wait about 150ms after the last keystroke before sending) plus a minimum prefix length (do not query for one or two characters) collapses that to perhaps five to eight requests per query. That single client behavior is a 2-to-4x reduction in server load before the request ever leaves the browser, which is why it belongs in the design even though it lives on the client.

Now size the payload and bandwidth. A response is k completions, say 10 strings of about 20 to 40 bytes each plus light metadata, roughly 300 bytes of content, call it 0.5 to 1 KB with JSON and headers. At a 30,000 rps peak that is 15 to 30 MB/s of egress, about 120 to 240 Mbps. Requests are tiny, just a prefix and headers. This is comfortably within a small fleet's NICs; bandwidth is not the constraint here, latency and request rate are.

Size the index next, because it decides whether the suggestion data fits in memory. Even a large product accumulates only hundreds of millions of distinct historical queries, and you keep only those worth suggesting, the ones above a popularity threshold, perhaps the top 10 million queries and prefixes. Stored in a compact prefix structure (a trie, ternary search tree, or finite-state transducer) with precomputed top-k lists, that is on the order of 1 to 5 GB. A modern server has 64 to 256 GB of RAM, so the entire suggestion index fits in memory on a single box, which is exactly why the reference keeps it as one in-memory index node rather than a database.

Finally, size the hot-prefix cache and the offline pipeline. Query popularity follows a Zipf-like power law: a tiny head of prefixes absorbs the overwhelming majority of traffic. Caching the top roughly 100,000 prefixes at about 1 KB each is only about 100 MB of memory, and it captures well over 90% of requests, which is what makes a 95%-plus cache hit ratio realistic rather than aspirational. The offline side ingests those 1.3 billion query events per day into a stream, aggregates counts with workers, and rebuilds the index on a cadence of roughly 10 to 60 minutes; eventual freshness means you never pay that cost online.

High-level architecture

The architecture has two halves that meet only through an immutable index artifact: a read path optimized to do nothing but look up from memory, and an offline build path that does all the thinking. Keeping them decoupled is the central idea.

On the read path, a keystroke flows from the client through an API gateway, into a stateless suggest service, which checks a top-query cache, and only on a cache miss touches the in-memory suggestion index. Map these directly to the simulator's components. The client is the keystroke source, debounced and capped. The API gateway terminates and routes requests and is replicated so one death does not drop traffic; the reference runs 2 replicas at 60,000 capacity each. The suggest service ranks and returns the top completions for a prefix and is the part you scale out with replicas; the reference runs 6 replicas at 9,000 capacity each, for 54,000 rps of headroom. The top-query cache serves the hottest prefixes from memory at a 0.96 hit ratio. The suggestion index is the prefix or trie structure of last resort, with a capacity of 20,000, that the cache shields from the firehose.

Why a cache in front of an already-in-memory index? Because the index is a single logical resource and the cache is what keeps the request volume that reaches it small enough to be cheap and safe. The cache also gives you a cheap replication surface for hot keys. The gateway exists for auth, routing, rate-limiting, and as the replicated front door that survives a node loss. The suggest service is stateless on purpose: it holds no session, so you scale it horizontally just by adding replicas behind the gateway, and a dead replica is invisible to users as long as the others have headroom.

The offline build path is the other half. Raw query logs land in a durable stream (think Kafka). A fleet of aggregation workers (Flink, Spark, or a MapReduce job) counts query frequencies over a rolling, time-decayed window so recency matters, applies a popularity threshold, computes the top-k completions for every prefix, and serializes the result into a compact immutable trie. That artifact is shipped to every serving node, which swaps it in atomically. The read path never aggregates, never ranks, never computes a popularity score in real time; it only reads a precomputed answer. This is the single most important structural decision in the design and the one the rubric rewards most.

One deliberate omission: there is no database on the hot path. A relational LIKE 'prefix%' query per keystroke, or a full-text engine query per keystroke, would be correct in spirit but melts under this volume; the simulator scores the LIKE approach at zero and the full-text approach as merely workable but heavier and slower than a purpose-built prefix index. The lesson is that the data structure, an in-memory prefix index, is the design, and everything else is plumbing to keep it fed and shielded.

Deep dive: the cache hit ratio is the whole game

The most important number in this entire system is the cache hit ratio, and it is worth proving why. The suggestion index has a fixed serving capacity; in the reference it is 20,000 requests per second. The cache sits in front and absorbs the head of the popularity distribution. Whatever fraction of requests the cache misses falls through to the index. So, when the tiers ahead of the cache are sized to pass the peak through, the index load equals peak request rate times (1 minus hit ratio).

Run the numbers at the 30,000 rps peak, assuming the gateway and suggest tiers are provisioned to deliver that peak to the cache, as the reference's 54,000-rps suggest tier is. With the reference hit ratio of 0.96, the index sees 30,000 times 0.04, which is 1,200 requests per second against a capacity of 20,000: a utilization of about 0.06, essentially idle. Now drop the hit ratio to 0.70, the value the under-tuned starter design hands you, and the index sees 30,000 times 0.30, which is 9,000 requests per second. Pointed at the starter index capacity of 6,000 that is a utilization of 1.5: the index is overloaded, it drops one in three of the requests that reach it, and queues the rest. The starter is in fact doubly broken, because its 12,000-rps suggest tier also caps out below the peak and sheds load upstream, but the hit-ratio lever alone is enough to melt the index. That single parameter is the difference between an idle index and a melted one.

Latency makes this even sharper, because the simulator models per-node latency as a base cost multiplied by a queueing factor of 1 divided by (1 minus utilization), with utilization capped at 0.95 so the factor maxes out at 20x. At 0.06 utilization the index queueing factor is about 1.06, so its roughly 14ms base latency stays near 15ms. At 1.5 utilization the factor is pinned at its 20x cap and the index latency balloons to nearly 300ms, dragging the whole critical-path p99 far past the 80ms target. The cache hit ratio does not just protect availability; it is the dominant lever on tail latency, which is why the latency SLO carries the heaviest weight in scoring.

This is also where the hot-key problem lives, and autocomplete has a beautiful answer to it. The simulator's worst moment is the trending-query stage, where everyone types the same thing and the load factor hits 2.0. In most systems a single hot key is a nightmare because it concentrates load on one cache entry or one shard. In autocomplete it is the opposite: a trending query is the single easiest thing in the world to cache. It is one key, it is read-only, and it is requested so often that it is essentially always a hit. A trend pushes the hit ratio up, not down. The residual risk is that one cache key becomes a throughput hotspot, and the mitigations are standard: replicate hot entries across cache nodes, keep a tiny in-process cache on each suggest service replica so the hottest handful of prefixes never even leave the box, and let client debounce thin the request stream. Caching the most popular prefixes is explicitly the move the simulator rewards, and refusing to cache (hitting the index on every character) is the move it penalizes, because the cache is what makes the index survivable at this volume.

Deep dive: building and sharding the index offline

The read path is only fast because something else did the ranking ahead of time. That something is the offline build, and getting it right is the second hard part of this problem. The goal is to turn a firehose of raw query strings into a compact, query-ready structure where the top-k answer for any prefix is a direct read.

Aggregation comes first. The 1.3 billion daily query events stream into workers that count occurrences per query. To learn popularity you do not need exact counts; a count-min sketch bounds memory while estimating frequencies, and a rolling window with time decay lets recency tilt the rankings so yesterday's news fades and today's trend rises. You apply a popularity floor to discard the long tail of one-off queries that no one would want suggested. Then, for each node in the prefix structure, you precompute and store its top-k completions, sorted by the popularity-plus-recency score, so serving never has to sort or aggregate.

The serving structure itself is a trie or one of its compact cousins. A naive trie stores top-k at every node, which is memory-heavy; production systems use a finite-state transducer or a double-array trie to share suffixes and shrink the footprint into the low gigabytes that fit in RAM. The build job serializes this into an immutable artifact and ships it to every serving node, which loads it and atomically swaps from the old version to the new one. Immutability is what makes this safe under high read concurrency: readers never see a half-updated index, and rollback is just keeping the previous artifact. Rebuild cadence trades freshness against cost; every 10 to 60 minutes is plenty given the eventual-freshness requirement.

Scaling beyond one box brings in sharding, and autocomplete has a clean sharding story most read systems envy. Shard the index by prefix: route all prefixes beginning with a given letter or two-character pair to the shard that owns them. Because a prefix maps deterministically to exactly one shard, and that shard holds the complete top-k for everything under it, a request hits a single shard and gets its full answer with no scatter-gather. Compare that to sharding by hash, which spreads load evenly but forces every prefix query to fan out to all shards and merge, multiplying request count and tail latency. The simulator models a single index node, but in an interview you should reach for prefix-range sharding and call out its one weakness, that a popular prefix range can become a hot shard, mitigated by splitting hot ranges finer or, again, by leaning on the cache that sits in front of all of it.

Bottlenecks under load and how to scale them

Under the simulator's escalating load and scripted failures, four bottlenecks emerge in order, and each maps to a concrete scaling move. Walking them in order is how you turn the under-tuned starter into the reference design.

The first and worst is the index melting when the cache hit ratio is too low. The fix is two-pronged: raise the hit ratio (the starter's 0.70 must climb toward 0.96) so the index sees a trickle instead of a flood, and raise the index capacity (from the starter's 6,000 toward 20,000) so even the trickle has headroom. Together these take index utilization from an overloaded 1.5 down to about 0.06 at peak. This is the highest-leverage change you can make.

The second is the suggest service queueing under load. The simulator's queueing penalty grows as utilization climbs: at 0.5 utilization latency roughly doubles, at 0.8 it is 5x, and past 0.95 it is capped at 20x. The reference provisions 6 replicas at 9,000 capacity for 54,000 total, so at the 30,000 peak the service runs at about 0.556 utilization, a queueing factor near 2.25 that keeps its 10ms base around 22ms. The starter's 3 replicas at 4,000, for 12,000 total, is already over capacity at the 15,000 baseline and collapses entirely at peak. The lever is replica count, sized so utilization stays comfortably below roughly 0.6; the saturation SLO at 0.9 is the guardrail that forces this headroom.

The third is availability when nodes die. The simulator kills a service replica mid-spike (at the 1.6x lunchtime stage) and a gateway replica near the end (at peak), each outage lasting six seconds. Replication is the entire defense: with 6 service replicas, losing one at the 1.6x load leaves 5 times 9,000, or 45,000 capacity, against 24,000 of demand, so not a single request drops. With 2 gateway replicas, losing one at peak leaves 60,000 capacity against 30,000 of demand, again no drops. This is why the reference keeps both the gateway and the suggest service replicated, and why availability holds at essentially 100% even through the chaos, comfortably above the 98% target.

The fourth is the index latency spike, the simulator's deliberate reminder that even a shielded index can slow down. At the trending stage the index takes an 8x latency multiplier for six seconds. The cache is what saves you, and the mechanism is precise: because the cache holds index utilization near 0.06, the queueing factor stays around 1.06, so the 8x lands on a near-idle 14ms base and produces roughly 119ms, painful but bounded. Had the index been redlined instead, that same 8x would have compounded with the capped 20x queueing factor and produced multi-second latency. On top of that, the latency SLO scores the median of per-tick p99 samples, so a six-second spike in a 35-second run barely moves the graded number. And in the real system the cache means only about 4% of users ever touch the slow index at all. The structural lesson is that the cache does not just cut average load; it contains the blast radius of an index-side problem. If index slowness were chronic rather than transient, the answer would be more index replicas or shards, but the cache buys you the time to react.

• Raise cache hit ratio toward 0.96 and index capacity toward 20,000: index utilization drops from 1.5 to about 0.06 at peak.
• Provision the suggest service near 6 replicas at 9,000 so utilization stays near 0.556, keeping the queueing latency penalty around 2.25x.
• Keep the gateway at 2 replicas and the service multi-replica so a single node death is fully absorbed with zero drops.
• Lean on the cache to contain transient index latency spikes; the latency SLO is a median, robust to brief chaos.

Key trade-offs and what to defend in the interview

The defining trade-off is where the prefix lookup lives. An in-memory trie is fast and cheap to read but requires an offline build pipeline and tolerates staleness. A relational LIKE 'prefix%' query per keystroke is trivial to build but collapses under keystroke-level read volume and is the wrong answer (the simulator scores it zero). A full-text search engine query per keystroke works and is sometimes chosen for its flexibility, but it is heavier and slower than a purpose-built prefix index, so it is a compromise, not the target. Lead with the trie and explain that you are buying read speed and predictability at the cost of an offline build and eventual freshness, which the requirements explicitly permit.

Freshness versus cost is the second axis. Rebuilding the index more often makes trends surface faster but burns more compute and ships more artifacts; rebuilding every 10 to 60 minutes is the usual sweet spot, and you can layer a fast path that injects truly viral queries sooner without waiting for the full rebuild. The third axis is responsiveness versus load: aggressive client debounce and a minimum prefix length cut request volume 2-to-4x but add a little lag and withhold suggestions for very short prefixes; capping k bounds payload and index work at a small cost to suggestion breadth. These are cheap wins and the simulator rewards debouncing explicitly.

The fourth axis is sharding strategy: prefix-range sharding gives single-shard reads with no scatter-gather but risks a hot shard on a popular range, while hash sharding balances load but forces fan-out and merge on every query. For autocomplete, prefix-range almost always wins because the cache absorbs the hot ranges. The last axis, which you should name even though it is out of scope here, is personalization: blending per-user history into rankings improves relevance but shatters the shared cache, because a prefix no longer has one global answer. The standard compromise is to serve the globally popular completions from the shared cache and the index, then optionally re-rank a small candidate set with lightweight per-user signals, preserving the cache hit ratio that the entire system depends on.

• In-memory trie versus DB LIKE versus full-text engine: the trie wins on read speed and predictability; DB LIKE melts (scored zero); full-text works but is heavier.
• Freshness versus cost: rebuild every 10 to 60 minutes, with an optional fast path for viral queries.
• Responsiveness versus load: debounce and minimum prefix length cut requests 2-to-4x; cap k to bound payload and index fan-out.
• Prefix-range sharding (single-shard reads, hot-shard risk) versus hash sharding (balanced, but scatter-gather); personalization trades relevance for cache hit ratio.