Distributed Search

Distributed search

Find the documents that best match a free-text query, ranked by relevance, fast, across more data than one machine holds. Getting it wrong means either slow LIKE '%term%' scans that melt the primary database, or a search box that returns the wrong results and erodes user trust — both are silent until traffic or corpus size exposes them.

When to reach for this

Users type words and expect ranked, relevant matches — not exact-key lookups. The corpus is text-heavy (documents, products, logs, messages), queries are ad-hoc (any term, any combination), and results need ranking, highlighting, facets, or typeahead. Reach for it when a WHERE col LIKE or full-table scan is already the read bottleneck, or when you need fuzzy/partial matching a B-tree index cannot serve.

When NOT to

The access pattern is fetch-by-known-key or a fixed filter — a primary database index serves that far more cheaply and consistently; keep it in data-storage. The corpus is tiny (thousands of rows): an in-process filter or the database's built-in full-text index is enough — a separate search cluster is pure operational overhead (YAGNI). Search is a derived, eventually-consistent copy of your data; never make it the system of record.

Clarify first

• Corpus size and growth — document count, average doc size, total index

bytes? (→ back-of-the-envelope) This decides shard count.

• Query QPS and shape — read-heavy? term queries, phrase, fuzzy, facets,

autocomplete? Latency target (p99)?

• Indexing freshness — must a new/edited doc be searchable in seconds

(near-real-time) or is minutes/hours of lag fine?

• Relevance bar — is exact term-match enough, or do users expect "best"

results (ranking, synonyms, typo tolerance)?

• Write rate — how many docs/sec change? This sizes the indexing pipeline.

The options

The pipeline (almost always present): a source emits document changes → an indexing pipeline transforms/analyzes them → the inverted index stores term→document postings → the query path matches and ranks. For a crawl-based system (web search), prepend crawl → parse → dedupe; that crawler is its own subsystem feeding the same pipeline.

Index build mode

• Batch / bulk reindex: rebuild the whole index periodically. Use when the

corpus changes slowly or freshness in hours is acceptable.

• Near-real-time (incremental): apply changes continuously so docs are

searchable in seconds. Use when users expect to find what they just wrote.

Ranking model

• Boolean / filter only: match, no scoring. Use for exact filtering (tags,

facets) where order doesn't matter.

• TF-IDF / BM25 (lexical): score by term frequency and rarity. The default

full-text relevance model; cheap and explainable.

• Hybrid (lexical + signals): blend BM25 with popularity, recency, or

business boosts. Use when "best" means more than word overlap.

Autocomplete

• Prefix trie / FST in memory: sub-millisecond typeahead from a prefix. Use

for suggestion-as-you-type.

• Edge-n-gram index: prefix matching inside the main index. Use when

suggestions must also respect filters/relevance, at higher cost.

Distribution: split the index into shards (each a self-contained inverted index over a doc subset) for capacity, and replicas per shard for read throughput and fault tolerance. Sharding theory lives in data-storage.

Trade-offs

| Option | What it solves | What it worsens | Change it when | |---|---|---|---| | Batch reindex | Simple, atomic swap, no live-write complexity | Stale until next build; full rebuild is costly | Users need fresh results → near-real-time | | Near-real-time | Seconds-fresh; no full rebuild | Segment churn, merge load, refresh cost on writes | Write rate or merge cost overwhelms nodes → batch/larger refresh interval | | Boolean/filter | Cheapest; deterministic | No notion of "best" result | Users judge result quality → add BM25 | | BM25 | Good relevance, explainable, cheap | Ignores popularity/recency/intent | Word-overlap isn't enough → hybrid signals | | Hybrid signals | Matches business/user intent | Complex, harder to debug, needs tuning data | Tuning cost exceeds value → fall back to BM25 | | Prefix trie/FST | Fastest typeahead | Separate structure to build/refresh; ignores filters | Suggestions need filters/relevance → edge-n-gram | | More shards | Parallelism, fits big corpus | Per-query fan-out + merge overhead; tiny shards waste resources | Fan-out latency dominates → fewer, larger shards | | More replicas | Read QPS + HA | More RAM/disk; replication lag on writes | Write amplification hurts → fewer replicas |

Behavior under stress

Search amplifies trouble through fan-out and derived-data lag.

• Query fan-out tail latency: every query hits all shards; the slowest shard

sets the response time. One hot or GC-paused shard drags every query. Mitigate: size shards evenly, add replicas, cap result depth, use timeouts + partial results.

• Indexing vs query contention: a write/merge surge (bulk import, reindex)

steals CPU and I/O from queries, spiking latency. Mitigate: throttle bulk indexing, schedule big merges off-peak, isolate index vs query node roles.

• Hot shard / skew: an uneven shard key concentrates docs or popular terms on

one node. Mitigate: hash-route documents; reroute or split the hot shard.

• Deep pagination: from=100000 forces every shard to sort huge windows.

Mitigate: cursor/search_after, cap page depth.

• Pipeline backlog: if the source produces changes faster than the indexer

consumes, freshness lag grows unbounded. Mitigate: backpressure and a durable buffer (→ messaging-streaming); monitor lag, not just throughput.

• Cold cache after restart: filesystem/page cache is empty, so latency spikes

until it warms. Mitigate: warm critical queries; ramp traffic.

Monitor: per-shard p99 query latency, indexing lag (source→searchable), segment/merge count, heap/GC, shard balance, and rejected/queued requests.

How to apply

1. Clarify the inputs — pin corpus size, query QPS and shape, freshness

target, and the relevance bar (see Clarify first). If a DB index or built-in full-text serves the access pattern, stop — you don't need a search cluster.

1. Pick from the trade-off table — choose a build mode (freshness), a ranking

model (relevance bar), and whether autocomplete needs its own structure.

1. Set the key knobs — shard count (from index bytes ÷ target shard size),

replica count (from read QPS + HA), the analyzer/tokenizer (language, stemming, synonyms), and the refresh interval (freshness vs write cost).

1. Stress-test the choice — walk Behavior under stress (fan-out tail,

indexing contention, hot shard, deep pagination, pipeline backlog) and confirm a mitigation for each one the traffic profile can trigger.

1. Size it with numbers — confirm shards fit the corpus and per-shard size

stays in a healthy range, replicas cover peak QPS, and indexing throughput keeps lag inside the freshness budget (→ Numbers that matter).

1. Pick a provider — default to the generic recipe; open a provider file only

if the user named a cloud (see Choosing a provider).

Dos and don'ts

Do

• Treat the index as a derived, rebuildable copy — keep the system of record in

data-storage and be able to fully reindex from it.

• Size shards before launch (corpus ÷ target shard size); aim for even, not tiny,

shards to bound fan-out cost.

• Feed the indexing pipeline through a durable buffer so a write surge can't

outrun the indexer or lose changes.

• Start ranking with BM25; add popularity/recency signals only when word-overlap

demonstrably misses intent.

• Monitor indexing lag separately from query latency — freshness fails silently.

Don't

• Don't use a search engine as your primary store or for transactional writes.
• Don't reach for a separate cluster when a DB full-text index or in-process

filter covers a small corpus (YAGNI).

• Don't allow deep from/offset pagination; use cursors instead.
• Don't over-shard — many tiny shards add fan-out and merge overhead without

benefit.

• Don't run heavy bulk reindex unthrottled against a cluster serving live queries.

Numbers that matter

The quantities that drive the design: total index bytes (corpus × per-doc overhead, then ÷ target shard size to get shard count), read QPS × fan-out (each query touches every shard) for replica sizing, and indexing throughput vs change rate to keep freshness lag inside budget. A single shard performs well within a bounded size range; past it, split. Use back-of-the-envelope for the latency, QPS, and storage figures — don't restate them here.

Interface sketch

The contracts are the document, the query, and the postings. A document is a typed record with analyzed fields, e.g. { "id": "p123", "title": "...", "body": "...", "tags": ["a","b"], "price": 9.99 }. A query names fields, match type, filters, sort, and pagination cursor, e.g. q="wireless earbuds", fields=[title^2, body], filter={tag:audio}, sort=_score, search_after=. The inverted index maps each term → posting list of (doc_id, term_freq, positions); ranking reads these to compute BM25. Decide the analyzer (tokenizer, lowercasing, stemming, synonyms) up front — it is part of the contract and changing it requires a reindex.

Choosing a provider

Default to the generic recipe above (Elasticsearch/OpenSearch, Lucene, Solr, self-hosted). If the user names a cloud, read references/providers/.md for the managed-service mapping, quotas/limits, and provider-specific trade-offs. If no file exists for that provider, the generic recipe is the answer.

Diagram

To visualize the source → indexing pipeline → inverted index (sharded + replicated) → query/rank path, or the crawl→parse→dedupe front end, use the in-plugin architecture-diagram skill — show the indexing path and the query fan-out as distinct flows, with replicas behind each shard.

Related building blocks

• data-storage — alternative to a DB LIKE/full-table scan for text search;

search owns the inverted index, while sharding/partitioning and replication theory live there — name and link, don't re-teach.

• messaging-streaming — depends on this for the index-update pipeline: a

durable buffer carries document changes to the indexer and absorbs write surges (delivery, ordering, backpressure are owned there).

• caching — pairs with this to cache hot/repeated queries and reduce fan-out

load (stampede, hot-key, eviction handling owned there).

• back-of-the-envelope — feeds into this skill: corpus bytes, QPS, and

freshness numbers size the shards, replicas, and pipeline.

• system-design — owned-concept lives in the orchestrator: the reasoning

loop, the trade-off method, and the ten failure modes.

References

• references/deep-dive.md — inverted-index internals (postings, segments,

merges), the crawl/index/search pipeline, BM25 scoring, near-real-time refresh, autocomplete (trie/FST/n-gram), shard routing and replica reads. Read when designing the search layer in detail.

• references/providers/{generic,aws,azure,gcp}.md — service mappings,

limits, and pitfalls per environment.

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: proyecto26
• Source: proyecto26/system-design-skills
• License: MIT
• Homepage: https://proyecto26.com/system-design-skills/

Install and usage instructions live in the source repository linked above.