Token-Bucket vs Leaky-Bucket for Telemetry Shedding

When a geofence router must throttle admitted telemetry rather than drop it at a cliff, the rate limiter it uses decides whether a legitimate burst survives or gets shed. This page sits under backpressure and flow-control strategies and the broader event routing and backpressure architecture, and it answers one narrow question mobility teams search for by name: for bursty GPS telemetry, does a token bucket or a leaky bucket give the better shed behavior? The two algorithms look interchangeable on a whiteboard and diverge sharply under a real fleet’s load shape — one absorbs the shift-change spike, the other flattens it into a shed event. Getting this wrong shows up as either over-shedding legitimate bursts or letting a sustained overload leak through unthrottled.

Concept and specification #

Both algorithms cap a long-run admitted rate while differing in how they treat short-run bursts. The difference is entirely about where the “state” lives: a token bucket stores accumulated permission, a leaky bucket stores accumulated work.

Token bucket. A bucket holds up to $B$ tokens and refills at $r$ tokens per second. Each admitted event spends one token; an event arriving when the bucket is empty is shed. Because tokens accumulate up to $B$ during quiet periods, the bucket can admit a burst of up to $B$ events instantly, then falls back to the sustainable rate $r$. The maximum burst it will pass is:

$$N_{\text{burst}}=B+r\cdot t_{\text{burst}}$$

for a burst lasting $t_{\text{burst}}$ seconds. Capacity $B$ is the burst-tolerance knob; $r$ is the sustained ceiling.

Leaky bucket. Work enters a queue of depth $B$ that drains (“leaks”) at a fixed rate $r$. Admission is constant at $r$ regardless of arrival pattern; anything arriving when the queue is full is shed. It never emits a burst — the output is smoothed to $r$ by construction. The time to fill the leaky bucket from empty under an arrival rate $\lambda >r$ is:

$$t_{\text{fill}}=\frac{B}{\lambda -r}$$

after which it sheds the excess $\lambda -r$ continuously.

The distinction that matters for telemetry: a token bucket is rate-limiting with memory of idleness, so it rewards a stream that was quiet before a burst; a leaky bucket is rate-shaping without memory, so it treats every burst identically no matter how quiet things were. GPS fleets are bursty in a way that favors the token bucket — a delivery fleet is near-idle overnight, then all vehicles power on within a few minutes at shift start, and that burst is legitimate traffic you want to admit, not shed.

Resolution of the two knobs is the whole design. For a token bucket, set $r$ to the sustainable drain rate of the evaluation worker (the rate at which it can complete containment checks without the queue growing) and set $B$ to the largest legitimate burst you want to pass instantly — a value derived from the fleet’s power-on spread, not guessed. The per-item shed budget and how this feeds the queue watermark are covered in sizing bounded asyncio queues for geofence pipelines.

Step-by-step implementation #

Prerequisites: Python 3.11+, standard library only (time.monotonic for the clock). Both limiters are pure-float state machines with no background task — refill and leak are computed lazily on each call, so there is no timer coroutine competing for the event loop during a burst.

1. Implement the token bucket with lazy refill. No background timer: compute elapsed time on each call and credit tokens up to capacity.

from __future__ import annotations

import time
from dataclasses import dataclass, field


@dataclass(slots=True)
class TokenBucket:
    capacity: float          # B — max burst admitted instantly
    refill_per_s: float      # r — sustainable ceiling
    _tokens: float = field(default=0.0)
    _last: float = field(default_factory=time.monotonic)

    def __post_init__(self) -> None:
        self._tokens = self.capacity          # start full so a cold service tolerates a burst

    def try_admit(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        elapsed = now - self._last
        # Lazy refill, clamped to capacity — idle time accrues burst tolerance.
        self._tokens = min(self.capacity, self._tokens + elapsed * self.refill_per_s)
        self._last = now
        if self._tokens >= cost:
            self._tokens -= cost
            return True                        # admit
        return False                           # shed — bucket empty

2. Implement the leaky bucket as a lazily-drained level. The state is the current queue level; it leaks at r per second, and admission is allowed only while the level plus one stays under capacity.

@dataclass(slots=True)
class LeakyBucket:
    capacity: float          # B — queue depth before shedding
    leak_per_s: float        # r — constant drain / output rate
    _level: float = field(default=0.0)
    _last: float = field(default_factory=time.monotonic)

    def try_admit(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        # Lazy leak: drain the level by elapsed * r, floored at zero.
        self._level = max(0.0, self._level - (now - self._last) * self.leak_per_s)
        self._last = now
        if self._level + cost <= self.capacity:
            self._level += cost                # admit and enqueue the work
            return True
        return False                           # shed — bucket full

Gotcha: initialize the token bucket full (_tokens = capacity) but the leaky bucket empty (_level = 0). A cold token bucket that starts empty sheds the very first burst — exactly the shift-change spike you deployed it to survive. The __post_init__ above handles this; the leaky bucket has no equivalent hazard because an empty level is maximal headroom.

3. Wire the limiter into the admission decision. The limiter only engages for low-priority telemetry once the queue is meaningfully full, so it smooths bursts without penalizing normal load.

def admit_idle_ping(bucket: TokenBucket, queue_frac: float, item: object,
                    queue) -> bool:
    # Only throttle idle pings, and only once the queue is filling.
    if queue_frac >= 0.60 and not bucket.try_admit():
        return False                           # route to dead-letter
    queue.put_nowait(item)
    return True

Benchmark and verification #

The measured scenario is a 30k events/sec baseline driven to a 3x burst (90k/sec) for 5 seconds, with the evaluation worker sustaining 32k/sec. Both buckets are set to r = 32_000; the token bucket is given B = 24_000 (roughly 0.75s of headroom), and a deliberately undersized bucket B = 4_000 is included to show the failure mode.

The token bucket sized to the real burst admits ~89% of the shift-change spike and sheds only ~8% overall, because the accrued tokens cover the legitimate burst before throttling engages. The leaky bucket sheds ~29% — it cannot tell a legitimate burst from a sustained overload, so it flattens both. Critically, the undersized token bucket (B=4k) behaves almost like the leaky bucket, over-shedding by roughly 3x versus the correctly-sized one: with only ~0.12s of headroom it exhausts tokens almost immediately and sheds legitimate traffic it should have passed. A minimal harness:

import time


def bench_burst(limiter, baseline: int, burst_mult: int, secs: float) -> dict[str, float]:
    admitted = shed = 0
    rate = baseline * burst_mult
    interval = 1.0 / rate
    end = time.monotonic() + secs
    while time.monotonic() < end:
        if limiter.try_admit():
            admitted += 1
        else:
            shed += 1
        time.sleep(interval)                   # simulate arrival spacing
    total = admitted + shed
    return {"admitted": admitted, "shed": shed, "shed_rate": shed / total}

Verify before deploying: replay a captured real burst (not a synthetic constant rate) through both limiters and compare shed rates. The token bucket’s advantage only materializes against bursty input; against a truly constant overload the two converge, because there is no idleness for tokens to accrue against.

Failure modes and edge cases #

• Bucket too small (over-shed). The dominant failure. A token bucket with B below the legitimate burst size sheds traffic it should pass, degrading to leaky-bucket behavior. Size B from the measured burst (power-on spread times device count), never from a round number.
• Bucket too large (masks sustained overload). The opposite error: a huge B admits a sustained overload for B/r seconds before throttling, letting the downstream queue grow past its bound in the meantime. B must be a burst budget, not a reservoir; cap it near one second of headroom.
• Clock choice. Use time.monotonic, never time.time. A wall-clock adjustment (NTP step) can make elapsed negative, crediting a negative refill or leak and corrupting the level. monotonic cannot go backward.
• Float drift under sustained calls. Millions of try_admit calls accumulate float error in _tokens/_level; the min/max clamps bound it, but assert 0 <= level <= capacity in a debug build to catch a logic bug that lets state escape the range.
• GIL contention. Both limiters are cheap enough to run inline on the event loop, but if a single limiter instance is shared across threads it needs a lock, and that lock on the hot path can serialize admission. Prefer one limiter per worker shard over a shared locked instance.

Related #

• Backpressure & Flow-Control Strategies — parent overview of shedding, priority lanes, and where rate limiting fits.
• Sizing Bounded asyncio Queues for Geofence Pipelines — how the queue watermark and the bucket refill rate must agree.
• Event Routing & Backpressure — the routing tier these limiters protect.