Skip to main content

Design a Web-Scale Search Engine

This is the first Hard problem in this module, and it's a genuine step up from the Medium tier for a specific reason: it isn't solved by picking one clever mechanism the way Design Twitter's fan-out choice was — it needs at least two independently hard sub-problems solved correctly at the same time (indexing the entire web, and ranking results fast enough for a human to feel like the answer was instant), plus the crawler from Design a Web Crawler feeding it continuously. Following the framework from How to Answer a System Design Interview Question.

1. Requirements​

Functional:

  • Given a text query, return a ranked list of the most relevant web pages.
  • Continuously incorporate newly crawled and updated pages into what's searchable.

Non-functional:

  • Query latency needs to be well under a second — this is the single hardest constraint in the whole problem, since it has to hold true against an index covering essentially the entire web.
  • Index freshness can tolerate real lag — a page appearing in search results hours or even a day after being crawled is normal and acceptable, a clear eventual consistency case.
  • Extreme read scale: enormously more searches happen than pages get crawled or updated.

Scale estimate: assume an index covering 50 billion web pages, at roughly 10KB of extracted text each — around 500PB of raw text, before even accounting for the index structure built on top of it. At 100,000 queries/sec globally, no single machine can hold this index or answer a query alone; both the index and the query-serving path have to be distributed from the start, not as an afterthought.

2. API Design​

GET /search?q={query}&page={n}
  returns: { results: [{ url, title, snippet, score }], total_estimate }

3. Data Model​

The core structure is an inverted index — instead of storing "document → words it contains" (which would require scanning every document to answer a query), it stores the reverse: "word → list of documents containing it."

inverted_index
  term        VARCHAR
  postings    LIST<{ doc_id, positions, term_frequency }>

documents
  doc_id      VARCHAR PRIMARY KEY
  url         VARCHAR
  title       VARCHAR
  crawled_at  TIMESTAMP

A query for "distributed systems" becomes: look up the term "distributed"'s posting list, look up "systems"'s posting list, and intersect them — a fast set operation over two much shorter lists, instead of a scan over 50 billion documents.

4. High-Level Design​

System Design Lab

The crawler from Design a Web Crawler is this system's continuous input, not a one-time bulk load — new and updated pages flow into the indexing pipeline constantly, which is exactly why index freshness is an eventual-consistency property rather than a strict one.

5. Deep Dive: sharding the index — by document or by term​

The index is far too large for one machine, so it has to be sharded — and there are two structurally different ways to do it, each with a real cost:

System Design Lab
  • Document-partitioned — each shard holds a full inverted index, but only for a subset of all documents. A query goes to every shard (each searches its own slice of the web independently), and the top results from each are merged. This is the far more common real-world choice: it scales cleanly by adding shards, and losing one shard just means missing that slice of documents, not the whole index.
  • Term-partitioned — each shard holds the full document set, but only some terms' posting lists. A query might only need to contact one or two shards (whichever hold the queried terms), but a single popular term's posting list can be enormous and load one shard heavily, and it's much harder to rebalance a term's data cleanly across nodes as vocabulary and document counts grow.

6. Deep Dive: ranking without scoring 50 billion pages per query​

Even after narrowing to documents that contain the query terms, that intersected set can still be enormous for common terms. Running an expensive, high-quality relevance model (weighing hundreds of signals — content quality, link authority, freshness, personalization) against every one of those candidates per query would be far too slow. Real search engines solve this with a two-phase approach: a cheap, fast first pass (simple term-frequency scoring against the inverted index) narrows millions of candidates down to a few hundred, and only that small shortlist is re-scored with the expensive, high-quality ranking model. This is the same "cheap filter first, expensive work only on the survivors" shape as a Bloom Filter — a fast, approximate step doing most of the elimination so the accurate, costly step only ever runs on a small remainder.

7. Tradeoffs​

Document partitioning is the default for the reasons above — cleaner scaling, more graceful degradation — but it means every query fans out to every shard, paying a "slowest shard" latency tax on every single request (the overall response can't return faster than its slowest contributing shard). Term partitioning avoids that fan-out for queries whose terms happen to land on few shards, at the cost of much harder load balancing, since term popularity is wildly uneven.

The two-phase ranking from the deep dive above has its own version of the same speed-vs-completeness tension: the cheap first pass narrows the field using only a fast, approximate signal (term frequency), which means a page that's genuinely the best answer by the full ranking model's standards — strong link authority, high freshness, but merely average term frequency — can be cut before the expensive model ever gets to see it. Making that first pass more accurate (weighing more signals cheaply) shrinks this risk but narrows the speed gap that makes the two-phase approach worth doing in the first place; the practical answer is tuning how large a shortlist the first pass keeps, wide enough to rarely lose a true top result, narrow enough that the second pass still finishes in milliseconds.

Document-partitioned vs. term-partitioned index sharding: pros and cons​

Document-partitioned

  • Scales cleanly by adding shards, each independently holding a slice of documents
  • Losing one shard only misses that shard's documents, not the whole index
  • Load stays naturally balanced regardless of how uneven term popularity is

Term-partitioned

  • A single popular term's posting list can overload the one shard holding it
  • Rebalancing term data across shards as vocabulary grows is genuinely hard
  • Uneven term popularity makes load balancing far harder to get right

Further Reading​

Share this lesson

Saved locally in your browser — visible in the sidebar as you go.