Design Search Autocomplete: System Design Interview 2026

Search autocomplete has a strict interaction budget: a useful list must arrive while the user is still composing the query. The design is therefore not “put every query in a trie.” It is a pipeline that normalizes text, retrieves a bounded candidate set, enforces privacy and safety policy, ranks for context, and publishes the result without letting stale responses or caches leak information.

This walkthrough assumes the 6-step system design framework and applies it at senior depth. It is Part 9 of a system design series.

Table of Contents

1. The Problem
2. Step 1 - Clarify Requirements
3. Step 2 - Estimate Scale
4. Step 3 - API, Text, and Client Contract
5. Step 4 - High-Level Design
6. Step 5 - Retrieval, Ranking, and Publishing
7. Step 6 - Failure, Regions, and Operations
8. Reference Architecture
9. Common Interview Mistakes
10. Quick Reference
11. Sources
12. Frequently Asked Questions
13. Related Articles

The Problem

Given a partially entered query, return a small ordered list of useful completions. Depending on the product, candidates may come from popular queries, products, artists, locations, commands, or curated navigation targets. Prefix completion, typo tolerance, next-token prediction, and spelling correction are different features with different cost and quality models.

The senior framing has four parts:

• retrieval: find enough plausible candidates without scanning the corpus;
• ranking: combine stable global signals with request context;
• policy: prevent suggestions from exposing private, unsafe, unavailable, or manipulated content;
• interaction correctness: handle Unicode input, IME composition, cancellation, and out-of-order responses.

Precomputation is central, but “no work at request time” is false once locale, inventory, policy, trends, or personalization matter.

Step 1 - Clarify Requirements

Functional questions

• Is matching strict prefix, token prefix, infix, fuzzy, transliterated, or several modes?
• Are suggestions past queries, catalog entities, editorial entries, or a blended set?
• Which contexts affect eligibility or rank: locale, country, product surface, age mode, inventory, or user history?
• What is the minimum prefix length, maximum input length, and returned k?
• May the system show personalized or recent-history suggestions, and can users disable or delete them?
• How quickly must a harmful or legally removed suggestion disappear from every cache?

Non-functional requirements

• Define an end-to-end interaction SLO and a smaller service budget; benchmark by region and device class.
• Return a bounded response under head-prefix load and adversarial input.
• Preserve a last-known-good serving version during build or rollout failure.
• Prevent cross-user cache leakage and avoid retaining raw prefixes unnecessarily.
• Measure quality and safety, not only latency and click-through rate.

The corpus and policy drive the architecture. A product catalog can use approved titles directly; query-log suggestions need aggregation thresholds, privacy review, anti-abuse defenses, and moderation before publication.

Step 2 - Estimate Scale

Use scenario assumptions rather than presenting one company's traffic as fact. Suppose autocomplete receives 50 billion requests per day after client suppression. That averages about 579,000 requests per second, but traffic follows geography, time zones, launches, and head prefixes, so size from measured peaks and cache-miss rate.

Assume 100 million approved candidate strings with an average of 20 Unicode code points. The text alone is already billions of code points. A naive object-per-character trie with top-k strings copied at every node could consume far more than “hundreds of gigabytes.” Estimate:

• encoded text and candidate metadata;
• number of distinct prefixes after normalization;
• node, edge, pointer, allocator, and ranking-list overhead;
• whether top lists store compact candidate IDs or duplicate strings;
• compression from a radix trie or finite-state transducer;
• replicas, simultaneous old/new versions, warmup, and failure headroom.

If a client emits ten requests per completed search, that is an assumption to validate, not a consequence of debounce. IME sessions, paste, deletion, fast typing, mobile latency, and request cancellation all change the ratio.

The build side is not necessarily “a handful of hourly writes.” Aggregation, catalog changes, moderation, deletions, trend updates, and model or policy versions form continuous inputs even if the main serving artifact is immutable between publishes.

Step 3 - API, Text, and Client Contract

Normalize deliberately

Client and server need the same versioned normalization contract:

normalize(displayInput, locale, analyzerVersion)
  -> normalizedPrefix

Unicode normalization such as NFC makes canonically equivalent sequences comparable, but case folding, diacritics, transliteration, tokenization, and compatibility normalization are product and language decisions. Preserve the display form; do not blindly apply NFKC if distinctions matter. Count limits in code points or grapheme clusters intentionally, not bytes by accident.

Public versus private requests

A public, non-personalized endpoint can be cacheable:

GET /v1/public-autocomplete?prefix=ama&locale=en-US&surface=shop

Its cache key must include normalized prefix, locale, market, surface, analyzer version, policy epoch, and snapshot version. Infrastructure must not log raw query strings by default if prefixes may be sensitive.

A contextual or personalized request should be private and normally bypass shared caches:

POST /v1/autocomplete
{
  prefix, locale, surface, requestSequence,
  optionalContextToken
}
 
-> { requestSequence, snapshotVersion, suggestions[] }

The server derives authenticated identity; it does not accept an arbitrary user ID from the body. Return candidate IDs, display text, type, and optional destination metadata rather than making clients reconstruct links from strings.

Client interaction correctness

Debounce or throttle after a tested interval, cancel the previous request when input changes, and render a response only when its sequence and normalized prefix still match current input. Network cancellation is an optimization; the sequence check is the correctness guard.

Do not treat every key event as committed text. W3C UI Events defines composition sessions for IMEs with compositionstart, updates, and compositionend; while composing, the intermediate string may not be a useful search prefix. Support paste, deletion, speech, and handwriting input too.

Client caches must be bounded and scoped by locale, surface, policy/snapshot version, and personalization identity. Clear private entries on logout or account switch.

Step 4 - High-Level Design

flowchart TD
    Catalog[Approved catalogs and entities] --> Build[Candidate and score pipeline]
    Logs[(Governed aggregate signals)] --> Build
    Policy[Safety and policy control plane] --> Build
    Build --> Validate[Validate and canary]
    Validate --> Snapshot[Versioned base snapshot]
    Trend[Moderated trend stream] --> Overlay[(Bounded overlay)]
    Client([Unicode-aware client]) --> Edge[Public head-prefix cache]
    Edge -->|miss or private| API[Autocomplete API]
    API --> Index[(In-memory prefix index)]
    Snapshot -.atomic load.-> Index
    Overlay --> API
    Policy --> API
    API --> Rank[Filter, rerank, deduplicate]

Figure 1. A validated immutable base snapshot supplies candidates; a small moderated overlay adds freshness, while request-time policy and ranking remain bounded.

The base build and online path are decoupled through a versioned artifact. A failed build leaves the last good version serving. The trend overlay cannot bypass safety policy just because it is fresh.

The edge cache serves only public, context-free variants. Personalized history, account context, and sensitive policy dimensions stay behind private caching rules.

Step 5 - Retrieval, Ranking, and Publishing

Prefix data structures

A plain trie walks one edge per normalized symbol. Lookup to the prefix node is O(prefix length), but returning k results is at least O(k), and pointer-heavy nodes can be expensive in memory and cache misses.

A radix tree compresses chains of single-child edges. A weighted finite-state transducer (FST) can share structure and enumerate high-weight completions; Lucene's weighted FST suggester traverses the prefix and then high-ranked paths rather than requiring copied top-k strings on every logical node.

A sorted array or SSTable can binary-search lower and upper prefix bounds. It is simple and compact, though ranking a large range needs extra summaries or a bounded index. Search engines also provide completion fields with analyzers, context filters, fuzzy options, and their own shard trade-offs.

flowchart LR
    Prefix[Normalized prefix] --> Route[Versioned routing directory]
    Route --> Retrieve[Trie, radix tree, FST, or sorted range]
    Retrieve --> TopM[Bounded top-m candidate IDs]
    TopM --> Policy[Policy and availability filters]
    Policy --> Rerank[Contextual rerank]
    Rerank --> TopK[Return top-k]

Figure 2. Retrieval returns more than k candidates so mandatory filtering and a small online rerank can still produce a complete result.

The right answer is not “always trie.” Benchmark memory, build time, lookup latency, fuzzy requirements, and update/publish strategy with the real language mix.

Precomputed top-m, not blindly top-k

Storing a base top list near each retrievable prefix can make the online candidate step cheap. Keep compact candidate IDs and fetch immutable display metadata efficiently. Retrieve m > k because policy, inventory, deduplication, or context can remove candidates.

If every possible prefix stores the same ten IDs repeatedly, memory can dominate. Alternatives include FST path enumeration, shared posting lists, only materializing hot prefixes, or hybrid indexes. Request work remains bounded, but not literally constant.

Ranking and feedback loops

A base score may combine aggregated frequency, recency decay, source quality, catalog authority, locale, and editorial boosts. Query count alone is unsafe:

• previous rankings create exposure and click-position bias;
• bots can manufacture a trend;
• rare queries may identify a person or reveal private intent;
• popular text may be harmful, misleading, illegal, or unavailable;
• optimizing only clicks can reward sensational suggestions.

Apply minimum support and privacy rules before a phrase enters the candidate catalog. Run abuse detection and moderation on both base and streaming inputs. At request time, enforce current policy, region, age mode, inventory, and emergency suppressions before ranking. Use offline evaluation, guarded experiments, diversity, abandonment, reformulation, downstream satisfaction, and safety metrics alongside CTR.

Personalization should rerank a bounded approved set or blend a private source under explicit controls. Never let a private recent query enter a public shared cache or global trend pipeline without governance.

Freshness overlay

The base snapshot has a measured publish cadence. A small streaming overlay holds versioned, expiring candidates for events or inventory changes. Each overlay entry still needs provenance, aggregation, abuse checks, policy approval, locale, score, and TTL.

flowchart TD
    Events[Aggregated recent signals] --> Detect[Trend and change detection]
    Detect --> Guard[Privacy, abuse, and policy gates]
    Guard --> Delta[Versioned expiring overlay]
    Base[Base top-m] --> Merge[Merge and deduplicate]
    Delta --> Merge
    Suppress[Emergency suppression epoch] --> Merge
    Merge --> Result[Eligible ranked candidates]

Figure 3. Freshness is an overlay with the same governance boundary, not an unreviewed bypass around the base build.

If the overlay is stale or unavailable, serve the base and record degraded freshness. An emergency suppression path must reach origin and caches faster than the normal rebuild; long CDN TTLs without purge or edge policy enforcement are unsafe.

Snapshot build and atomic publish

A robust publish sequence is:

1. Freeze governed input versions and analyzer, policy, and model versions.
2. Build partition artifacts plus a manifest, checksums, counts, and compatibility metadata.
3. Validate size, coverage, language mix, policy invariants, known queries, and latency.
4. Load on shadow nodes and canary a small traffic slice.
5. Warm required pages and head-prefix caches.
6. Atomically advance a serving manifest or routing epoch.
7. Retain the previous version for rollback until the new version is proven.

Plan memory for old and new artifacts during rollout. A “read-only snapshot” can still take minutes to download, verify, map, and warm; replicas are operationally simpler than mutable indexes, not free.

Sharding and caching

Raw first-letter sharding is skewed, while hashing the entire prefix can destroy prefix locality and complicate lookup. Common options are:

• replicate shallow, very hot prefixes and route longer prefixes by a fixed routing prefix;
• partition normalized prefix ranges using a versioned directory;
• separate languages, markets, or product surfaces when their corpora and policies differ;
• adapt shard ownership from QPS, memory, and candidate cost, with online migration.

Bound cross-shard fan-out. Elasticsearch's official completion documentation notes a two-phase cost when suggestions span shards, a concrete reminder that “add shards” can hurt the read path.

Cache only approved head prefixes. Use versioned keys, bounded negative caching, admission control, and request coalescing. A cache key missing locale or policy epoch is a correctness bug, not merely a relevance issue.

Step 6 - Failure, Regions, and Operations

Failure modes

• Serving shard loss: route to a warm replica; reload from the verified snapshot if capacity permits. Shed rare-prefix work before exhausting every node.
• Bad or incomplete build: validation and canary block promotion; the prior manifest remains active.
• Partial rollout: every response reports its snapshot version, and the routing epoch prevents mixed-schema requests from reaching incompatible nodes.
• Overlay failure: serve the base, expire stale deltas, and alert on freshness lag.
• Policy emergency: advance a suppression epoch and purge or bypass affected edge entries without waiting for a full build.
• Dependency slowdown: apply deadlines and return a safe base list or empty result; autocomplete must not delay the search box itself.
• Traffic or bot spike: per-origin and per-client limits, prefix-length guards, admission-controlled caching, and bounded fuzzy work protect the service.

Fuzzy matching should normally begin only after enough input and within strict edit-distance, state, and candidate budgets. One-character fuzzy queries can explode work and produce poor suggestions.

Multiple regions

Immutable artifacts replicate well, but relevance and governance are regional. Build global components only from allowed aggregates; publish locale/market partitions under local policy and residency constraints. Regions need local serving copies, caches, and a last-good version even if the central build control plane is unavailable.

Propagate emergency suppressions and deletion obligations with measurable lag. A regional failover must know which snapshot, overlay offset, analyzer version, and policy epoch it is serving. Personalization should degrade to public suggestions rather than reaching across a forbidden data boundary.

Observability

Track:

• end-to-end visible latency, service latency, timeout rate, stale-response drops, and IME-aware request rate;
• edge/client hit ratio by cache class, origin QPS, hot-prefix concentration, and shard fan-out;
• retrieval size, filter attrition, no-result rate, deduplication, and fuzzy-work budget;
• snapshot age, build stage duration, validation failures, canary deltas, load/warm time, and rollback;
• overlay lag, expired deltas, suppression propagation, and policy-version mismatch;
• quality by locale and surface: selection, reformulation, abandonment, downstream success, diversity, and fairness;
• abuse, privacy, and safety guard outcomes using protected aggregates rather than raw prefixes in metric labels.

Define the SLO with cache and context classes. A public cache hit and a private personalized miss have different budgets and failure modes.

Reference Architecture

The reusable pattern is:

Build a governed, versioned candidate artifact; retrieve a bounded set from a compressed in-memory index; apply current policy and context online; publish and cache only with explicit version and privacy boundaries.

flowchart LR
    Inputs[Governed inputs] --> Artifact[Validated immutable artifact]
    Artifact --> Retrieval[Bounded candidate retrieval]
    Context[Policy and request context] --> Online[Filter and rerank]
    Retrieval --> Online
    Online --> Cache[Correctly scoped cache]
    Overlay[Moderated fresh overlay] --> Online

Figure 4. Precomputation removes unbounded work, while current policy and context remain explicit online stages.

This pattern also appears in navigation suggestions, command palettes, entity pickers, related-item panels, and precomputed recommendation candidates.

Common Interview Mistakes

• Treating a pointer-heavy trie with copied top-k strings at every node as memory-free.
• Calling lookup O(1) and ignoring O(prefix length), O(k), normalization, filtering, and network work.
• Assuming a trie is the only option instead of considering radix trees, FSTs, sorted ranges, or a native completion engine.
• Publishing raw or rare query logs as suggestions without privacy, moderation, or anti-abuse gates.
• Ranking only by popularity or CTR and ignoring exposure bias, bots, availability, and safety.
• Using one fixed debounce interval, ignoring IME composition, or letting an old response overwrite a newer prefix.
• Putting personalized results in a shared CDN cache or omitting locale and policy epoch from the key.
• Rebuilding “hourly” without measuring build time, freshness needs, artifact load, dual-version memory, or rollback.
• Hashing arbitrary prefixes without explaining routing, shallow-prefix replication, or cross-shard fan-out.
• Calling multi-region trivial while ignoring regional policy, data residency, deletion, and emergency suppression.

Quick Reference

Sources

• Apache Lucene 10.1 weighted FST suggester - prefix traversal followed by ranked path enumeration.
• Elasticsearch completion suggester - in-memory completion structures, analyzers, fuzzy options, contexts, and cross-shard cost.
• Unicode Standard Annex #15: Normalization Forms - canonical and compatibility normalization semantics and cautions.
• W3C UI Events: composition events - IME composition session and event ordering.

Frequently Asked Questions

Why use a trie for search autocomplete?

A trie or radix tree reaches a prefix in work proportional to the normalized prefix length, but it is not the only valid index. A weighted finite-state transducer can compress shared structure and enumerate high-weight paths, while a sorted array can use prefix range lookup. Choose from memory, build cost, update model, fuzzy matching, and the candidate count needed for policy filtering and reranking.

How does autocomplete return results fast enough to feel instant?

Move expensive candidate generation and base scoring out of the request path, then retrieve a bounded top-m set from an in-memory prefix index. The online path still normalizes input, applies policy and context filters, reranks, deduplicates, and returns k items, so its cost is closer to prefix traversal plus bounded candidate work and output, not O(1). Head-prefix caching and cancellation of stale requests reduce load and visible latency.

How are autocomplete suggestions ranked?

Build a base score from approved candidates, aggregated popularity, time decay, quality, and locale or market context. At request time, apply mandatory safety, privacy, availability, and legal filters before a bounded contextual or personalized rerank. Search logs are biased by previous exposure and vulnerable to bots, so clicks and counts are signals rather than ground truth.

How fresh do autocomplete suggestions need to be?

Set freshness by source and risk instead of assuming one hourly rebuild. Publish a validated versioned base snapshot on a measured cadence, merge a small moderated streaming overlay for trends, and support immediate suppression for unsafe or legally removed terms. If the overlay fails, serve the last good base snapshot and expose the degraded freshness in telemetry.

Why is client-side debounce important for autocomplete?

Debounce or throttle reduces redundant calls, but the interval should be tested against typing speed, network conditions, and accessibility rather than fixed universally. Respect IME composition, abort obsolete requests, and attach an increasing client sequence so an older response cannot overwrite a newer prefix. Scope caches by locale and personalization, and never place private suggestions in a shared cache.

Is the autocomplete index a source of truth?

No. It is a versioned serving artifact derived from an approved candidate catalog, aggregated signals, and policy configuration. Raw query logs are inputs, not authoritative content: they contain noise, attacks, private data, and retention or deletion obligations. Keep the last good snapshot, publish atomically, and retain enough governed inputs to rebuild or roll back.

Related Articles

• System Design Interview Problems: A Senior's Roadmap - the full series index and pattern library.
• System Design Interview Guide: The 6-Step Framework - the method this walkthrough applies.
• Design a Web Crawler - Part 8; a possible source of approved entity and document candidates.
• Design Video Streaming - Part 10; versioned derived artifacts and edge delivery.
• Design a Distributed Cache - Part 4; cache keys, stampede control, and version-aware invalidation.
• Design a News Feed - Part 5; bounded candidate generation, ranking, and policy filtering.

This is Part 9 of the core track in a 16-part system design series. Next: Design Video Streaming.