Design Search Autocomplete

MediumSearch & DiscoveryTrieCachingStream ProcessingLow Latency

Problem

Design the typeahead box for a large search engine. As a user types, the service returns the top 10 most popular completions for the current prefix. Suggestions must appear within about 100 ms of each keystroke so they keep pace with typing. The engine serves 5 billion searches per day, and suggestions should reflect trending queries within an hour. Offensive or unsafe suggestions must be filtered out.

  • Are suggestions global, or personalized by user history and location?
  • How many languages and scripts must we support?
  • How fresh is fresh enough: an hour, or minutes for breaking news?
  • Do we match only prefixes, or also words in the middle of a query and misspellings?
  • How many suggestions does the UI show, and on which devices?
  • Is there a policy team that maintains a blocklist we must honor?

Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.

  • Return up to 10 completions ranked by popularity for any typed prefix.
  • Update rankings so trending queries appear within an hour.
  • Filter offensive, dangerous, and legally removed suggestions.
  • Boost suggestions that match the user's country and language.
  • Blend in the user's own recent searches at the top of the list.
  • Tolerate small typos in the prefix for longer inputs.

Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.

  • 5 billion searches per day, about 58,000 per second, peaking near 150,000.
  • End-to-end latency under 100 ms; server time under 10 ms at p99.
  • Each search produces about 6 keystroke requests after debouncing, so suggestion traffic peaks near 900,000 requests per second.
  • Highly available: a missing suggestion box is tolerable briefly, but errors on every keystroke are not.
  • The index covers about 1 billion distinct queries per language region after pruning rare ones.

Query logs are aggregated offline (with a streaming layer for recent trends) into a ranked prefix index in which every prefix node stores its precomputed top completions. The index is shipped as an immutable snapshot to a fleet of in-memory serving nodes sharded by prefix, so a lookup is a single memory read. Browsers, CDN edges, and the serving tier all cache short prefixes, which absorb most of the traffic.

Loading diagram...

Serve a suggestion. After a short debounce (about 50 ms of no typing), the browser requests GET /suggest?q=new%20yo&lang=en&cc=US. Short prefixes hit the CDN, which caches responses per prefix, language, and country for a few minutes. On a miss, the suggestion service routes to the shard that owns the prefix, reads the node's precomputed top list, merges in the user's matching recent searches, and returns 10 strings.

Build the index. Every hour, the batch aggregator counts completed searches from the past several weeks with exponential time decay. The index builder drops queries below a frequency threshold, applies the blocklist, constructs the prefix index with top-K lists per node, and writes a versioned snapshot.

Pick up trends. The streaming trend detector compares the last 15 minutes of query counts to a baseline and emits queries that are spiking. These are merged into the next snapshot, or, for urgent news, pushed as a small overlay that serving nodes merge with the base index.

Deploy a snapshot. Serving nodes download the new snapshot, load it into memory alongside the old one, and atomically switch over. A rollback is a switch back to the previous version.

Stateless front tier that parses the request, routes to the right shard, and merges results.

  • C++ or Go for predictable sub-millisecond latency.
  • gRPC between the service and index shards.

API

  • GET /suggest?q=&lang=&cc= returns { suggestions: [string] } with Cache-Control: max-age=300 when no user history is merged.

Scalability

The service is stateless and scales horizontally. Personalized responses are not cacheable at the CDN, so personalization is applied client-side for logged-out users and server-side only for logged-in users, keeping most traffic cacheable.

Tradeoffs

Debouncing on the client and caching at the edge cut request volume by an order of magnitude. Sending a request on every keystroke without debounce would feel slightly more responsive but would multiply load for little visible gain.

In-memory data structure that maps any prefix to its top completions in one lookup.

  • A compressed trie (radix tree) or a finite state transducer, memory mapped from the snapshot file.

Diagram

Loading diagram...

Data Model

  • Node: { edge label, children, topK: [(completion id, score)] }.
  • Completion table: completion id -> query string stored once and shared by all nodes.

Scalability

Shard by prefix range (for example by the first two characters, then split hot ranges like th further). Each shard is replicated across several nodes for throughput and availability. Storing completion ids instead of strings in each node keeps a billion-query index within tens of gigabytes per region.

Tradeoffs

Precomputing the top 10 at every node trades memory and build time for constant-time reads. Computing the top results at query time by walking the subtree would use less memory but would be far too slow for short prefixes, whose subtrees contain millions of queries.

Turns raw search logs into decayed popularity scores.

  • Kafka for the query log.
  • Spark for hourly batch aggregation; Flink for the streaming trend detector.

Data Model

  • query_counts(normalized_query, lang, country, hour, count)
  • query_scores(normalized_query, lang, country, score, updated_at)

Scalability

Queries are normalized (lowercased, whitespace collapsed) and counted with combiners so the shuffle stays small. Only completed searches are counted, not keystrokes, which avoids inflating partial prefixes.

Tradeoffs

A batch plus streaming design keeps the main index cheap to compute and auditable while still surfacing breaking news quickly. Updating the serving trie in place on every search would give instant freshness but would require locking a structure that serves almost a million reads per second.

Removes unsafe suggestions before they can be served.

  • Curated blocklists maintained by a policy team, plus a text classifier for hateful, sexual, or violent completions.

Scalability

Filtering runs at build time, so it adds no serving latency. An emergency removal is pushed as a small deny list that every serving node checks before returning results, taking effect within seconds.

Tradeoffs

Build-time filtering is cheap and thorough but slow to react, so the runtime deny list exists for urgent cases. Running the classifier on every request would catch more novel content but would add latency to every keystroke.

Publishes immutable index builds and rolls them out to serving nodes.

  • Object storage for versioned snapshots and a lightweight coordinator that announces the active version.

Scalability

Nodes pull snapshots in staggered waves so only a fraction of capacity is loading at once. Peer-to-peer fetching between nodes in a region avoids saturating object storage.

Tradeoffs

Shipping whole immutable snapshots makes deploys and rollbacks trivial and keeps serving nodes free of write logic. The cost is that freshness is bounded by the build interval, which the streaming overlay covers.

Related questions