Design Search Autocomplete

Typeahead / Google Suggestions System Design

Overview

Type three letters into Google and a ranked dropdown of completions appears before your finger lifts. That dropdown is a search autocomplete (or typeahead) system: for every keystroke the client fires a query with the current prefix, and the service must return the top 5–10 completions ranked by popularity within roughly 100 ms. At Google scale that prefix query runs across billions of historical search strings, billions of times per day.

The question is labeled "Medium" because the core data structure — a trie — is well-known, but a naive trie doesn't come close to meeting the latency requirement. The key insight that separates an "okay" answer from a strong one is precomputing the top-K completions at every trie node — in a pointer-based trie that's an O(prefix length) walk plus O(1) retrieval; implemented as a flat key-value store it's a single O(1) hash lookup — rather than a full subtree traversal per keystroke. On top of that you need a write pipeline that updates those top-K lists from streaming query logs without slowing the read path, a sharding strategy that handles the enormous cardinality of short prefixes, and an aggressive caching layer to absorb the Zipfian skew of real traffic.

In this walkthrough you will scope the system, size it, pick the right data structure, design the API, draw the read and write paths, and go deep on the three questions that decide whether the design actually works: the prefix structure and top-K precomputation, ranking with near-real-time frequency updates, and sharding and caching the read path at scale.

Functional requirements

• Suggest completions. Given a prefix (the characters typed so far), return the top 5–10 query completions ranked by some notion of popularity.
• Near-real-time popularity. The ranking should reflect recent search trends — a suddenly viral query ("Taylor Swift Eras Tour 2026") should surface in suggestions within minutes; baseline is an hourly rebuild, with an optional 1–5 minute fast lane for trending detection. "Near-real-time" means minutes, not milliseconds or days.
• Multiple languages and locales. Suggestions should be scoped to the user's language (covered as an extension for the interview, but worth naming upfront to show awareness).
• Keystroke-level latency. Every keystroke fires a request; the service must respond in under 100 ms end-to-end from the browser's perspective.

Out of scope (state it): search results ranking, spell correction (extension), ad injection, and personalization beyond global popularity (extension). We own the suggestion list for a typed prefix.

Non-functional requirements

• Latency. Sub-100 ms per suggestion request, measured at the p99. Users type continuously; a visible lag breaks the UX.
• Read-heavy, high throughput. Every keystroke on every Google search is a read. Writes (ingesting new query data) are a fraction of the read volume and happen asynchronously.
• High availability, not strict consistency. A suggestion list that is a few minutes stale is fine. Missing an update for one keystroke is tolerable; serving an error is not.
• Scalability. Billions of queries per day, hundreds of millions to over a billion unique prefixes (English-only to full multilingual coverage).
• Write path decoupled from read path. The write path aggregates query logs and rebuilds/updates the trie. It must not block, slow, or corrupt the live read path.

Estimations

State assumptions; the goal is to justify data-structure choices and infrastructure sizing, not exact arithmetic.

Rounded assumptions

• Daily active users: ~1 billion.
• Searches per user per day: ~5 → ~5 billion searches/day.
• Keystrokes per search: ~5 on average (users start getting useful suggestions fast) → ~25 billion prefix queries/day.
• Peak reads/sec: 25B / 86,400 ≈ ~300K reads/sec, with a 3–5× peak multiplier → ~1M reads/sec at peak.
• Unique prefix strings: ~100–300M for English-only; well over a billion across all languages. Traffic is extremely Zipfian — the top few thousand prefixes ("a", "ap", "app", "the", "how to", …) absorb the large majority of traffic.
• Top-K list size: K = 10 completions per prefix node; ~100 bytes each with metadata → 1 KB per node.
• Trie size (top-K precomputed, English only): ~100–300M unique prefixes × ~1 KB ≈ 100–300 GB — cannot fit in a single machine's RAM; must be sharded. Full multilingual coverage (over a billion prefixes) pushes into the TB range and requires proportionally more shards.
• Write volume: query logs at ~5 billion searches/day → ~60K raw events/sec → stream-aggregated into prefix→count updates ~hourly or on rolling windows.

How the numbers affect the design

Core entities / data model

Four things are stored: the trie/prefix store (the indexed completions), the query log (raw events from users), the aggregated counts (per-prefix popularity signal), and an optional trending/decay score for recency-aware ranking.

The PrefixNode is the heart of the system: for any prefix a user types, a single point lookup on this store returns the top-K completions pre-sorted by score. It is a derived entity — rebuilt from PrefixCount — and can always be reconstructed from the raw logs.

The QueryLog is the source of truth. Every submitted search is appended here. The aggregation pipeline reads from it to compute counts; if a count table is lost or corrupted, it is rebuilt from the logs.

Trie vs. flat prefix table. In production, the conceptual trie is implemented as a flat key-value store keyed on the full prefix string — see Deep Dive 1 for the full reasoning and lookup complexity analysis.

API design

Two endpoints carry the product: the suggest read endpoint (called on every keystroke) and an internal ingest write endpoint (called from the aggregation pipeline, not by users).

Suggest completions

GET /api/suggest?q=app&locale=en&k=10
200 OK
Returns: {
  "prefix": "app",
  "suggestions": [
    { "completion": "apple", "score": 9847321 },
    { "completion": "apple store", "score": 7654210 },
    { "completion": "applebee's", "score": 3102944 },
    ...
  ]
}

q is the typed prefix (URL-encoded). locale scopes results to a language/region. k defaults to 10. Served from cache; if the prefix is not cached, falls through to the distributed prefix store. Response time must be under 100 ms end-to-end including network.

Update prefix top-K (internal, write path)

POST /internal/prefix-update
Body: {
  "prefix": "app",
  "updates": [
    { "completion": "apple", "delta": 1204 },
    { "completion": "application", "delta": 832 }
  ]
}
204 No Content

Called by the aggregation pipeline, never by clients. Applies count deltas and recomputes the top-K list for the prefix. Can be batched: one call updates many completions at once. Rate-limited and asynchronous relative to user reads.

High-level architecture

The system has a fast read path (prefix → cached suggestions), a batched write path (query logs → stream aggregation → trie rebuild/update), and a combined view. We'll walk each, then combine them.

1. Read path

Every keystroke hits the read path. The goal is to make it hit an in-memory cache as close to the user as possible.

flowchart LR
    Client["Client (browser)"] -->|"GET /suggest?q=app"| Edge["CDN / Edge Cache"]
    Edge -->|"cache hit: top-K list"| Client
    Edge -.->|"cache miss"| SuggestSvc["Suggest Service"]
    SuggestSvc -->|"lookup prefix 'app'"| LocalCache["Local in-process\ncache (L1)"]
    LocalCache -->|"hit: top-K"| SuggestSvc
    LocalCache -.->|"miss"| PrefixStore[("Distributed Prefix\nStore (Redis / KV)")]
    PrefixStore -->|"top-K list"| SuggestSvc
    SuggestSvc -->|"suggestions"| Client

1. The browser sends GET /suggest?q=app. A CDN or edge cache may serve the response directly from a nearby POP if the prefix is hot enough to be edge-cached.
2. On a CDN miss, the request reaches a Suggest Service node. The service checks an L1 in-process cache (a small LRU cache in application memory, ~100K hot prefixes).
3. On an L1 miss, it reads the distributed prefix store (Redis or similar) — an O(1) key lookup returning the pre-sorted top-K list.
4. The result is returned and backfilled into L1.

The full round trip on a cold prefix is: network latency + Redis lookup (sub-millisecond on a local cluster). With L1 hits for the hottest prefixes, end-to-end under 10ms is realistic.

2. Write path — from query logs to updated top-K

The write path is asynchronous and never touches the read path directly. It processes query events in a stream, aggregates them into updated counts, and then updates the prefix store.

flowchart LR
    Users["User searches\n(billions/day)"] -->|"log events"| Queue[["Query Log Stream\n(Kafka / Pub-Sub)"]]
    Queue --> Agg["Stream Aggregator\n(per-prefix count windows)"]
    Agg -->|"prefix → completion → count (rolling total)"| CountStore[("Count Store\n(Postgres / DynamoDB)")]
    CountStore --> Builder["Top-K Builder\n(batch job, ~hourly)"]
    Builder -->|"write updated top-K\nper prefix"| PrefixStore[("Distributed Prefix\nStore (Redis / KV)")]
    PrefixStore -.->|"read path\nserves from here"| SuggestSvc["Suggest Service"]

1. Every search event is published to a query log stream (Kafka or a cloud pub-sub). The stream is the source of truth for raw events.
2. A stream aggregator (Spark Streaming, Flink, or a simpler cron-driven batch) consumes the stream and maintains rolling-window counts per (prefix, completion) — e.g. how many times "apple" was searched in the last 30 days, broken down by prefix ("a", "ap", "app", "appl", "apple"). The aggregator upserts a running rolling-window total per (prefix, completion), not raw increments — each write to the count store is an absolute count for the current window, not a delta.
3. Aggregated counts are written to a count store (a durable KV or relational table).
4. A top-K builder job runs periodically (hourly or shorter windows) and, for each prefix, recomputes the sorted top-K list from the count store. It writes the result back into the prefix store that the read path queries.
5. Until the prefix store is updated, the read path keeps serving the previous top-K. A few minutes of staleness is fine.

Why batch/stream aggregate instead of updating the trie on every query? A naive write-through approach would increment a counter on every search — potentially millions of times per second for popular completions — and each increment would require atomically updating the top-K list for every prefix of that completion (e.g. searching "apple" touches nodes for "a", "ap", "app", "appl", "apple" — 5 updates per search for an average English query). At billions of searches per day that is billions of trie writes, massively amplified by the per-prefix fan-out. Batching amortizes those writes orders of magnitude more efficiently.

3. Combined architecture

flowchart TD
    Users["Users"] -->|"keystrokes"| CDN["CDN / Edge Cache"]
    CDN -->|"miss"| SuggestSvc["Suggest Service\n(stateless, horizontally scaled)"]
    SuggestSvc -->|"check L1"| L1["L1 Cache\n(in-process LRU)"]
    L1 -.->|"miss"| PrefixStore[("Distributed Prefix Store\n(sharded Redis / KV)")]
    Users -->|"completed searches"| Kafka[["Query Log\n(Kafka)"]]
    Kafka --> Aggregator["Stream Aggregator\n(Flink / Spark)"]
    Aggregator --> CountStore[("Count Store")]
    CountStore --> TopKBuilder["Top-K Builder\n(hourly job)"]
    TopKBuilder -->|"write updated top-K"| PrefixStore

The read and write paths share only the prefix store and never contend: the top-K builder writes new top-K lists atomically (swap the key's value), and readers always see a consistent list (never a partially updated one). The Suggest Service is stateless and horizontally scalable; the prefix store is the only stateful component on the critical path, and it is kept warm by the multi-layer cache.

Deep dives

1. The prefix structure and top-K precomputation

The central data structure question every interviewer will push on: how do you actually store and look up completions?

The trie, and why a naive one fails. A trie stores strings such that every prefix of a string shares a path from the root. A lookup for prefix "app" walks root → 'a' → 'p' → 'p' and arrives at the "app" node. From there, to find the top-K completions you would normally traverse the entire subtree below that node. The subtree for "app" can contain millions of nodes (every string starting with "app"). At 1M reads/sec and 100ms budget, that traversal is impossible.

The fix: precompute top-K at every node. Instead of traversing the subtree at read time, store the sorted top-K list directly at each node. The "app" node holds ["apple", "apple store", "applebee's", ...] pre-sorted. In a pointer-based in-memory trie a read walks O(prefix_length) characters to reach the node, then retrieves the cached list in O(1). The flat key-value implementation (described below) eliminates even that walk — a Redis GET on the prefix string is a single O(1) hash lookup regardless of prefix length.

flowchart LR
    Root["root\n(top-K: ['the','how','what',...])"] --> A["'a'\n(top-K: ['amazon','apple','ask',...])"]
    A --> AP["'ap'\n(top-K: ['apple','apple store','app',...])"]
    AP --> APP["'app'\n(top-K: ['apple','apple store','applebees',...])"]
    APP --> APPL["'appl'\n(top-K: ['apple','apple store','apple watch',...])"]
    APP --> APPE["'appe'\n(top-K: ['applebees','appease',...])"]

Each node stores its own independent top-K list. A 1-character prefix like "a" has a very different top-K list than a 5-character prefix like "apple" (the former is more generic; the latter is nearly exact-match completions).

Flattening to a key-value store. In a distributed system, a pointer-based trie across machines is complex to implement and shard. The simpler equivalent is a flat key-value store where the key is the full prefix string and the value is the serialized top-K list:

"a"     → ["amazon", "apple", "ask me", "abc", …]
"ap"    → ["apple", "apple store", "app", "applebee's", …]
"app"   → ["apple", "apple store", "applebee's", "application", …]
"appl"  → ["apple", "apple store", "apple watch", …]
"apple" → ["apple", "apple store", "apple watch", "apple music", …]

This is semantically equivalent to a trie with precomputed top-K at each node. The lookup is a single key access — Redis GET prefix:app in under 1 ms. Sharding is straightforward: distribute by prefix string (described in deep dive 3).

How top-K lists are built and updated. The top-K builder job (described in the write path) processes this challenge: given a new set of frequency counts for all completions under a prefix, compute the top-K sorted list and write it. For a prefix with many candidate completions, computing top-K is a heap-based O(N log K) operation, where N is the number of distinct completions stored for that prefix in the count store (not a trie-subtree traversal — N is bounded by the count store's cardinality for that prefix). N can be very large for short prefixes (single-character prefixes may have millions of candidate completions), but the builder runs offline and is sharded by prefix range, so no single job scans the entire count store — each shard processes only the prefix range assigned to it. This runs entirely offline, never on the read path.

Storage size. Each prefix entry is at most K completions × ~100 bytes each = ~1 KB. English-only: ~100–300M unique prefixes × ~1 KB ≈ 100–300 GB total. Full multilingual coverage pushes this into the TB range (see Estimations). Both fit in a sharded in-memory store across dozens to hundreds of machines — expensive but standard at Google scale.

Why not skip the trie entirely and use a different data structure?

2. Ranking — frequency, recency, and near-real-time updates

The ranking signal. The score attached to each completion is primarily historical frequency (how many times this query has been searched, ever or in a rolling window), with an optional recency decay to boost trending queries. A simple baseline:

score(completion, prefix) = count(completion, last_30_days)

More sophisticated versions weight recent searches more heavily — a query that surged in the last hour should surface before an equally-counted query that peaked six months ago. A common formula:

score = Σ (count_in_window_t × decay_factor^t)

where decay_factor < 1 (e.g. 0.9 per day) means older counts contribute less. This is called exponential decay or a exponential moving average.

How counts get updated without blocking reads. This is the second major interview question on this topic. You cannot update the top-K list atomically on every incoming search query — the amplification (every search updating O(prefix_length) nodes, for billions of searches) is unacceptable. The write path's job is to decouple this update from the read path:

1. Stream aggregation. Kafka consumers run a stream aggregation over query events, maintaining rolling counts per (prefix, completion) in a lightweight in-memory structure (or a fast KV like Redis). Each aggregator shard handles a partition of the prefix space. Counts are checkpointed to the durable count store periodically.
2. Periodic top-K rebuild. The baseline batch job runs hourly; an optional fast lane (1–5 minute window) handles trending spikes. The time lag from query to suggestion visibility equals the batch interval — "near-real-time" means minutes, not milliseconds.
3. Atomic swap. When the builder writes a new top-K list for a prefix, it replaces the old value atomically. Readers always see either the old complete list or the new complete list — never a partial update. In Redis this is a single SET command.

What about truly real-time updates — can you make it faster? For most prefixes, hourly refresh is fine. For highly trending queries you can run a faster write-path lane: a second aggregation job with a 5-minute or 1-minute window that detects completions whose count is growing anomalously fast. Rather than merging boosts at read time, this fast-lane builder computes a merged top-K — folding the trending completions into the baseline top-K — and writes the result directly into the prefix store under the same key, or into the TrendingBoost store keyed by prefix. The read path is unchanged: it still does a single GET on the prefix key and returns whatever top-K is there, which now reflects the trending-boosted result. This keeps the read path simple while confining all merging logic to the write path.

Personalization (mention as extension in the interview). The score above is a global popularity signal. A personalized version would weight completions that the specific user has searched before, or that match their location or interests. Personalization is harder to cache (different top-K per user × billions of users), so the production approach is to blend a global cached suggestion list with a small, user-specific re-ranking step applied at the edge. Keep this as an "if time permits" extension.

3. Sharding the prefix store, caching, and scale

The cardinality problem. English-only unique prefixes run to ~100–300M (≈ 100–300 GB at ~1 KB each); across all languages the count exceeds a billion, pushing into TB-scale. A single Redis instance holds ~100 GB comfortably; you need a sharded cluster.

Sharding strategy. Distribute prefix keys across nodes by prefix string. Two natural options:

Recommendation: hash-based sharding for even distribution. Arrange prefix keys as opaque strings and distribute by hash. Each prefix lookup hits exactly one shard — no fan-out needed since each prefix is looked up as a standalone key.

Hot prefix shards. Short prefixes ("a", "b", "t", "th", "the") receive vastly more traffic than long prefixes. Even with hash sharding, a small number of keys dominate traffic on their respective shards. The solution is not to make those shards bigger — it is to cache those keys aggressively:

flowchart LR
    Request["GET /suggest?q=a"] --> L1["L1: in-process LRU\n(top ~100K prefixes)"]
    L1 -->|"hit (most traffic)"| Response["top-K returned"]
    L1 -.->|"miss"| Redis[("Distributed Prefix Store\n(sharded Redis cluster)")]
    Redis -->|"hit: top-K list"| L1
    Redis -.->|"miss: return empty/stale"| Response

The L1 in-process cache on each Suggest Service node holds the ~100K hottest prefixes in application memory. A prefix like "a" never leaves L1 — it is touched on virtually every request. For a service with thousands of nodes worldwide, this means the sharded Redis cluster for hot prefixes is queried at a negligible rate; the vast majority of traffic is absorbed by L1 across the fleet. On a Redis miss (a very cold or brand-new prefix), the service returns an empty or stale list — the builder runs on a fixed schedule, not triggered by misses.

Cache TTL and consistency. L1 entries expire after a short TTL (1–5 minutes) and are refreshed from Redis on miss. Redis entries are refreshed whenever the top-K builder writes a new list. A lag of at most TTL + builder-interval (minutes) is acceptable.

Cache stampede on hot prefix expiry. If the L1 entry for "a" expires while millions of requests are in flight, all of them may simultaneously miss L1 and hit Redis. Mitigate with single-flight (one request reloads the entry while others wait) or probabilistic early refresh (XFetch) (pre-refresh the entry slightly before its TTL expires, while it is still being served, so it never actually expires under load). Both techniques are worth naming.

Estimating the shard count. At 100–300 GB of English-only prefix data (TB-scale for multilingual), a cluster of 50–200 Redis nodes (each holding a few GB in memory) is sufficient for English; multilingual deployments need proportionally more shards. On steady-state traffic, L1 absorbs the vast majority of reads and Redis ops are a small fraction of the ~1M peak reads/sec — the ~1M figure is a cold-cache or long-tail worst case. Even in that worst case, each of tens of thousands of ops/sec per node is well within Redis's single-node capacity.

Tradeoffs & bottlenecks

• Precomputed top-K at every node vs. on-demand traversal. Precomputation makes reads O(1) (a single hash GET on the prefix key) but requires a write pipeline to maintain every node's list — O(prefix_length) writes per updated completion. The batch pipeline amortizes this cost; real-time updates are too expensive. Storage cost is the price: 100–300 GB for English-only, TB-scale for full multilingual coverage.
• Batch vs. stream updates for counts. Hourly batch rebuild is simple and durable but introduces lag. Near-real-time stream aggregation reduces lag to minutes but adds pipeline complexity and operational burden. At Google scale a two-lane pipeline (slow batch for historical accuracy + fast stream for trending detection) is the production answer.
• Global popularity vs. personalization. Global ranking is cheap to cache (one list per prefix for all users). Personalization makes every prefix potentially user-specific, blowing up the cache key space from ~millions (prefixes) to ~billions (user × prefix pairs). The production compromise: serve a global list by default; apply a lightweight per-user re-ranking step at the edge, on the small returned list.
• Hot prefix shards. Zipfian traffic means a few prefix shards take disproportionate traffic. L1 in-process caching solves this for reads; the write path (builder job) must handle popular prefixes without lock contention — write updates atomically via single SET, never read-modify-write under a lock.
• Trie update fan-out. Updating one completion's score triggers updates to all its prefixes (e.g. "apple" → update 5 prefix nodes). For a batch that changes millions of completions, this is hundreds of millions of prefix updates. The builder job must process these efficiently — parallelize by prefix shard, avoid redundant reads, pipeline Redis writes.
• Latency at the edge. Even a fast Redis lookup adds network round-trip latency. Edge caching (CDN for common/stable prefixes) and L1 in-process caching are what push end-to-end latency below 100ms.

Extensions if asked

If the interviewer wants to push beyond the core system, add only the extension that changes the design discussion:

• Typo tolerance and fuzzy matching. When the prefix matches no completions (e.g. "apole"), fall back to an edit-distance search or an n-gram index. A common approach: index completions by their character n-grams; a query with a typo shares most n-grams with the correct completion. This is done on a cold path (not the hot trie), with results merged with exact-prefix results.
• Trending / sudden spike terms. A fast stream lane (5-minute rolling window) detects completions whose count is growing anomalously. Those terms get a large recency boost blended in at read time, even before the hourly rebuild runs. This is what allows a viral event ("Taylor Swift tour 2026") to surface in suggestions within minutes.
• Multi-language and locale. Maintain separate prefix stores per locale or language. The Suggest Service routes to the appropriate shard based on the locale parameter. Cross-locale prefix sharing (e.g. shared English/Spanish completions) is possible but adds complexity.
• Personalization. Blend the global top-K list with a small per-user history re-ranker at the API layer. The user's recent query history is fetched from a user-session store; the global top-K list is re-scored with a personalization weight and the result is returned. The re-ranking step runs on the already-small returned list (10 items), so it adds negligible latency.
• Safe search / content filtering. A blocklist of disallowed completions is applied at read time as a filter on the returned top-K list, not stored in the prefix store itself. This lets you update the blocklist without rebuilding the trie.

What interviewers look for & common mistakes

What interviewers usually reward:

• Recognizing that naive trie traversal fails at scale, and proactively stating the precomputed top-K-at-every-node fix before being asked.
• Clearly separating the read path and the write path. The read path is an O(1) hash GET on the prefix key (flat KV store); the write path is an asynchronous batch/stream pipeline that updates the precomputed lists. They never block each other.
• Justifying the multi-layer cache (L1 in-process → Redis) using the Zipfian distribution: a small number of hot prefixes absorb most traffic and should never leave L1.
• Quantifying the write-path fan-out problem (updating O(prefix_length) nodes per completion × billions of searches/day) and explaining why batching is the only viable answer.
• Naming the sharding dimension (hash on prefix string) and calling out the hot-prefix problem explicitly, then solving it with caching rather than more shards.
• Atomic writes to the prefix store (single SET per key, never read-modify-write) so the read path always sees a consistent list.

Before you finish, do a quick mistake check:

• Did you avoid a subtree traversal per keystroke, and instead state that top-K is precomputed at every trie node?
• Did you separate the read path (O(1) lookup from prefix store) from the write path (async stream aggregation + top-K rebuild)?
• Did you call out the Zipfian distribution of prefix traffic and explain why L1 in-process caching is the primary latency lever?
• Did you quantify the write fan-out (O(prefix_length) updates per completion change) and justify batching the write pipeline?
• Did you name the hot-prefix problem and solve it with caching, not more shards?
• Did you make writes to the prefix store atomic (swap whole top-K list, never partial update)?
• Did you mention at least one extension — typo tolerance, trending detection, or personalization — showing you've thought beyond the happy path?