Design a web crawler: frontier, politeness, and dedup

The first version of every crawler is a loop: pop a URL, fetch it, parse the links, push them. It runs fine against a test site. Pointed at the real web, it produces three incidents by the afternoon. One host's operator emails to say your address is blocked. The queue grows from ten thousand URLs to forty million and the process runs out of memory. And the fetch rate, the number everyone was watching, falls, because most of the queue now belongs to a few large hosts that the loop is hammering one request at a time.

None of these are fetching problems. Fetching a page is an HTTP GET. A crawler is a scheduler that decides which of billions of URLs deserves the next GET, which host may receive it right now, and which URLs are not worth a request at all. Get the scheduling right and the fetching is a thread pool.

Take a target of one billion pages a month.

fetch rate:   1,000,000,000 / (30 x 86,400 s)  =  386 pages/s, call it 400/s
bandwidth:    400/s x 100 KB average page       =  40 MB/s, about 320 Mbit/s inbound
raw storage:  1,000,000,000 x 100 KB            =  100 TB/month before compression
discovery:    400 pages/s x ~50 links per page  =  20,000 URLs/s to check

The hard numbers are the last two lines. A hundred terabytes a month of HTML means the body store is object storage from day one, not a database column. And twenty thousand discovered URLs a second, fifty times the fetch rate, means the dedup check is the hottest path in the system and the frontier grows without bound unless something other than "first seen, first fetched" decides what gets in. Back-of-the-envelope estimation is the whole first hour of this design.

Two rules shape the frontier, where discovered URLs wait. Priority: a news site's front page and a page linked from nowhere are not worth the same fetch. Politeness: however many URLs a host has queued, only one request at a time goes to that host, with a gap between requests.

The structure that satisfies both is a set of per-host queues fed from a priority stage, plus a heap of hosts keyed by the time each host is next allowed a request. Discovered URLs are scored (link depth, domain reputation, observed change rate) and appended to their host's queue. A fetcher never asks "what is the next URL". It asks "which host is allowed a request right now", pops that host from the heap, takes its oldest URL, and pushes the host back with a new allowed time.

public sealed class HostScheduler
{
    private readonly PriorityQueue<string, DateTimeOffset> _ready = new();
    private readonly Dictionary<string, Queue<CrawlUrl>> _perHost = new();
    private readonly TimeSpan _minGap = TimeSpan.FromSeconds(2);

    public bool TryTakeNext(DateTimeOffset now, out CrawlUrl url)
    {
        url = default!;
        if (!_ready.TryPeek(out var host, out var allowedAt) || allowedAt > now)
        {
            return false; // every host with work is still inside its gap
        }

        _ready.Dequeue();
        var queue = _perHost[host];
        url = queue.Dequeue();

        if (queue.Count > 0)
        {
            _ready.Enqueue(host, now + _minGap); // re-arm the host, not the URL
        }

        return true;
    }
}

The gap can adapt: a host answering in 80 ms can take a request a second, one answering in 3 s gets a longer gap, because response time is the host telling you how loaded it is. Everything here must be durable: the frontier of a crawler that runs for months is a database or a partitioned log with an in-memory working set, not a Queue<T> that dies with the process.

A crawler's throughput is not set by how fast it can fetch. It is set by how many distinct hosts it is allowed to be talking to at once.

That explains the falling fetch rate from the opening. With a two second gap, one host yields half a fetch per second, so 400 fetches a second needs at least 800 hosts with queued work at every moment. The frontier has to be breadth-first across hosts even when it is priority-first within one.

Before a host's first request, the crawler fetches /robots.txt, parses the rules for its user agent, and caches them. RFC 9309 lets the crawler cache that file and says not to rely on a cached copy for more than 24 hours unless the file has become unreachable, so a per-host cache with a one day TTL is the right shape. Check each discovered URL against the rules at scheduling time, not fetch time, so a disallowed URL never occupies a queue slot.

DNS is the quiet cost. Four hundred fetches a second is four hundred resolver lookups a second if the HTTP client resolves on every request, and resolvers rate limit. Resolve once per host, cache the addresses with the record TTL, and treat a resolution failure as a host-level pause rather than a URL-level retry. Here the crawler is the client being rate limited, so it should limit itself first.

Fetching and parsing fail differently. A fetch fails because of the network; a parse fails because of the page, and a page that crashes the HTML parser will crash it again on every retry. If the two are one function, a parser bug refetches the page, spends the host's politeness budget, and loops.

Split them with a checkpoint. The fetcher writes the raw body to the blob store, records a fetch row with the URL, status, content hash, and storage key, and marks the frontier entry done. A parser job then reads the body from storage. A parser crash retries from stored bytes, a parser bug fixed next week replays across a month of fetches, and the host never sees a second request.

{
  "url": "https://example.org/docs/index.html",
  "fetchedAt": "2026-09-21T09:14:03Z",
  "status": 200,
  "contentHash": "sha256:9f2c...",
  "bodyKey": "bodies/2026/09/21/9f2c...",
  "parsed": false
}

The same page is discovered many times under many spellings. Normalize first: lowercase the scheme and host, drop the default port and the fragment, resolve dot segments as RFC 3986 section 6 describes, and strip query parameters you know are tracking noise. Then check the canonical string against the set of URLs already seen.

An exact set does not survive the arithmetic. A billion canonical URLs at 80 bytes each is 80 GB, shared by every worker, at 20,000 lookups a second. A Bloom filter holds a billion entries at a one percent false positive rate in about 1.2 GB (roughly 9.6 bits per entry) and fits in every worker's memory. The cost is that one URL in a hundred is wrongly believed seen and never fetched, which a crawler can accept because the page is usually discovered again through another link. When it cannot, a sorted key-value store gives an exact answer at the price of a disk read per check, with the Bloom filter in front so only the "maybe seen" URLs pay for it.

With many workers, per-host state (last fetch time, robots rules, resolved addresses) is cheapest to keep inside one worker. Partition the host space with consistent hashing: every URL for example.org routes to the worker that owns that host, so politeness is a local variable rather than a distributed lock, and adding a worker moves a fraction of the hosts rather than all of them. The seen-set can be partitioned by the same key.

Two different URLs often return the same bytes: mirrors, http and https, a trailing slash. Hash the body and index the hash; an exact match is stored once and the parse is skipped. Near-duplicates (the same article with a different sidebar) need a similarity fingerprint. Simhash produces a 64-bit value in which similar documents differ in only a few bits, so near-duplicate detection becomes a Hamming distance check against an index of fingerprints.

Freshness is a scheduling decision again. Record whether the content hash changed on each recrawl and derive a change rate per URL. A page that changed on its last three visits earns a shorter interval; one unchanged for ten visits has its interval doubled, up to a cap. The rate feeds the priority score, so fetches go to pages likely to have changed. The parsed documents then flow into an index the way a change data capture pipeline feeds a search index.

The failure modes are all about the frontier's size. Calendars with a "next month" link, session ids in URLs, and unbounded pagination generate infinite URL spaces; a depth cap per host, a per-host URL budget, and a rule that deprioritizes a host whose URLs keep hashing to the same content are the guards. Watch the ratio of discovered to fetched URLs: when it climbs, the priority function, not the fetcher count, needs attention. The frontier is a load-leveling queue whose producer is the web itself, and the web does not slow down when you fall behind.

Each decision above is a box and an edge that the naive loop does not have. Katabench's System Design Studio has a "Build a Distributed Web Crawler" series that adds them one at a time: "Start the URL Frontier", "Checkpoint Before Parsing", "Deduplicate Discovered URLs", "Cache DNS and Robots Rules", "Schedule Hosts Politely", "Partition Crawl Ownership", "Deduplicate Page Content", "Recrawl for Freshness", "Index the Crawled Web", and "Operate the Web Crawler". Each challenge checks the canvas against authored structural rules (the parser reads from storage rather than refetching, no worker bypasses the frontier, every host has one owner), so the feedback is about the topology rather than the drawing. The tracks overview shows where the Studio sits next to the code tracks.