Design a Search Autocomplete (Typeahead) System
Scenario prompt
Design the typeahead backend behind a search bar with millions of daily users. Requirements:
- p99 latency in the tens of milliseconds — suggestions must feel instant as the user types, keystroke by keystroke
- Suggestions should reflect what's actually popular/trending, not just alphabetically-first matches
- The long tail of rare prefixes needs an answer too, without falling back to a full table scan
- A newly-trending query should start surfacing within minutes, not wait for a nightly batch rebuild
Mihir's attempt
[!todo] Write your own attempt here before reading the model solution below — how you'd serve the common-prefix case in single-digit milliseconds and how you'd get a trending term surfaced quickly without a full rebuild.
Model solution
Precompute top-K suggestions per prefix offline, serve from a fast KV store — don't rank on every keystroke. Ranking candidates live for every request is too slow for a tens-of-milliseconds budget. Instead, a batch job over historical query logs computes, for every prefix worth serving, the top-K most popular completions, and stores prefix -> [top-K results] in Redis or an in-memory trie replicated across serving nodes. A request then becomes a single lookup, not a ranking computation — the same "push cost to write time, keep reads cheap" tradeoff underlying Caching Strategies.
Layer a real-time signal on top for freshness, since batch alone is too slow to react. A pure nightly-batch popularity table means a genuinely trending query (breaking news, a live event) doesn't show up for suggestions until the next rebuild. A second, smaller real-time counter — a stream processor tracking recent query volume per prefix over a short sliding window — gets merged with the batch-computed top-K at read time, boosting anything spiking recently. This two-tier structure (slow-changing bulk data plus a fast-moving recent-signal overlay) is a repeating pattern anywhere "popular" needs to mean both "generally popular" and "popular right now."
Cache aggressively at the edge for the small set of prefixes that get disproportionate traffic. Query volume against prefixes is heavily skewed — a handful of short, common prefixes ("a", "th", "how") account for a large share of all requests. CDN/edge caching (per CDN and Edge Caching) for these high-frequency prefixes keeps the hottest traffic from ever reaching the origin at all, and load balancing across origin replicas (per Load Balancing Algorithms) handles the rest.
Shard the index when it stops fitting one node, and degrade gracefully for the uncached long tail. Once the prefix index outgrows a single node's memory, shard by prefix range across nodes with a thin fan-out/merge layer in front. For rare prefixes with no precomputed entry, fall back to a bounded on-the-fly query against an inverted index (e.g., a prefix query against Elasticsearch) under a strict time budget — and if that budget is exceeded, return no suggestions rather than blocking the search box. A typeahead feature failing open to "no suggestions" is a far better failure mode than a slow or hung search bar.
Gaps to revisit
- Personalization (boosting a user's own query history) alongside global trending, without leaking one user's private query patterns into another user's suggestions
- Filtering offensive or harmful predicted completions without adding enough latency to blow the budget
- Prefix matching breaks down for languages without whitespace-delimited tokens (CJK, etc.) — what does "prefix" even mean there, and does it need a different indexing strategy entirely?
Principal Engineer Lens
The real design tension here is precompute-for-cheap-reads versus compute-live-for-freshness, and the two-tier batch-plus-real-time-overlay solution is a pattern that recurs well beyond search — feed ranking, trending-topics surfaces, and recommendation systems all face the identical "bulk signal is cheap but stale, live signal is fresh but expensive" tradeoff. Being able to name that tradeoff explicitly, and justify why the blend point sits where it does, is a stronger architecture-review answer than either extreme ("just precompute everything" or "just rank live"). This is squarely BigTech-consumer-platform territory — the kind of latency-and-scale problem that shows up at any company running a search or feed surface with millions of daily users.
Reel Script
Setup: Every keystroke in a search box triggers a request, and the response has to feel instant — tens of milliseconds, not hundreds. How do you serve good suggestions that fast, at scale, and still keep them fresh?
Concept walkthrough: Explain why ranking live on every keystroke is off the table at this latency budget, and why the fix is precomputing top-K suggestions per prefix offline and serving a single fast lookup at request time. Then introduce the freshness problem that precompute-alone creates, and the real-time counter overlay that fixes it.
Real example tie-in: Walk through a breaking-news scenario — a query starts spiking right now. Explain why the batch-only version wouldn't surface it until the next rebuild, and how blending a short-window real-time signal into the precomputed top-K solves that without rebuilding everything.
Tradeoffs & alternatives: Contrast the CDN-cached hot-prefix path (cheap, instant, covers most traffic) against the long-tail fallback (a live, budget-capped index query) — and why failing open to "no suggestions" beats a slow search bar when that budget is blown.
Principal Engineer takeaway: Precompute-for-cheap-reads versus live-compute-for-freshness is a tradeoff that shows up everywhere from typeahead to feed ranking — naming it explicitly, and defending where you draw the blend line, is what a strong system-design review answer looks like.