Search Engine

System Design series #3 (EP24). Topic skill: skills/search-engine/. Design a web search engine with crawler, indexing, ranking, and serving at scale.

1. The problem and why it is deceptive

Most people picture a simple box: the user types a query, gets ten links, done. Underneath is a large pipeline. You discover pages, decide what is worth fetching, download content without harming third- party sites, parse and extract text/links/metadata, normalize, deduplicate, build an inverted index, compute offline features, optionally build embeddings, and finally serve queries in a few milliseconds with relevant ranking.

The architecture changes enormously with the goal. Internal documentation search is one problem. Public web-scale search is another world. One sentence captures the system:

A search engine is a distributed factory that turns URLs into rankable documents.

It is a chain of decisions: what to discover, fetch, store, index, retrieve, and promote. Each stage kills bad cost and keeps useful signal.

2. Four subsystems + two support planes

• Crawler: discover and fetch pages.
• Processing pipeline: parse, clean, extract, enrich.
• Indexing pipeline: build the indexes.
• Query serving: analyze the query, retrieve candidates, rank, assemble the result.
• Support: metadata / policy (robots.txt, politeness, canonical rules, scheduling, dedup) and observability / control (metrics, debugging, reprocess, backfill, allow/blocklists).

3. Requirements

Functional: accept seeds; discover links recursively; respect crawl policy (robots.txt, delays, per-host limits); fetch HTML (optionally PDFs, feeds, images); parse and extract text, links, title, headings, anchor text, canonical, language, timestamp, structured metadata; detect duplicates and near-duplicates; build an inverted index for lexical search; optionally a vector index for semantic recall; answer queries with paging, snippets, filters, relevance ranking; re-crawl periodically for freshness.

Non-functional: horizontal scalability at every stage; high offline throughput; low serving latency (typically < 200 ms end to end, ideally well under); high availability on the query path; eventual consistency between crawl and search is acceptable if it converges; predictable cost; safe, non-abusive behavior toward third-party sites; enough observability to explain why a page is not indexed or why a query returned what it did.

4. End-to-end mental model

flowchart LR
  seeds --> frontier --> fetcher --> parser --> extractor --> dedup
  dedup --> docstore --> index
  index --> serving
  serving --> analyzer --> retriever --> ranker --> result

Seeds → frontier picks an eligible URL → fetcher downloads → parser turns bytes into a structured document → extractor produces clean text, outlinks, metadata → deduplicator decides new/exact/near-dup → document store persists the canonical version → indexing tokenizes and builds postings lists → offline jobs compute global signals (e.g. link-graph popularity) → at query time the analyzer normalizes, the retriever finds candidates, the ranker scores, the result builder assembles snippets.

5. The crawler (the heart)

URL frontier

The central structure. It is not one queue. A serious implementation separates three concepts:

• URL-seen store: has this URL appeared before? (Bloom filter in front of a persistent store.)
• Crawl-state store: last attempt status, content hash, HTTP code, response time, next recrawl window.
• Scheduler priority queues: pick the next URL respecting priority and politeness.

Why a Bloom filter? (Burton Bloom, 1970.) A probabilistic set membership structure: it answers "have I seen this URL?" in O(1) and a few bits per element, with no false negatives and a tunable false-positive rate. At web scale you cannot keep every seen URL in memory exactly; the Bloom filter gives you "definitely new" vs "probably seen, go check the store" cheaply.

Multi-queue per host

A single global queue creates two problems: hot domains (one heavily-linked domain fills the queue) and lost politeness (you fire many concurrent requests at one host, looking like a DDoS). The fix: one pending queue per host, each with a next_eligible_timestamp; a global heap orders hosts by lowest eligible time and highest priority. When a host becomes eligible, pop a URL, fetch, update backoff, reinsert the host. This gives fairness and politeness together.

Canonicalization

Normalize before enqueue: lowercase host, drop fragments, default ports, clean irrelevant query params, resolve relative paths, drop known session ids, normalize trailing slash. Skipping this explodes duplicates and crawl cost.

robots.txt and politeness

Cache robots.txt per host with a TTL; respect allow/disallow and crawl-delay (the Robots Exclusion Protocol, now RFC 9309, 2022). Politeness is not a fixed sleep:

next_request_allowed = max(min_delay, k * observed_latency, robots_crawl_delay)

plus max concurrency per host and exponential backoff on errors. This avoids hammering slow sites.

Fetcher

Stateless, heavy I/O: async networking, connection pooling, DNS cache, TLS reuse, gzip/brotli, redirect limits, max download size, content-type sniffing (do not trust the header alone), and conditional GET (ETag / If-Modified-Since) for cheap recrawl. Persist metadata: status code, headers, final URL after redirects, response time, body checksum.

Crawler traps

The web has infinite false pages: calendars generating endless date pages, e-commerce facet combinations, arbitrary-parameter URLs, a site's own internal search, pagination loops. Guardrails: crawl budget per host, fan-out limit per page, parameter regex blocklists, a template-repeat score, depth limits. Without these, 80% of cost goes to the worst 5% of the web.

6. Crawl scheduling (where money becomes strategy)

Crawling the whole web every day is impossible for almost everyone. With a finite budget of requests, bandwidth, and CPU, scheduling is a business decision. A rough crawl score:

crawl_score ~ quality * freshness_need * business_priority / fetch_cost

(Intuition, not a literal universal formula.) Adaptive recrawl: changed twice in a short interval → shrink the window; unchanged many times → grow it; errors → back off. Far better than a fixed cron. Freshness tiers A/B/C/D (minutes → rarely) by domain, URL pattern, or dynamic score.

7. Theory, deduplication

Web search without dedup is chaos: the same content appears with/without www, http/https, different params, print pages, syndication, mirrors, republications, and soft duplicates.

Three levels:

1. URL duplicate: same normalized URL.
2. Exact content duplicate: same hash of clean text.
3. Near-duplicate: almost-equal content.

For near-duplicates you fingerprint with shingles + MinHash (Broder, 1997) or SimHash (Charikar, 2002). MinHash estimates Jaccard similarity between shingle sets from a few hash minima; SimHash maps a document to a bit vector where Hamming distance tracks similarity, so you can cluster by fingerprint cheaply. Store a document_fingerprint and a canonical_document_id; many URLs map to one canonical document. Dedup early and in layers, or you pay to process expensive duplicates, and you consolidate ranking signals (inbound links, clicks) onto the canonical.

8. Storage by function

• Raw content store: the original response, compressed, in cheap object storage, for reprocessing and audit.
• Parsed document store: doc_id, canonical_url, fetch_time, title, clean_text, language, outgoing_links, anchors_in, headers, content_type, quality_signals, fingerprint.
• Crawl metadata store: operational state with frequent random updates: url, host, discovered_at, last_fetch_status, last_success_at, next_fetch_at, retry_count, robots_policy_version, blocked_reason. A KV/wide-column store fits better than object storage here.

9. Theory, the inverted index

The classic lexical structure. Instead of storing terms per document, store, for each term, the list of documents it appears in. That list is a postings list:

term: crawler
postings: [(doc1, tf=3, positions=[4,18,22]), (doc7, tf=1, positions=[9])]

Per posting: doc_id, term frequency, positions (for phrase queries), field info (title vs body), optional payloads.

Build pipeline

Tokenize → normalize (lowercase, strip accents, stem/lemmatize) → drop stopwords where sensible → emit term → posting pairs → sort-merge by term → compress postings → persist immutable segments → publish a new index version. This is naturally distributable, model it as MapReduce (Dean & Ghemawat, 2004) or streaming with batch compaction.

Sharding

Two strategies: document sharding (each shard holds a subset of documents and their terms) vs term sharding (each shard holds a subset of terms). Document sharding usually simplifies serving, replication, and rebalancing: a query fans out to all document shards, each returns a local top-K, and an aggregator merges.

Segments and merge

Updating a big index in place is expensive. The Lucene model (Doug Cutting) uses immutable segments plus periodic background merges: cheap sequential writes, simple snapshots, easy rollback, concurrent serving during reindex. Costs: background merge work, deleted docs linger as tombstones until merge, and more segments raise query cost.

Compression

Postings must be compressed or the index explodes: delta encoding of doc ids, variable-byte encoding, frame-of-reference, bit packing, and skip lists to jump over blocks. Goal: read fast without burning CPU on decompression.

10. Query serving (the online path)

sequenceDiagram
  Client->>Gateway: query
  Gateway->>Analyzer: normalize, parse operators, classify intent
  Analyzer->>Shards: fan-out
  Shards-->>Ranker: top-K + partial scores
  Ranker->>Assembler: full features -> final score
  Assembler-->>Client: snippets + results

Analyzer

Normalize case, tokenize, optional spell-correction, synonym expansion, language detection, operator parsing (quotes, -, site:, filetype:), and intent classification (navigational / informational / transactional / fresh). Intent changes ranking: the same words can want different things.

Candidate retrieval

You do not rank the whole web. First recall a candidate set via BM25 on the lexical index, field filters, title/anchor boosts, optionally ANN search over embeddings, or a hybrid union. Typically top-N per shard (~500-1000), then merge.

BM25 (Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond) is the standard lexical relevance function: it rewards term frequency with saturation and penalizes long documents, with tunable parameters k1 and b. It is the workhorse baseline that strong systems still build on.

Ranking

The final score combines families of features:

• Textual match: BM25, term-in-title, term-in-heading, term proximity, phrase match, anchor-text match.
• Document: domain authority, page quality, freshness, spam score, language match, structure.
• Query: intent, freshness need, entity type, ambiguity.
• Behavioral (if available): CTR, long clicks, query reformulations, dwell time, fast abandonment.

A simple start is a weighted linear score, e.g. 0.45*bm25 + 0.20*title + 0.15*authority + 0.10*freshness + 0.10*anchor. Mature systems move to learning-to-rank: but only with good features and click data, or you buy expensive complexity.

Result assembly

Highlighted snippet, canonical URL, clean title, breadcrumbs, date when relevant, sitelinks, and dedup of near-identical results. A good snippet drives perceived quality; it is not cosmetic.

11. Theory, the link graph and global signals

A real web search engine does not live on page text alone. The link graph is a strong global signal: if many relevant pages point to a document, that suggests authority. Build a directed graph (vertices = documents or domains, edges = hyperlinks, weights consider context, link position, anchor text) and run offline batch jobs (daily/hourly, never on the query path) to compute authority, hub, centrality, and domain reputation.

PageRank (Brin & Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, 1998) is the famous approximation: a page's importance is the stationary distribution of a random surfer following links with a damping factor. Modern practice combines it with many anti-spam checks, or link farms and spam networks manipulate it. HITS (Kleinberg, 1999) is the related hub/authority formulation.

12. Spam, abuse, and quality

Open search attracts adversaries. Abuse: keyword stuffing, hidden text, doorway pages, link farms, cloaking, mass low-value content, aggressive duplication, deceptive redirects. Defenses: a spam classifier on content + link-graph features, domain reputation, per-template/cluster limits, boilerplate detection, mass-similarity checks, manual review for strategic cases, and a click/bounce feedback loop. Without a quality layer, the best index in the world serves garbage fast.

13. Freshness vs cost

More freshness means more crawl, processing, and cost. Less means stale, inconsistent results and lost trust. The answer is rarely uniform, use tiers: Tier A (very dynamic, high value) recrawled in minutes/hours; Tier B daily; Tier C weekly/monthly; Tier D rarely. Tier by domain, URL pattern, or dynamic score.

14. Index publishing and consistency

Index and documents are rarely synchronized in real time. Operate with versions: workers build new segments, a manifest describes the complete index version, the publisher commits it atomically, query servers warm up the new version, then swap. Benefits: simple rollback, serving without downtime, read consistency per version. For frequent updates, combine a base snapshot with smaller delta indexes.

15. Hybrid search (lexical + semantic)

Many teams jump straight to embeddings. For general search, lexical remains the foundation; embeddings complement it, they do not automatically replace it. Lexical is precise for rare terms, names, codes, and specific queries; semantic helps recall for natural language, synonyms, and varied phrasing; hybrid ranking usually beats either alone. Implementation: inverted index for lexical recall, an ANN index (e.g. HNSW) for document embeddings, query embedding generated online or cached, union of both candidate sets, final ranker decides. But generating embeddings, storing vectors, and running ANN at scale is not cheap, do it only when the problem demands it.

16. Scale and partitioning

Frontier partitioned by host hash (one owner per host so politeness coordination stays in one place). Fetchers stateless, autoscaling. Index: e.g. 64 logical shards × 2-3 replicas, leader publishes segments, followers serve, gradual rebalancing. Link-graph jobs as heavy distributed batch in windows , never on the query path.

17. Observability and SRE

• Crawl: URLs discovered/min, fetch success rate, bytes/min, latency per host, robots block rate, errors by DNS/timeout/TLS/4xx/5xx, frontier backlog per partition, recrawl lag.
• Indexing: docs parsed/min, duplicate rate, index size, merge duration, fetch-to-index-publish lag, failures per stage.
• Serving: QPS, p50/p95/p99, error rate, fan-out time, cache hit rate, top queries, zero-result queries, CTR, reformulation rate.

Mandatory debugging tools: URL inspection (crawl + index status of one URL), query explain (which shards answered, candidates, features, final score), host dashboard (errors, politeness, backlog, blocks per host), and document replay through the pipeline. Without these, the team spends its life guessing.

18. Failure modes

19. Incremental plan

1. Vertical slice: small seed set, HTML only, per-host frontier with basic politeness, simple parser, basic inverted index (Lucene/OpenSearch is fine), BM25 query, URL-inspection tool.
2. Efficiency / quality: exact + near dedup, better canonicalization, adaptive recrawl, initial quality scoring, better snippets, more observability.
3. Real scale: partitioned frontier, distributed fetchers, sharded versioned index, link-graph jobs, multi-factor ranking, disaster recovery + replay.
4. Advanced relevance: learning-to-rank, behavioral signals, hybrid embeddings, personalization, sophisticated anti-spam.

Advanced relevance on top of bad ingestion is expensive makeup. The order matters.

20. Operational summary (the north star)

• A good crawler is not the one that downloads the most pages. It is the one that chooses best what to download.
• A good parser is not the one that reads perfect HTML. It is the one that survives broken web and still extracts useful signal.
• A good index is not the one that stores everything. It is the one that organizes information to retrieve relevant candidates fast.
• Good ranking is not the most complex. It is the one that combines local signals, global signals, and query intent well.
• Good operations is not never failing. It is explaining fast why it failed and recovering without chaos.

References

• Sergey Brin & Lawrence Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, WWW, 1998 (PageRank).
• Jon Kleinberg, Authoritative Sources in a Hyperlinked Environment (HITS), JACM, 1999.
• Stephen Robertson & Hugo Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, 2009.
• Andrei Broder, On the Resemblance and Containment of Documents (shingling/MinHash), 1997.
• Moses Charikar, Similarity Estimation Techniques from Rounding Algorithms (SimHash), STOC, 2002.
• Burton Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (Bloom filter), CACM, 1970.
• Dean & Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004.
• Manning, Raghavan & Schütze, Introduction to Information Retrieval, Cambridge, 2008 (inverted index, tokenization, ranking).
• Apache Lucene documentation (immutable segments, merge policy).
• RFC 9309: Robots Exclusion Protocol, 2022.
• Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using HNSW graphs, 2016 (ANN for hybrid search).

This page mirrors Search Engine in the wiki. Edit it there.