Search, Indexing, and Retrieval Systems

A search request has 180 milliseconds at p99 from gateway acceptance to a usable response. Route and parse may spend 15 ms. Distributed retrieval gets 70 ms, top-k merge 20 ms, feature access 25 ms, reranking 30 ms, document fetch 15 ms, and 5 ms remains as reserve. The allocation sums exactly to the objective; therefore every optional stage has a stop condition, not a hope that some later stage will run faster.

The design decision is how much expected result quality each millisecond buys. Search is not merely a fast lookup. It is a controlled reduction from a large corpus to a few ordered results while ingestion, refresh, deletes, merges, replicas, and schema versions keep changing the searchable state. The system trades indexing work, memory, storage, and sometimes approximation for low query latency.

Use two related boundaries. The indexing boundary begins when a document version is accepted and ends when that version is searchable under a named index generation. The serving boundary begins when a query is accepted and ends when ordered results, coverage, freshness, and degradation metadata are returned. The source document system remains authoritative unless the index contract deliberately says otherwise.

Two paths must agree on identity and time

The indexing path typically performs:

accept document/version
  -> validate and parse
  -> normalize/tokenize/embed
  -> write postings, stored fields, doc values, or vectors
  -> create segment
  -> refresh searchable view
  -> merge/compact and retire old segment state

The query path typically performs:

accept query/deadline
  -> parse/rewrite and authorize
  -> select indexes, shards, and replicas
  -> retrieve candidates
  -> merge shard-local top-k
  -> fetch features and rerank
  -> fetch documents/snippets
  -> return results with boundary metadata

These paths meet through document identity, schema/analyzer version, index generation, delete state, tenant boundary, and visible timestamp. A document acknowledged by the source but not yet refreshed may correctly be absent from search. A deleted document can remain in immutable segment bytes while a live-doc mask excludes it. A query spanning two index generations can produce inconsistent ranking or duplicates unless routing pins a supported view.

Define freshness from a start and end event. “Three-minute freshness” might mean p99 from authoritative source commit to search visibility for accepted document versions, excluding quarantined documents and planned reindex. Track source commit time, ingest acceptance, parse completion, segment creation, refresh visibility, and query-observed generation. Queue age at each boundary is more actionable than the age of the indexing process.

Inverted indexes turn terms into candidates

An inverted index maps a term in a field to an ordered postings list of documents containing it. A term dictionary finds the term; postings can carry document IDs, frequencies, positions, offsets, payloads, or impact information depending on the field and codec. Stored fields support retrieving document values by document ID. Column-oriented per-document values support sorting, faceting, and feature access. These are different access paths with different storage and cache behavior.

Parsing is part of the index contract. Tokenization, case normalization, stemming, synonyms, language handling, field boundaries, and character filters determine which terms exist. Changing an analyzer changes semantics, not merely bytes. Store the analyzer/schema version with the index generation and maintain fixtures for exact terms, phrase positions, Unicode, identifiers, and languages that matter.

Postings compression exploits ordered document IDs and repeated patterns. Dictionaries and block encodings reduce memory and transfer, but query cost depends on term frequency, conjunction opportunities, skip/impact behavior, positions, and scoring. “Compressed index size” does not predict the latency of a phrase over a ubiquitous term.

For a conjunction, the engine can advance through shorter or more selective postings and skip ranges that cannot contribute. For a disjunction with many common terms, candidate work may grow dramatically. Exact total-hit counting can require more work than finding a competitive top 10. Make hit-count accuracy a product requirement rather than an unnoticed side effect.

Sharding chooses the fan-out and failure shape

Sharding is a retrieval decision as well as a capacity decision.

By document. Each shard holds a subset of documents and a complete term space for that subset. Most queries scatter to all eligible shards, then the coordinator merges local top-k results. Adding shards increases parallelism and per-shard working-set locality but also fan-out, coordination, queues, and the probability of a slow participant.

By term. A shard owns terms or term ranges. Term lookup can touch fewer shards, but assembling multi-term scoring and document features crosses ownership boundaries. Hot common terms concentrate load. This layout is specialized because ranking usually needs evidence across terms and documents.

By tenant. A routing directory maps tenants to shards or indexes. It can improve isolation, authorization, locality, and query fan-out, but tenant sizes and rates are skewed. Large tenants need subsharding; small tenants may need safe packing. Cross-tenant search becomes an explicit scatter path.

By geography or policy domain. Data stays near users or inside residency boundaries. Query routing and index pipelines must preserve authority, deletion, version, and failover rules. Global results require a federated merge whose scores may not be comparable without calibration.

SignalWeave Search uses 50 document shards for its main corpus. Each shard returns up to 200 first-stage candidates, so the coordinator may receive 10,000 candidates before global reduction. It selects 500 for feature access, 50 for expensive reranking, and returns 10. The funnel reduces candidate count 20×, then 10×, then 5×. Those counts are modeled operating inputs, not ideal constants.

Shard-local top-k is safe only relative to the scoring and merge contract. If a globally excellent document can rank below local k because score statistics, personalization, or cross-shard features differ, it never reaches the coordinator. Increase local depth, normalize evidence, route more selectively, or accept measured quality loss. Validate against a deeper or exact oracle on the actual shard distribution.

Fan-out turns per-shard tails into query tails. Do not estimate a query p99 by multiplying or averaging shard p99 values. Replay correlated load and failure, measure coordinator wait, and record the slowest shard, queue, replica, segment state, and candidate contribution for each sampled query.

Ranking is a sequence of economic gates

A practical retrieval funnel spends cheap signals broadly and expensive signals narrowly:

1. candidate generation uses lexical postings, filters, vector retrieval, or several retrievers;
2. first-stage scoring combines inexpensive term, freshness, popularity, or proximity signals;
3. feature retrieval loads document, user, context, or interaction features for a smaller set;
4. reranking applies a more expensive model or cross-feature function;
5. fetch and presentation retrieve stored documents, snippets, permissions, and response fields.

At every gate ask: What population enters? What quality metric can improve? What is the incremental latency, CPU, memory, network, and dependency risk? How does the stage stop? What happens to correctness and user interpretation when it is skipped?

The 180 ms model allocates:

Budgets are not independently configured timeouts. Each stage receives the minimum of its allocation and the remaining propagated deadline. Work must observe cancellation, and owners must account for orphaned shard searches or inference requests. A timed-out coordinator that leaves 50 shard tasks running converts user latency protection into background overload.

Ranking quality needs an explicit population and metric. Offline choices may use recall@k against an exact retriever, precision, normalized discounted cumulative gain, mean reciprocal rank, calibration, or task-specific judgments. Online evidence may include reformulation, abandonment, successful task completion, or guarded experiments. Clicks alone contain presentation and position bias. Report segments such as language, tenant, head/tail query, device, and freshness; a global mean can conceal severe quality loss.

Approximation is a scoped quality decision

Approximate nearest-neighbor (ANN) indexes search vector space without evaluating every vector exactly. Graph, inverted-file, quantized, and hybrid methods move compute and memory between index construction and query service. Their trade-off is not simply “accuracy versus speed.” It includes build time, update behavior, memory, filter interaction, corpus geometry, recall, tail latency, and recovery.

The fixture uses a synthetic frontier:

Moving from effort 32 to 64 buys 0.060 recall for 11 ms in this model. Moving from 128 to 256 buys 0.018 for 37 ms. That diminishing frontier suggests a target near 128 only for the modeled corpus and deadline. It is not a measured product claim.

Measure ANN quality with a labeled query set and an exact-search oracle over the same eligible corpus, distance function, filters, and index generation. Report recall@k by query segment and tail, plus latency, distance computations, memory, build time, update rate, and concurrency. A post-filter applied after ANN retrieval can remove most candidates and collapse recall; integrated filtering, oversampling, or a different retrieval path may be required.

Approximation is usually more acceptable in candidate generation when later stages can recover quality and the product tolerates a measured miss rate. It may be unacceptable for legal discovery, exact identifier lookup, complete security-policy matching, or any workflow whose contract promises exhaustive results. Hybrid lexical/vector retrieval can improve coverage, but it adds candidate fusion, score calibration, duplication, and more deadline competitors.

Define an approximation envelope:

population: corpus generation, query set, language/tenant/filter segments
oracle: exact method and distance/relevance definition
quality: metric, k, target, confidence/uncertainty, worst protected segment
performance: concurrency, latency percentiles, CPU/memory/network, warm state
index: algorithm/parameters, embedding/model, build/update path, hardware/version
degradation: timeout behavior, fallback, partial result label
change gate: maximum quality regression and latency/cost improvement required

Without that envelope, “95% recall” is an orphaned number.

Freshness, segments, deletes, and merges are one lifecycle

Many indexes create immutable searchable segments from buffered writes. A refresh publishes a new searchable view. Merge combines smaller segments, reclaims some deleted-document space, and improves search shape at the cost of read/write I/O, CPU, temporary disk, and cache churn.

At 20,000 accepted documents/s and a two-second refresh interval, up to 40,000 documents arrive during one modeled interval. That is not a bound on observed visibility: queueing, parsing, indexing, refresh scheduling, replication, and failures add time. If the three-minute freshness objective is exhausted, 3.6 million documents arrive at the stated rate. The backlog measure must therefore include document count, bytes, oldest authoritative version age, and processing stage.

Refreshing every request can make documents visible sooner while creating tiny segments and forcing frequent searcher changes. Delaying refresh improves indexing throughput and segment size but increases visibility lag. Choose by the freshness population and query/index cost, then measure segment count, refresh duration, unsearchable age, merge debt, cache turnover, and query tails.

An update is often a new document version plus deletion of the old searchable version. Immutable bytes for deleted documents may remain until merge. Search must apply live-document state so the old version does not appear. Deletion correctness is separate from space reclamation. Privacy erasure may require source deletion, index deletion, snapshots, replicas, logs, caches, derived vectors, and proof across retention policy; a normal merge schedule is not a complete erasure contract.

Merge control must preserve disk reserve and query service. A merge can read and rewrite many bytes, compete for page cache and I/O, and invalidate warmed structures. Throttle or schedule it under a debt objective, but do not defer forever: too many segments raise per-query work, file descriptors, and recovery time. Test failure during segment creation, refresh publication, merge, and old-file cleanup.

Caches save different work and fail differently

Search systems use several caches whose names should identify their key and authority:

• a term or dictionary cache avoids repeated metadata and term-structure access;
• a filter/bitset cache reuses a stable predicate over an index generation;
• a result cache reuses ordered document IDs or response fragments for a normalized query and context;
• a document/feature cache avoids stored-field or remote feature fetches; and
• operating-system page cache keeps hot index blocks near memory.

Include tenant, authorization, language, schema/analyzer, index generation, personalization, experiment, and freshness boundary in the key where they change the answer. A result cache keyed only by query text can leak data or return the wrong ranking. A short TTL does not repair a missing identity dimension.

Hot terms and filters can help cache hit rate while concentrating postings and CPU. A synchronized invalidation or node loss can shift that demand to storage and replicas. Size the miss path, warm by priority under admission, and track hit rate by byte/work saved rather than requests alone. A 99% hit rate can hide the 1% most expensive queries.

Replica selection should consider eligibility, topology, queue, service time, and cache locality. Sending every repeated query to the warmest replica can create a hotspot; random routing can discard locality. Adaptive selection needs fresh signals, bounded movement, and a fallback when telemetry is stale. Replicas improve read capacity only if storage, network, coordinator, and hot-term work also distribute.

Bound adversarial and accidental query cost

A valid query can be operationally hostile: a leading wildcard, huge synonym expansion, very broad disjunction, expensive script, deep pagination, high-cardinality aggregation, unconstrained vector effort, or request for exact total hits across a vast corpus. Attackers and honest users can generate the same resource shape.

Classify before execution where possible. Bound query length, clauses, expansion, automaton states, candidate depth, page depth, aggregation buckets, vector effort, fetched fields, snippets, and total work. Estimate by corpus statistics but enforce runtime counters because estimates fail. Charge a tenant or API identity for CPU, postings advanced, candidates, bytes, inference, and concurrent shard work—not only requests/s.

Use separate lanes for interactive search, administrative export, reindex validation, and offline evaluation. Returning a clear “query too expensive” outcome is safer than allowing one request to consume the p99 budget of every neighbor. Avoid retries for deterministic cost rejection; provide a narrower alternative or asynchronous job contract.

Hot queries deserve explicit mechanisms: cache, precomputed filters, query normalization, request coalescing, more eligible replicas, or a specialized index. Hot terms may require impact-aware skipping, conjunctive anchors, or different product semantics. Splitting one term across shards can increase merge work and complicate scoring; measure rather than assume.

Partial results require product semantics

With 50 shards, SignalWeave’s modeled minimum is 48 complete shards, or 96% shard coverage, for a degradable discovery query. The response includes completed/eligible shard counts, index generation range, timeout/degradation reason, and whether ranking or snippets were skipped. That does not mean the result contains 96% of relevant documents. Missing shards can contain a disproportionate tenant, geography, time range, or hot category.

Choose among:

Fail the request. Correct for exhaustive or policy-sensitive queries where incomplete results could be misleading.

Return labeled partial results. Acceptable for some discovery experiences when coverage and bias are bounded and visible, and the client can render degradation honestly.

Use a stale or cached complete view. Exchanges freshness for completeness under a named version and maximum age.

Degrade optional stages. Keep complete first-stage shard coverage but skip expensive features, reranking, exact totals, or snippets. This often preserves a clearer contract than dropping shards.

The coordinator should stop work when the remaining deadline cannot justify its expected contribution. It should not wait to the deadline and then fabricate completeness. Define a minimum useful response time before serialization, cancellation propagation, and client delivery.

Reindexing is a versioned migration

Analyzer changes, incompatible mappings, vector-model changes, shard-layout changes, and codec upgrades may require rebuilding the corpus. At 800 million documents and a sustainable 20,000 documents/s, the arithmetic lower bound is 40,000 seconds, about 11.11 hours. If dual-write and validation reduce effective capacity by a modeled 18%, the lower bound becomes about 13.55 hours. Source reads, transformations, retries, merges, throttling, and tail catch-up make reality longer.

A safe migration uses explicit generations:

1. define source snapshot/version and new schema, analyzer, ranking, and shard plan;
2. build the new generation under separate identity and quotas;
3. capture changes after the source snapshot by dual write or an ordered change log;
4. validate document counts, identities, deletes, term/vector fixtures, query quality, latency, freshness, and resource cost;
5. shadow or sample queries against both generations without mixing their candidates;
6. switch a versioned routing pointer for a controlled population;
7. preserve rollback and continue comparison through a soak; and
8. retire the old generation only after reader, retry, cache, and recovery horizons.

Dual write is not atomic by default. Record per-generation outcomes and reconcile missing versions. A schema change may alter document identity or split one source into several index documents; count equality alone is then insufficient. A vector-model change invalidates comparisons unless the oracle and relevance evaluation are updated deliberately.

Do not merge candidates from old and new generations as if scores were directly comparable. Pin each query to one coherent generation unless a calibrated fusion method is the migration itself.

Search query budget

Request boundary:
  query class, tenant/auth context, corpus/index generation,
  deadline start/end, percentile/window, exclusions

Result contract:
  top k, ordering/ties, total-hit accuracy, required fields,
  completeness/partial rule, freshness and stale fallback

Retrieval:
  lexical/vector/filter paths, eligible shards/replicas,
  local candidate depth, coordinator depth, exact/approximate boundary

Stage budget (must fit the propagated deadline):
  route/parse/auth, retrieve, merge, feature access,
  rerank/inference, fetch/snippets, delivery reserve

Quality:
  oracle/judgments, metric and protected segments,
  ANN/filter parameters, offline uncertainty, online guardrail

Cost and overload:
  postings/candidates/distance work, CPU/memory/network,
  clause/depth/bucket limits, tenant concurrency, rejection outcome

Index lifecycle:
  ingest rate/bytes, refresh visibility, segments/merge debt,
  deletes, cache keys, reindex/dual-serving generation

Failure and evidence:
  slow/missing shard, stale telemetry, dependency timeout,
  cancellation, raw traces/metrics, replay fixture, transfer limits

Reject a budget that allocates more than the end-to-end objective, calls reserve an optional stage, has no quality metric for approximation, permits partial results without coverage semantics, or promises freshness without a source-to-search time boundary.

Applied work

Design strict-p99, bounded-freshness search. Use the 50-shard and 180 ms model. State query population, top-k and completeness contract, three-minute source-to-search freshness objective, shard routing, replica selection, stage deadlines, candidate depths, cache identities, expensive-query limits, cancellation, and degraded response. Calculate one-refresh and full-freshness-window arrivals. Then test normal, hot-term, cold-cache, one-slow-replica, one-missing-shard, merge-heavy, and indexing-backlog states.

Choose an approximation boundary. Build an exact oracle for a labeled corpus and query set. Compare at least four ANN operating points under the same filters, concurrency, cache state, and generation. Report recall@10 and latency distributions globally and for protected segments. Decide whether approximation is allowed in candidate generation, reranking, neither, or both; state the maximum permitted quality loss and the fallback when the quality or deadline guard fails.

Exercise a generation switch. Rebuild a small but distribution-faithful corpus with one analyzer or vector-model change. Replay concurrent updates and deletes, compare generations, switch a canary route, inject a failed dual write, reconcile it, and roll back. Verify that no query mixes generations and that caches cannot cross the generation key.

Sources and transfer limits

• Apache Lucene core index APIs describe postings, term dictionaries, stored fields, and related access structures. Lucene concepts illuminate the mechanism; codecs and behavior vary by version and higher-level system.
• Elasticsearch segment information, refresh controls, and search shard routing document one current implementation’s segment visibility and replica-selection controls. Treat its defaults and APIs as product-specific examples.
• OpenSearch k-NN query documentation documents adjustable search effort and the recall/latency trade-off for supported methods. It does not establish a frontier for another corpus, engine, filter, or hardware boundary.
• Malkov and Yashunin’s HNSW paper introduces the hierarchical navigable small-world approach and evaluates its reported workloads. Reproduce quality and resource evidence for the active implementation and data distribution.

The numeric search example is a deterministic model in examples/performance-engineering-system-design-handbook/part-05/search-retrieval/. Its ANN points are explicitly synthetic. The fixture checks arithmetic and diminishing modeled gain, not production quality, tail latency, or index correctness.

Decision rule

Allocate query work by expected contribution to result quality. Stop, skip, or degrade an optional stage when the remaining propagated deadline cannot justify that contribution. Preserve authorization, generation coherence, minimum completeness, and response truthfulness before ranking polish. Approximate only inside a measured quality envelope; cache only with complete answer identity; add shards only after accounting for fan-out and merge tails.

The same discipline will matter when the unit of retrieval becomes an object, media segment, or cached file. There, namespace and metadata authority, large transfers, durability, and placement replace postings and ranking as the central costs—but the serving path still succeeds only when work, state, and deadline meet at an explicit boundary.