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?
Engineering 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.