Web Search Engine

Google Search

Design a web search engine: turn crawled pages into a sharded index, rank with text and link signals such as PageRank and anchor text, and answer a query from thousands of machines in a fraction of a second.

Overview

A web search engine has three jobs, and Google describes its own search the same way: crawl the web to fetch pages, index them (understand each page and store it in a giant lookup structure), and serve results for each query. The crawler is its own problem (the Web Crawler topic), and the inverted index and BM25 are covered in Search System Design. This page is about what makes web search different: the size of the corpus, links as a ranking signal, and a serving system spread over thousands of machines.

Two published designs make good anchors. Brin and Page's 1998 paper on the Google prototype describes the index structures, PageRank and anchor text on a crawl of 24 million pages. Barroso, Dean and Hölzle's 2003 paper describes how Google served queries: an index split into shards of randomly chosen documents, each shard served by a pool of replicas, and a second phase that fetches titles and snippets.

Questions to ask first

How big is the index? — About 50 billion pages, 100 KB of HTML each
How much traffic? — 100,000 queries a second on average, 3× at peak
How fast? — Results in under 300 ms at the 99th percentile
How fresh? — News within minutes; most pages within days to weeks
Which result types? — Ten blue links with titles and snippets; no ads or images
Personalization? — Language and location only

What you will be able to do

Walk a page from the repository into a compressed, sharded inverted index.
Compute PageRank and explain what anchor text adds.
Explain document-partitioned shards with replica pools, and do the capacity math.
Serve a query in two phases and keep latency down with tiers, early exit and caching.
Explain how freshness, duplicates and link spam are handled.

Key concepts

Crawl, index, serve
Forward and inverted index
Document-partitioned shards
Replica pools
PageRank
Anchor text
Posting compression
Tiered index and early exit
Canonical pages
Continuous indexing

Functional requirements

Accept a query and return the 10 best pages with title, URL and a snippet
Match words in the page body, title, URL and in anchor text pointing at the page
Support phrase queries and prefer pages where the words appear close together
Show one result per group of duplicate pages (the canonical URL)
Reflect new and changed pages: news within minutes, most pages within days
Correct obvious spelling mistakes

Non-functional requirements

p99 latency under about 300 ms at 300,000 queries a second (targets we chose)
Losing any machine, or a whole shard replica, never makes part of the index unavailable
Adding pages means adding shards; adding traffic means adding replicas
Ranking cannot be bought, and link manipulation must not dominate it

Interview questions

How is the index split across machines, and why that way?
Explain PageRank. How is it computed at web scale?
Why use anchor text?
Walk me through serving one query.
The capacity math says 190,000 index servers. How do you bring that down?
How do you keep results fresh?
How does a multi-word query score proximity?
How would you stop link spam?