Design a search engine like Google

A web search engine turns two or three words into ten links, in a fraction of a second, out of tens of billions of pages. Someone on a crowded platform types “train running status 12951”; a fan types “ipl score” in the last over of a final; a student types “aaj ka mausam”, or the same words in Devanagari. Three hard problems hide behind that box: an index far too big for one machine, which must be compressed and split across a thousand; a query path that touches every piece and still finishes in under 300 ms at the 99th percentile; and a ranking function that blends word matching, link authority and hundreds of learned signals. Here you design the indexing pipeline, ranking and query serving of a Google-like engine. Crawling is an input with its own design: design a web crawler.

Understand the problem

Scope it in the first minute. Web search is three loops running at very different speeds: crawling in hours to weeks, indexing in minutes to days, serving in milliseconds. Here you design indexing, ranking and serving; the crawler is a black box that hands you pages. Make the scale concrete early: 10 million documents fit in one Elasticsearch cluster, while 20 billion need a different design.

Functional requirements

1. The system should turn crawled pages into a searchable index. It parses each page, picks one canonical copy among duplicates, and makes the page findable by any word in its title, body, URL, or the anchor text of links pointing at it.
2. Users should be able to search with a few words and get the ten best pages, each with a title, URL and snippet, and page through more. Queries arrive in many languages and scripts — English, Hindi in Devanagari, Hinglish in Latin letters — often with typos.
3. Results should be ranked by relevance and quality, not by keyword count: a page that respected sites link to should beat a keyword-stuffed copy of it.
4. The index should stay fresh. A news story or an updated score page should be searchable within minutes of being crawled; the rest of the web within days.

Non-functional requirements

• Corpus. 20 billion unique pages, chosen from about 100 billion URLs the crawler knows. Google’s own index covers hundreds of billions of pages and well over 100,000,000 GB; ours is smaller but the same shape.
• Query load. 4 billion queries a day: about 46,000 a second on average and 100,000 at peak — board-exam results mornings, the last over of a cricket final.
• Latency. Server-side p50 under 100 ms and p99 under 300 ms; cached results under 20 ms. In search, speed is part of quality: good results fast beat the best results slowly.
• Freshness. Breaking pages searchable about 5 minutes after the crawl; any recrawled page within a day.
• Ingest. About 1 billion fetches a day from the crawler, roughly 11,600 pages a second.
• Availability. 99.99%. Losing a machine, a shard or a region may cost capacity or a sliver of recall — never the service.
• Cost. Every query touches a thousand machines, so CPU per query is the main bill.

Out of scope

• Crawling: frontier, politeness, fetch dedup — see design a web crawler.
• Ads, and the image, video, news and maps verticals.
• Answer boxes and the knowledge graph. A live scorecard or a train’s current position comes from a structured feed, not from ranking web pages.
• Suggestions while typing — see design typeahead.
• Deep personalisation beyond language and location.

The set-up

Plan the approach

Start with the index, because its size drives everything: the index size sets the shard count, and the shard count sets every query’s fan-out. Then satisfy each requirement with the simplest design, and spend most of the time in the deep dives: index format, sharding, tail latency, ranking, freshness, caching and messy queries.

Core entities

• Document. A canonical page: docID (local to its shard, assigned in order of static quality), canonical URL, content hash, language, title, length, static scores such as PageRank and spam likelihood, and the duplicate URLs it stands for.
• Term. A normalised token — ipl, 12951, mausam, मौसम — with its document frequency. The lexicon maps each term to its posting list.
• Posting. One entry in a term’s list: docID, term frequency, positions, and flags for where the term appeared (title, URL, anchor text) — the 1998 Google paper’s “fancy hits”.
• Link. Source, target and anchor text. Inverted, it becomes extra text for the target and an edge for PageRank.
• Query. Raw text plus what query understanding derives: language, script, spelling fix, transliterated variants and intent (fresh, local, navigational).
• Result. DocID, score, URL, title and snippet.

API

Search. One read endpoint; hl is the interface language, gl the country.

GET /v1/search?q=train+runing+status+12951&hl=en-IN&gl=IN&start=0&num=10

{
  "query": {
    "original": "train runing status 12951",
    "corrected": "train running status 12951",
    "language": "en",
    "intent": ["fresh"]
  },
  "results": [
    {
      "rank": 1,
      "url": "https://enquiry.example.in/trains/12951/live-status",
      "title": "12951 Mumbai Rajdhani: live running status",
      "snippet": "…train 12951 is running 8 min late, last reported at Kota Jn…",
      "result_token": "r_1a7c"
    }
  ],
  "next_start": 10,
  "partial": false,
  "search_id": "s_9f2c41"
}

partial: true means some shards missed the deadline and the page was built from the rest. Deep paging is capped (say, at 300 results), because every extra page multiplies the candidates each shard must return.

Click events, sent asynchronously; they become ranking training data.

POST /v1/events/click
Content-Type: application/json

{ "search_id": "s_9f2c41", "result_token": "r_1a7c", "rank": 1, "dwell_ms": 41000 }

Leaf search, the internal call to one replica of every shard (gRPC in production):

{
  "shard": 417,
  "terms": [["train"], ["running"], ["status"], ["12951"]],
  "k": 10,
  "phase1_k": 200,
  "deadline_ms": 120,
  "model": "ltr-v83"
}

It returns up to k candidates with docID, score and a compact feature vector, plus the fraction of the shard searched.

Ingest. The indexer consumes the crawler’s pages.fetched events: URL, a pointer into compressed page files in blob storage, fetch time, content hash and status.

Back-of-envelope estimates

These numbers decide the shard count, the replica count and the fleet. (Method: back-of-envelope estimation.)

Queries. 4,000,000,000 ÷ 86,400 s ≈ 46,000/s on average; peaks run about 2×, so plan for 100,000/s.

After the cache. Google’s cache servers saw hit rates of 30–60%. At 40%: 100,000 × 0.6 = 60,000 queries/s reach the index.

Text. A web page has under 1,000 terms on average; with title and anchors, call it 1,000 tokens of about 6 bytes. 20B × 6 KB = 120 TB of text.

Postings. About 400 distinct terms per page: 20B × 400 = 8 trillion postings, and 20B × 1,000 = 20 trillion positions.

Index size. Raw: 8T × 8 B (4-byte docID, 4-byte count) + 20T × 4 B = 64 TB + 80 TB = 144 TB. Compressed at about 1.5 bytes per posting and per position: 12 TB + 30 TB = ≈ 42 TB — 3.4× smaller, and 35% of the text, inside the textbook rule that a compressed positional index is a third to a half of the text. Positions are 30 of the 42 TB.

Ranking data. About 500 bytes of features per page: 20B × 500 B = 10 TB.

Shards. Keep everything in RAM. With 1,000 shards of 20M pages: 42 GB of postings + 10 GB of features ≈ 52 GB, about 60 GB with lexicon and fresh segments — comfortable on a 128 GB server.

CPU. Assume 3 ms of CPU per shard per query. One query costs 1,000 × 3 ms = 3 CPU-seconds, about 9 billion cycles at 3 GHz — the same order as the tens of billions of cycles per query that Google reported in 2003. At peak: 60,000 × 3 = 180,000 cores busy.

Replicas. A 48-core leaf at ≤ 50% CPU does 24 ÷ 0.003 = 8,000 shard-queries/s, so 60,000 ÷ 8,000 = 7.5 copies of every shard must serve. Three regions must survive losing one, so two regions carry the peak: 7.5 ÷ 2 = 3.75 → 4 replicas per region, 12 per shard, 12,000 leaves. Normal load is 60,000 ÷ 12 = 5,000/s per leaf (31% CPU); with a region down, 7,500/s (47%).

Fan-out. 60,000 × 1,000 = 60M leaf calls/s. A leaf replies with 10 candidates × 100 B = 1 KB; parents keep 40, so the root receives 25 × 40 × 100 B = 100 KB per query.

Snippets. Text compressed about 3:1, as the 1998 paper measured with zlib: 120 TB ÷ 3 = 40 TB per copy, and up to 60,000 × 10 = 600,000 snippet fetches/s.

Updates. 1B fetches a day ≈ 11,600/s; if 30% changed, ≈ 3,500 updates/s, just 3.5 per shard per second.

Link graph. About 50 links per page: 20B × 50 = 1 trillion edges, ≈ 10 TB as pairs of 5-byte IDs.

High-level design

Build the engine one requirement at a time. By the end it answers correctly over the whole web, with fresh results — just not yet fast or cheap enough.

The system should turn crawled pages into a searchable index

The indexer reads the crawler’s pages.fetched events and, for each page:

1. Parses the HTML. A parser that meets the whole web must never crash, only give up on one page — the 1998 Google paper lists typos in tags, kilobytes of zeros inside a tag and tags nested hundreds deep.
2. Picks a canonical copy. The same article lives at many URLs; Google clusters similar pages and indexes the most representative one.
3. Extracts visible text, title, headings, language, and every outgoing link with its anchor text.
4. Tokenizes with script-aware rules: Unicode normalisation, case folding, Devanagari and Latin word splitting, keeping 12951 and IPL-2026 searchable.
5. Writes a forward index entry: this docID contains these terms at these positions.

An inverted index is the forward index turned inside out: sort every (term, docID, positions) record by term, then docID, and each term’s records become its posting list. The 1998 prototype did exactly this with “forward barrels” that a sorter re-sorted by word; today it is a large distributed sort.

Links matter twice. Anchor text is attached to the page a link points to, because anchors often describe a page better than the page itself — the original Google design indexed 259 million anchors for 24 million pages, and could even return pages it had never crawled. And the link graph feeds PageRank, computed offline and stored with each page as a static score.

Each shard keeps a compact lexicon in memory, and a document store keeps compressed text for snippets.

Users should be able to search and get the ten best pages

The simplest query path follows the shape Google described in 2003: a frontend, an index layer that finds and scores documents, and a document layer that turns winning docIDs into titles and snippets.

1. The query reaches a frontend in the nearest region.
2. The frontend normalises it exactly as the indexer normalised documents, or nothing will match.
3. The root sends it to one replica of every shard. Each leaf looks up the terms, walks their posting lists in docID order to find pages containing all of them, scores those and returns its ten best.
4. The root merges 1,000 lists of ten. Shards hold random samples of the web and share global statistics such as each term’s web-wide frequency, so their scores are comparable.
5. Doc servers cut snippets around the query words; spelling suggestions run in parallel.

Intersection is the core operation. Both lists are sorted by docID, so the leaf advances two cursors and never goes back. Start with the rarest term: 12951 matches far fewer pages than running, so it decides which parts of the longer lists are worth reading.

Results should be ranked by relevance and quality

“ipl score” matches hundreds of millions of pages; the user reads ten. Ranking is a funnel: cheap scores on many candidates, expensive scores on few.

The signals fall into four groups:

• Text match: BM25 per field (title, body, URL, anchors) — often called BM25F — plus how close the query words sit. The 1998 ranker already weighted hits by type and binned proximity into ten levels, from phrase match to “not even close”.
• Static quality: PageRank, spam likelihood, page experience — computed offline, a few bytes per page.
• Learned relevance: a model trained on human ratings and aggregated interaction data, combining hundreds of features.
• Context: language, country, device. Google’s example: “bicycle repair shops” should differ between Paris and Hong Kong.

PageRank and model training are offline jobs; each ships an artefact — a column of scores, a model file — that leaves load on their next refresh.

The index should stay fresh

The simplest design that meets the freshness goal has two tiers: a base tier of all 20 billion pages rebuilt weekly, and a small in-memory fresh tier fed one page at a time as pages are crawled. The root queries both and merges.

You now have a complete engine: pages flow in, queries fan out to every shard, a funnel ranks the matches, and fresh pages appear within minutes. The deep dives make each part survive real scale.

Deep dives

How do we build and store the inverted index?

The index must be small enough for RAM, fast enough to decode millions of numbers per query, and buildable from 120 TB of text in hours.

Bad: a (term, docID) table in a general-purpose database. Eight trillion rows under a B-tree. Each row carries tens of bytes of overhead, nothing is compressed, and a common word becomes a scan of hundreds of millions of rows through an engine built for point updates. Between builds web search is read-only, so you pay for transactional machinery you never use.

Good: sorted posting lists from a distributed sort. The indexer emits (term, docID, frequency, positions) records; a shuffle groups them by shard and sorts by term, then docID; each shard’s builder writes every term’s postings contiguously, plus a lexicon. DocID order turns multi-term queries into a linear merge. Google’s 1998 prototype sorted its barrels on four machines in about a day; a modern batch cluster does 20 billion pages in hours. The cost is space: 144 TB raw needs 3,000 machines with 48 GB each just for one copy.

Great: compressed, block-structured lists with positions kept apart. Four techniques take 144 TB to about 42 TB without slowing queries:

1. Store gaps, not docIDs. In a sorted list, store the first docID and then the differences, which are small.
2. Use as few bytes as each gap needs. Variable-byte coding puts 7 bits of the number in each byte and uses the eighth to mark the last byte. On the Reuters-RCV1 collection it shrinks a docID-only index from 400 MB as 32-bit integers to 116 MB, about 1.2 bytes per posting.
3. Cut lists into blocks with headers. Each block of 128 postings starts with its last docID and byte offset, so a query can jump to the right block and decode only that one. These are skip pointers.
4. Keep positions in a separate stream. They are 30 of the 42 TB, but only phrase checks and proximity scoring of top candidates need them.

Decode speed matters as much as size. Google’s 2009 numbers: classic varint decoded about 180 million numbers a second, a two-bit-length variant 240 million, and group varint — four numbers sharing one prefix byte of lengths, decoded through a 256-entry table — about 400 million. Bit-packing each block of 128 gaps at the width of its largest gap, with rare outliers stored apart (the idea behind PForDelta-style codes), goes the same way: fixed-width numbers the CPU unpacks many at a time.

Three more choices complete the format:

• Assign docIDs best-first. Give high-PageRank, low-spam pages the smallest docIDs, as Google’s 2009 talk recommends. Lists then hold the best candidates first, which enables early termination.
• Flag field hits. The 1998 prototype stored each hit in 2 bytes and kept a much smaller set of “short barrels” with only title and anchor hits, searched first — the first tiered index.
• Make segments immutable. Leaves memory-map read-only files, replicas copy them byte for byte, and a new build is swapped in by pointing a replica at new files.

How do we shard the index?

42 TB cannot live on one machine, and even one CPU decoding a billion-posting list at 400 million numbers a second needs 2.5 seconds. The index must be split, and the two ways to cut it behave very differently.

Bad: a few huge machines. RAM per box runs out at a few terabytes, and one CPU still decodes each list. Google’s 2003 paper bet the other way: many cheap machines, reliability in software, speed from parallelism.

Tempting but wrong for the web: partition by term (a global index). Shard i–k owns ipl, shard s–t owns score, and a two-word query touches two shards. The costs:

• Network. To intersect, one list must travel. ipl in 10 million pages is about 15 MB; at 60,000 queries a second, nearly a terabyte a second.
• Hot spots. During an IPL final, the shard holding ipl takes a huge share of traffic while others idle.
• Ranking data elsewhere. PageRank and length for each candidate become extra lookups.
• Updates and failures. A new page touches ~400 shards; a dead shard removes a term for every page.

Great: partition by document (a local index) and replicate every shard. Each shard is a complete index of its own 20M pages, assigned by hashing the canonical URL, so each is a random sample of the web. Google’s 2003 paper describes exactly this (each shard holds “a randomly chosen subset of documents”), and Jeff Dean’s 2009 talk concluded that by-document made more sense in their environment.

The cost is the last row: every query works on every shard — at least one disk seek per shard per term, Dean noted, when indexes lived on disk. Two things defuse it. Keep the index in memory: once enough replicas existed that their combined RAM could hold it, Google moved its index into memory in 2001 and saw throughput rise and tail latency fall. Replicate for capacity: 12 copies per shard behind a load balancer that routes around dead replicas. A lost replica costs capacity in proportion; losing every replica of a shard in one region costs 0.1% of recall until the root borrows that shard from another region, a few tens of milliseconds away.

Shard count is a dial: smaller shards cut per-leaf latency but raise fan-out overhead and the odds of a slow leaf. Pick shard size from the memory budget and let the count follow. Two refinements from Google help:

• Micro-partitions. Make about 20 partitions per machine and move partitions to rebalance, shifting load in roughly 5% steps.
• Selective replication. Give popular and important pages extra copies in several partitions, so likely top-ten pages are never missing. Google’s web search did this, at times biasing partitions by language and adjusting their replication as the query language mix shifted through the day.

How do we answer a query in a few hundred milliseconds?

Start from the budget. Most of the 300 ms belongs to the index tier:

Notice “slowest”. A query is only as fast as the last of its thousand answers. Google measured this in a real fan-out service: one random leaf finished within 10 ms at the 99th percentile, but all leaves took 140 ms — and the last 5% of leaves accounted for half of that.

Bad: the root calls every leaf, each leaf scores every match, and the root waits for all. The root juggles 1,000 RPCs and 10,000 candidates per query. A leaf that fully scores 200,000 matches for “ipl score” with an expensive model blows its budget. And the tail compounds: if 1 leaf call in 1,000 is slow — a garbage-collection pause, a noisy neighbour — then 1 − 0.999¹⁰⁰⁰ ≈ 63% of queries are slow.

Good: a tree, top-k at every level, pruning in each leaf, and deadlines.

• A serving tree. Google’s 2004 design had root, parent and leaf servers. Here the root talks to 25 parents and each parent to 40 leaves; leaves return 10, parents keep 40, the root merges 1,000.
• Pruning. The leaf walks lists document by document, keeping a heap of the best 200. Each list stores the highest score any of its postings can add, so the leaf skips stretches whose best possible total cannot beat the current 200th — the idea behind WAND and MaxScore. Most matches are never scored.
• Early termination. With docIDs assigned best-first, a leaf can stop once it has enough good matches and the remaining static scores cannot catch up. The 1998 prototype stopped after 40,000 matches and searched title-and-anchor barrels first.
• Deadlines that travel. The root sets 250 ms, leaves get 120 ms, and a leaf out of time returns what it has, marked incomplete.

Great: make the tail tolerant, not just short. Slowness usually comes from interference, not the query, so route around it.

• Hedged requests. If a leaf has not answered by the 95th-percentile latency (about 15 ms), send the request to another replica and take the first answer; waiting for the p95 caps extra load near 5%. In Google’s benchmark, reading 1,000 keys from 100 servers, hedging after 10 ms cut the 99.9th-percentile latency from 1,800 ms to 74 ms with 2% more requests. In our numbers, if slow calls are independent, both copies are slow one time in a million, so slow queries fall from 63% to about 0.1%.
• Good-enough results. If 99% of shards have answered at the deadline, return. The chance that one particular shard holds the best result is about 1 in 1,000, and selective replication lowers it further. Set partial: true, skip caching, and alert if the rate climbs.
• Probation. Parents stop sending to a persistently slow replica, keep sending it shadow requests, and readmit it when it recovers.
• Canary requests. A query that crashes one leaf crashes all thousand — Dean called them “queries of death”. For unusual queries, try one or two leaves first.

And keep leaf work small with two-phase ranking: phase 1 scores with BM25F, proximity and PageRank and keeps 200; phase 2 runs the learned model on those 200. At roughly 5 µs per page for a tree ensemble, that is about 1 ms per leaf.

How do we rank results?

Build ranking in three layers and keep all three, because each later layer uses the earlier ones as features.

Bad: text relevance alone. Score pages by how often they use the query words, weighted by rarity. BM25 is the standard form:

score(q, d) = Σ over query terms t:  idf(t) × tf(t, d) × (k1 + 1)
                                     ─────────────────────────────────────────
                                     tf(t, d) + k1 × (1 − b + b × len(d) / avglen)

idf(t) = ln(N / df(t))     N = pages in the index, df(t) = pages containing t

Two properties beat raw counts. Rarity: with N = 20 billion, ipl in 10 million pages gets idf = ln(2,000) ≈ 7.6, while score in 400 million gets ln(50) ≈ 3.9. Saturation: with k1 = 1.2 (the Lucene and Elasticsearch default, with b = 0.75), the term-frequency factor is 1.0 for one occurrence, 1.57 for three, 1.96 for ten and never above 2.2, so stuffing a word fifty times buys little; b discounts long pages. What BM25 cannot see is quality. Brin and Page complained that the classic vector-space model “often returns very short documents that are the query plus a few words”, and anyone can publish pages built to match queries.

Good: add the link graph — anchor text and PageRank. Links are votes by other authors, much harder to fake at scale than words on your own page. Anchor text becomes its own BM25 field. PageRank turns the graph into one importance score per page: a random surfer follows a random link on each page and, with probability 1 − d, jumps to a random page instead; PageRank is the long-run share of time spent on each page. Brin and Page usually set d = 0.85.

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

(The 1998 paper writes the first term as 1 − d, which makes the scores sum to N; dividing by N makes them a probability distribution.) Compute it by power iteration: start every page at 1/N and reapply the formula. Each round shrinks the error by about a factor of d, so 50 rounds leave 0.85⁵⁰ ≈ 0.0003 of it.

With a trillion edges, each round streams every edge and sums contributions per target page, partitioned by target. On a thousand machines, each scanning a billion edges per round, 50 rounds take on the order of an hour or two; in 1998, 26 million pages took “a few hours on a medium size workstation”. PageRank is query-independent, so it ships to leaves as a static score and is combined with the text score — the 1998 ranker combined its hit-type and proximity score with PageRank in just this way.

You gain authority that is hard to fake by editing your own page. You pay because links can be bought and farmed (see the follow-ups), new pages start with almost no rank, and one global number cannot say that a cricket site is authoritative for “ipl score” but not for “home loan rates”.

Great: learning to rank over hundreds of signals. Google says relevance depends on hundreds of factors, including location, language and device, and that it turns aggregated, anonymised interaction data into signals for machine-learned systems, alongside links from prominent sites as one sign of quality. The pattern:

• Features per (query, page): BM25 per field, proximity and phrase matches, PageRank and site authority, spam and quality scores, freshness for fresh-intent queries, language and country match, mobile-friendliness, and click priors.
• A model — gradient-boosted trees or a small neural network — trained on human ratings plus clicks corrected for position bias (people click higher results regardless of quality).
• Placement: the model runs in leaf phase 2, where every feature of the page is local. The root adds a pass that needs the whole list: at most two results per site, blending fresh results, removing near-duplicates.
• Evaluation: offline on human-rated query sets with graded metrics such as NDCG, then live on a small random slice at production latency — the cycle Dean described in 2009. Google reports hundreds of thousands of experiments a year.

You gain a ranking learned from data instead of hand-tuned weights, which the 1998 paper called “something of a black art”. You pay in CPU per candidate (hence the funnel), a training pipeline that must never leak future clicks into features, and a model nobody fully explains — so keep a debug view of every feature’s contribution, as the 1998 team did.

How do we keep the index fresh?

“ipl score” at 9:40 pm wants pages updated minutes ago; “newton’s laws of motion” is happy with last month’s index. Spend freshness where queries need it.

Bad: rebuild everything, then swap. Run the whole pipeline over the whole corpus and roll the new index out replica by replica. Google did this for years: around 1999 the index changed about once a month, copied onto replicas taken offline at low traffic, and by 2010 the old system’s main layer updated every couple of weeks. It is simple and consistent, but a page waits for the next build and then spends days in the pipeline — 2–3 days per document in Google’s MapReduce-based system, per the Percolator paper. Latency grows with the corpus, not with the change.

Good: tiers by freshness. Keep the base tier on its slow cycle and put small, fast tiers in front — daily and real-time — each indexing only what changed; the root merges and the newest copy wins. Dean’s 2009 talk describes running several retrieval systems this way, one with sub-second updates and one for very many documents updated daily. You pay for several systems with different internals, more work per query, and approximate global signals: a fresh page has no settled PageRank and few known anchors, so you estimate them from its site and the links seen so far.

Great: incremental indexing, with segments on every leaf. Stop thinking in builds.

• Per-document processing with transactions. Google’s Caffeine, built on Percolator, replaced about 100 MapReduces with about 10 observers: code triggered when a column in a Bigtable-like repository changes. A new page triggers duplicate clustering (keeping the highest-PageRank URL as canonical), which triggers link inversion (pushing anchor text to targets, forwarding links to duplicates on to the canonical), which triggers features and an index update. Transactions keep these invariants true while thousands of workers touch overlapping pages.
• Leaves that accept updates. Each shard is an immutable base segment plus small in-memory segments, like an LSM tree. An update, routed by the hash of its canonical URL, lands in the newest segment within seconds and a bitmap hides the old copy; background merges fold segments together. At 3.5 updates per shard per second, this is a trickle.
• Batch jobs, off the critical path. PageRank is recomputed regularly, and base segments are rebuilt weekly to re-sort docIDs by quality and drop deleted pages.

With the same daily crawl, Caffeine moved the median document through indexing over 100 times faster, cut the average age of documents in results by nearly 50%, and held a collection three times larger. The price was about twice the resources for the same crawl rate, plus concurrency complexity — and the paper notes that work which cannot be split into small updates still belongs in batch.

Freshness also depends on what the crawler re-fetches: a score page recrawled every 30 seconds during a match stays fresh; one recrawled weekly cannot.

How do we cache and absorb load?

A small head of queries — “ipl score”, “weather”, “irctc login”, “board result 2026” — repeats millions of times a day, while a long tail is typed once; Google says 15% of the searches it sees each day are new. Dean’s 2009 talk adds a useful fact: queries that hit the cache tend to be popular and expensive, because popular queries use common words with long posting lists.

Bad: no cache. The ten-thousandth “ipl score” of the minute still costs 1,000 leaf calls and 3 CPU-seconds, and you size the fleet for a cricket-final spike made mostly of a few hundred repeated queries.

Good: a result cache in front of the root. Key it by normalised query, language, country, page and device class, and store the finished page with snippets in a distributed cache. Google’s cache servers stored both results and snippets, hit 30–60% of the time depending on index update frequency, query mix and personalisation, and let “10s of machines do work of 100s or 1000s”.

The bars use the same arithmetic as the estimates: replicas per region = ceiling(index queries/s ÷ 8,000 ÷ 2), times 3 regions and 1,000 shards. At 0% hits, ceiling(6.25) = 7 per region gives 21,000 leaves; at 60%, ceiling(2.5) = 3 gives 9,000.

The catch is invalidation. Dean warned of a big latency spike and capacity drop when the index is updated or the cache flushed: leaves that normally see 60% of traffic suddenly see all of it, about 1.7× their usual load.

Great: several caches, each invalidated the way its data changes.

• Freshness-aware TTLs. Fresh-intent queries (“ipl score”, “train running status”, anything trending) live 30–60 seconds; evergreen ones (“pythagoras theorem”) live hours. At 2,000 identical requests a second, a 30-second TTL still means one miss per 60,000 requests.
• Cache the base, query the fresh layer live. Cache top results from base segments, which change weekly, and merge in a live call to the small fresh segments at query time.
• Never flush at once. Stamp entries with the base build version and refresh them early with a probability that rises with age, so a rollout spreads misses over hours.
• Coalesce misses. When a hot entry expires, one request recomputes it while others wait or get the stale copy — see hot keys and cache stampedes.
• Caches lower down. Doc servers cache snippets, and leaves can keep a pair cache of pre-intersected lists for terms often searched together — Dean’s examples were “new” with “york” and “barcelona” with “restaurants”.
• Personalise after the cache. Cache the non-personalised candidates and re-rank per user; personal keys collapse the hit ratio.

How do we understand messy queries?

Users type “irtc train status”, “aaj ka mausam” or “12951 kahan hai” (“where is 12951?”), or the same words in Devanagari. If a query is tokenized differently from the documents, the best page never enters the funnel.

Bad: exact tokens only. “aaj ka mausam” then matches only Latin-script Hinglish pages and misses every Hindi page that says “आज का मौसम”; “irtc” matches nothing useful.

Good: normalise both sides identically, then expand. Use the same Unicode normalisation, case folding and tokenizer at index and query time. Correct spelling from query logs: when many people who type “irtc” retype “irctc”, the model learns the fix. Google lists spelling correction as a basic step of understanding a query, next to a synonym system that matches “change laptop brightness” with pages saying “adjust”. Add transliteration (mausam → मौसम and back), then rewrite into weighted alternatives such as (mausam OR मौसम^0.9) AND aaj. You pay because every variant is another posting list on every shard, so keep two or three variants, weighted below exact matches.

Great: learned query understanding plus semantic retrieval. Train models on query logs to rewrite queries, detect intent (fresh, local, navigational — “irctc login” wants one site) and pick the result language. Add an embeddings index per shard that finds pages close in meaning even when no words match, and merge its candidates into phase 2. Google says one of its language-understanding systems for queries took over five years to build and improves results in over 30% of searches. The cost: model inference on the query path — once per query at the frontend, never per shard — and a vector index beside every inverted one.

The final design

Each region holds a full copy of the serving stack; indexing runs continuously and feeds every region.

Follow one query, then one page:

1. Route and understand. Geo-aware DNS picks the nearest of three regions. The frontend normalises the query, detects language and script, fixes spelling, adds transliterated variants and classifies intent.
2. Check the cache. Normalised query, language, country, page and device class form the key. About 40% of queries end here in a few milliseconds; fresh-intent entries live 30–60 seconds, evergreen ones hours.
3. Fan out. On a miss, the root picks one replica of each of the 1,000 shards and sends the query through 25 parents with a 250 ms deadline (canary leaves first for unusual queries). Parents give leaves 120 ms and hedge calls still pending at the 95th percentile.
4. Retrieve and score. Each leaf searches its base and fresh segments, skipping deleted copies; phase 1 keeps 200 by BM25F, proximity and PageRank, and phase 2 returns the model’s top 10. Parents keep 40; the root merges 1,000, limits results per site, blends fresh results and picks ten — or, if only 99% of shards answered, marks the response partial.
5. Snippets and response. Doc servers cut snippets for the ten pages; the frontend renders, fills the cache unless the answer was partial, and logs impressions for click tracking.
6. Ingest. The crawler publishes one pages.fetched event per stored page, about 11,600 a second.
7. Index incrementally. In transactions on the doc repository, the indexer picks each page’s canonical copy, pushes its anchor text to its targets and computes its features, then sends the update to the page’s shard; replicas add it to a fresh segment within minutes and hide the old copy.
8. Rebuild and retrain offline. From repository snapshots, batch jobs recompute PageRank over the trillion-edge graph and rebuild base segments weekly with docIDs re-sorted by quality, rolled out replica by replica. Click logs and human ratings train ranking models, shipped after offline evaluation and a live experiment.

Check it against the requirements. Latency: about 65 ms typical against a 240 ms p99 budget, protected by deadlines, hedging and good-enough answers. Scale: 42 TB of postings in 1,000 shards of about 60 GB in RAM. Throughput: a 40% cache turns a 100,000/s peak into 60,000/s at the index, which 12,000 leaves serve at 31% CPU. Freshness: minutes for any recrawled page; a week for re-sorting and global recomputation. Availability: a dead replica costs a twelfth of one shard’s capacity, a dead shard 0.1% of recall or a cross-region hop, and a dead region leaves two running at 47% CPU.

What interviewers look for by level

Follow-up questions

What if spammers build link farms to inflate PageRank?

A link farm is thousands of pages that exist only to link to a target. Cap how much rank one site or IP block can pass, so ten thousand pages on one domain count like a handful. Bias the random jump towards hand-vetted trustworthy sites: Brin and Page noted that applying the damping jump to a chosen page or group of pages can make it “nearly impossible to deliberately mislead the system”, because rank then flows from places spammers do not control. Feed link patterns — dense reciprocal links, brand-new domains — into a spam classifier whose score is a ranking feature.

What if a whole region goes down during the IPL final?

Geo DNS moves its users to the other two regions. Leaf capacity was planned for this (47% CPU), but caches were not: the survivors have never seen the failed region’s query mix, so hit ratios dip and leaf load rises until they warm. Drop optional side calls first, and expect the mix to shift — Google saw a data-centre outage send a large share of one language’s queries to another continent, materially changing that site’s workload.

What if the index has to grow to 100 billion pages?

Five times the pages is about 210 TB of postings and five times the CPU per query. Rather than 5,000 shards in RAM, tier by quality: keep the best 20–30 billion pages, which win almost every top ten, in RAM, and serve the long tail from flash-based leaves queried only when the top tier finds too few good matches — the 1998 short and full barrels at a new scale. Dean’s rule applies: design for 10× growth, plan to rewrite before 100×.

What if users expect semantic matches, not just shared words?

Add dense retrieval beside lexical retrieval. Embed each page at indexing time into a per-shard approximate-nearest-neighbour index; embed the query once at the frontend; let each leaf merge top lexical and top semantic candidates into phase 2. Budget for vectors — 20 billion at 256 one-byte dimensions is about 5 TB — and keep lexical matching for exact tokens such as “12951”.

What if results must be personalised?

Personalise late. Retrieval and phase 1 stay identical for everyone, so the cache keeps serving non-personalised candidates, and a final root-level re-rank uses language, location and, with consent, recent history. Every personal signal in the cache key lowers the hit ratio, which is why Dean lists personalisation among the factors that set it.

How to say it in the interview

“I’ll design web search over 20 billion pages at 100,000 queries a second at peak, with p99 under 300 milliseconds and fresh pages searchable within minutes.

The core is an inverted index: for each term, a docID-sorted posting list with positions. Gap encoding and variable-byte or bit-packed blocks shrink it from 144 to about 42 terabytes, mostly positions. I partition by document, not by term, into 1,000 shards of 20 million pages, about 60 gigabytes each in RAM, because that keeps load even, replies small and ranking features local. The price is that every query touches every shard.

So serving is a tree: a root, 25 parents, a thousand leaves. Each leaf does two-phase ranking — cheap BM25F plus PageRank with pruning, then a learned model on its best 200 — and returns ten. With a 1,000-way fan-out, a leaf that is slow once in a thousand calls makes most queries slow, so I use deadlines, hedged requests after the 95th percentile and good-enough answers when 99% of shards reply.

Sizing: 3 CPU-milliseconds per shard per query and 60,000 queries a second after a 40% result cache give 12 replicas per shard across three regions — 12,000 leaves, enough to lose a region.

Ranking layers BM25, anchor text and PageRank with damping 0.85, then learning to rank over hundreds of signals. Freshness comes from Caffeine-style incremental indexing into in-memory segments on each leaf, with weekly batch rebuilds for PageRank and docID order. The cache uses freshness-aware TTLs and is never flushed all at once.”

Concepts used in this design

• How search engines work — the crawl, index and serve loop this design implements.
• Search data structures — inverted indexes and posting lists in depth.
• How Google Search works — the public description of the stages and signals.
• Search end to end — from crawled page to ranked result.
• Disk I/O and durability for search — why the index lives in RAM, and what changes on flash.
• Database sharding — the general form of the document-versus-term choice.
• Data replication — replicas for capacity and failover.
• Timeouts, retries and backoff with jitter — deadlines and hedged requests.
• Caching 101 — the result cache and its hit ratio.
• Hot keys, cache stampede and invalidation — coalescing misses on hot queries.
• Batch vs stream processing — weekly rebuilds versus per-document indexing.
• Multi-region and active-active — three regions sized to lose one.
• Elasticsearch — segments, BM25, shards and replicas in an off-the-shelf engine.
• Embeddings and semantic search — meaning-based retrieval beside the inverted index.

References and further reading

1. The Anatomy of a Large-Scale Hypertextual Web Search Engine (Brin and Page, 1998)infolab.stanford.eduThe original design: hit lists, 64 forward barrels sorted into an inverted index, short and full barrels, anchor text attached to the target page, PageRank with d = 0.85, and storage numbers for 24 million pages.
2. Web Search for a Planet: The Google Cluster Architecture (Barroso, Dean and Hölzle, IEEE Micro 2003)static.googleusercontent.comIndex shards as random subsets of documents, a replica pool per shard, docservers for snippets, mostly read-only serving, and a query costing hundreds of megabytes and tens of billions of CPU cycles.
3. Challenges in Building Large-Scale Information Retrieval Systems (Jeff Dean, WSDM 2009 keynote)static.googleusercontent.comPartitioning by document versus by word, cache hit rates of 30–60%, the in-memory index, root–parent–leaf serving, block and group-varint encodings, and a decade of growth numbers.
4. The Tail at Scale (Dean and Barroso, CACM 2013)research.googleHow fan-out amplifies slow servers, measured leaf latencies, hedged and tied requests, micro-partitions, selective replication of important documents, good-enough results and canary requests.
5. Large-scale Incremental Processing Using Distributed Transactions and Notifications (Peng and Dabek, OSDI 2010)usenix.orgPercolator: replacing 100 MapReduces with per-document transactions and observers; documents 100× faster through indexing, results about 50% younger, at roughly twice the resources.
6. Our new search index: Caffeine (Official Google Blog, 2010)googleblog.blogspot.comThe layered old index whose main layer refreshed every couple of weeks, and the move to updating the index continuously in small portions.
7. In-depth guide to how Google Search works (Google Search Central)developers.google.comThe three stages, duplicate clustering and canonical selection, signals collected at indexing time, and ranking that depends on location, language and device.
8. How Google Search works: organizing information and ranking resultsgoogle.comAn index of hundreds of billions of pages and over 100,000,000 GB, 15% of daily searches being new, spelling and synonym handling, and interaction data used as signals.
9. Introduction to Information Retrieval (Manning, Raghavan and Schütze), online editionnlp.stanford.eduVariable-byte codes and measured postings compression on Reuters-RCV1, positional index size rules of thumb, and the BM25 formula with typical k1 and b values.
10. Elasticsearch similarity settings (BM25 defaults)elastic.coBM25 as the default similarity, with k1 = 1.2 controlling term-frequency saturation and b = 0.75 controlling length normalisation.