Design a Web Crawler

A distributed fetch pipeline

A crawler starts from seed URLs and repeatedly: takes a URL from the frontier (priority queues), respects robots.txt and per-host politeness limits, fetches the page, parses links and content, and adds unseen URLs back. At billions of URLs, a Bloom filter offers a compact "have we seen this?" check with a small false-positive rate and no false negatives; content hashes detect duplicate pages. Workers are partitioned by host so politeness is enforced locally.

A Bloom filter for seen URLs, run

I ran this with Python 3.12.3 using only the standard library; inputs are fixed or seeded, so the output is reproducible. With 10 bits per URL and 7 hash functions, 100,000 URLs fit in 122 KiB; a URL that was added is always found, and the measured false-positive rate of 0.814% matches the theoretical 0.819%.

# Bloom filter for a web crawler's "seen URL" check
import hashlib, math

class Bloom:
    def __init__(self, m_bits, k):
        self.m, self.k, self.bits = m_bits, k, bytearray(m_bits // 8 + 1)
    def _positions(self, item):
        d = hashlib.sha256(item.encode()).digest()
        h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:16], "big")
        return [(h1 + i * h2) % self.m for i in range(self.k)]
    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)
    def __contains__(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(item))

n, m = 100_000, 1_000_000                      # 10 bits per URL
k = round(m / n * math.log(2))                 # optimal number of hashes
bf = Bloom(m, k)
for i in range(n):
    bf.add(f"https://example.com/page/{i}")
print("k =", k, "| memory:", len(bf.bits) // 1024, "KiB")
print("seen URL found:", "https://example.com/page/123" in bf)
fp = sum(f"https://example.org/new/{i}" in bf for i in range(100_000))
print(f"false positive rate: measured {fp / 100_000:.3%}, theory {(1 - math.exp(-k * n / m)) ** k:.3%}")

Output:

k = 7 | memory: 122 KiB
seen URL found: True
false positive rate: measured 0.814%, theory 0.819%

Accept the trade-off explicitly

A false positive means skipping a new page occasionally; say why that is acceptable for a crawler.

त्वरित जाँच: What error can a Bloom filter make?

• Returning the wrong item
• Reporting an added item as absent
• Losing all items on restart only
• Reporting an item as present when it is not (false positive)