Fixed Window, Sliding Log, and Sliding Window Counter

In one line

A fixed window counts requests per clock minute with INCR + EXPIRE, simple but bursty at window edges. A sliding log stores every request timestamp in a sorted set for exact limits at high memory cost. A sliding window counter blends two fixed windows for a close approximation at fixed-window cost.

0/4 · 0%

Think of it like this

A gym allowing 100 entries per hour. A fixed window resets the tally at every o'clock, so 100 people could enter at 9:59 and 100 more at 10:00. A sliding window asks "how many entered in the last 60 minutes?" at every moment, which is fairer and needs a better record.

Key ideas

01
Fixed window: key rl:{user}:<floor(now/60)>, INCR, set EXPIRE on the first hit (atomically via Lua or SET NX EX + INCR), reject when the count exceeds the limit. O(1) and one small key per user per window. The weakness: up to 2× the limit in a short burst across a boundary.
02
Sliding log: a sorted set per user with one member per request (score = timestamp in ms, member = a unique request ID). On each request: ZREMRANGEBYSCORE older than now − window, ZCARD, and ZADD if under the limit, all in one Lua script. Exact, but memory is O(limit) per user: 1,000 requests/min × 1M users is a lot of entries.
03
Sliding window counter: keep fixed-window counts for the current and previous windows and estimate count = current + previous × (1 − elapsed_fraction). Two small keys per user, smooth limits, and an error that's usually small (it assumes the previous window's requests were spread evenly). Cloudflare described this approach for their rate limiting at scale.
04
Always return useful headers from the limiter: remaining quota, reset time, and Retry-After on HTTP 429.
05
Keys and Cluster: all keys for one limiter decision must share a hash tag (rl:{user:42}:...) because the Lua script touches several of them.

Code & diagrams

boundary-burst.mermaiddiagram

Rendering diagram…

sliding-log.lualua

-- KEYS[1] = zset key; ARGV: now_ms, window_ms, limit, request_id
local now, window, limit = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', now - window)
local count = redis.call('ZCARD', KEYS[1])
if count >= limit then
  local oldest = redis.call('ZRANGE', KEYS[1], 0, 0, 'WITHSCORES')
  local retry_ms = tonumber(oldest[2]) + window - now
  return {0, count, retry_ms}
end
redis.call('ZADD', KEYS[1], now, ARGV[4])
redis.call('PEXPIRE', KEYS[1], window)
return {1, count + 1, 0}

sliding-counter.lualua

Two fixed-window counters, weighted. KEYS share a hash tag so they're in one slot.

-- KEYS[1] = current window key, KEYS[2] = previous window key
-- ARGV: limit, window_sec, elapsed_sec_in_current_window
local limit, window, elapsed = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local cur  = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local estimate = cur + prev * ((window - elapsed) / window)
if estimate >= limit then
  return {0, math.floor(estimate)}
end
cur = redis.call('INCR', KEYS[1])
if cur == 1 then redis.call('EXPIRE', KEYS[1], window * 2) end
return {1, math.floor(cur + prev * ((window - elapsed) / window))}

Interview problem

The problem

100 requests per minute, without the boundary burst

Implement "100 requests/minute per user" with a fixed window, show the boundary problem, then fix it with a sliding window. Compare memory for 5M active users.

You're given

Limit 100/min/user
5M active users
Exactness: small overshoot acceptable

The interviewer follows up

How accurate is the sliding window counter?

When it breaks

Sliding log for high limits (10,000 req/min per API key)

What you see

Each hot key's sorted set holds 10,000 entries; ZREMRANGEBYSCORE and memory grow with traffic; the limiter itself becomes a big-key and latency problem.

Fix & prevent

Use a sliding window counter or token bucket for high limits; keep logs for small, exact limits (for example 5 login attempts).

Explain it without notes

Compare fixed window, sliding log and sliding window counter on accuracy and memory.

Practice

Write a test that sends 100 requests at second 59 and 100 at second 61 of a minute, and check which algorithms allow them.

Trade-offs

↔
Exactness costs memory: sliding logs are exact but heavy; counters are cheap and approximate.

Done when you can

I can implement all three window algorithms atomically in Lua.
I can explain the boundary burst and choose an algorithm by accuracy and memory.

Command Palette