Design a Search Engine

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Three loosely coupled subsystems connected by storage, not RPC: the crawler writes raw pages to a document store; the indexing pipeline reads the store and emits immutable index shards; the serving tier loads shards and answers queries. Each subsystem scales and fails independently, and the batch boundary between them (index epochs) is what makes the whole thing operable: serving never depends on the crawler being healthy.

The crawler is a frontier-driven loop: a URL frontier (priority queues partitioned by domain) feeds fetchers, fetched HTML is parsed for text and outlinks, new URLs flow back to the frontier. Politeness is enforced structurally: all URLs for one domain map to one frontier queue with a per-queue rate limit, so no coordination is needed to avoid hammering a site. Content-seen deduplication (SimHash for near-duplicates, exact hash for identical bodies) prunes the 30-plus percent of the web that is duplicated before it wastes index space.

The indexing pipeline is a classic MapReduce shape even if you run it on Spark: map each document to (term, docId, positions, tf) tuples, shuffle by term, reduce into per-term posting lists sorted by docId and delta-compressed. Alongside, a link-graph job extracts (src, dst) edges and iterates PageRank to convergence. The output is a new immutable index epoch: document-partitioned shards, each containing its term dictionary, posting lists, and per-doc static scores (PageRank, spam score, length norms).

Serving is scatter-gather over document-partitioned shards. A query hits a coordinator, which normalizes terms, broadcasts to one replica of each shard, and each shard intersects posting lists, scores its local candidates with BM25 plus static signals, and returns its top 50. The coordinator merges, takes the global top 10, and hydrates snippets. Document partitioning (vs term partitioning) is the industry default because intersection happens locally on one node, network cost per query is bounded, and a dead shard degrades results by 1/250th instead of breaking specific terms.

Freshness is layered rather than solved once: the big batch index rebuilds weekly, a small delta index rebuilds hourly from recently crawled pages, and serving queries both and merges (with the delta winning on doc collisions). This mirrors the Lucene segment model and avoids the false choice between real-time indexing complexity and week-stale results.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Write a polite async crawler: httpx with a per-domain asyncio semaphore and a 1 req/s per-domain sleep, seeded with 20 URLs from a niche you like
2. 02Respect robots.txt via urllib.robotparser and store fetched pages (url, html, text, outlinks) in SQLite
3. 03Extract text and links with selectolax; canonicalize URLs (strip fragments and utm params) and dedupe with a seen-set before enqueueing
4. 04Crawl ~5,000 pages, then build the inverted index: tokenize, lowercase, stem with nltk, emit term -> sorted list of (doc_id, tf) into a pickle or SQLite table
5. 05Compute PageRank over the crawled link graph with 30 power iterations (a 50-line function, no library needed)
6. 06Implement BM25 scoring over posting-list intersection for multi-term queries and blend with 0.2 x log PageRank
7. 07Serve GET /search?q= with FastAPI: tokenize the query, intersect postings, score, return top 10 with title and a naive snippet (text window around the first match)
8. 08Verify: search a term you know appears on exactly 3 crawled pages and confirm those 3 rank above pages that merely link to them

import math, re
from collections import defaultdict

TOKEN = re.compile(r"[a-z0-9]+")

def build_index(docs):  # docs: dict[doc_id] = text
    index = defaultdict(list)          # term -> [(doc_id, tf)] sorted by doc_id
    doc_len = {}
    for doc_id in sorted(docs):
        terms = TOKEN.findall(docs[doc_id].lower())
        doc_len[doc_id] = len(terms)
        tf = defaultdict(int)
        for t in terms:
            tf[t] += 1
        for t, f in tf.items():
            index[t].append((doc_id, f))
    avgdl = sum(doc_len.values()) / max(1, len(doc_len))
    return index, doc_len, avgdl

def bm25(index, doc_len, avgdl, n_docs, query, k1=1.2, b=0.75):
    scores = defaultdict(float)
    for term in TOKEN.findall(query.lower()):
        postings = index.get(term, [])
        if not postings:
            continue
        idf = math.log(1 + (n_docs - len(postings) + 0.5) / (len(postings) + 0.5))
        for doc_id, tf in postings:
            norm = tf * (k1 + 1) / (tf + k1 * (1 - b + b * doc_len[doc_id] / avgdl))
            scores[doc_id] += idf * norm
    return sorted(scores.items(), key=lambda x: -x[1])[:10]

def pagerank(links, d=0.85, iters=30):
    # links: dict[url] = list of outlink urls (within the crawled set)
    pages = set(links) | {v for outs in links.values() for v in outs}
    n = len(pages)
    rank = {p: 1.0 / n for p in pages}
    inlinks = {p: [] for p in pages}
    for src, outs in links.items():
        for dst in outs:
            inlinks[dst].append(src)
    for _ in range(iters):
        dangling = sum(rank[p] for p in pages if not links.get(p))
        new = {}
        for p in pages:
            incoming = sum(rank[q] / len(links[q]) for q in inlinks[p] if links.get(q))
            new[p] = (1 - d) / n + d * (incoming + dangling / n)
        rank = new
    return rank

import asyncio, time
from urllib.parse import urlparse
import httpx

class PoliteCrawler:
    def __init__(self, delay_per_domain=1.0, max_pages=5000):
        self.next_ok = {}          # domain -> earliest next fetch time
        self.seen = set()
        self.frontier = asyncio.Queue()
        self.delay = delay_per_domain
        self.budget = max_pages

    async def fetch(self, client, url):
        domain = urlparse(url).netloc
        wait = self.next_ok.get(domain, 0) - time.monotonic()
        if wait > 0:
            await asyncio.sleep(wait)
        self.next_ok[domain] = time.monotonic() + self.delay
        r = await client.get(url, timeout=10, follow_redirects=True)
        return r.text if r.status_code == 200 else None

    async def worker(self, client, on_page):
        while self.budget > 0:
            url = await self.frontier.get()
            if url in self.seen:
                continue
            self.seen.add(url)
            html = await self.fetch(client, url)
            if html:
                self.budget -= 1
                for link in on_page(url, html):   # parse, store, return outlinks
                    if link not in self.seen:
                        self.frontier.put_nowait(link)