Sweaty Imposter

Token Bucket

TechniqueThroughput and FlowMidSeniorUpdated
Bucket refills at rate R; each request takes one token. Allows controlled bursts up to bucket size.

When to Use Token Bucket

Rate limiting where occasional bursts are fine. Most general-purpose throttle: e.g., 100 req/min average, allow 30 in a burst.

In Practice

AWS API Gateway, Stripe, Cloudflare all use token bucket variants. Linux's tc traffic shaper uses it for QoS.

Sketch

Python

class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.refill = refill_per_sec
        self.last = time.time()

    def allow(self):
        now = time.time()
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.refill)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

How Token Bucket Comes Up in Interviews

Scenario

Your public API allows 100 req/min per key on average but you want to let well-behaved clients burst up to 30 requests at once after a quiet period. Which rate-limiting algorithm fits naturally?

Token bucket refills at the average rate but lets requests consume accumulated tokens, allowing controlled bursts up to the bucket size. Leaky bucket smooths bursts out entirely.

Token bucket refills at the average rate R and lets requests consume from an accumulated pool up to the bucket's capacity, naturally allowing controlled bursts after quiet periods. AWS API Gateway, Stripe's API, Cloudflare's rate limiter, and Linux's tc traffic shaper all use token-bucket variants. The two knobs (refill rate, bucket size) tune average throughput and burst size independently. The contrast with leaky bucket: token bucket says 'you've got credits saved up, spend them in a burst,' while leaky bucket says 'I'll drain you at a fixed rate, queue or drop the rest.' For human-facing APIs where bursts are normal behavior (page loads firing 30 parallel requests), token bucket is the right shape.

Where It Comes Up