What is Token Bucket

• Capacity: max tokens in bucket (burst size)
• Refill rate: r tokens/sec (long-term average)
• Per-key: one bucket per user/IP/API key
• Storage: Redis atomic ops (INCR/DECR + EXPIRE)
• Typical: 60 req/min = 1 token/sec refill + capacity 10 (burst)

# Redis Lua pseudocode
local tokens = redis.call("GET", key) or capacity
tokens = min(capacity, tokens + (now - last_refill) * rate)
if tokens >= 1 then
  redis.call("SET", key, tokens - 1)
  return allow
else
  return deny
end

• Rate Limiting
• Idempotency

The Token Bucket algorithm is a popular method for controlling the rate of traffic sent to a network. It allows for bursty traffic while still enforcing an average rate limit. The algorithm operates using two main parameters: the rate at which tokens are added to the bucket (r tokens/sec) and the maximum capacity of the bucket (B tokens). When a request is made, it consumes one token from the bucket. If the bucket has tokens available, the request is processed; if not, the request is rejected.

This mechanism ensures that applications can handle sudden bursts of traffic without overwhelming the system, as long as the average rate does not exceed the specified limit. The algorithm is particularly useful in scenarios where user behavior is unpredictable, such as web services and APIs.

Additionally, the Token Bucket algorithm is less restrictive compared to the Leaky Bucket algorithm, which enforces a constant outflow rate, making it more suitable for applications that experience variable traffic patterns.

• Key Advantages:
• Allows for bursts of traffic.
• Simple to implement and understand.
• Flexible in managing varying traffic loads.

NGINX Configuration:

To implement Token Bucket rate limiting in NGINX, you can use the limit_req_zone directive. Here is an example configuration:

In this example, the rate is set to 1 request per second, with a burst capacity of 5 requests, allowing for short bursts of traffic while maintaining an average rate.

Rate limiting is essential for protecting systems from abuse and ensuring fair resource allocation. The Token Bucket algorithm is often compared with other rate-limiting techniques, including the Leaky Bucket, Sliding Window, and Fixed Window algorithms. Understanding the differences can help in selecting the most appropriate algorithm for a given application.

Leaky Bucket: Unlike the Token Bucket, the Leaky Bucket algorithm enforces a strict output rate. It processes requests at a constant rate, regardless of incoming traffic bursts. This approach effectively smooths out bursts but can lead to delays in processing if the incoming rate exceeds the specified limit.

Sliding Window: The Sliding Window algorithm offers precise control over request rates by keeping track of requests over a fixed time window. While it allows for more accurate rate limiting, it is computationally more expensive due to the need for maintaining state information for each request.

Fixed Window: The Fixed Window algorithm divides time into fixed intervals and counts the number of requests within each interval. This can lead to edge effects, where a burst at the end of one interval may cause denial of service at the start of the next interval. The Token Bucket's flexibility in allowing bursts mitigates this issue.

In summary, the choice of a rate-limiting algorithm should be based on the specific needs of the application, considering factors like burst tolerance, complexity, and resource management.