Design a Search Autocomplete System

Autocomplete looks trivial from the outside, you type a letter, a dropdown appears. But underneath it requires a data structure that answers prefix queries in microseconds, a ranking model that surfaces the most relevant suggestions, a caching hierarchy that absorbs a 10× read spike, and a pipeline that keeps scores fresh without rebuilding from scratch every hour.

The interviewer is probing whether you can reason about the tension between query-time latency (the user notices anything over 100ms) and data freshness (yesterday's trending topic should appear today). These two goals pull in opposite directions: freshness pushes toward more frequent updates, which strain a live trie; latency pushes toward aggressive caching, which delays propagation of new trends.

Before any architecture discussion, establish what the system actually needs to do. These answers determine almost every architectural decision that follows.

Functional requirements

Non-functional requirements

With 100M DAU and 3 searches per user per day, each search session generates roughly 3 autocomplete API calls (after client debouncing removes redundant mid-word keystrokes). The write side, ingesting query events to update scores, is a fraction of the read side.

Client applies a 150–300ms debounce before sending each request, preventing a separate API call for every keystroke and cutting effective QPS by 3–5×.

CDN Edge caches the top-k suggestions for the most common prefixes (typically 1% of all prefixes account for 80%+ of traffic). A TTL of 60 seconds balances freshness against hit rate; trending prefixes get a shorter TTL or explicit invalidation.

API Gateway handles TLS termination, rate limiting per user/IP, and load balancing across Query Service instances.

Query Service performs an in-process or Redis-backed trie lookup, merges results from the trending overlay, applies the personalization layer, and returns the final top-k list.

Trie Shards are in-memory data stores holding pre-ranked top-k lists at every trie node. Sharding is by first-character range to distribute load.

Trending Service maintains a "hot prefix" overlay rebuilt every few minutes from the streaming pipeline output. It stores only the delta, prefixes whose scores have changed significantly - to enable fast merges with the base trie.

Stream Pipeline (a durable message queue such as Kafka feeding a stream processor such as Flink) ingests all query events, windowed-aggregates counts per prefix, and emits score updates to the Trending Service.

Query Log DB (an object store such as S3 feeding a columnar analytics warehouse such as BigQuery) retains the full query log for the hourly/daily Trie Builder batch job.

Trie Builder runs as a batch job (a distributed compute engine such as Spark) that recomputes global popularity scores across the full retention window and produces a new serialized trie snapshot that is atomically swapped in.

Architectural rationale

Real-world comparison

Every autocomplete system has one central algorithmic question: how do you find all strings that share a given prefix, quickly? Two primary approaches dominate production systems, and they involve fundamentally different tradeoffs around memory, flexibility, and operational complexity.

Our choice for this system

A trie is the right structure for a general-purpose prefix autocomplete. It maps naturally to prefix traversal, stores exactly one top-k list per node (so no merge is needed at query time for the base case), and fits entirely in memory for a 100M-term corpus. The inverted index approach is preferable when the system also needs fuzzy matching (correcting typos), multi-word completions, or language-specific stemming, capabilities an enterprise search platform like Elasticsearch provides out of the box.

// Each node stores: children map + pre-ranked top-k list
class TrieNode {
  constructor() {
    this.children = new Map(); // char → TrieNode
    this.topK = [];           // [{term, score}] pre-sorted, length ≤ k
  }
}

function query(root, prefix, k = 5) {
  let node = root;
  for (const ch of prefix) {
    if (!node.children.has(ch)) return []; // no completions
    node = node.children.get(ch);
  }
  // O(L) traversal, then O(1) read of the pre-ranked list at the terminal node
  return node.topK.slice(0, k);
}

function insertWithScore(root, term, score, k = 10) {
  // O(L × k log k) per term, build top-k in batch (Trie Builder), not on each live insert
  // Start by updating root (handles empty-prefix queries, e.g. showing global top-k on focus)
  const _upsert = (node) => {
    const existing = node.topK.findIndex(e => e.term === term);
    if (existing >= 0) node.topK.splice(existing, 1);
    node.topK.push({ term, score });
    node.topK.sort((a, b) => b.score - a.score);
    if (node.topK.length > k) node.topK.pop();
  };
  _upsert(root); // root top-k = global top-k for empty prefix ""
  let node = root;
  for (const ch of term) {
    if (!node.children.has(ch))
      node.children.set(ch, new TrieNode());
    node = node.children.get(ch);
    _upsert(node); // update top-k at every prefix node along the path
  }
}

The read side needs one endpoint; the write side (query logging) is fire-and-forget. Both are simple by design, autocomplete latency budgets leave little room for complex server-side logic at the API layer.

GET /v1/autocomplete

Returns top-k suggestions for a given prefix. Uses GET because the operation is idempotent and cacheable , the CDN caches this endpoint by query string.

GET /v1/autocomplete?q=appl&k=5&locale=en-US&session_id=abc123

{
  "prefix": "appl",
  "suggestions": [
    { "term": "apple",        "score": 9.2, "source": "global" },
    { "term": "apple store",   "score": 8.1, "source": "global" },
    { "term": "apple watch",   "score": 7.4, "source": "trending" },
    { "term": "apple iphone",  "score": 6.9, "source": "global" },
    { "term": "apple pie",     "score": 5.3, "source": "personalized" }
  ],
  "served_by": "edge",   // or "origin", for observability
  "latency_ms": 8
}

POST /v1/query-log (async, fire-and-forget)

Clients log completed searches (not every prefix keystroke) to feed the scoring pipeline. This is sent asynchronously after the user submits, it must not block the UI.

// Request
POST /v1/query-log
{
  "query": "apple watch",
  "session_id": "abc123",
  "locale": "en-US",
  "timestamp": "2026-04-01T12:34:56Z",
  "selected_suggestion": true  // did user pick from dropdown?
}

// Response 202 Accepted, do not wait on this

The complexity lies in the caching hierarchy and the fallback behaviour. The freshness NFR from §2 drives the key decision: whether to serve from edge cache or fall through to origin.

Four entities shape the data model, and they are used very differently. Understanding their access patterns first prevents choosing the wrong storage engine or schema.

Entities and access patterns

Two things jump out. First, the trie lookup is by far the hottest read, it must be in memory. Second, the query event log is write-heavy and append-only, which means it belongs in a durable append log (Kafka) feeding an object store, not a transactional database.

Autocomplete is an unusually cache-friendly workload: the same popular prefixes are queried millions of times per hour, results are small (5–10 strings), and the cache key is simply the prefix string plus locale, making cache hits trivially deterministic. The latency NFR from §2 makes caching mandatory - not optional.

Cache invalidation

The hardest part of this cache hierarchy is the CDN layer. Since autocomplete results are cacheable by prefix key (an exact-match query), invalidation is precise, only the affected prefix needs to be purged, not the entire cache. The Trending Service publishes invalidation events to a CDN Purge API whenever a prefix's trending score crosses a threshold. This means frequently-changing hot prefixes get near-real-time updates, while stable prefixes (like "weather") coast on the 60-second TTL.

At L5 and above, the interviewer wants to see how the system holds together under load, during failures, and across regions. The capacity numbers from §3 set the context: ~3K RPS average, ~17K RPS at peak, ~15GB trie in memory.

The same system, described at different depths, distinguishes a junior engineer from a staff engineer. Here is what changes at each level.

Classic probes, level-differentiated answers

During the interview, the interviewer may pivot to probe your knowledge of edge cases and extensions.

freq_score = log(1 + count_90d)

recency_score = log(1 + Σ count_day_i × e^(−λ × days_ago_i))
// λ = 0.1 gives a half-life of ~7 days  [ln(2)/0.1 ≈ 6.93]

score = α × freq_score + (1 − α) × recency_score
// α ≈ 0.6 weights steady popularity over pure recency
// Without the log on recency_score, raw decay sums would dwarf freq_score regardless of α