Google Search System Design Interview: Serving a Trillion-Page Inverted Index in 200 Milliseconds
Google fields on the order of 100,000 searches every second, which works out to trillions of queries a year against an index of hundreds of billions of documents (roughly 400 billion documents as of 2020, per public reporting). The hard part is not storing that corpus. It is answering an arbitrary two-word query against all of it, ranking the results, and painting ten blue links in under a fifth of a second, every single time.
Google Search is two loosely coupled systems joined by a data structure. The offline half crawls the web, parses pages, and builds an inverted index that maps every term to the list of documents containing it, sharded across thousands of machines. The online half takes a user query, resolves it against every index shard in parallel, scores the candidate documents with PageRank plus hundreds of other signals, and merges the top results. The central tension is scale versus latency: the index is far too large for one machine, so it is partitioned by document into shards that are each replicated many times, and a query fans out to all shards at once in a scatter-gather pattern. Because a single slow shard would stall the whole query, the serving path leans on in-memory posting lists, tight per-stage timeouts, hedged requests, and partial-result tolerance. On top of that sits a snippet-generation stage, a heavy caching layer for popular queries, an autocomplete service that predicts the query before it is finished, and an incremental indexing pipeline that keeps fresh pages searchable within seconds.
Asked at: Asked at Google, Microsoft (Bing), Amazon, Meta, and most large product companies, usually as a staff or senior level design round. It also shows up in scaled-down forms such as design a search autocomplete, design a document search service, or design an inverted index.
Why this question is asked
Interviewers like this problem because it forces a candidate to reason about the largest read-heavy system there is and to make an explicit trade between latency and completeness. It touches nearly every core topic: partitioning strategy, replication, fan-out and aggregation, tail latency, caching, batch versus incremental pipelines, and ranking as a distinct concern from retrieval. A strong candidate separates the offline indexing path from the online serving path early, chooses document partitioning over term partitioning and can defend it, and shows they understand that the 99th percentile latency of a fan-out query is governed by the slowest shard, not the average one.
Requirements
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
Functional requirements
- Accept a free-text query and return a ranked list of relevant web pages with title, URL, and a snippet.
- Crawl the public web continuously and discover new and updated pages.
- Build and maintain an inverted index mapping terms to the documents that contain them.
- Rank results by relevance using link-based signals (PageRank) plus content and query-understanding signals.
- Provide query autocomplete and spelling correction as the user types.
- Support phrase and multi-term queries, returning documents that match all or most terms.
- Keep fresh content searchable quickly, so breaking news appears within minutes not days.
- Paginate results and support filters such as time range, language, and region.
- Generate a query-dependent snippet that highlights why each result matched.
Non-functional requirements
- End-to-end query latency in the low hundreds of milliseconds at the tail, not just the median.
- Extremely high read throughput, on the order of 100,000 queries per second globally.
- High availability: search must degrade gracefully rather than return an error page.
- Freshness: newly crawled pages become searchable within seconds to minutes.
- Horizontal scalability of both the index size and the query rate on commodity hardware.
- Result quality and relevance, measured by human raters and click behavior, not just uptime.
- Cost efficiency, since serving trillions of queries against a huge index is dominated by machine and power cost.
Back-of-envelope scale estimates
Show your math. Pulling numbers from thin air signals you have not thought about the load.
Query rate
~100,000 queries/sec
Public reporting puts Google at several trillion searches per year. 5e12 / (365 * 86400) is about 158,000 queries per second averaged over the year, so a steady-state design target near 100,000 QPS with headroom for peaks is reasonable. Derived from published annual totals, treat as an estimate.
Index size (documents)
~400 billion documents
Widely reported figure for Google's serving index around 2020, drawn from trillions of URLs crawled but filtered down to what is worth serving. The crawl frontier is much larger than the served index. Estimate, not an official current number.
Raw index storage
~10s of petabytes
Derived: 400e9 documents at an average served/compressed footprint on the order of tens of kilobytes of postings and metadata per document lands in the tens of petabytes range. Order-of-magnitude estimate to justify heavy partitioning; real figures are not published.
Number of index shards
thousands
Derived: if each shard holds tens of millions of documents in memory for fast posting-list scans, 400e9 documents divided by ~5e7 per shard is on the order of 10,000 shards before replication. Exact count is not public.
Machines in the serving fleet
tens of thousands
Derived: thousands of shards, each replicated many times for both throughput and fault tolerance, plus doc servers, mixers, cache, and autocomplete tiers, pushes the serving fleet into the tens of thousands of machines. Order-of-magnitude estimate.
Per-query latency budget
< 200 ms at the tail
Google has publicly targeted sub-quarter-second responses. That budget is split across query rewriting, the scatter-gather over index shards, snippet generation on doc servers, and network hops, which is why each internal stage gets a tight timeout. Target/estimate.
High-level architecture
Split the system into an offline path and an online path. Offline, a distributed crawler starts from a seed set and a frontier of known URLs, fetches pages while respecting robots rules and politeness delays, and stores raw content in a repository. An indexing pipeline parses each page, extracts terms and links, deduplicates near-identical content, and produces two structures: a forward index (document to its terms) and the inverted index (term to the sorted list of documents containing it, with positions and per-term metadata). The inverted index is partitioned by document into shards, so any single document lives in exactly one shard, and each shard is replicated. Link data is fed into PageRank and other graph computations that produce query-independent quality scores baked into the index. Online, a user query hits a front end that does query understanding: spelling correction, tokenization, synonym expansion, and intent signals. The rewritten query goes to a root or mixer node that scatters it to a replica of every index shard in parallel. Each index server scans its posting lists, finds documents matching the terms, applies a first-pass score, and returns its local top-k document IDs with scores. The mixer gathers these partial lists, merges them into a global top-k, and then asks the document servers to fetch titles, URLs, and to generate query-specific snippets for just those winners. A final ranking pass reorders using the heavier signals, results are assembled, and the page is returned. A results cache short-circuits popular queries, and a separate autocomplete service answers keystroke-by-keystroke as the user types.
In a real interview, sketch this on the whiteboard before diving into any single box.
Core components
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
Crawler (fetch and frontier)
A distributed fleet that pulls URLs from a prioritized frontier, fetches pages, and honors robots.txt and per-host politeness limits. It discovers new links from fetched pages, schedules recrawls based on how often a page changes, and stores raw HTML in a content repository for the indexer. Priority and freshness scheduling decide what gets crawled next out of a frontier far larger than the served index.
Indexing pipeline
Takes raw pages and produces the forward and inverted indexes. It parses and tokenizes content, records term positions for phrase matching, deduplicates near-duplicate pages, and merges new documents into the shard structure. Historically this was a batch MapReduce rebuild; the Caffeine generation moved to incremental indexing so a single new page can be added without rebuilding the whole index.
Inverted index shards (index servers)
The heart of retrieval. The index is partitioned by document into thousands of shards, each holding the posting lists for its slice of the corpus, kept in memory to avoid disk seeks. Each shard is replicated many times so that read throughput scales and any single machine can fail without losing coverage. An index server scans posting lists, intersects them across query terms, and returns a local top-k.
Mixer / root aggregator
The scatter-gather coordinator. It fans the query out to one replica of every shard, collects the per-shard partial results, and merges them into a single global ranked list. It enforces per-shard timeouts, can issue hedged (duplicate) requests to a second replica when one is slow, and returns partial results rather than stalling on a lagging shard.
Document servers and snippet generation
Once the mixer has the winning document IDs, doc servers fetch the stored document, its title and URL, and generate a query-dependent snippet by locating the matching terms in context. This is a second fan-out but only over the handful of results that will actually be shown, so it is cheap relative to the index scan.
Ranking system
A layered set of signals applied at different stages. Query-independent quality (PageRank and spam scores) is precomputed into the index; a fast first-pass score runs on the index servers; heavier models such as RankBrain, BERT-based neural matching, and freshness boosts reorder the small candidate set at the top. Ranking is deliberately separate from retrieval so the expensive models only see a few hundred candidates.
Caching and autocomplete tiers
A results cache stores fully rendered result sets for popular and repeated queries, absorbing a large fraction of traffic before it ever reaches the index. A separate autocomplete service serves query predictions from a prefix structure (such as a trie of popular queries with frequency weights) so suggestions appear within tens of milliseconds as the user types.
Data model
Pick the right store per table. Justify each choice with the access pattern, not by reflex.
documentsdoc_idurlcontent_hashlast_crawled_atpagerank_scoreThe canonical record for each served page. doc_id is an internal integer used everywhere downstream so posting lists store compact IDs, not URLs. content_hash drives deduplication; pagerank_score is a query-independent quality signal precomputed offline.
inverted_index (postings)termshard_idposting_listdoc_frequencypositionsMaps a term to the sorted list of doc_ids that contain it, within one shard. posting_list is delta-encoded and compressed; positions support phrase queries; doc_frequency feeds relevance scoring. Partitioned by document, so each shard holds full postings for its own documents only.
forward_indexdoc_idterm_idsterm_positionsfield_weightsThe inverse mapping, document to its terms, used during index build, snippet generation, and re-scoring. field_weights distinguish a term appearing in a title from one in body text.
link_graphfrom_doc_idto_doc_idanchor_textlink_weightEdges of the web graph. Feeds the PageRank computation and provides anchor text, which is often a better description of the target page than the page's own content. Rebuilt or updated as the crawl progresses.
crawl_frontierurlprioritynext_crawl_athostlast_statusThe scheduling queue of URLs to fetch. priority and next_crawl_at implement freshness-aware recrawl; host is used to enforce politeness so one domain is not hammered. Far larger than the served corpus.
autocomplete_termsprefixsuggestionfrequencyregiontrend_scoreBacks the type-ahead service. Popular completed queries indexed by prefix with frequency and recency weights so the top few suggestions per prefix can be served from memory in a single lookup.
Deep dives
These are the conversations the interviewer is steering you toward. Practice each one until you can talk through it without notes.
Building the inverted index and why it beats scanning
A naive search scans every document for the query terms, which is impossible at web scale. The inverted index flips that: for each term you precompute the sorted list of document IDs that contain it, called a posting list. Answering a two-term query then becomes intersecting two sorted lists, which is linear in their length and needs no document scan. The index is built by the pipeline in stages: parse each page into tokens, emit (term, doc_id, position) tuples, then group and sort by term so all postings for a term end up together. This grouping is the classic use case for MapReduce, where the map emits term-keyed records and the reduce concatenates them into posting lists. Postings are stored delta-encoded (store gaps between doc_ids rather than the IDs themselves) and compressed, which shrinks them enough to keep hot shards in memory. Positions are stored alongside so phrase queries like "system design" can verify the two terms are actually adjacent, not just present somewhere on the page.
Document partitioning versus term partitioning
There are two ways to shard an inverted index and the choice drives everything. Term partitioning puts all postings for a given term on one machine, so a query touches only the machines holding its terms. It sounds efficient but it concentrates hot terms on single machines, makes multi-term intersections require shipping long posting lists between nodes, and turns adding one new document into an update that touches many shards. Document partitioning instead assigns each document to exactly one shard and stores that shard's full postings locally. The cost is that every query must fan out to every shard, since a match could be anywhere. Google and most large engines choose document partitioning because it load-balances naturally, keeps intersections local to each shard, and makes incremental updates trivial: a new page lands in one shard and nowhere else. The fan-out cost is real but it is solved with parallelism and replication rather than avoided.
Scatter-gather query serving and the tail latency problem
With document partitioning, a query is scattered to a replica of every shard, each shard computes its local top-k in parallel, and a mixer gathers and merges the partial results. The catch is that the query is only as fast as the slowest shard that responds. If you touch 1,000 shards and each has a 99.9th percentile latency of 10 ms, the probability that at least one of the 1,000 is slow on any given query is high, so the tail of the whole query is dominated by stragglers. The defenses are layered: keep posting lists in memory so the common case is fast, set a tight per-shard timeout and accept partial results if a shard misses it, and use hedged requests where the mixer sends the same shard request to a second replica after a short delay and takes whichever answers first. Replication is what makes hedging cheap, because there are always several replicas of each shard to choose from. This is the single most important insight the interviewer is listening for.
Ranking as a separate concern from retrieval
Retrieval finds documents that match the query. Ranking decides their order, and it is deliberately staged so the expensive work runs on the fewest documents. Query-independent signals like PageRank and spam scores are precomputed offline and baked into the index, so they cost nothing at query time. Index servers apply a cheap first-pass score to pick each shard's local top-k, which cuts billions of candidates down to a few thousand. Only then do the heavy models run: RankBrain and neural matching interpret the query's intent even when the exact words are absent, BERT-style models read word order and prepositions to disambiguate meaning, and freshness systems boost recent content for queries that deserve it. Because these models only see a few hundred candidates at the top, their cost is bounded. PageRank itself models the web as a graph and computes the probability that a random surfer lands on each page, so a link from a high-quality page counts for more than one from an obscure page, and anchor text often describes the target better than the target describes itself.
Crawling, freshness, and incremental indexing
The crawler works from a frontier of URLs ordered by priority and by when each page is next due for a recrawl. Pages that change often, like a news homepage, are recrawled far more frequently than a static archive page, which is a freshness-aware scheduling problem, not a simple queue. Politeness matters: the crawler caps how fast it hits any one host so it does not act like a denial-of-service attack, and it obeys robots.txt. The bigger architectural shift was in indexing. The original design rebuilt the entire index in large batch passes, which meant a new page could wait a long time to become searchable. The Caffeine generation moved to incremental indexing, where a freshly crawled page is analyzed and merged into the index on its own, so it becomes searchable within seconds instead of waiting for the next full rebuild. This is what lets breaking news show up almost immediately while the bulk of the index stays stable.
Caching and the query distribution
Search traffic is extremely skewed. A small set of popular queries accounts for a large share of volume, while the long tail is enormous and mostly unique. That shape makes caching very effective at the head and useless at the tail. A results cache stores the fully assembled result page for hot queries, keyed by the normalized query plus locale and personalization bucket, so a large fraction of traffic is answered without ever touching the index. The tricky part is invalidation: cached results must expire or refresh as the index changes and as freshness-sensitive queries demand new content, so time-to-live is tuned per query class rather than set globally. Below the results cache, index servers benefit from posting-list locality since common terms are read constantly. The long tail of unique queries still has to pay the full scatter-gather cost, which is another reason the base serving path must be fast on its own and cannot lean on caching to hide latency.
Autocomplete as its own low-latency system
Autocomplete is a separate service with a much tighter latency budget than search itself, because it fires on nearly every keystroke and has to feel instant, on the order of tens of milliseconds. It is essentially a prefix-lookup problem: given the characters typed so far, return the most likely completions. A common structure is a trie or a compact prefix index of popular past queries, each weighted by frequency and recency, with the top few completions for each prefix precomputed so a keystroke is a single fast lookup rather than a ranked search. It also blends in personalization, regional trends, and spelling correction, and it has to suppress unsafe or policy-violating suggestions. Because it runs so often, it is aggressively cached and served from memory close to the user, and it is engineered to fail open: if autocomplete is slow or down, the user can still type the full query and search normally.
Trade-offs to discuss
Every senior interviewer expects you to surface at least 3 of these. Pick the decisions, state the alternatives, and justify your choice.
Document partitioning versus term partitioning
Document partitioning forces every query to fan out to all shards, which is more network work per query. It wins anyway because it balances load evenly, keeps term intersections local, and lets a new document update exactly one shard. Term partitioning concentrates hot terms and makes updates and multi-term joins painful.
In-memory index versus disk-backed index
Keeping posting lists in RAM removes disk seek latency and is what makes sub-200 ms fan-out feasible, at the cost of far more machines and memory. At Google's read rate the latency and throughput gain justifies the hardware; a disk-backed index would be cheaper per document but could not hit the tail latency target.
Incremental indexing versus batch rebuild
Batch MapReduce rebuilds are simpler and produce a clean, consistent index, but they delay freshness by the length of the rebuild cycle. Incremental indexing adds complexity around merging and consistency but makes new pages searchable in seconds, which matters for news and trending queries.
Hedged requests versus waiting for every shard
Sending duplicate requests to a second replica after a short delay cuts tail latency because you take the first response, but it adds load, sometimes doubling work for the slow fraction of queries. That extra load is a good trade because tail latency, not average, defines the user experience.
Partial results versus perfect recall
If a shard misses its timeout, the mixer returns without it rather than stalling the whole query. This sacrifices a sliver of recall on rare occasions in exchange for bounded latency and availability. For web search, a slightly incomplete result in 150 ms beats a complete result in 2 seconds.
Separating retrieval from ranking
Running heavy ranking models on every candidate would be far too slow, so cheap scoring narrows billions to a few hundred and the expensive models only reorder the top. This costs some relevance precision on the boundary between stages, but it is the only way to afford neural ranking at query time.
How Google Search actually does it
Google's public record spans decades. The original 1998 Anatomy of a Large-Scale Hypertextual Web Search Engine paper by Brin and Page described the crawler, the repository, the forward and inverted indexes stored in barrels, the lexicon, and PageRank. The 2003 Web Search for a Planet paper by Barroso, Dean, and Holzle described the serving side: queries handled by index servers that hold document-partitioned shards and return doc IDs, followed by document servers that produce snippets, all on replicated commodity hardware where replication buys both throughput and fault tolerance. The 2010 Caffeine announcement documented the move from periodic batch rebuilds to continuous incremental indexing for fresher results. On the ranking side, Google publicly documents named systems including PageRank, RankBrain, BERT-based neural matching, passage ranking, MUM, and freshness systems in its ranking systems guide. Public reporting and Google statements put current volume in the trillions of searches per year against an index measured in the hundreds of billions of documents.
Sources
- Google research: Web Search for a Planet, the Google Cluster Architecture (Barroso, Dean, Holzle)
- Google Search Central: Our new search index, Caffeine
- Google: A guide to Google Search ranking systems
- Google: How Search Works (crawling, indexing, ranking)
- Search Engine Land: Google now sees more than 5 trillion searches per year
Lessons to study before this interview
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.
Related system design interview questions
Practice these next. They lean on the same core building blocks as Google Search.