How to design a web crawler

In this lesson, we’ll design a crawler that pulls a billion pages a month without ever getting our IP range blocked. We’ll start from a single measured number (how many pages per second one web server will politely give us) and let every later decision fall out of it. By the end you’ll be able to size the fleet from a workload, explain why host diversity and not hardware is the ceiling, and defend each guard in the design as a number, not a guess.

A web crawler starts from a handful of known web addresses, downloads each page, extracts the links inside it, and repeats. A web address is a URL (uniform resource locator), the https://example.com/path?q=1 string that names one document.

• Input: a seed set of a few thousand starting URLs, the home pages of large sites, a directory dump, or a previous crawl’s index.
• Output: a growing store of raw HTML documents, plus one metadata row per document recording when it was fetched, the server’s version tag, a fingerprint of its content, and how fast it appears to change.

Everything in between is scheduling. Downloading a page over HTTP is a solved problem you get from a library. Deciding which page to download next is the whole design.

One number decides the size and shape of the system: how many pages per second you may take from a single web server. Two terms recur throughout:

• Politeness is the contract a crawler owes a server it does not own: open at most one connection to it at a time, and wait a fixed gap between consecutive fetches, so the crawl does not resemble an attack.
• The frontier is the crawler’s to-do list, the set of URLs discovered but not yet fetched, plus the machinery that decides which one to hand a worker next.

Because you may open only one connection per host and must wait between fetches, throughput is not a function of your fleet size but of how many distinct hosts you have URLs for right now. A host here means one web server, named by a hostname such as example.com.

Framing: one decision, four forces

The design turns on one decision (how the frontier is organized) and four forces constrain it at once. Any frontier design has to answer for all four.

A CMS (content management system) is the software a site runs to publish pages, such as WordPress. A session id is a per-visitor token some sites paste into the URL, so the same page hands you a different address every time.

Politeness is not a feature added at the end; it is the constraint that decides the frontier’s data structure. Everything downstream (the queue layout, the shard key, the fleet size) follows from the per-host rate derived in the politeness ceiling.

Four things break in production, most frequent first:

1. A DNS resolver saturates, and the fetchers idle at a few percent utilization.
2. A single CMS generates tens of millions of calendar URLs and eats a week of crawl budget.
3. A shared-hosting IP takes thousands of requests per second, because politeness was keyed on the hostname, not on the server behind it.
4. The URL-seen filter passes the capacity it was sized for and begins silently discarding real pages.

Requirements

Functional

• Fetch pages from a seed set, extract links, and repeat.
• Store the raw document plus enough metadata to re-fetch it conditionally.
• Honor robots.txt, including Crawl-delay and Sitemap.
• Detect and skip duplicate and near-duplicate content.
• Re-crawl pages at a rate driven by their observed change rate.

Three of those need glossing:

• robots.txt is a plain-text file every site may publish at its root (https://example.com/robots.txt) listing the paths crawlers may and may not fetch. Crawl-delay inside it asks for a specific number of seconds between fetches; Sitemap points at a machine-readable list of the site’s URLs.
• A conditional re-fetch requests a page only if it changed since your copy. The server answers with either the full page or a tiny “not modified” reply.
• Near-duplicate content is two documents that are not byte-identical but say the same thing: a print view, a mirror, the same article with a different advertisement in the margin.

Out of scope: ranking, the search index itself, and running a full browser to execute each page’s JavaScript. Each is real work, but none of it changes the scheduler, which is what this design is about.

Non-functional

A trap is a URL space that is infinite, or finite but enormous, and machine-generated. To DoS a server is to deny service to it: send so many requests that real users cannot get through. last_fetch_at is the timestamp of the crawler’s most recent fetch from a given host; it is the only thing standing between a fleet restart and a simultaneous burst at every server the crawler knows.

The assumptions the numbers rest on

Every number below is downstream of a short list of assumptions. The four load-bearing ones each move a design decision, not just a cost:

Supporting assumptions that move costs but not decisions: novelty among extracted links stays above 1%; roughly 30% of the corpus is near-duplicate and 10% byte-identical; page changes follow a Poisson process (constant average rate, independent arrivals); peak traffic is twice average; storage is replicated three times and HTML recompresses 5:1.

Two measured values are worth stating separately, because guards depend on them:

• Of the ~100 links on a page, about 10 are pages nobody has crawled yet, the branching factor. This is a reading of the 100-links figure at ~10% novelty, and it is the sole basis for the depth cap.
• The crawl touches about 1 million distinct hosts on a given day. Sanity check: ~33 million fetches a day over 1 M hosts is 33 pages per host per day, the shape of a broad crawl, which is what a general web crawler is. This sets the robots.txt cache saving and the whole DNS section.

Back of the envelope

The product hands you one number (a billion pages a month) and every other quantity comes out of it.

Volume, bandwidth, storage

• Request rate. A billion pages a month is ~33 million a day, ~333 pages/s average. At the assumed 2x peak, ~666 pages/s.
• Bandwidth. A crawler fetches the HTML document, gzipped, at ~100 KB on the wire, not the ~2 MB a browser downloads to render a page (images, fonts, scripts). Billing 2 MB per page is the classic 20x error that sizes a fleet that does not exist. At 100 KB: ~267 Mbps average, ~533 Mbps peak, about 53% of one 1 Gbps NIC. A NIC (network interface card) is the port connecting a machine to the network.
• Storage. Stored HTML recompresses ~5:1 to ~20 KB/page. Over a year at replication factor 3 (every byte on three machines) that is ~730 TB, about twenty commodity boxes. The document bodies go to object storage; only a reference lives in the database.

Bandwidth and storage are both cheap, so neither is the constraint.

One rule prevents the arithmetic from going wrong later: never confuse offered load with service capacity. The 267/533 Mbps figures are offered load, a property of the workload. The 1 Gbps NIC is service capacity, a property of the machine. Two corollaries:

1. Never scale an average by a peak ratio to get a peak. Re-derive the peak from the peak page rate.
2. Never size a fleet at exactly the offered load. Size it at offered load divided by a target utilization, the fraction of capacity you plan to consume, conventionally 80%, because queueing delay climbs steeply above it.

The politeness ceiling

The constraint that is not cheap is how many pages per second one host can give you, because that number times the number of hosts you can work on at once is your throughput.

One connection per host means fetches to a host are serial. A crawl delay adds a gap between them. So the period between two consecutive pages from one host is the fetch plus the delay:

• Fetch latency, keep-alive: 0.1 s round trip + 0.1 s transfer = 0.2 s. (Keep-alive holds the connection open between fetches, so only the first pays connection setup; RTT is round-trip time.)
• Politeness delay: 1.0 s.
• Period per page from one host: 1.2 s, so 0.833 pages/s per host.

0.833 pages per second per host is the constant the whole design runs on. Throughput is hosts_in_flight x 0.833, where hosts_in_flight counts the distinct hosts the crawler is legally allowed to be fetching from right now, a property of the frontier’s contents, not the hardware. The 666 pages/s peak therefore needs 800 distinct hosts in flight (666 / 0.833).

The fleet those 800 host-slots need is tiny. 800 concurrent sockets (one open connection each) fit in a fraction of one async fetcher process, one that holds thousands of sockets by never blocking a thread on a response. Parsing 666 pages/s at ~10 ms each is 6.66 cores of demand, ~8.3 cores at 80% utilization.

The crawler is not CPU-bound, bandwidth-bound, or socket-bound. It is bound by host diversity. Adding machines does nothing; adding hosts to the frontier does everything. Two consequences follow:

• One large site is effectively uncrawlable. A 100-million-page site at 0.833 pages/s takes about 3.8 years. That is why large-site crawling is a negotiated relationship (sitemaps, feeds, an agreed rate, or a bulk export), not a scheduling problem you solve. It gets worse under Crawl-delay: 10, which stretches the period to 10.2 s (0.098 pages/s); a million-page site then takes ~118 days.

• Politeness must be keyed on the IP address, not the hostname. An IP names the machine; a hostname names a site. Shared hosting puts thousands of sites on one machine, so a per-hostname limit lets thousands of “polite” streams hit the same box: 5,000 hostnames at 0.833 pages/s each is 4,165 requests/s at one server, a denial of service you will be blamed for, even though every individual hostname was polite. Key on the resolved IP, or the (host, IP) pair. The pair matters for sites behind a CDN (content delivery network) that may resolve to many anycast addresses (the same address announced from many locations, routed to the nearest); keying on the hostname alone would throttle all of that capacity to one slot.

The frontier does not converge

The to-do list never empties, which is why the interesting question is what to fetch next, not how to fetch faster.

Crawling one page removes one URL (the one fetched) and adds 100 x novelty URLs, where novelty is the fraction of extracted links never seen before. The frontier breaks even when 100 x novelty = 1, i.e. novelty = 1%.

• Below 1% novelty, the frontier drains.
• Above 1%, it grows without bound no matter how fast you fetch. At 2% novelty, a billion pages crawled leaves the frontier a billion URLs longer than it started.

Real novelty on a fresh crawl is far above 1%, so the frontier is permanently oversubscribed and the design question is prioritization, not drainage.

API sketch

The crawler’s API is internal (no outside customer calls it) but it is the seam between the scheduler and everything else. Each line below is an HTTP verb and path, with the request body in braces and responses indented.

POST /v1/frontier/urls     {"urls": [{"url","priority","depth","from"}]}
  202 accepted             filtering and dedup happen asynchronously

GET  /v1/frontier/lease?worker_id=&n=32
  200 [{"url","host","ip","lease_expires_at"}]
  204 nothing is polite to fetch right now      <- the normal empty case

POST /v1/frontier/complete {"url","status","etag","content_ref",
                            "simhash","outlinks":[...]}
GET  /v1/hosts/{host}/policy  -> {"crawl_delay_s","robots_expires_at"}

Two fields in complete appear before their sections. An etag is the opaque version tag a server hands out with a document; send it back next time and the server can answer “not modified” instead of resending the body. A simhash is a 64-bit similarity fingerprint of the page’s text, built so two documents saying the same thing land at nearly the same value; it is not a cryptographic hash and is not used like one.

Three choices in the sketch are deliberate:

• Lease, not pop. Popping removes a URL and hands it over; leasing hands it over but keeps it, marked as out on loan until a deadline. A worker that dies mid-fetch must not lose the URL, and must not have it re-issued instantly. The lease expiry is the redelivery clock, and it must exceed the fetch timeout or you double-fetch every slow host.
• 204 is a first-class response, not an error. “Nothing is polite right now” is the steady state whenever host diversity is thin. A client that treats it as failure will hot-loop (retry continuously) hammering the scheduler for nothing.
• complete carries the outlinks. Extraction happens on the worker, where the bytes already are. Shipping documents back to a central parser would move hundreds of Mbps for no reason.

Data model

Three tables, and only one decision inside them is genuinely load-bearing: which field decides where a row lives. (TEXT, BYTEA, INET, SMALLINT, BIGINT, REAL are SQL column types: text, raw bytes, an IP address, small and large integers, and a float.)

host_state                                -- the politeness ledger
  host TEXT PRIMARY KEY, ip INET, crawl_delay_s REAL
  last_fetch_at TIMESTAMP                 -- must survive restart
  robots_body TEXT, robots_expires_at TIMESTAMP, consecutive_errors SMALLINT

frontier                                  -- partitioned by hash(ip)
  url_hash BYTEA PRIMARY KEY, url TEXT, host TEXT
  priority SMALLINT, depth SMALLINT, discovered_at TIMESTAMP

docs
  url_hash BYTEA PRIMARY KEY, fetched_at TIMESTAMP, http_status SMALLINT
  etag TEXT, last_modified TEXT
  simhash BIGINT                          -- 64 bits, content dedup
  change_rate REAL                        -- lambda, freshness
  content_ref TEXT                        -- object store key

Why the frontier shards on IP

A shard is one of the machines a table is split across; the shard key is the field whose hash decides which shard a row lands on. The frontier’s shard key is hash(ip), not hash(url). Compare the two against the invariant “one connection per host”:

• hash(url) spreads one host’s URLs across every shard, so enforcing one connection per host would need every shard to coordinate with every other on every fetch.
• hash(ip) makes each host the exclusive property of one shard. Politeness becomes a purely local decision: compare last_fetch_at against the clock. No locks and no RPC (a remote procedure call, a network round trip dressed up as a function call).

This applies the ring from the consistent-hashing chapter with a deliberately non-obvious key.

Where the bytes live

The document store is append-mostly with large immutable values, rows are added and almost never modified. That is the workload an LSM tree (log-structured merge tree) is built for: it buffers writes in memory and flushes them as sorted files instead of updating pages in place, derived in the database-internals chapter. The document bodies go to object storage (a service such as S3 that stores blobs under a key for a tenth of the price of a database); only the content_ref key lives in the row.

High-level architecture

Here is the whole pipeline once, end to end. It is a loop, not a pipeline with an end: the arrow leaving the bottom returns to the top.

flowchart TD
    SEED["Seed URLs"] --> FRONT["Front queues<br/>priority 0 to 4"]
    FRONT --> ROUTER["Back queue router<br/>sticky host to queue map"]
    ROUTER --> BACK["Back queues<br/>1,024, one host each"]
    BACK --> HEAP["Ready heap<br/>keyed on next_fetch_at"]
    HEAP --> DNS["DNS<br/>own recursive resolver + cache"]
    DNS --> ROB{"robots.txt cached<br/>and allows it?"}
    ROB -->|"no"| DROP["Drop"]
    ROB -->|"yes"| FETCH["HTTP fetcher<br/>keep-alive, conditional GET"]
    FETCH -->|"304 Not Modified"| SCHED["Re-crawl scheduler<br/>update change rate"]
    FETCH -->|"200"| CSEEN{"Content seen?<br/>simhash within 3"}
    CSEEN -->|"yes"| SCHED
    CSEEN -->|"no"| STORE[("Doc store<br/>compressed HTML")]
    STORE --> EXT["Link extractor<br/>and URL canonicalizer"]
    EXT --> FILT["URL filter<br/>scheme, depth, traps, blocklist"]
    FILT --> USEEN{"URL seen?<br/>bloom, 20 bits per key"}
    USEEN -->|"yes"| DROP
    USEEN -->|"no"| FRONT
    SCHED --> FRONT

    style ROUTER fill:#bc6c25,color:#fff
    style USEEN fill:#1d3557,color:#fff
    style CSEEN fill:#1d3557,color:#fff
    style DROP fill:#9d0208,color:#fff

Following one URL through the loop:

1. It enters the front queues, as a seed, or later as a link found in another page. Five front queues, numbered by priority 0 to 4.
2. The back queue router assigns it a back queue via a sticky host-to-queue map, so the URL joins whichever back queue already owns its host. There are 1,024 back queues, each holding one host only.
3. The ready heap decides which back queue goes next, keyed on next_fetch_at, the earliest time politeness permits another fetch from that host.
4. DNS resolves the hostname using the crawler’s own recursive resolver plus a cache. Recursive means the resolver chases the answer down the domain hierarchy itself.
5. A gate checks the cached robots.txt. If it disallows the fetch, the URL is dropped and never revisited.
6. The HTTP fetcher issues a conditional GET over a kept-alive connection, carrying the version tag from last time, so the server may answer 304 Not Modified instead of resending bytes.
7. A 304 goes straight to the re-crawl scheduler (nothing changed, nothing stored). A 200 reaches the content-seen check, which compares the document’s simhash against everything stored and treats a match within Hamming distance 3 as a duplicate. Hamming distance is the count of bit positions in which two equal-length bit strings differ.
8. Fresh documents go to the doc store as compressed HTML.
9. The link extractor and canonicalizer pull out the outbound links and rewrite each into one standard form.
10. The URL filter drops what should never be fetched, by scheme, depth, trap signature, or blocklist.
11. What survives hits the URL-seen check (the bloom filter at 20 bits per key). Anything genuinely new re-enters the front queues, and the loop closes.

The diagram asserts four things, each with its own section below: priority and politeness need two queue layers; URL dedup is a bloom filter whose false-positive rate is a product decision; content dedup cannot be an exact hash; and the loop-back arrow is governed by an observed change rate.

Deep dive 1: front queues and back queues

The frontier’s shape falls out of two impossibilities:

• One queue cannot hold both priority and politeness. A page contains ~100 links to the same host, so any FIFO or priority order hands a worker 100 consecutive URLs for one server. (FIFO is first-in-first-out, plain arrival order.) Either you fetch those 100 and violate politeness 100x, or you skip them and turn the queue into a linear scan through the head looking for a host you may touch, a scan that runs on every fetch.

• Per-host queues alone cannot hold priority. With millions of hosts you would need millions of queues, which you cannot keep in memory or schedule over. And nothing in that structure expresses “this news site matters more than that parked domain” (a parked domain is registered but holds no real content).

The answer is two layers with a router between them. The left half is priority, the right half is politeness, and the router is the only thing connecting them.

flowchart LR
    IN["New URLs"] --> P["Prioritizer<br/>site rank, freshness, depth"]
    P --> F0["Front 0"] & F1["Front 1"] & F2["Front 2"]
    F0 & F1 & F2 --> R["Router<br/>host -> back queue<br/>sticky, table-backed"]
    R --> B0["Back 0<br/>host A only"] & B1["Back 1<br/>host B only"] & B2["Back 2<br/>host C only"]
    B0 & B1 & B2 --> H["Ready heap<br/>next_fetch_at per queue"]
    H --> W["Worker pool"]

    style R fill:#bc6c25,color:#fff
    style H fill:#2d6a4f,color:#fff

New URLs are scored by the prioritizer on site rank, expected freshness, and depth from the seed, then queued by priority. The router hands each to the back queue that owns its host. The ready heap picks which back queue may go next. A worker pool drains it. Four properties make it work:

• Front queues carry priority. Selection between them is weighted-random, not strict. Under strict priority the low queues never get picked, and the low queues are where host diversity lives.
• Back queues carry politeness. Each holds one host only, and a worker takes from one back queue at a time, so two overlapping requests to one server are structurally impossible, not policed by a check somebody can forget.
• The router is a sticky table, not a hash. Sticky means a host keeps the same slot while it has work. Hashing hosts into slots gives collisions, and a collision means two hosts share a back queue and one blocks the other. The table assigns a free slot on first sight and releases it when the queue drains.
• The ready heap is keyed on next_fetch_at per back queue. A heap keeps the smallest key on top, so “what may I fetch now” costs O(log b) with b queues, a handful of comparisons, not a scan of all 1,024.

Sizing the back-queue count. One back queue holds one host, and the peak needs 800 hosts in flight, so you need at least 800 back queues, rounded up to 1,024 (a power of two makes index arithmetic a bit mask), giving ~1.28x headroom. The back-queue count is a hard ceiling on throughput: with b back queues you can never exceed b x 0.833 pages/s, no matter how many workers you run.

The frontier in code

A working frontier with a simulated clock. Four assertions pin the section’s claims: one host tops out at 0.833 pages/s; eight hosts with eight queues run eight times faster at identical per-host politeness; eight hosts with only two queues are capped by the queues (b x 0.833); and a host whose slot is recycled to someone else still owes the full 1.2 s when it comes back. That last path is the subtle one: the slot is a recyclable resource, the politeness debt is not, which is why last_fetch lives outside the slot table and _next_ok charges fetch_s + delay_s.

"""The frontier: front queues carry priority, back queues carry politeness."""
import heapq
from collections import defaultdict, deque


class Frontier:
    """One back queue per host in flight, so a worker bound to one back queue
    cannot issue two overlapping requests to the same server."""

    def __init__(self, n_back=8, delay_s=1.0, fetch_s=0.2, priorities=3):
        self.front = [deque() for _ in range(priorities)]
        self.back, self.slot_of, self.host_of = {}, {}, {}
        self.free = deque(range(n_back))
        self.ready = []                       # heap of (next_fetch_at, slot)
        self.last_fetch = defaultdict(lambda: -1e18)   # outlives slot reuse
        self.delay_s, self.fetch_s = delay_s, fetch_s
        self.admissions = 0                   # host -> slot assignments so far

    def add(self, url, host, priority=1):
        self.front[min(priority, len(self.front) - 1)].append((url, host))

    def _next_ok(self, host, now):
        """Earliest polite time for `host`: a FULL period after its last fetch.
        Fetch plus delay, not the delay alone -- charging only the delay makes
        the gap 1.0 s instead of 1.2 s for hosts that lost their slot and came
        back, a path no simulation that adds each host once will reach."""
        return max(now, self.last_fetch[host] + self.fetch_s + self.delay_s)

    def _fill(self, now):
        """Route front-queue URLs into back queues until the slots run out."""
        for q in self.front:
            while q:
                url, host = q[0]
                slot = self.slot_of.get(host)
                if slot is None:
                    if not self.free:
                        return                # no slot: the router blocks
                    slot = self.free.popleft()
                    self.slot_of[host], self.host_of[slot] = slot, host
                    self.back[slot] = deque()
                    self.admissions += 1
                    heapq.heappush(self.ready, (self._next_ok(host, now), slot))
                q.popleft()
                self.back[slot].append(url)

    def pop(self, now):
        """Return (url, host), or None if nothing is polite to fetch yet."""
        self._fill(now)
        if not self.ready or self.ready[0][0] > now:
            return None
        _, slot = heapq.heappop(self.ready)
        host, url = self.host_of[slot], self.back[slot].popleft()
        self.last_fetch[host] = now
        if self.back[slot]:
            heapq.heappush(self.ready, (now + self.fetch_s + self.delay_s, slot))
        else:
            del self.back[slot], self.slot_of[host], self.host_of[slot]
            self.free.append(slot)            # slot recycled; the debt is not
        return url, host


def simulate(hosts, per_host, n_back):
    f = Frontier(n_back=n_back)
    for h in range(hosts):
        for i in range(per_host):
            f.add(f"http://h{h}/p{i}", f"h{h}")
    now, done = 0.0, 0
    while done < hosts * per_host:
        if f.pop(now) is not None:
            done += 1
        elif f.ready:
            now = max(now, f.ready[0][0])
        else:
            break
    # Each admission gets one free fetch (the gap is BETWEEN fetches of one
    # host), so netting them off makes b x 0.833 an exact ceiling.
    return done, (done - f.admissions) / now            # fetched, pages/s


# One host: the period is fetch + delay, so the ceiling is 1/1.2 = 0.833/s.
assert abs(simulate(1, 100, n_back=1)[1] - 1 / 1.2) < 0.01
# Eight hosts, eight queues: 8x the rate, identical politeness per host.
assert abs(simulate(8, 100, n_back=8)[1] - 8 / 1.2) < 0.05
# Eight hosts, two queues: throughput is capped by the QUEUES, not the hosts.
assert simulate(8, 50, n_back=2)[1] < 2 / 1.2 + 1e-9
# Slot resurrection: host A drains, loses its slot, is re-added. Politeness
# still owes the full 1.2 s from A's last fetch, not the 1.0 s delay alone.
resurrect = Frontier(n_back=1)
resurrect.add("http://a/1", "A")
assert resurrect.pop(0.0) == ("http://a/1", "A")   # queue drains, slot freed
resurrect.add("http://a/2", "A")
assert resurrect.pop(1.0) is None                  # 1.0 s is not yet 1.2 s
assert resurrect.pop(1.2) == ("http://a/2", "A")

Deep dive 2: URL dedup, and what a false positive costs

“Have I already seen this URL?” has a two-stage answer: rewrite the URL into a standard form, then test it against a compact probabilistic filter.

flowchart LR
    RAW["Extracted URL"] --> CANON["Canonicalize<br/>normalize form, strip tracking params"]
    CANON --> BLOOM{"Bloom filter<br/>seen before?"}
    BLOOM -->|"bit clear: definitely new"| KEEP["Add to frontier"]
    BLOOM -->|"all bits set: maybe seen"| EXACT{"Exact on-disk set<br/>confirm"}
    EXACT -->|"present"| DROP["Drop"]
    EXACT -->|"absent"| KEEP

Stage one: canonicalization

Canonicalization (URL normalization) rewrites a URL into one standard form, so the many spellings of the same address collapse to a single string:

• Lowercase the scheme (the https part) and the host.
• Drop the default port (:80 for HTTP, :443 for HTTPS).
• Resolve . and .. path segments.
• Drop the #fragment, which never reaches the server.
• Sort the query parameters, so ?a=1&b=2 and ?b=2&a=1 become one string.
• Strip known tracking and session parameters (utm_*, sid, jsessionid, PHPSESSID): marketing tags and per-visitor tokens that change the string without changing the page.

This is the cheapest deduplication in the system: pure string manipulation, running first. At a ~30% collapse rate over the ~3.3 billion links extracted per day, it removes about a billion filter lookups a day for free, before the expensive filter ever sees a URL.

Stage two: the bloom filter

A bloom filter is a bit array plus k hash functions.

• To insert a key, hash it k ways and set those k bits.
• To test a key, hash it the same k ways and check whether all k bits are set.
• If any bit is clear, the key is definitely absent: a bloom filter never gives a false negative.
• If all k bits are set, the key is probably present. Those bits may have been set by other keys: that is a false positive, the filter saying “seen” about something it never saw.

The design knob is m/n, the bits per key (m bits available, n keys stored). The optimal k = (m/n) ln 2 and the false-positive probability p = 0.6185 ^ (m/n) are derived in the key-value-store chapter and used here as given.

What is specific to a crawler is the cost function. A false positive here is not a wasted disk read. It is a page that is never fetched, and nothing anywhere logs it. The URL is declared already-seen, dropped, and never reconsidered. No error, no retry, no metric that moves.

The table sizes the filter at the settings you would actually consider. The RAM column is 10^10 keys x bits / 8. The last column turns the FP rate into pages of the web silently lost over one corpus pass, one full sweep through the 10 billion URLs.

The last column is the one that matters: it converts a percentage nobody has intuition about into pages of the web that will never be crawled. Moving from 10 to 20 bits per key costs 12.5 GB of extra RAM and buys back ~81 million pages, about 6.5 million pages recovered per gigabyte. That is why the crawler runs at 20 bits per key while an LSM store runs at 10: same structure, same formula, different cost of being wrong. The LSM tree pays a false positive with one wasted disk read; the crawler pays it with a document that will never exist. Take the target rate to the product owner as a number of missing pages, not a percentage.

The failure mode is a cliff, not a slope. Put twice the design keys into a filter sized for n and m/n halves from 20 to 10, but k stays at the 14 the filter was built with. That does not halve the accuracy. It multiplies the FP rate by about 283x (from 0.0067% to ~1.9%), and the only symptom is a crawl that quietly gets smaller. So alert on inserted-key count against design capacity, not on any measured error rate: there is no ground truth to measure the error against.

Two mitigations:

• A scalable bloom filter. When the current generation reaches its design capacity, freeze it and start a new one; a lookup checks every generation. Error grows by addition across generations instead of collapsing exponentially inside one.
• An exact backing set. An on-disk sorted set of every URL seen. The filter answers “definitely new” for free; only the “maybe seen” answers pay for a disk lookup to confirm.

Partition both across the fleet by hash(url). The asymmetry with the data model is deliberate: the frontier is partitioned by IP because politeness is per-server, while the seen-set is partitioned by URL because dedup is per-URL. Two shard keys in one system, each derived from what it has to make local.

The code inverts the closed form and pins the two operating points, the 25 GB footprint, the pages recovered, and the cliff:

import math


def bits_per_key(target_fp):
    """Invert p = 0.6185 ^ (m/n): the bits/key a target FP rate costs."""
    return math.log(target_fp) / math.log(0.6185)


def fp_at(bits, k=None):
    k = k or max(1, round(bits * math.log(2)))
    return (1 - math.exp(-k / bits)) ** k


N = 10_000_000_000
assert round(fp_at(10), 6) == 0.008194          # the LSM operating point
assert round(fp_at(20), 6) == 0.000067          # the crawler operating point
assert round(N * 20 / 8 / 1e9, 1) == 25.0       # 25 GB of RAM
assert round(N * fp_at(10) - N * fp_at(20)) == 81_265_850   # pages recovered
assert 19.0 < bits_per_key(1e-4) < 19.4         # 0.01% costs ~19 bits/key
assert round((1 - math.exp(-14 / 10)) ** 14 / fp_at(20)) == 283   # the cliff

Deep dive 3: content dedup, where exact hashing has zero recall

The previous section deduplicated addresses. Deduplicating content is harder: an exact hash is useless, so it takes a similarity fingerprint plus a way to look one up among ten billion others without scanning.

Why an exact hash scores zero

SHA-256 is a cryptographic hash: it turns any input into a 32-byte value where a one-bit change scrambles the whole output. That property makes it useless here. It catches byte-identical documents and nothing else, and any page carrying a rendering timestamp, a rotating ad slot, a CSRF token, a visitor counter, or a “3 comments” badge is byte-different on every fetch. (A CSRF token is a per-visit random string a site embeds against cross-site request forgery.)

Measure a detector by recall, the fraction of true duplicates it finds. Against the near-duplicate population an exact hash does not merely score low; it scores zero, because “near-duplicate” means “not byte-identical,” which is the only thing an exact hash can see.

Using the 30% near-duplicate and 10% byte-identical shares, the band only a near-duplicate detector can catch is 20% of the corpus, about 200 million pages a month and ~4 TB of storage, spent on mirrors, print views, syndicated wire copy, and session-id variants of pages you already have. The storage is nothing; the 200 million wasted fetches are 20% of the throughput you sized a whole fleet for, and fetch slots are the resource you cannot buy more of.

What a simhash is

Simhash is a 64-bit fingerprint, built in four steps:

1. Cut the document into shingles, overlapping runs of a few consecutive words. “the quick brown fox” and “quick brown fox jumps” are two shingles of length 4.
2. Hash each shingle to 64 bits.
3. For each of the 64 bit positions keep a running total: add one if that bit is set in the shingle’s hash, subtract one if it is clear.
4. The fingerprint has a 1 wherever the total came out positive, 0 elsewhere.

The point is the vote. Changing a few shingles nudges a few of the 64 totals across zero and leaves the rest alone, because every other shingle still votes the same way. So two documents sharing most of their text land at small Hamming distance. Near-duplicate is distance <= 3.

Querying ten billion fingerprints without scanning

The hard part is querying: find every fingerprint within distance 3 of a probe, over 10 billion fingerprints, at ~666 probes/s. Scanning is 10 billion comparisons per probe. An ordinary hash table does not help either, because the whole point is that the two fingerprints are not equal.

The trick is the pigeonhole principle: if only 3 bits differ and you split the fingerprint into more than 3 blocks, at least one block has no differing bit at all. So split the 64 bits into B blocks; if two fingerprints differ in at most 3 bits, at least B - 3 blocks are bit-identical. Build one hash table for every combination of B - 3 blocks, keyed on those blocks’ bits, and at least one table is guaranteed to have filed both fingerprints under the same key. A fuzzy search becomes a set of exact lookups.

Two ways to choose B (where C(n,r) counts ways to pick r of n):

• B = 4 blocks of 16 bits leaves at least one block clean, but you do not know which, so you index every block: C(4,1) = 4 tables keyed on 16 bits. A 16-bit key spreads 10^10 fingerprints over 65,536 buckets, so ~152,000 candidates per probe, ~610,000 per query, 0.32 TB of index.
• B = 6 blocks leaves at least 3 clean; index every combination of three: C(6,3) = 20 tables keyed on 31+ bits. A 31-bit key gives ~4.7 candidates per probe, ~93 per query, 1.6 TB of index.

At 666 probes/s the 4-table split is ~406 million comparisons/s, a memory-bandwidth problem larger than the crawl itself. The 20-table split is ~62,000 comparisons/s, negligible. So 1.28 TB of extra index removes 406 million comparisons per second: the 20-table split wins. The trade is entirely a consequence of corpus size. Drop 10 B to 100 M and the candidate count per probe falls by the same factor, changing the answer.

Why simhash and not minhash

Minhash is the other standard similarity sketch: store the minimum hash value under each of many hash functions and compare how many minima agree. It costs about 64x the space (a 128-hash signature is ~512 bytes per document, ~5 TB for the corpus, against simhash’s 8 bytes and ~80 GB). It answers a richer question (an estimate of Jaccard similarity, the size of the overlap of two sets divided by the size of their union) that a crawler does not need. “Is this the same page” is a threshold test at a fixed cut-off, not a graded score, so the 8-byte fingerprint wins. Minhash earns its keep where you need the graded answer or genuine set-overlap semantics (clustering, plagiarism scoring), not a yes-or-no rejection.

The fingerprint and the index in code

simhash follows the four steps: v is the 64 running totals, the loop casts the votes, the final sum turns positive totals into set bits. NearDupIndex builds the 20 tables from itertools.combinations. The assertions demonstrate the claim directly: two copies of a page differing only in a rendering timestamp get different SHA-256 hashes, land within Hamming distance 3, and are matched by one probe, while unrelated prose is more than 10 bits away and matches nothing.

"""Simhash plus the block-permutation index that makes it queryable."""
import hashlib
import itertools
import re

BLOCKS = [(0, 11), (11, 11), (22, 11), (33, 11), (44, 10), (54, 10)]


def simhash(text, bits=64, k=4):
    w = re.findall(r"[a-z0-9]+", text.lower())
    v = [0] * bits
    for i in range(max(1, len(w) - k + 1)):
        h = int.from_bytes(hashlib.blake2b(
            " ".join(w[i:i + k]).encode(), digest_size=8).digest(), "big")
        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, b):
    return bin(a ^ b).count("1")


class NearDupIndex:
    """C(6,3) = 20 tables. At Hamming distance <= 3 across 6 blocks at least
    3 blocks are untouched, so one of the 20 three-block keys must match."""

    def __init__(self, max_distance=3, clean=3):
        self.combos = list(itertools.combinations(range(len(BLOCKS)), clean))
        self.tables = [{} for _ in self.combos]
        self.max_distance = max_distance

    def _keys(self, fp):
        for combo in self.combos:
            yield tuple((fp >> BLOCKS[i][0]) & ((1 << BLOCKS[i][1]) - 1)
                        for i in combo)

    def add(self, fp, doc_id):
        for table, key in zip(self.tables, self._keys(fp)):
            table.setdefault(key, []).append((fp, doc_id))

    def probe(self, fp):
        seen, hits = set(), []
        for table, key in zip(self.tables, self._keys(fp)):
            for cand, doc_id in table.get(key, ()):
                if doc_id not in seen:
                    seen.add(doc_id)
                    if hamming(fp, cand) <= self.max_distance:
                        hits.append(doc_id)
        return hits


BASE = " ".join(f"the quick brown fox jumps over the lazy dog number {i}"
                for i in range(80))
A, B = BASE + " page generated at 04 15 02", BASE + " page generated at 09 41 37"
C = " ".join(f"unrelated prose about b trees and write amplification {i}"
             for i in range(80))

assert sum(BLOCKS[-1]) == 64 and len(NearDupIndex().combos) == 20
# Exact hashing has zero recall against a rendering timestamp; simhash does not.
assert hashlib.sha256(A.encode()).digest() != hashlib.sha256(B.encode()).digest()
assert hamming(simhash(A), simhash(B)) <= 3
assert hamming(simhash(A), simhash(C)) > 10

idx = NearDupIndex()
idx.add(simhash(A), "doc-A")
assert idx.probe(simhash(B)) == ["doc-A"] and idx.probe(simhash(C)) == []

Traps, and guards that are arithmetic, not heuristic

Sites generate unbounded URL spaces by accident (nobody built a trap to hurt you) and each guard can be derived from a number instead of picked, which is what lets you defend “why 16 and not 12?”.

Faceted navigation is the filter sidebar on a shop (colour, size, sort, page) where every combination of choices is its own URL, so n filters explode combinatorially over one small catalogue. A soft 404 says “not found” in its body while the server reports a 200 success, defeating every check that looks only at the status code.

The depth cap, derived. Depth is the number of link hops from a seed. The cap rests on the branching factor, the ~10 genuinely new pages each crawled page reveals (not the 100 outbound links, most of which point at pages you already have). Reach at depth d is branching_factor ^ d, so at a branching factor of 10 the entire 10-billion-page target is reachable at depth 10. Cap at 16 and you have six orders of magnitude of slack (10^16 is a million times the corpus), so anything deeper cannot be reachable content. Move the branching factor and the cap moves with it: at branching factor 5 the corpus is reached at depth 15 and the cap lands at 23.

URL length gets the same treatment: median URL length is ~66 bytes, so a 1,000-byte guard is ~15x the median, nothing a human ever typed comes near it.

The per-host budget is the guard that actually contains a trap, and it is a diversity control, not a politeness control. Cap each host at 10,000 pages/month and filling the 1-billion monthly budget requires 100,000 distinct hosts, exactly the breadth throughput depends on. One host can physically yield ~72,000 pages/day, so 10,000/month binds long before politeness does. One guard solves two problems: it stops any single trap from eating the budget, and it forces the breadth that makes the fleet fast.

robots.txt

The crawler must fetch each site’s robots.txt before anything else, which creates a second request stream that can outweigh the first. A TTL (time to live) is how long a cached copy may be used before re-fetching.

• No cache: one robots.txt fetch per page, ~33 million a day.
• A shared 24-hour cache: one fetch per host per day, ~1 million, 33x fewer.
• A per-process cache across 16 fetcher processes: 16 million fetches, 16x worse than the shared cache.

The cache must be shared, not per-process, or you multiply the fetch count by the fleet size, and every one of those fetches consumes a politeness slot on the very host you are trying to be polite to.

Two status-code rules are easy to get backwards. A 4xx means allow-all: a missing robots.txt is a site saying nothing, so nothing is forbidden; crawl it. A 5xx or a timeout means disallow-all: a failing robots.txt is a site that is unwell, and hammering it is rude and useless; back off the whole host. Cache the negative verdict with a short TTL so a recovered site is picked up within minutes, not a day.

DNS

Every fetch needs the hostname turned into an IP first, and the obvious way saturates before a single page downloads. Resolving 1 million new hosts a day at ~100 ms each, serialized, is ~100,000 seconds of work, more than a full day’s worth (~1.16x) on one blocking resolver, before a single page is fetched.

The real problem is blocking: the calling thread sits idle until the answer arrives. getaddrinfo, the standard C library call every language’s DNS lookup reaches, is synchronous, and in several implementations of libc (the C standard library the OS ships) it serializes on a process-wide lock. So a crawler with one thread per fetch stalls its entire fleet behind DNS, no matter how many threads you give it.

The fix has two parts: an asynchronous resolver that keeps many queries outstanding at once over UDP (the connectionless protocol DNS runs on), plus an aggressive local cache. With the cache, only the first fetch of each host per day pays a resolution: ~10 recursive resolutions per second at a ~97% hit rate, trivial once it is off the critical path. Crawlers deliberately hold DNS entries far past their TTL (minutes to hours, against CDN TTLs of 30–60 s); a crawler does not need a browser’s failover precision, and re-resolving on every fetch would put you straight back at full resolver utilization.

Freshness: re-crawl by observed change rate

How often should you re-fetch a page you already have? The answer contradicts the intuitive policy.

The freshness formula

Model a page’s changes as a Poisson process at rate lambda (changes arrive independently at a constant average rate, with no memory). Re-crawl every T units of time. Then freshness F (the fraction of time your stored copy matches the live page, averaged over one interval) is:

F = (1 - e^(-lambda T)) / (lambda T)

The only input is the product lambda T, the expected changes per crawl interval:

Crawling a page exactly as often as it changes leaves you fresh only 63% of the time. Matching the change rate does not amount to keeping up, contrary to intuition.

The budget split

Take two pages and a budget of one fetch per day to split between them: a wire feed that changes 10 times a day (lambda = 10) and a slow blog that changes once every 10 days (lambda = 0.1). The Total column is the sum of the two freshness scores (best possible 2.0):

Allocating budget in proportion to change rate is 4.8x worse than allocating it uniformly, and it is the obvious policy. A page changing 10 times a day is stale almost all the time no matter what you do, so every fetch spent on it buys nearly nothing; the same fetch spent on a slow page buys almost all of that page’s freshness. Proportional allocation spends the budget precisely where it is worth least. The optimum is therefore non-monotonic in lambda: as a page changes faster, effort first rises, then falls back toward zero for pages you could never track. Uniform is within 0.6% of optimal and needs no per-page estimate, so uniform is what to ship. Do not build the estimator that gets the last 0.6%.

You still want a rough per-page lambda to cap the fast movers, estimated from observed intervals between changes with exponential smoothing (a weighted average that favors recent observations). A 304 is evidence of no change and must update the estimate too; skip it and every unchanged page drifts toward a fictitious high rate.

Conditional requests carry the previous ETag or Last-Modified so the server can answer with headers alone: a 304 is ~500 bytes against ~100 KB for a 200, so 200x cheaper in bytes and exactly as expensive in fetch slots. It still holds a connection and burns a full crawl-delay interval. Since bandwidth is at 53% of a NIC and host slots are the binding constraint, conditional requests save the resource you have plenty of and none of the resource you are short of. They are still worth doing for the origin server and your bandwidth bill, just not for throughput.

Coverage against freshness

The decision with a schedule attached is how much of the fetch rate goes to re-crawling pages you have versus discovering pages you do not. A 50/50 split leaves ~166 pages/s for discovery, so building a 10-billion-page corpus takes about 23 months. Freshness and coverage come out of the same budget, and the split is a product decision.

The code evaluates the formula and the four splits; total_freshness converts a budget share into an interval (1.0 / (budget * s)), and the search finds the optimal split instead of asserting it:

import math


def freshness(lam, period):
    """Time-average probability a copy is current under Poisson change."""
    x = lam * period
    return 1.0 if x == 0 else (1 - math.exp(-x)) / x


def total_freshness(rates, shares, budget=1.0):
    """shares[i] is page i's fraction of the fetch budget, in fetches/day."""
    return sum(freshness(lam, 1.0 / (budget * s))
               for lam, s in zip(rates, shares) if s > 0)


RATES = [10.0, 0.1]                      # a wire feed and a slow blog
proportional = [r / sum(RATES) for r in RATES]
uniform = [0.5, 0.5]
best = max(((a / 100, 1 - a / 100) for a in range(1, 100)),
           key=lambda s: total_freshness(RATES, list(s)))

assert abs(freshness(1.0, 1.0) - 0.632) < 0.001
assert abs(total_freshness(RATES, proportional) - 0.198) < 0.002
assert abs(total_freshness(RATES, uniform) - 0.956) < 0.002
assert abs(total_freshness(RATES, list(best)) - 0.962) < 0.002
assert 0.28 <= best[0] <= 0.38           # optimal is ~33% to the fast page
assert total_freshness(RATES, uniform) / total_freshness(RATES, proportional) > 4.8

Bottlenecks and scaling

Every resource the crawler consumes, and the number that bounds it. Only the first two rows are binding; everything below has slack.

The scaling conversation people expect is “add fetchers.” The scaling conversation that is true is “add hosts.” If the frontier is deep on 50 hosts (millions of URLs each, but only 50 distinct servers) a thousand machines fetch 50 x 0.833 = 42 pages/s between them, because that is all politeness permits. The other 999 machines are idle by construction, and no hardware changes that number.

Failure modes

Nine ways the design fails in production. Most are silent by default, so the detection column is the interesting one.

Four terms: 429/403 are “too many requests” and “forbidden,” and a spike in either is a server telling you politeness is not working. Jitter is a small random offset added to a scheduled time, so many timers do not fire in the same instant. A private, loopback, or link-local address (10.x, 127.0.0.1, 169.254.x) is only meaningful inside a network; refuse them after resolution, because a public hostname can resolve to one. 169.254.169.254 is the cloud metadata endpoint, so a crawler that follows a link to it fetches its own credentials. Enforced streaming checks the size cap while decompressing, not after. After is the point at which 10 GB is already in memory.

Design tradeoffs

Several designs look reasonable and fail for a specific, numeric reason. Two fail for a different reason than the folklore gives.

One global priority queue. Trivial, and priority is exact. But a page yields ~100 links to one host, so the head is always a burst against a single server. You either violate politeness 100x or scan the queue for a legal URL. The two-layer frontier exists precisely to make the politeness check O(1) instead of a search.

Partition the frontier by hash(url). Perfectly even load. But it spreads one host’s URLs across every shard, so “one connection to this host” becomes a distributed lock on every fetch. hash(ip) makes politeness a local timestamp comparison; the uneven load it creates is bounded by the per-host cap, not by the hash.

An exact URL set in a database instead of a bloom filter. No false positives, so no page is silently lost, but rejected on footprint and latency, not on device count. The folklore divides the lookup rate by 10,000 IOPS (input/output operations per second) and concludes you need several NVMe devices (the fast flash interface that replaced SATA). That 10,000 is a latency number (what one device delivers when you ask for one thing at a time) misread as a capacity number. At queue depth (many requests outstanding) an NVMe device delivers ~500,000 random-read IOPS, and the ~66,600 lookups/s at peak need about 0.13 of one device. What actually rejects the exact set: footprint (10 billion URLs at ~70 bytes is ~700 GB, against the filter’s 25 GB, it cannot live in RAM) and latency (an out-of-RAM lookup is a ~100 µs device read instead of a ~100 ns memory reference, a thousandfold more, on the hottest path). The right answer is both: bloom filter in front, exact set behind, so only the 0.0067% of “maybe” lookups pay that latency.

SHA-256 of the body for content dedup. Exact, cheap, no index, but a rendering timestamp changes every byte of the hash while changing zero bits of meaning, so recall against the 20% near-duplicate band is zero: 200 million wasted fetches a month.

Render every page in a headless browser (a real browser engine driven by code, so the page’s JavaScript runs). You see what a user sees, and single-page apps become crawlable. (A single-page app ships an almost-empty HTML document and builds the visible content in the browser, so a crawler reading only the HTML sees nothing.) But headless rendering is ~1 s of CPU per page against ~10 ms to parse, 100x, turning 6.7 cores into 666. Render selectively: a cheap classifier reads the raw HTML and asks whether the body has real text and whether the page loads a known SPA framework; only pages that answer badly get a browser, on an explicit capped budget.

Re-crawl in proportion to change rate. Intuitive, and the obvious policy, but it scores 0.198 against uniform’s 0.956, a 4.8x loss, since fetches spent on a page you can never keep up with buy nothing.

Skip robots.txt caching and fetch it per URL. Always current, but it doubles request volume against every host, and each of those fetches consumes one of the host’s politeness slots, taken from the very host the file protects. You are 33x more current about a file that changes weekly, and the site pays for it. The correct trade is a shared 24-hour cache with a short TTL on the negative verdict.

Conclusion

• The binding constraint is host diversity, not hardware. One host yields 0.833 pages/s (0.2 s fetch + 1 s delay), so throughput is hosts_in_flight x 0.833. Adding machines does nothing; adding hosts does everything. The 666 pages/s peak needs 800 distinct hosts, not 800 machines.
• Politeness decides the data structure. The frontier is two layers, front queues for priority, back queues (one host each) for politeness, with a sticky router between, and it shards on hash(ip) so politeness is a local timestamp comparison. The seen-set shards on hash(url) because dedup is per-URL: two shard keys, each making the thing it protects local.
• Both dedup filters can fail silently, so cost matters more than the rate. A bloom false positive is a page never crawled: run at 20 bits per key and alert on fill, not on error rate, because there is no ground truth. Exact hashing has zero recall on the 20% near-duplicate band, so content dedup needs a simhash plus a pigeonhole index.
• The web is hostile by accident. Depth caps, per-host budgets, and URL-length limits are all derived from numbers, not chosen, which is how you defend them. The per-host cap doubles as the diversity control that makes the fleet fast.
• Uniform re-crawl beats proportional by 4.8x. Fetches spent on a page you can never keep up with buy almost nothing; ship uniform and spend the real decision on the coverage-versus-freshness split.

One line to remember: a web crawler is bound by host diversity, not hardware: throughput is hosts_in_flight x 0.833, and every other number in the design is downstream of that one constant.

Further reading

• Heydon and Najork, Mercator: A Scalable, Extensible Web Crawler (1999): the design most modern crawlers descend from, including the front-queue/back-queue frontier.
• Lee, Leonard, Wang, and Loguinov, IRLbot: Scaling to 6 Billion Pages and Beyond (WWW 2008): trap avoidance, budget enforcement, and dedup at scale.
• Manku, Jain, and Das Sarma, Detecting Near-Duplicates for Web Crawling (WWW 2007): the simhash block-permutation index used here.
• Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (1970): the original bloom filter.
• Cho and Garcia-Molina, Effective Page Refresh Policies for Web Crawlers (2003): the freshness model and why proportional refresh is suboptimal.
• Broder, Glassman, Manasse, and Zweig, Syntactic Clustering of the Web (1997): shingling and minhash, the alternative sketch.