Design a web search engine

There are two ways to split an inverted index. Term partitioning puts all postings for a term on one machine ('cricket' lives on shard 17). A query then touches only the shards for its 2-3 terms, but intersecting long posting lists means shipping huge lists across the network, and popular terms create hot shards. Document partitioning gives each shard a slice of documents (10M pages) and a complete mini-index over them. Every query goes to every shard, but each shard does its own intersection and scoring locally and returns only a tiny top-K list. Load is naturally balanced because documents are assigned by hash. Web search engines use document partitioning. The cost is fan-out: one query becomes 5,000 shard requests, so the slowest shard decides latency. You control that with a tree of aggregators, per-shard deadlines (drop a shard that is late and return a slightly incomplete result), replicas for every shard and hedged requests (send a backup request to another replica if the first has not replied by the p95 time). Mention that the system degrades gracefully: losing one shard loses 0.02% of documents, not the whole query.

You cannot run an expensive model on billions of documents per query, so ranking is a funnel. Stage 0 is retrieval: intersect posting lists (with WAND or block-max WAND to skip documents that cannot make the top-K) and score with BM25 plus a static quality score. Posting lists can be ordered by quality so a shard can stop early once it has enough good candidates. Each shard returns ~50, so the root sees ~250k candidates and keeps ~500. Stage 1 is a learning-to-rank model (gradient-boosted trees like LambdaMART) over a few hundred features: BM25 per field (title, body, anchor text, URL), term proximity, PageRank, spam score, freshness, historical click-through for this query-URL pair. Stage 2, if budget allows, is a small transformer cross-encoder on the top ~50. Budget example: 20 ms query understanding, 60 ms shard retrieval, 30 ms LTR, 40 ms neural re-rank, 20 ms snippets. Training labels come from human raters plus click logs corrected for position bias (people click result #1 because it is #1).

Rebuilding a 50-billion-page index takes many hours, so a single batch index is always a day or more stale. That is fine for Wikipedia, not for 'India vs Australia score' or a breaking news story. The standard answer is a tiered index. The main index is rebuilt in batch (daily or every few days), immutable, highly compressed and cheap to serve. A fresh tier is a small index (say 100M recent or fast-changing pages) built from a stream: pages from news sites and high-change URLs flow from Kafka into an indexer that builds small in-memory segments every few seconds, LSM-style, and merges them in the background. At query time the root queries both tiers and merges, with the query understanding step boosting the fresh tier when it detects news intent. Deletions (DMCA takedowns, pages gone 404) are handled with a deleted-doc bitmap checked at serve time, because rewriting immutable segments for one deletion is too expensive.

Around a quarter to a third of crawled pages are exact or near duplicates: mirrors, printer versions, URLs with tracking parameters. Exact dupes are caught with a content hash. Near-dupes use SimHash: a 64-bit fingerprint where similar documents differ in few bits; you look for fingerprints within Hamming distance 3 using several permuted tables. Duplicates are clustered under one canonical URL (respecting rel=canonical), which saves index space and stops results pages full of copies. Spam fights the ranking signals. Link farms inflate PageRank, so you compute trust-propagated scores (TrustRank) from a seed set of known-good sites and down-weight links from new or clustered domains. Keyword stuffing is caught by text classifiers. Spam scores are static features in the index, and spammy pages can be dropped at build time.

Document partitioning wins: balanced load, local scoring, graceful degradation when a shard is down. Term partitioning reduces fan-out but moves huge posting lists over the network and creates hot shards for common terms. Accept the fan-out and fight tail latency with replicas, deadlines and hedging.

Immutable segments compress better, need no locks and are trivially replicated and rolled back. A fully incremental index (like Elasticsearch at this scale) would carry constant merge overhead on every shard. Hybrid: batch main index plus a small streaming fresh tier.

Shards return results within a deadline and may skip low-quality postings (early termination). You lose a tiny amount of recall in exchange for a predictable p99. For web search, a slightly worse result in 150 ms beats a perfect one in 2 s.

Caching the head of the query distribution cuts backend load by 30-50%. The cost is staleness, handled by putting the index version in the cache key and using short TTLs for queries classified as news.

With 5,000 shards, even a 1-in-1,000 slow shard request hits most queries. Fixes: aggregator tree to limit fan-in per node, hedged requests after the p95 time, per-shard deadlines with partial results, keeping index data in RAM/SSD and isolating batch jobs from serving machines.

More documents means more shards and more fan-out. Use a tiered index: a small 'tier 1' of the highest-quality ~10% of pages answers most queries; only go to the full tier when tier 1 returns too few good results. This also cuts serving cost sharply.

Add replicas of every shard (cost grows linearly), raise the cache hit rate with better query normalisation, and serve from more regions. Shard count does not need to change for traffic growth.

Aggregators health-check replicas and route to the others. If all replicas of a shard are slow, the shard is skipped after the deadline and the response is marked partial internally; the user loses 0.02% recall, not the page.

New index versions roll out shard by shard to canary replicas with automated quality checks (known-query regression suite, result overlap with the previous version, click metrics). Keep the previous version on disk so rollback is a pointer flip.

Every region holds a full replica of the index. GeoDNS and anycast move traffic to the next region; capacity planning keeps N+1 regions so a loss raises latency but not error rate.