Typeahead Search

What is a typeahead search service?

Every time you type into a search box and suggestions appear before you finish, a typeahead service is running. The real challenge is not storing queries; it is retrieving ranked prefix matches in under 100ms across billions of daily requests, while a background write pipeline refreshes popularity scores fast enough that trending queries surface within minutes. The question tests memory-efficient data structures, distributed caching, and offline aggregation pipelines because read-path latency and write-path freshness pull in different directions.

TL;DR

Serve suggestions from a versioned, compressed Radix-tree snapshot that keeps the top-K results at each prefix. Put a client session cache and a Redis cache in front of the in-memory index so common prefixes avoid the index fleet altogether.

Log completed searches asynchronously to Kafka, aggregate frequency over several time windows, and rebuild the index on a schedule. Add a short-lived per-instance hot-query boost for trends that cannot wait for the next snapshot. Treat the index as a replaceable read-only artifact: stale results are preferable to empty results during a rebuild or cache failure.

Scope and assumptions

The following are illustrative interview planning assumptions, not product specifications or vendor guarantees:

• Approximately 5 billion suggestion requests per day (about 58,000 requests/second on average) and 1 billion unique query strings in the index.
• About 10 million newly observed unique queries per day; completed-search events, rather than every keystroke, feed popularity aggregation.
• The API returns up to 10 suggestions, with a configurable maximum of 20. Global popularity is the ranking signal; personalization, fuzzy matching, and multilingual analysis are separate extensions.
• The end-to-end p99 target is 100ms. The server-side lookup budget is about 20ms after allowing for network, serialization, and cache time.
• Counts are aggregated at least every 60 seconds and the full index is rebuilt about every 5 minutes. A short-lived in-memory trend path may make especially hot queries visible sooner.
• A 99.9% read-path availability target is assumed. Briefly stale suggestions are acceptable, but the service should continue returning a previous snapshot during partial failures.

Functional Requirements

Core Requirements

1. As a user types a prefix, return the top N relevant suggestions in real time.
2. Suggestions are ranked by popularity (query frequency).
3. Results appear within 100ms of each keystroke.

Below the Line (out of scope)

• Full-text search across document bodies
• Multi-language or fuzzy-match suggestions
• Personalized suggestions based on individual user history

The hardest part in scope: Storing prefix-to-suggestion mappings in a structure that supports O(prefix_length) lookups at 58,000 queries per second while keeping popularity scores fresh enough that trending queries surface within 5 minutes. Fast reads and near-real-time write propagation push in opposite directions, and the entire architecture is a negotiation between them.

Full-text search across document bodies is out of scope because it requires inverted indexes over tokenized content rather than prefix matching over query strings. An extension could run a separate document index, then merge and re-rank the two result sets in a blending layer before serving.

Multi-language and fuzzy-match suggestions are out of scope because they require language detection, stemming, and edit-distance calculations that each add latency. An extension could run a fast approximate-match pass using BK-trees or n-gram indexes in parallel with the exact prefix lookup, then merge the results at the suggestion service layer.

Personalized suggestions are out of scope because they require a per-user history store and a real-time re-ranking pass, multiplying storage by the number of active users. An extension could store recent queries in a small per-user Redis hash, blend personal frequency with global popularity using a weighted score, and re-rank the top-20 candidates from the global index at request time.

Non-Functional Requirements

Core Requirements

• Latency: Suggestion response under 100ms p99 end to end. The lookup itself must complete in under 20ms (network, serialization, and Redis each consume their own slice of that budget).
• Scale: 5B search queries per day, 1B unique queries in the prefix index.
• Writes: 10M new unique queries discovered per day; popularity scores updated every 5 minutes for the full corpus, with trending queries surfacing within 60 seconds via an in-memory fast path.
• Availability: 99.9% uptime. Stale suggestions for a brief window are acceptable; missing suggestions for minutes are not.
• Data freshness: Trending queries must influence suggestions within 5 minutes of going viral.

Below the Line

• Perfectly synchronized query counts across all Trie replicas in real time
• Sub-second freshness for newly discovered queries

Read-dominant workload: At 5B queries per day (roughly 58,000 GET requests per second) against 10M new unique query writes per day (roughly 115 per second), the read-to-write ratio is approximately 500:1. The design therefore optimizes the read path first while keeping write freshness within the stated target.

The 100ms budget is end to end from keystroke to rendered suggestion. A typical mobile network round trip may consume 20-40ms, Redis lookup adds about 1ms, and serialization adds 2-5ms in this illustrative budget. That leaves under 20ms for the actual prefix lookup, which explains why a Redis cache in front of the Trie is useful at this scale.

30-second answer / outline

1. Keep the hot read path separate from the popularity write path: client prefix cache, Redis suggestion cache, then an in-memory Radix-tree shard.
2. Precompute the top-K suggestions for each indexed prefix so lookup is proportional to prefix length rather than the size of the matching subtree.
3. Publish completed-search events to Kafka, aggregate rolling 1-hour, 24-hour, and 7-day counts, and write the resulting scores to a query-count store.
4. Rebuild and blue/green hot-swap the read-only index every few minutes; use a short-lived local hot-query boost for trends between rebuilds.
5. State the failure behavior: serve the previous snapshot on rebuild failure, tolerate small ranking divergence across replicas, and replay the durable event stream after consumer failures.

5-minute explanation

Start with the illustrative 500:1 read-to-write ratio. A keystroke should not wait for a database or for a popularity update, so the suggestion service reads a local snapshot and uses Redis only as a cache for common prefixes. A client can often filter a cached parent prefix locally, reducing network traffic further.

The index is a compressed Radix tree. Each node stores a short edge label and a precomputed top-K list, which avoids sorting thousands of descendants on every request. The full snapshot is sharded and replicated in memory; rebuilds happen off the live path and become visible through an atomic blue/green swap.

Completed search submissions go through Kafka rather than mutating the live tree. A streaming or micro-batch aggregator blends short and long time windows, writes scores to Redis sorted sets, and feeds the next rebuild. A per-instance 60-second hot-query map can adjust the returned candidates before the next snapshot, with the explicit trade-off that replicas may rank a trend slightly differently for a short period.

The detailed high-level architecture and critical flows below show how the read path, aggregation path, index rebuild, cache behavior, and failure handling fit together.

45-minute interview approach

This is a time-boxed plan for answering the design question in an interview, not a claim that the article should be read in 45 minutes.

• 0–5 minutes — Clarify the contract: Confirm prefix length, result count, ranking signals, languages, personalization, privacy requirements, freshness, and behavior when no suggestion is available.
• 5–10 minutes — Establish scale: Use the illustrative request rate, unique-query count, new-query rate, response size, p99 target, and read/write ratio. Separate keystroke traffic from completed-search logging.
• 10–15 minutes — Define APIs and data: Walk through the suggest endpoint, completed-search event, query count, prefix index, cache keys, and the maximum indexed prefix length.
• 15–22 minutes — Draw the read path: Show client parent-prefix caching, Redis cache-aside lookup, the Suggestion Service, weighted Trie shards, and the stale-snapshot fallback.
• 22–30 minutes — Deep dive on the index: Compare SQL prefix scans, an uncompressed Trie, and a compressed Radix tree with top-K lists. Do the memory estimate and explain sharding and blue/green swaps.
• 30–35 minutes — Deep dive on freshness: Compare synchronous mutation, local write-behind, and Kafka aggregation. Explain rolling windows, replay, hot-query boosts, and ranking divergence.
• 35–41 minutes — Reliability, security, and operations: Cover cache failure, rebuild failure, Kafka lag, duplicate events, query-log privacy, input limits, abuse controls, and the key latency and freshness metrics.
• 41–45 minutes — Trade-offs and close: Compare client caching versus freshness, full snapshots versus incremental updates, and global versus personalized ranking. Recap the read/write split and invite follow-ups.

Core Entities

• Query: A search string issued by a user. The atomic unit of what we index and count.
• QueryCount: The aggregated frequency of a given query string over a rolling time window. This is the popularity score that drives suggestion ranking.
• Suggestion: A query string enriched with its popularity score, ready to be returned in the suggest API response.
• PrefixIndex: The in-memory data structure (a compressed Radix tree) that maps a prefix string to its precomputed top-K suggestions.

Full schema, indexes, and column types are deferred to the data model deep dive. The entities above are enough to drive the API design and High-Level Design.

API Design

FR 1 and FR 3: Return ranked suggestions for a typed prefix:

# Return the top N suggestions for the typed prefix
GET /v1/search/suggest?q={prefix}&limit=10
Response: {
  suggestions: [
    { query: "netflix", score: 9823410 },
    { query: "new york times", score: 7234109 },
    { query: "near me", score: 5901002 }
  ],
  prefix: "ne"
}

Use GET because this is a pure read. The q parameter is short and URL-safe for typical prefix lengths. limit defaults to 10 and caps at 20 to prevent unbounded result sets. The response echoes the prefix back so clients can discard stale responses if the user has moved on to a longer prefix before the response arrives.

The naive endpoint shape works here. There is no failure mode that demands an evolved shape at the request contract level; the complexity lives inside the service, not at the API boundary.

FR 2 (implicit): Log completed searches for ranking:

# Record a completed search for offline frequency aggregation
POST /v1/search/log
Body: { query: "netflix", session_id: "s_abc", timestamp: "2026-03-29T12:00:00Z" }
Response: { ok: true }

This is a fire-and-forget write. Clients call it after the user commits to a full search, not on every keystroke. Logging only completed searches rather than every prefix keystroke reduces write volume by roughly 5x and filters out noise prefixes that never resolve to an intent. Authentication is out of scope but would add a user_id field here for personalization.

High-Level Design

1. Return top suggestions for a typed prefix

The minimal read path: client sends the prefix, Suggestion Service looks it up in an in-memory prefix index, returns the top-K results.

The simplest design that satisfies FR 1 and FR 3 is a single Suggestion Service with a prefix index loaded into memory. The index internals are treated as a black box here and covered in Deep Dive 1. Keeping the index in-process (not behind a network call) is a deliberate choice: at 58K QPS, even a 1ms network hop to an external index service adds up to 58 seconds of cumulative wait per second across the fleet.

Components:

• Client: Web or mobile browser sending GET /v1/search/suggest?q=... on each keystroke.
• Suggestion Service: Stateless app server. Receives the prefix, traverses the in-memory prefix index, and returns ranked results.
• In-Memory Prefix Index: The prefix lookup data structure. Each prefix maps to a precomputed top-K list of suggestions sorted by score. Lookups run in O(prefix_length) time.

Request walkthrough:

1. User types "ne". Client fires GET /v1/search/suggest?q=ne&limit=10.
2. Suggestion Service receives the request.
3. Suggestion Service looks up the prefix "ne" in the in-memory index.
4. The index returns the precomputed top-10 suggestions for that prefix.
5. Suggestion Service serializes and returns the result to the client.