Distributed Crawling

"I am a crawler, politely knocking on a billion doors. I remember which ones I have already opened, I wait my turn at every house, and I never forget that someone downstream has to read everything I drag home."

A Fetcher Worker, Pacing Itself Behind a Per-Host Token Bucket

The previous section framed the web-scale RAG pipeline end to end: crawl, clean, chunk, embed, index, retrieve, generate. We now zoom into the first stage, because it is the one stage whose failure modes are invisible from the answer side. A retriever that returns nothing useful looks the same whether the relevant page was poorly embedded or simply never fetched, and only one of those is fixable downstream. Crawling is also the stage that most resembles the classic distributed-systems problems of this book: a shared data structure (the frontier) read and written by many workers, a partitioning of work across machines, a deduplication problem solved with a probabilistic set, and a coordination discipline (politeness) that the system must honor against external parties it does not control. Treating the crawl casually, as a script that loops over URLs, is the surest way to either miss most of the web or get every worker's IP address blocked.

1. The Frontier Is a Distributed Queue Beginner

The heart of a crawler is the frontier: the set of URLs discovered but not yet fetched. On one machine the frontier is just a queue; at web scale it is a distributed data structure that many workers consume concurrently, and almost every design decision in a crawler is really a decision about how that queue is partitioned, ordered, and kept consistent. The frontier holds billions of entries, far more than one machine's memory, so it must be sharded across nodes; and because the entries flow in faster than any single coordinator could hand them out one at a time, workers pull batches from their assigned shards rather than from a single global head.

The natural partition key is the host. We assign each URL to shard $\text{hash}(\text{host}) \bmod S$, so every URL belonging to example.com lands in the same shard regardless of which worker discovered it. This host-based sharding, the same partition-by-key idea introduced as a coordination concept in Chapter 2 and used for data shards in Chapter 8, is what makes politeness tractable: if one shard owns all of a host's URLs, then the worker draining that shard is the single place where that host's request rate is enforced, and no cross-worker coordination is needed to avoid hammering the host. The frontier is therefore not partitioned for storage reasons alone; the partition key is chosen so that the hardest coordination constraint, per-host politeness, becomes a local property of a single shard.

2. Politeness Is the Constraint That Shapes Everything Beginner

A crawler that fetches as fast as its workers allow is a denial-of-service attack with good intentions. Two disciplines keep it civil. The first is robots.txt: before fetching any URL on a host, the crawler retrieves and caches that host's robots file, which declares the paths the site owner permits or forbids and may specify a crawl delay. Honoring it is both an ethical and a practical necessity, because the alternative is a blocked IP range and a corpus with holes where the most valuable, most actively defended sites used to be. The second is rate limiting: even on permitted paths, the crawler spaces its requests to a single host, typically allowing only one in-flight request and a fixed gap between requests, so that the host sees a trickle rather than a flood.

These two disciplines interact with sharding to set the crawler's real throughput. A worker draining a shard cannot simply fetch as fast as its CPU and network allow; it is rate-limited per host, so its useful throughput depends on how many distinct hosts live in its shard. A shard dominated by one enormous host (a content farm, a wiki with millions of pages) is throttled to that one host's polite rate no matter how much hardware you give the worker, while a shard spread across thousands of small hosts can keep many fetches in flight concurrently. This is the crawler's version of the load-skew problem that haunts every partitioned system in this book, and it is why the host count per shard, not the URL count, is the quantity to watch.

3. Deduplicating the URL Space with a Bloom Filter Intermediate

The web is densely cross-linked, so the same URL is discovered again and again from different pages. If the crawler re-enqueues every discovered link, the frontier explodes and workers waste their politeness budget re-fetching pages they already have. The crawler therefore maintains a set of already-seen URLs and tests every newly extracted link against it before enqueueing. At web scale this set holds tens of billions of URLs, far too many to store as exact strings in memory, so crawlers use a Bloom filter: a bit array with $k$ hash functions that answers set membership in constant time and constant memory per element, at the price of a tunable false-positive rate.

The trade is worth understanding precisely because it sets a memory budget. A Bloom filter of $m$ bits holding $n$ elements with $k$ hash functions has false-positive probability

minimized by choosing $k = (m/n)\ln 2$ hash functions, which gives the clean relation $p \approx (0.6185)^{\,m/n}$. The crucial consequence is that the memory cost is a function of the false-positive rate you are willing to tolerate and the number of elements, not of the length of the URLs: at the optimal $k$, holding $p$ fixed costs roughly $m/n = -\log_2 p / \ln 2 \approx 1.44 \log_2(1/p)$ bits per URL. Ten billion URLs at a one-percent false-positive rate cost about $1.44 \cdot \log_2(100) \approx 9.6$ bits each, near twelve gigabytes, which is why the seen-set is itself distributed: sharded by the same host hash as the frontier, so the worker that owns a host also owns the dedup decisions for that host.

A false positive in this filter is benign in a specific way: it causes the crawler to wrongly believe it has already seen a URL and skip it, so a small false-positive rate means a small fraction of pages silently never fetched. That is a coverage loss, and coverage loss is exactly the kind of downstream-invisible damage this section warns about, so the budget is chosen with the RAG corpus in mind, not as a generic data-structures default. The code below builds a Bloom filter for seen-URL dedup, measures its actual false-positive rate against the theory at four memory budgets, and then confirms that host-hash partitioning balances the frontier across shards.

import hashlib, math, random

class BloomFilter:
    def __init__(self, n_bits, n_hashes):
        self.m = n_bits
        self.k = n_hashes
        self.bits = bytearray((n_bits + 7) // 8)

    def _idx(self, item, i):                       # i-th hash via a personalized BLAKE2b
        h = hashlib.blake2b(item.encode(), digest_size=16,
                            person=i.to_bytes(2, "little")).digest()
        return int.from_bytes(h, "little") % self.m

    def add(self, item):
        for i in range(self.k):
            j = self._idx(item, i)
            self.bits[j >> 3] |= (1 << (j & 7))   # set the bit

    def __contains__(self, item):
        for i in range(self.k):
            j = self._idx(item, i)
            if not (self.bits[j >> 3] & (1 << (j & 7))):
                return False                       # a clear bit proves "never seen"
        return True

n = 200_000                                        # distinct URLs already crawled
rng = random.Random(0)
seen  = [f"https://site{rng.randrange(50_000)}.com/page/{i}" for i in range(n)]
probe = [f"https://other{i}.net/path/{i}" for i in range(200_000)]   # never inserted

print(f"{'bits/url':>9} {'mem (MiB)':>10} {'k':>3} {'measured FPR':>13} {'theory FPR':>11}")
for bits_per_url in (4, 8, 12, 16):
    m = bits_per_url * n
    k = max(1, round((m / n) * math.log(2)))       # optimal hash count
    bf = BloomFilter(m, k)
    for u in seen:
        bf.add(u)
    fp = sum(1 for u in probe if u in bf)          # false positives among never-seen URLs
    measured = fp / len(probe)
    theory   = (1 - math.exp(-k * n / m)) ** k
    print(f"{bits_per_url:>9} {m/8/2**20:>10.2f} {k:>3} {measured:>13.5f} {theory:>11.5f}")

def host_of(url):  return url.split("//", 1)[1].split("/", 1)[0]
def shard_of(host, S):
    h = hashlib.blake2b(host.encode(), digest_size=8).digest()
    return int.from_bytes(h, "little") % S         # same partition key as the frontier

S = 16
counts = [0] * S
for u in seen:
    counts[shard_of(host_of(u), S)] += 1
mean, maxc = sum(counts) / S, max(counts)
print(f"\nshards={S}  urls={n}  mean/shard={mean:.0f}"
      f"  max/shard={maxc}  imbalance(max/mean)={maxc/mean:.3f}")

 bits/url  mem (MiB)   k  measured FPR  theory FPR
        4       0.10   3       0.14708     0.14689
        8       0.19   6       0.02184     0.02158
       12       0.29   8       0.00287     0.00314
       16       0.38  11       0.00044     0.00046

shards=16  urls=200000  mean/shard=12500  max/shard=12970  imbalance(max/mean)=1.038

4. The Throughput Arithmetic of a Crawl Intermediate

How many machines does a target crawl need? The aggregate fetch rate of the fleet is the per-worker rate times the worker count, capped by the politeness ceiling. If each of $W$ workers sustains $r$ fetches per second, the fleet's nominal rate is

and the wall-clock time to fetch a corpus of $N$ pages is $T = N / R = N / (W r)$. A concrete reading: at $r = 50$ pages per second per worker, a fleet of $W = 200$ workers fetches $R = 10{,}000$ pages per second, and a corpus of $N = 10^{9}$ pages takes $T = 10^{9} / 10^{4} = 10^{5}$ seconds, a little over a day. That arithmetic is necessary but not sufficient, because politeness imposes a second, independent ceiling. If the crawler allows at most one request every $\delta$ seconds to a host, then a single host yields at most $1/\delta$ pages per second, and a corpus concentrated on $H$ distinct hosts cannot be fetched faster than

regardless of how many workers you provision. The achievable rate is the smaller of the two, $R_{\text{eff}} = \min(W r,\; H/\delta)$. With a one-second politeness gap, fetching ten thousand pages per second requires drawing from at least ten thousand distinct hosts at any moment; a crawl of a few large hosts is host-bound, and adding workers past that point only raises cost. This is the same lesson as the practical example, now as an inequality you can evaluate before provisioning: count your hosts, not just your pages.

5. Coordination Hazards and Continuous Recrawl Advanced

A shared frontier read and written by hundreds of workers raises every consistency question of Chapter 2. Two workers can extract the same new URL at the same instant and both pass the Bloom-filter test before either inserts it, briefly enqueueing a duplicate; the seen-set therefore tolerates a small rate of duplicate fetches rather than serializing every insertion behind a global lock, trading exactness for throughput in exactly the way distributed systems usually must. A worker can crash mid-shard, so the frontier must record which URLs are leased to which worker and re-lease them on a timeout, the same lease-and-recover discipline that makes MapReduce re-execute failed tasks in Chapter 6. And the robots cache must be coherent enough that a forbidden path is not fetched by one worker just because another worker's cache had not yet refreshed.

Once the harvested pages land in distributed storage, the rest of the ingestion pipeline reads them as a batch: extracting text, deduplicating near-identical documents, and computing the cleaned corpus is a textbook MapReduce job, mapping over raw pages and reducing by content fingerprint, exactly the batch model of Chapter 6, and the raw and cleaned crawls live in the distributed object store of Chapter 8. A crawl is never finished, though. The web changes, and a corpus frozen at one crawl grows stale, so production systems run a continuous recrawl: a stream of re-fetch tasks prioritized by how often each page changes, processed by the stream-processing machinery of Chapter 9. Freshness is the temporal half of coverage, and for a RAG system answering questions about a moving world it is just as load-bearing as breadth.

import scrapy

class CorpusSpider(scrapy.Spider):
    name = "corpus"
    start_urls = ["https://example.com/"]
    custom_settings = {
        "ROBOTSTXT_OBEY": True,            # read and honor robots.txt
        "AUTOTHROTTLE_ENABLED": True,      # adapt the per-host rate to latency
        "CONCURRENT_REQUESTS_PER_DOMAIN": 1,
        "DOWNLOAD_DELAY": 1.0,             # the politeness gap, delta = 1 s
        "DUPEFILTER_CLASS":                # seen-URL dedup (Bloom-backed)
            "scrapy_bloom.BloomDupeFilter",
    }

    def parse(self, response):
        yield {"url": response.url, "html": response.text}   # to distributed storage
        for href in response.css("a::attr(href)").getall():  # discovered links
            yield response.follow(href, self.parse)           # re-enter the frontier