Rate Limiter Design: Token Bucket vs Sliding Window

In distributed architectures and API gateways, protecting backend microservices from DDoS attacks, brute-force logins, and noisy neighbors requires robust **rate limiting**. A well-designed rate limiter regulates the rate of client requests sent or received over a specific time window.

This comprehensive system design guide analyzes popular rate-limiting algorithms—specifically **Token Bucket**, **Leaky Bucket**, **Fixed Window Counter**, and **Sliding Window Log/Counter**—and explores how to implement them efficiently using **Redis and Lua scripts**.

1. Token Bucket Algorithm

The **Token Bucket** algorithm is one of the most widely used rate-limiting strategies (utilized by AWS API Gateway and Stripe). A container (bucket) of a fixed capacity holds tokens that are added at a constant refill rate.

• How It Works: When a request arrives, the system checks if a token is available in the bucket. If available, a token is consumed, and the request proceeds. If the bucket is empty, the request is throttled (`429 Too Many Requests`).
• Burst Allowance: Unlike leaky buckets, token buckets allow short bursts of traffic up to the maximum capacity of the bucket.
• Memory Efficiency: Requires storing only two values per client: `tokens_remaining` and `last_refilled_timestamp`.

# Python Token Bucket Implementation Concept
import time

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity
        self.tokens = float(capacity)
        self.refill_rate = refill_rate # tokens per second
        self.last_refilled = time.time()

    def consume(self, tokens: int = 1) -> bool:
        now = time.time()
        elapsed = now - self.last_refilled
        self.last_refilled = now
        
        # Refill tokens based on elapsed time
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)

        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False;

2. Sliding Window Algorithms: Log vs. Counter

While **Fixed Window** counters are simple to implement, they suffer from a major flaw: traffic spikes at the edge of window boundaries (e.g., doubling the allowed limit across a boundary). **Sliding Window** algorithms solve this issue:

• Sliding Window Log: Keeps track of exact request timestamps in a Redis sorted set (`ZSET`). When a request arrives, stale timestamps outside the current window are removed, and the remaining count is evaluated. Highly accurate, but high memory overhead for high-throughput clients.
• Sliding Window Counter (Recommended): Combines the fixed counter of the current window with a weighted count from the previous window based on the current timestamp's overlap percentage. Extremely memory-efficient and smooths out traffic spikes.

-- Redis Lua Script for Sliding Window Counter or Token Bucket Atomic Execution
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local current_time = tonumber(ARGV[2])
local window_size = tonumber(ARGV[3])

-- Remove old entries outside the sliding window
redis.call('ZREMRANGEBYSCORE', key, 0, current_time - window_size)

local current_requests = redis.call('ZCARD', key)

if current_requests < limit then
    redis.call('ZADD', key, current_time, current_time)
    redis.call('EXPIRE', key, window_size)
    return 1 -- Allowed
else
    return 0 -- Rate limited
end;

3. Distributed Rate Limiting Architecture

In modern microservice architectures, rate limiters cannot reside in local application memory because multiple API gateway instances scale horizontally.

• Centralized Redis Cluster: A distributed Redis cache stores rate-limiting counters or tokens keyed by user ID, API key, or IP address.
• Atomic Operations via Lua Scripts: To prevent race conditions (e.g., read-modify-write concurrency issues across multiple gateway nodes), rate limit logic is executed atomically inside Redis using embedded Lua scripts.
• Local Memory Caching (Edge): For ultra-low latency, API gateways often use local token bucket caches with a synchronization heartbeat to Redis every few hundred milliseconds.

Conclusion

Choosing the right rate-limiting strategy depends on your application's traffic profile. Use **Token Bucket** when you need to accommodate legitimate traffic bursts, and **Sliding Window Counters** backed by **Redis** when strict, rolling-window rate enforcement is required across distributed services.