You type four words into a box, press enter, and roughly two hundred milliseconds later you get ten results drawn from a corpus of several hundred billion documents. That sentence contains the entire engineering problem. No clever data structure makes searching hundreds of billions of documents cheap. There is only a stack of decisions, each trading some generality away to make the common case fast.
Most explanations stop at "it uses an inverted index," which is true and roughly as useful as saying a database uses a B-tree. The inverted index is the opening move. The interesting part is everything that has to be true around it: how the index is compressed so it fits in memory, how it is split across thousands of machines, how a query is broadcast to all of them and the answers merged, why that merge is dominated by the slowest machine rather than the average one, and why ranking is a cascade of progressively more expensive models rather than one scoring function.
We start from the constraints and the arithmetic, because the numbers rule out most architectures before you draw anything. One note on figures: Google does not publish current serving internals, so the numbers here come from public statements, the published research the system is built on, and back of envelope arithmetic consistent with both. They are the right order of magnitude, meant to drive reasoning rather than to be quoted as production metrics.
What the system actually has to do
The functional surface is small. Accept a text query, return a ranked list of documents with titles and snippets, and do it for anyone on the internet without authentication.
The design is set by a latency budget spent across four stages, not by the feature list, which fits in a sentence.
The constraints are where the design lives, and the tightest one is a budget rather than a feature. Take two hundred milliseconds as the total user perceived target. Network round trip to the nearest edge and back consumes eighty to a hundred of that on a typical connection. Query understanding, meaning parsing, correction, and expansion, has to fit in a handful of milliseconds. Snippet generation and page assembly take a slice at the end. That leaves something like thirty to fifty milliseconds for the part everyone thinks of as search: reaching into several hundred billion documents, finding candidates, and ranking them.
Thirty to fifty milliseconds is the number that kills most designs. It rules out disk on the critical path, any algorithm linear in corpus size, and a single machine, since no single machine holds the index. And because the answer must be assembled from many machines, it quietly rules out waiting for all of them, for reasons we will get to.
The other constraints are softer. Availability has to be very high, because search is the entry point to everything else. Freshness is tiered: a breaking news page needs to be findable in minutes, a decade old reference page can wait a week. Consistency you get to relax almost completely. Nobody can tell whether their query hit a replica nine minutes behind, and nobody would care if they could.
Three subsystems, and two of them are offline
It helps to separate web search into three systems that share a name and share nothing else.
Crawling and indexing are throughput problems measured in hours. Serving is a latency problem measured in milliseconds. They meet only at the index artifact.
Crawling discovers and fetches documents. Its hard problems are URL frontier scheduling, duplicate detection, per host politeness, and deciding what is worth recrawling and how often. Indexing turns fetched documents into the structures the serving path reads: it parses HTML, extracts text and anchor text, detects language, computes document level signals, assigns internal document identifiers, and builds the inverted index. Both are measured in documents per second and hours of wall clock.
Serving is the only one that runs while a user waits, and it is the subject of this piece. The two offline systems exist to move work out of the online one. Every signal computed at index time, every posting list presorted, is latency the serving path does not pay. When you see work in a search system, the first question is whether it can move to index time. That question drives more of the design than any data structure choice.
The numbers that set the architecture
The corpus is on the order of four hundred billion documents. Query volume is around eight and a half billion searches per day, roughly one hundred thousand per second on average, with peaks a few times that.
Four hundred billion documents times a thousand terms each is four hundred trillion postings. That number, and the memory it implies, sets the shard count.
A typical indexed document contributes on the order of one thousand distinct terms after tokenization. Four hundred billion documents times a thousand terms is four hundred trillion postings, where a posting is one entry saying "this term appears in this document." Uncompressed, a document identifier alone needs five bytes at that corpus size, so the raw index is petabytes before you store anything about the occurrence. Compressed to roughly one and a half bytes per posting, which is achievable and we will see how, the identifier and frequency index lands around six hundred terabytes. Add positions, needed for phrase queries and proximity scoring, and it roughly triples.
That has to live in memory, because the budget forbids disk. Take the identifier and frequency index, the part every query scans, as the thing that sets the machine count. If a serving machine dedicates two hundred and fifty six gigabytes of RAM to it, one complete copy needs on the order of two thousand machines. Positional data does not change that number, because it is held in a separate co-located tier and consulted only for the small set of candidates where phrase or proximity scoring actually needs it, rather than being decoded for every posting scanned. Two thousand is therefore the natural fanout of a query, and each machine holds about two hundred million documents. Then multiply by replication, because one copy cannot absorb a hundred thousand queries per second, let alone survive a machine failure. The fleet is many complete replicas of that two thousand machine set, spread across data centers, each able to answer any query independently.
The arithmetic has already decided several things. The index must be sharded. It must be in memory. Compression is what makes the machine count affordable. And a query has to touch about two thousand machines, which is the fact that will come back to hurt us.
The inverted index, and why the obvious index is wrong
The natural way to store documents is a forward index: document identifier maps to the terms in that document. It is the shape documents arrive in, and it is exactly wrong for search.
A forward index answers "what is in this document." A query asks the opposite question, so the index is inverted to answer "which documents contain this term."
A query does not ask what is in document 8,412,993. It asks which documents contain "distributed" and "consensus." Answering that from a forward index means scanning every document, the linear cost the budget forbids. So you invert it. The inverted index maps each term to a posting list, the sorted list of documents containing it. A single term query becomes a dictionary lookup and one list read. A two term query becomes two lookups and an intersection of sorted lists.
The structure has two parts. The lexicon maps a term string to metadata about its posting list: how many documents contain it, and where the list lives. It is small relative to the postings, tens of millions of distinct terms rather than hundreds of billions of entries, and it stays fully in memory in a compact form such as a finite state transducer or a front coded sorted array. The postings are the bulk. Both are built offline, so the serving path never sorts, never merges, and never builds anything. It reads.
The forward index does not disappear. Snippet generation needs document text, so a separate document store, sharded the same way, holds processed content. It is read only for the handful of documents that survive ranking, never for candidates.
What a posting list actually contains
A posting list is not just document identifiers, and the extra content is what makes ranking possible without reading documents.
Each posting carries the document identifier, the term frequency, and the position and field context of each occurrence, which is everything early scoring needs.
Each posting carries the document identifier, the number of occurrences, and for each occurrence a position plus context about where it happened. Position is what makes phrase search possible: "machine learning" as a quoted phrase requires documents where the position of "learning" is exactly one greater than that of "machine." The context bits encode whether the occurrence was in the title, a heading, the URL, anchor text, or the body, along with a coarse emphasis marker. The original Google paper described exactly this, packing a hit into two bytes with bits for capitalization, font size, and position, and splitting hits into fancy hits for titles, anchors, and URLs versus plain hits for body text.
The packing matters beyond space. Because occurrence context lives in the posting, a leaf server can score a candidate without touching the document, distinguishing a title match from a body match using data already in the cache line it just read. That is the same move again: do it at index time so the serving path does not have to.
Anchor text deserves a specific mention because it is one of the ideas that made web search work. When page A links to page B with the text "distributed consensus," that text is indexed as if it belonged to page B. You get descriptions written by other people, often better than what a document says about itself, and you can index documents whose content you cannot parse at all.
Compression is the reason this fits in memory
At four hundred trillion postings, the difference between four bytes and one and a half bytes per posting is the difference between five thousand machines and two thousand for a single index copy. Compression is a first class architectural concern, not a storage detail.
Sorting document identifiers turns large absolute numbers into small gaps, and small gaps compress into one or two bytes each.
Posting lists are sorted by document identifier, so instead of storing identifiers, store the gaps between consecutive ones. A list containing 1,004,215 then 1,004,318 then 1,004,902 becomes 1,004,215 then 103 then 584. The absolute values need twenty bits each. The gaps need seven and ten. This is delta encoding, and it works better the denser the list is, which is convenient because the longest lists are the ones worth compressing.
Then you need a variable length code for small integers. Variable byte encoding uses seven bits of each byte for data and the eighth as a continuation flag, so a gap under 128 costs one byte. Modern implementations usually prefer block based schemes such as PForDelta or SIMD friendly binary packing, which encode a block of 128 gaps at the bit width most of the block needs and store rare large outliers separately. These decode several times faster because they avoid an unpredictable branch on every value, and decode speed is what matters when you decode tens of millions of postings per query per machine. Elias-Fano is another option, close to the information theoretic bound while still supporting random access into the list, which matters for the skipping we are about to need.
One more trick has a large payoff. Document identifiers are assigned by the indexing pipeline, and you choose the assignment. Assign nearby identifiers to similar documents, for instance by sorting by URL so pages from one site get adjacent identifiers, and posting lists become clustered, gaps shrink, and the same encoder produces a meaningfully smaller index. That is a free reduction in machine count bought entirely at index time.
Splitting the index: by term or by document
Two thousand machines have to divide the index, and there are exactly two natural cuts. The choice is not close, but the losing option is the one that looks better on paper.
Term partitioning sends each query to a few machines but distributes load terribly. Document partitioning sends every query everywhere and is still the right answer.
Term partitioning assigns each term's entire posting list to one machine. A two term query touches exactly two machines, which sounds wonderful. It fails three ways. Load follows term popularity, which is Zipfian, so the machine holding a common term is hammered while the one holding rare technical vocabulary sits idle. Posting list lengths follow the same distribution, so shards are wildly unequal and a very common term's list may not fit on one machine. Worst, intersecting two terms means one machine ships its posting list to the other, which for common terms is tens of millions of postings crossing the network inside a thirty millisecond budget.
Document partitioning assigns each machine a subset of documents and builds a complete, self contained inverted index over just those documents. Every query goes to every shard, which does the full retrieval and ranking job over its own two hundred million documents and returns its own top results. Load is even by construction because documents are assigned by hash, index sizes are even for the same reason, and no posting list crosses the network because every intersection is local. The cost is a fanout of two thousand instead of two. Every production web scale search system makes this trade and then spends serious engineering on the consequence.
Scatter and gather
With document partitioning, the query flow is a tree, and the aggregation logic is where correctness gets subtle.
The root broadcasts one query to every leaf, each leaf returns only its local top results, and the root merges a few tens of thousands of candidates rather than billions.
A front end runs query understanding and hands a structured query to a root server. The root broadcasts to every leaf shard, in practice through one or two intermediate levels so no single machine manages two thousand outbound RPCs. Each leaf runs retrieval and scoring against its own index and returns its local top k, where k is small, on the order of twenty to a hundred document identifiers with scores. Intermediates merge their children and pass up their own top k. The root merges what it receives, applies whatever global reranking it can afford, fetches titles and snippets for the survivors from the document servers, and returns the page.
The volume reduction is the point. Two thousand leaves returning fifty results each gives the root one hundred thousand candidates, a trivial merge. If leaves returned every boolean match instead, the root would receive tens of millions and the network would be the bottleneck. This works because top k merging is decomposable: if a document's score depends only on that document and the query, the global top ten is guaranteed to lie inside the union of the per shard top tens. There is a condition hiding in that sentence. Scores from different shards have to be on the same scale, and the usual relevance weightings depend on corpus wide term statistics such as document frequency, which a shard can only see locally. So those statistics are computed globally at index time and distributed to every shard, rather than each shard computing its own. A shard scoring against its own local statistics would produce numbers that are not comparable, and the merge would quietly return the wrong ten documents. That guarantee, once it holds, licenses the architecture and also constrains ranking. Any signal that depends on other documents in the result set, such as diversity or cross shard deduplication, cannot be applied at the leaf and has to wait for the root, where the candidates finally meet.
Query understanding happens before retrieval
Before anything touches the index, the raw string becomes a structured query. This stage has an outsized effect on quality relative to how little budget it gets.
The raw string is normalized, corrected, segmented, and expanded into a structured query, and each step can change the result set completely.
Tokenization and normalization split the string, fold case, handle punctuation by context, and deal with scripts that have no whitespace word boundaries. Spelling correction runs against a model built from query logs, since the best evidence that "recieve" means "receive" is that millions of people typed the first and immediately typed the second. Segmentation decides "new york times" is one entity, not three words. Expansion adds synonyms and morphological variants, so "running shoes" can also match "run" or "sneakers," with expansion terms weighted below the originals so they do not overwhelm exact matches.
Intent classification decides what kind of answer the query wants. Navigational queries need a different result shape than informational ones, local intent triggers a geography dependent path, and some queries route to separate verticals so the final page is assembled from several backends.
Learned models live here too. Google's public disclosures describe RankBrain, introduced in 2015 for handling never before seen queries, and BERT based language understanding rolled out in 2019, which they said affected roughly one in ten searches in English in the United States by better modeling prepositions and word order. The architectural detail that matters is that these models are expensive, so they sit here at a fanout of one, before the broadcast, rather than at the leaves where their cost would be multiplied by two thousand.
You cannot afford to read the whole posting list
Inside a leaf, the naive algorithm intersects the posting lists for all query terms and scores every survivor. For rare terms that is fine. For a common word, the posting list on a single two hundred million document shard can hold tens of millions of entries, and scoring all of them does not fit.
Skip pointers let the intersection jump over regions that cannot match, and score bounds let the scorer skip documents that cannot reach the current top k threshold.
Two families of technique make this tractable. The first is skipping. Posting lists carry skip pointers, a sparse auxiliary structure that lets a reader jump forward to approximately a target identifier without decoding everything in between. Intersecting a rare term with a common one, you drive from the rare list and use skip pointers to advance the common one, so cost becomes proportional to the shorter list rather than the longer one. Always driving the intersection from the shortest list is the single most important implementation detail in a boolean retriever.
The second family is dynamic pruning, and WAND is the canonical algorithm. If you already have k candidates and the lowest scored 4.7, then any document whose maximum achievable score is below 4.7 cannot enter the top k and never needs scoring. To exploit that, the index stores an upper bound on each term's contribution. During evaluation you keep a running threshold and use those bounds to decide cheaply whether a candidate could beat it. Block-max WAND stores bounds per block of the posting list rather than per list, making them much tighter and letting the algorithm skip whole blocks. In practice these cut fully scored documents by one or two orders of magnitude with no change to the returned top k, which makes them exact rather than approximate. That distinction matters. You can turn them on without a quality review.
Ranking is a cascade, not a function
There is a tempting model where ranking is one scoring function applied to every match. At this scale that is not just wrong, it is impossible. Ranking is a funnel, and each stage earns the right to spend more compute per document by having fewer documents.
Each stage cuts the candidate count by orders of magnitude and spends orders of magnitude more compute per document, so no single stage dominates the budget.
The first stage is retrieval, the boolean and pruned scan above. It runs against the whole shard at nanoseconds per document and produces candidates. The second is a cheap ranker, a linear or tree based model over features already present in the posting and document metadata: term frequencies, field matches, proximity, quality priors such as PageRank, language, freshness. It costs a few hundred nanoseconds per document and reduces tens of thousands of candidates to a few hundred with high recall of the genuinely good ones. Twenty thousand candidates on one shard at two hundred nanoseconds each is about four milliseconds, which is the sort of number that has to be true for the stage to exist at all.
The third stage holds the expensive machinery, running on hundreds of documents rather than millions. Learned ranking models operate over rich features, and transformer based relevance models can afford a cross attention pass over the query and the specific passage that matched. Per document that pass is enormously more expensive than anything earlier, but it runs once per query rather than once per shard, and the few hundred candidates go through as a single batch on accelerator hardware, which is what keeps the stage inside a few milliseconds instead of a few hundred. Google's public description of passage ranking, scoring individual passages within a long document rather than the document as a whole, belongs here. It may sit at the leaf, an intermediate, or the root depending on which features it needs.
The final stage is at the root and concerns the result set rather than individual documents: deduplicating near identical pages, enforcing diversity so you do not get ten results from one site, blending verticals, applying policy filters, and personalizing lightly on location and language. The cascade is a compute allocation strategy. No stage dominates the budget, because candidate count falls about as fast as per document cost rises, and quality lands close to running the expensive model on everything at a fraction of the price.
Three caches, at three different layers
Query traffic is Zipfian the way term frequency is, so caching helps a great deal. The right answer caches at more than one layer, because the layers have different hit patterns.
A result cache serves repeated queries outright, a posting list cache serves repeated terms across different queries, and a document cache serves snippets.
The result cache sits at the front and maps a normalized query plus its context, meaning language, country, and personalization bucket, to a rendered result set. A hit skips the entire backend. Because a small set of queries repeats constantly, this absorbs a substantial share of traffic, commonly reported in the thirty to fifty percent range for web search workloads. Its weakness is that the tail of unique queries is enormous and a large fraction of daily queries have never been seen before. Entries also need short time to live values, because a cached result for a news query goes stale in minutes.
The posting list cache sits at the leaf and holds decompressed posting list blocks for hot terms. Its hit pattern is complementary: two completely different queries sharing one common term both benefit. Since term frequency is far more skewed than query frequency, this cache gets high hit rates even on queries the result cache has never seen. The document cache holds processed content for snippet generation, a surprisingly expensive step that has to find and highlight the passage justifying the result.
The tail is the system
Here is the failure mode that defines high fanout architectures, and it is not intuitive until you see the arithmetic.
With a fanout of two thousand, a leaf p99 of ten milliseconds means essentially every query waits on a straggler. The root cannot afford to wait for everyone.
Suppose a leaf responds within ten milliseconds ninety nine percent of the time. That is a good leaf. Now broadcast to two thousand of them and wait for all responses. The probability that every leaf comes back within ten milliseconds is 0.99 raised to the two thousandth power, about two in a billion.
At a fanout of two thousand, a one percent tail is not an outlier, it is every single query.
If the root waits for everyone, the p50 of the whole system is roughly the p99.97 of a single leaf. Your median user experiences your worst case. Jeff Dean and Luiz Barroso made this point precisely in "The Tail at Scale": with a hundred servers and a one percent chance of a one second response, sixty three percent of user requests exceed one second. Fanout does not average the tail out, it amplifies it.
The leaf tail comes from ordinary, unavoidable causes: a garbage collection pause, a background compaction, a noisy neighbor on the host, a kernel scheduling hiccup, a queue that briefly built up behind an expensive query. You cannot eliminate them, so the architecture has to tolerate them.
The mitigations are well established. The root sets a deadline and returns once it has heard from, say, ninety nine percent of leaves, accepting that a few shards contributed nothing. Because shards are random subsets of documents, missing one out of two thousand degrades recall by a fraction of a percent and is almost never visible, a remarkable trade for cutting p99 by an order of magnitude. Hedged requests send a duplicate to a second replica if the first has not answered within, for example, the p95 latency, and take whichever returns first, costing a few percent extra load. Tied requests refine that: send to two replicas immediately and have each cancel the other as soon as it starts executing. Below all of it sits hygiene, including micro-partitioning shards so a slow machine's load redistributes quickly, and putting a persistently slow replica into probation until it recovers.
A second, sharper failure mode bites during deploys. A new index version is a new set of files with a completely cold posting list cache. Shift traffic to it all at once and every leaf takes cache misses on every term simultaneously, latency spikes fleet wide, the root's deadline starts dropping large numbers of shards, and result quality visibly degrades. The fix is to warm the new index with shadow traffic before it serves anything real, then shift gradually so no large fraction of the fleet is ever cold at once. This shape, where a correlated cache invalidation converts a healthy system into an overloaded one, is not specific to search.
Keeping the index fresh
A fully rebuilt index is a clean artifact but a slow one. If a rebuild takes hours, a new document can be unfindable for hours, which is unacceptable for news, sports, and anything else people search for while it is happening.
A large, slowly rebuilt base index is queried alongside a small, constantly updated real-time index, and the results are merged at query time.
The standard answer is a two tier index. A large base index is built by the batch pipeline on a slow cadence. Alongside it sits a small real-time index, held in memory, receiving new and updated documents continuously. Every query goes to both and the leaf merges the two result sets. The real-time tier is small enough to be less compressed and more mutable, and periodically its contents fold into the base index during the next build. Deletions are handled by a separate deleted document bitmap consulted at query time, because physically removing a posting from a compressed list means rewriting it, which you would rather do during the merge.
Google's public work describes exactly this evolution. The original architecture rebuilt the index in large batch passes. Percolator, published in 2010, replaced the batch pipeline with incremental processing built on transactions and observers over Bigtable, and the paper reports that it halved the average age of a document in Google search results. The Caffeine indexing system that shipped that year was the production result, updating the index incrementally as documents were crawled rather than rebuilding layers wholesale.
Crawl scheduling completes the picture, because freshness is decided before indexing runs. Recrawl frequency is estimated per URL from observed change rates and importance, so a news homepage may be fetched every few minutes and a static reference page every few weeks. Spending crawl capacity where change actually happens is what makes minute level freshness affordable.
The trade-offs
Every choice bought something and cost something, and naming both sides is the difference between understanding the design and reciting it.
Document partitioning bought even load and local intersections, and cost a fanout of two thousand plus all the tail latency work that follows. Serving from memory bought the latency budget and cost a machine count driven entirely by index size, which is why compression became architectural. Aggressive compression bought that machine count and cost decode CPU on every query, which is why codecs that decode fast beat codecs that compress best. Dynamic pruning bought an order of magnitude fewer scored documents at no quality cost, but constrains scoring to functions where per term upper bounds are computable. The ranking cascade bought expensive model quality at cheap model cost, and cost a recall ceiling, since a document the cheap stage discards can never be recovered later. Deadline based aggregation bought a controlled p99 and cost a small amount of recall. Two tier indexing bought minute level freshness and cost a merge on every query plus two index formats to operate.
The patterns that transfer
Strip away the search vocabulary and these decisions show up constantly elsewhere.
Four moves carry over to most high fanout systems: invert the structure, shard by the unit you scan, cascade your compute, and never wait for the slowest replica.
Invert the data structure to match the question, not the data. The forward index is how documents arrive and the inverted index is how they are asked about, and building the second one offline is what makes the query cheap. Any time a read path is scanning to answer a question, ask what structure would answer it with a lookup, and whether you can build that structure at write time.
Shard by the unit you scan, not the unit you look up. Term partitioning optimizes the lookup and destroys the scan by skewing load and forcing data across the network. Document partitioning accepts broad fanout to keep every scan local and balanced. When the two conflict, the option that keeps work local usually wins, and you pay for it in fanout.
Structure expensive computation as a cascade. When you cannot afford your best model on every item, build a funnel of increasingly expensive stages where each cuts the candidate set by an order of magnitude. The cost is roughly that of the cheapest stage, the quality is close to the most expensive one, and the thing to watch is the recall ceiling each early stage imposes.
Never wait for the slowest replica. At any meaningful fanout the tail dominates, and the mitigations are always some combination of deadlines with partial results, hedged or tied duplicate requests, and taking slow replicas out of rotation. If your system fans out to more than about ten backends and you have not thought about this, your p99 is worse than you think.
Learn to see which of these levers your own bottleneck sits on, and the design stops being a memorized answer and starts being a method.
I teach system design this way, from first principles with real diagrams and the trade-offs that only surface in production, as an interactive course at systemdesign.academy. The foundation lessons are free and need no signup.
Read the free lessons: https://systemdesign.academy
Top comments (0)