Design a web-scale search engine that crawls, indexes, and ranks billions of documents, returning relevant results for a query in well under a second.
[Crawler] (Web Crawler) → [Raw Page Store]
│
▼
[Indexing Pipeline] → builds → [Inverted Index] (sharded across many machines)
│
▼
[Query Service] → [Index Shards] (query fanned out in parallel) → [Ranking] → [Results]
Forward index (NOT what's used for search): document → list of words it contains
Inverted index (what search actually uses): word → list of documents containing it
"database" → [doc_47, doc_102, doc_5891, ...] (sorted by document ID, for fast merging)
"scaling" → [doc_12, doc_47, doc_998, ...]
Query "database scaling" → intersect the two posting lists → docs containing BOTH terms
The inverted index is what makes a query fast against billions of documents — rather than scanning every document for a match (which would be far too slow at this scale), the query looks up each query term's posting list directly (a fast index lookup) and intersects them, a comparatively cheap operation. This single data structure is the foundational reason search-at-scale is even tractable.
With tens of terabytes of index data, no single machine holds the whole index — it's sharded (commonly by document range, sometimes by term) across many machines. A query fans out to EVERY shard in parallel (since any shard might contain a matching document), each shard returns its local top candidates, and a merging layer combines and re-ranks the combined results — this fan-out-and-merge pattern is what keeps query latency roughly constant as the total index grows, by adding more shards rather than making each shard's query slower.
Ranking is a distinct stage after retrieval: once candidate documents matching the query terms are found (via the inverted index), a ranking function scores each candidate using signals like term frequency, document authority (link-based signals like PageRank), and (in modern systems) learned ranking models trained on click behavior. Retrieval finds the candidates; ranking decides their ORDER — conflating the two is a common conceptual mistake worth explicitly avoiding in an interview answer.
GET /api/v1/search?q=distributed+systems+scaling&page=1
→ 200 {
"results": [ { "url": "...", "title": "...", "snippet": "...", "score": 0.94 }, ... ],
"totalEstimated": 4820000,
"tookMs": 87
}
totalEstimated is deliberately approximate at this scale — computing an EXACT count of all matching documents across billions of documents is itself expensive and rarely worth the cost for a number users only skim past; approximating it is a standard, accepted tradeoff.
posting_list:{term} → [ {docId, termFrequency, positions[]}, ... ] (sorted by docId)
document_metadata:{docId} → { url, title, pageRank, lastCrawled }
Posting lists are typically stored compressed (delta-encoding the sorted document IDs, since consecutive IDs are numerically close, compresses very well) — this compression is a major factor in keeping index size manageable at tens-of-billions-of-documents scale, directly trading a small amount of CPU (decompression at query time) for a large reduction in storage and, critically, in the amount of data that must be read from disk/memory per query.
Both the crawling/indexing pipeline and the query-serving layer scale horizontally and largely independently: indexing throughput scales by adding more indexing workers (an offline, batch-oriented workload, more tolerant of latency), while query-serving scales by adding more index shard replicas (each shard typically replicated multiple times both for fault tolerance and to handle query fan-out load) — a query going to more replicas of popular shards under load, similar in spirit to read replicas in Database Scaling Specifics.
Query fan-out to every shard means the SLOWEST responding shard determines the overall query latency (a classic tail-latency problem — see why Percentile Metrics matter over averages) — mitigated with aggressive per-shard timeouts and returning best-effort partial results if a small number of shards are slow/unavailable, rather than waiting on every single shard unconditionally.
A shard is temporarily unavailable: the query proceeds with the remaining shards and returns results missing that shard's documents rather than failing the entire query — a deliberate availability-over-completeness choice, since a search engine returning SOME relevant results fast is almost always preferable to returning none while waiting for a struggling shard.
The indexing pipeline falls behind (a large crawl backlog): search results become progressively staler but the SERVING path is unaffected (it's fully decoupled from indexing) — this isolation between the write/indexing path and the read/query path is a deliberate, important architectural property, not an accident.