Redis Rate Limiting with Lua: Fixed Window to Token Bucket

“Design a rate limiter” is one of the most common system design prompts, and Redis is the expected building block. Interviewers want three things: an algorithm with its trade-offs (fixed window, sliding window, token bucket), an explanation of why the check must be atomic, and working Redis commands. The atomicity part also opens the door to “how do Redis transactions work?” and “why use Lua instead of MULTI?”, so this guide covers both.

Everything here targets Redis 7.4/8.x and works on Valkey. The Lua scripts were run with redis-py against fakeredis, an in-process emulator that executes real Lua; outputs shown are from those runs.

Before you start

You should know INCR, EXPIRE/PEXPIRE and sorted sets (ZADD, ZCARD, ZREMRANGEBYSCORE). Basic Lua syntax is enough for the scripts: local variables, if ... then ... end, and redis.call(...) to run a Redis command. Arguments arrive in two arrays: KEYS for key names and ARGV for everything else, both 1-indexed.

The short answer

A rate limiter reads a counter, decides, and writes, so it must be atomic or concurrent requests slip through. I implement it as a Lua script, which Redis runs as one indivisible unit in one round trip. The simplest algorithm is a fixed window: INCR a per-client key for the current window and set an expiry on the first hit; it is cheap but allows up to twice the limit around window boundaries. A sliding window log stores request timestamps in a sorted set and is exact but costs memory per request. A token bucket stores tokens and a timestamp in a hash, refills by elapsed time and allows bursts up to the bucket size with a steady average rate. I use the server’s clock (redis.call('TIME')) and pick fail-open or fail-closed explicitly.

How it works

Why atomicity matters, and the three tools

The naive limiter is a race:

count = int(r.get(key) or 0)   # two requests both read 99
if count < 100:
    r.incr(key)                # both increment: 101 requests allowed

Two transaction facts interviewers check: if a command fails at queue time (unknown command, wrong arity), EXEC returns EXECABORT and nothing runs; if it fails at execution time (WRONGTYPE), the other commands still apply. There is no rollback.

Lua rules that matter here

Scripts block the server while they run, so keep them O(1) or O(log N). Pass every key in KEYS so Redis Cluster can route the script and check the keys share a slot. Lua numbers returned to the client are truncated to integers, so return tostring(x) for fractions. Since Redis 7, Functions (FUNCTION LOAD, FCALL) are a persisted, named alternative to EVAL; the scripts below work in either form.

The algorithms

Step-by-step walkthrough

Step 1: Fixed window in Lua

-- KEYS[1] = rl:{client}:{window-start}, ARGV[1] = window length in ms
local count = redis.call('INCR', KEYS[1])
if count == 1 then
  redis.call('PEXPIRE', KEYS[1], ARGV[1])
end
return count

fixed = r.register_script(FIXED)
window = int(time.time() // 60)
count = fixed(keys=[f"rl:{client_id}:{window}"], args=[60_000])
allowed = count <= 100

Calling it four times on a fresh key returned [1, 2, 3, 4], with a positive PTTL. The INCR and the expiry happen together, so a crash can never leave a counter without a TTL. The weakness: 100 requests at 12:00:59 and 100 more at 12:01:00 are both allowed, 200 in two seconds.

Step 2: Sliding window log with a sorted set

-- KEYS[1] = rl:log:{client}; ARGV: now_ms, window_ms, limit, unique member
local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)
if redis.call('ZCARD', key) >= limit then
  return 0
end
redis.call('ZADD', key, now, ARGV[4])
redis.call('PEXPIRE', key, window)
return 1

With a limit of 3 per 60,000 ms, requests at 0, 100, 200, 300, 59,999, 60,001 and 60,150 ms returned 1, 1, 1, 0, 0, 1, 1: the fourth and fifth were rejected, and capacity returned exactly as the oldest entries left the window. The member must be unique (timestamp plus a request ID), or two requests in the same millisecond collapse into one entry. Memory grows with the limit, which is fine for 100 per minute and expensive for 100,000.

Step 3: Token bucket with the server clock

-- KEYS[1] = rl:tb:{client}; ARGV: capacity, refill rate per second, cost
local key      = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

local t   = redis.call('TIME')       -- {seconds, microseconds} from the server
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate / 1000)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HSET', key, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', key, math.ceil(capacity / rate * 1000) * 2)
return { allowed, math.floor(tokens) }

With capacity 5 and 2 tokens per second, seven immediate calls returned [1,4] [1,3] [1,2] [1,1] [1,0] [0,0] [0,0]; after a one-second pause, the next call was allowed again with one token left, because two tokens had refilled. Reading the server clock avoids skew between application servers; calling TIME inside a script is safe since Redis 5 because scripts replicate their effects, not the script itself.

Step 4: Call it from the application

bucket = r.register_script(TOKEN_BUCKET)     # EVALSHA with automatic EVAL fallback

def check(client_id: str) -> tuple[bool, int]:
    try:
        allowed, remaining = bucket(keys=[f"rl:tb:{client_id}"], args=[100, 10, 1])
        return bool(allowed), remaining
    except redis.exceptions.ConnectionError:
        return True, -1                       # fail open: availability over strictness

Return the remaining quota in RateLimit-Remaining style headers and a 429 Too Many Requests with Retry-After when denied. Fail open for ordinary API traffic, fail closed for login attempts or expensive operations where abuse is worse than an outage.

Step 5: Scale it across a cluster

Each script above touches one key, so limiters for different clients spread naturally over Redis Cluster slots. If a script must touch two keys (a per-user and a per-tenant limit together), give them the same hash tag, such as rl:{tenant:9}:user:42 and rl:{tenant:9}:total. Avoid one global key for all traffic: it becomes a hot key on a single shard.

Worked scenario

An API gateway used this limiter for 1,000 requests per hour per API key:

# Broken: two separate commands
count = r.incr(f"rl:{api_key}")
if count == 1:
    r.expire(f"rl:{api_key}", 3600)
if count > 1000:
    raise TooManyRequests()

During a deploy, pods were killed mid-request. For a handful of customers, the process died after INCR returned 1 but before EXPIRE ran. Those keys had no TTL, so the counter never reset: once those customers reached 1,000 requests, they were blocked permanently, and support tickets arrived days later. TTL rl:<key> returned -1 for each affected key.

The fix moved both commands into the Step 1 script, so the expiry is set in the same atomic unit as the first increment, and added a cleanup:

# find counters that lost their TTL (SCAN, never KEYS)
redis-cli --scan --pattern 'rl:*' | while read k; do
  [ "$(redis-cli TTL "$k")" = "-1" ] && redis-cli EXPIRE "$k" 3600
done

An alert on keys matching rl:* with no TTL now catches the bug class early.

Common mistake

• Separate INCR and EXPIRE calls. A crash between them creates a counter that never resets.
• “MULTI makes check-then-increment safe.” You cannot read the count inside the transaction to decide; use WATCH or Lua.
• “Transactions roll back on error.” Runtime errors leave the other commands applied.
• Using client clocks. Skewed application servers disagree about windows and refill time; use TIME in the script or one clock source.
• Building key names inside the script. Cluster cannot route or validate keys it does not see in KEYS.
• Non-unique sorted-set members. Same-millisecond requests overwrite each other and undercount.

Verify the behavior

The sequences quoted above come from runs like this one (redis-py, works the same against a real server):

fixed = r.register_script(FIXED)
print([fixed(keys=["rl:fixed:u1:1700000000"], args=[60000]) for _ in range(4)])
# [1, 2, 3, 4]
print(r.pttl("rl:fixed:u1:1700000000") > 0)
# True

bucket = r.register_script(TOKEN_BUCKET)
print([bucket(keys=["rl:tb:42"], args=[5, 2, 1]) for _ in range(7)])
# [[1, 4], [1, 3], [1, 2], [1, 1], [1, 0], [0, 0], [0, 0]]
time.sleep(1.0)
print(bucket(keys=["rl:tb:42"], args=[5, 2, 1]))
# [1, 1]

For concurrency, fire 500 parallel requests at a limit of 100 from several processes and count the allowed responses: the Lua versions allow exactly 100, the naive GET-then-INCR version allows more. SLOWLOG GET should show no limiter scripts; if it does, a script is doing O(N) work.

Follow-up questions

What does EXEC return if a watched key changed? A null reply; nothing was executed, and the client retries the whole read-modify-write.

What happens if a Lua script runs too long? After busy-reply-threshold (5 seconds) other clients get BUSY; SCRIPT KILL stops it only if it has not written yet, otherwise the only option is SHUTDOWN NOSAVE.

How would you approximate a sliding window cheaply? The sliding window counter: keep the current and previous fixed-window counts and estimate previous * (1 - elapsed_fraction) + current. Two small keys per client, smooth limits, slight inaccuracy.

How do you rate limit across regions? Usually per region with a share of the global budget, because a cross-region round trip on every request costs more than slight over-admission.

Interview exercise

A login endpoint must allow at most 5 failed attempts per username per 15 minutes, and at most 100 failed attempts per source IP per 15 minutes. It runs on Redis Cluster. Which algorithm and keys do you use, and how do you keep the check atomic?

Answer and reasoning

Use a sliding window log or a fixed window per dimension; for security limits, exactness at boundaries matters, so a sorted-set log (only failures are recorded, so memory stays small) is a good fit. The username key and the IP key are different entities and will live in different slots, so do not force them into one script with a shared hash tag (that would funnel all logins through one shard). Instead run two single-key scripts, rl:login:user:{alice} and rl:login:ip:{203.0.113.7}, and deny if either rejects; each check is atomic on its own key, and checking both independently is acceptable because each limit is enforced separately. Use the server clock inside the scripts, fail closed if Redis is unreachable (login abuse is worse than a brief outage), and reset the username log on a successful login.

Continue learning

Practise with the Redis interview questions and the Redis MCQs. Related notes: System design rate limiting and fairness, Redis distributed locks with SET NX PX for more compare-and-set scripts, and Redis data structures for sorted sets. Primary sources: Scripting with Lua, Redis functions, Transactions and the EXPIRE command reference.