Loading…
Loading…
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.
Q: What is an inverted index, and why is it central? A: It maps each term to a postings list: the documents containing that term, often with positions and frequencies. A query intersects or merges the postings lists for its terms, instead of scanning every document. Postings are sorted by document ID and compressed, so intersections are fast and the index fits in memory or on fast storage.
Q: How are results ranked? A: Usually in stages. A cheap first stage retrieves candidates using a term-matching score such as BM25, possibly combined with document quality signals such as link-based importance. A more expensive second stage re-ranks the top few hundred candidates with a machine-learned model that uses many features: freshness, click history, semantic similarity from embeddings, and query–document match details.
Q: How do you shard the index? A: Document-partitioned sharding is the common choice. Each shard holds a full inverted index for a subset of documents. A query is sent to all shards in parallel (scatter-gather), each returns its top results, and a broker merges them. Replicas of each shard provide throughput and fault tolerance, and tail latency is managed with timeouts and hedged requests.
Q: How do new or updated documents become searchable quickly? A: Write new documents into small, recent index segments, which are searchable within seconds and merged into larger segments in the background. That's the model Lucene/Elasticsearch use: segments are immutable, deletes are marked with tombstones, and merges reclaim space. It trades a small query cost (searching more segments) for fast indexing.
Q: How are typos and synonyms handled? A: At query time, spelling correction uses edit distance against the vocabulary, weighted by query-log frequency ("did you mean…"). Synonyms and stemming expand the query (run → running, laptop ↔ notebook). Semantic retrieval with embeddings catches matches that share meaning but not words, and is often combined with keyword retrieval in hybrid search.
Q: How do you evaluate whether a ranking change improves results? A: Offline, use human-judged relevance sets with metrics such as NDCG or MRR. Online, run A/B tests, or interleaving experiments, measuring clicks, successful sessions and query reformulations. Offline gains must be confirmed online, because users' behaviour is the real judge.