Engineering Atlasby Abhishek Goyal
System design / Search & storage

How Google Search Works: Crawling, Indexing, Ranking and Serving at Scale

How Google Search works, explained for system design interviews: a polite web crawler with a URL frontier and robots.txt, the inverted index, PageRank with the random surfer, why Google shards its index by document, serving with caches and index servers, and the move from batch rebuilds to Caffeine and Percolator.

By Abhishek Goyal Read time ~12 min read Level Beginner → Senior Stack Googlebot, robots.txt, MapReduce, Bigtable, Percolator, PageRank Members
On this page
  1. A library that reads the whole web in advance
  2. Crawling: the frontier, politeness and robots.txt
  3. Indexing: from pages to an inverted index
  4. PageRank: the random surfer
  5. Ranking signals, at a high level
  6. Splitting a planet-sized index: by document or by word
  7. Serving: the index tree, caching and tail latency
  8. Freshness: from batch rebuilds to Caffeine and Percolator
  9. How this shows up in HLD interviews

Google's first index, in 1998, had 26 million pages. Ten years later, its systems had seen 1 trillion unique URLs. At the level that matters for an interview, the machine behind that is four steps you already know from this series: crawl, index, rank, serve. The hard part is doing each one politely, in parallel and fast.

Where this fits: Part of the Search & storage series. The core journey searched one site's index; this is the same idea at planet scale.

Before you start: How search engines work (inverted index, BM25) and Elasticsearch (shards, scatter-gather). Storage data structures is optional.

After reading this you will be able to

  • Design a polite crawler: a URL frontier, robots.txt checks, per-host rate limits and a seen-URL set.
  • Explain PageRank with the random surfer, and why it is one signal among hundreds.
  • Argue for sharding a web index by document rather than by word.
  • Explain how Google moved from rebuilding its index every few weeks to updating it continuously.

01A library that reads the whole web in advance

Imagine a librarian who walks every shelf of every library in the world (crawl), writes an index card for every word (index), notes which books other books cite most (PageRank), and hands you the best ten in a fraction of a second (serve). The key idea: when you search, you are searching Google's index, not the live web.

A few terms, one line each:

  • Crawler (Googlebot): a program that downloads pages and follows their links.
  • URL frontier: the queue of URLs waiting to be fetched.
  • Canonical URL: the one version Google keeps when several URLs show the same page.
  • Shard: one slice of the index, held on its own group of machines.

Google's own guide names three stages: crawling, indexing and serving. I split ranking out because interviewers ask about it separately. Here is the whole pipeline.

Fig. 1

Google Search pipeline: work done before you search, and work done when you search

Google Search pipeline: work done before you search, and work done when you searchTop row, before you search: URL discovery feeds the frontier, then crawling by Googlebot, rendering with Chrome, and indexing. Bottom row, when you search: your query goes to serving (cache and index servers), then ranking, then results. The index connects down to serving; the query never touches the live web.Before you searchWhen you searchprebuilt indexURL discoverylinks + sitemapsFrontierwhat to fetch nextCrawlGooglebotRenderrecent ChromeIndexinverted indexYour querycheap flights goaServecache + index serversRankhundreds of signalsResultsten blue links
The top row happens before you ever type. Only the bottom row runs on your query, and it never touches the live web.

02Crawling: the frontier, politeness and robots.txt

There is no central list of web pages. Google discovers URLs from links on pages it already knows and from sitemaps. Crawling starts from well-connected seed pages and follows links outward.

In Brin and Page's 1998 paper, a URLserver handed URLs to several distributed crawlers, a storeserver compressed the pages into a repository, and every URL got a number, its docID. That URLserver is an early URL frontier.

Today Googlebot decides what to crawl and how often, and learns how often content changes. It is polite: when a site returns HTTP 500 errors, Googlebot slows down. Pages are rendered with a recent Chrome, so JavaScript content is visible too.

robots.txt Definition

A text file at a site's root listing which paths crawlers may fetch. The rules are standardised in RFC 9309, where the most specific matching rule wins. Google is clear that it manages crawler traffic and "is not a mechanism for keeping a web page out of Google" (Search Central).

Now, how you'd design it. This is a standard interview crawler, not Google's internals.

Fig. 2

A polite crawler loop, as you would design it in an interview

A polite crawler loop, as you would design it in an interviewSeed URLs enter the frontier, which keeps one queue per host. Each URL passes a robots.txt check, then a fetcher that is rate-limited per host and backs off on errors. Fetched pages are parsed and rendered, a link extractor pulls out new URLs, and a seen-URL check (for example a Bloom filter) drops URLs already known before the rest go back into the frontier.pageunseen onlySeed URLswell-linked pagesFrontierone queue per hostrobots.txt checkallowed to fetch?Fetcherrate limit + backoffSeen-URL checkBloom filterLink extractornew URLsParse + rendertext, links, JSHow you'd design it, not Google's internals
The crawler is a loop. The frontier decides what's next, politeness decides how fast, and the seen-URL check stops you fetching the same page forever.

Notice two things. The frontier keeps one queue per host, so fetchers can spread load across sites. And the seen-URL check runs on billions of URLs, so it needs to be small.

Seen this before?

"Have I seen this URL?" over billions of URLs is a natural fit for a Bloom filter: a few bits per URL, no false "no", and a small chance of a false "yes" (you skip a page you never crawled). We cover it in Storage data structures. This is our suggestion for your design, not a claim about Google.

03Indexing: from pages to an inverted index

In 1998 the indexer turned each page into hits: a word, its position, an approximate font size and capitalisation. Hits were grouped by document, a forward index, then a sorter re-sorted them by word into the inverted index:

Fig. 3

Flipping a forward index into an inverted index

Flipping a forward index into an inverted indexLeft, the forward index: doc1 contains cheap, flights and goa; doc2 contains goa and beaches. A sort by word flips it into the inverted index on the right: cheap maps to doc1, flights to doc1, goa to doc1 and doc2, beaches to doc2.Forward index (by document)Inverted index (by word)sortdoc1cheap, flights, goadoc2goa, beachescheapdoc1flightsdoc1goadoc1, doc2beachesdoc2
Same data, flipped. The forward index is easy to write as you crawl; the inverted index is fast to search.

One clever trick: anchor text, the clickable words of a link, is credited to the page the link points to. A page that many sites link to as "cheap flights" can match that query even if it was never crawled.

The paper's storage table lists 24 million pages fetched, a 53.5 GB compressed repository, a 37.2 GB inverted index and a 293 MB lexicon (the list of all words).

Today, indexing analyses text, tags and media, clusters duplicates and picks a canonical, and stores signals like language and country in an index "hosted on thousands of computers". A crawled page may never make it in.

Seen this before?

The inverted index is the heart of How search engines work. LinkedIn's Galene keeps both a forward and an inverted index too; see Search case studies.

04PageRank: the random surfer

Imagine someone clicking random links forever, now and then getting bored and jumping to a random page. PageRank is the share of time they spend on each page. A link from a busy page sends more visitors, and a page that links to fifty others splits its visitors fifty ways.

The paper writes it like this, where T1 to Tn are the pages linking to A, and C(T) is how many links T has:

PR(A) = (1 - d) + d * ( PR(T1)/C(T1) + ... + PR(Tn)/C(Tn) )

The damping factor d, usually 0.85, is the chance the surfer keeps clicking. You compute it by iteration: start every page at 1, apply the formula, repeat until the numbers settle. For 26 million pages that took "a few hours on a medium size workstation".

Try it first

Three pages. A links to B and C. B links to C. C links to A. Which page ranks highest? Guess before reading on.

C wins, but only just. With d = 0.85, my own arithmetic gives C about 1.19, A about 1.16 and B about 0.64. C gets half of A's vote plus all of B's. A has one link, but it carries all of C's vote. The lesson: who links to you matters more than how many.

A slightly bigger web, each page sized by rank:

Fig. 4

PageRank on a five-page web, with each page sized by its rank

PageRank on a five-page web, with each page sized by its rankFive pages with links A to B, A to C, B to C, C to A, D to C, E to C and E to D. With damping 0.85 the ranks come out roughly: C 1.93, A 1.79, B 0.91, D 0.21, E 0.15. C is drawn largest and E smallest. A dashed random jump shows the surfer occasionally landing on any page.all of C's voteArank 1.79Brank 0.91Crank 1.93D0.21E0.15Random jump15% of the time, any page
Pages linked from strong pages grow. The random jump (dashed) keeps rank from getting stuck in a loop and gives every page a small floor.

Keep it in proportion

PageRank made Google famous, but today relevance uses "hundreds of factors" (Search Central). Treat it as one signal, not the ranking.

Members-only article

Keep reading with the Article Pass

You've read the free part. The other 5 sections of this guide, with every diagram and worked example, are for members. One Article Pass unlocks every members-only article on Engineering Atlas: the ones live today and every one I publish while your pass is active.

  • Ranking signals, at a high level
  • Splitting a planet-sized index: by document or by word
  • Serving: the index tree, caching and tail latency
  • Freshness: from batch rebuilds to Caffeine and Percolator
  • How this shows up in HLD interviews
Become a member Sign in

From ₹49 · one-time payment, no auto-renewal · separate from course passes

Interview practice

Used in these design problems

Keep learning