Google Search

Assume 50B indexed documents, 120B discovered URL records, 2T directed links in the link graph, an average compressed document representation of 20 KB, an average inverted-index contribution of 20 KB per document including terms, positions, fields, skip blocks, and metadata, and 3 replicas for online serving.

Assume 100K average query QPS globally, 500K peak query QPS, 30 percent of queries served from full-result cache, and 2,000 primary document-sharded index partitions. Each primary shard holds about 25M documents. Query fan-out contacts one healthy replica of each required shard group, and each shard returns a local top 100 to top 1,000 candidate set.

• Document store: 50B indexed documents times 20 KB compressed representation is about 1,000,000,000,000 KB, or about 1 PB logical.
• Inverted index: using another 20 KB per document for compressed postings, positions, field annotations, term statistics, and skip data gives about 1 PB logical.
• Replication: 1 PB document store plus 1 PB inverted index is 2 PB before replicas. With 3 serving replicas, link graph storage, crawl metadata, index generations, and compaction headroom, plan for roughly 6 to 9 PB.
• Shards: 50B documents divided by 2,000 primary shards gives 25M documents per primary shard. With 3 replicas, the serving fleet runs about 6,000 shard copies.
• Query load: 500K peak QPS with 30 percent full-result cache hits leaves about 350K QPS that need query planning and shard fan-out.
• Per-shard load: if every uncached query fans out to all 2,000 primary shard groups, the aggregate shard request rate is enormous, so production systems use tiering, early termination, query routing, replicas, and cached posting blocks. In interviews, call out that each shard does bounded local work and returns only top candidates.
• Crawl rate: 2B fetches per day divided by 86,400 seconds is about 23K fetches per second. Politeness spreads this across hosts so a single host may receive only one request every few seconds even while the global fleet is large.
• Latency: a 200ms p95 page budget might allocate 10ms to query parsing and cache lookup, 35ms to shard fan-out waiting, 25ms to merge candidates, 40ms to ranking and feature fetches, 30ms to snippets and rendering, and the rest to network and safety margin.

• url_frontier.host_key, next_fetch_at supports per-host politeness queues and due-for-fetch scans.
• url_frontier.url_key deduplicates discovered URLs before they enter the frontier.
• documents.doc_id is the stable key stored in posting lists and used by serving shards.
• documents.content_hash and documents.simhash support exact and near-duplicate clustering.
• link_edges.target_doc_id supports link analysis jobs that aggregate incoming authority.
• index_generations.generation_id, shard_id lets serving clusters discover the exact segment set to load.

URLs become documents only after canonicalization, fetching, and duplicate handling. Many discovered URLs can map to one canonical document. Documents emit outgoing link edges, and link analysis writes authority features back into document or ranking-feature stores. Index generations reference immutable segment files, and online search clusters load only validated generations.

Use Bigtable, HBase, Cassandra, DynamoDB, or Spanner-like storage for crawl state and document metadata, partitioned by URL hash, host key, or document id depending on access pattern. Store large compressed bodies and index segments in distributed object storage or a Colossus-like file system. The inverted index is best represented as immutable segment files plus compact serving metadata, not as row-per-posting records in a transactional database.

The crawler starts from seeds such as sitemaps, known high-quality domains, feeds, and links extracted from fetched pages. Every discovered URL is normalized, stripped of obvious tracking noise, hashed, and checked against a distributed seen set before it enters the frontier. This prevents infinite loops over calendar pages, faceted navigation, and duplicate URL variants.

The frontier is not a simple FIFO queue. It is closer to a distributed priority scheduler with per-host queues. It must honor robots.txt, crawl-delay directives where applicable, host health, DNS failures, and site-specific crawl budgets. Even if the global fleet can fetch tens of thousands of pages per second, one host may be limited to a request every few seconds.

Freshness is priority-driven. News homepages, popular documents, and pages with known frequent changes receive short recrawl intervals. Stable long-tail pages can wait days or weeks. The freshness model uses last-modified headers, ETags, historical change rates, PageRank-style importance, query demand, and publisher signals. The key tradeoff is that crawling more often improves freshness but increases cost and can harm external sites if politeness is weak.

Fetched HTML is messy. The processing pipeline must parse malformed documents, follow canonical tags, extract visible text, remove boilerplate, detect language, extract title and structured metadata, identify spam, compute content hashes, and cluster near-duplicates with fingerprints such as SimHash. It also extracts outgoing links and anchor text for graph analysis.

The inverted index maps each term to a posting list. A posting usually contains document id, term frequency, positions, field flags such as title or heading, and sometimes compact quality or payload data. Posting lists are sorted by document id, delta-encoded, block-compressed, and augmented with skip pointers so shards can intersect terms and jump over low-value regions quickly.

Index builders create immutable segments. New crawls first produce small delta segments, and background jobs merge them into larger optimized segments. Serving shards load a generation consisting of base segments plus deltas. This design avoids rewriting a petabyte-scale index for every new crawl while still allowing periodic full rebuilds to fix tokenizer, ranking-feature, or dedup logic.

The standard interview design shards by document, not by term. Each shard stores all terms for its subset of documents. A query is sent to every primary shard group or to a selected tier of shards, and each shard independently returns its local top K documents. The broker then merges the local candidates into a global ranking set.

Document sharding makes ranking easier because all features for a document partition are local, and every shard can run the same retrieval logic. It also avoids a single hot shard for very common terms. The cost is fan-out: every uncached query may touch many shard groups, so tail latency becomes the main serving challenge.

The broker controls that tail with replica selection, deadlines, hedged requests, shard health, and early termination. It can also use tiered indexes: search a high-quality or high-PageRank tier first, then expand to more shards if recall is insufficient. For rare or long-tail queries, the system may need broader fan-out; for navigational queries, caches or shortcuts can avoid it.

First-stage ranking usually combines lexical relevance with static document signals. Lexical relevance includes BM25-like term matching, phrase matches, field boosts for title or headings, anchor text matches, and freshness. Static signals include PageRank-style link authority, site quality, spam scores, language, locality, and historical engagement.

Link analysis is computed offline over the link graph. The graph can have tens of billions of nodes and trillions of edges, so PageRank-style jobs run in distributed batch systems and write compact authority features for serving. Anchor text is also valuable because other pages often describe a target better than the target describes itself.

Learned ranking runs in stages. Shards apply cheap retrieval and first-stage scoring to return candidates. A second-stage ranker uses richer features on hundreds or thousands of candidates. A final reranker may use neural or transformer-based models on a much smaller set. The design must bound model cost and have fallbacks to simpler ranking if feature stores or model servers are slow.

Search has a skewed query distribution. A large fraction of traffic is repeated navigational, celebrity, sports, weather, news, or product queries. Full result pages can be cached for short TTLs keyed by normalized query, locale, safety setting, and freshness class. Even a 30 percent cache hit ratio removes enormous fan-out load at peak.

Below full-result caching, serving shards cache term dictionaries, hot posting-list blocks, document features, and shard-local results for common query fragments. Ranking services cache static features such as link authority and site quality. Snippet stores cache titles and precomputed summaries. These caches must respect freshness and safety updates, so invalidation is often generation-based rather than per-document.

Latency budgets should be explicit. The API might spend 10ms on parsing and cache checks, the broker might wait 35ms for shards, merging might take 25ms, ranking and snippets might take 40 to 70ms, and the rest is network and rendering. If a shard misses its deadline, the broker should prefer slightly lower recall over blowing the entire page latency budget.

Index storage is versioned. Builders publish immutable segment files plus manifests that describe shard id, term statistics, checksums, document ranges, and compatibility. Serving clusters load a manifest, warm caches, run validation queries, and then gradually shift traffic to the new generation.

Periodic full rebuilds are necessary because changes in tokenization, deduplication, spam scoring, link analysis, or schema may require recomputing the entire index. Incremental updates are necessary because users expect fresh pages quickly. A practical design combines daily or weekly base builds with frequent delta segments for new or changed documents.

The online path never waits for a rebuild. If an incremental pipeline is delayed, users see a slightly older but still valid index. If a new generation is bad, serving can roll back to the previous manifest. This separation is what keeps a search engine available while the web crawler and index builder process petabytes of changing data.

Alternative one is term sharding, where each shard owns a subset of terms. It can reduce work for some rare terms but creates severe hot spots for common terms and makes document-level ranking features harder to combine.

Alternative two is a smaller vertical search engine such as product, code, or document search. It can use fewer shards, stronger structured filters, and simpler crawling, but the same inverted-index and ranking principles apply.

Alternative three is a purely neural retrieval system over embeddings. It can improve semantic matching, but it is not a replacement for web-scale lexical retrieval, freshness, exact phrase matching, and explainable filtering. A practical search engine often uses lexical retrieval first and neural reranking or hybrid retrieval later.

Do not build a web-scale search engine if the problem is only searching a small application database, a private document corpus, or a single website. Use a managed search service, a relational full-text index, Elasticsearch, OpenSearch, Solr, or a vector database depending on the corpus and query type. Web search is justified only when crawling, ranking, freshness, and global-scale serving are core product requirements.