Implementing API Rate Limiting with the Token Bucket Algorithm

The Necessity of API Rate Limiting

Rate limiting is a fundamental component in robust distributed systems, serving to protect APIs from abusive behavior, prevent system overload, and ensure service availability. Without effective rate limiting, a sudden surge in traffic—whether malicious or accidental—can lead to resource exhaustion, increased latency, and outright service failures, impacting all users. It's about maintaining stability and fairness in resource consumption.

Flaws of Fixed-Window Rate Limiters

A common but flawed approach to rate limiting is the fixed-window counter. This method tracks requests within a predefined time window (e.g., 60 seconds) and resets the count at the window's end. While simple, it suffers from a significant drawback known as the "burst problem" or "edge case anomaly."

The Token Bucket Algorithm: A Robust Solution

The Token Bucket algorithm addresses the shortcomings of fixed-window counters by modeling rate limits as a continuously refilling resource pool. Instead of strict time windows, it uses a "bucket" that holds a maximum number of "tokens." Each request consumes one token. If no tokens are available, the request is either rejected or delayed.

• Bucket Size (Capacity): This defines the maximum burst of requests allowed. It's the upper limit of tokens that can accumulate in the bucket.
• Refill Rate: This is the rate at which tokens are added to the bucket (e.g., tokens per second), representing the sustainable long-term request rate.
• Request Consumption: Each incoming request attempts to consume one token. If successful, the request is processed; otherwise, it's denied or queued.
• Burst Smoothing: When traffic is idle, tokens accumulate up to the capacity. During a sudden spike, the accumulated tokens allow a burst of requests to pass through without exceeding the long-term rate, effectively smoothing the load.

import time
import threading

class TokenBucket:
    def __init__(self, rate, capacity):
        """
        rate – tokens added per second (float)
        capacity – max tokens in the bucket (int)
        """
        self.rate = rate
        self.capacity = float(capacity)
        self.tokens = float(capacity) # start full
        self.timestamp = time.monotonic()
        self.lock = threading.Lock()

    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.timestamp
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.timestamp = now

    def allow(self, cost=1):
        with self.lock:
            self._refill()
            if self.tokens >= cost:
                self.tokens -= cost
                return True
            return False