Case study: Full-text search engine
Design a distributed full-text search engine: document-partitioned inverted indexes, two-phase scatter-gather, WAND early termination, and tail-latency defences across shards.
35 min9 steps
By the end you can
- Estimate postings-list storage with delta compression and quantify fan-out tail latency across shards
- Justify document partitioning over term partitioning for multi-word queries
- Design a two-phase scatter-gather query pipeline with query caching and multi-stage ranking
- Mitigate slow or unavailable index shards using caching, hedging, and partial-result soft timeouts
Pin down what you are building
Full-text search
- Boolean/phrase queries; BM25 + PageRank + re-ranking; snippets; continuous indexing
20B documents
- ~100k queries/s; p99 <200-250ms; production partial results
Work out the numbers
Queries/s
93k
8B/day / 86,400; 200k peak
Postings
4 trillion
20B docs / 200 terms
Index size
32 TB
4T / 8 B; 64 shards / 500 GB
All shards fast
52.6%
0.99^64; independent-shard assumption
Design the external and internal APIs
GET /v1/search?q={terms}&page=1; PUT /v1/documents/{docId}
- Ranked hits/snippets; enqueue indexing
Internal RPC
- Shard.Query(topK=25); DocStore.GetSnippets(global top 10)
Model the inverted index and sharding strategy
Document partitions
- hash(docId) / shard; term / sorted (docId, frequency, positions)
Term partitions
- Common-word intersections require network transfers; document partitions intersect locally
Draw the high-level architecture
Put the steps of an uncached full-text search query in order.
- 1Coordinator fetches titles and snippets for the winning 10 docIds from the document store and caches the result
- 2Each shard intersects its local posting lists using WAND/BM25 and returns its top-k (docId, score) pairs
- 3Coordinator merges shard candidates into the global top-10 docIds
- 4Coordinator normalises the query, checks the query result cache, and misses
- 5Coordinator scatters the parsed query in parallel to all document-partitioned index shards
Deep dive: WAND pruning, immutable segments, and tail defences
Fast local search
- Skip pointers; Block-Max WAND skips blocks below top-k score bound
Freshness and tails
- Immutable segments merge; caches; 30ms replica hedge; 150ms soft deadline
Evaluate alternatives
search-full-scan
- Store saturates; latency SLO fails
Tiered index
- Hot 10% in RAM; cold fallback
Fancy lists
- Precomputed term winners accelerate common queries
Run the failure scenarios
Inject
slow-shard: 6x
Observe
parallel(all) waits for idx2
Result
Uncached p99 rises; cache hits stay fast
Inject
shard-outage: 400ms
Observe
Uncached fixture searches fail
Result
Cache hits/writes survive; production replicas or partial results
Inject
hot-query: 35%
Observe
First lookup scatters
Result
qcache absorbs subsequent repeated queries
Wrap up and self-assess
Explain
- Document sharding, WAND, compression, two-phase retrieval
Watch
- Fan-out tail, index freshness, cache hits; hedge within capacity
Answer this step to continue.