The 100 problems, solved / Search and indexing / 013 · Design Google Search

Design Google Search

From a crawl to a ranked ten blue links in 200 ms: index, serve, rank.

Problem 013 of 100Search and indexingL61 Nov 2026
Concepts this design leans on
  • Inverted indexes — From every word to the documents that contain it: how search answers in milliseconds.
  • Sharding and partitioning — Splitting data by key so each machine holds a slice it can handle.
  • Replication — Keeping copies so reads scale and a dead machine loses nothing.
  • Caching strategies — Read-through, write-through, write-back, TTLs and invalidation.
  • Ranking pipelines — Scoring thousands of candidates in stages, cheap first, expensive last.

01The design, in the six-step framework

1. Requirements

Functional

  • Given a query, return the ten most relevant web pages with titles and snippets, with paging to further results.
  • Corrections and query understanding (spelling, synonyms) at a basic level; freshness for news queries.
  • Out of scope here: the crawler (see Design a web crawler), ads, personalisation, images and video verticals.

Non-functional

  • Index 100 billion pages; serve 100,000 queries per second at peak.
  • End-to-end latency under 200 ms at p99 for the result page; the index tier itself under 50 ms.
  • The index is rebuilt or incrementally updated so a new page is searchable within a day, news within minutes.
  • Availability 99.99 percent; a data centre loss degrades quality slightly, never availability.
Back of the envelope

Index size: 1011 pages × about 1,000 distinct terms each = 1014 postings. A compressed posting (doc id delta plus position info) is about 2 to 4 bytes, so the index is 200 to 400 TB; with positions and multiple tiers, say 500 TB. Document snippets and metadata add another 100 TB.

A machine with 256 GB RAM holds about 2 × 107 documents' index in memory → 1011 / 2 × 107 = 5,000 index shards for one full copy.

At 100,000 queries/s and 50 ms per shard query, each shard sees every query: a shard must handle 100,000 queries/s, which one machine cannot. Replicate each shard 20 to 50 times across data centres; the serving fleet is on the order of 100,000 to 250,000 machines.

2. Core entities

  • Document: doc id, URL, title, language, crawl time, static quality score, body (for snippets).
  • Posting list: term → sorted list of (doc id, term frequency, positions).
  • Index shard: a subset of documents with the full postings for them, plus per-doc scores.
  • Query: raw text, parsed terms, rewritten variants, user locale.

3. API

  • GET /search?q=&start=&hl= → ranked results: URL, title, snippet, plus suggestions.
  • Internal: index.query(terms, k, deadline) on each shard → top-k (doc id, score); docs.get(doc_ids) → titles and snippets; ranker.rerank(candidates, query).
  • Build side: POST /index/segments from the indexing pipeline; POST /index/swap to publish a new generation.

4. High-level design

ClientsFront endServingIndex buildquerytop-k per shardcandidatessnippetsload generationBrowserQuery front end(parse, rewrite, cache)Aggregator(scatter-gather)Index shards(5,000 × replicas)Document servers(snippets)Re-rankerPage storeIndexer(batch + streaming)Index segments

A query from keystroke to page:

  1. The front end checks a result cache (identical queries repeat a lot), then parses and rewrites the query: spelling, stemming, synonyms, detected language.
  2. The aggregator sends the rewritten query to one replica of every index shard with a deadline. Each shard intersects the posting lists, scores by a cheap function (term weights, proximity, static page quality), and returns its top few hundred.
  3. The aggregator merges the shard results into a few thousand candidates, the re-ranker applies an expensive model to the top few hundred, and the document servers produce snippets for the final ten.
  4. In the background, the indexer turns the crawler's page store into new index segments: a full rebuild on a schedule and a streaming path for fresh pages, published to shards as a new generation.

5. Deep dives

Document-partitioned or term-partitioned index?

Partition byQuery pathHot spotsIndex build
Document (each shard holds all terms for its docs)every shard answers every query; merge top-knone; load is evenindependent per shard
Term (each shard holds some terms for all docs)only the shards for the query's terms; but intersection needs full posting lists moved across the networkpopular terms overload their shardglobal sort by term

Choice: document partitioning. Sending a 100-byte query to 5,000 shards is cheap; moving a 10 GB posting list for a common word between machines is not. Document partitioning also fails gracefully: a dead shard removes 0.02 percent of the web from results rather than making the word "the" unsearchable. The scatter-gather cost is tail latency, handled next.

Tail latency: 5,000 shards and a 50 ms budget

If each shard answers in 50 ms at p99, a query that waits for all 5,000 sees the slowest, which is the p99.98 of one shard, far beyond 50 ms. Three techniques, used together. Hedged requests: after waiting for the 95th percentile latency, send the same request to a second replica and take the first answer. Deadlines with partial results: the aggregator returns at the deadline with whatever shards have answered, degrading recall slightly rather than latency. Tiered indexes: a small top tier holds the highest-quality 10 percent of documents and is searched first; the full tier is consulted only when the top tier returns too few good results, which for most queries it does not. Shard replicas also live in several data centres, and the front end routes to the nearest healthy cluster.

Ranking in stages under a latency budget

A single expensive model over 1011 documents is impossible, so the ranking pipeline narrows in stages: posting-list intersection selects documents containing the terms (millions); a cheap scorer on each shard picks hundreds using precomputed per-document quality and term statistics; the aggregator's merge picks thousands; a heavy learned ranker with hundreds of features scores the top few hundred; the final ten get snippets. Each stage is given a budget in milliseconds and a maximum candidate count, and quality is measured per stage offline. Freshness and query intent (a news query wants the last hour) are features at the merge stage that boost a separate fresh index's candidates.

Updating a 500 TB index without a pause

Index segments are immutable. The batch indexer builds a new generation of each shard from the page store, writes it to shared storage, and each shard server loads the new generation next to the old one, atomically switches queries over, then drops the old. Replicas switch in waves so capacity never dips. Fresh content takes a second path: a small streaming indexer builds minute-level segments that shards merge in memory and query alongside the main generation, so news is searchable in minutes and the daily rebuild folds it in. Deletions (removed pages, legal takedowns) are a tombstone list consulted at query time until the next rebuild.

The result cache and what it does and does not buy

Query popularity is heavy-tailed: a few hundred thousand queries make up a large share of traffic, and they are answered from a result cache keyed by (normalised query, locale) with a TTL of minutes to hours depending on how fresh the query's results need to be. That cache cuts the load on the shard fleet substantially, but the remaining traffic is the long tail of unique queries, each of which must scatter to every shard, so the fleet is still sized for the tail. An interviewer who hears "we cache results" will ask about the hit rate; the right reply is a number (a hit rate in the tens of percent is typical) and the admission that capacity planning is for misses.

6. What a strong answer sounds like

  • Size the index in bytes and shards, and derive the replica count from queries per second; the fleet size falls out and it is large.
  • Choose document partitioning and explain the network argument for it.
  • Treat tail latency as the central serving problem: hedging, deadlines with partial results, tiers.
  • Describe ranking as stages with budgets, not as one model.
  • Expect follow-ups on the result cache hit rate, on query rewriting, on how a dead data centre is handled, and on where ads would attach.
  • Common mistake: term partitioning, or forgetting that a cache in front does nothing for the long tail of unique queries.

02Where this question was reported