Token Bucket Algorithm

At an arcade, you buy a cup of tokens at the entrance. Each game costs one token. When your cup is empty, you cannot play until you buy more. But the arcade also gives you one free token every 10 minutes. If you sit idle for an hour, you accumulate 6 free tokens, enough for a small burst of games.

The token bucket algorithm works exactly like this. A "bucket" holds tokens. Each API request consumes one token. Tokens are added to the bucket at a fixed rate (the refill rate). If the bucket is empty, the request is rejected. The bucket has a maximum capacity, which determines the maximum burst size.

This is the most widely used rate limiting algorithm in production. AWS API Gateway, Nginx, Envoy, Kong, Cloudflare, GitHub, Stripe, and Twitter/X all use token bucket or a close variant. Its popularity comes from one killer feature: it naturally allows short bursts while enforcing a long-term average rate. Real users are bursty. They send a flurry of requests, go quiet, then burst again. Token bucket accommodates this without punishing legitimate behavior.

AWS API Gateway uses token bucket with a default burst of 5,000 requests and a steady-state rate of 10,000 requests per second. Stripe rate-limits to 100 requests per second per API key in live mode with a burst allowance of 25 requests.

Parameters:

• Bucket capacity (burst size): Maximum tokens the bucket can hold
• Refill rate: How many tokens are added per second
• Current tokens: How many tokens are currently in the bucket

For each request:

1. Calculate tokens to add since last request: elapsed_seconds * refill_rate
2. Add tokens to bucket (cap at bucket capacity)
3. If tokens >= 1: consume 1 token, allow request
4. If tokens < 1: reject request (429 Too Many Requests)

class TokenBucket {
  private tokens: number;
  private lastRefill: number;

  constructor(
    private capacity: number,    // max tokens (burst size)
    private refillRate: number   // tokens per second
  ) {
    this.tokens = capacity;      // start full
    this.lastRefill = Date.now();
  }

  tryConsume(): boolean {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;

    // Refill tokens based on elapsed time
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillRate
    );
    this.lastRefill = now;

    // Try to consume one token
    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;  // Request allowed
    }
    return false;    // Request rejected (429)
  }
}

// 10 requests/second sustained, burst up to 50
const limiter = new TokenBucket(50, 10);

Example timeline (capacity: 5, refill: 1/sec):

t=0: tokens=5,  3 requests -> tokens=2,  all allowed
t=1: tokens=3 (+1), 1 request -> tokens=2,  allowed
t=2: tokens=3 (+1), 5 requests -> only 3 allowed, 2 rejected
t=5: tokens=3 (+3 over 3 idle seconds, capped at 5)

Here is the same algorithm in Python. Press Run. Watch a burst of 8 requests drain the bucket, then see what happens after a short idle window.