Design a Web Search Engine

Design the core of a general web search engine. A user types a few words and expects ten relevant results with titles and snippets in a few hundred milliseconds, drawn from tens of billions of crawled pages that keep changing.

Two systems meet here. The indexing side crawls the web, extracts text and builds an index that is far too large for one machine. The serving side must answer well over a hundred thousand queries per second at peak, touching that whole index for each query, and still rank results well.

In 45 minutes, focus on the inverted index and how it is partitioned, how a query is executed and ranked across shards, how fresh pages get into the index, and how you keep the serving cost under control. Crawling politeness and the ranking model's internals can stay brief.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Data & Infrastructure · problem 44 of 70

Ask before you design. Try answering each yourself, then compare.

1. How large is the corpus?
   Typical answer

   About 20 billion indexed pages, roughly 10 KB of extracted text each, with around 1 billion pages re-crawled per day.

2. What query load and latency?
   Typical answer

   Around 4 billion queries a day, ~140k QPS at peak, with p99 under 300 ms server side.

3. How fresh must results be?
   Typical answer

   News-like pages should appear within minutes; the bulk of the web can lag by days.

4. What do we return?
   Typical answer

   Ten organic results per page with title, URL and a snippet highlighting query terms. Ads, images and answer cards are out of scope.

5. What ranking signals can we assume?
   Typical answer

   Text relevance (term frequency, field matches, proximity), page quality and link-based authority, freshness, and click feedback used offline to train a learned ranker.

6. Do we need to support phrase queries and other languages?
   Typical answer

   Phrase queries yes, via positions in postings. Assume per-language tokenizers exist.

Requirements

Functional

• Crawl web pages, extract text and links, and deduplicate near-identical pages.
• Build an inverted index with positions and per-document signals.
• Answer keyword and phrase queries with the top 10 ranked results, titles and snippets, with pagination.
• Pick up new and changed pages, with fast-changing sites refreshed within minutes.

Non-functional

• 140k QPS peak, server-side p99 under 300 ms.
• 20B documents indexed; 99.95% query availability, degrading to partial results rather than failing.
• Fresh index lag under 10 minutes for high-priority sites, under a few days for the long tail.
• Serving cost proportional to traffic, not to the full corpus for every query.

Out of scope

• Ads, image and video search, and knowledge panels.
• Details of the learned ranking model and its training pipeline.
• Personalisation beyond language and location.

Back-of-the-envelope estimates

• Queries: 4B/day ≈ 46k QPS average, ~140k at peak. A result cache for repeated queries absorbs 40–50%, leaving ~75k QPS for the index.
• Corpus: 20B pages × ~10 KB text ≈ 200 TB of text, about 400 TB including raw page copies. Re-crawling 1B pages/day is ~12k fetches/s.
• Index size: compressed postings with positions run at about 25–30% of the text, so ~60 TB, plus ~200 TB of document data for snippets.
• Shards: at ~50M documents per shard, the full index is ~400 shards. If one replica of a shard handles ~1,000 QPS, fanning every query to all 400 shards at 75k QPS needs ~75 replicas each, roughly 30k machines.
• Tiering: putting the best 2B pages in a tier-1 index (~40 shards) that answers ~80% of queries alone cuts that to a few thousand machines plus a smaller tier-2 fleet.

Query fan-out times QPS drives cost, so caching and index tiering matter more than raw storage.

API

GET /search?q=sourdough+starter&page=1&lang=en&loc=GB
   -> {results:[{url, title, snippet, score}], tookMs, partial:false}

// internal RPCs
ShardSearch(shardId, parsedQuery, globalStats, k=100, deadlineMs) -> [{docId, score}]
FetchDocs(docIds, queryTerms) -> [{docId, url, title, snippet}]

Shard RPCs carry a deadline: the root returns whatever arrived in time and marks the response partial, because one slow shard must not hold up every query.

Data model

Inverted index: per shard, a term dictionary maps each term to a postings list of (doc_id, term_freq, positions), sorted by doc ID and compressed with delta plus variable-length encoding. Doc IDs are assigned so that higher-quality pages get smaller IDs, letting queries stop early.

Per-document data: URL, title, length, quality and authority scores, language, and a compressed copy of the text for snippets, stored next to the postings in the same shard.

Partitioning: by document: each shard holds a complete mini-index for its slice of the web, so writes are local and load is even. Crawl state (URL, last fetched, content hash, change rate) lives in a wide-column store keyed by host-reversed URL; raw pages go to object storage.

High-level design

Query path. The query frontend normalises the query, fixes spelling, detects language and checks the result cache, which holds the top results for popular queries for a few minutes. On a miss it sends the parsed query to a root aggregator. The root first fans out to every tier-1 shard. Each shard walks the postings for the query terms, scores candidates with a cheap formula (BM25-style relevance plus static quality), and returns its local top 100. The root merges these lists; if too few good results come back, it also queries the larger tier-2 index. The best ~1,000 candidates then go to a re-ranker that applies a learned model with richer features, and the final ten are sent back to the owning shards for titles and query-specific snippets.

Indexing path. A URL frontier orders URLs by importance and expected change rate while respecting each site's crawl rate. Crawlers fetch pages, honour robots rules, drop duplicates by content hash, and store raw pages and extracted text in the page store. Batch jobs compute link-based authority and spam scores over the link graph. The index builder turns changed pages into new index segments per shard and publishes them; shard servers load new segments alongside existing ones and swap them in without downtime. A small real-time index for very fresh pages is queried alongside the main one.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Partition by document, not by term

Term partitioning puts each word's entire postings list on one machine, so a two-word query touches only two servers, but popular terms create huge hot shards, multi-word queries must ship enormous postings lists across the network to intersect them, and adding a document updates many machines. Document partitioning gives every shard a full index for its slice, so each query fans out to all shards, but each does a small, local, parallel piece of work and returns only a short top-k list. Load spreads evenly, and a lost shard means slightly worse results instead of a missing word. The cost is fan-out, handled with replication, deadlines and tiering.

Ranking in stages

Stage one runs on every shard and must be cheap: intersect or union postings, compute BM25-like text relevance with global term statistics so scores are comparable across shards, and add static quality and authority. Because doc IDs are ordered by quality and postings carry per-block maximum scores, a shard can skip blocks that cannot beat its current top-k, often avoiding most of the postings. Stage two runs at the root on about a thousand candidates with a learned model using proximity, field matches, freshness, click-derived features and location. Only stage two can afford expensive features, so stage one's job is high recall.

Keeping the index fresh

A full rebuild of 20B documents takes hours to days, so combine three layers. The base index is rebuilt periodically in batch and is heavily optimised. Incremental segments, built every few hours from changed pages, are merged in at query time and compacted later, with deleted or replaced documents masked by a tombstone bitmap. A small real-time index, fed by a priority crawl of news and frequently changing sites, makes new pages searchable within minutes. The crawl scheduler estimates each page's change rate from history and spends the fetch budget where change is likely and the page matters.

Tail latency at high fan-out

When one query waits for hundreds of shards, the slowest shard sets the latency, so a rare 1% slowdown hits most queries. Send a backup request to another replica if a shard has not answered within its p95, cap each shard's work with a deadline, and return partial results flagged as such. Keep postings for tier 1 in memory, shed load by trimming tier-2 lookups under pressure, and use the result cache to remove repeated popular queries entirely.

Failure modes

• If a shard replica is slow, hedged requests to another replica keep the query on time; if every replica of a shard is down, results come back slightly incomplete and flagged partial.
• If the result cache fails, the index fleet sees roughly double the load; keep headroom or shed tier-2 lookups and spelling suggestions first.
• If a bad index build is published, shards keep the previous version and roll back automatically when quality checks on a sample of queries regress.
• If crawlers are blocked or slowed by a site, the frontier backs off that host so politeness is preserved and the crawl budget moves elsewhere.
• If the re-ranker is unavailable, fall back to first-stage scores; results are worse but still served.

Core algorithm in code

import heapq
import math
import re
from collections import Counter, defaultdict

STOP = {"the", "a", "an", "of", "to", "and", "in", "for", "on", "is", "how"}


def tokenize(text):
    return [t for t in re.findall(r"[a-z0-9]+", text.lower()) if t not in STOP]


class Shard:
    """One document-partitioned index shard: postings list per term, BM25 scoring."""

    def __init__(self, k1=1.2, b=0.75):
        self.k1, self.b = k1, b
        self.postings = defaultdict(list)       # term -> [(doc_id, term_freq)]
        self.doc_len, self.quality, self.titles = {}, {}, {}

    def add(self, doc_id, title, body, quality):
        terms = tokenize(title + " " + title + " " + body)   # title counted twice: a cheap field boost
        self.doc_len[doc_id], self.quality[doc_id], self.titles[doc_id] = len(terms), quality, title
        for term, tf in Counter(terms).items():
            self.postings[term].append((doc_id, tf))

    def stats(self, terms):
        return len(self.doc_len), sum(self.doc_len.values()), {t: len(self.postings.get(t, [])) for t in terms}

    def search(self, terms, n_docs, avg_len, df, k):
        scores = defaultdict(float)
        for t in terms:
            idf = math.log(1 + (n_docs - df[t] + 0.5) / (df[t] + 0.5))
            for doc, tf in self.postings.get(t, []):
                norm = tf * (self.k1 + 1) / (tf + self.k1 * (1 - self.b + self.b * self.doc_len[doc] / avg_len))
                scores[doc] += idf * norm
        ranked = ((s + 1.5 * self.quality[d], d) for d, s in scores.items())   # blend in a static quality prior
        return [(round(s, 3), d, self.titles[d]) for s, d in heapq.nlargest(k, ranked)]


def root_search(shards, query, k=3):
    terms = tokenize(query)
    # phase 0: global term statistics so scores are comparable across shards
    n_docs, total_len, df = 0, 0, Counter()
    for sh in shards:
        n, l, d = sh.stats(terms)
        n_docs, total_len = n_docs + n, total_len + l
        df.update(d)
    # phase 1: scatter to every shard, each returns its local top-k
    partial = [hit for sh in shards for hit in sh.search(terms, n_docs, total_len / n_docs, df, k)]
    # phase 2: gather and merge
    return heapq.nlargest(k, partial)


docs = [
    (1, "Sourdough bread recipe", "flour water salt starter long fermentation bread", 0.9),
    (2, "Bread machine manual", "settings for white bread and dough cycles", 0.3),
    (3, "History of bread", "bread in ancient egypt and rome grain", 0.6),
    (4, "Quick yeast bread", "fast bread recipe with instant yeast in two hours", 0.7),
    (5, "Starter troubleshooting", "why your sourdough starter smells and how to fix it", 0.5),
    (6, "Pizza dough recipe", "neapolitan pizza dough with flour water yeast salt", 0.8),
]
shards = [Shard(), Shard()]
for doc_id, title, body, q in docs:
    shards[doc_id % 2].add(doc_id, title, body, q)           # documents spread by ID

for q in ["sourdough bread recipe", "dough yeast", "how to fix a starter"]:
    print(f"query: {q!r}")
    for score, doc_id, title in root_search(shards, q):
        print(f"   {score:6.3f}  doc {doc_id}  {title}")

Trade-offs

• Document partitioning balances load and keeps updates local but fans every query out to all shards; term partitioning reduces fan-out but creates hot shards and heavy network intersection.
• Index tiering cuts serving cost sharply but can miss a relevant long-tail page when tier 1 seems good enough.
• A result cache removes a large share of load but serves results that may be minutes stale.
• Cheap first-stage scoring scales but can drop documents a richer model would rank highly; widening the candidate set improves quality at higher cost.
• Batch base index plus incremental segments keeps quality high and freshness acceptable but adds query-time merging and compaction complexity.

What a strong answer shows

• Explains the inverted index concretely: dictionary, sorted compressed postings, positions.
• Chooses document partitioning and justifies it against term partitioning.
• Describes scatter-gather with global statistics, per-shard top-k and a merge at the root.
• Ranks in stages: cheap recall-oriented scoring, then a learned re-ranker on a small candidate set.
• Addresses freshness with incremental and real-time indexes rather than full rebuilds.
• Controls cost and tail latency with caching, tiering, hedged requests and deadlines.

Mistakes to avoid

• Proposing a relational database with LIKE queries, or one giant index on a single machine.
• Running the expensive ranking model over every matching document.
• Ignoring that per-shard term statistics make scores incomparable across shards.
• Rebuilding the whole index for every change and having no plan for freshness.
• Forgetting tail latency when every query fans out to hundreds of servers.

Follow-ups to expect

• How would you add autocomplete? (A separate prefix index or trie of popular queries, updated from query logs.)
• How would you detect near-duplicate pages? (Shingling with SimHash or MinHash signatures; keep the canonical one.)
• How would you incorporate click feedback without being gamed? (Aggregate offline with position-bias correction and bot filtering; feed it into the re-ranker's training.)
• How would you serve phrase queries efficiently? (Positional postings, or index frequent bigrams as single terms.)

Practice next