System Design · Lesson 15 of 18

Web Crawler

Frontier design, politeness, dedupe, traps and distributed fetching.

  • Advanced
  • 55 min read
  • 6 objectives

Before this lessonLesson 14: File Storage (Dropbox / Drive)

What you will learn

  • Size a crawler from a freshness target
  • Build a Mercator frontier with per-host politeness
  • Normalise URLs and honour robots.txt
  • Deduplicate URLs with Bloom filters and pages with SimHash
  • Schedule recrawls and defuse crawler traps
  • Partition, checkpoint and recover a distributed crawl

Your Progress

0 of 18 lessons 0%

  • Lessons0 / 18
  • Completed0
  • Est. time left~ 16 hours

Progress is saved in this browser. No account needed.

Tip: pressing Next marks this lesson complete automatically.

Design a web crawler: a system that starts from a set of seed URLs, downloads pages, pulls out the links in them, and keeps going, indefinitely, across billions of pages on hundreds of millions of servers it does not own. Search engines are the obvious customer, but they are not the only one. The same machinery powers web archives, price and SEO monitoring, link checkers, brand and copyright scanning, security scanners, and the text corpora that language models are trained on.

The toy version is twenty lines: a queue, a while loop, requests.get and a regex for href. It is a good interview prompt precisely because every one of those lines breaks at scale, and each breaks differently:

  • The queue becomes tens of billions of URLs that do not fit in memory, must be prioritised, and must be released per host at a polite rate. This is the heart of the design.
  • The loop becomes thousands of concurrent fetches spread over dozens of machines that must never gang up on one small website.
  • "Have I seen this?" becomes a membership test over 40 billion URLs, and a near-duplicate test over billions of documents that differ only in an ad banner.
  • The web itself is adversarial. Infinite calendars, session ids in every link, spam farms, pages that lie to crawlers, and servers that hang forever.
  • The job never ends. Pages change. Keeping a copy fresh is a scheduling problem with a fixed budget, and the naive answer to it is provably worse than doing nothing clever at all.

The sentence to say early: the fetcher is the easy part; the frontier is the design. Most of this lesson is about what sits in front of the HTTP call.

Step 1 — Clarify the requirements

Crawlers vary more by purpose than almost any other prompt, so the clarifying questions genuinely change the design. Ask these:

  • Purpose? A general search-engine crawler, a focused crawler (only product pages, only news), or an archival crawler that must keep every version? Search cares about freshness and importance; archives care about completeness and fidelity.
  • Content types? HTML only, or also PDFs, images, video? If more types are likely later, the parse step must be a pluggable set of processors keyed by MIME type, not one HTML parser.
  • Protocols? HTTP and HTTPS only, or also FTP and others? Same answer: a protocol module per scheme behind one interface, so adding one later is a new class, not a rewrite.
  • One-shot snapshot or continuous? A one-shot crawl has an end. A continuous crawl needs a recrawl scheduler, which is half the system.
  • Scale? How many pages must we hold fresh, and how fresh?
  • JavaScript? Must we see content that only appears after scripts run? Rendering costs 10–50x a plain fetch, so the answer decides the fleet size.
  • Politeness rules? Must we obey robots.txt and crawl-delay? (The answer is yes; say it anyway.)

Functional, in scope for v1

  • Accept seed URLs and continuously discover new URLs from fetched pages.
  • Fetch HTML over HTTP/HTTPS, following redirects, respecting robots.txt, crawl-delay and 429/Retry-After.
  • Skip URLs already known; detect exact and near-duplicate content so mirrors do not flood downstream systems.
  • Store raw responses and extracted metadata (status, headers, outlinks, fingerprints) durably, and emit a "page fetched" event for the indexer.
  • Recrawl known pages on a schedule driven by how often they change and how important they are.
  • Render JavaScript for a small, explicitly chosen subset of hosts.

Explicitly out of scope

The indexer and ranking, PageRank computation itself (we consume a score, we do not compute it), the search front end, logging in to sites, crawling the dark web, and non-HTML media processing beyond storing the bytes. Say these out loud so the interviewer knows where the boundary is.

Non-functional

  • Scale: keep 10 billion pages fresh, with an average revisit cycle of 10 days, and track roughly 40 billion known URLs (you always know about far more pages than you fetch).
  • Freshness: high-value pages (home pages, news) revisited within hours; the long tail within weeks.
  • Politeness: at most one connection per host at a time by default, with at least the host's crawl-delay between requests. This is a hard constraint, not a goal.
  • Robustness: any single machine can die without losing the frontier; a malformed page, a trap or a hung server can only waste a bounded amount of our capacity.
  • Extensibility: new content types, new protocols, and new URL filters are plug-ins.
  • Throughput over latency: no user waits on a fetch. We care about pages per second and freshness, not p99 of a single request. That one fact justifies a lot of batching later.

Step 2 — Back-of-the-envelope estimation

For a crawler the freshness target, not the page count, drives the fetch rate. Start from "10 billion pages every 10 days" and let everything else fall out.

PAGES_TARGET     = 10_000_000_000    # distinct pages we keep fresh
REFRESH_DAYS     = 10                # full refresh cycle for the average page
SECONDS_PER_DAY  = 86_400

# --- Fetch rate: the number every other number hangs off ---
fetch_avg = PAGES_TARGET / (REFRESH_DAYS * SECONDS_PER_DAY)
fetch_peak = fetch_avg * 2           # retries, redirects, robots.txt, bursts
print(f"fetches: {fetch_avg:,.0f}/s avg, {fetch_peak:,.0f}/s provisioned")

# --- Bandwidth ---
avg_html_kb = 100                    # uncompressed; ~1/4 of it on the wire (gzip/br)
wire_kb = avg_html_kb / 4
gbps = fetch_peak * wire_kb * 1000 * 8 / 1e9
print(f"inbound bandwidth: {gbps:,.1f} Gbit/s at peak")

# --- Storage for one full snapshot of raw HTML ---
compressed_kb = avg_html_kb / 5      # gzip in WARC records
snapshot_tb = PAGES_TARGET * compressed_kb * 1000 / 1e12
print(f"one snapshot: {snapshot_tb:,.0f} TB compressed, x3 replicas = {snapshot_tb*3/1000:,.1f} PB")

# --- Frontier: URLs discovered but not yet fetched ---
known_urls = PAGES_TARGET * 4        # the web you know about >> the web you fetch
url_bytes = 100                      # avg URL + priority + host + timestamps
frontier_tb = known_urls * url_bytes / 1e12
print(f"known URLs: {known_urls/1e9:.0f}B -> {frontier_tb:.1f} TB of URL records")

# --- Seen-URL set: exact vs Bloom ---
exact_gb = known_urls * 8 / 1e9      # 64-bit fingerprint per URL
bloom_gb = known_urls * 9.6 / 8 / 1e9  # ~9.6 bits/URL for 1% false positives
print(f"URL-seen: exact 64-bit fps {exact_gb:,.0f} GB, Bloom @1% {bloom_gb:,.0f} GB")

# --- Hosts and politeness ---
hosts = 200_000_000
active_hosts = 20_000_000            # hosts with at least one URL due this cycle
per_host_rate = fetch_avg / active_hosts
print(f"avg per active host: one fetch every {1/per_host_rate:,.0f} s")

# --- Machines ---
fetches_per_node = 400               # async I/O node, bounded by politeness not CPU
print(f"fetcher nodes: ~{fetch_peak / fetches_per_node:,.0f}")
Output
fetches: 11,574/s avg, 23,148/s provisioned
inbound bandwidth: 4.6 Gbit/s at peak
one snapshot: 200 TB compressed, x3 replicas = 0.6 PB
known URLs: 40B -> 4.0 TB of URL records
URL-seen: exact 64-bit fps 320 GB, Bloom @1% 48 GB
avg per active host: one fetch every 1,728 s
fetcher nodes: ~58

What the numbers actually decide

  • ~23k fetches/s is not a CPU problem. A single async node can hold thousands of open connections. The limit is politeness: we have 20 million hosts to spread load over, so the scheduler, not the network card, sets throughput. The ~58 nodes are sized by concurrency and parsing, not bandwidth.
  • 4.6 Gbit/s inbound is real but ordinary for a data-centre footprint. What is expensive is doing it through a stable, reputable set of IP addresses, because hosts rate-limit and block by IP.
  • The frontier is terabytes. 40 billion URL records at ~100 bytes each is ~4 TB. It cannot live in RAM; it is a disk-backed structure with in-memory buffers at the head and tail. Anyone who draws "a Redis list" as the frontier has not done this math.
  • The URL-seen set is the interesting memory question. 320 GB of exact 64-bit fingerprints versus ~48 GB for a Bloom filter at 1% false positives. We will look at what that 1% costs in Step 10.
  • One snapshot is ~200 TB compressed, 0.6 PB replicated. Keeping several historical versions multiplies this, so storage is an object store, compressed, with lifecycle rules, not a database.
  • Per host, the load is tiny on average (one fetch every half hour) but the distribution is brutally skewed: a news site may have 10 million URLs due while a personal blog has three. The design must handle both a host with a queue of millions and 20 million hosts with a queue of one.

Step 3 — Interfaces

A crawler has no public API, but it has three internal interfaces worth defining, and one table (how to react to each HTTP outcome) that interviewers love.

## Control plane (operators and upstream systems)

POST /v1/seeds          { urls: [...], priority: 0-2, source: "sitemap|manual|feed" }
  -> 202 { accepted: 9812, rejected: [{ url, reason: "DENYLISTED" }] }
     # Seeds go through the SAME normalise + filter + seen-test as discovered links.

PUT /v1/hosts/{host}/policy
  { max_concurrency: 1, min_delay_ms: 2000, render_js: false, paused: false }
  -> 200    # manual override: a webmaster complaint is handled in minutes, not a deploy

POST /v1/recrawl        { url, reason: "ping|sitemap_lastmod|manual" } -> 202
  # Push hint (sitemaps, IndexNow-style pings) jumps a URL up the schedule.

GET  /v1/urls/{url_fp}  -> 200 { url, state, last_fetch, next_fetch, status,
                                  content_fp, change_rate, priority }

## Data plane: the event every downstream consumer reads (Kafka topic page.fetched)

{ url, url_fp, host, fetched_at, http_status, final_url, redirect_chain: [...],
  content_type, content_length, etag, last_modified,
  exact_fp: "sha256:...", simhash: "0x9c1e...", is_near_dup_of: null,
  warc: { object: "s3://crawl/2026/09/23/node17-000412.warc.gz", offset, length },
  outlinks_count: 184, render: "none|headless", fetch_ms: 212 }
  # The page body is NOT in the event. Consumers read it by (object, offset, length).

## Processor plug-in contract (extensibility)

interface Protocol  { schemes(); fetch(url, conditional_headers) -> Response }
interface Processor { mime_types(); process(doc: DocumentStream) -> Links, Metadata }
interface UrlFilter { accept(url, context) -> bool | reason }

What each fetch outcome does to the frontier

OutcomeActionWhy
200Store, parse, extract links, update change-rate estimateThe normal path
304 Not ModifiedRecord "unchanged", lengthen revisit intervalConditional GET (If-None-Match / If-Modified-Since) saves the bytes and is the cheapest possible freshness signal
301 / 308Enqueue target, mark source as an alias of itPermanent: future links to the source should resolve to the target
302 / 307Follow up to 5 hops, keep the source as canonicalTemporary: the source is still the address to remember
404 / 410Retire after 2–3 confirmations (410: at once)A single 404 is often a deploy glitch
429 / 503 + Retry-AfterPush the whole host back by Retry-After, double its delayThe server is telling you to slow down. Backing off one URL and hitting the next is still hammering it
Other 5xx, timeout, resetRetry with exponential backoff, host-level circuit breaker after N in a rowA dying server should not consume a fetcher slot every 2 s for a week
DNS NXDOMAINMark host dead, retry the host dailyDomains expire; do not keep resolving them for every URL
Body over 10 MB, or non-HTML typeTruncate / skip processing, store headers onlyA 4 GB ISO behind an innocent link must not stall a fetcher

Step 4 — Data model

Four kinds of state, with very different access patterns. Everything that is per host lives on the node that owns the host (Step 15), so almost nothing needs a cross-node lookup.

-- =========================================================
-- URL STORE (the durable frontier + history)  — RocksDB / Bigtable-style KV
-- key = host_hash(8B) | url_fp(8B)   -> value below
-- Keying by host first keeps one host's URLs contiguous on disk, so the
-- scheduler can scan "all due URLs for host H" as one range read.
-- =========================================================
url_record {
  url            string   -- canonical form (Step 9), needed to actually fetch it
  state          enum     -- DISCOVERED | QUEUED | FETCHED | FAILED | RETIRED
  priority       float    -- importance score (link-based rank, sitemap, depth)
  next_fetch_at  int64    -- set by the recrawl scheduler (Step 13)
  last_fetch_at  int64
  last_status    int16
  etag, last_modified     -- for conditional GET: turns a re-fetch into a 304
  content_fp     bytes8   -- exact hash of the extracted text of the last fetch
  simhash        uint64   -- near-duplicate fingerprint of the last fetch
  change_rate    float    -- estimated changes/day (Step 13)
  fail_count     int8     -- consecutive failures, drives backoff and retirement
  depth          int8     -- hops from a seed, a cheap trap signal
}
-- secondary index for scheduling:  due:(shard, next_fetch_at, url_fp)

-- =========================================================
-- HOST TABLE — one row per host, hot, small (~200M rows, fits in RAM per shard)
-- =========================================================
host_record {
  host              string
  robots_rules      blob     -- parsed robots.txt, plus fetched_at and expires_at
  crawl_delay_ms    int32    -- max(robots crawl-delay, our default, adaptive backoff)
  next_allowed_at   int64    -- the politeness clock (Step 7)
  ips               [ip]     -- cached DNS answer + expiry (Step 11)
  error_streak      int16    -- host-level circuit breaker
  budget_remaining  int32    -- trap guard: max URLs/day we will spend here
  render_js         bool
  quality           float    -- spam score; low values shrink the budget
}

-- =========================================================
-- SEEN SETS
-- =========================================================
url_seen      -- Bloom filter in RAM per shard (fast "definitely new")
              -- + the URL store itself as the exact answer on a Bloom "maybe"
content_seen  -- exact:  KV  sha256(text)[:8]  -> first url_fp with this content
              -- near:   4 tables keyed by one 16-bit SimHash block each (Step 10)

-- =========================================================
-- PAGE STORE — object storage, append-only WARC files
-- =========================================================
s3://crawl/2026/09/23/node17-000412.warc.gz     -- ~1 GB each, many gzip members
  record: WARC/1.1 headers + full HTTP response (status, headers, body)
page_index    -- KV  url_fp|fetched_at  ->  (object, offset, length)
              -- a random read of one page = one ranged GET on one object

-- =========================================================
-- LINK GRAPH — append-only, feeds offline ranking
-- =========================================================
edges (src_fp, dst_fp, anchor_text, fetched_at) -> columnar files, batch jobs

Four modelling decisions to explain

  • Store a fixed-size fingerprint, not just the URL string, as the key. A 64-bit hash of the canonical URL is the identity everywhere: seen-set, events, link graph. The full string is stored once, in the record, because you need it to fetch.
  • The key starts with the host. Politeness and scheduling are per host, so a host's URLs must be one contiguous range. A key of url_fp alone scatters one host across the whole keyspace.
  • Pages go to large append-only WARC files, not one object per page. Ten billion tiny objects is a request-cost and metadata disaster for any object store. Batching thousands of records into 1 GB files and indexing (offset, length) keeps random access to one page at one ranged read.
  • The frontier is a view over the URL store, not a separate copy. "Due URLs" is an index on next_fetch_at. This means a crash cannot lose URLs that are "in the queue" — the queue is derived from durable state.

Step 5 — High-level design

The core loop is the textbook one: pick a URL, resolve its host, fetch it, parse it, test the new links, add the survivors, store the page, repeat. What makes it a system is where each step runs and what sits between them.

flowchart TB SEEDS[Seeds, sitemaps,
recrawl scheduler] --> FR subgraph NODE["Crawl node (owns a slice of hosts)"] FR["URL frontier
front queues = priority
back queues = per host"] ROB["robots.txt cache"] DNS[DNS cache + async resolver] FET["Fetchers (async HTTP)"] DIS[Document stream
fetch once, read many] PROC["Processors by MIME
HTML link extractor, PDF..."] CS{Content seen?
sha256 + SimHash} NORM[Normalise URL] FIL{URL filters +
trap guard} US{URL seen?
Bloom + URL store} FR --> FET ROB -.-> FR DNS --> FET FET --> DIS --> CS CS -->|new| PROC PROC --> NORM --> FIL --> US US -->|new, my host| FR end US -->|new, other host| EX[[URL exchange
batched, by host hash]] EX --> FR2[Frontier on owning node] FET --> RENDER["Render tier
(headless browsers)"] RENDER --> DIS DIS --> WARC[(Object store
WARC files)] CS --> K[("Kafka: page.fetched")] K --> IDX[Indexer] K --> GRAPH[Link graph + ranking] GRAPH -.->|priority scores| FR FR --- US_DB[("URL store + host table
local KV, checkpointed")]

Every node runs the whole pipeline for the hosts it owns. The only cross-node traffic is batched URL hand-off to the owning node, and the only shared services are the object store, Kafka and the ranking feedback loop.

What each component owns

  • URL frontier — which URL to fetch next and when. Priority across URLs, politeness per host. The subject of Step 7.
  • robots.txt cache — fetched once per host per day, consulted before a URL is released. Also supplies crawl-delay.
  • DNS resolver — a local caching resolver with async lookups and prefetch. Without it DNS alone becomes the bottleneck.
  • Fetchers — async HTTP clients with strict timeouts, size caps, redirect limits and conditional headers. Deliberately dumb.
  • Document stream — the fetched bytes, buffered once (in memory up to ~64 KB, spilled to a temp file beyond that) so that the content-seen test, the link extractor, the WARC writer and any other processor can each read it without re-downloading.
  • Content-seen test — exact checksum and SimHash. Duplicates are stored as a pointer and their links are not re-extracted.
  • Processors — one per MIME type. The HTML one extracts <a href>, <link rel=canonical>, meta robots (noindex, nofollow) and text.
  • Normaliser, filters, URL-seen test — turn raw href strings into canonical URLs, drop the unwanted, drop the known.
  • URL exchange — a link found on node 3 that belongs to a host owned by node 41 is batched and shipped there. Only the owner may enqueue it.
  • Render tier — a separate pool of headless browsers for hosts flagged render_js. Isolated because it is 10–50x more expensive and crashes more.
  • Recrawl scheduler — sets next_fetch_at for every fetched URL from its change rate and importance.

Traversal order: BFS, DFS, or neither

The textbook answer is breadth-first: a FIFO queue from the seeds reaches important pages early, because well-linked pages are close to other well-linked pages. Depth-first is useful in one narrow case — once connected to a small site, exhausting it over one kept-alive connection saves handshakes — but as a global strategy it falls into the first deep site or trap it meets. The production answer is best-first: a priority queue ordered by an importance estimate (link-based rank, sitemap priority, depth, host quality), which is what the front queues implement. Mention path-ascending crawling as a discovery trick: when you fetch /a/b/page.html, also enqueue /a/b/, /a/ and /. It finds directory indexes and orphaned sections that nothing links to.

Step 6 — Walk one URL end to end

sequenceDiagram participant F as Frontier participant R as robots cache participant D as DNS cache participant W as Fetcher participant S as shop.example.com participant C as Content-seen participant P as HTML processor participant U as URL-seen participant O as Object store F->>R: may I fetch /shoes/42 ? R-->>F: allowed, crawl-delay 5 s F->>F: host due? next_allowed_at <= now F->>W: release URL, host locked W->>D: resolve shop.example.com D-->>W: 203.0.113.7 (cached) W->>S: GET /shoes/42, If-None-Match "abc" S-->>W: 200, 38 KB, ETag "def" W->>F: done - host next_allowed_at = now + 5 s W->>O: append WARC record W->>C: sha256 + SimHash of extracted text C-->>W: new content W->>P: extract links from document stream P->>U: 184 canonical, filtered URLs U-->>F: 11 are new - enqueue with priority W->>F: schedule recrawl of /shoes/42 in 3 days

The politeness decision happens before the fetch, the politeness clock is advanced the moment the fetch finishes, and everything after the fetch can run off the critical path.

The order of operations, and why

  1. robots.txt before release, not before fetch. Checking in the frontier means a disallowed URL never occupies a fetcher slot or a politeness window.
  2. Politeness is a property of the host, not the URL. The frontier releases a URL only if its host is due, and marks the host busy so a second fetcher cannot hit it concurrently.
  3. Conditional GET whenever we have an ETag or Last-Modified. A 304 costs the server almost nothing, costs us no storage, and is still a freshness signal.
  4. Advance the host clock when the fetch ends, not when it starts. A slow server that took 4 s to respond should get more breathing room, not less. Many crawlers set the gap to a multiple of the last response time.
  5. Write the raw record before any processing. If the parser crashes on a pathological page, the bytes are safe and can be reprocessed; the fetch is never repeated to recover from our own bug.
  6. Content-seen before link extraction. A mirror of a known page has the same links; extracting and testing them again is pure waste.
  7. URL-seen after normalising and filtering. Testing a raw href is useless: ../b?utm_source=x#top and /a/b are the same page, and a filtered URL should not pollute the seen-set.

Step 7 — The URL frontier

This is the deep dive the interviewer wants. The frontier has two jobs that pull in opposite directions: priority (fetch important pages first) and politeness (never hit one host too often). A single priority queue does the first and wrecks the second — the top thousand URLs are often all from the same big site. A single FIFO per host does the second and ignores the first.

The Mercator design: front queues and back queues

  • F front queues, one per priority level. The prioritiser scores each incoming URL and appends it to the matching queue. Only concerns: how important is this?
  • B back queues, each holding URLs for exactly one host. Only concerns: when may this host be hit again? Rule of thumb: B ≈ 3x the number of fetcher threads, so there is always a due host.
  • A min-heap of (next_allowed_at, host) over the back queues. A fetcher pops the heap top; if it is due, it takes one URL from that host's queue. After the fetch, the host is pushed back with now + delay.
  • A router between them. When a back queue empties, its slot is freed and refilled by pulling from the front queues with a biased random choice (priority 0 picked more often, low priorities never fully starved). A pulled URL whose host already has a back queue joins that queue; otherwise it claims the free slot.
flowchart LR IN[New and due URLs] --> PRIO[Prioritiser] PRIO --> F0["Front queue 0
(high)"] PRIO --> F1["Front queue 1"] PRIO --> F2["Front queue 2
(low)"] F0 --> SEL["Biased selector
weights 4 : 2 : 1"] F1 --> SEL F2 --> SEL SEL --> ROUTER[Back-queue router
host to queue map] ROUTER --> B1["Back queue: news.example.com"] ROUTER --> B2["Back queue: blog.example.org"] ROUTER --> B3["Back queue: archive.example.net"] B1 --> HEAP["Min-heap
(next_allowed_at, host)"] B2 --> HEAP B3 --> HEAP HEAP --> T1[Fetcher 1] HEAP --> T2[Fetcher 2]

Front queues answer "what matters", back queues answer "who is allowed now". Separating them is the whole trick.

Here is a runnable, single-process version with a simulated clock. Three hosts, four URLs from a high-priority news host with a 2-second crawl-delay, and lower-priority URLs from two other hosts using the default 1 second.

import heapq, itertools, random
from collections import deque
from urllib.parse import urlsplit

class MercatorFrontier:
    """Front queues decide WHAT is important. Back queues decide WHEN a host
    may be hit again. A heap of (next_allowed_time, host) glues them together."""

    def __init__(self, num_priorities=3, num_back_queues=4, seed=7):
        self.front = [deque() for _ in range(num_priorities)]   # 0 = highest
        self.weights = [2 ** (num_priorities - 1 - i) for i in range(num_priorities)]
        self.max_back = num_back_queues
        self.back: dict[str, deque] = {}        # host -> its URLs (one host per queue)
        self.ready: list[tuple[float, int, str]] = []  # heap: (next_allowed_at, seq, host)
        self.seq = itertools.count()            # tie-break: first routed, first served
        self.delay: dict[str, float] = {}       # per-host politeness delay (robots)
        self.rng = random.Random(seed)

    # ---------- producer side ----------
    def add(self, url: str, priority: int):
        self.front[priority].append(url)

    def set_delay(self, host: str, seconds: float):
        self.delay[host] = seconds

    # ---------- the front -> back router ----------
    def _pull_from_front(self):
        """Biased random pick: priority 0 is chosen 4x as often as priority 2,
        but low priorities are never starved completely."""
        nonempty = [i for i, q in enumerate(self.front) if q]
        if not nonempty:
            return None
        i = self.rng.choices(nonempty, weights=[self.weights[j] for j in nonempty])[0]
        return self.front[i].popleft()

    def _refill(self, now: float):
        # Route URLs until every back-queue slot is occupied by some host.
        while len(self.back) < self.max_back:
            url = self._pull_from_front()
            if url is None:
                return
            host = urlsplit(url).hostname
            if host in self.back:
                self.back[host].append(url)     # host already has a queue: join it
            else:
                self.back[host] = deque([url])  # new host takes a free slot
                heapq.heappush(self.ready, (now, next(self.seq), host))

    # ---------- consumer side (a fetcher thread) ----------
    def next_url(self, now: float):
        """Returns (url, host) if a host is due, else (None, wait_seconds)."""
        self._refill(now)
        if not self.ready:
            return None, None
        t, _, host = self.ready[0]
        if t > now:
            return None, t - now                # nothing due yet: sleep this long
        heapq.heappop(self.ready)
        return self.back[host].popleft(), host

    def done(self, host: str, now: float, fetch_seconds: float):
        """Called after the fetch completes. The next slot for this host is
        pushed out by max(robots delay, 10x the time the server took)."""
        gap = max(self.delay.get(host, 1.0), 10 * fetch_seconds)
        if self.back[host]:
            heapq.heappush(self.ready, (now + gap, next(self.seq), host))
        else:
            del self.back[host]                 # free the slot for another host

f = MercatorFrontier()
f.set_delay("news.example.com", 2.0)
for i in range(4):
    f.add(f"https://news.example.com/story/{i}", priority=0)
for i in range(3):
    f.add(f"https://blog.example.org/post/{i}", priority=1)
for i in range(3):
    f.add(f"https://archive.example.net/page/{i}", priority=2)

now, log = 0.0, []
while True:
    url, info = f.next_url(now)
    if url is None:
        if info is None:
            break                                # frontier empty
        now += info                              # sleep until a host is due
        continue
    fetch_time = 0.05                            # pretend each fetch takes 50 ms
    now += fetch_time
    f.done(info, now, fetch_time)
    log.append((round(now, 2), url.split("//")[1]))

for t, u in log:
    print(f"t={t:5.2f}s  {u}")
news = [t for t, u in log if u.startswith("news")]
print("news.example.com gaps:", [round(b - a, 2) for a, b in zip(news, news[1:])])
Output
t= 0.05s  news.example.com/story/0
t= 0.10s  blog.example.org/post/0
t= 0.15s  archive.example.net/page/0
t= 1.15s  blog.example.org/post/1
t= 1.20s  archive.example.net/page/1
t= 2.10s  news.example.com/story/1
t= 2.20s  blog.example.org/post/2
t= 2.25s  archive.example.net/page/2
t= 4.15s  news.example.com/story/2
t= 6.20s  news.example.com/story/3
news.example.com gaps: [2.05, 2.05, 2.05]

Read the log the way an interviewer would. The news host is served first because it is highest priority, but its four URLs are spread exactly 2.05 s apart (2 s crawl-delay plus the 50 ms fetch), while the fetcher fills the gaps with the other two hosts at their 1 s pace. No host is ever hit faster than its delay, and the fetcher is never idle while any host is due. That is priority and politeness at once.

Making it real: the frontier on disk

  • Buffered queues. Each queue keeps an in-memory tail buffer for appends and an in-memory head buffer for pops; the middle lives in sequential disk segments. Appends are batched writes, pops are batched reads, and the disk only ever sees sequential I/O.
  • Recrawls enter through the same door. The scheduler scans the due index for URLs whose next_fetch_at has passed and feeds them to the prioritiser like newly discovered ones.
  • Politeness by IP, not just hostname. Thousands of small sites share one IP on shared hosting. Keying back queues by hostname alone can hit one physical server from 500 back queues at once. Production crawlers apply a second limit per IP (or per /24) using the cached DNS answer.
  • Adaptive delay. delay = max(robots crawl-delay, default, k × last_response_time), doubled on 429/503 and slowly decayed after successes. Servers that answer fast can take more; servers that struggle get less.
  • Prioritisation signals. Link-based importance from the previous crawl's graph, sitemap priority and lastmod, depth from seed, host quality, and for recrawls, expected staleness (Step 13).

Wrong answers candidates give

  • "A distributed queue like Kafka or SQS is the frontier." A message queue delivers in arrival order and cannot answer "the next URL for a host that is due." You would pop a URL, find its host busy, and requeue it, forever. Kafka is fine for moving URLs between nodes; it is not the scheduler.
  • "Sleep for the crawl-delay in the fetcher thread." That parks a thread per host per delay. With 20 million hosts, the fetcher pool is asleep. The heap turns waiting into a timestamp.
  • "Lock the host in Redis." A global lock service for 23k fetches/s works but is pointless: if one node owns each host (Step 15), politeness is a local variable.

Step 8 — Politeness and robots.txt

The Robots Exclusion Protocol (standardised as RFC 9309 in 2022) lets a site publish /robots.txt: groups of rules per User-agent, each with Allow and Disallow path prefixes. Details that matter:

  • Most specific user-agent group wins; a crawler follows the group naming it, or * if none does. It does not merge groups.
  • Within a group, the longest matching path wins, and Allow wins a tie. (Python's urllib.robotparser uses first match instead, which is why the example below lists Allow before the broader Disallow.)
  • Status codes decide the default. A 4xx means "no rules": crawl everything. A 5xx or timeout means "assume everything is disallowed" and retry later — the server may be overloaded, and a crawler that treats an error as permission is the one that gets blocked.
  • Crawl-delay is non-standard but widely published; respect it anyway. Also honour Sitemap: lines as a discovery source.
  • Page-level signals complement it: <meta name="robots" content="noindex,nofollow">, the X-Robots-Tag header, and rel="nofollow" on links.
  • Cache it. One robots fetch per host per ~24 h, never one per URL. The cache is per host and lives on the node that owns the host.
import time
from urllib.robotparser import RobotFileParser

AGENT = "StackconeBot"
ROBOTS_TTL = 24 * 3600          # re-fetch robots.txt at most once a day per host

# Stand-in for the network: what each host's /robots.txt returns.
FAKE_WEB = {
    "shop.example.com": (200, """
User-agent: *
Disallow: /cart
Disallow: /search
Crawl-delay: 2

User-agent: StackconeBot
Disallow: /cart
Allow: /search/popular
Disallow: /search
Crawl-delay: 5
"""),
    "blog.example.org": (404, ""),              # no file -> everything allowed
    "flaky.example.net": (503, ""),             # server error -> assume disallow
}

class RobotsCache:
    def __init__(self, fetch, clock=time.monotonic):
        self._fetch, self._clock = fetch, clock
        self._cache: dict[str, tuple[float, RobotFileParser | None, str]] = {}
        self.fetches = 0

    def _load(self, host):
        self.fetches += 1
        status, body = self._fetch(host)
        rp = RobotFileParser()
        if 200 <= status < 300:
            rp.parse(body.splitlines()); mode = "rules"
        elif 400 <= status < 500:
            rp.parse([]); mode = "allow-all"      # 4xx: no rules published
        else:
            rp = None; mode = "deny-all"          # 5xx/timeout: back off, retry later
        ttl = ROBOTS_TTL if mode != "deny-all" else 3600
        self._cache[host] = (self._clock() + ttl, rp, mode)

    def _entry(self, host):
        e = self._cache.get(host)
        if e is None or e[0] < self._clock():
            self._load(host); e = self._cache[host]
        return e

    def allowed(self, host, path):
        _, rp, mode = self._entry(host)
        return False if rp is None else rp.can_fetch(AGENT, f"https://{host}{path}")

    def crawl_delay(self, host, default=1.0):
        _, rp, _ = self._entry(host)
        d = rp.crawl_delay(AGENT) if rp else None
        return float(d) if d is not None else default

robots = RobotsCache(fetch=lambda h: FAKE_WEB.get(h, (404, "")))
checks = [("shop.example.com", "/shoes/42"), ("shop.example.com", "/cart/checkout"),
          ("shop.example.com", "/search/popular"), ("shop.example.com", "/search?q=x"),
          ("blog.example.org", "/post/1"), ("flaky.example.net", "/")]
for host, path in checks:
    print(f"{host + path:36} allowed={robots.allowed(host, path)}")
print("crawl-delay shop:", robots.crawl_delay("shop.example.com"), "s")
print("robots.txt fetches for", len(checks), "checks:", robots.fetches)
Output
shop.example.com/shoes/42            allowed=True
shop.example.com/cart/checkout       allowed=False
shop.example.com/search/popular      allowed=True
shop.example.com/search?q=x          allowed=False
blog.example.org/post/1              allowed=True
flaky.example.net/                   allowed=False
crawl-delay shop: 5.0 s
robots.txt fetches for 6 checks: 3

Six decisions, three robots fetches, and the default for each failure mode is the conservative one. Note that StackconeBot gets its own group (5 s delay, /search/popular allowed) rather than the * group — the most specific group wins entirely.

Two more politeness habits worth mentioning: identify yourself with a descriptive User-Agent that includes a URL explaining the crawler and a contact address, and publish the IP ranges you crawl from so site owners can verify you. A crawler that hides is treated as an attacker.

Step 9 — URL normalisation and filters

The same page appears under dozens of spellings: different case in the host, an explicit default port, /./ and /../ segments, a fragment, tracking parameters, reordered query strings. Without normalisation, every spelling is a "new" URL, and the URL-seen test is useless. Normalise before the seen-test, and store only canonical forms.

from urllib.parse import urlsplit, urlunsplit, urljoin, parse_qsl, urlencode, quote, unquote
import posixpath

TRACKING = {"utm_source", "utm_medium", "utm_campaign", "utm_term",
            "utm_content", "gclid", "fbclid", "sessionid", "phpsessid", "sid"}
DEFAULT_PORT = {"http": 80, "https": 443}
SAFE_PATH = "/:@!$&'()*+,;=-._~"     # RFC 3986 characters that stay unescaped

def normalize(base: str, href: str) -> str | None:
    url = urljoin(base, href.strip())
    p = urlsplit(url)
    scheme = p.scheme.lower()
    if scheme not in DEFAULT_PORT:
        return None                   # mailto:, javascript:, ftp: -> not ours
    host = (p.hostname or "").lower().rstrip(".")
    if not host:
        return None
    host = host.encode("idna").decode("ascii")      # unicode host -> punycode
    port = p.port
    netloc = host if port in (None, DEFAULT_PORT[scheme]) else f"{host}:{port}"

    # Resolve /./ and /../, keep a trailing slash, re-encode consistently.
    path = p.path or "/"
    trailing = path.endswith("/")
    path = posixpath.normpath(unquote(path))
    if path == ".":
        path = "/"
    if trailing and not path.endswith("/"):
        path += "/"
    path = quote(path, safe=SAFE_PATH)

    # Drop tracking/session params, sort the rest so order does not matter.
    params = [(k, v) for k, v in parse_qsl(p.query, keep_blank_values=True)
              if k.lower() not in TRACKING]
    query = urlencode(sorted(params))

    return urlunsplit((scheme, netloc, path, query, ""))   # fragment dropped

base = "https://Shop.Example.com:443/catalog/shoes/index.html"
for href in ["../bags/?utm_source=mail&color=red&size=9#reviews",
             "./?size=9&color=red",
             "HTTP://shop.example.com:80/a/./b/../c",
             "/caf%C3%A9 menu",
             "https://bücher.example/",
             "mailto:sales@example.com",
             "javascript:void(0)"]:
    print(f"{href!r:52} -> {normalize(base, href)}")
Output
'../bags/?utm_source=mail&color=red&size=9#reviews'  -> https://shop.example.com/catalog/bags/?color=red&size=9
'./?size=9&color=red'                                -> https://shop.example.com/catalog/shoes/?color=red&size=9
'HTTP://shop.example.com:80/a/./b/../c'              -> http://shop.example.com/a/c
'/caf%C3%A9 menu'                                    -> https://shop.example.com/caf%C3%A9%20menu
'https://bücher.example/'                            -> https://xn--bcher-kva.example/
'mailto:sales@example.com'                           -> None
'javascript:void(0)'                                 -> None

Rules, and where to stop

  • Always safe: lowercase scheme and host, drop default ports, drop the fragment (the server never sees it), resolve dot segments, consistent percent-encoding, punycode for international hosts.
  • Safe with a list: drop known tracking and session parameters (utm_*, gclid, sessionid). Session ids in URLs are one of the classic ways to crawl one site infinitely.
  • Usually safe: sorting query parameters. Almost every server ignores order; a few do not.
  • Not safe globally: lowercasing the path, stripping www., removing index.html, or dropping all query strings. Some servers treat those as different resources. Learn these per host instead: if two URL variants on a host keep producing the same content hash, add a host-specific rewrite rule.
  • Let the site tell you: <link rel="canonical"> and 301 redirects are the site's own normalisation. Record the alias, and fetch the canonical.

URL filters

Filters run after normalisation and before the seen-test, and are a plug-in chain: deny-listed domains (spam, malware, legal takedowns), allowed schemes, allowed TLDs or domains for a focused crawl, extension filters (skip .zip, .iso, .mp4 for an HTML crawler), maximum URL length, and the trap guard in Step 14. Each filter returns a reason, which is logged — "why did we never crawl X?" is a question operators ask weekly.

Step 10 — Deduplication: URLs and content

Two separate questions, often confused in interviews: have I seen this address? (URL-seen) and have I seen this content? (content-seen). The first saves fetches; the second saves storage and indexing, and stops mirrors from diluting results. Roughly a quarter to a third of fetched pages are exact or near duplicates of something else.

URL-seen: exact store vs Bloom filter

An exact set of 40 billion 64-bit fingerprints is 320 GB — feasible on disk, partitioned by host, with a hot in-memory cache (popular URLs like a site's home page are linked from every page, so the cache hit rate is high). A Bloom filter is the classic space saver: a bit array of m bits and k hash functions. Adding sets k bits; a lookup that finds any of them unset proves the item is new. It never says "new" for something seen (no false negatives), but it can say "seen" for something new, with probability

p ≈ (1 − e−kn/m)k, minimised at k = (m/n) ln 2, which gives m = −n ln p / (ln 2)2 — about 9.6 bits per item for 1%, 14.4 for 0.1%.

import hashlib, math

def bloom_params(n: int, p: float) -> tuple[int, int]:
    """Optimal bit count m and hash count k for n items at false-positive rate p."""
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    k = max(1, round(m / n * math.log(2)))
    return m, k

def fp_rate(m: int, n: int, k: int) -> float:
    return (1 - math.exp(-k * n / m)) ** k

class BloomFilter:
    def __init__(self, n: int, p: float):
        self.m, self.k = bloom_params(n, p)
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        # Kirsch-Mitzenmacher: two base hashes simulate k independent ones.
        d = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little") | 1
        return ((h1 + i * h2) % self.m for i in range(self.k))

    def add(self, item: str):
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item: str) -> bool:
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

# ---- the math at crawler scale ----
for p in (0.01, 0.001, 0.0001):
    m, k = bloom_params(40_000_000_000, p)
    print(f"40B URLs @ p={p:<7} -> {m/8/1e9:6.1f} GB, k={k:2d}, {m/40e9:4.1f} bits/URL")

# ---- empirical check on a small filter ----
n, p = 50_000, 0.01
bf = BloomFilter(n, p)
for i in range(n):
    bf.add(f"https://site{i % 997}.example/page/{i}")
false_hits = sum(f"https://other{i}.example/x/{i}" in bf for i in range(100_000))
print(f"\nsmall filter: m={bf.m:,} bits, k={bf.k}, {len(bf.bits)/1024:.0f} KiB")
print(f"all inserted found: {all(f'https://site{i % 997}.example/page/{i}' in bf for i in range(n))}")
print(f"measured FP rate: {false_hits/100_000:.4f}   predicted: {fp_rate(bf.m, n, bf.k):.4f}")

# ---- what happens if you under-size it (the real production failure) ----
for load in (1, 2, 4):
    print(f"filled to {load}x design capacity -> FP {fp_rate(bf.m, n * load, bf.k):.1%}")
Output
40B URLs @ p=0.01    ->   47.9 GB, k= 7,  9.6 bits/URL
40B URLs @ p=0.001   ->   71.9 GB, k=10, 14.4 bits/URL
40B URLs @ p=0.0001  ->   95.9 GB, k=13, 19.2 bits/URL

small filter: m=479,253 bits, k=7, 59 KiB
all inserted found: True
measured FP rate: 0.0098   predicted: 0.0100
filled to 1x design capacity -> FP 1.0%
filled to 2x design capacity -> FP 15.7%
filled to 4x design capacity -> FP 67.9%

What a false positive costs a crawler, and the fix

  • The failure is silent. A false positive says "seen" for a URL we have never fetched, so that page is never crawled. At 1%, that is 1 in 100 genuinely new pages lost forever, and you will never find out which.
  • Overfill is catastrophic. The last lines show it: a filter sized for 50k items that holds 100k has a 16% false-positive rate. The URL space grows every week, so size for the future and rebuild (or use a scalable Bloom filter that adds layers) before you get there.
  • The production pattern: the exact store is the truth, the Bloom filter is a shortcut. A Bloom "no" is certain, so a genuinely new URL is confirmed new without a disk read. A Bloom "maybe" goes to the exact store to confirm. No page is ever lost to a false positive; the false-positive rate only decides how many extra disk reads you do. Most extracted links point to URLs we already know (every page links to its site's home page and navigation), so those "maybe" answers are served by a small in-memory cache of popular fingerprints before they reach disk.
  • Batch the disk checks. Instead of one random read per link, collect a few hundred thousand candidate fingerprints, sort them, and merge them against the sorted on-disk set in one sequential pass. Throughput goes up by orders of magnitude, and latency does not matter here (Step 1).
  • Bloom filters cannot delete. If URLs must expire from the seen-set, use a counting Bloom filter or a cuckoo filter, at 3–4x the memory.

Content-seen: exact checksums

Hash the extracted text (not the raw HTML, which contains timestamps and ad slots) with SHA-256 and keep the first 8 bytes: 10 billion documents is 80 GB of fingerprints, partitioned by fingerprint prefix. An exact match means a byte-identical copy: store a pointer to the original, do not extract links, do not index. Exact hashing catches mirrors and http/https twins, but one changed character defeats it.

Content-seen: SimHash for near-duplicates

Most duplicates are near-duplicates: the same article with a different footer, date, or ad block. SimHash (Charikar; used by Google's crawler) gives similar documents similar fingerprints: every word shingle hashes to 64 bits and votes +1 or −1 on each bit position; the final fingerprint keeps the sign of each total. Documents that share most shingles share most votes, so their fingerprints differ in few bits, and similarity becomes Hamming distance.

import hashlib, re

def shingles(text: str, k: int = 3):
    words = re.findall(r"[a-z0-9]+", text.lower())
    return [" ".join(words[i:i + k]) for i in range(max(1, len(words) - k + 1))]

def h64(s: str) -> int:
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

def simhash(text: str, bits: int = 64) -> int:
    """Every shingle votes +1/-1 on every bit. Similar documents share most
    shingles, so most votes, so most final bits."""
    v = [0] * bits
    for sh in shingles(text):
        h = h64(sh)
        for b in range(bits):
            v[b] += 1 if (h >> b) & 1 else -1
    return sum(1 << b for b in range(bits) if v[b] > 0)

def hamming(a: int, b: int) -> int:
    return bin(a ^ b).count("1")

base = ("The city council approved the new riverside park on Tuesday after a "
        "two hour debate. Construction starts in March and the park will include "
        "a playground, a cycling track, public toilets and four hundred new trees. "
        "The budget is twelve million and the project should finish next autumn.")
docs = {
    "original":        base,
    "mirror + footer": base + " Copyright 2026 Example Mirror. All rights reserved.",
    "one edit":        base.replace("four hundred", "five hundred"),
    "ad + nav chrome": "Home News Sport Weather " + base + " Advertisement Sign up now",
    "different story": ("Local football club signs a new striker from abroad for a record "
                        "fee. The manager says the player will start on Saturday against "
                        "the league leaders and fans have already sold out the stadium."),
}
# Short demo texts have few shingles, so fingerprints are noisier than for a real
# page with thousands of shingles and boilerplate stripped (there, ~3 bits is typical).
THRESHOLD = 12
ref = simhash(docs["original"])
exact = hashlib.sha256(docs["original"].encode()).hexdigest()[:12]
for name, text in docs.items():
    sh = simhash(text)
    same_sha = hashlib.sha256(text.encode()).hexdigest()[:12] == exact
    d = hamming(ref, sh)
    verdict = "near-duplicate" if d <= THRESHOLD else "distinct"
    print(f"{name:16} sha256-equal={str(same_sha):5}  hamming={d:2d}  -> {verdict}")

# Finding candidates among billions: if two 64-bit prints differ in <= 3 bits,
# then split into 4 blocks of 16, at least one block matches EXACTLY (pigeonhole).
# So index every print under its 4 blocks and only compare within a bucket.
from collections import defaultdict
index = defaultdict(list)
def blocks(fp): return [(i, (fp >> (16 * i)) & 0xFFFF) for i in range(4)]
for name, text in docs.items():
    for blk in blocks(simhash(text)):
        index[blk].append(name)
probe = simhash(docs["mirror + footer"])
candidates = {n for blk in blocks(probe) for n in index[blk]}
print("bucket candidates for 'mirror + footer':", sorted(candidates))
Output
original         sha256-equal=True   hamming= 0  -> near-duplicate
mirror + footer  sha256-equal=False  hamming= 6  -> near-duplicate
one edit         sha256-equal=False  hamming= 6  -> near-duplicate
ad + nav chrome  sha256-equal=False  hamming=10  -> near-duplicate
different story  sha256-equal=False  hamming=32  -> distinct
bucket candidates for 'mirror + footer': ['mirror + footer', 'one edit']

SHA-256 considers only the first document equal to itself. SimHash places the mirror, the one-word edit and the version wrapped in navigation chrome close to the original, and the unrelated story around 32 bits away — what you expect for two random 64-bit values. The last line shows the lookup trick and its limit: the 4-block index guarantees finding everything within 3 bits, so "one edit" (6 bits from the probe but sharing a block by luck) is found, while "original" is not. To search a wider radius you need more, smaller blocks — for a threshold of d bits, at least d+1 blocks, and the tables multiply. That is the real engineering trade-off: recall radius against index copies.

Do not confuse the two probabilistic tools: Bloom filters answer exact membership approximately; SimHash answers approximate similarity. Using a Bloom filter for near-duplicate detection is a common wrong answer.

Step 11 — DNS resolution

Every fetch needs an IP address, and DNS is a hidden bottleneck: a public resolver takes 10–200 ms per lookup, many system resolver libraries are synchronous (one blocked thread per lookup), and 23k fetches/s of uncached lookups is enough to get you rate-limited by upstream resolvers.

  • Run your own caching resolver per node (or per rack). Hosts repeat heavily — a host with 10,000 due URLs needs one lookup, not 10,000 — so hit rates above 95% are normal.
  • Respect TTLs, with a floor and a ceiling (say, at least 5 minutes, at most a day). A floor stops hosts with 30 s TTLs from dominating; a ceiling stops stale answers for hosts that moved.
  • Resolve asynchronously and ahead of time. When a host is routed into a back queue, prefetch its address, so the lookup is done before the host is due.
  • Cache failures too. NXDOMAIN for a dead domain should be remembered for hours, not retried for every URL.
  • The DNS answer feeds politeness. The IP is what the per-IP limit keys on (Step 7).

Step 12 — Fetching and the JavaScript rendering tier

The HTML fetcher

  • Async I/O, not a thread per request. Most of a fetch is waiting for bytes. An event loop per core holds thousands of connections.
  • Strict limits on everything: connect timeout ~5 s, total ~30 s, max body ~10 MB (truncate, keep what you have), max 5 redirects, drop connections that trickle bytes slowly (a "tarpit" can keep a connection open for hours at one byte per second).
  • Keep-alive per host when fetching several URLs in a row from one host, and HTTP/2 where offered — cheaper for the server too.
  • Accept compression (gzip, br) to cut bandwidth ~4x.
  • Check the Content-Type header before downloading the body, and abort early if it is not a type any processor wants.
  • Protocol modules by scheme behind one interface — the extensibility requirement, satisfied without touching the loop.

When pages need a browser

Many modern sites ship an almost empty HTML shell and build the content with JavaScript. A plain fetch sees nothing. Rendering means running a headless browser: load the page, execute scripts, wait for the network to settle, then serialise the DOM.

  • Cost: 1–5 s of CPU and hundreds of MB of RAM per page, versus milliseconds for a plain fetch. Render everything and the fleet becomes 10–50x larger.
  • So render selectively, as a second pass. Fetch everything plainly first. Queue a page for rendering only if the host is flagged, or a cheap heuristic fires: very little text but a large script bundle, a known single-page-app framework marker, or links that exist only in script.
  • A separate tier with its own queue and budget. Browsers crash, leak memory and hang; isolate them, recycle each process after N pages, and give each page a hard wall-clock limit.
  • Politeness applies to the sub-requests too. One rendered page may trigger 50 requests for scripts, images and APIs. Cache static assets across pages and block images, fonts and trackers, which are irrelevant to the text.

Step 13 — Freshness: recrawl scheduling

For a continuous crawler, deciding when to come back is as important as discovering new pages. The budget is fixed (23k fetches/s), so the question is how to split it across 10 billion pages that change at wildly different rates — a live-score page every few minutes, an "about us" page once a year.

  • Estimate each page's change rate. Every revisit tells you whether the content fingerprint changed. The naive rate (changes seen ÷ time) under-counts, because two edits between visits look like one; the estimator below corrects for that.
  • Freshness of a page is the fraction of time our copy matches the live page. For changes arriving as a Poisson process at rate λ and revisits every I days, expected freshness is (1 − e−λI) / (λI).
  • Allocate revisits to maximise importance-weighted freshness. The gains are concave, so a greedy allocation is optimal.
import heapq, math

def estimate_change_rate(visits: int, changes_seen: int, interval_days: float) -> float:
    """Changes per day, from 'we visited n times at interval I and saw X changes'.
    Naive X/(n*I) under-counts: two edits between visits look like one. This
    bias-corrected estimator (Cho & Garcia-Molina) accounts for that."""
    return -math.log((visits - changes_seen + 0.5) / (visits + 0.5)) / interval_days

def freshness(rate: float, visits_per_day: float) -> float:
    """Expected fraction of time our copy is current, for Poisson changes at
    `rate`/day and a revisit every 1/visits_per_day days."""
    if visits_per_day == 0:
        return 0.0
    x = rate / visits_per_day
    return (1 - math.exp(-x)) / x

print("estimated rate (10 visits, 1/day):",
      [round(estimate_change_rate(10, x, 1.0), 2) for x in (1, 5, 9, 10)], "changes/day")

pages = {                       # name: (true change rate per day, importance weight)
    "homepage":      (24.0, 5.0),
    "live-scores":   (96.0, 2.0),
    "category-page": (2.0,  3.0),
    "product-page":  (0.3,  2.0),
    "blog-post":     (0.05, 1.0),
    "about-us":      (0.01, 1.0),
}
BUDGET = 60.0                   # fetches per day we can spend on these six pages

def score(alloc):
    total_w = sum(w for _, w in pages.values())
    return sum(w * freshness(r, alloc[p]) for p, (r, w) in pages.items()) / total_w

uniform = {p: BUDGET / len(pages) for p in pages}
total_rate = sum(r for r, _ in pages.values())
proportional = {p: BUDGET * r / total_rate for p, (r, _) in pages.items()}

# Greedy: hand out the budget in small steps to whichever page gains the most
# weighted freshness from one more step. Concave gains -> greedy is optimal.
step, optimal = 0.25, {p: 0.0 for p in pages}
def gain(p):
    r, w = pages[p]
    return w * (freshness(r, optimal[p] + step) - freshness(r, optimal[p]))
heap = [(-gain(p), p) for p in pages]; heapq.heapify(heap)
for _ in range(int(BUDGET / step)):
    _, p = heapq.heappop(heap)
    optimal[p] += step
    heapq.heappush(heap, (-gain(p), p))

print(f"\n{'page':14} {'rate/day':>8} {'uniform':>8} {'proport.':>8} {'optimal':>8}")
for p, (r, _) in pages.items():
    print(f"{p:14} {r:8.2f} {uniform[p]:8.1f} {proportional[p]:8.1f} {optimal[p]:8.2f}")
for name, a in (("uniform", uniform), ("proportional", proportional), ("optimal", optimal)):
    print(f"weighted freshness, {name:12}: {score(a):.3f}")
Output
estimated rate (10 visits, 1/day): [0.1, 0.65, 1.95, 3.04] changes/day

page           rate/day  uniform proport.  optimal
homepage          24.00     10.0     11.8    44.00
live-scores       96.00     10.0     47.1     0.00
category-page      2.00     10.0      1.0    11.00
product-page       0.30     10.0      0.1     3.50
blog-post          0.05     10.0      0.0     1.00
about-us           0.01     10.0      0.0     0.50
weighted freshness, uniform     : 0.628
weighted freshness, proportional: 0.427
weighted freshness, optimal     : 0.749

The counter-intuitive result

Proportional allocation — "revisit pages as often as they change" — is the answer most candidates give, and it scores worse than uniform. It spends almost half the budget on live-scores, which changes 96 times a day: even 47 visits a day leave it stale most of the time, so those fetches buy very little freshness. The optimal allocation gives up on the page it cannot keep fresh and spends the budget where each visit moves the needle: the heavily weighted homepage and the category page. (In practice you would still fetch live-scores occasionally for discovery; freshness is not the only goal.) This is a well-known result from the crawler literature and a strong thing to say in an interview.

Signals beyond the estimator

  • Push beats pull: sitemaps with lastmod, RSS/Atom feeds, and ping protocols (such as IndexNow) tell you a page changed. Treat them as hints and verify, since they are sometimes wrong.
  • Conditional GET makes checking an unchanged page almost free for both sides, so you can afford to check more often than you download.
  • Only meaningful changes count. A changed timestamp or rotating ad should not count as a change; compare SimHash distance or the extracted main text, not raw bytes.
  • New pages have no history: start with the host's or the URL pattern's average rate, and adapt.

Step 14 — Crawler traps and spam

A crawler trap is any part of a site that generates an unbounded number of URLs. Some are accidents: a calendar with a "next month" link that never ends, faceted search where every filter combination is a URL, a session id added to every link, relative links on a misconfigured "page not found" page that produce /a/b/a/b/a/b/…, or symbolic-link loops on a file server. Some are deliberate: link generators built to waste crawler capacity or catch email harvesters. Then there is spam: link farms built to inflate ranking, and cloaking, where a server shows the crawler different content from what users see.

No single rule catches all traps, so the defence is layered: cheap static checks, then budgets that cap the damage anything unanticipated can do.

import re
from collections import Counter, defaultdict
from urllib.parse import urlsplit, parse_qsl

MAX_URL_LEN, MAX_DEPTH, MAX_PARAMS, MAX_REPEAT = 2048, 12, 6, 2
BLOCKED_EXT = re.compile(r"\.(jpg|jpeg|png|gif|zip|exe|mp4|mp3|iso|dmg)$", re.I)
DENY_HOSTS = {"spam-farm.example"}

class TrapGuard:
    """Static rules reject obviously bad URLs. Per-host budgets catch the
    infinite spaces no static rule can predict."""
    def __init__(self, per_host_budget=1000, per_pattern_budget=50):
        self.per_host = Counter()
        self.per_pattern = defaultdict(Counter)
        self.host_budget, self.pattern_budget = per_host_budget, per_pattern_budget

    @staticmethod
    def pattern(path: str) -> str:
        # /calendar/2031/07/14 -> /calendar/N/N/N : one "shape" of URL
        return re.sub(r"\d+", "N", path)

    def check(self, url: str) -> str:
        p = urlsplit(url)
        segs = [s for s in p.path.split("/") if s]
        if p.hostname in DENY_HOSTS:              return "reject: deny-listed host"
        if len(url) > MAX_URL_LEN:                return "reject: url too long"
        if BLOCKED_EXT.search(p.path):            return "reject: non-HTML extension"
        if len(segs) > MAX_DEPTH:                 return "reject: path too deep"
        if any(c > MAX_REPEAT for c in Counter(segs).values()):
            return "reject: repeating segments (loop)"
        if len(parse_qsl(p.query)) > MAX_PARAMS:  return "reject: too many params"
        shape = self.pattern(p.path)
        if self.per_pattern[p.hostname][shape] >= self.pattern_budget:
            return f"reject: pattern budget spent ({shape})"
        if self.per_host[p.hostname] >= self.host_budget:
            return "reject: host budget spent"
        self.per_host[p.hostname] += 1
        self.per_pattern[p.hostname][shape] += 1
        return "accept"

g = TrapGuard(per_pattern_budget=3)
tests = [
    "https://shop.example.com/shoes/42",
    "https://shop.example.com/a/b/a/b/a/b/a/b/item",
    "https://shop.example.com/img/banner.JPG",
    "https://spam-farm.example/win",
    "https://shop.example.com/list?a=1&b=2&c=3&d=4&e=5&f=6&g=7",
] + [f"https://events.example.org/calendar/2031/{m:02d}/01" for m in range(1, 6)]
for u in tests:
    print(f"{g.check(u):46} {u[8:60]}")
Output
accept                                         shop.example.com/shoes/42
reject: repeating segments (loop)              shop.example.com/a/b/a/b/a/b/a/b/item
reject: non-HTML extension                     shop.example.com/img/banner.JPG
reject: deny-listed host                       spam-farm.example/win
reject: too many params                        shop.example.com/list?a=1&b=2&c=3&d=4&e=5&f=6&g=7
accept                                         events.example.org/calendar/2031/01/01
accept                                         events.example.org/calendar/2031/02/01
accept                                         events.example.org/calendar/2031/03/01
reject: pattern budget spent (/calendar/N/N/N) events.example.org/calendar/2031/04/01
reject: pattern budget spent (/calendar/N/N/N) events.example.org/calendar/2031/05/01

The layers

  • Static rules: URL length, path depth, repeated segments, parameter count, blocked extensions, deny-listed hosts.
  • Pattern budgets: collapse digits (and other variable parts) into a "shape" and cap URLs per shape per host. The calendar above is stopped after 3 months, however many years it offers.
  • Host budgets: a daily URL cap per host, scaled by the host's importance and quality. A new, unlinked host gets a few hundred; a major news site gets millions. This is the backstop that makes every other failure bounded.
  • Content signals: if a host's newly discovered pages are mostly near-duplicates of each other (SimHash), the host is generating URLs rather than content; shrink its budget.
  • Soft 404s: pages that return 200 with "not found" text. Detect by fetching a deliberately random URL on the host once; if that returns 200, compare other pages against its fingerprint.
  • Cloaking: occasionally re-fetch a sample with a browser-like user agent from a different IP range and compare; a large difference marks the host as untrustworthy.
  • Link farms: handled downstream by the ranking system (dense clusters of low-quality hosts linking to each other), which then feeds lower priority back into the frontier.

Step 15 — Storage and output

  • WARC (Web ARChive, ISO 28500) is the standard container: each record is the full HTTP response, headers and all, plus metadata such as fetch time and target URI; request and metadata records can sit alongside. Keeping raw responses means the indexer can be rebuilt, and new extractors run over old crawls, without re-fetching the web.
  • Batch into ~1 GB files, gzip each record separately. Per-record compression means a single page can be decompressed from its (offset, length) without reading the whole file.
  • Object storage (S3, GCS, HDFS) for the files: cheap, durable, and scaled independently of the crawl nodes. Lifecycle rules move old snapshots to colder, cheaper tiers.
  • Don't store the same bytes twice. For exact duplicates and 304 responses, write a small "revisit" record pointing to the earlier copy (WARC has a record type for exactly this).
  • Metadata goes to the event stream (page.fetched), which the indexer, link-graph builder and analytics consume independently. The crawler never calls the indexer directly — if indexing falls behind, the crawl does not stop.

Step 16 — Distribution: partition by host

With ~58 nodes, the key decision is what to partition on. Partition by host (hash of the registered domain or hostname), and assign hosts to nodes with consistent hashing (see lesson 10).

  • Politeness becomes local. Exactly one node owns each host, so that node's frontier alone decides when it is hit. No distributed lock, no coordination at fetch time.
  • Per-host state is co-located: robots rules, DNS cache, back queue, URL records, seen-set partition and trap budgets for a host all sit on its owner. The three kinds of data the crawler keeps — URLs to visit, URL fingerprints, and content fingerprints — are partitioned along the same line, except the content-seen index, which must be partitioned by fingerprint (a mirror lives on a different host from its original).
  • Cross-node traffic is only URL hand-off. A node that discovers a link to a host it does not own buffers it and ships batches every few seconds to the owner, which runs the seen-test and enqueues it. Batching (thousands of URLs per message) keeps this cheap; dedupe inside the batch before sending.
  • Consistent hashing makes membership changes cheap. Adding or losing a node moves only ~1/N of the hosts, with their state, rather than reshuffling everything.
  • Hot hosts are a special case. Hash by URL instead of host and you lose politeness; hash by host and one giant host sits on one node. Giant hosts are rarely a CPU problem, because politeness caps their rate anyway; where a site explicitly permits higher rates, give it more virtual nodes or a dedicated sub-frontier.
  • Geography. Crawling a host from a nearby region cuts latency and cross-ocean bandwidth; large crawlers assign hosts to regional clusters by server location, then hash within the region.

Why not partition by URL hash?

It spreads load perfectly — and breaks politeness, because every node now holds URLs for every host and all 58 may hit the same small site at once. You would then need a global per-host rate limiter, which is the coordination you were trying to avoid. This is the most common wrong answer in this section.

Step 17 — Failures, checkpoints and restart

A full crawl cycle takes days or weeks; restarting from the seeds after a crash is not an option. Each node must be able to die and be replaced from durable state.

  • Durable by construction: the URL store and host table are a local LSM store (RocksDB-like) with a write-ahead log, so a process crash loses nothing that was acknowledged.
  • Periodic checkpoints off the machine: every N minutes, snapshot the in-memory frontier buffers, the Bloom filter and the host politeness state, and upload them with the latest store snapshot to object storage. A replacement node restores the latest checkpoint for its hash range.
  • Replay the gap: URLs handed off to a node are also written to a durable log (Kafka partitioned by owner); on restore, the node replays from the checkpoint's offset. Duplicates are harmless because the seen-test is idempotent.
  • At-least-once is fine; exactly-once is unnecessary. After a restore, some URLs will be fetched twice. That costs one extra polite fetch, and the content-seen test absorbs the duplicate. Say this: it shows you know where not to pay for strong guarantees.
What failsEffectMechanism
Crawl node diesIts hosts pause for minutesConsistent hashing reassigns the range; the new owner restores the checkpoint and replays hand-off log
Fetcher process hangsSlots held foreverWall-clock watchdog per fetch; host lock is a lease with expiry, not a flag
Parser crashes on a pageOne page lostRaw record already in WARC; mark URL "poison" after 2 crashes, skip processing
Target site overloaded / 5xxThat host slows downHost-level backoff and circuit breaker; other hosts unaffected
Object store slow or downFetching pausesLocal disk buffer of WARC segments (hours), then backpressure on fetchers. Never drop fetched pages silently
Kafka / indexer downIndexing lags, crawl continuesEvents buffer in the log; the crawl does not depend on the consumer
DNS resolver downNew hosts stallCached answers keep known hosts crawling; fail over to a secondary resolver
Bloom filter lostMore disk readsRebuild from the URL store in the background; correctness never depended on it
A webmaster complainsReputation, blocksPer-host policy override applied in minutes; the crawler must support "stop now" for any host

Step 18 — Observability

  • Throughput: fetches/s per node, bytes/s, fraction of fetcher slots idle (idle slots with a full frontier mean a politeness or DNS bottleneck, not a lack of work).
  • Health of the crawl: status-code mix over time (a jump in 429 means you are too aggressive somewhere), robots-disallow rate, duplicate rate, average freshness by priority tier, and discovery rate (new URLs per fetch).
  • Frontier: queue depth by priority, age of the oldest due URL per tier (the crawl's real lag), number of active hosts, the top hosts by URLs and by budget spent.
  • Trap detection as metrics: hosts whose URL count grows fastest, URL patterns hitting their budget, near-duplicate ratio per host. These are alerts, reviewed by a human.
  • Per-host audit trail: for any host, when did we fetch, how fast, what did robots say. When a site owner complains, you answer with data within minutes.

Step 19 — Legal and ethical constraints

An interviewer will not ask for law, but mentioning these briefly signals seniority:

  • robots.txt is a convention, not a contract, but ignoring it is the fastest way to be blocked and, in some places, can count against you in court. Obey it.
  • Terms of service, copyright and database rights vary by country. Storing and republishing content is different from indexing it; archives and training-data crawls raise different questions from search.
  • Personal data: crawled pages contain personal information, so privacy laws (GDPR and similar) apply to what you store, for how long, and whether you honour deletion requests.
  • Do not crawl behind logins or paywalls, do not bypass CAPTCHAs or other access controls, and treat an explicit block as a "no".
  • Offer opt-outs: a documented user agent, a robots token for opting out of specific uses (for example, AI training), and a contact channel that actually responds.
  • Politeness is also ethics: the cost of your crawl is paid by other people's servers.

The trade-off summary — how to close

  • Partition by host, not by URL. We accept uneven load (a big host is one node's problem) to make politeness a local decision with no coordination.
  • A custom two-level frontier, not a message queue. Priority and politeness are different questions; front queues and back queues answer them separately. A general-purpose queue cannot express "next URL for a host that is due".
  • Exact URL store as truth, Bloom filter as a shortcut. We pay 320 GB of disk to lose no pages, and use ~48 GB of RAM to skip most disk reads for new URLs. A Bloom filter alone silently loses 1% of new pages.
  • Exact hash plus SimHash for content. Exact is cheap and certain; SimHash catches the more common near-copies at the cost of tuning a threshold and extra index tables.
  • Selective JavaScript rendering. Rendering everything would multiply the fleet; we render only where plain fetching demonstrably misses content.
  • Freshness by greedy allocation, not by change rate. Some fast-changing pages are deliberately left stale because chasing them buys nothing.
  • At-least-once fetching. Duplicated fetches after a crash are cheaper than the coordination needed to prevent them.
  • Budgets as the universal backstop. Every host has a cap, so an unknown trap costs a bounded amount of capacity.
  • What I would build first: a single node with the Mercator frontier, robots cache, normaliser, RocksDB URL store and WARC output, crawling a few thousand hosts. Then partition by host and add nodes; then add recrawl scheduling; then the render tier.

Related lessons: consistent hashing and partitioning in Key-Value Store, queues and backpressure in Queues, APIs and Reliability, token-bucket style per-key limits in Rate Limiter, and the search side of the pipeline in Typeahead.

// Write your solution here
// Write your solution here
// Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 16Typeahead and Nearby SearchTries, prefix caches, geohash, quadtrees and proximity queries.