Web Crawler

In plain words

A web crawler downloads pages, finds the links in them, and downloads those too — for the whole web. The loop is easy. What is hard is remembering a billion addresses you have already seen, being polite to each website while still going fast overall, and not losing your place when a machine dies.

The numbers

Assume a billion pages a month, so about 400 pages/s sustained, with room to run ten times that during a full re-crawl. Each page yields around 40 links, of which nearly all have been seen.

pages fetched, sustained

400 /s

'seen before?' checks (40 per page)

16 K /s

a fetch — almost all of it waiting

400 ms

to remember a billion URLs (Bloom filter)

1.2 GB

Worked the way back-of-envelope estimation describes: a few facts, a few multiplications, and the big number tells you the shape of the problem.

The fetch rate is chosen, not discovered. Everything downstream is sized from it, and the seen-URL check — forty per page — is the busiest operation in the system.

Decision 1: the frontier is the crawler

The URL frontier — the crawler's to-do list — is a queue with two jobs that pull in opposite directions. Priority says important pages first: a news front page before a forum archive. Politeness says no host is fetched more than once every few seconds, whatever its priority.

1. Front queues, one per priority

   New URLs go into a queue by importance. High-priority queues are drained more often.

2. Back queues, one per host

   Each host has its own queue and a timer: "not before 14:02:07.5". URLs move from front queues to their host's back queue.

3. A worker asks for the next URL

   It gets one from a host whose timer has expired, chosen from the highest-priority front queue that has something for it. No worker ever coordinates with another about a host — the frontier does it for them.

import heapq, time

class Frontier:
    def __init__(self, min_gap=2.0):
        self.by_host = {}          # host -> deque of URLs
        self.ready = []            # heap of (next_allowed_time, host)
        self.min_gap = min_gap

    def push(self, url):
        host = hostname(url)
        if host not in self.by_host:
            self.by_host[host] = deque()
            heapq.heappush(self.ready, (time.time(), host))   # allowed now
        self.by_host[host].append(url)

    def next_url(self):
        allowed_at, host = heapq.heappop(self.ready)           # host whose timer expired soonest
        if allowed_at > time.time():
            heapq.heappush(self.ready, (allowed_at, host)); return None  # nothing polite to do yet
        url = self.by_host[host].popleft()
        if self.by_host[host]:
            heapq.heappush(self.ready, (time.time() + self.min_gap, host))  # this host again in 2 s, not before
        return url

Decision 2: have we seen this URL?

Forty links per page at 400 pages a second is 16,000 "seen?" checks a second against a set of a billion URLs. An exact set is tens of gigabytes — too big for memory, too slow on disk at that rate.

A Bloom filter answers from memory in a fraction of the space: a billion URLs at a 1% false-positive rate (how often it wrongly says "seen") is about 1.2 GB. It never says "not seen" for a URL that was seen. It occasionally says "seen" for one that was not — and the crawler simply skips that page. A few missed pages in a billion is a fine price for a check that costs nothing.

for link in extract_links(page):
    url = normalise(link)                 # lowercase host, strip fragment, sort query params
    if seen.might_contain(url):           # 99% of links: skip, no disk touched
        continue
    seen.add(url)
    frontier.push(url)

The same trick, applied to content, catches duplicates: a simhash of the page text — a fingerprint where similar text gives similar bits — compared by counting differing bits, finds the same article mirrored under a different address.

Decision 3: fetchers wait, parsers work

They are different kinds of machine and should be sized separately. DNS — turning a hostname into an address — is the dependency nobody draws: a billion pages is a billion lookups, and a local caching resolver turns that into a few percent of misses.

Where this design breaks

• A single huge host. Politeness caps any one host at a few requests a second, so crawling a site with a hundred million pages takes a year. That is correct; the fix is an agreement with the site, not a faster crawler.
• Crawler traps. Calendars that generate a page for every date, forever. Depth limits and per-host page budgets, enforced in the frontier.
• Losing the frontier. If it lives only in worker memory, one crash loses the crawl's place. It is a durable queue for exactly this reason.
• Re-crawl policy. Fetching everything monthly wastes most fetches on pages that never change. Track change frequency per page and let the scheduler use it.

Take this with you

• The one idea: the frontier is the crawler. Priority and politeness live in the queue, so workers can be dumb and many.
• In an interview, explain the two-layer frontier, the Bloom filter for "seen?", and why fetchers and parsers are different kinds of machine.
• At work, the same pattern — a durable to-do list feeding waiting-bound workers — is most batch pipelines. Size the workers by concurrent calls.