Design Google Search

Search 50 billion pages at 100 k queries a second: the ten best results with snippets in under 200 ms, and news within minutes.

Last updated 2026-10-26. Difficulty: hard. Patterns: inverted-index, scatter-gather, tail-latency, ranking, search. Reported at Google, Microsoft, Amazon, Meta, LinkedIn, Apple.

Functional requirements

• Return the ten best results for a query. Ranked by relevance and quality, each with title, URL and snippet. Later pages exist but are rare, so the design optimises page one.
• Query-dependent snippets. The lines under each result show the query's words in context, so they are generated per query from stored page text, and only for the ten results shown.
• Understand the query. The same tokenisation as the index, spelling correction ("did you mean"), stemming and synonyms, language and region. Most bad results start as a badly understood query.
• Phrases and operators. Quotes, site: and minus terms. Exact phrases need word positions in the index, which roughly doubles its size.
• Fresh content within minutes. A news article fetched a minute ago should rank for the query people are typing about it. The main index is rebuilt daily, so freshness needs its own path.
• Index the crawled web. Turn the crawler's stored pages and link graph into a sharded inverted index: parse, keep one page per duplicate cluster, compute link-based quality (PageRank) and anchor text, invert, compress, ship.
• Removals take effect quickly. Dead pages, spam and legal takedowns must leave results, and cached result pages, within minutes to hours, not at the next weekly build.
• Out of scope. Crawling (the Web Crawler question) and autocomplete (the Typeahead question) are existing systems we consume. Also out: ads, image and video verticals, knowledge panels, personalisation beyond language and region, and training the ranking model.

Non-functional requirements

• Latency (p99 < 200 ms server side). Budget: ~15 ms front end and query understanding, ~10 ms canary, ~70 ms fan-out with a 60 ms leaf deadline, ~30 ms re-rank, ~20 ms snippets, ~15 ms render, ~40 ms reserved for a tier-2 fall-through. This drives the hardest tradeoff: at a 1,000-way fan-out, waiting for every leaf makes the slowest leaf everyone's latency.
• Query rate (100 k/s peak · ~4 B/day). Read-only from the user's side. About half is absorbed by the result cache; the other half fans out to every index shard.
• Corpus (50 B documents · ~125 TB index). After the crawler's duplicate collapse. A thousand times what one machine holds in memory, which forces the partitioning decision.
• Freshness (fetched news searchable < 1 min). "Minutes after publication" end to end also depends on the crawler finding the page. The batch index lags by a day (tier 1) or a week (tier 2); the real-time tier covers the gap.
• Availability (99.99 %). Degrade by recall, never by errors: losing one shard drops 0.1 % of documents from a query, which nobody can see. An error page or a two-second page is seen by everyone.
• Relevance (NDCG offline + A/B online). Ranking quality is a requirement with a number, checked on human-rated queries and live experiments. A change that is faster but worse does not ship.
• Cost (RAM only where it earns it). Everything in memory at 15 replicas would be ~1.9 PB of index in RAM. Tiering and the result cache bound the cost per query; this is the second hardest tradeoff after latency.

Back-of-envelope estimates

• Query rate: ~100 k/s peak · ~4 B/day. Peak 100 k/s is about twice the average, so ~50 k/s × 86 400 s ≈ 4.3 B queries/day. All of them are reads; documents arrive from the crawler at a far lower rate and in batches.
• Index size: ~2.5 KB/doc · ~125 TB. A page has ~1 000 words and ~400 distinct terms after boilerplate removal: 400 postings. With delta + varint a posting with positions is ~5 B (vs ~20 B raw), so 2 KB of postings plus ~0.5 KB of per-document scoring data. 50 B docs × 2.5 KB ≈ 125 TB. It grows with the corpus, not with time, because it is rebuilt rather than appended.
• Tier-1 shard size: 10 M docs · ~25 GB in RAM. Tier 1 is the best 10 B documents over 1 000 shards: 10 M docs per shard × 2.5 KB ≈ 25 GB. Small enough for a leaf to hold two copies in memory, which is what lets a new version load beside the live one.
• Queries reaching the index: ~50 k/s · ~55 M leaf requests/s. A result-cache hit rate of ~50 % (Jeff Dean's 2009 WSDM talk gives 30–60 % for Google's cache servers) leaves 100 k × 0.5 = 50 k/s at peak. Each fans out to ~1 100 leaves (1 000 tier 1 plus 100 real-time): ~55 M leaf requests a second.
• Tier-1 leaf machines: ~15 replicas/shard · ~15 k leaves. A leaf spends ~4 ms of CPU per query; 32 cores at 60 % ≈ 5 k queries/s per replica. 50 k/s ÷ 5 k = 10 replicas per shard for throughput, ~15 once three regions are each sized to absorb a lost one. 1 000 shards × 15 ≈ 15 000 machines: the fan-out, not the corpus, sets the fleet size.
• Queries that wait on a slow leaf: ~100 %. If each leaf exceeds its p99 (40 ms) 1 % of the time, all 1 000 are fast with probability 0.99^1000 ≈ 0.004 %. Almost every query waits on some leaf's tail, so without hedging and deadlines the leaf p99.9 becomes the query median.
• Real-time tier: ~170 M docs · ~1.7 TB. ~1 k fresh docs/s from the crawler's priority lanes × 48 h (172 800 s) ≈ 170 M docs. Updatable in-memory segments compress less, ~10 KB/doc, so ~1.7 TB over 100 shards of ~17 GB. Under 0.4 % of the corpus: freshness is a small index, not a fast big one.
• Snippet reads and doc store: ~500 k reads/s · ~200 TB. 10 snippets × 50 k queries/s = 500 k doc reads/s. Making snippets for all 500 re-ranked candidates would be 25 M/s, 50× more, which is why they come last. The doc store is 50 B docs × ~4 KB of compressed text ≈ 200 TB, three replicas on SSD.

Components

• Browser / app: The search box and results page. Sends the submitted query (suggestions while typing come from the separate Typeahead system) and reports clicks, the main online signal of whether ranking is good. Results are the same for everyone with the same language and region, which is what makes them cacheable.
• Search front end (owns the 200 ms budget): Terminates TLS in the nearest region, calls query understanding, checks the result cache and on a miss hands the query to a root server. Holds the small hot-term table from the real-time tier, which decides a query's freshness class and whether a cached page is still valid. Sets one deadline that every downstream call inherits, renders the page, and logs impressions and clicks.
• Query understanding (spelling · intent · term stats): Normalises and tokenises the query with exactly the analyser the indexer used, corrects spelling from what users retype, adds stems and synonyms, and detects language. Returns each term's global document frequency, which gives the root its IDF and predicts whether the query is rare. Also tags freshness intent from history: do users of this query click recent results?
• Result cache (query → page · ~50 % hits): Finished result pages keyed by normalised query, language, region and SafeSearch: ~100 M entries, ~500 GB per region. Query popularity is Zipf-like, so the head is cheap to cache, and the ~15 % of daily queries that are new cap the hit rate. TTL follows the freshness class (60 s for news-like queries, hours otherwise), and an entry created before a burst on one of its terms is treated as a miss.
• Root server (scatter, merge, re-rank): Runs one query: canary leaves first, then the fan-out to tier 1 and the real-time tier (and tier 2 when needed), merge, dedupe by URL fingerprint, re-rank, snippets. Holds the query deadline and decides whether shard coverage is good enough to serve. Stateless; any root can serve any query.
• Aggregators (~25 per query, 40 leaves each): The middle of the serving tree. Each sends the query to 40 leaves, hedges the slow ones, merges 400 results into its top 50, and returns at the deadline with whatever it has plus a count of shards answered. Keeps any one machine from gathering 1,000 responses and puts hedging decisions next to the leaves.
• Tier-1 leaves (1,000 shards × 15 replicas · RAM): Each holds one shard: ~10 M of the best documents, ~25 GB of compressed postings and per-document data in memory. Intersects posting lists, scores matches with BM25 over fields plus proximity and static rank, prunes with WAND-style bounds, and returns its top 10 with features. Documents are placed by URL hash, so every shard does the same work for every query.
• Tier-2 leaves (1,000 shards × 6 replicas · SSD): The long tail: the other ~40 B documents, ~100 GB per shard on local NVMe SSD, rebuilt weekly. Searched in parallel when a query looks rare, or afterwards when tier 1 returns too few good results: ~15 % of index queries. Rare terms have short posting lists, so SSD is fast enough for exactly the queries that get here.
• Real-time index (~48 h · 100 shards · in memory): Indexes fresh documents from the stream into small in-memory segments that become searchable every ~5 s and merge in the background. Queried on every cache miss beside tier 1; when both return a page, the newer copy wins. Counts terms in fresh documents per 5-minute window and publishes the bursting ones as hot terms.
• Re-ranker (learned model · 500 candidates): Orders the merged candidates with a learned model over a few hundred features: the leaves' text scores, anchor and click signals, freshness, and the similarity of query and document embeddings. About 50 µs a document, affordable for 500 and absurd for millions. Trained offline on human ratings and clicks; a new model ships only after it wins an A/B test.
• Doc servers (text by URL fingerprint · 200 TB): The stored text, title and URL of every indexed page (~4 KB compressed), sharded by URL fingerprint and replicated three times on SSD. Builds query-dependent snippets for the final ten results only. Written by the batch build and by the fresh stream, so new pages get snippets too.
• Crawler (existing) (content store + crawl log): The Web Crawler design, taken as given: it fetches pages politely, collapses duplicates, and stores pages with a log of every fetch and the extracted link graph. Its priority lanes (news sites, pinged sitemaps) also publish to the fresh stream. Everything in this design starts from its output.
• Fresh doc stream (Kafka · key = URL fingerprint): Recently fetched pages from the crawler's priority lanes, ~1 k documents a second. Keyed by URL fingerprint so successive versions of one page stay in order. The real-time index and the doc servers consume it independently, so a slow consumer delays only itself.
• Batch indexer (MapReduce · tier 1 daily): Parses pages, computes PageRank and anchor text over the link graph, assigns documents to shards by URL hash, to tiers by static rank and to doc ids in rank order, then inverts and compresses postings in a MapReduce-style job. Rebuilds tier 1 daily and tier 2 weekly. Validates every build against the live version before it ships.
• Index versions (immutable shard files · DFS): Versioned, immutable shard files on a distributed file system: postings, term dictionary, per-document data and global term statistics. Leaves load a new version beside the old one and swap. Rollback is pointing at yesterday's files, never a rebuild under pressure.

User flows

1. A query the cache has not seen. The main read path. One query becomes about 1,100 leaf requests plus aggregators, a re-ranker and ten doc servers, and must come back within 200 ms at p99. Each stage does expensive work on fewer documents than the last: millions matched, 10 per leaf, 500 re-ranked, 10 snippets.
   1. The browser sends the query to the nearest front end. DNS and anycast route to the closest region. The front end owns the 200 ms budget and stamps a deadline that every downstream call inherits, so work stops as soon as its answer can no longer be used. It logs the impression now and the click later, for ranking training and cache statistics.
   2. Query understanding normalises the text, fixes spelling, and returns term statistics and a freshness intent. Tokenisation must match indexing exactly (Unicode normalisation, case folding, stemming), or query terms never meet their postings. Spelling corrections come from query logs: what people retyped after a miss. Global document frequencies give the root its IDF and predict whether the query is rare.
   3. The front end looks the normalised query up in the result cache and misses. The key is a hash of normalised terms, language, region, SafeSearch and page number. About half of all queries hit and return the finished page in ~20 ms without touching the index; this one is in the long tail.
   4. The root sends the query to two canary leaves, then to the whole tier-1 tree and the real-time tier at once. Canaries first: a query that crashes leaves (a parser bug, a pathological term) takes down two machines instead of a thousand, a technique Dean and Barroso describe in "The Tail at Scale". Global IDF travels with the query so every shard scores on the same scale. About 25 aggregators fan out to 40 leaves each, so no machine gathers 1,000 responses.
   5. Each leaf finds the matching documents in its shard, scores them cheaply, and returns its top 10. Doc ids are assigned in descending static rank, so lists sorted by id are also sorted by quality. The leaf intersects from the rarest list using skip pointers, scores matches with BM25 over title, body, anchor text and URL plus proximity and static rank, and uses WAND-style upper bounds to skip documents that cannot beat its current tenth. It scores thousands of documents rather than millions, ~4 ms of CPU.
   6. Aggregators merge their leaves' lists; the root merges those with the real-time hits and keeps the best 500. Each aggregator keeps 50 of its 400 and the real-time tier contributes its best 100, so the root keeps 500 of ~1,350 by cheap score. Duplicates collapse on URL fingerprint and a real-time copy beats the batch copy because it is newer. A leaf that misses the deadline costs 0.1 % of the documents for this query, not the query.
   7. The re-ranker orders the 500 candidates with a learned model, and the root picks the final ten. Gradient-boosted trees or a small network over a few hundred features: the leaf's text scores, anchor matches, the document's click history, freshness, and query-document embedding similarity. ~50 µs a document, ~25 ms for 500. Then rules: at most two results per host, near-duplicates collapsed, removals filtered.
   8. Doc servers build query-dependent snippets for the ten winners. Each doc server reads the page's stored text and picks the window with the most query terms closest together, then highlights them. Ten documents instead of 500 is 500 k reads a second instead of 25 M. A doc server that misses its 20 ms deadline is replaced by the page's stored description.
   9. The front end renders the page, caches it with a TTL set by freshness class, and returns it. Low-freshness queries are cached for hours, bounded by the index version, with jitter so entries never expire together; fresh-class queries for 60 s. The entry stores its terms and creation time, so a later burst on any of its terms invalidates it on read.
2. Building and shipping the daily index. The batch write path. The crawler's pages become 1,000 immutable tier-1 shards every day (tier 2 weekly) through a MapReduce-style job, then replace the live index one replica group at a time. The build may be slow; the swap must never be risky.
   1. The batch indexer reads the crawler's stored pages and link graph. The crawler's content store and crawl log are its output and our input. Parsing extracts main text, title, headings, outlinks with their anchor text and language, and keeps one page per near-duplicate cluster the crawler identified.
   2. Link analysis computes PageRank and attaches anchor text to the pages it points to. PageRank (Brin and Page, 1998) is a few dozen iterations over ~50 B pages and ~1 T links in a graph-processing job. Anchor text often describes a page better than the page itself, so it is indexed as a field of the target. With spam and quality scores this gives every page a static rank: its quality before anyone types a query.
   3. Pages are assigned to shards by URL hash, to tiers by static rank, and to doc ids in rank order. shard = hash(url_fp) mod 1,000 spreads pages, and therefore work, evenly. The top 10 B by static rank go to tier 1 and the other 40 B to tier 2. Within a shard doc id 0 is the best page, so every posting list is in quality order and a leaf can stop early.
   4. Mappers tokenise each page and emit postings; one reducer per shard writes compressed posting lists. The shuffle groups by shard and sorts by term, then doc id. Each list stores gaps between doc ids in variable-length bytes (group varint, which Dean's 2009 WSDM talk describes, decodes faster than plain varint), with skip pointers every 128 postings, shrinking a posting with positions from ~20 bytes to ~5. A failed reduce task is retried alone, because every shard is an independent partition.
   5. The build writes immutable shard files and the document text for snippets. A tier-1 shard is ~25 GB: postings, term dictionary, per-document data and global term statistics. Files are versioned and never modified, so rollback is pointing at the previous version. The doc store gets each page's text, title and URL (~4 KB compressed) keyed by URL fingerprint.
   6. Validation compares the new build with the live one before any leaf loads it. Per-shard document counts and sizes against yesterday (a shard 30 % smaller is a bug, not news), then a replay of sampled queries against both versions comparing top-10 overlap and NDCG on a rated query set. A failed build simply does not ship: yesterday's index keeps serving and the real-time tier keeps the newer pages.
   7. Leaves load the new shard beside the live one, warm it, and swap, one replica group at a time. A tier-1 leaf has memory for two 25 GB copies: it loads the new one while serving the old, warms it with replayed queries, flips a pointer, and frees the old. One of 15 replica groups goes first and is watched for latency, coverage and click metrics before the rest follow. Mixed versions during the rollout are harmless, because a page lives in the same shard in both.
3. Breaking news, searchable within a minute. An earthquake story is fetched at 14:02 and ranks for "earthquake" by 14:03, although the batch index was built last night and "earthquake" is suddenly the hottest key in the cache. Freshness needs its own small index and a cache that knows which entries went stale.
   1. The crawler fetches the article and publishes it to the fresh-document stream. Only the crawler's priority lanes publish here (news sites, sitemaps with a recent lastmod, pinged URLs): ~1 k documents a second, a tiny fraction of the crawl. Keyed by URL fingerprint so later versions of the same page stay ordered.
   2. Real-time leaves index the article in memory and make it searchable within seconds. The same analyser as the batch build writes into small in-memory segments that are opened for search every ~5 s and merged in the background, an LSM-like design. With no PageRank yet, static quality comes from the host's history and early links. The tier keeps ~48 h, ~170 M documents over 100 shards; anything older is in the batch index.
   3. The article's text is also written to the doc store so it can get a snippet. A result without a snippet is a bad result. A separate consumer writes it keyed by URL fingerprint, so a newer version of a page replaces the snippet source and a slow doc store never delays indexing.
   4. The real-time tier sees "earthquake" bursting and publishes it to the front ends as a hot term. Per-term counts in fresh documents over 5-minute windows, compared with each term's own baseline, so a term that is always common never looks like news. A hot term makes any query containing it fresh-class: a 60 s cache TTL and a recency boost in ranking.
   5. Searches for "earthquake" jump to 20 k/s; the cached page from before the burst is treated as a miss. The cached page from 13:50 has no news in it. Instead of finding every affected key, the front end compares an entry's created_at with the burst time of each of its terms on read. Invalidation by comparison costs nothing to issue and is exact for the queries that are actually asked.
   6. One request per key goes to the index; the rest wait for it or are served the current page. Single-flight per cache key: the first miss computes the page and concurrent requests wait up to ~100 ms for it. With a 60 s TTL and stale-while-revalidate, the busiest query in the world costs the index about one query a minute per region. The recency boost lets the 14:02 article outrank a high-PageRank page about earthquakes in general.
   7. Tonight's build includes the article, and the real-time tier drops it once that version is live. The real-time tier keeps everything newer than the live batch version's cutoff, which is why it holds 48 h for a daily build: a late or failed build must not make yesterday's news vanish. During the overlap the root dedupes by URL fingerprint and keeps the newer copy.
4. One slow leaf among a thousand. At a 1,000-way fan-out something is always slow: a leaf in a garbage-collection pause, a machine being drained, a failing disk. Waiting for everyone would make the slowest leaf's tail every query's latency, so the design never waits for everyone.
   1. The aggregator sends each shard's request to the replica with the fewest outstanding requests. Each shard has ~5 replicas per region. Least-outstanding-requests (or the better of two random picks) steers away from busy machines before anything has gone wrong, which is the cheapest tail-latency fix there is.
   2. Replica 3 is stuck in a 150 ms pause; after 20 ms with no answer, the aggregator sends a backup to another replica. Hedging at about the leaf's p95 sends a backup for ~5 % of requests, and the loser is cancelled on the first answer. Hedges are capped at 5 % per aggregator so they cannot snowball when every leaf is slow. "The Tail at Scale" reports that hedging after 10 ms cut a 100-server BigTable fan-out's p99.9 from 1,800 ms to 74 ms for 2 % more requests.
   3. A replica machine dies; its in-flight requests fail fast and are retried on a sibling. A reset connection is an immediate signal, unlike a slow leaf, so the retry lands within milliseconds and well inside the deadline. Health checks drop the machine from every aggregator's list within seconds, and its siblings absorb the load because each runs at ~60 % CPU.
   4. At 60 ms the aggregator stops waiting and returns what it has, saying which shards are missing. With document partitioning, a missing shard removes 0.1 % of the documents from this one query, and the chance that one of its documents belonged in the top ten is about 1 %. That is invisible; a two-second page is not. The coverage count lets the root and monitoring see it.
   5. The root checks coverage; below a floor it retries the query in another region instead of serving a quietly bad page. Coverage is normally 99.9 % or more. If a rack or a replica group is out and it falls below ~97 %, results get noticeably worse, so the front end resends the query to the next region and an alert fires. Silent partial results must never become the normal state.
   6. A replica that is persistently slower than its siblings is put on probation. Latency-induced probation, another technique from "The Tail at Scale": the replica gets only shadow requests until its latency matches its siblings again. Slow machines are usually a noisy neighbour, a failing disk or a stuck background task, and none of those recover faster under live load.
5. A rare query falls through to tier 2. Most queries are answered entirely from the best 10 B documents in memory. A query for an obscure part number needs the long tail, which lives on SSD in tier 2 and is searched only when tier 1 will come up short.
   1. Query understanding returns tiny document frequencies, so the root predicts tier 1 will be thin. For "TPS54331 errata" the rarest term appears in a few thousand pages in the whole corpus. When the expected number of tier-1 matches, from global document frequencies, is under ~100, the root queries both tiers in parallel rather than in sequence, which keeps the query inside its budget.
   2. The root fans out to tier 1 and tier 2 through the aggregators at the same time. Tier 2 has the same 1,000-way layout with 40 M documents per shard, ~100 GB on local NVMe. Rare terms have short posting lists, so a tier-2 leaf reads a few hundred KB and answers in ~20 to 30 ms: the long tail is cheap exactly for the queries that need it.
   3. For a query not predicted rare, tier 2 is consulted only when tier 1 returns too few good candidates. The trigger is fewer than ~50 merged candidates above a quality threshold. This sequential path costs ~40 ms, which the latency budget reserves, and happens for a few percent of queries. Under overload it is the first work to be shed.
   4. Candidates from both tiers are merged on one scale and re-ranked together. Both tiers use the same scoring function and the same global IDF, so their cheap scores compare directly. A tier-2 page can still win: static rank decided where it is stored, not whether it may rank for a query only it answers.
   5. Snippets come from the same doc store, and the page is cached like any other. Rare queries rarely repeat, so caching them is cheap insurance rather than a win: they are why the hit rate tops out around 50 to 60 %. Google has said for years that about 15 % of each day's queries have never been seen before.

Deep dives

The theory behind it

• Tail latency and hedged requests: an interactive playground. Fan one request out to 100 backends and watch a 1% stall become the typical case, then hedge slow calls and see what it costs in load.
• Inverted index and search ranking: an interactive playground. Search sixteen reviews through an inverted index: see posting lists, AND and OR queries, TF-IDF ranking and why common words cost the most.
• Web search engine architecture: How a Google-style web search engine fits together: crawling, document processing, building inverted indexes, document-partitioned versus term-partitioned indexes, tiered indexes, query serving with scatter-gather, ranking signals including links, freshness, caching and the numbers involved.
• Search, indexing and autocomplete: Inverted indexes, analysis and ranking, prefix search with tries, filtering by permissions, index freshness, and when vector search actually belongs in the answer.
• Search ranking and relevance: How search results are ordered: retrieval then ranking, text relevance with BM25, business and personal signals, learning to rank, semantic and hybrid search, query understanding, evaluation with NDCG and click metrics, and serving ranking within a latency budget.

Related

• Design a News Feed
• Design Search Autocomplete
• Design a Project-to-Contractor Matching System
• Design Yelp
• All 83 system design interview questions
• Run this question for a friend: the interviewer kit