02. Web Crawler — Low-Level Design¶

~22 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)

The HLD named the boxes. This file opens the four that carry the design's weight — the URL frontier with politeness, the Bloom-backed seen-set, distributed fetching, and freshness scheduling — and pins down the data, the algorithms, and the concurrency corners where a crawler actually breaks.

Data models¶

The frontier's persistent state is a set of per-host queues plus one in-memory heap that decides which host is fetchable next.

# Per-host back queue (on disk, one logical queue per active host)
back_queue[host] = FIFO of { url, priority_band, enqueued_at }

# Host schedule heap (in RAM) — the politeness gate
heap entry: { host, next_fetch_at, back_queue_ref }
   ordered by next_fetch_at ASC   # the host due soonest is at the top

# Front queues (priority bands, on disk with in-memory heads)
front_queue[b] = FIFO   for b in 0..N   # 0 = highest priority (news re-crawl, seeds)

The two-level structure is deliberate. Front queues encode what to crawl next (priority): a re-crawled news homepage lands in band 0, ordinary discovered links in a middle band, trap-suspected URLs in the lowest. Back queues encode when a host may be touched (politeness): exactly one back queue per active host, and the host heap — keyed by each host's next_fetch_at — is what a fetcher consults to find a host that is due. Separating the two is what lets priority and politeness both hold at once.

The seen-set and freshness metadata are keyed by a URL fingerprint, not the raw URL, to bound key size.

url_fingerprint = 64-bit hash of the *canonicalized* URL   # 8 bytes, not ~80

# Freshness metadata (KV store, keyed by url_fingerprint)
{
  url_fp:            uint64,
  last_crawled_at:   timestamp,
  last_content_hash: uint64,      # exact-dup detection across re-crawls
  simhash:           uint64,      # near-dup detection across URLs
  change_interval:   seconds,     # adaptive; news ≈ 3600, static ≈ weeks
  next_crawl_at:     timestamp,
  consecutive_unchanged: uint8
}

Storing a 64-bit fingerprint instead of the ~80-byte URL is what makes the numbers work: the exact seen-set is 100e9 × 8 B = 800 GB rather than 100e9 × 80 B = 8 TB. Canonicalization before hashing is essential — otherwise http://Host.com/a, http://host.com/a/, and http://host.com/a?utm=x produce three fingerprints for one page and defeat dedup.

Component internals¶

Component 1 — URL Frontier with politeness¶

Responsibility: hand fetchers URLs in priority order while guaranteeing no host is fetched faster than its politeness delay.

class Frontier:
    def add(url, priority_band, discovered_from) -> None
    def get_next(fetcher_id) -> Lease | Empty      # politeness-gated, leased
    def ack(url, outcome, crawl_delay) -> None      # fetched | retry | dead

class HostHeap:
    def due_host(now) -> host | None                # top of heap if next_fetch_at <= now
    def reschedule(host, next_fetch_at) -> None

add runs a URL through canonicalization, the seen-set, and the robots.txt check, then routes it: choose the priority band for the front queue, and append to the host's back queue (creating one if the host is new, which also inserts the host into the heap with next_fetch_at = now). get_next is the politeness gate: it pops the host at the top of the heap only if that host's next_fetch_at <= now, takes the head URL from that host's back queue, and immediately reschedules the host to now + crawl_delay before returning. Because the reschedule happens at hand-out time, two fetchers cannot both be cleared to hit the same host inside its delay window.

Component 2 — Seen-set (Bloom filter + exact confirm)¶

Responsibility: answer "have I already discovered this URL?" in nanoseconds for the common case, with a bounded, known error.

class SeenSet:
    def contains(url_fp) -> SEEN | MAYBE_NEW       # Bloom test
    def confirm_and_add(url_fp) -> WAS_NEW | WAS_SEEN   # exact SSD tier

The Bloom filter uses k = 10 hash functions over an m ≈ 1.44e12-bit array for n = 100e9 URLs, giving the target 0.1% false-positive rate (m/n ≈ 14.4 bits/URL, k = (m/n)·ln2 ≈ 10). A Bloom filter has no false negatives: if it says SEEN, the URL was definitely added, so the crawler can drop it with zero disk access — that is the fast path taken by the vast majority of the thousands of duplicate links every page contains. Only a MAYBE_NEW answer touches the exact fingerprint tier on SSD to distinguish a true new URL from a 0.1% false positive; that confirmation both resolves the ambiguity and adds the fingerprint. This is what keeps the hottest check in the system in RAM while still being exact when it matters.

Component 3 — Distributed fetcher¶

Responsibility: download a leased URL politely and durably, without letting one slow host stall the fleet.

def fetch_loop(fetcher_id):
    while True:
        lease = frontier.get_next(fetcher_id)      # already politeness-cleared
        if lease is Empty: sleep_briefly(); continue
        ip = dns_cache.resolve(lease.host)          # cached; rarely a real lookup
        if not robots.allows(lease.host, lease.url):
            frontier.ack(lease.url, DEAD); continue
        resp = http_get(lease.url, timeout=10s, max_redirects=5)
        if resp.status in (429, 503):
            frontier.ack(lease.url, RETRY, backoff(resp)); continue
        content_ref = content_store.put(compress(resp.body))
        publish_fetched(lease.url, resp, content_ref)
        frontier.ack(lease.url, FETCHED, crawl_delay=robots.delay(lease.host))

Fetchers are stateless and I/O-bound, so a single machine runs hundreds to thousands of concurrent fetches (async or a thread pool); throughput per box is bounded by open connections, not CPU. Each URL is handed out under a lease with a visibility timeout: if the fetcher dies before ack, the lease expires and the frontier re-queues the URL, so a crash costs a retry, never a lost URL. Politeness is not re-checked here — it was enforced at get_next — which keeps the fetch path branch-light.

Core algorithm — the frontier scheduling loop under the news deadline¶

Walk the threaded scenario through the frontier: 10 billion pages while re-crawling 10,000 news domains hourly at ≤ 1 fetch/host/second.

The freshness scheduler wakes newssite.com's due pages and calls frontier.add(url, band=0, ...) for each — band 0 because a stale news page costs more than an undiscovered obscure one. Say 100 of its pages are due this hour.
add canonicalizes each URL, gets SEEN or MAYBE_NEW from the seen-set (re-crawls are already seen but are re-injected by fingerprint via the freshness path, bypassing the seen-drop), and appends to back_queue[newssite.com]. The host is in the heap with some next_fetch_at.
A fetcher calls get_next. The HostHeap returns newssite.com only if next_fetch_at <= now. It pops the head URL and immediately reschedules the host to now + 1s (its politeness delay).
The fetcher downloads that one page. The next get_next for newssite.com cannot succeed until now + 1s — so the host drains at exactly 1 page/second regardless of how many fetchers are idle. 100 due pages therefore take 100 seconds to sweep, well inside the hour.
Now the breaking-news failure: the domain publishes a flood and 5,000 pages come due. At 1/second the sweep needs 5,000 s ≈ 83 minutes — past the deadline. Two levers apply without breaking politeness: (a) a per-host cap on band-0 slots so this domain cannot also starve the other 9,999 news domains; (b) subset prioritization — refresh the homepage and section pages and newly-linked articles first (say the top 1,000), which sweeps in ~17 minutes, and let the long tail slip to next hour. (c) If newssite.com's robots.txt allows a 0.3s Crawl-delay, the heap reschedules to now + 0.3s and the 5,000-page sweep drops to ~25 minutes. The knob is always which pages and how fair, never fetch this host faster than it permits.
Meanwhile the 10B-page discovery crawl runs in the lower bands, filling fetcher slots left idle by the ~280 pages/second of news traffic, so the fleet stays near its polite ceiling.

The property that makes this correct: because rescheduling happens at hand-out time in step 3, the 1-fetch-per-second guarantee holds no matter how many fetchers race for the same host — politeness is a structural invariant of the heap, not a check that can be skipped under load.

Sequence diagram — a fetch cycle with dedup and re-scheduling¶

Scheduler   Frontier    HostHeap    Fetcher     Web       SeenSet    ContentStore  Freshness
   │  add(url,band0)│        │          │         │          │            │            │
   ├──────────────▶│ append │          │         │          │            │            │
   │               ├─ reschedule(host) ▶│         │          │            │            │
   │               │        │          │ get_next│          │            │            │
   │               │◀───────┼──────────┤         │          │            │            │
   │               ├ due_host(now)─────▶│         │          │            │            │
   │               │◀─ host (due) ──────┤         │          │            │            │
   │               ├─ reschedule(now+1s)▶│        │          │            │            │
   │               ├─ lease(url) ───────┼────────▶│          │            │            │
   │               │        │          │ http_get│          │            │            │
   │               │        │          ├────────▶│  HTML    │            │            │
   │               │        │          │◀────────┤          │            │            │
   │               │        │          ├─ put(compressed) ──┼────────────▶│            │
   │               │        │          ├─ extract links     │            │            │
   │               │        │          ├─ contains(fp) ────▶│ SEEN/MAYBE │            │
   │               │        │          │◀───────────────────┤            │            │
   │               │◀─ add(new links) ─┤ (unseen only)      │            │            │
   │               │        │          ├─ record(hash) ─────┼────────────┼───────────▶│ set next_crawl
   │               │        │          ├─ ack(FETCHED) ─────┼────────────┼────────────┤

One fetch drains exactly one URL from the host, reschedules the host by its delay, dedups the extracted links so only new ones re-enter the frontier, and lets the freshness service set the next re-crawl time from the content hash.

Freshness scheduling algorithm¶

Re-crawl interval adapts per page from observed change history, so budget flows to pages that change.

def on_recrawl(meta, new_content_hash):
    if new_content_hash == meta.last_content_hash:
        meta.consecutive_unchanged += 1
        meta.change_interval = min(meta.change_interval * 2, MAX_INTERVAL)  # calm down
    else:
        meta.consecutive_unchanged = 0
        meta.change_interval = max(meta.change_interval // 2, MIN_INTERVAL) # heat up
        content_store.put_version(meta.url_fp, new_content_hash)
    meta.next_crawl_at = now + meta.change_interval

A news homepage that changes on nearly every visit is driven toward MIN_INTERVAL (clamped at 1 hour by product policy for the news tier), while a static page that comes back unchanged repeatedly doubles its interval — 1h → 2h → 4h → … → capped at MAX_INTERVAL (say 30 days) — so the crawler stops wasting fetches on it. This is a coarse estimator of each page's change rate; the effect is that of the ~10,000/second polite ceiling, the fraction spent re-crawling is concentrated on pages that actually move, which is how hourly news freshness is afforded inside a fixed fetch budget.

Concurrency and edge cases¶

Two fetchers, one host (politeness race). Resolved structurally: get_next reschedules the host to now + delay before returning the lease, and the host heap only ever exposes a host whose next_fetch_at <= now. A second fetcher that polls in the same instant finds the host no longer due and gets a different host. Politeness cannot be violated by concurrency.
Duplicate discovery of the same URL. The same page is linked from thousands of others, so add is called for one URL many times concurrently. The Bloom SEEN fast-path drops the repeats without disk access; the one genuine first-add is made atomic in the exact tier with a compare-and-set on the fingerprint, so exactly one instance enqueues it.
Bloom false positive drops a real URL. ~0.1% of genuinely new URLs are wrongly judged SEEN and dropped — ~10M pages on a 10B crawl. Accepted, because important pages are linked from many sources and re-enter through another path; the exact-tier confirmation on MAYBE_NEW also catches most, since only true "possibly new" answers reach it.
Lease expiry vs. slow fetch. A genuinely slow (not crashed) fetch can exceed the visibility timeout, causing the URL to be re-leased and fetched twice. Made harmless by keying the content store on URL fingerprint + version so a double-store is idempotent; the second ack is ignored.
Canonicalization mismatch. If two forms of one URL canonicalize differently, they dedup as two pages and get crawled twice — a politeness and waste bug, not a correctness crash. Mitigated by a strict, well-tested canonicalizer (lowercase host, strip default ports, sort/strip tracking query params, resolve ./..) applied before every fingerprint.
Redirect chains and loops. A 301/302 is followed up to max_redirects=5; the final URL is canonicalized and re-checked against the seen-set so a redirect target already crawled is not stored again, and a redirect cycle terminates at the cap rather than looping.
robots.txt changes mid-crawl. The cache has a TTL; a path allowed at enqueue time may be disallowed by fetch time. The fetcher re-checks robots.allows at fetch time (cheap, in-memory) so the newest known rules win and a freshly-disallowed URL is dropped rather than fetched.