Full-text search engine
Index billions of documents into an inverted index sharded by document ID, scatter queries across shards in parallel, score candidates with BM25 + static signals (PageRank) + neural re-ranking, and gather the top results with snippets under a tight tail-latency budget.
Component labels and connections
- Clients (client) · calls: Load balancer
- Load balancer (loadBalancer) · calls: Query coordinator 1, Query coordinator 2
- Query coordinator 1 (service) · calls: Query result cache, Inverted index shard 1, Inverted index shard 2, Document + snippet store
- Query coordinator 2 (service) · calls: Query result cache, Inverted index shard 1, Inverted index shard 2, Document + snippet store
- Query result cache (cache) · calls: none
- Inverted index shard 1 (searchIndex) · calls: none
- Inverted index shard 2 (searchIndex) · calls: none
- Document + snippet store (database) · calls: none
Requirements
Functional
- Full-text search over multi-word queries with boolean/phrase matching, returning ranked results with title, URL, and highlighted snippet.
- Ingest new and updated documents continuously so fresh documents become searchable within seconds to minutes.
- Multi-stage ranking: fast lexical retrieval (BM25 + static quality score) followed by re-ranking of the top candidates.
Non-functional
- Search p99 latency under ~150–250 ms despite fanning out across many index shards.
- High availability: if one shard replica is slow or down, serve partial or hedged results rather than failing the whole query.
- Scale to tens of billions of documents and ~100k queries/s.
Worked estimates
Query rate
≈ 93k queries/s average, ≈ 200k/s peak
8B queries/day ÷ 86,400
Inverted index size
≈ 32 TB of compressed postings across shards (fits in RAM/NVMe across ~500 shard nodes)
20B docs × ~200 unique terms × ~8 B per posting (delta-compressed docId, tf, positions)
Fan-out tail amplification
almost half of uncached queries hit at least one 99th-percentile shard — requires query caching, shard replicas, and soft timeouts
1 query touches N = 64 shards; if each shard has p99 = 50 ms, P(all < 50 ms) = 0.99⁶⁴ ≈ 53%
Snippet fetch
two-phase fetch avoids reading full document text for thousands of scored candidates
top 10 results fetched only after merging top-k docIds
API
GET /v1/search?q={terms}&page=1
Request: query string, locale, pagination cursor
Response: 200 { totalApprox, hits: [{ docId, title, url, snippet, score }] }
PUT /v1/documents/{docId}
Request: { url, title, body, pagerank, updatedAt }
Response: 200
Appended to an indexing log; indexed into immutable LSM-like segments.
Data model
- documents — store: docstore
Inverted index: maps `term → postings list [(docId, termFreq, positions)]` sorted by `docId` (or by static quality tier) for fast intersection via skip pointers and WAND.
Document partitioning (local index per shard) vs term partitioning: sharding by `docId` means every query fans out to all shards, but multi-word intersection happens locally in memory without shipping giant posting lists across the network.
Immutable index segments (Lucene style): new documents buffer in memory and flush to immutable segments that are merged in the background, avoiding in-place locks on posting lists.
High-level design
Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.
Deep dives
Inverted index internals: postings, compression, and WAND
An inverted index maps each term in a vocabulary dictionary to a sorted postings list of `(docId, termFreq, positions)`. Because docIds are sorted, we store gaps (`delta = docId[i] - docId[i-1]`) compressed with SIMD-BP128 or Elias-Fano coding, shrinking postings to a few bytes per occurrence. To avoid scoring every document containing common words, WAND (Weak AND) and Block-Max WAND maintain upper-bound score metadata per block and skip entire blocks that cannot beat the current k-th best score.
Document partitioning and two-phase scatter-gather
Documents are hash-partitioned across N shards (and tiered into hot/high-PageRank in-memory tiers vs cold tiers). Phase 1 scatters the parsed query to all shards; each shard intersects its local posting lists using WAND, runs fast BM25 + static scoring, and returns only the top k `(docId, score)` pairs. The coordinator merges the `N × k` pairs, optionally invokes a learned re-ranker on the top ~100, and in Phase 2 fetches titles and dynamic snippets for the final 10 results.
Taming tail latency across 64+ shards
When a request fans out to N shards, the slowest shard determines latency. Three defences work together: (1) a query result cache in front of the coordinator (caching full results for common queries and posting list intersections for common sub-queries), (2) hedged requests to a replica shard if a shard hasn't answered by its p95, and (3) a soft timeout (~120 ms) where the coordinator returns the best results gathered from the 98% of shards that responded on time.
Real-time indexing with immutable segments
Mutating compressed posting lists in place on disk is prohibitively slow. Instead, indexers buffer incoming documents in an in-memory inverted index and flush them every second into a new immutable segment (Lucene's Near-Real-Time search). Searches query all active segments in parallel; a background merge thread compacts small segments into larger ones and drops deleted docIds.
Failure scenarios
One inverted index shard degrades 6× (segment merge)
Scenario and expected result
From t = 1.3 s to 2.2 s index shard 2 runs 6× slower due to a heavy background segment merge.
Expected: Because every uncached scatter-gather waits for both shards (`join: all`), the single slow shard pulls up overall search latency for every cache miss — the classic fan-out tail latency problem. Popular queries stay fast in the query cache.
An index shard goes down
Scenario and expected result
Index shard 2 crashes from t = 1.5 s to 1.9 s.
Expected: Cached queries and document writes continue to succeed, while uncached searches requiring `all` shards fail during the 400 ms outage. In production, each shard is a replica group and the coordinator also uses a soft deadline to return partial results from healthy shards rather than an error.
Viral news query takes 35% of search traffic
Scenario and expected result
A single query accounts for 35% of all traffic.
Expected: The query result cache absorbs the viral query after the first scatter-gather, shielding the index shards from redundant fan-out.
Alternative designs
Reference
- Inspect the architecture above and run the same scenario.
No inverted index: full scan of document store
- Without an inverted index (`byTerm`), every search scans the document table. Even on a 20,000-document cell, full scans saturate the store and miss the 250 ms deadline.
Reference
- Inspect the architecture above and run the same scenario.
Partition index by term instead of by document
- In a term-partitioned index, a single-word query hits only one shard. Wait until a user searches 'the best coffee near me': you must read a multi-gigabyte posting list for 'the' and 'best' over the network to intersect them, and the shards holding common stop words melt down. Document partitioning keeps intersection local to each shard.
Reference
- Inspect the architecture above and run the same scenario.
Return full snippets from every shard during scatter
- If all 64 shards generate and return full text snippets for their top 10 candidates, 640 snippets are generated and transferred when only 10 are shown. Two-phase search (Phase 1: shards return only `(docId, score)`; Phase 2: coordinator requests snippets only for the global top 10) cuts disk reads and network payload by an order of magnitude.
Clarifying questions
- How many documents and what average document length?
- How fresh must newly published or edited documents be in search results?
- Is returning 98% complete results acceptable when a shard times out?
- Do we need phrase queries and positional proximity scoring?
Common mistakes
- Sharding the inverted index by term without accounting for multi-word intersection network traffic and hot stop words.
- Fetching full document bodies/snippets from all shards during the first scatter phase.
- Mutating inverted index posting lists in place instead of writing immutable segments.
- Ignoring how fan-out across puluhan shards amplifies p99 latency.
- Scoring every matching document instead of early termination with WAND / tiered indexes.
Self-assessment rubric
requirements / levels 1-4
- 1/4 Keyword search.
- 2/4 Ranked results with snippets.
- 3/4 Multi-stage ranking, near-real-time indexing, and tail-latency SLO.
- 4/4 Partial-result degradation vs complete failure under shard slowdowns.
estimates / levels 1-4
- 1/4 None.
- 2/4 QPS and doc count.
- 3/4 Postings size with compression and shard count.
- 4/4 Quantifies fan-out tail latency amplification across N shards.
api / levels 1-4
- 1/4 Search endpoint.
- 2/4 Search + indexing.
- 3/4 Two-phase internal RPC (IDs/scores then snippets).
- 4/4 Pagination cursors, soft-timeout flags, and idempotent document updates.
data model / levels 1-4
- 1/4 Documents table.
- 2/4 Mentions inverted index.
- 3/4 Document-partitioned postings lists with delta compression + forward store.
- 4/4 Immutable segments, skip lists/Block-Max metadata, and quality tiers.
high level / levels 1-4
- 1/4 API + DB.
- 2/4 Coordinator + index shards.
- 3/4 Query cache, scatter-gather across replicated shards, two-phase snippet fetch.
- 4/4 Real-time segment ingestion pipeline and multi-stage re-ranking.
deep dive / levels 1-4
- 1/4 None.
- 2/4 Explains inverted index.
- 3/4 Document vs term partitioning and WAND/skip-pointer intersection.
- 4/4 Tail-latency mitigations (hedging, soft timeouts, tiering) and LSM segment merges.
wrap-up / levels 1-4
- 1/4 Stops.
- 2/4 Mentions latency.
- 3/4 Slow shards and segment merge I/O storms as top risks.
- 4/4 SLOs on p99 latency, recall/completeness ratio, and indexing lag.