Building a Sliding Window Rate Limiter with Redis

Protect your APIs from abuse using sorted sets, Lua scripts, and the sliding window algorithm

By SysAdmin · Published 2026-05-27

Building a Sliding Window Rate Limiter with Redis

Fixed windows have a burst problem at boundaries. Token buckets are complex. The sliding window algorithm hits the sweet spot — accurate, simple, and Redis-native.

1. The Problem

Rate limiting is the first line of defense for any API. Without it, a single client can exhaust your server's resources — whether by accident (runaway loop) or malice (DDoS).

The challenge: implement a sliding window rate limiter that:

• Allows a configurable number of requests per time window
• Tracks per-user request counts in Redis (shared across instances)
• Uses true sliding windows (not fixed windows with boundary bursts)
• Handles concurrent requests atomically

2. The Naïve Approach (and Why It Fails)

Fixed Window

// Window: 12:00:00 - 12:01:00 → allows 100 requests
// At 12:00:59 → 100 requests
// At 12:01:00 → counter resets, 100 more requests
// Result: 200 requests in 2 seconds!

Fixed windows reset at boundaries, allowing 2x burst at the window edge. A client sends 100 requests at 12:00:59 and 100 more at 12:01:00 — 200 requests in 2 seconds despite a "100 per minute" limit.

Simple Counter

long count = redis.incr("ratelimit:" + userId);
if (count == 1) redis.expire(key, windowSizeSeconds);
return count <= maxRequests;

This is a fixed window with TTL — same boundary burst problem. Plus, incr and expire aren't atomic, creating a race condition where the key increments but never expires.

3. The Right Model

A sorted set where each request is a member scored by its timestamp:

Redis Sorted Set: ratelimit:{userId}
  member: "1716825600123:a1b2c3d4"    score: 1716825600123
  member: "1716825600456:e5f6g7h8"    score: 1716825600456
  ...

To check if a request is allowed:

1. Remove all entries older than now - windowSize
2. Count remaining entries
3. If count < maxRequests, add the new request

All three steps in a single Lua script for atomicity.

4. The Implementation, Walked Through

The Interface

public interface RateLimiterContract {
    boolean allowRequest(String userId);
    void configure(int maxRequests, int windowSizeSeconds);
    int getRemainingRequests(String userId);
    void reset(String userId);
}

The Lua Script — Heart of the Solution

local key = KEYS[1]
local now = tonumber(ARGV[1])
local windowStart = tonumber(ARGV[2])
local maxReqs = tonumber(ARGV[3])
local member = ARGV[4]

-- 1. Remove expired entries
redis.call('ZREMRANGEBYSCORE', key, '-inf', windowStart)

-- 2. Count current entries
local count = redis.call('ZCARD', key)

-- 3. Conditionally add
if count < maxReqs then
    redis.call('ZADD', key, now, member)
    redis.call('EXPIRE', key, tonumber(ARGV[5]))
    return 1  -- allowed
else
    return 0  -- rejected
end

💡 Tip: The member includes a UUID fragment ("timestamp:uuid") to ensure uniqueness. Without it, two requests in the same millisecond would overwrite each other in the sorted set, effectively "losing" a request from the count.

Why Lua?

Without Lua, there's a race between ZCARD and ZADD:

• Thread A: ZCARD → 99 (under limit)
• Thread B: ZCARD → 99 (under limit)
• Thread A: ZADD → count becomes 100
• Thread B: ZADD → count becomes 101 (over limit!)

The Lua script makes the check-and-add atomic.

Remaining Requests

public int getRemainingRequests(String userId) {
    // Another Lua script: cleanup expired + count
    long windowStartMs = System.currentTimeMillis() - (windowSizeSeconds * 1000L);
    Object result = redis.eval(REMAINING_SCRIPT, ...);
    return (int) toLong(result);
}

⚠️ Trap: Always clean up expired entries before counting. If you don't ZREMRANGEBYSCORE first, stale entries inflate the count and users get rate-limited even though their window has passed.

5. Performance + Concurrency

Sorted Set Efficiency

• ZREMRANGEBYSCORE: O(log N + M) where M is removed entries — typically a few entries per call
• ZCARD: O(1)
• ZADD: O(log N)

For a 100-request window, each operation touches ~100 entries — sub-millisecond.

TTL as Safety Net

redis.call('EXPIRE', key, windowSizeSeconds + 1)

The +1 buffer ensures the key lives slightly longer than the window, so the last request in a window isn't lost to premature expiry. The TTL is a safety net — ZREMRANGEBYSCORE is what actually enforces the window.

Concurrent Safety

The grader fires 4 threads making requests simultaneously. Without Lua atomicity, some threads would slip through the limit. With Lua, the sorted set count is always accurate at decision time.

6. What the Grader Checks

7. Takeaways

1. Sorted sets are natural sliding windows. Score = timestamp means ZREMRANGEBYSCORE cleanly removes expired entries, and ZCARD gives you the count — all in O(log N).

1. Unique members prevent count corruption. Append a UUID fragment to the timestamp to ensure two requests in the same millisecond aren't collapsed into one.

1. Lua scripts are the right tool for distributed atomicity. Any time you need "read count, check condition, write" in Redis, a Lua script eliminates the race window between commands.

👉 Try it yourself: Sliding Window Rate Limiter on Cruscible