System Design · 7 chapters · ~12 min read

Designing a Search & Autocomplete System

A naive autocomplete implementation runs a LIKE '%prefix%' query against the primary database on every keystroke — which works at demo scale and falls over the moment real users start typing. This design walks through replacing that with a sharded, cache-fronted index built specifically for prefix lookups, and the consistency trade-offs that come with it.

Mangesh MandlikLast updated: 3 November 2026

Chapter 01

Problem Definition

Users type a few characters and expect instant, relevant results. Autocomplete suggestions arriving in well under 100 milliseconds and full search results in well under 200 milliseconds are common product targets — illustrative SLOs used throughout this module, not universal hard ceilings every search system must hit.

The core interaction is deceptively simple: a user starts typing in a search box, suggestions appear before they finish, they press enter, and a ranked list of relevant results arrives. Underneath that simplicity is one of the most latency-sensitive and read-intensive workloads in software engineering.

The same shape of problem shows up across several domains — product/catalog search, content search, user/entity search, document search — and the domain materially affects freshness requirements, ranking signals, filtering needs, and how autocomplete should behave. This module uses a product-catalog example throughout, but the architecture generalizes.

The fundamental insight

The source database is the source of truth. The search index is optimized to find that truth quickly. These are different tools with different data structures, different consistency models, and different performance characteristics.

Interactive

Visual Design Journey

Watch a single database query buckle under scale, then follow the exact chain of engineering decisions — indexing pipeline, prefix trie, ranking, caching, sharding — that turns it into a resilient, millions-of-queries-per-second system.

Chapter 02

Requirements

Functional requirements describe what the system does. Non-functional requirements describe the constraints that make it hard.

Functional

Full-text/keyword search across a large corpus (products, content, users, documents). Autocomplete/typeahead suggestions as the user types. Relevance ranking. Filters and facets (category, price range, rating). Pagination through result sets. Visibility of document creates/updates/deletes within some freshness expectation. Typo tolerance/fuzzy matching where the domain calls for it. Optional personalization.

It helps to separate four distinct concerns that are easy to conflate: search correctness — can the user find matching documents at all; relevance quality — are the best documents ranked first among the matches; freshness — how quickly do source changes become searchable; availability — can search return useful results during partial failures. A system can be correct but poorly ranked, or fresh but unavailable during a shard outage — treating these as one undifferentiated "search works" requirement hides real trade-offs.

Non-functional

Low latency

Illustrative product SLOs used in this module: autocomplete under ~100ms P99, full search under ~200ms P99. Treat these as example targets to design around, not universal industry ceilings — the right numbers depend on the product and user expectations.

High read QPS

Search is typically one of the most read-heavy workloads in a system, often reaching very high queries-per-second at scale. Indexing (write) QPS is often lower than read QPS — but not always: bulk catalog imports, high-frequency event-driven domains, or large content platforms can produce indexing workloads that are substantial in their own right, not automatically "orders of magnitude lower."

High availability

Search downtime is immediately visible to every user. Favor graceful degradation over hard failure where the domain allows it — though whether stale or partial results are actually preferable to no results depends on the domain (see Scale, Sharding & Failure below).

Eventual consistency

The search index commonly lags the source database by some window — seconds is a common illustrative assumption for many search use cases. This trade-off is what unlocks the indexing-pipeline pattern that lets search scale independently of the transactional database. The acceptable lag is a domain/product decision, not an inherent property of search.

Capacity estimate (illustrative)

Illustrative planning numbers, not measurements of any real system. Every figure below follows from the stated assumptions; change an assumption and the shard and replica counts change with it. This sizes the main search index; autocomplete is counted only for request volume, since it is served from its own prefix index.

Quantity	Assumption / formula	Result
Corpus	Assumption: 100M documents	100M docs
Indexed size per document	Assumption: ~2 KB (inverted index + doc values + stored fields)	—
Primary index size	100M × 2 KB	200 GB
Primary shards	Assumption: ~25 GB per primary shard (small enough to relocate and recover quickly); 200 GB ÷ 25 GB	8 shards
Searches per day	Assumption: 20M daily users × 5 searches	100M/day
Average search QPS	100M ÷ 86,400 s	≈ 1,160/s
Peak search QPS	Assumption: peak = 3× average	≈ 3,470/s
Replica copies per shard	Assumption: one shard copy serves ~1,500 queries/s; every broad query hits all 8 primaries (hash sharding), so each shard group must absorb the full peak: ⌈3,470 ÷ 1,500⌉	3 copies (1 primary + 2 replicas)
Total shard copies and storage	8 shards × 3 copies; 24 × 25 GB	24 copies, ≈ 600 GB
Shard-level requests at peak	3,470 queries/s × 8 shards (scatter-gather fan-out)	≈ 27,800/s
Indexing rate	Assumption: 1% of documents change per day; 1M ÷ 86,400 s	≈ 12 writes/s average
Autocomplete requests at peak	Assumption: 4 debounced requests per search; 100M × 4 ÷ 86,400 × 3 peak	≈ 13,900/s
Autocomplete reaching the cluster	Assumption: 80% cache hit rate, so 20% reach the prefix index	≈ 2,800/s

Illustrative estimate; units are queries or requests per second unless stated

What this drives in the design: shard count is set by index size (8 shards at ~25 GB each), while replica count is set by query throughput (3 copies per shard) — two different knobs, which is why the next chapters treat sharding and replication separately. The 8× fan-out turns ~3,470 user queries/s into ~27,800 shard requests/s and makes tail latency depend on the slowest of 8 shards. The same 80% hit-rate assumption shows the cache-failure exposure: without it, autocomplete would reach the cluster at ≈ 13,900/s instead of ≈ 2,800/s, the 5× rise given by 1 / (1 - hit_rate). Indexing at ≈ 12 writes/s is negligible next to reads here, but the page's earlier caveat stands: bulk imports can change that picture.

Chapter 03

Why Not Just Query the Database?

A LIKE query against the source database works for small datasets. It fails at scale — though the reason is more nuanced than "databases can't search text."

Naive architecture: User → API → Database. Full-table LIKE scans for every query.

A query such as LIKE '%iphone%' generally cannot use a normal B-tree index efficiently — leading-wildcard patterns defeat the index's sorted-prefix structure, forcing a full table scan. But relational databases are not limited to that: many support full-text indexes, trigram indexes, specialized extensions, and prefix indexes for patterns that don't have a leading wildcard. For a small catalog or a low-QPS internal tool, database-native full-text search can be entirely reasonable.

The stronger argument for a dedicated search engine isn't that databases can't search text — it's that large-scale search commonly needs several things together: inverted indexes built for this exact access pattern, relevance scoring, language-aware analyzers, typo/fuzzy matching, facet aggregation, distributed retrieval, and the ability to scale search capacity independently of the transactional workload. See Trade-offs & Decisions → Database vs Dedicated Search Index for the full comparison.

Chapter 04

Search Index & Indexing Pipeline

The search engine maintains an inverted index — a data structure that maps each token to the documents containing it. The indexing pipeline keeps this index synchronized with the source database.

Inverted index

For the term 'iphone': { 'iphone': [doc_1, doc_42, doc_891, ...] }. At query time, the union or intersection of posting lists for query terms is computed. Term-dictionary lookup itself can be very fast, but the posting list for a term can be long, and processing it has a real cost that depends on posting-list size, the number of query terms, applied filters, and scoring — it is not free regardless of corpus size. Search engines use compressed postings, skip structures and optimized top-k algorithms specifically to keep this fast without naively scanning everything. See Architecture Deep Dive → Inverted Index & Posting Lists for the full mechanics.

Indexing pipeline

Source DB → change stream/queue → indexer → search index. This pipeline must handle inserts, updates and deletes, with idempotency/versioning so redelivered or out-of-order events don't corrupt the index, plus a way to fully rebuild the index when needed. Change Data Capture (CDC) — reading the database's transaction log — is one common way to feed this pipeline, but it is not the only valid approach: application-emitted events and batch/scheduled imports are legitimate alternatives with different coupling and freshness trade-offs. See Trade-offs & Decisions → CDC vs Application Events vs Batch Reindex.

Index lag

Index lag is workload- and pipeline-dependent, not a fixed number — steady-state lag of single-digit seconds is a common illustrative assumption for many product-search use cases, but bulk imports or pipeline backlog can push it to minutes. What's acceptable is a domain decision: fine for most product search, generally too loose for time-critical or financial data.

Full architecture: source DB → CDC → queue → indexing pipeline → search index + prefix index. Read: user → cache → search LB → sharded nodes → ranker.

For duplicate events, out-of-order updates, delete/tombstone handling and dead-letter behavior, see Architecture Deep Dive → Indexing Pipeline Correctness. For rebuilding the index without downtime after a schema/analyzer change, see Architecture Deep Dive → Zero-Downtime Reindexing.

Chapter 05

Autocomplete — Prefix Index

Autocomplete queries arrive on every keystroke and need a tight, predictable latency budget. There isn't one canonical implementation — autocomplete is best understood as prefix → candidate generation → ranking → top suggestions, with several valid ways to generate candidates.

Candidate generation approaches

A prefix query against the existing search engine (reuses infrastructure, simpler operations); edge n-grams/prefix terms indexed at write time (fast prefix lookup, larger index); a dedicated trie/FST-like prefix structure (efficient traversal, its own operational footprint); or a precomputed suggestion index built from query logs (excellent for popular queries, needs freshness/spam handling). See Architecture Deep Dive → Autocomplete Candidate Generation for a full comparison.

This module's choice, and why

This module illustrates a dedicated prefix structure as its chosen architecture, on the reasoning that a strict, predictable low-latency budget under concurrent full-text query load justified isolating autocomplete from the main search path. That's a defensible choice under those specific assumptions — not evidence that a dedicated trie is the universally correct production answer. A smaller system, or one without that concurrent-load pressure, might reasonably choose the unified search-engine prefix approach instead (see Trade-offs & Decisions → Separate Autocomplete Index vs Unified Search).

Suggestions themselves don't have to be raw dictionary-term completions — they can represent searchable entities/products directly, previously popular full queries, categories, or a deliberately mixed list. Ranking candidates (by popularity, recency/trending, locale, and optionally personalization) is a separate concern from generating them — see Architecture Deep Dive → Autocomplete Ranking and Autocomplete Request Control for debounce/cancellation/rate-limiting mechanics.

Chapter 06

Ranking & Caching

The search index retrieves candidate matches. Candidates are not results — they must be ranked. For the most common queries, a cache may already have the answer.

Retrieve then rank

The pipeline: query → retrieve a candidate set from the inverted index → first-stage lexical score (BM25 is a common baseline) → optional business/personalization re-ranking on a bounded slice of that candidate set → top results. Bounding the re-ranking stage to a fixed candidate-set size keeps that stage's cost predictable — it does not make the whole query's cost constant, since candidate retrieval itself still has variable cost depending on posting-list sizes and filters. See Architecture Deep Dive → Ranking Pipeline for BM25 explained conceptually and the full staged breakdown.

Result cache

Search query distributions commonly follow a Zipf-like pattern — a relatively small number of queries dominate traffic — which is what makes caching effective at all. The cache key needs to be more than just the query string: it should capture normalized query text, filters, sort, locale/market, page/cursor, and ranking/model version, since any of these can change the correct response. TTL and hit rate are workload-dependent, not fixed constants — see Trade-offs & Decisions → Cache TTL vs Freshness and Architecture Deep Dive → Search Cache Design.

Chapter 07

Scale, Sharding & Failure

A single search node cannot hold the entire index for a large corpus in memory, and cannot serve millions of QPS. The index must be sharded and, typically, replicated.

Sharding

A common baseline: coordinator → relevant/all shards → local top-k → merge → final top-k. Hash/document-ID sharding gives balanced distribution but means a broad query typically must reach every shard. Tenant/category/routing-key sharding, or time-based/domain-specific partitioning, can route a query to only the relevant shard subset when the query can supply that key — reducing fan-out at the cost of possible imbalance. Not every system broadcasts every query to every shard; see Architecture Deep Dive → Sharding, Routing and Scatter-Gather and Trade-offs & Decisions → Hash Sharding vs Routed/Domain Sharding.

Search node failure

If a healthy replica exists, it can take over with reduced capacity or elevated latency for the surviving nodes — but this is not an automatic guarantee of "no outage." Depending on replica availability and configuration, a shard failure can still mean partial results, errors, or materially higher latency. See Architecture Deep Dive → Replication and Partial Results and Failure & Scale Scenarios → Search Node / Shard Failure.

Cache failure — thundering herd

When the cache disappears, cluster-facing load rises by roughly 1 / (1 - hit_rate) — the exact multiplier depends on the workload's actual hit rate, not a fixed number. Mitigations: cache replication, circuit breakers, request coalescing (collapse identical in-flight requests into one). See Failure & Scale Scenarios → Cache Failure / Stampede.

Indexing pipeline failure

The search index serves stale data but keeps serving, as long as the underlying event log/queue retains the backlog and the pipeline can catch up faster than new events arrive. This recovery is conditional, not automatic — see Failure & Scale Scenarios → Indexing Pipeline Backlog.

Key takeaways

Keep the transactional DB as source of truth; the search index is a read-optimized derivative
Autocomplete is candidate generation + ranking — a dedicated prefix structure is one valid choice among several, justified by this module's assumed latency/isolation requirements
An indexing pipeline (commonly CDC-fed, though not the only valid mechanism) keeps the index eventually consistent — the acceptable lag is a domain decision, not a universal number
Retrieve-then-rank: retrieve candidates from the index, rank with signals, return top-k — this bounds re-ranking cost, not total query cost
Cache popular queries with a cache key that includes filters, sort, locale and page — not just the raw query string; TTL and hit rate are workload-dependent
Shard the index for scale; replication improves but does not guarantee availability during a shard failure
Cache failure raises cluster-facing load by an amount derived from the actual hit rate — mitigate with request coalescing and capacity headroom