Design a Web Search Engine

1Clarifying the requirements#

Never start drawing boxes. "Search engine" spans a 10,000-document site search to all of Google, and the sizing moves the architecture by orders of magnitude. Get the numbers before committing to anything.

Candidate: Are we indexing the open web, or searching inside one company's documents? Those are very different beasts. Site search for a million docs fits on one box. The open web does not. Interviewer: The open web. Think a general-purpose engine.

Candidate: Do we need full result pages with snippets and ranking, or just a list of matching URLs? Interviewer: Ranked results, ten per page, with a title and a text snippet.

Candidate: Freshness: is it fine if a page we crawl today shows up tomorrow, or do you want news-grade seconds-level freshness? This decides whether I batch-build the index or need a live update path. Interviewer: Minutes to hours for most pages is fine. Assume a separate fast path for news if you have time.

Candidate: Query features: just keyword matching, or typos, autocomplete, and personalization? Personalization in particular would blow up the caching story, so I want to scope it out if I can. Interviewer: Keyword with basic typo tolerance and autocomplete. Skip heavy personalization.

Candidate: Scale? Give me a rough corpus size and query volume, because the answer decides whether the index lives in RAM or on disk. Interviewer: Assume 40 billion pages in the index, and a few hundred thousand queries per second at peak.

What those five answers just told me:

• This is a RAM-and-fan-out problem, not a single-box problem.
• Freshness relaxed to minutes/hours means I can batch-build and compress hard.
• Personalization scoped out means the result cache stays sane (shared answers, not per-user).
• 40B pages plus hundreds of thousands of QPS is the interviewer handing me the thesis: the read side is fan-out-bound.

Functional requirements

• Crawl pages, follow links, respect robots.txt, re-crawl on a schedule.
• Parse and extract text, title, links, language.
• Build and maintain an inverted index (term to document postings).
• Serve ranked results for a multi-word query, with snippets.
• Autocomplete and basic spelling correction.

Non-functional requirements

• Query latency p99 under 200ms end to end. This is the headline SLO, and every read-path call answers to it.
• High read availability (99.99%). A crawl outage survives for hours. A query outage costs money and trust the moment it starts.
• Horizontal scale on both the index-build side and the serving side.
• Index freshness of minutes to hours, with a faster lane for news.
• The write path can be eventually consistent. The read path must be fast and deterministic enough to feel stable to a human.

2Back-of-the-envelope estimation#

Get real numbers on the table, because one of them dictates the whole architecture. Write it where the interviewer can see it.

Corpus and index size.

• 40B pages, about 8KB of usable text each after stripping markup: 40B x 8KB = 320TB of raw text.
• That text is compressed into blob storage and mostly not served live. It exists for snippet generation and re-indexing, not query time.
• The inverted index is what matters. Assume 2,000 unique terms per page after dedup and stemming: 40B x 2,000 = 80 trillion postings.
• A posting (doc id + position + a byte or two of metadata) compresses to roughly 1.5 bytes with delta encoding and variable-length coding.
• Index size: 80T x 1.5B is about 120TB, replicated 3x for availability and read throughput, so roughly 360TB to keep in memory or on fast SSD across the fleet.

Query load (the number that bites).

• Peak 300K QPS.
• The multiplier that scares people: each query fans out to every index shard.
• Split the index into 1,000 shards and one user query becomes 1,000 internal lookups.
• 300K x 1,000 = 300M internal shard reads per second. That is the number I circle on the whiteboard.

Crawl throughput.

• Keep 40B pages fresh on an average 2-week re-crawl: 40B / (14 x 86400) is about 33,000 pages fetched per second, sustained, with bursts higher.
• At 8KB text plus HTTP and markup overhead, that is a few hundred MB/s of fetch bandwidth, which is modest.
• The cost of crawling is not bytes. It is open connections, DNS lookups, and politeness bookkeeping per host.

Why I cannot just cut the fan-out.

• If I could change one thing to make this cheaper, it would be fan-out.
• I cannot cut it without breaking phrase queries, so I pay for it with RAM, caching, and two-phase scoring.
• More on exactly why in the sharding deep dive.

3Core APIs#

Keep the public surface tiny on purpose. That almost all the engineering hides behind three endpoints is itself the signal: the interesting work is internal, not in the API shape.

GET /search?q=distributed+consensus&page=0&n=10
200 OK
{
  "query": "distributed consensus",
  "corrected": null,
  "total_estimate": 4120000,
  "results": [
    {
      "url": "https://example.org/raft",
      "title": "In Search of an Understandable Consensus Algorithm",
      "snippet": "Raft is a consensus algorithm that is ...",
      "score": 0.87
    }
  ],
  "took_ms": 54
}

Three deliberate choices worth defending:

• total_estimate is an estimate, not a count. Counting the true size of a posting-list intersection across 1,000 shards costs as much as the query itself, and nobody needs the exact number.
• corrected carries the rewritten query when we spell-corrected it, so the UI can say "showing results for X" honestly.
• page and n give cursor-free pagination, and we deep-link rarely past page 3 because almost no real traffic goes there, which lets us cap per-shard work.

GET /autocomplete?prefix=distri
200 OK
{ "suggestions": ["distributed systems", "distributed consensus", "distribution"] }

POST /admin/seed        # internal: inject seed URLs into the crawl frontier
{ "urls": ["https://news.example.com"], "priority": "high" }

4High-level design#

Two pipelines. Walk the write path, then the read path, then name the seam.

Write path (offline, batch-ish).

• A URL Frontier holds the queue of URLs to fetch, prioritized by importance and politeness.
• Crawlers pull from it, fetch pages, and dump raw HTML into blob storage.
• A parser extracts text, links, title, and language.
• New links go back into the frontier, deduped against a seen-URL set so we never re-queue the same page forever.
• Extracted docs flow into the indexer, which tokenizes, stems, and builds inverted-index segments per shard.
• Finished segments get published to the serving fleet.
• Nothing here has an SLO tighter than minutes, which is exactly why I batch it, compress hard, and run it on cheaper hardware.

Read path (online, latency-critical).

• A query hits the front end, where it is normalized, spell-corrected, and expanded.
• A query coordinator fans the query out to all shards in parallel.
• Each shard returns its top-k candidates with a cheap first-pass score.
• The coordinator merges, runs a more expensive second-pass re-ranker on the merged top few hundred, fetches snippets, and returns ten results.
• A result cache sits in front of the whole thing for popular queries.
• Every component here is stateless and replicated, so I scale horizontally and survive node loss without dropping queries.

Why the seam matters.

• The write path produces segments; the read path consumes them; neither side blocks the other.
• On publish, serving keeps answering from the old snapshot until the swap is atomic.
• That one property lets the two pipelines scale, fail, and deploy on completely independent schedules.

5Data model#

Different parts want different stores, so justify each by access pattern, not by habit. The rule: pick the store that makes the single dominant read cheap.

Document metadata (key-value by doc id). One lookup by doc id to build a snippet and show the URL. No joins, no scans, no cross-row transactions. A wide-column or big key-value store fits because the only access pattern is "give me everything about doc 48213011."

• The dense int64 doc_id is not cosmetic. Posting lists are lists of doc ids, and dense sequential ids are what make delta encoding compress to that 1.5 bytes per posting.
• Use a raw URL or a random UUID as the id and the index grows several times larger, and the whole in-memory story collapses.

Inverted index (custom structure, not a general DB). The heart of the system: a map from term to a sorted posting list of doc ids.

• Positions live in the posting, not just doc ids, because phrase queries need them.
• Without positions I can say a page contains "new" and "york" somewhere, but not that they sit next to each other. "new york" vs "new ideas from york university" is the difference between a good result and a bad one.

URL frontier / seen set (key-value store plus Bloom filter). The seen-URL set answers "have I crawled this?" billions of times.

• A Bloom filter in front of the store keeps it cheap: the filter answers "definitely new" or "probably seen" in memory, and we only hit the store on a probable hit to confirm.
• A false positive costs one skipped crawl of a page we might not have actually seen, a fine price for keeping 40B lookups off the backing store.

Why no SQL anywhere here.

• There is no relational query, no transaction spanning rows, no ad-hoc join.
• The dominant access is "give me the posting list for this term" and "give me metadata for this doc id." Both are point lookups into purpose-built structures.
• SQL would buy nothing and cost latency and operational weight at this scale.

6Deep dives#

6.1 Crawling at scale: the frontier, politeness, and traps#

Crawling sounds like a for loop over URLs. It is not. The hard parts are politeness, prioritization, and not getting stuck, and each one has bitten a real crawler team hard.

The URL Frontier is two levels of queues.

• Front queues prioritize by page importance: a page linked from high-PageRank sites gets crawled sooner, because we would rather spend our 33K-per-second budget on pages people actually search for.
• Back queues enforce politeness: one queue per host, each with a scheduled "next allowed fetch time" so we never hammer a single server.
• A crawler worker always pulls the host whose timer has expired.
• This structure is what keeps us from accidentally DDoSing a small WordPress blog while still crawling 33K pages a second across millions of hosts.

Three things that bite everyone.

• Duplicate and near-duplicate content. Compute a content hash (and a simhash for near-dupes) so a wire story syndicated across a hundred sites is not indexed a hundred times. Index one canonical copy, remember the rest point to it, and keep the index from being dominated by boilerplate.
• Crawler traps. Infinite calendars that let you click "next month" forever, and session-id URLs that generate endless unique pages. Cap crawl depth per host, normalize URLs to drop volatile query params, and throttle any host producing suspiciously many near-identical pages.
• robots.txt and rate limits. Fetched once per host and cached. Non-negotiable. Ignoring it gets your crawler IP-blocked and your company a letter from someone's lawyer, both of which cost far more than the pages you skipped.

Re-crawl scheduling is adaptive.

• A news homepage changes every few minutes; a university's 2009 syllabus does not.
• Track observed change rate per URL and re-crawl frequently-changing, high-value pages more often, letting the stale long tail drift.
• That is how we hit "minutes for news, two weeks for the long tail" without the waste of crawling all 40B pages on the same fixed schedule.

6.2 The inverted index, sharding, and the fan-out problem#

This is the part a senior candidate has to nail, and where I spend the most whiteboard time. The inverted index maps each term to the docs containing it, plus positions for phrase queries ("new york" as a phrase, not "new" AND "york" scattered across a page).

The core inner loop.

• Query "distributed consensus" becomes: fetch the posting list for distribut (stemmed), fetch the posting list for consensu, intersect, score survivors, return top-k.
• Both lists are sorted by doc id, so intersection is a linear merge.
• Skip pointers let the merge jump ahead instead of walking every doc id, so intersecting a rare term with a common one costs roughly the length of the rare list, not the common one.

Sharding: by document, not by term. This is the opinionated call, and the one most candidates get wrong.

• So I shard by document: each shard holds the complete inverted index for a slice of the corpus, say 40M docs per shard across 1,000 shards.
• Every query goes to every shard, each finds its local top-k, and the coordinator merges.
• I pay the fan-out cost with in-memory indexes, caching, and the two-phase scoring below.

Two-phase scoring to keep fan-out cheap.

• Phase one, inside each shard, uses a cheap score (roughly BM25 times PageRank) so shards prune hard and return a couple hundred candidates each, not every matching doc.
• Phase two, at the coordinator, runs the expensive learned re-ranker (hundreds of features) on only the merged few hundred.
• We never run the expensive model on billions of docs. We run it on the survivors.
• That split is the only reason sub-200ms is possible against 40B docs, because the heavy per-document math scales with "few hundred," not with corpus size.

Handling the straggler.

• With 1,000 shards, the slowest shard sets your latency, and there is always a slow one: a GC pause, a hot node, a cold posting list.
• So the coordinator waits for, say, 95% of shards, then returns with what it has.
• Missing a few shards' candidates barely moves the top ten, because PageRank-heavy authoritative results are spread across all shards, not concentrated in the 50 we skipped.
• Trading a tiny bit of recall for a big tail-latency win is a trade I make on purpose. I would rather explain that choice than ship a p99 held hostage by one GC pause.

6.3 Ranking: BM25, PageRank, and why order matters#

Matching is easy, ranking is the product. Return every page containing both words in random order and the engine is useless no matter how fast it is. Order is where a search engine earns or loses its users.

First-pass relevance is a text score.

• TF-IDF captures the intuition: a term matters more if it appears often in this doc (term frequency) but is rare across the corpus (inverse document frequency).
• "the" is in everything, so its IDF is near zero and it contributes nothing. "consensus" is rare, so matching it counts a lot.
• Modern engines use BM25: TF-IDF with saturation (the 50th occurrence of a word does not count 50x the first) and length normalization (a 10,000-word page does not automatically beat a focused 500-word one).
• I name BM25 specifically because it signals I have shipped search, not just read about it.

Authority is PageRank.

• The idea: a page is important if many important pages link to it, computed as the stationary distribution of a random surfer following links.
• It is expensive and global, so it is precomputed in a batch job over the link graph and stored as one float per doc in the metadata table.
• It is a query-independent prior: it does not depend on what the user typed, so we fold it into the first-pass score and authoritative pages float up before we even look at the query.
• Precomputing it offline is what keeps the cost off the 200ms read budget.

Second-pass is a learned ranker over the merged candidates.

• Features like exact-phrase match, term proximity, freshness, click signals, and the two scores above.
• This is where typo tolerance and query expansion pay off: type "consesus" and we correct it (edit distance against a term dictionary), also try the expanded term, and let the ranker decide which interpretation produced better candidates.

The ordering discipline, stated as a principle.

• Cheap global prior (PageRank, baked in) plus cheap per-query text score (BM25) inside the shards, then one expensive learned model on a few hundred survivors.
• Push cheap work down to the shards where it runs in parallel; keep expensive work small and central where I can afford a heavy model.
• Break that discipline and either latency or cost explodes.

7Bottlenecks and trade-offs#

What breaks first: query fan-out and tail latency.

• As the corpus grows, shard count grows, fan-out grows, and the probability that at least one shard is slow approaches one.
• With 1,000 shards, even a 99.9% per-shard fast rate means the typical query hits a slow shard.
• Mitigations: partial results (answer at 95% of shards), hedged requests (send a duplicate to a second replica of a slow shard, take the first to answer), and bounded per-shard work via two-phase scoring.
• This is the dominant operational headache of a real search engine, and I would spend real review cycles on it in production.

Hot queries and cache dependence.

• A small set of queries ("weather", trending news, a celebrity name during an event) is a big fraction of traffic.
• The result cache absorbs that, and a healthy hit rate cuts the shard fan-out we actually serve by a large margin.
• But a cache miss storm (a trending event the cache has never seen, or a cold cache right after a deploy) can slam the shards all at once.
• Keep the cache warm with staggered restarts so the whole tier never cold-starts together, and treat cache hit rate as a first-class SLO with alerting, not a nice-to-have nobody watches.

The write path is an eventual-consistency machine, on purpose.

• A page crawled now is not searchable now. Segments are built, published to shards, then merged in, with a lag of minutes to hours.
• I accept that because the alternative, updating a live in-memory index per document, murders read latency with locking and fragmentation.
• The consistency call: reads come from an immutable, slightly stale snapshot, and we swap snapshots atomically so a query never sees a half-built index.
• Freshness loses to latency and stability, the right call for web search because a two-hour-old result for most queries is indistinguishable from a fresh one.
• The news fast-path is the escape hatch for the cases where freshness matters: a smaller, faster, more frequently rebuilt index just for recent content.

Single points of failure.

• The coordinator tier and the frontend are stateless and replicated behind a load balancer, so a dead node just drops out of rotation.
• If the indexer or segment-publisher dies, serving keeps working on the last snapshot (good) but freshness stalls until recovery (tolerable, because stale beats down).
• The frontier's seen-set store is the dangerous one. Lose it and we re-crawl the world and burn weeks of crawl budget, so it gets replicated and backed up harder than almost anything else in the system.

Storage tier choice.

• Keeping 360TB of replicated index purely in RAM is expensive enough to notice on the bill.
• Realistically it is tiered: the hottest shards and the posting lists for the most common terms live in memory, the long tail on NVMe SSD.
• The trade-off is a latency cliff when a query touches a cold, SSD-resident posting list, because an SSD read is orders of magnitude slower than RAM.
• Soften it by caching decompressed posting lists for popular terms and co-locating term dictionaries in memory, so we know a posting list's size before fetching it and can budget the query accordingly.

Push cheap work down to the shards, keep the expensive work small and central. Break that discipline and either latency or cost explodes.

8Summary#

The decisions that matter, the ones I would defend in a debrief:

• Two independent systems meeting at the index. Slow batch write path, fast online read path, connected only by immutable segments swapped atomically. The backbone, and the first thing I protect if someone proposes a "simpler" unified pipeline.
• Shard by document, not by term. Even load and correct phrase queries beat the lower fan-out of term-sharding, and I pay the fan-out cost with in-memory indexes, caching, and partial-result tolerance.
• Two-phase scoring. Cheap BM25-plus-PageRank pruning inside each shard, then one expensive learned re-ranker on a few hundred survivors. This is what makes sub-200ms feasible against 40B docs.
• Reads from a slightly stale, immutable snapshot. Freshness yields to latency and stability for the bulk of the web, with a dedicated news fast-path where freshness earns its keep.
• Politeness-first crawling with per-host queues, adaptive re-crawl, and aggressive dedup, because a rude crawler is a blocked crawler and a blocked crawler indexes nothing.
• Out of scope by choice: heavy personalization, full spam/SEO defense, geo-distribution. Naming them keeps me honest about what 45 minutes covered.

For a related deep dive, see our guide on designing a large-scale distributed crawler and link-graph pipeline.