The prompt, scoped
"Design Google Search" is "crawl the web, index it, and answer queries fast and well." We keep the spine: a crawler that discovers and fetches pages, an indexing pipeline that builds an inverted index, and a query path that retrieves and ranks results, plus typeahead. Out of scope, said up front: the real ranking ML, ads, personalization, and the knowledge graph. The hard parts are the index and the scatter-gather query.
Step 1
Requirements: functional and non-functional
The functional core:
- Crawl the web: discover, fetch, and re-fetch pages.
- Index: build an inverted index (term to the documents containing it).
- Query: return ranked results for a search, fast.
- Typeahead: suggest queries as the user types.
Out of scope (say it): the ranking model itself, ads, personalization, knowledge panels.
The non-functional shape:
Two facts drive it: the index is an enormous, mostly-static artifact that must be queried in milliseconds, and crawling/indexing is a continuous, asynchronous pipeline behind it. A result a few hours stale is fine; a slow or failed query is not.
Maps to S2 (requirements) and S1 (availability vs completeness on the query path).
Step 2
Estimation: the numbers that bound the design
| Quantity | Assumption | Result |
|---|---|---|
| Documents | ~billions of pages | the index is far too big for one machine |
| Index size | postings for every term | sharded across thousands of serving nodes |
| Queries | tens of thousands+/sec | read-heavy; must fan out and return in ms |
| Crawl | continuous, prioritized | re-crawl important / changing pages more often |
| The shape | one query touches every shard | scatter-gather is the query pattern |
The number that decides the architecture
The index does not fit on one machine, not close. So it is sharded by document across thousands of nodes, and a query scatters to all of them in parallel, each returning its best local matches, then a coordinator gathers and ranks. That single fact, "the index is too big, so fan out", shapes the whole serving path.
Maps to S2 (capacity estimation) and S4 (sharding the index).
Step 3
API: query and suggest
| Endpoint | Does | Notes |
|---|---|---|
GET /search?q= | ranked results | scatter-gather across index shards, then rank; returns top-K + snippets |
GET /suggest?prefix= | typeahead | a separate, very fast prefix service over popular queries |
| crawler (internal) | fetch + parse pages | fed by the URL frontier; emits documents to the indexer |
| indexer (internal) | build the inverted index | batch/stream pipeline writing index shards |
Only two public endpoints. The heavy machinery, crawling and indexing, is an internal pipeline that produces the artifact the query path reads.
Maps to S5 (API design): a tiny read surface over a huge prebuilt index. See the API cheat sheet.
Step 4
Data model and store choices
Document(doc_id PK, url, title, fetched_at, page_rank) InvertedIndex: term -> posting list [ (doc_id, positions, score), ... ] Frontier: priority queue of URLs to crawl (+ seen-set for dedup) LinkGraph: doc -> outlinks (feeds PageRank / authority) Suggest: trie of popular queries by frequency stores Inverted index .. huge, read-heavy, sharded BY DOCUMENT -> in-memory / SSD across many nodes Doc store ....... url, snippet, metadata -> distributed KV Frontier ........ priority queue + seen-set -> queue + a dedup store Suggest ......... prefix lookups -> in-memory trie service
Why document partitioning, not term partitioning
You can shard the index two ways. By term (each node owns some terms, holds the full posting list) means a multi-term query hits only a few nodes, but those posting lists are gigantic and create hot spots. By document (each node owns a slice of docs, with the full term dictionary for them) means every query scatters to every shard, but each shard does a small, balanced amount of work. Web search uses document partitioning: balanced load and easy parallelism beat fewer-nodes-per-query.
Maps to S3 (the index as the access-pattern-driven structure) and S4 (partitioning strategy). See the data-stores cheat sheet.
Step 5
High-level architecture
Two halves meeting at the index. The crawl + index pipeline (top) pulls URLs from the frontier, fetches pages from the web, and the indexer writes them into the document-partitioned index shards. The query path (bottom) takes a search to a coordinator that scatters to every shard and gathers the ranked results. The index is the artifact one side builds and the other side reads.
Maps to S7 (architectural styles) and S6 (pipelines, scatter-gather).
Step 6
Deep dive A: the crawler frontier
Crawling the web is a scheduling problem, not a fetching one. The frontier decides what to crawl next, how often, and how to do it without hammering any one site.
the frontier = a priority queue of URLs + a seen-set
priority
- important pages (high PageRank, news) re-crawled often
- the long tail crawled rarely
- new links discovered during a crawl are enqueued
politeness
- rate-limit per domain (robots.txt, crawl-delay)
- do not let 1000 crawlers hit one host at once
- partition the frontier by host so per-host limits are local
dedup
- a seen-set (e.g. a Bloom filter over URL hashes) avoids
re-crawling the same URL endlessly
- canonicalize URLs (strip fragments, normalize) before dedup
Why the frontier is the hard part
The naive crawler floods sites and loops forever on the same pages. The frontier turns crawling into a governed schedule: prioritize by importance and freshness, dedup with a seen-set, and enforce politeness per host. It is the scheduler that makes a planet-scale crawl both polite and productive.
Maps to S4 (partitioning by host) and S9 (politeness is rate-limiting; be a good citizen).
Step 6 · continued
Deep dive B: the inverted index and scatter-gather
The data structure that makes search possible, and the query pattern it forces. An inverted index maps each term to the list of documents that contain it.
inverted index "system" -> [doc3, doc9, doc42, ...] (posting list, with scores) "design" -> [doc9, doc42, doc88, ...] query "system design" -> INTERSECT the posting lists -> candidates document partitioning (web search) - shard N holds a slice of documents + the full term dict for them - a query goes to EVERY shard (scatter) - each shard intersects locally and returns its top-K - coordinator merges all shards' top-K (gather), re-ranks, returns scatter-gather with a TIMEOUT - a slow shard is dropped; serve from the rest - missing a few docs from one shard is acceptable; waiting is not
The senior point
Two moves score. First, document partitioning so every shard does a small, balanced amount of work and the query parallelises cleanly. Second, a strict timeout on the gather: a query is only as fast as its slowest shard, so you drop stragglers and serve a 99%-complete result in time rather than a perfect result too late. Completeness yields to latency, on purpose.
Maps to S4 (document partitioning) and S1 (latency vs completeness).
Step 6 · continued
Deep dive C: ranking and typeahead
Retrieval finds candidates; ranking orders them; typeahead is a separate fast path. Ranking is two phases so the expensive scoring only touches a few documents.
ranking (two phase)
1. RETRIEVAL (cheap, in the shard): intersect posting lists,
score by BM25 / TF-IDF, return each shard's top-K candidates
2. RE-RANK (expensive, in the coordinator): score the merged
candidates with richer signals (authority/PageRank, freshness,
query features) -> final top-10
=> cheap filter over billions, expensive scoring over hundreds
typeahead (separate service)
- a trie / prefix tree of popular queries, weighted by frequency
- prefix lookup returns the top completions in ms
- rebuilt periodically from query logs; it does not touch the index
Why two-phase ranking
You cannot run an expensive relevance model over billions of documents per query. So retrieval is a cheap, index-native filter that produces a few hundred candidates, and the costly re-ranking runs only on those. The same shape appears in feeds and recommendations: a fast recall step, then a slow precision step on the survivors.
Maps to S1 (simplicity vs capability: phase the work) and S4 (typeahead as a separate cache).
Step 7
Reliability & failure design
| If this fails… | Mode | What the user sees |
|---|---|---|
| An index shard (slow or down) | fail open | dropped from the gather by timeout; results 99% complete, still fast |
| A shard replica | degrade | another replica serves that document slice; no gap |
| Crawler / indexer | retry | async pipeline; a failed fetch or index job retries, freshness lags slightly |
| Frontier overload | shed | deprioritize low-value crawls; protect query serving capacity |
| Coordinator | degrade | stateless and replicated; another coordinator handles the query |
Query serving is built to degrade, not fail: shards are replicated, the gather drops stragglers on a timeout, and coordinators are stateless and replaceable. The crawl/index pipeline is asynchronous and retryable, so a failure there costs freshness, never availability. Everything is bounded with timeouts, and the scatter-gather timeout is the single most important reliability knob.
Maps to S9 (designing for failure): fail open on a shard, drop stragglers. See the resilience cheat sheet.
Step 7 · continued
Observability & operability
- SLI / SLO: query latency p99 under 200ms, and result completeness (the fraction of shards that answered before the timeout).
- Index freshness: the age of the index, crawl rate, and indexing lag. A naive design serves stale results and never measures it.
- Shard health: per-shard latency and timeout rate; a few slow shards quietly erode completeness.
- The three pillars: metrics for latency and completeness, traces across the scatter-gather, structured logs for slow queries.
- Alert on pain and freshness: page on query-latency burn, completeness drops, and crawl staleness, not raw CPU.
Maps to S10 (observability). See the observability cheat sheet.
Step 8
Trade-offs along the six core axes
| Axis (S1) | The call here | Why it is least-wrong |
|---|---|---|
| Latency vs completeness | timeout slow shards | a 99%-complete result in time beats a perfect one too late |
| Consistency vs availability | availability + eventual index | a slightly stale result is fine; the query must always answer |
| Space vs time | a huge precomputed index | spend storage to turn a search into milliseconds of lookups |
| Partitioning | by document, not term | balanced shard load and clean parallelism over fewer-nodes-per-query |
| Simplicity vs capability | two-phase ranking | cheap recall over billions, expensive precision over hundreds |
| Freshness vs cost | prioritized re-crawl | crawl important/changing pages often, the long tail rarely |
The whole design is one structure and one pattern: an inverted index too big for any machine, sharded by document, queried by scattering to every shard and gathering the best within a deadline. Build it with a governed crawl, rank it in two phases, and say that, and the boxes follow.
Maps to S1 (the six core trade-offs) and S12 (present and defend).
Use this in the cohort
- Slot: Week 6 worked design. The inverted index, scatter-gather, and two-phase ranking are reusable far beyond search.
- Run it live: walk steps 1 to 5, then ask "the index does not fit on one machine, now what?" and let the room derive document partitioning and scatter-gather.
- The one sentence: "an inverted index sharded by document, queried by scatter-gather with a deadline, fed by a governed crawler frontier, and ranked cheap-then-expensive."