Design a Search Engine

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.

Capacity Estimation

• Index size: 50 billion web pages, each producing roughly 500 unique terms/postings on average (after removing common stop words) — the resulting inverted index (see below) is on the order of tens of terabytes even with compression, spread across many shards.
• Query volume: a major search engine handles on the order of 10 billion queries/day → roughly 115,000 QPS average, with sharp peaks — this volume alone rules out any design that scans documents at query time; the entire architecture is built around doing the expensive work (indexing) OFFLINE, ahead of time, leaving only a fast lookup at query time.

Architecture

[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]

The inverted index — the core data structure

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.

Sharding the index

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

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.

API

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.

Index Storage

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.

• Index freshness vs cost: re-indexing the entire web constantly for perfect freshness is prohibitively expensive; most search engines use an incremental update strategy (re-crawling/re-indexing pages more frequently if they change often, based on the Web Crawler's change-detection) — a direct trade of freshness for cost, tuned per-page rather than uniformly.
• Exact vs approximate result counts: as noted above, approximate counts at high result volumes trade perfect accuracy for a large latency/cost saving, a trade users essentially never notice.
• Sharding by document range vs by term: document-range sharding gives more even shard sizes and simpler rebalancing; term-based sharding can make certain multi-term queries faster (all postings for a query's rare term on one shard) but risks severe skew for common terms — document-range is the more common default.

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.