Token Bucket vs Leaky Bucket

Both algorithms cap a stream to an average rate by pairing one counter with the clock, and they differ in a single design choice: a token bucket lets a caller save up permits and spend them all at once, so a burst passes instantly until the saved permits run out; a leaky bucket forces every admitted request through a queue that drains at a fixed rate, erasing the burst and emitting a perfectly steady trickle.

That one difference is the whole trade-off. Below we run the same input through both with real numbers, look at correct pseudocode (the version you would actually ship stores two numbers, not a background timer), and place both against the rate-limiters you will really be choosing between in an interview or a design doc: fixed-window and sliding-window counters.

The two mechanisms, precisely

Token bucket. A bucket holds up to B tokens (its capacity = the maximum burst). Tokens are added at a steady r tokens/second, capped at B. Each request must remove cost tokens (usually 1) to be admitted; if the bucket has enough, the request passes and tokens are debited, otherwise it is rejected (an HTTP 429) or made to wait. Idle time accumulates tokens up to B — that stored credit is what permits a burst. Sustained throughput can never exceed r because that is the only inflow.

Leaky bucket. Model a fixed-size FIFO queue of capacity B that is drained at a constant r requests/second (the "leak"). Arrivals join the queue; if the queue is full they are dropped (overflow). Because the drain rate is constant regardless of how ragged the input is, the output is smooth — the burst is buffered, not passed on. The cost is queueing latency: an admitted request may wait behind everything already in the bucket.

Worked trace: capacity 10, refill 2/s, a burst of 15

Bucket starts full (10 tokens). At t = 0s a burst of 15 requests arrives at once, then 4 arrive at t = 1s, 1 at t = 2s, then idle. Each request costs 1 token.

Read the first row carefully: 10 of the 15 pass in the same instant — that is the burst, funded by the 10 stored tokens — and the other 5 are rejected on the spot. After that the bucket is empty and admission tracks the refill: about 2 per second. Idle seconds (t=3,4) rebuild credit toward the cap of 10, ready for the next burst.

The same input through a leaky bucket

Now a queue of capacity 10, drained at 2/s, starting empty. Before each arrival we first subtract whatever leaked since the last event.

The admission counts land in the same place as the token bucket — 10 in, 5 dropped on the burst, then ~2/s — because both bound the average to r with the same headroom B. The difference is what the downstream sees. The token bucket released all 10 at t = 0s; the leaky bucket releases them one every 0.5s, so the 10th admitted request does not exit until t ≈ 5s. The burst is gone, traded for up to ~5 seconds of queue latency. That is the entire choice in one sentence: token bucket preserves burstiness, leaky bucket destroys it and charges latency for the privilege.

Pseudocode you would actually ship

Neither production implementation runs a timer that ticks tokens in or drains the queue. You store two numbers — a level and a last-updated timestamp — and reconstruct the current level lazily from elapsed time on each request. This is what makes it cheap enough for millions of keys in Redis.

class TokenBucket:            # allow bursts up to `capacity`
    def __init__(self, capacity, refill_rate):
        self.capacity   = capacity        # max burst (B)
        self.rate       = refill_rate     # tokens per second (r)
        self.tokens     = capacity        # start full
        self.last       = monotonic()     # NOT wall-clock

    def allow(self, cost=1):
        now = monotonic()
        # lazily credit tokens for elapsed time, capped at capacity
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True                   # admit
        return False                      # reject (429)

class LeakyBucket:            # delay-based queue-less leaky bucket (GCRA)
    def __init__(self, capacity, leak_rate):
        self.capacity      = capacity     # queue capacity in REQUESTS (B); max tolerated delay = B / rate seconds
        self.rate          = leak_rate    # leak rate per second (r)
        self.next_dispatch = monotonic()  # time when the next request is allowed to execute

    def allow(self):
        now = monotonic()
        # The earliest this request is scheduled to execute
        scheduled_time = max(now, self.next_dispatch)
        delay = scheduled_time - now
        
        # Convert capacity (requests) into the max tolerated delay (seconds), then drop
        # any request that would have to wait that long or longer
        max_delay = self.capacity / self.rate
        if delay >= max_delay:
            return False, 0               # drop/reject (429)
            
        # Update the next dispatch time to schedule the next permit
        self.next_dispatch = scheduled_time + (1.0 / self.rate)
        return True, delay                # caller must sleep(delay) before executing request

The >= matters. A request whose delay equals capacity / rate already has capacity requests' worth of drain scheduled ahead of it — the equivalent queue is full — so it must be rejected. With a plain > the limiter admits capacity + 1 requests on a cold burst: re-run the burst-of-15 trace against the code and you get 11 admitted instead of the 10 the table shows.

Why the naive version is wrong. The tempting implementation spawns a background thread per bucket that adds a token (or drains one) every 1/r seconds. It breaks three ways: (1) it does not scale — one goroutine/thread per API key means millions of timers; (2) timer granularity and drift make the real rate wrong under load; (3) it is stateful in RAM, so it cannot be shared across servers. The lazy refill/drain form above is stateless enough to live in a single Redis key and be updated atomically. Also note that if a leaky bucket returns True immediately without returning a delay or sleeping, it is just a meter, not a shaper — a burst will pass immediately downstream. The GCRA/virtual-scheduling approach above avoids background timers by computing the exact dispatch delay per request. Also note monotonic(), not wall-clock: an NTP step backwards makes (now - last) negative and corrupts the rate limits.

When to use which — and versus the alternatives

The real decision is rarely token-vs-leaky in isolation; it is "which of the four common rate-limiters fits this endpoint." The other two you must know are fixed-window and sliding-window counters.

• Token bucket — allows bursts up to B, then holds the average at r. O(1) memory (two numbers per key), maps cleanly onto a Redis key, and the burst size is a separate tunable knob. This is the default for public API rate limits (Stripe, GitHub, AWS all use token-bucket-style limiters). Choose it when clients legitimately spike (a page load fires 8 API calls; a batch job flushes) and you want to absorb that without punishing them, while still capping sustained load.
• Leaky bucket — guarantees a perfectly smooth output rate and never lets a burst reach the thing behind it. Choose it when the downstream is fragile or fixed-capacity: a legacy backend, a payment processor with its own hard limit, an outbound queue to a partner, or traffic egress you must keep constant. NGINX's limit_req is a leaky bucket for exactly this reason. The cost you accept is queueing latency and the operational reality that a full bucket makes every accepted request slow — sometimes a fast 429 is kinder than a 5-second wait.
• Fixed-window counter — one integer per key per calendar window (e.g. count:user:minute) with a TTL. Cheapest possible; trivially distributed with INCR. Its flaw: a client can fire the full limit at 0:59 and again at 1:00, sending 2× the limit in two seconds across the boundary. Prefer it over token bucket when you only need coarse quota accounting ("1000 calls/day") and boundary bursts are harmless.
• Sliding-window counter — blends the current and previous fixed windows by weight, killing the boundary-burst problem at O(1) memory and near-exact enforcement (Cloudflare's approach). The full sliding-window log (a timestamp per request) is exact but costs O(requests) memory per key — usually too expensive. Prefer sliding-window over token bucket when you need tight, near-exact rate accuracy and explicitly do not want to permit bursts.

Crisp rule: choose token bucket when bursts are legitimate and you want to allow them under an average cap; choose leaky bucket when a downstream needs a constant, burst-free feed and you can pay latency; choose fixed-window for the cheapest coarse quota; choose sliding-window counter when you need accurate, burst-suppressing limits without a full log.

Pitfalls

• Per-node buckets multiply your limit. Run a local token bucket on each of N app servers and your effective limit is N × r, not r. Behind a load balancer this silently lets 5× or 10× through. Fix: centralize state in Redis with an atomic Lua script (or the cell-based approach), or pin each key to one node.
• Read-modify-write races over-admit. Two concurrent requests both read "1 token left," both debit, and you admit two. The check-and-decrement must be atomic (Redis Lua, a single INCR-based scheme, or a lock). This bites hardest exactly when you are under attack and it matters most.
• Wall-clock time goes backwards. NTP adjustments and VM live-migration can move the clock; with wall-clock now(), (now - last) can be negative and either mint free tokens or corrupt the leak. Always use a monotonic clock for elapsed time.
• Setting the burst (capacity) too high defeats the point. B is literally the largest instantaneous flood you will allow through. A generous B to "be nice to clients" can hand a fragile backend a 10,000-request spike. Size B to what the downstream can survive, independently of r.
• Leaky bucket under sustained overload is all latency. When arrival rate stays above r, the queue sits full, so every admitted request waits the maximum. If callers have their own timeouts, they are timing out and you are still doing the work. Consider load-shedding (reject early) instead of an ever-full buffer.
• Flat 1-token-per-request is wrong for uneven costs. A bulk/search endpoint that costs 50× a health check should debit 50 tokens (variable cost), or one cheap client of an expensive route drains your protection.

Takeaways

• One knob separates them: the token bucket saves permits so bursts pass immediately; the leaky bucket queues and releases at a constant rate, erasing bursts at the cost of latency.
• Both cap the average at r with headroom B; with the same numbers they admit the same count — they differ in output shape and latency, not in how much they let through.
• Ship the lazy "level + monotonic timestamp" form, not a background timer, and make the update atomic and centralized or you will over-admit across nodes.
• In practice you are choosing among four: token bucket (bursty APIs), leaky bucket (smooth feed to a fragile downstream), fixed-window (cheap coarse quota, tolerates boundary bursts), sliding-window counter (accurate, burst-suppressing, cheap).

Sources: Tanenbaum & Wetherall, Computer Networks (leaky- and token-bucket traffic shaping); the ATM Forum's GCRA / virtual-scheduling formulation of the leaky bucket; Stripe Engineering, "Scaling your API with rate limiters"; Cloudflare's sliding-window rate-limiter analysis; and the NGINX limit_req (leaky-bucket) documentation. Re-authored and deepened for this guide with an explicit numeric trace, shippable lazy-refill pseudocode, and a comparison against fixed-window and sliding-window limiters.