Token bucket rate limiter

Q: Token bucket or leaky bucket?

A token bucket allows bursts up to capacity and then enforces the average rate. A leaky bucket, in its queue form, releases requests at a fixed pace and smooths bursts out instead of allowing them. Most API limits are token buckets because clients naturally send bursts. For outgoing traffic you want to pace, such as calls to a fragile downstream, a leaky bucket is the better fit.

Q: How would this look in Go, and in production?

Go's extended library ships this as golang.org/x/time/rate (rate.NewLimiter(r, burst), with Allow, Wait(ctx) and Reserve), and it uses the same lazy-refill idea. Your own version would be a struct with a sync.Mutex, tokens float64 and last time.Time, taking a clock interface for tests. Across many servers an in-process bucket only limits each instance, so shared limits keep the two numbers in Redis and update them atomically in a Lua script.

easyRate limiting and resilience Must-do

Implement a token bucket, the rate limiter used by API gateways, cloud SDK clients and traffic shapers. The bucket holds up to capacity tokens and refills continuously at refill_rate tokens per second. Each request spends tokens. If there are not enough, the request is rejected. The result: short bursts up to capacity are allowed, and the long-run rate is capped at refill_rate.

API (Java: same names in camelCase, DoubleSupplier clock, allow() / allow(cost) overloads)

◈ DIAGRAM

TokenBucket(capacity: float, refill_rate: float, clock=time.monotonic)
allow(cost=1) -> bool        # spend `cost` tokens if available
wait_time(cost=1) -> float   # seconds until allow(cost) would succeed; 0.0 if it would now
tokens() -> float            # tokens available right now

Rules

The bucket starts full.
Refill is continuous: after s seconds, s * refill_rate tokens have been added, never above capacity. Fractional tokens are allowed.
A rejected request spends nothing.
cost <= 0 or cost > capacity raises ValueError (Java IllegalArgumentException). A request bigger than the bucket could never succeed, so rejecting it forever would hide a bug.
Do not use a background thread or timer. Everything is computed when a method is called.
If the clock ever goes backwards, treat the elapsed time as zero.

Outputs are the return values of each call, in order, with the fake clock set to t.

Examples

Example 1

Input: t=0 b = TokenBucket(capacity=3, refill_rate=1) t=0 b.allow() x4 t=1.5 b.allow() t=1.5 b.wait_time() t=1.5 b.tokens() t=3 b.allow(2) t=3 b.allow()

Output: true true true false true 0.5 0.5 true false

Explanation: Three tokens allow a burst of three. After 1.5 s there are 1.5 tokens: one request spends 1, leaving 0.5, so another needs 0.5 s more. At t=3 the bucket has 2.0 tokens, exactly enough for a cost of 2.

Example 2

Input: t=0 b = TokenBucket(capacity=3, refill_rate=1) t=0 b.allow(3) t=100 b.tokens() t=100 b.allow(4)

Output: true 3.0 error: cost exceeds capacity

Explanation: Idle time refills the bucket only up to capacity, not to 100 tokens.

Hints

Approach

Optimal

Store two numbers: tokens and last, the clock reading when tokens was last brought up to date. This is lazy refill.

_refill: compute elapsed = now - last (clamped at 0), set tokens = min(capacity, tokens + elapsed * rate), and move last to now.
allow(cost): refill, then if tokens >= cost subtract and return True. Otherwise return False and leave tokens unchanged.
wait_time(cost): refill, then the shortfall cost - tokens divided by rate is how long until enough tokens exist. This is the number a server puts in a Retry-After header on a 429 response.

State is two floats per bucket, no matter how many requests go through it, so you can afford one bucket per client.

ComplexityTime O(1) per callSpace O(1) per bucket

Python

import time
 
 
class TokenBucket:
    def __init__(self, capacity, refill_rate, clock=time.monotonic):
        if capacity <= 0 or refill_rate <= 0:
            raise ValueError("capacity and refill_rate must be positive")
        self.capacity = float(capacity)
        self.rate = float(refill_rate)       # tokens per second
        self.clock = clock
        self._tokens = self.capacity         # start full
        self._last = clock()
 
    def _refill(self):
        now = self.clock()
        elapsed = max(0.0, now - self._last)          # never refill backwards
        self._tokens = min(self.capacity, self._tokens + elapsed * self.rate)
        self._last = now
 
    def _check(self, cost):
        if cost <= 0:
            raise ValueError("cost must be positive")
        if cost > self.capacity:
            raise ValueError("cost exceeds capacity")
 
    def allow(self, cost=1):
        self._check(cost)
        self._refill()
        if self._tokens >= cost:
            self._tokens -= cost
            return True
        return False
 
    def wait_time(self, cost=1):
        """Seconds until allow(cost) would succeed (0.0 if it would succeed now)."""
        self._check(cost)
        self._refill()
        return max(0.0, (cost - self._tokens) / self.rate)
 
    def tokens(self):
        self._refill()
        return self._tokens

Follow-up questions

Limit per client: keep a map of buckets. How do you stop idle clients from filling memory?
Make allow thread-safe. Which lines have to be inside the lock?
Add a blocking acquire(cost) that sleeps for wait_time and retries.

Frequently asked questions

A token bucket allows bursts up to capacity and then enforces the average rate. A leaky bucket, in its queue form, releases requests at a fixed pace and smooths bursts out instead of allowing them. Most API limits are token buckets because clients naturally send bursts. For outgoing traffic you want to pace, such as calls to a fragile downstream, a leaky bucket is the better fit.

Go's extended library ships this as golang.org/x/time/rate (rate.NewLimiter(r, burst), with Allow, Wait(ctx) and Reserve), and it uses the same lazy-refill idea. Your own version would be a struct with a sync.Mutex, tokens float64 and last time.Time, taking a clock interface for tests. Across many servers an in-process bucket only limits each instance, so shared limits keep the two numbers in Redis and update them atomically in a Lua script.

Rate limits show up in every layer infra engineers own: ingress, API gateways, cloud API quotas, and client SDKs that must stay under them. The question checks whether you can turn a rule ("10 per second, bursts of 20") into correct O(1) code without timers or threads.

Problem statement