Token Bucket Algorithm

The Token Bucket Algorithm is a fundamental and effective method used for API rate limiting, balancing flexibility with control. It allows small bursts of traffic while maintaining a consistent average request rate, protecting backend systems from overload and abuse, and supporting fair usage and billing strategies.

How the Token Bucket Algorithm Works

• Each request consumes one token.
• Tokens are added to a bucket at a fixed, regular rate.
• The bucket has a maximum capacity, preventing token accumulation beyond this limit.
• If the bucket is empty when a request arrives, the request is rejected or throttled.
• During low traffic periods, tokens accumulate in the bucket, allowing for bursts during traffic spikes.
• In high traffic conditions, only requests with available tokens are processed.

import time

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = time.time()

    def allow_request(self):
        now = time.time()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        else:
            return False


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

for i in range(100):
    if bucket.allow_request():
        print(f"Request {i + 1}: Allowed")
    else:
        print(f"Request {i + 1}: Denied")
    time.sleep(0.1)  # Simulate time between requests        

Real-World Use Cases

• Protection against traffic spikes: Prevents backend overload during sudden surges.
• Limiting abuse: Restricts request rates per IP, user, or endpoint.
• Billing control: Charges based on tokens consumed, aligning cost with usage.
• Fair resource distribution: Ensures equitable access among users.

Practical Considerations

• The algorithm's flexibility makes it ideal in scenarios with variable traffic, such as e-commerce or streaming, where bursts are common.
• It supports different configurations, including adjusting the bucket capacity (burst size) and refill rate (average request rate).

Summary

The Token Bucket Algorithm provides a reliable, scalable, and adaptable way to manage API request traffic, helping ensure backend stability, fair usage, and operational cost control. Its capacity to handle burst traffic while enforcing steady state limits makes it a popular choice for modern API rate limiting implementations.