Token Buckets: Bounding Rate Limits at the Edge

On a summer Friday at Stripe, an API caller discovered they could send 200 requests per minute when the limit was 100—and Stripe’s monitors saw nothing unusual. The limit was 100 per minute; the caller respected it: two bursts of exactly 100, spaced 2 seconds apart. Yet both arrived in the same minute. The log said “compliant.” The load was twice what was promised. This is the boundary burst bug, and it haunted every fixed-window rate limiter until token buckets arrived.

Fixed-window counters leak at the 59/60-second boundary. Token buckets plug this hole.

The Naive Approach: Fixed-Window Counters

A fixed-window counter is simple: divide time into 60-second slots. For each client, reset the counter at the start of each slot and reject any request that would exceed the limit. It runs in O(1) time and O(1) space—no memory bloat, no background threads.

But simplicity breaks at the window boundary. If a client sends a burst of requests just before the window resets (at 0:59), the counter accepts all 100. The window ticks over at 1:00. A fresh counter starts. At 1:01, another 100 requests arrive; the counter accepts them all because the new window is empty. In the two seconds between 0:59 and 1:01, 200 requests crossed your gateway. Your monitor shows two separate windows, each at 100%. Your SLA said 100/min. You broke it invisibly.

Sliding-window counters fix the boundary leak but at a cost: store every request timestamp in a log. To compute the current rate, count requests in a rolling 60-second window. This is O(N) space per client and O(N) time per request. At high scale, one client can eat megabytes of memory.

The Breakthrough: Token Bucket

A token bucket works like a water bucket with a slow drip and a tap. Tokens refill at a constant rate (e.g., 100 tokens per minute, or ~1.67 tokens per second) up to a capacity (e.g., 100 tokens). Each incoming request costs one token; if the bucket has tokens, the request drains one and proceeds. If the bucket is empty, the request is rejected instantly.

The magic: capacity absorbs bursts; refill rate ensures sustained throughput. A client who waits 60 seconds will have 100 tokens (the capacity) available. If they spend them all in one second, the next 59 requests are rejected until the bucket refills. But if they make 100 requests spread evenly across the minute, all pass—they arrive at the steady refill rate.

Contrast with the fixed-window leak: with token bucket, those same two bursts of 100 at 0:59 and 1:01 burn the bucket dry. By 1:01, only a few tokens have refilled. The second burst is rejected. Rate is strictly bounded.

Lazy refill computes tokens on arrival. Token bucket absorbs bursts but bounds sustained rate.

How It Works: Lazy Refill

The clever trick is lazy refill: do not refill tokens on a background timer. Instead, when a request arrives, compute how many tokens are available right now based on how much time has passed since the last refill.

function allowRequest(clientId, cost = 1) {
  const bucket = getBucket(clientId); // from Redis/cache
  const now = Date.now();
  const elapsedMs = now - bucket.lastRefillMs;
  
  // Refill lazily
  const tokensGenerated = (elapsedMs / 1000) * bucket.refillRate;
  bucket.tokensAvailable = Math.min(
    bucket.capacity,
    bucket.tokensAvailable + tokensGenerated
  );
  bucket.lastRefillMs = now;
  
  // Drain or reject
  if (bucket.tokensAvailable >= cost) {
    bucket.tokensAvailable -= cost;
    saveBucket(clientId, bucket);
    return { allowed: true };
  } else {
    const retryAfter = (cost - bucket.tokensAvailable) / bucket.refillRate;
    return { allowed: false, retryAfterSec: Math.ceil(retryAfter) };
  }
}

This is O(1): one lookup, one arithmetic operation, one save. No timestamp log, no background scheduler, no thread contention.

Distributed Token Buckets

In a multi-gateway deployment, each gateway stores its own copy of each client’s token bucket (or queries a shared Redis). This introduces drift: if gateway A refills 100 tokens and gateway B refills 100 tokens separately, the effective rate can overshoot. The standard fix is to keep the refill rate low enough that drift is acceptable (e.g., refill every 10 seconds, not every request), or to use a Redis script that refills atomically.

When a request exceeds the limit, return 429 Too Many Requests with the Retry-After header set to the number of seconds until the bucket refills enough:

HTTP/1.1 429 Too Many Requests
Retry-After: 47
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0

Clients see this header and back off automatically. The standard is clear and widely respected.

Beyond Redis: Multi-Gateway Coordination

In single-gateway setups, a token bucket is local state in memory. But production APIs run behind multiple gateways, load-balanced across availability zones. If gateway A and B each maintain a token bucket for the same client, the effective rate is the sum of both—twice what you specified.

The standard fix is to centralize state in Redis:

1. Store per-client token state in Redis: token_bucket:{client_id} → {"tokens": N, "refilled_at": T}
2. On each request, fetch, refill lazily, deduct, and save atomically
3. Use a Lua script to ensure atomic read-modify-write: if tokens >= cost then tokens -= cost; return 1 else return 0

Redis serves thousands of rate-limit queries per millisecond. Latency is microseconds. The only catch: Redis is a single point of truth, so it must be highly available. Deploy it with Sentinel (automatic failover) or Redis Cluster.

Alternatively, keep local buckets but sync at lower frequency: every 30 seconds, each gateway reports its “total burst used” to a central counter. This trades some precision for lower Redis load. The leak is bounded: if you allow 50-client concurrency and they all burst simultaneously, you overshoot by up to 50 times the burst capacity per window. Acceptable for many scenarios.

Comparison: Why Token Bucket Won

Let me put four algorithms side by side:

Fixed Window (Simple but Broken): Reset counter at the start of each minute. Fast and tiny. But the boundary leak is unfixable—it is intrinsic to the design.

Sliding Window (Correct but Expensive): Store every request timestamp. Count requests in a rolling 60-second window on each arrival. Fixes the leak but eats O(N) memory per client. A busy client can store millions of timestamps.

Leaky Bucket (Smooth but Latent): Queue excess requests, drain at a fixed rate. Perfect for smoothing but introduces latency (requests wait in queue). Also stores a queue in memory. Better for background jobs than live APIs.

Token Bucket (Practical Sweet Spot): Refill at rate up to capacity. O(1) space, O(1) time. Absorbs small bursts naturally. Strict rate bound. No queue, no latency. This is why it is in every production system.

The Interview Problem

“Design a rate limiter” is asked at every systems interview. Token bucket is the answer: explain the fixed-window leak, show how bucket absorbs bursts, mention O(1) complexity, describe the lazy refill code, and note the Redis/distributed angle.

Curveballs will come. What if the refill rate itself is very high (millions of tokens per second)? Rounding errors accumulate in floating-point arithmetic. Use integer math where possible. What if capacity is tiny relative to refill rate? Every request triggers a refill, approaching sliding-window behavior and losing the efficiency gain. This is actually fine for very tight limits.

Token bucket is not theoretically perfect. But it is battle-tested: Stripe, AWS API Gateway, GitHub, Kubernetes, and Google Cloud all use it. It is the measure of a good rate-limiting API.

Trade-offs and When NOT to Use It

Token bucket is not universally optimal, though it is the default choice for most APIs.

Use token bucket when: your API is public and must reject excess traffic instantly, you have natural traffic bursts (spike in legitimate traffic over a few seconds), you want O(1) memory per client, and Redis is already in your stack.

Use leaky bucket when: you can queue excess requests, the clients can wait, and you want perfectly smooth output (e.g., image resizing, batch processing). Latency is acceptable or even desirable.

Use sliding window when: you must detect and reject every request that violates the window, edge cases are unacceptable (e.g., payment processing, security logs), and memory per client is not a constraint. The O(N) space is worth the correctness.

Use fixed window when: your API is internal, callers are trusted and well-behaved, the boundary leak is negligible because load is spread across the day, and simplicity matters more than perfect fairness.

But for public APIs where you must bound the rate, reject excess instantly, and allow small bursts, token bucket is the proven choice. It is the algorithm that turned a boundary-burst bug into a predictable feature. Thousands of engineers have debugged token buckets. Thousands of guides exist. It is boring in the best way possible—battle-tested, standardized, and taught at every company with a public API.