Rate Limiting Strategies — Token Bucket, Leaky Bucket, Sliding Window

In this tutorial, you'll learn about Rate Limiting Strategies. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Rate Limiting controls the number of requests a client can make to an API within a given time window, preventing abuse, ensuring fair resource allocation, and protecting backend services from traffic spikes.

What You'll Learn

By the end of this tutorial, you will implement four Rate Limiting algorithms (token bucket, leaky bucket, Sliding Window log, Sliding Window counter), deploy distributed Rate Limiting with Redis, and choose the right strategy for your API Gateway.

Why It Matters

Without Rate Limiting, a single misbehaving client can saturate backend resources, causing latency spikes and outages for all other users. Doda Browser applies Rate Limiting on its public API to ensure fair usage across thousands of clients, and Durga Antivirus Pro uses Rate Limiting on its threat intelligence endpoints to prevent automated scraping.

Real-World Use

A payment gateway API enforces 10 requests per second per merchant. When exceeded, the gateway returns HTTP 429 (Too Many Requests) with a Retry-After header. The merchant's SDK respects this header and backs off automatically.

Token Bucket Algorithm

The token bucket allows bursts up to a configured capacity while enforcing a long-term average rate. Tokens are added at a fixed rate, and each request consumes one token.

# token_bucket.py
# Token bucket rate limiter implementation
import time
from threading import Lock

class TokenBucket:
    """Token bucket rate limiter with thread safety."""
    def __init__(self, capacity, refill_rate, refill_interval=1.0):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.refill_interval = refill_interval
        self.tokens = capacity
        self.last_refill = time.time()
        self.lock = Lock()

    def _refill(self):
        """Add tokens based on elapsed time."""
        now = time.time()
        elapsed = now - self.last_refill
        new_tokens = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_refill = now

    def allow_request(self, tokens=1):
        """Check if request is allowed. Returns True/False."""
        with self.lock:
            self._refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

bucket = TokenBucket(capacity=10, refill_rate=2)

for i in range(15):
    allowed = bucket.allow_request()
    print(f"Request {i+1}: {'ALLOWED' if allowed else 'DENIED'}")
    time.sleep(0.1)

Expected output:

Request 1: ALLOWED
...
Request 10: ALLOWED
Request 11: DENIED
Request 12: DENIED
... (tokens refill at 2/sec so requests 13-15 may be allowed after ~0.5s)

The first 10 requests consume the initial capacity. Subsequent requests are denied until tokens refill. The burst capacity of 10 allows short spikes while the refill rate of 2/sec enforces the long-term average.

Leaky Bucket Algorithm

The leaky bucket queues requests and processes them at a fixed rate, smoothing out traffic spikes. Excess requests are rejected when the Queue is full.

# leaky_bucket.py
# Leaky bucket rate limiter implementation

import time
from collections import deque

class LeakyBucket:
    """Leaky bucket rate limiter with processing queue."""
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity
        self.leak_rate = leak_rate
        self.queue = deque()
        self.last_leak = time.time()

    def _leak(self):
        """Process (remove) requests at the configured rate."""
        now = time.time()
        elapsed = now - self.last_leak
        to_leak = int(elapsed * self.leak_rate)
        for _ in range(min(to_leak, len(self.queue))):
            self.queue.popleft()
        self.last_leak = now

    def allow_request(self, request_id=""):
        """Add request to queue if capacity available."""
        self._leak()
        if len(self.queue) < self.capacity:
            self.queue.append(request_id)
            return True
        return False

bucket = LeakyBucket(capacity=5, leak_rate=2)

for i in range(10):
    allowed = bucket.allow_request(f"req_{i}")
    print(f"Request {i+1}: {'QUEUED' if allowed else 'REJECTED'}")
    time.sleep(0.2)

Expected output:

Request 1: QUEUED
Request 2: QUEUED
Request 3: QUEUED
Request 4: QUEUED
Request 5: QUEUED
Request 6: REJECTED
... (queue leaks 2 req/sec, so some later requests may be queued)

The leaky bucket queues requests up to capacity 5 and processes them at 2 per second. Burst traffic is smoothed into a steady processing rate. Unlike the token bucket, the leaky bucket guarantees a fixed processing rate.

Sliding Window Log

The Sliding Window log stores timestamps of recent requests and checks how many fall within the current window.

# sliding_window_log.py
# Sliding window log rate limiter

import time
from collections import deque

class SlidingWindowLog:
    """Sliding window log rate limiter using timestamp deque."""
    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.requests = deque()

    def allow_request(self):
        """Check if request is allowed. Returns True/False."""
        now = time.time()
        cutoff = now - self.window_seconds

        while self.requests and self.requests[0] < cutoff:
            self.requests.popleft()

        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False

limiter = SlidingWindowLog(max_requests=5, window_seconds=10)

for i in range(8):
    allowed = limiter.allow_request()
    print(f"Request {i+1}: {'ALLOWED' if allowed else 'DENIED'}")
    time.sleep(0.5)

Expected output:

Request 1: ALLOWED
Request 2: ALLOWED
Request 3: ALLOWED
Request 4: ALLOWED
Request 5: ALLOWED
Request 6: DENIED
Request 7: DENIED
Request 8: DENIED

The Sliding Window log provides precise Rate Limiting by checking actual timestamps. It allows 5 requests per 10-second window. After 10 seconds, old entries expire and new requests are allowed. This approach is memory-intensive for high-traffic systems since it stores every timestamp.

Distributed Rate Limiting with Redis

For Distributed Systems spanning multiple servers, rate limiter State must be shared. Redis with atomic operations provides consistent Rate Limiting across all instances.

# redis_rate_limiter.py
# Distributed rate limiter using Redis

import redis
import time

class RedisSlidingWindowCounter:
    """Distributed rate limiter using Redis sorted sets."""
    def __init__(self, redis_client, max_requests, window_seconds):
        self.redis = redis_client
        self.max_requests = max_requests
        self.window_seconds = window_seconds

    def allow_request(self, client_id):
        """Check and record request atomically in Redis."""
        now = time.time()
        key = f"ratelimit:{client_id}"
        cutoff = now - self.window_seconds

        pipe = self.redis.pipeline()
        pipe.zremrangebyscore(key, 0, cutoff)
        pipe.zadd(key, {now: now})
        pipe.zcard(key)
        pipe.expire(key, self.window_seconds)
        _, _, count, _ = pipe.execute()

        return count <= self.max_requests

r = redis.Redis(host='localhost', port=6379, db=0)
limiter = RedisSlidingWindowCounter(r, max_requests=3, window_seconds=5)

for i in range(6):
    allowed = limiter.allow_request("user:42")
    print(f"Request {i+1}: {'ALLOWED' if allowed else 'DENIED'}")
    time.sleep(0.3)

Expected output:

Request 1: ALLOWED
Request 2: ALLOWED
Request 3: ALLOWED
Request 4: DENIED
Request 5: DENIED
Request 6: DENIED

The Redis-based limiter uses a sorted set per client. Old entries are removed with ZREMRANGEBYSCORE, the new timestamp is added with ZADD, and the count is checked with ZCARD. This works across all application instances because Redis is shared.

Common Errors

1. Rate Limiting at the Wrong Layer

Rate Limiting only at the application level misses traffic that never reaches your app. Always enforce rate limits at the API Gateway or load balancer level first, then add application-level limits as a second layer.

2. Not Returning Proper Headers

Clients need to know when they can retry. Always return Retry-After header with the rate limit, plus X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers following the IETF standard.

3. Using IP Address as the Only Identifier

NAT gateways and VPNs cause many legitimate users to share the same IP. Rate Limiting by IP alone blocks entire offices and universities. Use API keys, user IDs, or Composite keys (user + IP) for more precise limiting.

4. Ignoring Clock Drift in Distributed Systems

Servers with unsynchronized clocks produce inconsistent rate limits. Use NTP to keep clocks in sync. For critical systems, rely on Redis or a centralized rate limiter rather than local server time.

5. Allowing Unlimited Internal Service Calls

Internal services bypassing the API Gateway are not rate limited by gateway-level policies. Apply rate limits at the service mesh layer or enforce limits within internal API clients to prevent cascading failures.

6. Not Testing Rate Limit Behavior Under Load

Rate limiters that work perfectly at low volume fail under high concurrency due to race conditions. Always test with concurrent clients, verify atomicity of counter increments, and use Lua scripts or Redis transactions for distributed limits.

Practice Questions

1. What is the difference between token bucket and leaky bucket?

Token bucket allows bursts up to capacity and enforces an average rate by consuming tokens. Leaky bucket queues requests and processes them at a fixed rate. Token bucket permits short bursts; leaky bucket smooths all traffic to a constant rate.

2. Why is the Sliding Window log more accurate than a fixed window counter?

The Sliding Window log checks exact timestamps within a rolling window, preventing edge-case bursts at window boundaries. A fixed window counter resets at boundary intervals, allowing double the limit at the reset point.

3. How does Redis enable distributed Rate Limiting?

Redis provides atomic operations (sorted sets, counters, Lua scripts) that maintain consistent State across all application instances. All servers read and write to the same Redis instance, ensuring a unified rate limit regardless of which server handles the request.

4. What headers should a rate-limited API return?

The Retry-After header indicates seconds until the client can retry. Standard headers include X-RateLimit-Limit (max requests), X-RateLimit-Remaining (remaining in window), and X-RateLimit-Reset (when the window resets as Unix timestamp).

Challenge

Implement a multi-tier Rate Limiting system for a SaaS API: anonymous users get 10 requests per minute globally, authenticated users get 100 requests per minute per user, and premium users get 1000 requests per minute per user with a burst capacity of 200. Use Redis sorted sets for the Sliding Window and Lua scripting for atomic execution. Handle the case where a user upgrades their plan mid-window.

Mini Project: Express Rate Limiter Middleware

// rate-limiter.js
// Express middleware for Rate Limiting with Redis

const Redis = require('Redis');
const { RateLimiterRedis } = require('rate-limiter-flexible');

const redisClient = Redis.createClient({
  URL: 'Redis://localhost:6379',
  enable_offline_Queue: false,
});

redisClient.on('error', (err) => console.error('Redis error:', err));

const rateLimiter = new RateLimiterRedis({
  storeClient: redisClient,
  keyPrefix: 'middleware',
  points: 10,
  duration: 1,
  blockDuration: 2,
});

async function rateLimitMiddleware(req, res, next) {
  try {
    const key = req.user?.id || req.ip;
    await rateLimiter.consume(key);
    res.set('X-RateLimit-Remaining', rateLimiter.points);
    next();
  } catch (error) {
    if (error instanceof Error) {
      next(error);
    } else {
      const secs = Math.round(error.msBeforeNext / 1000) || 1;
      res.set('Retry-After', String(secs));
      res.status(429).JSON({
        error: 'Too Many Requests',
        retryAfter: secs,
      });
    }
  }
}

module.exports = rateLimitMiddleware;

// Usage in Express app:
// const rateLimitMiddleware = require('./rate-limiter');
// app.use('/API', rateLimitMiddleware);

Expected behavior: The middleware checks Redis for each request. If the client exceeds 10 requests per second, the middleware returns HTTP 429 with a Retry-After header. The rate-limiter-flexible library handles the Sliding Window logic and Redis atomicity internally.

Congratulations on completing this Rate Limiting tutorial! Next, explore API Gateway patterns for gateway-level rate enforcement, then learn about caching strategies for complementary performance optimization.

• Practice daily — Implement a token bucket rate limiter in your preferred language and test with concurrent clients
• Build a project — Build an API Rate Limiting dashboard that visualizes request patterns, blocked requests, and rate limit violations
• Explore related topics — Check out the IETF standard for Rate Limiting headers and advanced Redis Rate Limiting with Lua

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.