Two questions at once

Calling the frontier a priority queue undersells it badly.

It answers two questions at once. Which address matters most, and which address are you allowed to fetch right now.

See why those pull against each other. Your highest-priority addresses cluster on a few important domains, and politeness forbids hammering any single domain.

Use two layers of queues, the classic structure most textbooks descend from. Front queues split addresses by priority, with news and fast-changing pages high and deep archives low.

Back queues split by domain, one queue each, carrying a not-before time computed from the last request plus that domain's crawl delay.

Watch a fetcher ask for work. Your scheduler picks a domain queue whose time has passed, favouring the higher-priority refills, and hands out exactly one address.

Hold the invariant that matters: one domain never has two requests in flight, however many thousands of fetchers you run.

Shard by domain, never by address

Distribute it by hashing the domain, never the address, and this has one right answer. Hashing by domain gives each node exclusive ownership of its domains, so politeness state stays local with no coordination at all.

Hash by address instead and you scatter one domain across every node, turning each politeness check into a distributed locking problem.

Put the robots file on top as your legal-ish layer. Fetch it once per domain, cache it for about a day, honour what it disallows and the delay it asks for, and identify yourself honestly.

Go beyond compliance and adapt. Back off when a domain starts refusing you or its latency doubles, because a struggling server is telling you something. An operator who notices you is one firewall rule away from ending your crawl of their site.

the shape of it

step 1 of 3

Priority queues refill per-domain queues, and the scheduler releases a URL only when its domain's not-before timestamp has passed.

one domain, one request in flight, however many fetchers

Java

// Shard the frontier by hash of DOMAIN, never of URL. Domain
// hashing keeps politeness state local to one node, so no fetcher
// has to coordinate with another. URL hashing scatters one domain
// across every node and turns each check into distributed locking.
int node = Math.floorMod(hash(domainOf(url)), nodeCount);

Optional<String> next() {
  // Pick a domain queue whose not-before time has passed.
  for (DomainQueue q : byPriority()) {
    if (q.notBefore().isAfter(now()) || q.inFlight()) continue;

    q.setInFlight(true);
    q.setNotBefore(now().plus(q.crawlDelay()));   // from robots.txt
    return Optional.of(q.poll());
  }
  return Optional.empty();
}

Worked example

A market-research firm runs a 60-node crawl and shards the frontier by URL hash for even load. Each node keeps its own per-domain rate limiter at 1 request per second, which sounds polite until you multiply: a large retailer's URLs are spread across all 60 nodes, so the retailer sees up to 60 requests per second from one IP block. Two weeks in, their crawler's ASN lands on a shared blocklist, and coverage of the top 500 retail domains drops 70 percent overnight. Camille, brought in to fix it, reshards the frontier by domain hash so each domain belongs to exactly one node, making the 1 rps limit globally true, adds honest User-Agent headers with a contact email, and emails the blocklist maintainer. Delisting takes three weeks. The postmortem's first line: politeness that is not global is not politeness.

The Frontier and Politeness

Two questions at once

Shard by domain, never by address

Worked example