How Google Search works

Google Search works in three stages: crawlers discover and fetch pages, an indexing pipeline turns them into an inverted index partitioned by document plus signals such as links and duplicate clusters, and a serving stack fans each query out to thousands of index shards and merges the best answers in a fraction of a second. The 1998 Stanford prototype already had every stage; the decades since added scale, freshness and a long list of ranking systems.

This is part 6 of the search engines series. Parts 1–5 built search for Bazaar’s 50 million products: part 1 mapped the kinds of search, part 2 built the inverted index, part 3 put it on disk, part 4 chose the engine and part 5 ran the cluster. Every one of those products lived in Bazaar’s own database. Here we scale the same ideas to the web, where you must discover pages you don’t own, judge authority from links, fight people trying to fool you, and answer billions of queries a day from hundreds of billions of pages.

Picture it first: the food guide nobody signs up for

A publisher wants a guide to every eatery in Mumbai, down to the vada pav cart outside Dadar station. Nobody registers, so scouts start from known addresses and at each stall ask, “Who else is good around here?”, adding every name to their list.

Scouts don’t visit one lane twenty times a morning, and skip boards saying “No surveyors”. Busy places are revisited weekly, a sleepy Irani café yearly. A photocopied menu seen on ten stalls is filed once. A famous chef’s nod outweighs ten strangers’, and stalls that pay touts get found out.

The guide is split into volumes, each covering a random mix of eateries with its own index. A reader’s question goes to every volume keeper; each returns their best few, and the desk merges them, answering the commonest questions from a sheet.

Map it back: scouts are crawlers, the list is the URL frontier, “who else?” is link extraction, the lane rule is politeness, the board is robots.txt, photocopies are duplicates, the chef’s nod is PageRank, touts are link spam, volumes are document-partitioned shards and the sheet is the results cache.

What changes when the corpus is the web

Bazaar’s pipeline is a closed loop: the database knows every product, change data capture reports every change, and nobody lies about what a product is. The web breaks all three assumptions.

• Discovery. There is no central registry of pages, so Google must do “URL discovery” (how Search works): follow links, read sitemaps, revisit known pages.
• Authority. Pages with the same words differ wildly in trustworthiness. Instead of sales and stock, the web offers links, anchor text and quality signals.
• Adversaries. Google says its systems find 40 billion spammy pages every day.
• Scale. Google’s index “covers hundreds of billions of webpages and is well over 100,000,000 gigabytes”: 100,000,000 GB ÷ Bazaar’s 100 GB = a million times larger.

Much survives: part 2’s inverted index, part 5’s document-partitioned shards and query-then-fetch, and part 3’s immutable, batch-built index files. New are crawling, link analysis, duplicate detection, rendering, query understanding, tiers, and serving tricks for fan-outs of thousands.

The 1998 prototype

Sergey Brin and Larry Page described the first Google in The Anatomy of a Large-Scale Hypertextual Web Search Engine (WWW7, 1998), which they believed was the first detailed public description of a large web search engine. It indexed 24 million pages with every stage of today’s pipeline (Fig. 1):

1. A URL server hands lists of URLs to the crawlers.
2. Crawlers, typically about 3, each keep roughly 300 connections open.
3. A store server compresses pages with zlib (about 3 : 1) into the repository: 147.8 GB of HTML became 53.5 GB.
4. The indexer parses pages into hits (word position, font size, capitalisation) of 2 bytes each.
5. It writes them into 64 forward barrels, each covering a range of word IDs.
6. Links go to an anchors file; the URL resolver maps them to document IDs, attaches anchor text to the page the link points to, and writes ID pairs to a links database.
7. The links database feeds PageRank.
8. The sorter re-sorts each barrel by word ID: forward index in, inverted index out.
9. The searcher combines an in-memory lexicon (14 million words, fitting a 256 MB machine), the inverted barrels and PageRank.

Two 1998 ideas still matter. Anchor text often describes a page better than the page itself, and lets you return pages you never crawled; the 24 million pages carried over 259 million anchors. And two sets of inverted barrels: a short set with only title and anchor hits (4.1 GB), searched first, and a full set (37.2 GB) for when it found too few matches: a tiered index whose first tier was 4.1 ÷ 37.2 ≈ 11% of the second. The barrels were split by word-ID range, a term-partitioned layout; at planet scale Google switched to documents.

Once stable, the crawl fetched its last 11 million pages in 63 hours: 11,000,000 ÷ (63 × 3,600) ≈ 48.5 pages a second. The indexer ran at about 54 pages a second, and four machines sorted everything in about 24 hours. Queries took 1 to 10 seconds, dominated by disk reads over NFS, with no query caching yet.

PageRank, worked by hand

PageRank scores a page by the pages linking to it: each link carries the linker’s rank, divided among its outlinks. With damping factor d (the paper usually used 0.85) and N pages:

PR(p) = (1 − d) / N  +  d × Σ PR(q) / out(q)     over every page q linking to p

The paper writes the first term as (1 − d); dividing by N makes the ranks sum to 1, as intended. Picture a random surfer who follows a random link 85% of the time and jumps to a random page 15% of the time: PageRank is the share of time spent on each page.

Take four pages (Fig. 2): A links to B and C, B and D link to C, and C links to A. Start each at 0.25; the jump term is 0.15 ÷ 4 = 0.0375.

Iteration 1. A gets C’s whole vote: 0.0375 + 0.85 × 0.25 = 0.250. B gets half of A’s: 0.0375 + 0.85 × 0.125 = 0.144. C gets half of A’s plus all of B’s and D’s: 0.0375 + 0.85 × (0.125 + 0.25 + 0.25) = 0.569. D, with no inbound links, gets 0.0375.

Iteration 2. A = 0.0375 + 0.85 × 0.569 = 0.521; B = 0.0375 + 0.85 × 0.125 = 0.144; C = 0.0375 + 0.85 × (0.125 + 0.144 + 0.0375) = 0.298; D stays 0.0375. Each round sums to 1.

Rank sloshes between A and C, then settles after about 20 rounds with A (one inbound link) almost level with C (three): A’s one link comes from the best page and carries its whole vote. Who links to you matters more than how many. The paper computed PageRank for 26 million pages in a few hours on one workstation.

Two wrinkles. A dangling page with no outlinks leaks rank; the usual fix spreads its rank over every page, as if the surfer jumped. And PageRank invited link spam: Google says spammers soon began paying each other for links. Penguin fought link spam from 2012 and joined core ranking in 2016; PageRank, which “has evolved a lot”, is still a core ranking system.

Crawling at web scale

A crawler is a loop (Fig. 3): pick a URL, check permission, fetch, render, deduplicate, index, extract links, repeat. The hard questions are what next and how fast. The URL frontier answers both: a prioritiser orders URLs by importance and likelihood of change, and per-host queues with a next-allowed fetch time keep a thousand fetchers off any one small site.

Crawl budget. Google’s per-host crawl capacity limit, or hostload, caps how long a server spends holding Google’s connections: it starts conservative, rises while the site answers fast, and falls on slow responses, 5xx errors or 429s. Crawl demand depends on popularity, staleness and the site’s apparent size. The budget is what Google can and wants to crawl, per hostname.

robots.txt. Martijn Koster’s 1994 convention became RFC 9309 in September 2022. Among allow and disallow rules the longest match wins, allow breaking ties. A 4xx means no file, so anything may be crawled; a 5xx or network failure means assume complete disallow. Cached copies shouldn’t outlive 24 hours, and parsers must read at least 500 KiB. Google ignores crawl-delay, and on a 5xx pauses the site for 12 hours, then uses the last good copy for up to 30 days. It is a request, not access control. Sitemaps add URLs with optional lastmod hints.

Recrawl scheduling. Google’s crawlers learn how often content seems to change and revisit as needed. Suppose (illustrative numbers) you can fetch 1 billion pages a day and know 50 billion URLs: uniform recrawling revisits each every 50 days. Recrawl the 500 million fastest-changing pages daily and the other 49.5 billion share 0.5 billion fetches a day: one visit every 99 days. Scheduling is choosing who goes stale.

Rendering. JavaScript-built pages are empty shells as raw HTML. Google queues every page that returns 200 for rendering unless it is marked noindex; when resources allow, a headless evergreen Chromium runs the scripts, and the rendered HTML is indexed and mined for links. Rendering can lag by seconds or more and costs far more than parsing. With mobile-first indexing, Google indexes the mobile version, fetched with its smartphone agent.

Duplicates and canonical pages

The web repeats itself: mirrors, ?utm_source= variants, print versions, one press release on 500 news sites. Exact copies are caught by checksums; the 1998 document index already stored one per page. Near-duplicates, identical except for ads, counters or timestamps, need more.

Google’s published answer is Charikar’s SimHash, in Manku, Jain and Das Sarma’s Detecting Near-Duplicates for Web Crawling (WWW 2007). Turn a page into weighted features and hash each to 64 bits; for each bit position, add the feature’s weight if the bit is 1 and subtract it if 0; the sign of each total becomes one fingerprint bit. Unlike SHA-1 or MD5, similar pages get similar fingerprints, a few bits apart.

For 8 billion pages, 64-bit fingerprints with a threshold of k = 3 differing bits gave precision and recall both near 0.75. That is 8 billion × 8 bytes = 64 GB of fingerprints to check each new page against in milliseconds, and probing every fingerprint within 3 bits would take C(64, 3) = 41,664 lookups. The trick is pigeonhole: split the 64 bits into 4 blocks of 16; fingerprints differing in at most 3 bits share at least one whole block. Keep 4 sorted copies of the table, each keyed by a different block, and a check becomes 4 exact-prefix probes. A near-duplicate can then be skipped with its outlinks, or just deprioritised.

Canonicalisation picks one copy to represent the group. Google clusters similar pages and selects the most representative as the canonical, with rel="canonical" as a hint. The Percolator paper states the invariant: only the highest-PageRank URL among duplicates appears in the index, and links to any duplicate are forwarded to it, carrying their anchor text.

Partitioning the index: by document, not by term

An index of hundreds of billions of pages must be split, in one of two ways (Fig. 4).

Term-partitioned (global) index. Each shard owns a range of terms and their full posting lists, so “chai recipe” visits only two shards. But intersecting needs both lists in one place, so one shard ships millions of postings to another; a hot term overloads its owner; and one new page updates a shard for every distinct term on it.

Document-partitioned (local) index. Each shard holds a subset of pages with a complete inverted index over them. Every query goes to every shard; each intersects and scores alone and returns its local top k for a root to merge. You pay a fan-out to all shards; you gain shards that never talk to each other, load spread by random assignment, and new pages that touch one shard.

Google chose documents. Barroso, Dean and Hölzle’s Web Search for a Planet (IEEE Micro, 2003) describes index shards, each a “randomly chosen subset of documents”, served by a pool of replicas behind a load balancer. Replicas add query capacity, shards absorb growth, and because shards never communicate the speedup is nearly linear; a dead replica costs capacity, not documents. Pages are partitioned the same way onto doc servers holding text for snippets, so Google kept “dozens of copies of the Web”. In 2003 one query read hundreds of megabytes and burned tens of billions of CPU cycles, on clusters totalling over 15,000 commodity PCs.

That is Bazaar’s design from part 5: Elasticsearch shards are document-partitioned by hash(_id), and its query and fetch phases mirror Google’s index servers and doc servers.

Tiers. Fanning every query out to the whole index wastes work. A tiered index searches a smaller, higher-quality or fresher slice first and goes deeper only when needed, like the 1998 short barrels. Before 2010 Google’s index had several layers refreshed at different rates, the main one every couple of weeks. The Tail at Scale adds selective replication: extra copies of popular and important documents, and at times language-biased partitions re-replicated as the day’s query mix shifts. Google hasn’t published its current tiers, so any specific split is a guess.

From batch rebuilds to Caffeine

Part 3 showed why Lucene never edits a segment: immutable files are easy to cache and serve. Early Google treated its whole index that way: read-only while serving, updated by draining a replica, changing it and putting it back.

Building it was batch work. Peng and Dabek’s Percolator paper (OSDI 2010) describes the old pipeline: each day several billion documents, plus the existing repository, went through about 100 MapReduces. Batches keep invariants easy, since duplicate clustering finishes before link inversion starts. But new pages link to old ones, so updates re-ran the MapReduces over the whole repository, and a document spent 2–3 days being indexed.

Percolator made it incremental, on Bigtable:

• Transactions. Cross-row ACID transactions with snapshot isolation (MVCC at planet scale), built from Bigtable’s single-row transactions, timestamped versions, locks stored in Bigtable and a timestamp oracle.
• Observers. Code that runs when a watched column changes and triggers the next observer: a new page triggers clustering, which triggers link inversion, and so on.

The Percolator-based system is Caffeine, announced on 8 June 2010 with “50 percent fresher results”. The paper’s numbers: the same documents per day, the median document over 100× faster, results’ average document age down nearly 50%, and 10 observers instead of 100 MapReduces.

You pay in efficiency: about 4× the write cost of raw Bigtable and roughly 30× a traditional database’s CPU per transaction on a TPC-E-like benchmark. It is part 3’s refresh trade-off at planet scale, freshness bought with throughput (batch vs stream processing). How serving shards absorb the updates is not public.

Serving a query

The 2003 cluster paper and Dean and Barroso’s 2013 The Tail at Scale give this path (Fig. 5):

1. DNS picks a nearby cluster; a load balancer picks a front-end server (the Google Web Server, GWS, in 2003) to coordinate.
2. Query understanding: spelling, synonyms, language, intent. Google says the language models behind it took over five years to develop and significantly improve results in over 30% of searches.
3. Results cache. Popular queries repeat, so a cache keyed by normalised query, language and location can return a whole page, with short expiry for news. Google hasn’t published its cache design.
4. Scatter. On a miss, a root sends the query through intermediate servers to one replica of every leaf shard.
5. Gather. Each leaf returns its local top k; intermediates and the root merge, like part 5’s coordinator.
6. Fetch. Doc servers return title, URL and a query-specific snippet for the winners.
7. Blend. Ads and other features run in parallel; the front end assembles the page.

The latency budget. Google says it works to shave milliseconds: any feature that adds latency must be offset elsewhere. Fig. 5 splits an illustrative 200 ms: 60 of network both ways, 15 for the front end, 70 for the leaf fan-out, 25 for merging and snippets, 10 for assembly, 20 spare. The fan-out is the biggest, riskiest slice.

The load. Google processes billions of searches a day. At a round 5 billion, 5,000,000,000 ÷ 86,400 ≈ 58,000 queries a second on average. If each touched 1,000 leaves, that is 58 million leaf requests a second, which is why caching and tiers pay for themselves.

Taming the tail at 1,000 shards

If each leaf is slow 1% of the time, a query waiting for all n leaves is slow with probability 1 − 0.99ⁿ: 63% for 100 leaves, The Tail at Scale’s headline, and 1 − 0.99¹⁰⁰⁰ ≈ 99.996% for 1,000. In one measured Google service, a single leaf’s p99 was 10 ms but waiting for all leaves took 140 ms, half of it spent on the slowest 5%. The paper’s fixes:

• Hedged requests. If a replica hasn’t answered by the p95 latency, ask another and take the first answer, for about 5% extra load. Reading 1,000 Bigtable keys across 100 servers, hedging after 10 ms cut p99.9 from 1,800 ms to 74 ms with 2% more requests.
• Tied requests. Queue on two servers that know about each other; the first to start cancels its twin. With a 1 ms delay, median latency fell 16% and p99.9 about 38%.
• Micro-partitions. About 20 per machine, so load moves in 5% steps and a dead machine’s work spreads widely.
• Selective replication and probation. Extra copies of hot documents; slow machines are benched but get shadow requests until they recover.
• Good enough. Answer once enough leaves reply; the chance one leaf holds the best result is under 1 in 1,000. Late ads or spelling suggestions are skipped.
• Canary requests. Try one or two leaves first, so a query that crashes servers crashes two, not thousands.

Ranking today, as Google describes it

Google publishes a guide to its ranking systems and a How Search works site. They name systems and signals, never weights:

• Signals. Meaning, relevance, quality, usability and context such as location and language, weighted per query.
• Language understanding. RankBrain relates words to concepts; neural matching matches concept representations in queries and pages; BERT reads how word combinations change meaning; passage ranking scores sections of a page. MUM, Google says, isn’t used for general ranking, only specific applications.
• Links and freshness. Link analysis, PageRank included, remains core; “query deserves freshness” systems turn “earthquake” into news right after one.
• Quality and spam. Reliable-information, reviews and original-content systems; the 2022 helpful content system joined core ranking in March 2024. SpamBrain enforces the spam policies.
• The results page. Deduplication hides near-identical listings; site diversity generally shows at most two results per site at the top.
• Evaluation. In 2023 Google ran 719,326 search quality tests, 124,942 side-by-side experiments and 16,871 live traffic experiments, leading to 4,781 launches. Rater scores “do not directly impact ranking”.

AI Overviews and AI Mode sit on the same index: supporting links must be indexed and snippet-eligible, and both may fan one question out into several related searches.

1998, today and Bazaar side by side

Going deeper: what makes web search hard

• Spam is adversarial ranking. Every public signal gets gamed: keyword stuffing beat term counts, PageRank bred link farms, cloaking shows crawlers different content. Defences are classifiers, demotions, manual actions and secret weights; the 1998 paper noted that aiming the random jump at trusted pages makes PageRank far harder to mislead.
• Freshness vs completeness. Every fetch re-checking a news page is one not spent discovering a new page.
• Duplicates waste crawl budget, index space and result slots; a wrong canonical sends traffic to the wrong URL.
• Crawl traps. Infinite calendars, session IDs and faceted filters (?colour=red&size=m&sort=price) spawn endless URLs. Normalise URLs, cap URLs per host and depth, and remember seen URLs in a Bloom filter.
• Index size vs serving cost. Every indexed page costs disk, RAM and CPU on every query reaching its shard, times the replicas. Tiers and not indexing everything (indexing “isn’t guaranteed”) are cost controls.
• Hot queries. Breaking news hammers the same cache keys and leaves: hot keys and stampedes at planet scale.

Cheat sheet

How to say it in the interview

“Web search has three stages. Crawlers pull URLs from a frontier that prioritises by importance and change rate, with per-host queues for politeness; they obey robots.txt, render JavaScript and drop near-duplicates with SimHash. The indexer builds an inverted index partitioned by document, each shard a random slice of pages with a replica pool; links give PageRank and anchor text. Updates flow in incrementally, as Caffeine did on Percolator. A query is rewritten, checked against a results cache, fanned out to every shard, merged from each shard’s top k, and given snippets by doc servers. With 1,000 shards the tail dominates, so I hedge requests, accept good-enough results and use tiers.”

How would you shard a web-scale index? By document, randomly, with a full inverted index and a replica pool per shard. Replicas add query capacity, shards add room; shards never talk, so scaling is nearly linear.

Why not partition by term? Fewer shards per query, but long posting lists cross the network, hot terms overload their owner, and one new page updates a shard per term. Document partitioning pays a fan-out instead, which replicas and tail tricks absorb.

How does PageRank handle dangling pages and spam? A dangling page’s rank is spread over all pages, like the surfer jumping; damping guarantees every page a floor and convergence. Spam needs classifiers, trust-seeded jumps and demotions.

How do you keep the index fresh? Recrawl by observed change rate within each host’s budget, use sitemap lastmod hints, and index each page incrementally: Percolator replaced a 2–3 day batch pipeline and made results about 50% younger.

How do you meet 200 ms with 1,000 shards? Cache popular queries, try a small tier first, hedge requests slower than their p95, return when nearly all shards answer, skip late extras, and replicate hot documents.

Where to go next

• Next in the series: Search end to end: from crawl to ranked results: the whole pipeline as one design, from ingestion to the ranking funnel.
• Earlier parts: Types of search, Search data structures, Disk I/O and durability for search, Choosing a search engine and Elasticsearch in depth.
• Design a web crawler, Design a search engine like Google and Design typeahead (autocomplete): the interview problems.
• Consistent hashing, Database sharding and Data replication: partitions and replicas.
• Content delivery network, Distributed caching and Timeouts, retries and backoff with jitter: caching and hedging.

References and further reading

1. Brin and Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine (WWW7, 1998), archived copyweb.archive.orgThe prototype’s architecture, PageRank with d = 0.85, anchor text, hit lists and barrels, Table 1 storage figures, crawl and indexing rates and 1–10 s query times.
2. Google: How Google Search organizes informationgoogle.com“Hundreds of billions of webpages” and an index “well over 100,000,000 gigabytes”; recrawling paced by how often content changes.
3. Google Search Central: In-depth guide to how Google Search worksdevelopers.google.comThe three stages, URL discovery, rendering with a recent Chrome, duplicate clustering and canonical selection, and that indexing isn’t guaranteed.
4. Google Search Central: A guide to Google Search ranking systemsdevelopers.google.comBERT, RankBrain, neural matching, MUM’s limited use, PageRank as a core system, freshness, reviews, SpamBrain, site diversity and retired systems with dates.
5. RFC 9309: Robots Exclusion Protocol (September 2022)rfc-editor.orgLongest-match rules, 4xx versus 5xx handling, 24-hour caching and the 500 KiB minimum parsing limit.
6. Barroso, Dean and Hölzle, Web Search for a Planet: The Google Cluster Architecture (IEEE Micro, 2003)research.google.comDNS and hardware load balancing, index shards of random documents served by replica pools, doc servers, read-only serving and per-query cost.
7. Peng and Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications (OSDI 2010)usenix.orgPercolator’s transactions and observers; the old 100-MapReduce pipeline, 2–3 days per document, 100× lower latency and ~50% younger results; overheads.
8. Google blog: Our new search index: Caffeine (8 June 2010)googleblog.blogspot.comThe layered old index whose main layer updated every couple of weeks, “50 percent fresher results” and Caffeine’s scale in 2010.
9. Dean and Barroso, The Tail at Scale (Communications of the ACM, 2013)barroso.orgFan-out arithmetic, a measured root-to-leaf latency table, hedged and tied requests, micro-partitions, selective replication, good-enough results and canaries.
10. Manku, Jain and Das Sarma, Detecting Near-Duplicates for Web Crawling (WWW 2007)research.google.comSimHash fingerprints for 8 billion pages, k = 3 bits, 64 GB of fingerprints, permuted tables and batch throughput.