Design a simplified web search engine

A web search engine answers a query with the ten most useful pages out of billions, in a fraction of a second. It is a pipeline with an offline half and an online half. Offline, a crawler fetches pages, an indexer extracts their text and builds an inverted index, a list of the pages that contain each term, split into shards that each hold a slice of the pages, and a link job computes a quality score for every page from the links that point to it, such as PageRank. Online, a broker sends each query to every shard. Each shard scores its own pages by how well the text matches, with a formula such as BM25, combined with that link score, and returns its best few; the broker merges the lists into the top ten and adds their snippets. Popular queries are answered from a cache, and news is crawled and indexed again far more often than pages that rarely change.

5,787 queries a second, and every one reaches all 100 shards

Scope the engine before drawing it, because each answer moves a number:

• What is searched? Public HTML pages, 5 billion of them, in many languages; no images, video or ads.
• How fresh? News within minutes, other pages within a month.
• What comes back? Ten results with a title, an address and a snippet, and further pages on request.
• How fast and how much? 200 ms at the 99th percentilep99 (99th percentile): The latency within which 99 % of requests finish, so the slowest 1 % take longer. Tail latency is read from such high percentiles, because an average hides the slowest requests. More in “Latency, throughput and percentiles” in the search service, for 500 million queries a day.

The functional requirements: crawl and crawl again, index text and links, answer keyword queries with ranked results and snippets, and remove pages on request. The non-functional ones: that latency, high availability, an index that grows by adding machines, and rankings that spam cannot buy.

Quantity	Assumption and result
Queries	500 million a day: 5,787 a second, about 17,400 at a 3 × peak
Pages fetched	5 billion pages, each once a month: 1,929 a second
Text after extraction	5 billion pages × 10 KB: 50 TB
Inverted index	about a quarter of the text: 12.5 TB
Shards	50 million pages each: 100, and every query reaches all of them
Link graph	5 billion pages × 40 links × 8 bytes: 1.6 TB

Two rows decide the architecture. The index is far too big for one machine, so it is split, and because every query reaches all 100 shards, the slowest shard sets the latency. And 1,929 fetches a second is a system of its own, the web crawler, so this design starts where the pages are already stored.

Follow one query along the online half of the diagram:

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

1. A query arrives. Someone searches for monsoon flood. The query goes to the broker, the service that answers it for the whole index.
2. Not in the cache. Popular queries are answered from a cache of results. This one is not there, so the broker has to ask the index.
3. Every shard is asked. The index is split into 100 shards, each holding a slice of the pages. Any of them may hold a good match, so the query goes to all of them.
4. Each shard scores its slice. Each shard scores its own pages by how well the text matches, with a formula such as BM25, combined with each page's link score.
5. The best few come back. Each shard returns only its best few pages with their scores, not everything that matched.
6. Merged into ten. The broker merges the lists into the top ten and adds a title, an address and a snippet to each.
7. The answer. Ten results go back. The broker could only answer once the last shard had replied, so the slowest of the 100 set the latency.

The deep dives this design must answer:

• Index layout: an index split by page or by term, and why engines usually split by page.
• Ranking: BM25 scores how well a page’s text matches; PageRank scores the page itself from its links.
• Merging: each shard returns its best results, and the broker merges them into the final ten.
• Slow shards: with 100 shards in every query, one slow shard can slow most queries.
• Caching: many queries repeat, so a cache of results answers a large share of them.
• Freshness: news is crawled and indexed in minutes, stable pages once a month.
• Spam: link farms and stuffed keywords must not buy a high rank.

An answer is judged on the requirements and estimates, the pipeline, the index layout, ranking, serving latency, freshness and spam.

Two calls reach every shard: one for scores, one for snippets Pro: opens with a Pro, Premium or Ultimate pass

In this part:

• Split the index by page, and every shard is a small search engine
• BM25 scores the text, and PageRank scores the page from its links
  • PageRank by power iteration, with dead ends and a link farm, run
  • Combining the signals
• How does the broker merge 100 answers into an exact top ten?
  • Repeated queries cost nothing
• With 100 shards in every query, a slow shard is the normal case
  • Hedging after 10 ms
  • Sizing the replicas, with numbers
• News gets a tier of its own, and spam is fought at crawl and rank time
• What breaks first at 10 and 100 times the load, and in a failure?
• Practise: one round of PageRank, then the whole design
  • Write one round of PageRank, with pages that link nowhere
• Four simpler designs, and why each fails
• What each level is expected to cover
• A sample answer and a 45-minute self-mock
• Interview questions
  • What does PageRank measure, and why is it computed offline rather than for each query?
  • Your index of 5 billion pages has to be split over 100 machines. Do you split it by page or by term? Defend the choice with what happens to a two-word query, a hot term and a lost machine.
  • Every query fans out to 100 index shards. Each shard answers within 20 ms at its own 99th percentile, yet queries take 400 ms at the 99th percentile. Explain the gap and bring it under 100 ms.
  • A site with 10,000 new pages that all link to one store page now ranks first for a popular query. How do you stop link farms from buying rank without punishing genuine sites whose pages link to each other?
• Key takeaways

3 diagrams · 3 runnable examples (JavaScript, Python) · 1 exercise with sample tests · 3 interview answers · about 49 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

• Pro pass · 1 week · ₹79 · $2.99
• 30 days · ₹179 · $5.99
• 1 year · ₹1,699 · $45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Read a complete sample first: Design a news feed