Design a Web Search Engine

A search engine can't read the whole web every time you search, so it does the hard work in advance. A crawler discovers pages, an inverted index files every word against the pages that use it, and ranking decides the order. Your query is then just a lookup plus a sort. This is the shape of Google, from the 1998 'Anatomy' paper onward.

Crawl — fetch the web

A crawler (Googlebot) fetches pages automatically. A URL frontier — the to-do list of URLs — feeds addresses to crawlers; each fetched page is stored and compressed, and new links found on it go back into the frontier. It must be polite: per-site rate limits and duplicate removal. One modern step didn't exist in 1998 — Googlebot now renders each page in a headless Chrome, running its JavaScript, before indexing.

Index — invert the data

The inverted index flips a page-to-words layout into a word-to-pages one: for each word, a posting list of every page containing it. That is what makes search fast — you never read whole documents at query time, you read a few lists. A subtle rule: a link's anchor text is credited to the page it points to, not the page it sits on, so a page can rank for words that describe it from the outside.

Forward (per page):   page 7  -> { system, design, scaling }
Inverted (per word):  "system"  -> [ page 7, page 42, page 99, ... ]   (posting list)
                      "design"  -> [ page 7, page 42, page 305, ... ]

Query "system design"  ->  intersect the two posting lists  ->  { page 7, page 42, ... }

Query — look up and intersect

A search for system design fetches the posting list for each term and intersects them to find pages containing all the words. The cost is proportional to the length of those lists, not to the size of the web — that is the whole payoff of building the index up front.

Rank — never just PageRank

A query can match millions of pages, so order is everything. PageRank scores a page's importance: a link is a vote of confidence, and a page is important if many *important* pages link to it — a recursive definition, stabilized by a damping factor (~0.85) modelling a random surfer who usually follows a link but sometimes jumps. Crucially, ranking was never just 'sort by PageRank': even in 1998 it combined PageRank (importance) with where and how the words matched (relevance).

Scale — shard the index, gather results

The web is too big for one machine, so the inverted index is partitioned (sharded) across many — the 1998 paper split words into 64 'barrels' by word range, a prototype number, not today's scale. A query is scattered to the shards, each returns its top matches, and the results are gathered and merged (scatter/gather). Because a small set of queries is hugely repeated, popular queries are cached — their ranked answers kept ready to return.

1. 1Crawl: frontier feeds crawlers; store pages; new links return to the frontier.
2. 2Index: build word → posting-list, incrementally (Caffeine).
3. 3Query: fetch and intersect posting lists for the terms.
4. 4Rank: score candidates by PageRank + relevance + hundreds of signals.
5. 5Serve: scatter to sharded barrels, gather top results, cache hot queries.