Rate Limit Implementation With Redis

Sliding window log algorithm

We can use Sorted Set to implement Sliding window log algorithm.

For this algorithm, we need to do

1. Remove old request (older than 60 second)
2. Count the current request (within 60 second windows)
3. Allow or deny new request base on step 2

sequenceDiagram
    participant User
    participant App
    participant Redis
    User->>App: Sends Request
    App->>Redis: ZREMRANGEBYSCORE (Remove < now - 60s)
    App->>Redis: ZCARD (Get current count)
    alt Count < Limit
        App->>Redis: ZADD (Add current timestamp)
        App->>Redis: EXPIRE (Refresh TTL)
        App->>User: 200 OK
    else Count >= Limit
        App->>User: 429 Too Many Requests
    end

In order to do this, we can use lua script. Because in Redis, lua script will execute as a single block of atomicity.

local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])

-- 1. Clear old logs
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

-- 2. Check current count
local current_count = redis.call('ZCARD', key)

if current_count < limit then
    -- 3. Add new request and set expiry
    redis.call('ZADD', key, now, now) -- first now is the score. set the ranking. second now is the value
    redis.call('EXPIRE', key, window)
    return 1 -- Allowed
else
    return 0 -- Rate limited
end

How to use it (python example)

import redis
import time

r = redis.Redis()

lua_script = """
content of lua script
"""

# Register the script
rate_limiter = r.register_script(lua_script)

# Execute the script
# keys and args must be passed as lists
is_allowed = rate_limiter(keys=['user123'], args=[int(time.time()), 60, 5])

Sliding window counter algorithm

For sliding window counter algorithm, we can implement it with redis hash.

1. For the same key, keep track of 2 values current_minute and previous_minute
2. Calculate based on rate limit algorithm `current_minute + percentage_overlap x previous_minute
   1. If over than rejected
   2. Else, increase current_minute by 1

graph TD
    A[Start Lua Script] --> B[Get Redis Time]
    B --> C[Calculate Weight using % window]
    C --> D[HGET current + prev counts]
    D --> E{Estimated Count > Limit?}
    E -- Yes --> F[Return 0: Blocked]
    E -- No --> G[HINCRBY current bucket]
    G --> H[Return 1: Allowed]

-- KEYS[1]: The rate limit key
-- ARGV[1]: Window size in seconds (e.g., 60)
-- ARGV[2]: Max requests allowed (e.g., 100)

local key = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])

-- 1. Get the current time from Redis (returns {seconds, microseconds})
local redis_time = redis.call('TIME')
local now = tonumber(redis_time[1])

-- 2. Calculate buckets
local current_bucket = now - (now % window)
local prev_bucket = current_bucket - window

-- 3. Calculate weight (how much of the previous bucket still overlaps)
local seconds_into_bucket = now % window
local overlap = (window - seconds_into_bucket) / window

-- 4. Get counts from Hash
local current_count = tonumber(redis.call('HGET', key, current_bucket) or "0")
local prev_count = tonumber(redis.call('HGET', key, prev_bucket) or "0")

-- 5. Calculate estimated total
local estimated_count = current_count + (prev_count * overlap)

-- 6. Check limit
if estimated_count >= limit then
    return 0 -- Rate Limited
end

-- 7. Increment and Cleanup
redis.call('HINCRBY', key, current_bucket, 1)
redis.call('EXPIRE', key, window * 2) -- Keep keys for 2 windows to be safe
return 1 -- Success