32 min read

Design Google Search

Staff Search Storage and indexes ShardingUpdated 27 October 2026

Type two words into a search box and ten good links come back before you have lifted your finger. Behind that box sit ten billion documents. In under two hundred milliseconds the system has to find every document containing your words, score them, and return the best ten.

You cannot read ten billion documents in two hundred milliseconds. You cannot even stream them off disk. Everything on this page exists to avoid looking at almost all of them. Watch one query go through.

Ask. A query arrives at the front end, which parses it and fixes the spelling.

A few words come up all through this page:

The corpus is the whole collection of documents being searched, here ten billion web pages.
A term is a word after cleaning: lowercased, and cut down to its stem, so "Searching" and "searched" both become "search".
An inverted index is the index at the back of a textbook. Instead of each page listing its words, each word lists its pages. The list of documents for one word is its posting list, and one entry in it is a posting.
A shard is one machine's slice of the index. A leaf is a machine holding one shard, and the root aggregator is the machine that asks all the leaves and combines their answers.
p99 is the time 99 out of 100 queries beat. (Percentiles, quickly explains why we care about it more than the average.)

The real Google Search

This page builds the part of a web search engine like Google Search that finds matching pages fast: an inverted index split across many machines, answering in under 200ms. The numbers are interview assumptions. Google says its own index holds hundreds of billions of pages, far more than the ten billion used here. Ranking is left to "another team", so nothing here describes how Google orders its results.

The documents themselves come from a crawler, which has its own page. This page starts where the crawler stops: pages are stored, and now they have to be searchable.

Step 1: Understand the problem#

The full problem is a decade of work, and the interviewer knows it. So this is the question where cutting scope earns the most points. These six questions decide what you build.

You ask	They say	What it settles
How big is the corpus, and how many queries a second?	Ten billion documents, tens of thousands of queries a second.	That you cannot look at the corpus. Everything on this page exists to avoid touching all but a tiny fraction of it per query.
What is the latency budget?	200ms at p99, end to end.	A fan out (one request copied to many machines) to a thousand shards, where the slowest one decides your latency. It is also why the deadline is a query parameter rather than a constant.
How fresh does the index have to be?	News in minutes, everything else in hours.	Two indexing paths, not one. A small fast path for recent documents and a slow bulk path for the rest, merged at query time.
Are we building ranking, or retrieval?	Retrieval, with simple scoring. Ranking quality is a separate team.	The biggest cut on the page. Say it early: you are designing the system that finds candidate documents fast, and leaving what order they finally appear in to a layer above.
Do queries need phrases and boolean operators?	Phrases yes, complex boolean no.	To match "new delhi" as a phrase, the index must remember where in a document each word sits, not only that it is there. Those position lists are big, so they are stored separately from the posting lists.
Personalised results?	No.	Results are cacheable. Without personalisation the same query returns the same top ten for everyone, and a cache absorbs a large share of traffic that would otherwise fan out.

What you are building#

Functional requirements

What the system does.

Answer a multi word query from a corpus of billions of documents. Boolean intersection first, then relevance ranking.
Return the top ten by relevance in under 200ms. End to end, at p99, including ranking.
Ingest new and updated documents continuously. Fresh content within minutes, not a nightly rebuild.
Serve tens of thousands of queries per second. With a heavy head of repeated popular queries.

Non-functional requirements

How well it has to do it. The numbers you commit to.

10 billion documents, average 500 useful terms each.
50,000 queries per second at peak.
p99 under 200ms including ranking.
A machine failure must not lose documents from results.

Out of scope

What you cut, and say so out loud.

Crawling. It feeds this and has its own page.
The ranking model itself. Assume a scorer exists and focus on how the system feeds and budgets it.
Query understanding, spelling correction and synonyms. Real, large, and separable.
Personalisation, which changes the caching story enough to deserve its own discussion.

Back of the envelope#

One worked line first. Ten billion documents with 500 distinct terms each means ten billion times 500 postings: five trillion. At three bytes a posting that is 15 TB, and a machine with 512 GB of memory holds about half a terabyte, so you need around thirty machines just to hold the index. Move the sliders to see how fast that grows. (The method is in back of the envelope.)

Index size

Documents10 billion

Useful terms per document500

Bytes per posting after compression3

Total postings10B x 500 = 5.0 trillion

Index size compressed5.0T x 3B = 15 TB

Machines to hold it in memory at 512GB30

Postings scanned for a two word queryup to hundreds of millions

30 machines

just to hold the index in memory, before serving a single query

Three bytes per posting is not an accident, it is the whole reason this is affordable. Document ids are stored as gaps from the previous id (delta encoding) and then in as few bytes as each gap needs (variable byte encoding), so dense posting lists compress far below a raw 8 byte id. Doubling that number doubles your fleet. The widget in Step 2 shows the trick on a real list.

Step 2: Propose the high level design#

The API#

GET/v1/search?q=distributed+consensus&limit=10&cursor=...

returns 200 { results: [...], took: 84, complete: true }

Why: The response says whether every shard answered. A caller that needs completeness, such as an internal evaluation job, can retry, while a user facing page ignores it. Hiding partial results makes debugging a slow shard impossible.

GET/v1/search?q=...&deadline_ms=120

returns 200 with whatever finished in time

Why: The deadline is a parameter, not a constant. A page load wants 120ms and a background quality evaluation can afford 5 seconds, and the same fan out serves both by returning what it has when the clock runs out.

POST/v1/documents

{ "url": "...", "content": "...", "fetchedAt": "..." }

returns 202 { segmentEta: "~90s" }

Why: Indexing is asynchronous and the caller is told roughly when the document will be searchable. Promising immediate visibility would mean writing into a live compressed index, which is exactly what the segment design avoids.

The inverted index#

Think of the index at the back of a textbook. You do not read the book to find "quorum", you look up "quorum" and get page numbers. An inverted index is that, for ten billion documents: each term points to the sorted list of document ids that contain it. A normal database index points from one value to its rows (what an index actually is); this one points from every word to every document holding it.

How do you find every document that contains both words?

First try
Read every document
Open each document and check whether it has both words. It is correct and needs no index at all.
Where it breaks: Ten billion documents per query. You cannot even stream them off disk in 200ms, let alone 50,000 times a second.
Better
One inverted index on one big machine
Build the word to documents lists once. A query now reads two lists instead of the whole corpus.
Where it breaks: The napkin math above: about 15 TB compressed, roughly thirty machines of memory just to hold it, and a single machine cannot serve 50,000 queries a second anyway.
What you ship
The inverted index, split by document across a thousand leaves
Every leaf holds a complete small index over its own slice of documents, answers the whole query locally, and returns its best few. The first deep dive shows why splitting by document beats splitting by word.

A query for two words needs the documents that appear in both lists. Because both lists are sorted, you can walk them side by side, like two people reading the same register from the top, calling out matches. Try it, then turn on skip pointers and the gap view.

Intersect "raft" and "consensus"

"raft", 3 documents

74188

"consensus", 32 documents

23589121415192123262830333538414446495255576063667074798388

comparisons: 33entries read: 32 of 32in both: 41, 88

Both lists are sorted, so one pass over each finds the ids they share: 41 and 88. That took 33 comparisons and read all 32 entries of the long list, even though the short list has only 3 ids.

Toy lists. A real common term has hundreds of millions of entries, which is why skipping and compressing matter at all.

The table below is one posting list as it is actually stored.

posting listone entry per term, sorted by document id

term	string	PK	After tokenising, lowercasing and stemming.
doc_freq	int		How many documents contain it. Feeds IDF (inverse document frequency: a rare word counts for more than a common one) and query planning.
postings	delta encoded list		Ascending document ids stored as gaps, so a dense list costs a byte or two per entry.
positions	optional list		Where in the document. Needed for phrase queries and expensive to store, so often kept in a separate structure.
skip pointers	sparse index		Every few hundred entries, so intersecting a rare term with a common one can jump rather than scan.

Sample row

"quorum" | 84,102 | [17, +4, +23, +2, +981, ...] | ... | every 128th entry

Sorted order is what makes intersection cheap: two sorted lists intersect in a single linear pass, and skip pointers turn that into something closer to a binary search when one list is far shorter than the other. Nearly every optimisation in query serving depends on that ordering.

The whole system on one whiteboard#

Two systems live in Figure 1 and they meet in exactly one place. Indexing turns documents into segments: index files that are written once and never changed (immutable). Serving loads those files and answers queries. Neither one can slow the other down, which is the property you are buying.

Figure 1. A query fans out to every shard and comes back in 200ms. Indexing runs on its own clock and hands over immutable segments. The only thing crossing between them is a file.

Walking Figure 1:

The query is parsed, corrected and expanded at the front end. This is cheap and it is where a bad query gets turned into a good one.
Popular queries never go further. Without personalisation the top ten for "weather" is the same for everyone, and a result cache absorbs a large slice of traffic. (A cache hit is when the answer is already there, a miss when it is not. The layers of caching chapter covers the rest.)
On a miss the root aggregator takes over. It owns the deadline.
It asks every leaf shard, because the index is partitioned by document and any shard might hold a match. A thousand parallel requests, and the slowest one is your latency.
Each leaf intersects posting lists inside its own segments and returns its best few candidates, not its matches. Sending back thousands of document ids would drown the root in network traffic.
The root merges a thousand short lists, keeps the top ten, and only then fetches titles and snippets. That fetch is called hydrating: turning bare document ids into something you can show. Hydrating before merging would mean fetching a thousand times more documents than you show.
Indexing runs completely separately, on its own schedule, feeding on whatever the crawler produced.
The indexer writes segments once and never edits them.
A merger compacts (combines) small segments into large ones in the background, and publishing a new segment set is how updates reach serving. Rolling back is pointing at yesterday's set, the same move as switching back in a blue-green deploy.

Your answer

Step 4 asks all 1,000 shards on every query. The alternative is to shard by term, so a query only touches the shards holding its words. Which would you pick, and what does the other one cost?

Step 3: Design deep dive#

How to shard the index#

The index is far too big for one machine, so it has to be split into shards (the sharding chapter explains why the choice of split decides everything). There are two natural ways to split an inverted index, and both sound reasonable until you count what crosses the network.

How do you split the index across machines?

First try
Keep it on one machine
No splitting, no coordination, every query is local.
Where it breaks: It does not fit. The napkin math says about thirty machines of memory for the compressed postings alone, before positions, replicas or any query load.
Better
Split by term
Each shard owns whole posting lists for some words, so a two word query only touches the two shards holding its words.
Where it breaks: The query needs both lists in one place to intersect them, and a common word has hundreds of millions of entries. You end up shipping hundreds of megabytes across the network per query, and the shard holding common words takes most of the traffic.
What you ship
Split by document
Each shard holds a complete little index over its own slice of documents. Every shard answers the whole query locally and returns its own top few. One round trip, and only a handful of results cross the network per shard.

Flip between the two splits to see where the work happens.

Index partitioning

Every shard holds a complete index over its own slice of documents, so every shard can answer the whole query locally and return its own top ten. One round trip, perfect parallelism, and each shard scores documents it holds entirely in memory. The cost is that every query touches every shard, so a thousand shards means a thousand requests per query and your p99 is the slowest of a thousand machines. This is what everyone actually runs.

Sharding by document wins, and it wins for a reason worth stating precisely: it keeps the intersection local. Term sharding minimises the number of machines contacted and maximises the bytes moved, and in this workload bytes moved is what costs you.

There is a second reason. How often words are used follows a power law: a handful of words ("the", "of", "and") appear in a huge share of documents, and most words are rare. Split by term and that skew lands on whichever shards own the common words.

Shard load

Shard 2 carries 12.6% (even would be 12.5%)

Every shard answers every query over its own document slice, so load is inherently even regardless of what people search for. Even distribution with no tuning is a large part of why this scheme survives.

The two hundred millisecond budget#

A thousand shards is a thousand chances to be slow. If each shard is fast 99% of the time, the chance that all thousand are fast on one query is 0.99 multiplied by itself a thousand times: about 0.004%. So nearly every query waits for at least one slow shard. Tail latency (the slow end of the timings) does not average out under fan out, it compounds. Fan-out turns rare into common has a slider for exactly this.

How do you answer in 200ms when a thousand machines must reply?

First try
Wait for every shard
Send the query to all thousand leaves and reply when the last one answers. Complete results every time.
Where it breaks: The query is as slow as the slowest of a thousand machines, and some machine is always mid garbage collection or compaction. The p99 of the page becomes the worst case of the fleet.
Better
Hedge the slow ones
If a shard has not answered within its usual p95 time, send the same request to a replica of that shard and take whichever answer comes first.
Where it breaks: Better tails, but every query still fans out to a thousand machines. At 50,000 queries a second that is 50 million shard requests a second, many of them for popular queries a cache could have answered.
What you ship
Cache, tiers, hedging and a deadline
Answer popular queries from the result cache. Send most of the rest to a small tier one index of the best documents. Hedge slow shards. And when the deadline arrives, return what has arrived.

Here is the third rung one layer at a time.

1/4 Try the result cache first. Query popularity is extremely head heavy, so a modest cache absorbs a large share of traffic outright. This is also the only layer that can return in single digit milliseconds.

Two more techniques matter and both are worth naming out loud.

Hedged requests. If a shard has not replied within the time 95% of its requests normally take (its p95), send the same request to a replica, another machine holding a copy of the same shard, and take whichever answers first. Only about 5% of requests ever get a second copy, so it costs about 5% extra load, and it removes most of the tail, because a slow response is usually an unlucky machine rather than a hard query. (Hedged requests walks through one.)

Serve incomplete results. At the deadline, return what you have. A result set missing two shards out of a thousand is almost always identical in its top ten, and a user will never know. Waiting for stragglers to be complete is the wrong trade when the ranking is approximate anyway.

The follow up you will get

"What if a shard is down?" Each shard is replicated several times, so the root picks a healthy replica. If every replica of a shard is unavailable, the query returns results from the other 999 and records the incompleteness. Refusing to answer because one thousandth of the corpus is unreachable is worse for the user than a very slightly worse result set.

Keeping the index fresh#

Posting lists are sorted, compressed and packed. Inserting one document into the middle of a compressed sorted list is close to the worst operation you could ask for.

A news story was published two minutes ago. How does it become searchable?

First try
Rebuild the whole index every night
Simple, and every index file is built fresh and tidy.
Where it breaks: News has to be searchable in minutes. A story published at 9am would not show up until after the next nightly rebuild.
Better
Insert into the live posting lists
When a document arrives, add its id to the posting list of every term in it.
Where it breaks: Each insert into the middle of a sorted, gap encoded list means rewriting that list, for hundreds of terms per document, while queries are reading the same lists.
What you ship
Small immutable segments, merged in the background
New documents land in a small fresh segment that is searched alongside the big ones. Segments are never edited. Deletes are a list of removed ids applied at query time, and a merger combines small segments into big ones.

So do not edit. Build small immutable index segments continuously, search all of them, and merge them in the background. Deletes are a bitmap, one bit per document id, set to 1 when that document is removed and checked at query time, rather than a rewrite.

This is the same append only idea as an LSM tree in a database (the LSM-tree family), applied to an index rather than a key value store. It is also why searching a large corpus means intersecting across several segments and merging the results. Search autocomplete uses the same trick for its tries: build beside, then flip a pointer.

Figure 2. Indexing and serving are separate systems that meet only through immutable segments.

Because segments are immutable, a serving shard never modifies anything it reads. That makes concurrency trivial (no reader can see a half written list), makes replication a file copy, and means a rollback is pointing at an older segment set.

Break it#

Query serving

10k qps

10k qpsone slow shard50k qpshedged and tiered

Healthy. Cache absorbs the head, tier one answers most misses, fan out is fast and the p99 sits comfortably inside budget.

Read every step as text

10k qps · Healthy. Cache absorbs the head, tier one answers most misses, fan out is fast and the p99 sits comfortably inside budget.
one slow shard · Degraded. One machine out of a thousand starts running slow, perhaps mid compaction. Because every query touches every shard, that one machine is now in the critical path of every single query and the whole p99 moves.
50k qps · Down. At peak, fan out multiplies. 50,000 queries a second across 1,000 shards is 50 million shard requests a second, and the root is now doing more connection management than search. Fan out cost is superlinear in a way raw query rate hides.
hedged and tiered · Healthy. Tier one answers most queries against a much smaller fan out. Hedged requests remove the slow shard from the tail by asking a replica. And at the deadline the root returns what it has rather than waiting, so one bad machine costs a result nobody notices instead of a slow page everybody notices.

Trade-offs#

Choice	What you gain	What you pay	Pick it when
Shard by document	Intersection stays local, load is even without tuning, and one round trip answers the query.	Every query touches every shard, so tail latency compounds and fan out cost grows with cluster size.	Essentially always for full text search. Term sharding loses on network bytes.
Tiered index	Most queries are answered against a small fraction of the corpus, cutting both latency and fan out.	Two indexes to maintain, and a quality decision about what belongs in tier one.	Any corpus where document quality varies enormously, which is the whole web.
Hedged requests	Removes most of the tail caused by unlucky machines rather than hard queries.	A few percent extra load, and duplicate work that must be safe to discard.	Any large fan out where p99 matters more than raw throughput.
Immutable segments	No in place mutation, so replication is a file copy and rollback is pointing at older files.	Queries intersect across several segments, and background merging consumes real resources.	Any index that must stay fresh without being rebuilt wholesale.

Interview replay#

Interviewer

Index by document or by term across your thousand machines?

The core decision, and both answers can be argued badly.

You

By document. Term sharding touches fewer machines per query, which sounds better, but a multi word query has to intersect posting lists and a common term has hundreds of millions of entries, so you end up shipping hundreds of megabytes across the network per query. Document sharding keeps the intersection local: every shard answers the whole query over its own slice and returns its own top ten. It also spreads load evenly for free, whereas term frequency follows a power law and skews badly.

Names the metric that decides it, bytes moved rather than machines contacted, and adds the skew argument as a second independent reason.

Interviewer

Every query hits a thousand machines. What does that do to your p99?

The tail latency question, which is really about whether you have thought about fan out.

You

It makes the p99 of the query roughly the worst case of a thousand machines rather than the typical case of one. If each shard is slow one time in a hundred, essentially every query hits at least one slow shard. So I would hedge: once most shards have replied, send the outstanding ones to a replica and take the first answer. And at the deadline I return what I have. Missing two shards out of a thousand almost never changes the top ten.

The observation that tail compounds rather than averages under fan out is the senior insight in this whole question.

Interviewer

Returning incomplete results seems dangerous. Justify it.

Pushing to see whether the previous answer was considered.

You

The ranking is already an approximation, so completeness was never exact to begin with. The choice is between a page that is 200ms slower and a top ten that is very occasionally missing a result that was unlikely to be in it. I would still expose completeness in the response, so an internal evaluation job can demand the full set and a slow shard is visible rather than silently degrading quality.

Grounds the trade in what the product actually guarantees, then keeps the signal rather than hiding it.

Interviewer

How do you add a new document without rebuilding the index?

Freshness, and the answer should mention immutability.

You

I do not modify anything. New documents go into a small new segment, and a query searches all segments and merges. A background process compacts small segments into larger ones. Deletes are a bitmap of removed ids applied at query time rather than a rewrite. It is the same idea as an LSM tree, and immutability is what makes replication a file copy and rollback a matter of pointing at older segments.

Connects it to a structure already covered and names three separate benefits of immutability.

Interviewer

Where would you spend effort first if the p99 were 400ms?

Open ended prioritisation, which is what separates levels here.

You

I would measure where the time goes before changing anything, because the three candidates have very different fixes. If it is the tail of fan out, hedging and deadlines. If it is ranking, cut the candidate set or make the model cheaper. If it is a cache miss rate, that is the cheapest win of the three. I would not guess between them, since fan out tail and model cost look identical from the outside and the fixes have nothing in common.

Refuses to optimise without measurement and names why the guess would be unreliable. Honest and specific.

Checkpoint#

Checkpoint

1. Why is term sharding worse than document sharding despite touching fewer machines per query?

2. Each shard is slow 1% of the time and a query fans out to 1,000 shards. What is the practical consequence?

3. Why are index segments immutable rather than updated in place?

Worth memorising

10 billion documents, 200ms at p99. You can never touch more than a sliver of the corpus.
Shard by document, not by term. Every query asks all 1,000 shards and the slowest one is your latency.
Leaves return their best few candidates, not their matches. Otherwise the root drowns in network traffic.
Segments are immutable. A rollback is pointing at yesterday's set of files.

Say this in 60 seconds

The core structure is an inverted index with delta encoded posting lists, sharded by document rather than by term, because a multi word query has to intersect lists and term sharding would mean shipping hundreds of megabytes across the network per query while document sharding keeps the intersection local and the load naturally even. The cost of that choice is that every query touches every shard, so tail latency compounds instead of averaging, and I would handle that with a tiered index so most queries only search a small high quality subset, hedged requests to a replica once most shards have answered, and returning at the deadline with whatever arrived rather than waiting. Retrieval is deliberately cheap and returns about a thousand candidates, and only then does the expensive ranking model run. Freshness comes from small immutable segments merged in the background, with deletes as a bitmap applied at query time, so nothing is ever rewritten in place and replication is a file copy.