Token Bucket vs Leaky Bucket for Crawlers #

Both algorithms enforce an average rate, and choosing between them decides what your traffic looks like from the target’s side — smooth and predictable, or bursty within a bounded average. This guide compares them on the axes that matter for a crawler, shows both implementations, and explains when to layer one on the other. It sits under implementing polite rate limiting in the Compliance & Ethical Crawling Foundations section.

Problem Framing #

Suppose a target publishes a Crawl-delay of two seconds, and your frontier discovers a page containing forty links to that host. A token bucket with a capacity of forty will release all forty requests immediately and then throttle to one every two seconds; a leaky bucket will release them one every two seconds from the start. Over ten minutes both produce the same number of requests. Over the first second they produce forty and one respectively.

Same average, very different experience from the target side.

Which is correct depends entirely on what the host asked for. A Crawl-delay directive is a statement about the interval, not the average, and honouring it with a burst is not honouring it. A documented quota of “1000 requests per hour”, by contrast, says nothing about instantaneous rate and a modest burst is unobjectionable.

Getting this wrong in the permissive direction is the more common error, because a burst is invisible in your own averaged metrics and extremely visible in the target’s access log.

Step-by-Step Implementation #

1. The token bucket: bounded burst, exact average #

Production limiters layer all three and take the longest wait.

Tokens accumulate at a fixed rate up to a capacity; each request consumes one. Capacity is the burst size, refill rate is the long-run average.

import time

class TokenBucket:
    """Bursty up to `capacity`, averaging `rate` requests per second."""

    def __init__(self, rate: float, capacity: float):
        self.rate = rate
        self.capacity = capacity
        self._tokens = capacity
        self._updated = time.monotonic()

    def _refill(self, now: float) -> None:
        self._tokens = min(self.capacity, self._tokens + (now - self._updated) * self.rate)
        self._updated = now

    def acquire(self) -> float:
        """Seconds the caller must wait; 0.0 if a token was available now."""
        now = time.monotonic()
        self._refill(now)
        if self._tokens >= 1.0:
            self._tokens -= 1.0
            return 0.0
        return (1.0 - self._tokens) / self.rate

Setting capacity equal to rate gives one second’s worth of burst, which is usually enough to let a small discovered batch depart together without producing a spike anyone would notice. Setting capacity to sixty times the rate gives a full minute’s burst, which almost certainly will be noticed.

2. The leaky bucket: no burst, guaranteed interval #

Model it as departures at a fixed interval. There is no accumulated credit to spend, so an idle period buys nothing.

class LeakyBucket:
    """Strictly one request per `interval` seconds. Idle time earns no credit."""

    def __init__(self, interval: float):
        self.interval = interval
        self._next_allowed = 0.0

    def acquire(self) -> float:
        now = time.monotonic()
        if now >= self._next_allowed:
            self._next_allowed = now + self.interval
            return 0.0
        wait = self._next_allowed - now
        self._next_allowed += self.interval      # reserve this slot for the caller
        return wait

The reservation on the wait path is what makes this fair under concurrency: each caller gets its own future slot rather than several callers all waiting for the same one and then departing together, which would reintroduce exactly the burst the algorithm exists to prevent.

3. Layer them, because they answer different questions #

A production limiter usually needs both, plus a window counter for a published quota. Take the maximum wait of all the layers.

class HostLimiter:
    """Interval floor + burst shaping + quota ceiling. All three must permit a departure."""

    def __init__(self, interval_floor: float, burst_rate: float,
                 burst_capacity: float, quota: int, window_seconds: float):
        self.leaky = LeakyBucket(interval_floor)
        self.token = TokenBucket(burst_rate, burst_capacity)
        self.window = SlidingWindow(quota, window_seconds)

    def acquire(self) -> float:
        return max(self.leaky.acquire(), self.token.acquire(), self.window.acquire())

Order matters less than the max, but note that each layer’s acquire has a side effect — it consumes credit — so calling them all and taking the maximum means a request that waits still consumes from every layer. That is the correct behaviour: the request will depart, just later, and every layer should account for it.

4. Choose the parameters from what the host published #

def limiter_for(entry) -> HostLimiter:
    """Derive limiter settings from the registry entry and the rules snapshot."""
    interval = max(entry.crawl_delay_floor_seconds, entry.rules_crawl_delay or 0.0)
    rpm = entry.max_requests_per_minute
    return HostLimiter(
        interval_floor=interval,
        burst_rate=rpm / 60.0,
        # Burst capacity of one second's worth: enough to smooth scheduling jitter,
        # small enough that the host never sees a visible spike.
        burst_capacity=max(1.0, rpm / 60.0),
        quota=entry.daily_quota or 10 ** 9,
        window_seconds=86400.0,
    )

When a Crawl-delay exists, the leaky layer dominates and the token layer becomes inert — which is correct, because a declared interval is not a budget to be averaged. When no interval is declared, the token layer governs and the modest capacity keeps bursts inconspicuous.

Verification & Testing #

Both algorithms are deterministic given a clock, so inject one and assert on departure times rather than on wall-clock behaviour.

The first assertion survives every later throughput optimisation.

def test_token_bucket_bursts_then_throttles(fake_clock):
    bucket = TokenBucket(rate=1.0, capacity=5.0)
    departures = [bucket.acquire() for _ in range(8)]
    assert departures[:5] == [0.0] * 5          # burst of five
    assert all(w > 0 for w in departures[5:])   # then paced

def test_leaky_bucket_never_bursts(fake_clock):
    bucket = LeakyBucket(interval=2.0)
    waits = [bucket.acquire() for _ in range(4)]
    assert waits == [0.0, 2.0, 4.0, 6.0]        # each caller reserves its own slot

def test_layered_limiter_honours_the_strictest(fake_clock):
    limiter = HostLimiter(interval_floor=2.0, burst_rate=10.0,
                          burst_capacity=10.0, quota=1000, window_seconds=3600)
    assert limiter.acquire() == 0.0
    assert limiter.acquire() >= 2.0             # the interval floor wins over the burst

The third test is the one worth keeping forever: it asserts that adding burst capacity cannot override a declared interval, which is the property most likely to be broken by a well-meaning throughput optimisation.

Compliance & Operational Guardrails #

A published Crawl-delay is enforced by the interval layer, never averaged away by a burst.
Burst capacity defaults to about one second of traffic; larger values need a recorded justification.
All layers are keyed per host and shared across workers, not per process.
The applied wait and the layer that produced it are logged, so pacing decisions are explicable.
Adding capacity — more workers, more egress endpoints — never changes any layer’s parameters.

Common Mistakes #

Using a large token-bucket capacity to “catch up” after an idle period. The host experiences a spike precisely when your crawler resumes, which is the worst possible timing.
Implementing the leaky bucket without slot reservation. Concurrent callers all wait for the same instant and then depart together.
Enforcing only a window quota. A thousand requests per hour permits a thousand requests in the first second, which satisfies the quota and nothing else.

Frequently Asked Questions #

Which should be the default for a general crawler? #

A leaky bucket at the published or configured interval, with a small token bucket on top for scheduling smoothness. That combination honours declared intervals exactly while absorbing the millisecond-level jitter that scheduling introduces, and it never produces a burst large enough to register in a target’s monitoring.

How does this interact with concurrency limits? #

They are orthogonal and both are needed. The limiter governs how often a request may depart; a semaphore governs how many may be in flight. A crawler with a two-second interval and unbounded concurrency can still hold dozens of open connections against a slow host, which is covered in per-host concurrency limits with asyncio semaphores.

Where should the wait actually happen? #

In the scheduler, not the fetcher. Returning a wait rather than sleeping lets the frontier defer the URL and pick a different host instead of parking a worker, which is the politeness-aware scheduling behaviour that keeps one slow target from throttling the whole crawl.

How should the limiter behave when a host has never been seen before? #

Start at the most conservative configured setting and let observation relax it, never the reverse. A new host has no history, no observed latency and often no registry entry yet, so the safe default is the configured floor interval with a burst capacity of one. If the host turns out to publish a generous crawl budget, the limiter widens within a few observations; if it turns out to be fragile, nothing was damaged in the meantime. The opposite default — start fast, back off on failure — guarantees that the first thing every new host experiences is your worst behaviour.

What happens when the clock moves? #

Use a monotonic clock for interval arithmetic rather than wall time. Wall time can jump backwards when a machine synchronises, which makes an elapsed interval negative and can grant a burst of tokens that was never earned. Where limiter state is shared across processes, pass a timestamp from a single source into the atomic script rather than reading each worker’s own clock, so a skewed worker cannot spend credit the others have not accumulated.

Implementing Polite Rate Limiting — where these limiters sit in the request path.
Per-Host Concurrency Limits With Asyncio Semaphores — the second dial that rate alone does not cover.
Adaptive Rate Limiting From Response Headers — deriving the parameters from what the host publishes.