Design Google Search

Web search is four loosely coupled systems pretending to be one: a crawler that pulls the changing web into local storage, an indexer that turns documents into queryable posting lists, a ranker that scores documents per query against hundreds of signals, and a serving layer that fans the query out across thousands of shards and merges the results inside a sub-second budget. This design walks each pillar at the level a senior engineer needs to recognise the trade-offs in a real system: how Google moved from batched MapReduce indexing to incremental indexing on Percolator, why the index is partitioned by document and not by term, how tail latency is mitigated, and where you can credibly substitute commodity components when you build your own.

Mental model

Pin five concepts in this order — the rest of the article folds onto them:

1. Inverted index. A map from term → ordered posting list of documents containing that term. Almost every retrieval question reduces to “how do I store, partition, compress, and intersect posting lists at scale?”
2. Document-partitioned sharding. The index is split by document, not by term: each shard holds a complete inverted index for its slice of the corpus. Every query fans out to every shard (why this beats term-partitioning at web scale).
3. Caffeine + Percolator. Indexing is incremental, not batch: a crawl writes a row to Bigtable, Percolator observers fire, the inverted index for the affected terms is rewritten in place. The repository is never rebuilt from scratch.
4. Ranking is a stack, not a function. Cheap signals (PageRank, BM25, freshness) cut the candidate set; expensive learned models (BERT, MUM, RankBrain) re-rank the survivors. Cost grows with quality; budget is enforced top-down.
5. Tail latency is the budget. With thousands of shards per query, the slowest shard sets the wall-clock time. The serving layer is engineered around hedged and tied requests, early termination, and partial results — not around making any single shard fast.

The propagation rule: a freshly crawled page can be served minutes later through the fresh tier and is reflected in the main index within hours, depending on the page’s importance and Caffeine’s per-row update budget.

Requirements

Functional

Non-functional

Scale estimation

Anchored to the most recent Google statement on volume — “more than 5 trillion searches per year”, confirmed by Sundar Pichai in March 2025³:

1Annual queries:  > 5 × 10^122Daily queries:   ~14 × 10^93QPS (avg):       ~160 K4QPS (peak):      ~3× avg → ~500 K (depending on time-zone overlap and event spikes)5Autocomplete:    ~10× search QPS (one request per keystroke after the first)

1Indexed pages:    hundreds of billions     [Google "How Search Works"]2Index data size:  > 100,000,000 GB ≈ > 100 PB3Per-page storage: ~100 KB compressed HTML4Per-page index:   ~10–20% of raw → posting lists in the hundreds of PB

1URL discovery:   tens of billions of new URLs/day (sitemaps + outlinks)2Pages crawled:   prioritised subset; politeness-bound per origin3Bandwidth:       petabytes/day across all crawlers

1Bigtable / Colossus:2  Bigtable clusters    = thousands of machines3  Colossus filesystems = single clusters scale to multiple exabytes;4                          some exceed 10 EB[^colossus]5  Index shards         = thousands per datacenter6  Replication factor   = ≥ 3 for durability + intra-DC failure tolerance

Design paths

The shape of the index dictates the rest of the system. Three reasonable shapes:

Path A — monolithic single-datacenter index

Useful when:

• The corpus fits in a single cluster.
• Query volume is in the low thousands of QPS.
• Daily batch rebuilds are acceptable.

• Single index copy, simpler consistency.
• Vertical scaling on a few large boxes.
• Batch index rebuild; downtime or a stale read window during the swap.

Trade-offs:

• Simpler architecture and easier debugging; no distributed coordination overhead; strong consistency.
• Bounded by single-datacenter capacity; no geographic redundancy; rebuild windows force staleness.

Real-world example: Elasticsearch single-cluster deployments for enterprise search, comfortable into the billions of documents and thousands of QPS before coordination overhead bites.

Path B — distributed sharded index (Google’s shape)

Useful when:

• The corpus is web-scale.
• A global user base demands low edge latency.
• Continuous updates rule out rebuild windows.

• Index partitioned across thousands of machines.
• Each query fans out to all shards in parallel (this is the source of the tail-latency problem).
• Results are aggregated and re-ranked centrally.
• Shards are replicated across datacenters for redundancy and edge latency.

Trade-offs:

• Effectively unlimited horizontal scaling; geographic distribution; continuous updates; shard-level fault tolerance.
• Distributed coordination complexity; tail latency challenges (the slowest shard wins); cross-shard ranking requires a globally comparable score.

Real-world example: Google Search uses document-partitioned sharding with thousands of shards per datacenter. Index updates flow continuously through Caffeine; each shard handles a slice of the documents independently.

Path C — tiered index (hot / warm / cold)

Useful when:

• The query distribution is heavy-tailed.
• Storage cost is a meaningful constraint.
• Different latency budgets for popular vs. rare queries are acceptable.

• Most queries served from the hot tier (RAM-resident posting lists).
• Warm tier on SSD covers mid-frequency terms.
• Cold tier on HDD/object storage covers the long tail.
• The split between tiers is a tunable engineering choice, not a fixed law; the typical pattern is “small fraction of terms account for most query volume”.

Trade-offs:

• Optimal cost/performance ratio; sub-millisecond latency for popular queries; graceful degradation for rare ones.
• Tiering logic complexity; cache invalidation challenges; cold-start spikes when a previously cold term becomes popular.

Real-world example: Google combines tiered indexing with sharding. Frequently accessed posting lists stay memory-resident; cold terms live on disk. The system promotes/demotes based on access patterns rather than fixed quotas.

Path comparison

What this article assumes

The rest of the article assumes Path B with Path C optimisations. Web-scale search needs horizontal scaling beyond a single datacenter, users expect sub-second latency regardless of location, and modern serving layers combine document-partitioned shards with tiered storage for cost efficiency.

High-level design

Component overview

Request flow

Crawl pipeline

API design

Search query

1GET /search?q=distributed+systems&num=10&start=02Authorization: Bearer {api_key}3Accept-Language: en-US4X-Forwarded-For: {client_ip}

Response (200 OK):

1{2  "query": {3    "original": "distribted systems",4    "corrected": "distributed systems",5    "expanded_terms": ["distributed computing", "distributed architecture"]6  },7  "search_info": {8    "total_results": 2340000000,9    "search_time_ms": 187,10    "spelling_correction_applied": true11  },12  "results": [13    {14      "position": 1,15      "url": "https://example.com/distributed-systems-guide",16      "title": "Distributed Systems: A Comprehensive Guide",17      "snippet": "Learn about distributed systems architecture, including consensus algorithms, replication strategies, and fault tolerance...",18      "displayed_url": "example.com › guides › distributed-systems",19      "cached_url": "https://webcache.example.com/...",20      "page_info": {21        "last_crawled": "2026-03-15T10:00:00Z",22        "language": "en",23        "mobile_friendly": true24      }25    }26  ],27  "related_searches": ["distributed systems design patterns", "distributed systems vs microservices"],28  "knowledge_panel": {29    "title": "Distributed system",30    "description": "A distributed system is a system whose components are located on different networked computers...",31    "source": "Wikipedia"32  },33  "pagination": {34    "current_page": 1,35    "next_start": 10,36    "has_more": true37  }38}

Autocomplete

1GET /complete?q=distrib&client=web

1{2  "query": "distrib",3  "suggestions": [4    { "text": "distributed systems", "score": 0.95 },5    { "text": "distributed computing", "score": 0.87 },6    { "text": "distribution center near me", "score": 0.72 },7    { "text": "distributed database", "score": 0.68 }8  ],9  "latency_ms": 810}

Autocomplete must complete in well under 100 ms. Suggestions come from a separately optimised, trie-based index of popular queries — not the main document index.

Crawl status (internal API)

1GET /internal/crawl/status?url=https://example.com/page2Authorization: Internal-Service-Key {key}

1{2  "url": "https://example.com/page",3  "canonical_url": "https://example.com/page",4  "last_crawl": "2026-03-15T08:30:00Z",5  "next_scheduled_crawl": "2026-03-16T08:30:00Z",6  "crawl_frequency": "daily",7  "index_status": "indexed",8  "robots_txt_status": "allowed",9  "page_quality_score": 0.7810}

Data modelling

Document storage in Bigtable

Crawled pages live in a Bigtable “webtable” — the canonical example from the Bigtable paper, OSDI 2006. Row keys are the page URL with the hostname components reversed, so all pages from one host land in contiguous rows.

The paper’s own example: maps.google.com/index.html is stored under row key com.google.maps/index.html. This makes range scans for com.google.* cheap, gives the on-disk Bentley–McIlroy compression a long run of common-host boilerplate to deduplicate, and lets host- and domain-level analyses (link graph aggregation, robots.txt cache, per-host quality) run as a contiguous scan rather than a scatter.

Column families:

Schema (conceptual):

1Row: com.example.www/distributed-systems2├── content:html        → "<html>..."3├── content:text        → "Distributed systems are..."4├── content:title       → "Distributed Systems Guide"5├── links:outlinks      → ["com.other.www/page1", "org.wiki.en/dist"]6├── links:inlinks       → ["com.blog.www/article", ...]7├── crawl:last_crawl    → 1742044800 (timestamp)8├── crawl:status        → "success"9├── quality:pagerank    → 0.0004210└── quality:spam_score  → 0.02

Inverted index structure

The inverted index maps terms to posting lists — ordered lists of documents containing that term, with positions and frequencies attached. The same shape — per-term lists ordered by docID with positions, frequencies, and “fancy hits” carrying font/anchor/title weight — is what Brin & Page described as Google’s barrels in 1998⁶, and it is what Lucene-derived engines (Elasticsearch, OpenSearch, Solr) and Vespa still expose today.

Posting list (logical):

1Term: "distributed"2├── Document IDs: [doc_123, doc_456, doc_789, ...]3├── Positions:    [[5, 23, 107], [12], [3, 45, 89, 201], ...]4├── Frequencies:  [3, 1, 4, ...]5└── Quality hints: [0.9, 0.7, 0.85, ...]   # used for ordering / early termination

Compression — three independent layers:

• Document IDs — delta encoding (store the delta between consecutive sorted doc IDs, not the absolute value).
  • Original: [100, 105, 112, 150] → deltas [100, 5, 7, 38]. Smaller integers compress dramatically better with variable-byte / Elias-Fano encoding.
• Positions — delta encoded inside each document’s position list.
• Frequencies — variable-byte encoded.

Index entry (conceptual):

1-- Logical structure (production uses a custom binary format).2term_id:      uint64    -- Hashed term3doc_count:    uint32    -- Number of documents containing the term4posting_list: bytes     -- Compressed posting data5  ├── doc_ids:   varint[]   -- Delta-encoded document IDs6  ├── freqs:     varint[]   -- Term frequencies per doc7  └── positions: bytes      -- Position data for phrase queries

URL frontier schema

1CREATE TABLE url_frontier (2    url_hash         BIGINT PRIMARY KEY,   -- Hash of normalized URL3    url              TEXT NOT NULL,4    domain_hash      BIGINT NOT NULL,      -- For politeness grouping5    priority         FLOAT NOT NULL,       -- Crawl priority (0-1)6    last_crawl_time  TIMESTAMP,7    next_crawl_time  TIMESTAMP NOT NULL,8    crawl_frequency  INTERVAL,9    retry_count      INT DEFAULT 0,10    status           VARCHAR(20) DEFAULT 'pending',1112    -- Partitioned by priority for efficient dequeue.13    INDEX idx_priority (priority DESC, next_crawl_time ASC),14    INDEX idx_domain   (domain_hash, next_crawl_time ASC)15);

Politeness: at most one outstanding request per host (often per IP) at a time, with a host-specific delay derived from Crawl-delay (deprecated but still observed by many engines), adaptive backoff, and HTTP 429 / 503 signals. The domain_hash index makes per-host rate-limiting an indexed scan, not a full-table operation.

Storage selection matrix

Indexing — Caffeine and Percolator

Until 2010 Google’s index was rebuilt by a multi-stage pipeline of roughly 100 MapReduces. Adding a single newly crawled page meant waiting for the next pipeline tick, because reprocessing time scaled with the size of the entire repository, not with the size of the update. Caffeine, deployed in 2010, replaced the batch path with Percolator — a system of cross-row ACID transactions on Bigtable plus observers that fire when watched columns change⁷. The headline numbers from the OSDI 2010 paper: average document age in search results dropped by 50%, and per-document processing latency improved by ~100×⁷.

The mental model:

• Bigtable holds the canonical document (the webtable row).
• A new write triggers Percolator observers — application-defined functions registered against specific columns.
• Each observer runs inside a Percolator snapshot-isolation transaction that may touch many rows across many tablets.
• Cascading observer chains converge once nothing further fires; the row is then “indexed” and visible to serving.

This buys two properties classical batch indexing cannot:

• Cost is proportional to the update size, not the corpus size. Crawling a few million new pages an hour costs a few million updates, not a 100-PB rescan.
• A single page can be added without rebuilding adjacent state. The link graph, the duplicate cluster, and the affected posting lists are updated in lockstep.

Trade-offs Google was explicit about⁷:

• Percolator is roughly 30× more expensive per-byte than the equivalent MapReduce — the right tool for many small updates, the wrong tool when you actually need to reprocess > ~40 % of the corpus.
• The system depends on Bigtable’s per-row + cross-row transaction primitives. You cannot bolt this on top of an arbitrary KV store.

In an interview answer, the right framing is: Caffeine is what made “incremental” plausible at this scale; the inverted index is still the data structure, but it’s now mutated row-by-row instead of rebuilt batch-by-batch. The MapReduce path still exists for full reprocessing (e.g. a global signal change), but it is the exception, not the steady state.

A schematic of the batched / initial-build path is still useful as a mental anchor:

A conceptual MapReduce sketch — useful for showing the per-shard write path:

Show 10 hidden lines11  positions: number[]12}1314function mapDocument(doc: Document): Map<string, Posting> {15  const terms = new Map<string, Posting>()16  const tokens = tokenize(doc.content)1718  for (let pos = 0; pos < tokens.length; pos++) {19    const term = normalize(tokens[pos])2021    if (!terms.has(term)) {22      terms.set(term, {23        doc_id: hashDocId(doc.doc_id),24        frequency: 0,25        positions: [],26      })27    }2829    const posting = terms.get(term)!30    posting.frequency++31    posting.positions.push(pos)32  }3334  return terms35}3637function reducePostings(term: string, postings: Posting[]): PostingList {38  postings.sort((a, b) => b.quality_score - a.quality_score)3940  return {41    term,42    doc_count: postings.length,43    postings: deltaEncode(postings),44  }45}4647function deltaEncode(postings: Posting[]): Buffer {48  const buffer = new CompressedBuffer()49  let prevDocId = 05051  for (const posting of postings) {52    buffer.writeVarint(posting.doc_id - prevDocId)53    buffer.writeVarint(posting.frequency)54    buffer.writePositions(posting.positions)Show 5 hidden lines

Google runs all three in parallel: the main index is updated incrementally, a separate fresh-tier index handles real-time content, and the batch path stays available for occasional reprocessing.

Index sharding — document vs term

The “fan out to all shards” decision is a direct consequence of choosing document partitioning over term partitioning.

Web-scale engines, including Google, choose document partitioning despite the broadcast cost — the load and failure properties are dramatically better, and the broadcast cost is amortised by per-shard top-K and aggressive aggregation. Manning, Raghavan & Schütze’s Introduction to Information Retrieval spells out the same conclusion: “Most large search engines prefer the document-partitioned index”⁸.

Low-level design

Query processing pipeline

Spell correction

Google’s production spell corrector is a deep neural network with more than 680 million parameters that runs in under two milliseconds per query, described by Pandu Nayak in the ABCs of spelling in Google Search blog post⁹. It is trained on aggregate query logs — when millions of users follow javasript with javascript, the model learns the correction. This is also why spell correction works less well on rare technical terms (no signal) and in low-resource languages (smaller log volume).

Show 8 hidden lines9  if (await isKnownPhrase(query)) {10    return { original: query, corrected: query, confidence: 1.0, alternatives: [] }11  }1213  const modelOutput = await spellModel.predict(query)14  const contextualCorrection = applyContextRules(query, modelOutput)15  const popularMatch = await findPopularMatch(contextualCorrection)1617  return {18    original: query,19    corrected: popularMatch || contextualCorrection,20    confidence: modelOutput.confidence,21    alternatives: modelOutput.alternatives.slice(0, 3),22  }23}

Ranking system architecture

Google’s ranking is a layered ensemble — official documentation calls out “many factors and signals”²; community lists put the figure in the hundreds. The architectural shape is the important part:

PageRank

PageRank measures page authority from the link graph as the stationary distribution of a random web surfer following links with damping factor d (the original paper used d = 0.85)¹⁰:

Show 12 hidden lines1314  let ranks = new Map<string, number>()15  for (const page of graph.pages.keys()) {16    ranks.set(page, initialRank)17  }1819  for (let iter = 0; iter < MAX_ITERATIONS; iter++) {20    const newRanks = new Map<string, number>()21    let maxDelta = 02223    for (const page of graph.pages.keys()) {24      let inlinkSum = 025      const inlinks = graph.inlinks.get(page) || []2627      for (const inlink of inlinks) {28        const inlinkRank = ranks.get(inlink) || 029        const outlinks = graph.pages.get(inlink) || []30        if (outlinks.length > 0) {31          inlinkSum += inlinkRank / outlinks.length32        }33      }3435      const newRank = (1 - DAMPING_FACTOR) / numPages + DAMPING_FACTOR * inlinkSum36      newRanks.set(page, newRank)3738      maxDelta = Math.max(maxDelta, Math.abs(newRank - (ranks.get(page) || 0)))39    }4041    ranks = newRanks4243    if (maxDelta < CONVERGENCE_THRESHOLD) {44      break45    }46  }4748  return ranks49}

PageRank at scale:

• Web graph: hundreds of billions of nodes, trillions of edges.
• Computation: distributed iteration across thousands of machines (originally MapReduce; now incremental updates via Caffeine for affected subgraphs).
• Frequency: refreshed continuously rather than on a fixed monthly cadence.
• Storage: PageRank scores live in the quality:pagerank column of the webtable.

BERT

BERT (Bidirectional Encoder Representations from Transformers) was launched in Google Search on 25 October 2019 and initially affected ~1 in 10 English US queries; it later rolled out to 70+ languages¹¹. The point of BERT for search is understanding the role of small words (“for”, “to”, “without”) that change query intent:

1Query:  "can you get medicine for someone pharmacy"2Pre-BERT: matches pages about "medicine" and "pharmacy" independently3Post-BERT: understands intent as "picking up a prescription for another person"

RankBrain and MUM

RankBrain, launched in 2015, was Google’s first ML system in ranking — it embeds queries and candidate documents into a shared vector space and uses cosine similarity as one of many ranking signals.

1Query vector: [0.23, -0.45, 0.12, ...]   (hundreds of dimensions)2Doc vector:   [0.21, -0.42, 0.15, ...]3Similarity:   cosine_similarity(query_vec, doc_vec) ≈ 0.94

MUM (Multitask Unified Model), announced May 2021, is the multimodal, multilingual successor — trained across 75 languages and on text + images simultaneously, framed as “1000× more powerful than BERT” by Google¹². MUM rolls out behind specific features (e.g. expanded coverage on COVID vaccine names, certain visual / language tasks) rather than as a single switchover.

The architectural rule: cheap signals (BM25, PageRank, freshness) retrieve a candidate set per shard, expensive learned models (BERT/MUM/RankBrain) re-rank the survivors. Putting BERT in the retrieval path would blow the latency budget; putting BM25 in the re-ranking path would waste compute.

Two-stage retrieval and re-ranking

Modern web-scale ranking is phased, not monolithic. Vespa documents the same pattern under the name phased ranking: a first-phase cheap function over all retrieved hits, a second-phase over local top-K on each content node, and a global-phase cross-encoder on the merged top-K at the stateless container¹³. Google’s serving stack follows the same shape, scaled to thousands of shards.

The cost ratio between stages is what makes this work — a BM25 disjunction over a posting list pruned by WAND costs microseconds per document; a BERT cross-encoder costs milliseconds. With ~10^3 candidates per shard reduced to the top ~10^3 globally, the cross-encoder budget is bounded regardless of corpus size.

Neural matching and hybrid retrieval

Cheap retrieval no longer means only lexical. Google’s official How AI powers great search results page describes neural matching (deployed in 2018) as a retrieval-side system that “looks at an entire query or page rather than just keywords” and is explicitly distinct from RankBrain’s ranking-side role¹⁴. Search Engine Journal’s reporting of Google’s own clarifications puts it bluntly: “Neural matching helps us understand how queries relate to pages … RankBrain helps us rank”¹⁵. In production-engine terms this is hybrid retrieval — a sparse inverted index in parallel with a dense ANN index over learned embeddings, fused before re-ranking.

Practical notes:

• The dense path uses a bi-encoder (query and document encoded independently, scored by cosine / dot product) so embeddings can be precomputed and served from an ANN index. Cross-encoders are reserved for the re-rank stage where they only see ~10^3 candidates per query.
• ANN structures in production are typically HNSW (graph-based, high recall, RAM-resident) or IVF-PQ (inverted file with product quantisation, cheaper RAM at the cost of recall). Vespa, Elasticsearch, OpenSearch and Vespa-class engines all expose both.
• Fusion is most often Reciprocal Rank Fusion (score = Σ 1 / (k + rank_i) across the two lists, k ≈ 60) or a learned linear combination — both cheap, both recoverable from per-engine ranks alone.
• Hybrid retrieval is also the retrieval substrate of modern retrieval-augmented generation (RAG): the same sparse + dense + rerank pipeline feeds the context window of an LLM instead of an SERP renderer.

Distributed query execution

Querying a sharded index requires fan-out to all shards, parallel execution, and result aggregation under a strict deadline. With document partitioning the broadcast cost is unavoidable; the engineering work is in bounding the tail — every replica is a candidate, the slowest one would otherwise win.

Show 15 hidden lines1617  const shardPromises = shards.map((shard) =>18    queryShard(shard, query, top_k_per_shard).catch((err) => ({19      shard_id: shard.id,20      results: [],21      latency_ms: timeout_ms,22      error: err,23    })),24  )2526  const shardResults = await Promise.race([Promise.all(shardPromises), sleep(timeout_ms).then(() => "timeout")])2728  if (shardResults === "timeout") {29    return aggregatePartialResults(shardPromises)30  }3132  return mergeAndRank(shardResults as ShardResult[], query)33}3435function mergeAndRank(shardResults: ShardResult[], query: ParsedQuery): SearchResult[] {36  const candidates: ScoredDocument[] = []37  for (const result of shardResults) {38    candidates.push(...result.results)39  }4041  candidates.sort((a, b) => b.score - a.score)4243  const reranked = applyFinalRanking(candidates.slice(0, 1000), query)4445  return reranked.slice(0, query.num_results)46}4748async function queryShard(shard: ShardConnection, query: ParsedQuery, topK: number): Promise<ShardResult> {49  const start = Date.now()5051  const postingLists = await shard.getPostingLists(query.terms)5253  const candidates = intersectPostingLists(postingLists)5455  const scored = candidates.map((doc) => ({56    doc,57    score: computeLocalScore(doc, query),58  }))5960  scored.sort((a, b) => b.score - a.score)6162  return {63    shard_id: shard.id,64    results: scored.slice(0, topK),65    latency_ms: Date.now() - start,66  }67}

Tail latency

The fundamental observation from Dean & Barroso, The Tail at Scale (CACM 2013): a service that fans out to N replicas is at the mercy of the slowest one, and at N = 1000 even a 99th-percentile shard latency dominates the median user-visible latency¹⁶. The paper documents the techniques the serving layer relies on:

The cost is bounded — hedged requests typically add a small percentage of extra load in exchange for an order-of-magnitude tail-latency improvement¹⁶. They are safe for read-only or idempotent operations and explicitly inappropriate for non-idempotent writes.

Crawl scheduling and politeness

Show 12 hidden lines13  maxConcurrent: number14}1516class CrawlScheduler {17  private domainStates: Map<string, DomainState> = new Map()18  private frontier: PriorityQueue<CrawlJob>1920  async scheduleNext(): Promise<CrawlJob | null> {21    while (!this.frontier.isEmpty()) {22      const job = this.frontier.peek()2324      const domainState = this.getDomainState(job.domain)2526      if (!this.canCrawlNow(domainState)) {27        this.frontier.pop()28        this.frontier.push(job)29        continue30      }3132      if (domainState.concurrentRequests >= domainState.maxConcurrent) {33        continue34      }3536      domainState.concurrentRequests++37      domainState.lastRequestTime = new Date()3839      return this.frontier.pop()40    }4142    return null43  }4445  private canCrawlNow(state: DomainState): boolean {46    const elapsed = Date.now() - state.lastRequestTime.getTime()47    return elapsed >= state.crawlDelay * 100048  }4950  updateCrawlDelay(domain: string, responseTimeMs: number, statusCode: number): void {51    const state = this.getDomainState(domain)5253    if (statusCode === 429 || statusCode === 503) {54      state.crawlDelay = Math.min(state.crawlDelay * 2, 60)55    } else if (responseTimeMs > 2000) {56      state.crawlDelay = Math.min(state.crawlDelay * 1.5, 30)57    } else if (responseTimeMs < 200 && state.crawlDelay > 1) {58      state.crawlDelay = Math.max(state.crawlDelay * 0.9, 1)59    }Show 2 hidden lines

The robots.txt protocol itself — long a de facto standard — was published as RFC 9309 in September 2022; it formalises the parsing rules that crawlers had been implementing inconsistently for two decades.

Crawl prioritisation factors:

Near-duplicate detection (SimHash)

Crawled pages overlap heavily — mirrors, syndication, parameter-stuffed URLs, boilerplate. The standard tool is SimHash, originally Charikar’s locality-sensitive hash, applied to web crawling at Google by Manku, Jain & Das Sarma (WWW 2007)⁵:

• Each document is reduced to a 64-bit fingerprint that is similar (small Hamming distance) when the documents are similar.
• For a corpus of 8 billion pages, a Hamming distance of k ≤ 3 was found sufficient to identify near-duplicates with high precision⁵.
• The system is online: the crawler computes a fingerprint, looks for any existing fingerprint within Hamming distance k, and if found discards the page (and often its outlinks).

Without this step the crawl wastes bandwidth and the index wastes storage on near-identical content.

Frontend

Search results page (SERP)

The SERP must render fast despite complex content (rich snippets, knowledge panels, images).

Show 10 hidden lines11  const initialResults = data.results.slice(0, 3).map(renderResult).join("")1213  const deferredContent = `14    <script>15      window.__SERP_DATA__ = ${JSON.stringify(data)};16    </script>17  `1819  return `20    <html>21    <head>22      <style>${criticalCSS}</style>23    </head>24    <body>25      <div id="results">${initialResults}</div>26      <div id="deferred"></div>27      ${deferredContent}28      <script src="/serp.js" defer></script>29    </body>30    </html>31  `32}

Autocomplete

Show 8 hidden lines9    }1011    const cached = this.cache.get(query)12    if (cached) {13      return cached14    }1516    await this.debounce()1718    const suggestions = await this.fetchSuggestions(query)1920    this.cache.set(query, suggestions)2122    this.prefetchNextCharacter(query)2324    return suggestions25  }2627  private prefetchNextCharacter(query: string): void {28    const commonNextChars = ["a", "e", "i", "o", "s", "t", " "]29    for (const char of commonNextChars) {30      const nextQuery = query + char31      if (!this.cache.has(nextQuery)) {32        requestIdleCallback(() => this.fetchSuggestions(nextQuery))33      }34    }35  }36}

A workable per-keystroke latency budget:

1Total: 100 ms target2├── Network RTT:           30 ms (edge servers)3├── Server processing:     20 ms4├── Trie lookup:            5 ms5├── Ranking:               10 ms6├── Response serialization: 5 ms7└── Client rendering:      30 ms

Pagination vs. infinite scroll

Google sticks with pagination on web SERPs:

Infrastructure

Cloud-agnostic components

Google’s internal infrastructure

AWS reference architecture

A workable reference design when you do not own a Bigtable / Colossus / Borg / Percolator stack — you swap each component for the closest commodity equivalent:

Sizing for ~10 K QPS over ~1 B documents (illustrative, not optimised):

Self-hosted open-source stack

Variations

News search (freshness-critical)

News ranking demotes baseline relevance and authority in favour of freshness.

1function computeNewsScore(doc: NewsDocument, query: Query): number {2  const baseRelevance = computeTextRelevance(doc, query)3  const authorityScore = doc.sourceAuthority4  const freshnessScore = computeFreshnessDecay(doc.publishedAt)56  return baseRelevance * 0.3 + authorityScore * 0.2 + freshnessScore * 0.57}89function computeFreshnessDecay(publishedAt: Date): number {10  const ageHours = (Date.now() - publishedAt.getTime()) / (1000 * 60 * 60)11  return Math.exp(-ageHours / 8)12}

News-specific infrastructure:

• Dedicated fresh-tier index updated in (near) real time.
• RSS / Atom feed crawling on the order of minutes.
• Publisher push APIs for instant indexing.
• Separate ranking model trained on news engagement.

Image search

Image ranking blends visual features with text signals.

1interface ImageDocument {2  imageUrl: string3  pageUrl: string4  altText: string5  surroundingText: string6  visualFeatures: number[]7  safeSearchScore: number8}910function rankImageResult(image: ImageDocument, query: Query): number {11  const textScore = computeTextRelevance(image.altText + " " + image.surroundingText, query)1213  const visualScore = query.hasImage ? cosineSimilarity(image.visualFeatures, query.imageFeatures) : 01415  const pageScore = getPageRank(image.pageUrl)1617  return textScore * 0.4 + visualScore * 0.3 + pageScore * 0.318}

Local search

Location-aware search needs geographic indexing.

1interface LocalBusiness {2  id: string3  name: string4  category: string5  location: { lat: number; lng: number }6  rating: number7  reviewCount: number8}910function rankLocalResult(business: LocalBusiness, query: Query, userLocation: Location): number {11  const relevanceScore = computeTextRelevance(business.name + " " + business.category, query)1213  const distance = haversineDistance(userLocation, business.location)14  const distanceScore = 1 / (1 + distance / 5)1516  const qualityScore = business.rating * Math.log(business.reviewCount + 1)1718  return relevanceScore * 0.3 + distanceScore * 0.4 + qualityScore * 0.319}

Local search infrastructure:

• Geospatial index (R-tree or geohash-based).
• Business database integration (Google My Business / Maps).
• Real-time hours / availability from APIs.
• User location from GPS, IP, or explicit setting.

Conclusion

Web search at this scale is the conjunction of four hard problems plus the operational discipline to run them as one system:

• Crawling. Discover and fetch content from billions of URLs while honouring per-host politeness (RFC 9309). Prioritisation decides which pages stay fresh; SimHash keeps the corpus from drowning in duplicates⁵.
• Indexing. Posting lists are the data structure; document partitioning is the sharding choice; Caffeine + Percolator is the update path. Cost scales with the size of the update, not the size of the corpus⁷.
• Ranking. PageRank gives baseline authority from the link graph¹⁰; neural matching runs on the retrieval side¹⁴; BERT¹¹ and MUM¹² cover semantic understanding at re-rank; RankBrain provides query-document embedding similarity in ranking. Cheap signals retrieve (often hybrid sparse + dense), expensive cross-encoders re-rank — the same pattern Vespa formalises as first-phase / second-phase / global-phase¹³.
• Serving. 100 K+ QPS with sub-second latency means the tail latency dominates the budget. Hedged and tied requests, partial results, early termination, and replica imbalance compensate for the slowest shard¹⁶.

What this design optimises for:

• Query latency — caching, early termination, hedged fan-out.
• Index freshness — Caffeine for the bulk corpus, a separate fresh tier for QDF queries.
• Result relevance — a stack of complementary ranking systems, no single “the algorithm”.
• Horizontal scale — document-partitioned shards, replicated globally.

What it sacrifices:

• Simplicity — thousands of components, multiple ranking systems, complex coordination.
• Cost — only meaningful at the volumes that justify a million-server fleet.
• Real-time freshness for cold pages — minutes-to-hours for typical content (news handled separately).

Known limitations:

• Long-tail queries with little training signal under-perform.
• Adversarial SEO requires continuous ranking updates.
• New sites take time to surface even after first crawl.
• Personalisation creates filter bubbles.

Appendix

Prerequisites

• Information retrieval fundamentals (TF-IDF, BM25, inverted indexes).
• Distributed systems (sharding, replication, consensus, the tail-at-scale problem).
• Basic ML (embeddings, transformers).
• Graph algorithms (PageRank, link analysis).

Terminology

• Inverted index — Map from term → posting list of documents containing it.
• Posting list — Documents (with positions / frequencies) for a single term.
• Document partitioning — Each shard owns a full inverted index over a slice of documents.
• Term partitioning — Each shard owns posting lists for a slice of terms.
• PageRank — Page importance from the link-graph stationary distribution.
• BERT — Bidirectional transformer for word-context understanding (Search since 2019).
• MUM — Multitask Unified Model; multimodal, multilingual ranking model (announced 2021).
• RankBrain — ML system mapping queries + documents into a shared embedding space (since 2015); operates at the ranking stage.
• Neural matching — Google’s retrieval-side neural system (since 2018) that matches “fuzzier” query–page concept representations; distinct from RankBrain.
• Hybrid retrieval — Sparse (BM25 over inverted index) + dense (ANN over learned embeddings), fused before re-ranking.
• Bi-encoder vs cross-encoder — Bi-encoders score query and document independently (cheap, precomputable, retrieval-stage); cross-encoders score the pair jointly (expensive, re-rank stage).
• HNSW / IVF-PQ — Two dominant ANN index structures used to serve dense retrieval at scale.
• Phased ranking — Vespa’s term for the same architectural pattern: cheap first-phase, mid-cost second-phase, expensive global-phase cross-encoder.
• WAND / MaxScore — Dynamic-pruning algorithms for posting-list traversal; let cheap retrieval skip documents that cannot enter the top-K.
• Caffeine — Google’s incremental indexing system, deployed 2010, built on Percolator.
• Percolator — Cross-row ACID transactions on Bigtable + observer-driven cascading updates.
• SimHash — 64-bit locality-sensitive fingerprint used for near-duplicate detection.
• Crawl budget — Maximum pages a crawler will fetch from a host per time window.
• robots.txt — Per-host file specifying crawler access rules; standardised as RFC 9309 in 2022.
• QDF — Query Deserves Freshness; freshness-weighting flag for time-sensitive queries.
• SERP — Search Engine Results Page.
• Canonical URL — Preferred URL when many URLs share content.

Summary

• Google handles 5+ trillion searches/year (~14 B/day) over hundreds of billions of indexed pages³¹.
• The inverted index is document-partitioned across thousands of shards; each query fans out to all of them, intersected by Hamming-distance-bounded SimHash near-dup before storage⁵.
• Caffeine + Percolator replaced batch MapReduce indexing with cross-row transactional incremental updates on Bigtable⁷.
• Ranking is a stack — cheap retrieval signals (BM25, PageRank¹⁰) plus expensive re-rankers (BERT¹¹, MUM¹², RankBrain).
• Tail latency is the binding budget: hedged requests, tied requests, partial results, early termination¹⁶.
• Spell correction is a 680-million-parameter DNN running in under 2 ms, trained on aggregate query logs⁹.

References

• The Anatomy of a Large-Scale Hypertextual Web Search Engine — Brin & Page (1998), the original Google paper.
• The PageRank Citation Ranking — Page, Brin, Motwani, Winograd (Stanford TR 1999-66).
• Bigtable: A Distributed Storage System for Structured Data — Chang et al., OSDI 2006.
• Large-scale Incremental Processing Using Distributed Transactions and Notifications — Peng & Dabek, OSDI 2010 (the Percolator paper, foundation of Caffeine).
• The Tail at Scale — Dean & Barroso, CACM 2013.
• Detecting Near-Duplicates for Web Crawling — Manku, Jain & Das Sarma, WWW 2007.
• BERT: Pre-training of Deep Bidirectional Transformers — Devlin et al.
• Web Search for a Planet — The Google Cluster Architecture — Barroso, Dean, Hölzle, IEEE Micro 2003.
• How Search Works — Google official documentation.
• Google Search Ranking Systems Guide — Search Central, official ranking system documentation.
• The ABCs of spelling in Google Search — Pandu Nayak, March 2021.
• Understanding searches better than ever before — Pandu Nayak, October 2019 (BERT in Search).
• MUM: A new AI milestone for understanding information — Prabhakar Raghavan, May 2021.
• A peek behind Colossus, Google’s file system — Hildebrand & Serenyi, April 2021.
• How Colossus optimizes data placement for performance — Google Cloud Blog, March 2025.
• RFC 9309 — Robots Exclusion Protocol — IETF, September 2022.
• Distributed indexing — Introduction to Information Retrieval — Manning, Raghavan, Schütze.
• How AI powers great search results — Pandu Nayak, March 2022; introduces neural matching as the retrieval-side counterpart to RankBrain.
• Phased ranking — Vespa documentation — first-phase / second-phase / global-phase, the production-engine analog of two-stage Google ranking.
• Efficient query evaluation using a two-level retrieval process (WAND) — Broder, Carmel, Herscovici, Soffer, Zien (CIKM 2003).
• Reciprocal rank fusion outperforms Condorcet and individual rank learning methods — Cormack, Clarke, Büttcher (SIGIR 2009).
• Approximate Nearest Neighbor Search on High Dimensional Data — HNSW — Malkov & Yashunin, 2016.