Rate Limiting Algorithms: Token Bucket and Beyond

A deep dive into rate limiting algorithms with implementations, trade-offs, and guidance on choosing the right approach for your API.

Published on January 19, 2021Updated on September 9, 20264 min read

rate-limiting algorithms api-design backend distributed-systems

Rate limiting protects your system from abuse and overload, but the algorithm you choose determines how it feels to legitimate users. A poorly chosen limiter either lets burst traffic through when it should not, or throttles normal usage patterns unnecessarily.

Most developers reach for a simple counter — "100 requests per minute" — without considering how that counter resets, whether bursts are acceptable, and how it behaves across distributed servers. The choice of algorithm directly impacts user experience.

Fixed Window Counter

The simplest approach: divide time into fixed windows and count requests per window.

tstypescript

class FixedWindowLimiter {
  private windows = new Map<string, { count: number; expiry: number }>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = Math.floor(now / this.windowMs) * this.windowMs;
    const windowKey = `${key}:${windowStart}`;
 
    const window = this.windows.get(windowKey);
    if (!window || now > window.expiry) {
      this.windows.set(windowKey, {
        count: 1,
        expiry: windowStart + this.windowMs,
      });
      return true;
    }
 
    if (window.count >= this.maxRequests) return false;
    window.count++;
    return true;
  }
}

The problem: boundary bursts. A client can send 100 requests at 11:59:59 and 100 more at 12:00:00 — 200 requests in 2 seconds while technically staying under the "100 per minute" limit.

tstypescript

// ❌ Fixed window boundary problem
// Window 1 (11:59:00-11:59:59): 100 requests at 11:59:58 ✅
// Window 2 (12:00:00-12:00:59): 100 requests at 12:00:01 ✅
// Result: 200 requests in 3 seconds — limit is effectively doubled

Fixed window works for simple use cases where occasional bursts are acceptable. For stricter enforcement, use sliding window.

Sliding Window Log

Track the timestamp of every request and count how many fall within the sliding window. Accurate but memory-intensive.

tstypescript

class SlidingWindowLog {
  private logs = new Map<string, number[]>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = now - this.windowMs;
 
    let timestamps = this.logs.get(key) ?? [];
    // Remove expired entries
    timestamps = timestamps.filter((t) => t > windowStart);
 
    if (timestamps.length >= this.maxRequests) {
      this.logs.set(key, timestamps);
      return false;
    }
 
    timestamps.push(now);
    this.logs.set(key, timestamps);
    return true;
  }
}

This approach is perfectly accurate — no boundary bursts. But storing every timestamp is expensive. At 1000 requests per minute per user, you are storing 1000 timestamps per user in memory.

Sliding Window Counter

A hybrid that combines fixed window efficiency with sliding window accuracy. It interpolates between two adjacent fixed windows based on how far into the current window you are.

tstypescript

class SlidingWindowCounter {
  private windows = new Map<string, number>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const currentWindow = Math.floor(now / this.windowMs);
    const previousWindow = currentWindow - 1;
    const elapsed = (now % this.windowMs) / this.windowMs;
 
    const currentKey = `${key}:${currentWindow}`;
    const previousKey = `${key}:${previousWindow}`;
 
    const currentCount = this.windows.get(currentKey) ?? 0;
    const previousCount = this.windows.get(previousKey) ?? 0;
 
    // Weighted sum: full current + proportional previous
    const estimatedCount = currentCount + previousCount * (1 - elapsed);
 
    if (estimatedCount >= this.maxRequests) return false;
 
    this.windows.set(currentKey, currentCount + 1);
    return true;
  }
}

This is the sweet spot for most APIs. O(1) memory per user (two counters), no boundary burst problem, and close to exact counting.

Token Bucket

The token bucket allows controlled bursts while enforcing an average rate. Tokens are added at a steady rate. Each request consumes a token. No tokens, no request. The bucket can accumulate tokens up to a maximum, allowing short bursts.

tstypescript

class TokenBucket {
  private tokens: number;
  private lastRefill: number;
 
  constructor(
    private capacity: number,
    private refillRate: number, // tokens per second
  ) {
    this.tokens = capacity;
    this.lastRefill = Date.now();
  }
 
  isAllowed(cost: number = 1): boolean {
    this.refill();
 
    if (this.tokens >= cost) {
      this.tokens -= cost;
      return true;
    }
    return false;
  }
 
  private refill(): void {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillRate
    );
    this.lastRefill = now;
  }
}
 
// Example: 10 tokens max, refills at 2/sec
// Burst of 10 requests: allowed immediately
// Then: 2 requests per second sustained
const limiter = new TokenBucket(10, 2);

Token bucket is ideal when you want to allow bursts (page loads triggering multiple API calls) while capping sustained throughput. AWS and most cloud providers use this approach.

Distributed Rate Limiting with Redis

In-memory limiters fail when your application runs on multiple servers. Redis provides atomic operations for shared state.

tstypescript

import { Redis } from 'ioredis';
 
class RedisRateLimiter {
  constructor(
    private redis: Redis,
    private maxRequests: number,
    private windowSec: number
  ) {}
 
  async isAllowed(key: string): Promise<{ allowed: boolean; remaining: number }> {
    const redisKey = `ratelimit:${key}`;
 
    // Atomic increment + expire using a Lua script
    const result = await this.redis.eval(
      `
      local current = redis.call('INCR', KEYS[1])
      if current == 1 then
        redis.call('EXPIRE', KEYS[1], ARGV[1])
      end
      return current
      `,
      1,
      redisKey,
      this.windowSec
    ) as number;
 
    return {
      allowed: result <= this.maxRequests,
      remaining: Math.max(0, this.maxRequests - result),
    };
  }
}

The Lua script runs atomically in Redis — no race conditions between the INCR and EXPIRE calls. This is critical when multiple application servers share the same limiter.

Response Headers

Clients need to know their rate limit status. Return standard headers with every response.

tstypescript

// ❌ No rate limit headers — client has no idea why requests fail
app.use((req, res, next) => {
  if (!limiter.isAllowed(req.ip)) {
    return res.status(429).json({ error: 'Too many requests' });
  }
  next();
});
 
// ✅ Informative headers — client can adapt behavior
app.use(async (req, res, next) => {
  const result = await limiter.isAllowed(req.ip);
 
  res.set({
    'X-RateLimit-Limit': String(limiter.maxRequests),
    'X-RateLimit-Remaining': String(result.remaining),
    'X-RateLimit-Reset': String(result.resetAt),
    'Retry-After': result.allowed ? undefined : String(result.retryAfter),
  });
 
  if (!result.allowed) {
    return res.status(429).json({
      error: 'Rate limit exceeded',
      retryAfter: result.retryAfter,
    });
  }
  next();
});

The Retry-After header tells well-behaved clients exactly when to retry. Without it, clients either hammer the server with retries or back off too conservatively.

Choosing the Right Algorithm

Algorithm	Burst Handling	Memory	Accuracy	Best For
Fixed Window	Allows double	O(1)	Low	Simple cases, internal APIs
Sliding Window Log	Exact	O(n)	Perfect	Small request volumes
Sliding Window Counter	Good	O(1)	Very good	Most API rate limiting
Token Bucket	Explicit	O(1)	Good	Burst-tolerant public APIs

For most web APIs, the sliding window counter provides the best balance. For APIs where burst tolerance is a feature (file uploads, batch operations), use token buckets.

Key Takeaways

Fixed window has a boundary burst problem — traffic can double at window boundaries
Sliding window counter is the best default — O(1) memory with near-perfect accuracy
Token bucket is ideal for burst-tolerant APIs — explicitly controls burst size and sustained rate
Use Redis for distributed limiting — Lua scripts ensure atomicity across servers
Always return rate limit headers — X-RateLimit-Remaining and Retry-After enable well-behaved clients

Rate Limiting Algorithms: Token Bucket and Beyond

Fixed Window Counter

Sliding Window Log

Sliding Window Counter

Token Bucket

Distributed Rate Limiting with Redis

Response Headers

Choosing the Right Algorithm

Key Takeaways

Related Posts

API Rate Limiting: Algorithms and Implementation

Designing Idempotent APIs: Safely Retrying Failed Requests

Idempotency in API Design: Safe Retries at Scale