Search Engine

System Design series #3 (EP24). Topic skill: .claude/agents/system-architect/skills/search-engine/SKILL.md. The task is a web search engine with crawler, indexing, ranking, and serving at scale.

The problem

The user types a query and gets ten links. Underneath, you discover pages, decide what is worth fetching, download without harming third-party sites, parse out text, links, and metadata, normalize, deduplicate, build an inverted index, compute offline features, optionally build embeddings, and serve queries in milliseconds with relevant ranking.

The architecture changes with the goal: internal documentation search and public web-scale search are different problems. A search engine is a distributed factory that turns URLs into rankable documents. It is a chain of decisions about what to discover, fetch, store, index, retrieve, and promote, and each stage cuts bad cost and keeps useful signal.

Subsystems

Four subsystems: the crawler discovers and fetches pages, the processing pipeline parses, cleans, extracts, and enriches, the indexing pipeline builds the indexes, and query serving analyzes the query, retrieves candidates, ranks, and assembles the result.

Two support planes sit beside them. Metadata and policy covers robots.txt, politeness, canonical rules, scheduling, and dedup. Observability and control covers metrics, debugging, reprocess, backfill, and allow and block lists.

Requirements

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

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

End-to-end model

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

The frontier picks an eligible URL, the fetcher downloads it, the parser turns bytes into a structured document, and the extractor produces clean text, outlinks, and metadata. The deduplicator decides new, exact, or near-duplicate, and the document store persists the canonical version. Indexing tokenizes and builds postings lists, and offline jobs compute global signals such as link-graph popularity. At query time the analyzer normalizes, the retriever finds candidates, the ranker scores, and the result builder assembles snippets.

Crawler: the URL frontier

The frontier is several structures. The URL-seen store answers whether a URL appeared before (a Bloom filter in front of a persistent store). The crawl-state store holds last attempt status, content hash, HTTP code, response time, and next recrawl window. Scheduler priority queues pick the next URL by priority and politeness.

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

Crawler: per-host queues

One global queue creates hot domains (one heavily linked domain fills the queue) and loses politeness (many concurrent requests to one host look like a DDoS). Use one pending queue per host, each with a next_eligible_timestamp, and a global heap ordering hosts by lowest eligible time and highest priority. When a host becomes eligible, pop a URL, fetch, update backoff, and reinsert the host. This gives fairness and politeness together.

Crawler: canonicalization and politeness

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

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

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

Add a max concurrency per host and exponential backoff on errors so slow sites do not get hammered.

Crawler: fetcher and traps

The fetcher is stateless and I/O-heavy: async networking, connection pooling, DNS cache, TLS reuse, gzip and 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 status code, headers, final URL after redirects, response time, and body checksum.

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

Crawl scheduling

Crawling the whole web daily is out of reach for almost everyone. With a finite budget of requests, bandwidth, and CPU, scheduling is a business decision. A rough score, as intuition rather than a universal formula:

crawl_score ~ quality * freshness_need * business_priority / fetch_cost

Adaptive recrawl beats a fixed cron: a page that changed twice in a short interval gets a shorter window, one unchanged many times gets a longer one, and errors back off. Freshness tiers A, B, C, D (minutes down to rarely) are assigned by domain, URL pattern, or dynamic score.

Deduplication

The same content shows up with and without www, over http and https, with different params, as print pages, syndication, mirrors, republications, and soft duplicates. Dedup at three levels: URL duplicate (same normalized URL), exact content duplicate (same hash of clean text), and near-duplicate (almost equal content).

For near-duplicates, fingerprint with shingles plus 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 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. Consolidate ranking signals (inbound links, clicks) onto the canonical.

Storage by function

The raw content store keeps the original response, compressed, in cheap object storage for reprocessing and audit.

The parsed document store holds doc_id, canonical_url, fetch_time, title, clean_text, language, outgoing_links, anchors_in, headers, content_type, quality_signals, fingerprint.

The crawl metadata store holds 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 or wide-column store fits it better than object storage.

The inverted index

For each term, store 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])]

Each posting carries doc_id, term frequency, positions (for phrase queries), field info (title versus body), and optional payloads.

Build pipeline: tokenize, normalize (lowercase, strip accents, stem or lemmatize), drop stopwords where sensible, emit term → posting pairs, sort-merge by term, compress postings, persist immutable segments, publish a new index version. It distributes naturally as MapReduce (Dean and Ghemawat, 2004) or as streaming with batch compaction.

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

The Lucene model (Doug Cutting) uses immutable segments plus periodic background merges instead of in-place updates. You get cheap sequential writes, simple snapshots, easy rollback, and serving during reindex. You pay with background merge work, deleted docs lingering as tombstones until merge, and higher query cost as segments pile up.

Compress postings or the index explodes: delta encoding of doc ids, variable-byte encoding, frame-of-reference, bit packing, and skip lists to jump over blocks. The goal is fast reads without burning CPU on decompression.

Query serving

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

The analyzer normalizes case, tokenizes, optionally spell-corrects, expands synonyms, detects language, parses operators (quotes, -, site:, filetype:), and classifies intent (navigational, informational, transactional, fresh). Intent changes ranking: the same words can want different things.

Candidate retrieval recalls a candidate set instead of ranking the whole web: BM25 on the lexical index, field filters, title and anchor boosts, optionally ANN search over embeddings, or a hybrid union. Take about 500 to 1000 per shard, then merge.

BM25 (Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond) rewards term frequency with saturation and penalizes long documents, tuned by k1 and b. It is the lexical baseline that strong systems still build on.

Ranking

The final score combines four feature families. 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.

Start with a weighted linear score such as 0.45*bm25 + 0.20*title + 0.15*authority + 0.10*freshness + 0.10*anchor. Move to learning-to-rank only once you have good features and click data, or you buy expensive complexity.

Result assembly builds a highlighted snippet, canonical URL, clean title, breadcrumbs, date when relevant, sitelinks, and dedups near-identical results. Snippet quality drives perceived quality.

Link graph and global signals

Page text alone is not enough. If many relevant pages point to a document, that suggests authority. Build a directed graph (vertices are documents or domains, edges are hyperlinks weighted by context, link position, and anchor text) and run offline batch jobs, daily or hourly and never on the query path, for authority, hub, centrality, and domain reputation.

PageRank (Brin and Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, 1998) defines a page's importance as the stationary distribution of a random surfer following links with a damping factor. Modern practice pairs it with anti-spam checks, since link farms manipulate it. HITS (Kleinberg, 1999) is the related hub and authority formulation.

Spam and quality

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

Freshness versus cost

More freshness costs more crawl and processing; less gives stale results and lost trust. Use tiers: Tier A (very dynamic, high value) recrawled in minutes or hours, Tier B daily, Tier C weekly or monthly, Tier D rarely, assigned by domain, URL pattern, or dynamic score.

Index publishing

Index and documents are rarely in sync in real time, so operate with versions. Workers build new segments, a manifest describes the complete index version, the publisher commits it atomically, and query servers warm up the new version before the swap. You get simple rollback, serving without downtime, and read consistency per version. For frequent updates, combine a base snapshot with smaller delta indexes.

Hybrid search

For general search, lexical stays the foundation and embeddings complement 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 (for example HNSW) for document embeddings, a query embedding generated online or cached, the union of both candidate sets, and the final ranker decides. Generating embeddings, storing vectors, and running ANN at scale cost real money, so add them only when the problem demands it.

Scale and partitioning

Partition the frontier by host hash, one owner per host, so politeness coordination stays in one place. Fetchers are stateless and autoscale. The index runs as, for example, 64 logical shards with 2 to 3 replicas each: a leader publishes segments, followers serve, and rebalancing is gradual. Link-graph jobs run as heavy distributed batch in windows, never on the query path.

Observability

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

Build four debugging tools from the start: URL inspection (crawl and index status of one URL), query explain (which shards answered, candidates, features, final score), a host dashboard (errors, politeness, backlog, blocks per host), and document replay through the pipeline. Without them the team guesses.

Failure modes

Incremental plan

Phase 1, vertical slice: small seed set, HTML only, per-host frontier with basic politeness, simple parser, basic inverted index (Lucene or OpenSearch is fine), BM25 query, URL-inspection tool.

Phase 2, efficiency and quality: exact and near dedup, better canonicalization, adaptive recrawl, initial quality scoring, better snippets, more observability.

Phase 3, real scale: partitioned frontier, distributed fetchers, sharded versioned index, link-graph jobs, multi-factor ranking, disaster recovery and replay.

Phase 4, advanced relevance: learning-to-rank, behavioral signals, hybrid embeddings, personalization, sophisticated anti-spam. Advanced relevance on top of bad ingestion is expensive makeup, so keep the order.

North star

A good crawler chooses well what to download. A good parser survives the broken web and still extracts useful signal. A good index organizes information to retrieve relevant candidates fast. Good ranking combines local signals, global signals, and query intent. Good operations explains fast why something failed and recovers without chaos.

References

Sergey Brin and 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 and 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 and Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004.

Manning, Raghavan and 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 and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, 2016 (ANN for hybrid search).

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