Politeness and back queues

Politeness means not overloading any one website. Fetching is fast, so a crawler can easily send dozens of requests a second to one small site. The fix, used in Mercator and many crawlers since, is a queue per host plus a heap that records when each host may be contacted again.

The big idea

Picture a bank with one line per customer group, where each group is one host. A board lists when each line may call its next customer. The tellers never sit idle while any line is ready, and no single line is served too fast.

The picture breaks when a line stays slow. A slow host needs a longer wait, and the delay has to adapt to it.

Walking through it

The fetcher follows four steps:

1. Pop the host at the top of the heap. Wait until its time has come, if needed.
2. Take the next URL from that host's back queue, then fetch it.
3. If the back queue is empty, pull from the front queues, and assign that URL's host to this back queue.
4. Push the host back onto the heap with next_time = now + delay.

The delay is max(1 second, 10 × last response time). A slow host gets more room.

Here is a short trace with three hosts. Times are in seconds since the crawl started:

Heap (ready_at, host):  (0.5, wiki.org), (1.0, blog.test), (2.0, cnn.com)

At t = 0.6: top is wiki.org, ready at 0.5 → fetch it
  wiki.org last response was 0.3 s → delay = max(1, 10 × 0.3) = 3 s
  push (3.6, wiki.org)

At t = 1.0: top is blog.test, ready at 1.0 → fetch it

Nothing waits on a host that is not ready. The heap decides the order, and the delay keeps each host polite.

The design has about three back queues per fetcher thread. With 300 fetcher threads, that is roughly 900 back queues. While one host cools down, a thread can fetch from another host's queue.

Sharding by host

Assign each host to one worker, using a hash of the host name. Then one worker holds all of a host's politeness state. Two workers never fetch the same site at once, and no cross-machine coordination is needed. Sharding by URL would split a host across workers and break the limits.

Common mistakes

• One shared queue. A single slow host blocks threads that could fetch from elsewhere.
• A fixed delay for every host. Slow hosts still get hammered, and fast hosts wait too long.
• Sharding by URL. Each host's rate limit is then split across machines, and no single machine enforces it.
• Ignoring 429 responses. Back off exponentially and reduce the budget for that host.

Check yourself

1. A host's last response took 0.3 seconds. What delay applies under the rule max(1 s, 10 × latency)?

Answer: 3 seconds, since 10 × 0.3 = 3, which is larger than 1.

2. Why shard the crawl by host rather than by URL?

Answer: All of one host's politeness state lives on one worker, so its limits hold without coordination between machines.

Key takeaways

• One back queue per host keeps politeness local to one place.
• A heap of next-allowed fetch times wakes the right host at the right moment.
• The politeness delay grows with the host's latency, so slow hosts get more room.
• Shard by host, so each host has exactly one owner.

Further learning

Next, see how the crawler avoids fetching the same page twice in deduplication.