Token Bucket Algorithm

The algorithm uses a conceptual bucket that holds tokens. Tokens are added at a fixed fill rate (e.g., 10 tokens per second) up to a maximum bucket capacity (e.g., 50 tokens). To transmit a packet or process a request, a number of tokens equal to the packet size or request cost must be removed from the bucket. If insufficient tokens are available, the request is either queued or dropped, enforcing the rate limit.

Unlike a simple leaky bucket, the token bucket explicitly decouples the sustained rate from the burst size.

• Sustained Rate: Defined by the token fill rate. Over a long period, the average traffic cannot exceed this rate.
• Burst Size: Defined by the bucket capacity. A sender can transmit a burst of traffic up to the bucket's full capacity instantaneously, as long as tokens have been accumulated during idle periods. This makes it ideal for TCP traffic, which is inherently bursty.

In API gateways and Web Application Firewalls (WAFs), the token bucket is used to enforce per-client rate limits.

• Keying: A bucket is assigned per IP address, API key, or session token.
• Cost: A single HTTP request typically costs 1 token, but expensive endpoints (e.g., search queries) can cost more.
• Penalty: When a scraper exceeds the burst limit, the gateway returns a 429 Too Many Requests status code, often paired with a Retry-After header. This prevents automated scripts from exhausting server resources while allowing legitimate user bursts.

The algorithm requires maintaining minimal state per client: current token count and last refill timestamp. The logic is executed on every request:

1. Refill: Calculate elapsed time since the last check. Add elapsed_time * fill_rate tokens, capping at the maximum bucket size.
2. Consume: Check if current_tokens >= request_cost. If yes, subtract the cost and allow the request. If no, deny the request. This calculation is O(1) and memory-efficient, making it suitable for high-throughput edge functions and reverse proxies.

The token bucket is often contrasted with the leaky bucket algorithm:

• Leaky Bucket: Processes requests at a constant, fixed rate, smoothing out bursts completely by queuing them. It enforces a rigid output rate regardless of the input burst pattern.
• Token Bucket: Allows instantaneous bursts up to the bucket size while enforcing a long-term average rate. It does not smooth traffic but limits the total volume over time. For scraping mitigation, the token bucket is preferred because it does not introduce artificial latency for legitimate users during short, high-activity periods.

In a distributed system with multiple API gateway instances, a centralized state store is required to maintain a global token bucket. Redis is commonly used for this purpose. A naive implementation can suffer from race conditions. The Generic Cell Rate Algorithm (GCRA), often implemented via sorted sets or atomic Lua scripts in Redis, provides a formalized, race-condition-free method for calculating token availability in a distributed environment without requiring constant bucket state synchronization.