Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Worked design: a web crawler

A crawler designed from the morning a site blocked it: per-host queues paced by a politeness scheduler, a fetcher pool on leases, cached robots.txt and DNS, URL and content dedup, revisit timing, and the traps that grow the frontier without end.

Blocked before lunch

The first version of the crawler was one queue of URLs, 300 fetchers taking from its head, and a parser pushing every link it found onto its tail. It ran well for an hour. Then one fetch returned a large retailer's sitemap, and its 40,000 product URLs went onto the queue in one block. For the next few minutes every fetcher pulled from that block: 300 requests at a time to one shop. The shop answered with 503, then with 429 Too Many Requests, and at 11:40 its firewall dropped the crawler's address range altogether. The rest of the web, queued behind the block, waited the whole time.

Nothing in that design was slow. It was rude, and a site that blocks a crawler gives it nothing at all. The rest of the design follows from the rule that morning taught: the parallelism has to come from breadth across hosts, not from depth into one.

How much crawling, how fast

Say the target is 1 billion pages a month. A month is about 2.6 million seconds, so that is ~400 pages a second, sustained. At an average 500 KB a page, that is 200 MB a second inbound and ~500 TB a month raw before compression, written straight to object storage. If a fetch takes 500 ms on average, 400 pages a second keeps about 200 requests in flight, and the pool is sized with a wide margin over that, because slow hosts hold their slots for seconds; the method is the one in Approaching a system design problem.

Now put the retailer back in. A polite crawler fetches about one page a second from a host, so a 10-million-page shop takes months to crawl in full, and the design accepts that rather than getting banned. The 400 a second comes from hundreds or thousands of hosts at once, each contributing a little: a throughput pipeline bounded by politeness.

A queue per host, and a clock for each

So the URL frontier, the store of URLs waiting to be fetched, stops being one FIFO. It becomes a set of per-host queues: every URL is filed under its host, and the retailer's 40,000 links land in one queue while every other host keeps its own. A politeness scheduler decides when each host's next URL is released: at most one request per host per politeness interval, say one second, or longer if the host asks for it (a Crawl-delay line in robots.txt, outside the standard, which some crawlers honour). It releases a host's next URL only after that host's previous fetch has finished, so released URLs do not pile up into a later burst and each host normally has one fetch in flight. A priority layer on top orders each host's URLs by importance and by how stale the stored copy is.

Millions of hosts do not need millions of physical queues: classic crawlers such as Mercator keep a fixed set of queues, each lent to one host at a time, and a heap of when each host may next be fetched. Across machines the frontier is partitioned by host, so each host has one owner that paces it without coordination.

A fetcher leases the next released URL and acknowledges it only once what it fetched is stored durably and queued for parsing; until then, an expired lease returns the URL to its queue, so a fetcher that dies or stalls costs a repeat fetch, not a lost URL. The fetcher resolves the host through a local DNS cache (at 400 lookups a second, DNS is a real cost), checks the host's robots.txt, cached for up to a day, downloads, and writes the raw bytes to object storage.

Fetch path: the scheduler paces per-host queues, fetchers lease from them

When a server errors on robots.txt itself, the standard for that file (RFC 9309) says to treat everything as disallowed until it can be read. And when a host starts answering 429 or 503, the scheduler widens that host's interval, honouring a Retry-After header if there is one: what the retailer was asking for before it blocked.

What a fetched page hands back

Parsing runs as a separate pool reading from the raw store. In one process with fetching, a parser crash on a malformed page takes a fetch slot down with it, and CPU-bound parsing can only scale together with IO-bound fetching. Each page hands back two things: its links and its content.

Links are normalised first: lowercase the host, drop the #fragment and known tracking parameters, resolve relative paths. example.com/a, EXAMPLE.com/a, example.com/a?utm_source=x and example.com/a#top are one page; compare raw strings and each spelling is a new URL, and the frontier fills with copies of the same content.

Only URLs never seen before enter the frontier, and an exact seen set of 5 billion URLs, at around 100 bytes each, is half a terabyte. So the check is a Bloom filter: about 10 bits a URL for a 1% false-positive rate, roughly 6 GB. Data structures behind big systems opens it up; the crawler only cares about its two answers. Definitely not seen is always right, so no known URL slips back in. For a URL never added, it answers probably seen about 1% of the time, and each of those is a new page dropped silently, for as long as that filter is in use, so size it for the loss you accept and the URLs it will hold. Revisits never go through the filter; they come from the crawler's URL records.

Content gets its own check, because different URLs often serve the same page: mirrors, print versions, one article under two paths. A hash of the bytes catches exact copies only, so crawlers add a near-duplicate fingerprint, such as simhash, under which pages that differ in an ad block or a date come out a few bits apart; finding close is then a search within a few bits, not an exact lookup. A page already in the seen-content store goes no further; the rest go to the indexer, where Full-text search picks up and the Web Search Engine Challenge builds on.

Parse path: dedup content and URLs, loop links back

Coming back for the same page

Pages change, so each carries a next-visit time and goes back into the frontier when due. The usual rule adapts: changed since the last visit, come back sooner; unchanged, later, between a floor and a ceiling. A news front page's interval settles at minutes, an old product manual's at months. A conditional request (If-Modified-Since, If-None-Match) lets the server answer 304 Not Modified without a body, the same revalidation browsers use (HTTP caching: Cache-Control, ETags & revalidation); not every server honours it, so the content fingerprint has the final word on change.

Pages that never end

The second failure came from inside the frontier. A city site's event calendar had a next month link on every page, so /events?month=2026-11 led to 2026-12 and on through the decades, each a distinct URL. Another put a session ID in every path. These are crawler traps, pages that generate links without end. Per-host queues stop a trap from hurting its host or holding up others, but not from growing: its queue gets longer forever, and the crawler spends that host's fetches on pages worth nothing.

No single test catches every trap, so crawlers stack cheap ones: caps on path depth and URL length, normalisation that strips known session parameters, a watch for hosts whose new URLs keep producing fingerprints already seen, and a page budget per host per crawl cycle. The budget is the backstop: a trap that slips past the rest costs its host's budget of fetches, and a cap on each host's queue stops its URLs piling up.

When a part breaks

  • A fetcher dies: its leases time out and the URLs return to their queues. A page can then be fetched twice, costing the host one more request, and the content check stops the second copy before the indexer.
  • One host is slow or down: only its queue backs up, and with one fetch at a time per host, cut off by a fetch timeout, it ties up one fetcher slot, not the pool: the isolation the single queue lacked.
  • The Bloom filter is lost: rebuild it from the URL records in a batch, or accept a window of re-fetches. Either way nothing stored is corrupted.

Where politeness lives

The Web Crawler Challenge asks for this pipeline, from seeds to a page store for indexing, and the decision it makes you defend on the Grid is where politeness is enforced. Put it in the politeness scheduler, releasing each host's URLs into the URL frontier at that host's interval, and let the fetcher pool lease only what has been released. Write the interval on the release edge, and draw the URL check and the content check as separate edges from the parser pool, each labelled with the duplicate it catches.

Practice this