Rate Limiting Architectures: Sliding Window Counter Algorithm with Redis

Every public-facing API needs rate limiting. Whether guarding against abusive scrapers, credential stuffing bots, or accidental infinite loops in third-party client code, rate limiters protect your backend infrastructure from cascading failure.

However, naive rate-limiting algorithms often introduce subtle vulnerabilities:

• Fixed Window Counters allow double the intended traffic at boundary thresholds (e.g., 100 requests at 11:59:59 and another 100 at 12:00:01).
• Sliding Window Logs (storing every timestamp in a Redis sorted set) consume excessive memory when millions of requests stream in.

In this deep dive, we examine the Sliding Window Counter algorithm—the production standard popularized by Cloudflare and Stripe—and implement it atomically using Redis and Lua.

The Mathematics of Sliding Window Counter

Instead of storing individual timestamps, we track only two integers:

1. The request count in the current window.
2. The request count in the previous window.

Previous Window (12:00 - 12:01)        Current Window (12:01 - 12:02)
[====== 80 requests ======]            [==== 30 requests ====      ]
                    <---------- 1-Minute Sliding Window ---------->
                                  ^ Current Time (30% into window)

If the client makes a request at the 18th second of the current minute (30% into the window):

• We take 70% of the previous window's requests ($80 \times 0.70 = 56$).
• We add 100% of the current window's requests ($30$).
• Estimated current load: $56 + 30 = 86$ requests.

If the allowed limit is 100 requests per minute, the request is permitted! This calculation prevents boundary spikes with near-zero memory footprint.

Atomic Production Implementation with Redis Lua

-- sliding_window.lua
local current_key = KEYS[1]
local prev_key = KEYS[2]
local max_limit = tonumber(ARGV[1])
local window_size = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local current_count = tonumber(redis.call('get', current_key) or "0")
local prev_count = tonumber(redis.call('get', prev_key) or "0")

local current_window_start = math.floor(now / window_size) * window_size
local time_into_current = now - current_window_start
local prev_weight = (window_size - time_into_current) / window_size

local estimated_requests = math.floor(prev_count * prev_weight + current_count)

if estimated_requests >= max_limit then
    return {0, estimated_requests}
else
    redis.call('incr', current_key)
    redis.call('expire', current_key, window_size * 2)
    return {1, estimated_requests + 1}
end

Python API Integration

import time
import redis

class SlidingWindowRateLimiter:
    def __init__(self, redis_client: redis.Redis, lua_script_text: str):
        self.redis = redis_client
        self.lua_script = self.redis.register_script(lua_script_text)

    def is_allowed(self, client_id: str, limit: int = 100, window_seconds: int = 60) -> tuple[bool, int]:
        now = int(time.time())
        current_window = now // window_seconds
        prev_window = current_window - 1

        current_key = f"rate:{client_id}:{current_window}"
        prev_key = f"rate:{client_id}:{prev_window}"

        result = self.lua_script(
            keys=[current_key, prev_key],
            args=[limit, window_seconds, now]
        )

        allowed = bool(result[0] == 1)
        current_usage = int(result[1])
        return allowed, current_usage

Best Practices for API Gateways

1. Always Return Rate Limit Headers: Inform clients of their remaining quota using standard headers (X-RateLimit-Limit, X-RateLimit-Remaining).
2. Differentiate Identity: Rate limit unauthenticated endpoints by IP address (X-Forwarded-For), but rate limit authenticated endpoints by API_KEY or USER_ID.
3. Fail Open on Redis Outages: If Redis is temporarily unreachable, log an alert but allow traffic to pass rather than breaking your entire API.