yelgabo

Rate limiting with Redis

Four algorithms, the exact Redis commands behind each one, and the data structure they leave in memory after every request.

Try the sliding window log

Limit: 3 requests per 10,000 ms. Runs in your browser, replaying the commands a real Redis would execute.

15 s ago10 s ago (window start)now
Inside the window, counted Outside the window, still stored until the next call trims it
No requests yet. The key does not exist.

Stored in rl:log:demo


      

Commands run for the last request


      

The idea

A rate limiter caps how many requests a client can make in a period of time. On every incoming request you identify the client (a user ID, an application programming interface (API) key, or an Internet Protocol (IP) address), check how much of its allowance it has used, and either let the request through or reject it with Hypertext Transfer Protocol (HTTP) status 429 Too Many Requests.

Redis is a good home for that allowance because:

  • It is shared. Every app server checks the same numbers, so a client cannot dodge the limit by landing on a different server.
  • It is fast. Each check is one network round trip to an in-memory store.
  • It has atomic operations and server-side Lua scripts, so two servers checking at the same instant cannot both sneak a request through.
  • Keys can expire on their own, so state for idle clients cleans itself up.

All keys on this page start with rl: (short for rate limit) so they are easy to find and never collide with other data.

Redis toolkit

Every algorithm below is built from a handful of commands. This section covers how each one behaves, including the edge cases that matter for rate limiting.

Keys need no setup

Everything in Redis lives under a key, and a data structure is created the first time you write to it. There is no schema and no create step. Commands that read or increment a missing key treat it as empty: INCR treats a missing key as 0, increments it, and returns 1.

A counter from nothing
# Build
> INCR rl:user42:29310840
(integer) 1
> INCR rl:user42:29310840
(integer) 2

# Read
> GET rl:user42:29310840
"2"
> EXISTS rl:user42:29999999
(integer) 0

Expiry: TTL, PEXPIRE, PEXPIREAT

A key can carry a time to live (TTL), after which Redis deletes it. There are two ways to set one:

  • Relative: EXPIRE key seconds and PEXPIRE key milliseconds mean "delete this key that long from right now." Calling it again replaces the old deadline, so repeating the same number keeps pushing the deadline forward.
  • Absolute: PEXPIREAT key unix-ms means "delete this key at this exact Unix timestamp in milliseconds."

The NX flag (Redis 7 and later) sets the TTL only if the key has none yet, which lets you set a deadline once and leave it alone. TTLs apply to a whole key; there is no per-member expiry inside a sorted set.

Relative expiry resets the deadline each call

Three calls at three times. Each one replaces the previous deadline.

# Build
PEXPIRE rl:log:user42 60000    # at t=1758650400123, deletes at 1758650460123
PEXPIRE rl:log:user42 60000    # at t=1758650415456, deletes at 1758650475456
PEXPIRE rl:log:user42 60000    # at t=1758650431789, deletes at 1758650491789

# Same final deadline, written as an absolute time
PEXPIREAT rl:log:user42 1758650491789

# Read (at t=1758650431789)
> PTTL rl:log:user42
(integer) 60000

Sorted sets

A sorted set (ZSET) stores unique string members, each with a numeric score, kept ordered by score. The command shape is:

ZADD <key> <score> <member>
  • key is the name of the sorted set. ZADD creates it if it does not exist.
  • score is the number used for ordering.
  • member is the item being stored. Each member appears at most once per set. Adding a member that already exists updates its score instead of adding a second copy, and ZADD returns 0.

The other sorted set commands used here:

  • ZCARD key returns the number of members (the set's cardinality). It is O(1) because Redis stores the size, and returns 0 for a missing key.
  • ZREMRANGEBYSCORE key min max deletes every member whose score is between min and max, inclusive, and returns how many it deleted.
  • ZRANGE key start stop WITHSCORES reads members by position, lowest score first. 0 -1 means all of them; 0 0 means just the oldest.
An existing member gets its score updated
# Build
> ZADD demo 1000 "request"
(integer) 1                 # new member added
> ZADD demo 5000 "request"
(integer) 0                 # existing member, score updated

# Read
> ZRANGE demo 0 -1 WITHSCORES
1) "request"
2) "5000"                   # score 1000 is gone
> ZCARD demo
(integer) 1

# Flags that change what happens to an existing member
ZADD demo NX 5000 "request"   # only add new members, never update
ZADD demo XX 5000 "request"   # only update existing members, never add
ZADD demo GT 5000 "request"   # update only if the new score is greater
ZADD demo LT 5000 "request"   # update only if the new score is less

One set per user, or one set for everyone?

The deciding question is what you need to compare or count. A leaderboard ranks users against each other, so all users share one set with one member per user. A rate limiter counts one user's recent requests and users never interact, so each user gets their own set with one member per request, and ZCARD on that set answers "how many requests did this user make recently." A single shared set would count everyone's requests together and lose the per-user number.

Same command, different roles for key and member
# Build: leaderboard, member = player
ZADD leaderboard 4200 "alice"
ZADD leaderboard 3900 "bob"

# Build: rate limiter, member = one request
ZADD rl:log:user42 1758650400123 "1758650400123-9f2c"
ZADD rl:log:user42 1758650415456 "1758650415456-a71e"

# Read
> ZCARD leaderboard
(integer) 2
> ZCARD rl:log:user42
(integer) 2
leaderboard
scoremember
3900"bob"
4200"alice"
rl:log:user42
scoremember
1758650400123"1758650400123-9f2c"
1758650415456"1758650415456-a71e"

1Fixed window counter

Split time into fixed buckets (for example, whole minutes) and count requests per bucket. The bucket number is floor(unix_seconds / window_seconds), so the key name changes when a new window starts and the count starts over from 1. Each bucket key gets a TTL so old buckets delete themselves.

import time
import redis

r = redis.Redis()

def allow_fixed_window(client_id: str, limit: int, window_sec: int) -> bool:
    bucket = int(time.time() // window_sec)
    key = f"rl:{client_id}:{bucket}"

    pipe = r.pipeline()                     # wraps both commands in MULTI/EXEC
    pipe.incr(key)
    pipe.expire(key, window_sec, nx=True)   # set the TTL only on the first request
    results = pipe.execute()

    count = results[0]
    return count <= limit

The NX on EXPIRE matters: a bucket has a fixed end, so later requests should not push its deletion further out. Without any EXPIRE, every minute leaves a new key per client behind until memory fills.

Two requests in one bucket

Limit 3 per 60 s. Both requests at t = 1758650410 s, so bucket = 1758650410 // 60 = 29310840.

# Build
> INCR rl:user42:29310840
(integer) 1
> EXPIRE rl:user42:29310840 60 NX
(integer) 1                 # TTL set
> INCR rl:user42:29310840
(integer) 2
> EXPIRE rl:user42:29310840 60 NX
(integer) 0                 # TTL already set, unchanged

# Read (same second)
> GET rl:user42:29310840
"2"
> TTL rl:user42:29310840
(integer) 60
keyvalueTTL
rl:user42:29310840"2"60 s

The weakness is the boundary burst. A client can use its whole allowance at the end of one bucket and again at the start of the next.

Six requests in one second with a limit of 3

Three requests at t = 1758650459 s (bucket 1758650459 // 60 = 29310840), then three at t = 1758650460 s (bucket 1758650460 // 60 = 29310841).

# Build: t=1758650459
> INCR rl:user42:29310840
(integer) 1                 # allowed
> EXPIRE rl:user42:29310840 60 NX
(integer) 1
> INCR rl:user42:29310840
(integer) 2                 # allowed
> EXPIRE rl:user42:29310840 60 NX
(integer) 0
> INCR rl:user42:29310840
(integer) 3                 # allowed
> EXPIRE rl:user42:29310840 60 NX
(integer) 0

# Build: t=1758650460, new bucket
> INCR rl:user42:29310841
(integer) 1                 # allowed
> EXPIRE rl:user42:29310841 60 NX
(integer) 1
> INCR rl:user42:29310841
(integer) 2                 # allowed
> EXPIRE rl:user42:29310841 60 NX
(integer) 0
> INCR rl:user42:29310841
(integer) 3                 # allowed
> EXPIRE rl:user42:29310841 60 NX
(integer) 0

# Read
> GET rl:user42:29310840
"3"
> GET rl:user42:29310841
"3"
keyvalue
rl:user42:29310840"3"
rl:user42:29310841"3"

Tradeoff: one integer per client and the cheapest possible check, but up to twice the limit can pass around a bucket boundary.

2Sliding window log

Keep a log of every allowed request's timestamp in a per-client sorted set. The score is the request time in milliseconds; the member is a unique request ID. On each request: delete entries older than the window, count what remains, and add the new request only if the count is under the limit.

Those steps read, decide, then write, so they must run atomically. Otherwise two app servers could both read a count of 99 with a limit of 100 and both allow. A Lua script solves this: Redis runs a script to completion without interleaving any other command.

-- sliding_log.lua
-- KEYS[1] = rate limit key
-- ARGV[1] = now (ms), ARGV[2] = window (ms), ARGV[3] = limit, ARGV[4] = unique request id
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local member = ARGV[4]

redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

local count = redis.call('ZCARD', key)
if count >= limit then
    return 0
end

redis.call('ZADD', key, now, member)
redis.call('PEXPIRE', key, window)
return 1
import time
import uuid
import redis

r = redis.Redis()

with open("sliding_log.lua") as f:
    SLIDING_LOG_LUA = f.read()

sliding_log = r.register_script(SLIDING_LOG_LUA)

def allow_sliding_log(client_id: str, limit: int, window_ms: int) -> bool:
    now_ms = int(time.time() * 1000)
    key = f"rl:log:{client_id}"
    request_id = f"{now_ms}-{uuid.uuid4().hex}"

    result = sliding_log(keys=[key], args=[now_ms, window_ms, limit, request_id])
    return result == 1

What the set looks like, request by request

All cards in this section use limit = 3 and window = 60,000 ms. Member suffixes are shortened to 4 hexadecimal characters for readability; the code above uses a full 32-character universally unique identifier (UUID).

Card 1: One client after three requests
# Build: three allowed requests
ZADD rl:log:user42 1758650400123 "1758650400123-9f2c"
PEXPIRE rl:log:user42 60000
ZADD rl:log:user42 1758650415456 "1758650415456-a71e"
PEXPIRE rl:log:user42 60000
ZADD rl:log:user42 1758650431789 "1758650431789-03bd"
PEXPIRE rl:log:user42 60000

# Read (at t=1758650431789)
> TYPE rl:log:user42
zset
> ZRANGE rl:log:user42 0 -1 WITHSCORES
1) "1758650400123-9f2c"
2) "1758650400123"
3) "1758650415456-a71e"
4) "1758650415456"
5) "1758650431789-03bd"
6) "1758650431789"
> ZCARD rl:log:user42
(integer) 3
> PTTL rl:log:user42
(integer) 60000
rl:log:user42 (TTL 60000 ms)
scoremember
1758650400123"1758650400123-9f2c"
1758650415456"1758650415456-a71e"
1758650431789"1758650431789-03bd"
Card 2: Trim, then allow

New request at t = 1758650470000. Cutoff = 1758650470000 − 60000 = 1758650410000.

# Build: script run for the new request
> ZREMRANGEBYSCORE rl:log:user42 0 1758650410000
(integer) 1                 # removed "1758650400123-9f2c"
> ZCARD rl:log:user42
(integer) 2                 # 2 < 3, allowed
> ZADD rl:log:user42 1758650470000 "1758650470000-5c88"
(integer) 1
> PEXPIRE rl:log:user42 60000
(integer) 1

# Read
> ZRANGE rl:log:user42 0 -1 WITHSCORES
1) "1758650415456-a71e"
2) "1758650415456"
3) "1758650431789-03bd"
4) "1758650431789"
5) "1758650470000-5c88"
6) "1758650470000"
> ZCARD rl:log:user42
(integer) 3
rl:log:user42 (TTL 60000 ms)
scoremember
1758650400123"1758650400123-9f2c"
1758650415456"1758650415456-a71e"
1758650431789"1758650431789-03bd"
1758650470000"1758650470000-5c88"
Card 3: Blocked, and when to retry

New request at t = 1758650472000. Cutoff = 1758650472000 − 60000 = 1758650412000. The oldest score, 1758650415456, is above the cutoff, so nothing is trimmed.

# Build: script run for the new request
> ZREMRANGEBYSCORE rl:log:user42 0 1758650412000
(integer) 0
> ZCARD rl:log:user42
(integer) 3                 # 3 >= 3, rejected
                            # script returns 0, no ZADD

# Read: oldest entry decides the retry time
> ZRANGE rl:log:user42 0 0 WITHSCORES
1) "1758650415456-a71e"
2) "1758650415456"
rl:log:user42 (unchanged)
scoremember
1758650415456"1758650415456-a71e"
1758650431789"1758650431789-03bd"
1758650470000"1758650470000-5c88"

Retry in = oldest score + window − now = 1758650415456 + 60000 − 1758650472000 = 3456 ms. Send Retry-After: 4 (seconds, rounded up).

Card 4: Multiple clients side by side

Each client has its own key. They share nothing except the prefix.

# Build
ZADD rl:log:user7 1758650468210 "1758650468210-e41a"
ZADD rl:log:203.0.113.9 1758650469900 "1758650469900-7b02"

# Read (SCAN, never KEYS, in production)
> SCAN 0 MATCH rl:log:* COUNT 100
1) "0"
2) 1) "rl:log:user42"
   2) "rl:log:user7"
   3) "rl:log:203.0.113.9"
> ZCARD rl:log:user42
(integer) 3
> ZCARD rl:log:user7
(integer) 1
> ZCARD rl:log:203.0.113.9
(integer) 1
keymembers
rl:log:user423 (from Card 2)
rl:log:user71
rl:log:203.0.113.91 (keyed by IP address)
Card 5: Why members must be unique

Two requests arrive in the same millisecond. With the timestamp alone as the member, the second ZADD updates the first entry instead of adding one.

# Build: timestamp-only members (wrong)
> ZADD rl:log:user99 1758650480000 "1758650480000"
(integer) 1                 # added
> ZADD rl:log:user99 1758650480000 "1758650480000"
(integer) 0                 # same member, nothing added

# Read
> ZCARD rl:log:user99
(integer) 1                 # two requests counted as one

# Build: timestamp plus random suffix (correct)
> ZADD rl:log:user100 1758650480000 "1758650480000-2d9a"
(integer) 1
> ZADD rl:log:user100 1758650480000 "1758650480000-c613"
(integer) 1

# Read
> ZCARD rl:log:user100
(integer) 2                 # both counted
rl:log:user99
scoremember
1758650480000"1758650480000"
rl:log:user100
scoremember
1758650480000"1758650480000-2d9a"
1758650480000"1758650480000-c613"

What goes in the member

Anything, as long as it is unique within that client's set while it is inside the window. The limiter only uses the scores (to trim by time) and the count (ZCARD); it never reads the member's content. The timestamp prefix in the examples is redundant with the score and exists only to make the set readable when you inspect it.

A duplicate causes an undercount, which lets the client exceed the limit. It only matters when the same member string lands in the same client's set while the earlier copy is still stored. A rare collision lets one extra request through. A constant member such as "request" keeps the set at one member forever, so the client is never limited at all.

Three valid member choices
# Random UUID: what the code uses
ZADD rl:log:user42 1758650400123 "9f2c41d07ab84e1f9c3b2a6d58e0f7c1"

# Per-client counter: shorter, guaranteed unique, costs one extra key and command
> INCR rl:seq:user42
(integer) 57
ZADD rl:log:user42 1758650400123 "57"

# Existing request or trace ID: shows which requests used the quota
ZADD rl:log:user42 1758650400123 "req_8Hk2Lp0Qz"

Member length costs memory, since every member is stored for up to one window. With a high limit like 10,000 requests per hour per client, a short counter saves real space over a 32-character UUID.

Two cleanup mechanisms, two jobs

ZCARD counts every member currently stored. It has no concept of age. Old requests stop counting only because ZREMRANGEBYSCORE deleted them one line earlier. PEXPIRE is separate: it deletes the whole key if the client goes quiet for a full window, which is purely memory cleanup.

CommandWhat it removesWhen
ZREMRANGEBYSCORE key 0 <now − window>Individual old timestamps inside the setEvery call, right before ZCARD
PEXPIRE key <window>The entire setOnly if no request arrives for a full window

Resetting the TTL to the full window on every allowed request is correct here: the request just added is the newest member and stays relevant for exactly one window. Once that passes, every member is outside the window and the set would count as 0 anyway.

Walkthrough of both mechanisms

Window 60,000 ms, limit 3. Timestamps shortened to small numbers.

# t=1000
> ZREMRANGEBYSCORE key 0 -59000
(integer) 0
> ZCARD key
(integer) 0
> ZADD key 1000 "r1"
(integer) 1
> PEXPIRE key 60000           # whole key dies at t=61000 if untouched
(integer) 1

# t=5000
> ZREMRANGEBYSCORE key 0 -55000
(integer) 0
> ZCARD key
(integer) 1
> ZADD key 5000 "r2"
(integer) 1
> PEXPIRE key 60000           # deadline moves to t=65000
(integer) 1

# t=62000: key still alive (deadline 65000), but "r1" is trimmed
> ZREMRANGEBYSCORE key 0 2000
(integer) 1                   # removed "r1" (score 1000)
> ZCARD key
(integer) 1                   # "r2" only
> ZADD key 62000 "r3"
(integer) 1
> PEXPIRE key 60000           # deadline moves to t=122000
(integer) 1

# Read
> ZRANGE key 0 -1 WITHSCORES
1) "r2"
2) "5000"
3) "r3"
4) "62000"

Had the client gone silent after t=5000 and returned at t=70000, the key would have been deleted at t=65000. ZCARD on a missing key returns 0, so the client starts fresh.

Tradeoff: exact, with no boundary burst. Memory is O(limit) per client, which gets expensive for high limits.

3Sliding window counter

A middle ground between the first two. Keep fixed window counters as in algorithm 1, but estimate a sliding window by blending the previous bucket with the current one. The further you are into the current bucket, the less the previous bucket counts:

estimated = prev_count * (window - elapsed_in_current) / window + curr_count

Two integers per client, and the boundary burst mostly disappears. The estimate assumes the previous bucket's requests were spread evenly across it, so it is approximate.

-- sliding_counter.lua
-- KEYS[1] = current bucket key, KEYS[2] = previous bucket key
-- ARGV[1] = now (ms), ARGV[2] = window (ms), ARGV[3] = limit
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])

local curr = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')

local elapsed = now % window
local weight = (window - elapsed) / window
local estimated = prev * weight + curr

if estimated >= limit then
    return 0
end

redis.call('INCR', KEYS[1])
redis.call('PEXPIRE', KEYS[1], window * 2)   -- still needed as "previous" during the next window
return 1
with open("sliding_counter.lua") as f:
    SLIDING_COUNTER_LUA = f.read()

sliding_counter = r.register_script(SLIDING_COUNTER_LUA)

def allow_sliding_counter(client_id: str, limit: int, window_ms: int) -> bool:
    now_ms = int(time.time() * 1000)
    bucket = now_ms // window_ms
    curr_key = f"rl:sw:{{{client_id}}}:{bucket}"        # braces form a hash tag, see Production details
    prev_key = f"rl:sw:{{{client_id}}}:{bucket - 1}"

    result = sliding_counter(keys=[curr_key, prev_key], args=[now_ms, window_ms, limit])
    return result == 1
Rejected 15 seconds into a bucket

Limit 10 per 60,000 ms. Now = 1758650415000, so bucket = 1758650415000 // 60000 = 29310840, which started at 29310840 × 60000 = 1758650400000. Elapsed = 15000 ms, weight = (60000 − 15000) / 60000 = 0.75.

# Build: state left by earlier requests
SET rl:sw:{user42}:29310839 8
SET rl:sw:{user42}:29310840 4

# Read: what the script sees
> GET rl:sw:{user42}:29310839
"8"
> GET rl:sw:{user42}:29310840
"4"

# estimated = 8 * 0.75 + 4 = 10
# 10 >= 10, rejected, no INCR
keyvaluerole
rl:sw:{user42}:29310839"8"previous
rl:sw:{user42}:29310840"4"current
Allowed 30 seconds into the same bucket

Same state. Now = 1758650430000, elapsed = 30000 ms, weight = (60000 − 30000) / 60000 = 0.5.

# Read: what the script sees
> GET rl:sw:{user42}:29310839
"8"
> GET rl:sw:{user42}:29310840
"4"

# estimated = 8 * 0.5 + 4 = 8
# 8 < 10, allowed

# Build: script writes
> INCR rl:sw:{user42}:29310840
(integer) 5
> PEXPIRE rl:sw:{user42}:29310840 120000
(integer) 1
keyvaluerole
rl:sw:{user42}:29310839"8"previous
rl:sw:{user42}:29310840"5"current

Tradeoff: constant memory like the fixed window, accuracy close to the log. A good default when limits are high.

4Token bucket

Each client has a bucket holding up to capacity tokens that refills at a steady rate. Each request spends tokens (usually 1). Short bursts up to capacity are allowed, while the long-run average is held to the refill rate. State is a hash with two fields, tokens and ts (the time of the last update), and refilling is computed lazily from the elapsed time on each request, so no background job is needed.

-- token_bucket.lua
-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill rate (tokens per second), ARGV[3] = cost of this request
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])

local t = redis.call('TIME')   -- server clock, so app servers with skewed clocks agree
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])
local ts = tonumber(state[2])
if tokens == nil then
    tokens = capacity
    ts = now
end

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

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

redis.call('HSET', key, 'tokens', tokens, 'ts', now)
local full_refill_ms = math.ceil(capacity / rate * 1000)
redis.call('PEXPIRE', key, full_refill_ms)   -- an idle bucket is full again by then, so deleting it loses nothing
return {allowed, tostring(tokens)}           -- Lua numbers returned to Redis are truncated to integers

Calling TIME inside a script works as written on Redis 7 and later. On Redis 5 and 6, add redis.replicate_commands() as the first line.

with open("token_bucket.lua") as f:
    TOKEN_BUCKET_LUA = f.read()

token_bucket = r.register_script(TOKEN_BUCKET_LUA)

def allow_token_bucket(client_id: str, capacity: int, per_second: float, cost: int = 1) -> tuple[bool, float]:
    key = f"rl:tb:{client_id}"

    result = token_bucket(keys=[key], args=[capacity, per_second, cost])

    allowed = result[0] == 1
    remaining = float(result[1])
    return allowed, remaining
Refill, then spend

Capacity 5, refill 1 token per second, cost 1. Stored state: 2 tokens at ts = 1758650400000. Request at server time 1758650401500: elapsed = 1500 ms, refilled = 2 + 1500 × 1 / 1000 = 3.5, capped at min(5, 3.5) = 3.5. 3.5 ≥ 1, so allowed, leaving 2.5. Full refill time = ceil(5 / 1 × 1000) = 5000 ms.

# Build: prior state
HSET rl:tb:user42 tokens 2 ts 1758650400000

# Build: script writes for the request
> HSET rl:tb:user42 tokens 2.5 ts 1758650401500
(integer) 0                 # fields existed, updated
> PEXPIRE rl:tb:user42 5000
(integer) 1

# Read
> HGETALL rl:tb:user42
1) "tokens"
2) "2.5"
3) "ts"
4) "1758650401500"
> PTTL rl:tb:user42
(integer) 5000
rl:tb:user42 (hash, TTL 5000 ms)
fieldvalue
tokens"2.5"
ts"1758650401500"
A burst drains the bucket

Starting from the previous card. Four requests at server time 1758650402000.

RequestElapsedRefilledDecisionTokens after
A500 ms2.5 + 0.5 = 3.0allowed2
B0 ms2 + 0 = 2allowed1
C0 ms1 + 0 = 1allowed0
D0 ms0 + 0 = 0rejected (0 < 1)0
# Build: script writes, one HSET + PEXPIRE per request
HSET rl:tb:user42 tokens 2 ts 1758650402000    # A
PEXPIRE rl:tb:user42 5000
HSET rl:tb:user42 tokens 1 ts 1758650402000    # B
PEXPIRE rl:tb:user42 5000
HSET rl:tb:user42 tokens 0 ts 1758650402000    # C
PEXPIRE rl:tb:user42 5000
HSET rl:tb:user42 tokens 0 ts 1758650402000    # D, rejected, state still saved
PEXPIRE rl:tb:user42 5000

# Read
> HGETALL rl:tb:user42
1) "tokens"
2) "0"
3) "ts"
4) "1758650402000"
rl:tb:user42 (hash, TTL 5000 ms)
fieldvalue
tokens"0"
ts"1758650402000"

Retry in = (cost − tokens) / rate = (1 − 0) / 1 = 1 s.

Tradeoff: two fields per client, burst-friendly, and supports weighted requests through cost (an expensive endpoint can cost 5 tokens). This is what most production API gateways use.

Which to pick

AlgorithmRedis structureMemory per clientAccuracyBursts
Fixed windowString counter per bucket1 integerUp to 2× at bucket boundariesUncontrolled at edges
Sliding window logSorted set of timestampsO(limit)ExactNone beyond the limit
Sliding window counterTwo string counters2 integersClose approximationMostly smoothed
Token bucketHash with 2 fields2 fieldsExact average rateAllowed up to capacity

Wiring it into an app

Call the check once per incoming request, before any real work. It is a gate at the front of the request handler:

# request arrives
#   -> figure out client_id (user ID, API key, or IP address)
#   -> allow_sliding_log(client_id, limit, window_ms)
#        False -> return HTTP 429, stop
#        True  -> run the actual handler

Middleware covers every endpoint without repeating the check. With FastAPI:

from fastapi import FastAPI, Request
from fastapi.responses import JSONResponse

app = FastAPI()

LIMIT = 100          # requests
WINDOW_MS = 60_000   # per 60 seconds

@app.middleware("http")
async def rate_limit(request: Request, call_next):
    api_key = request.headers.get("X-API-Key")
    if api_key is not None:
        client_id = api_key
    else:
        client_id = request.client.host  # fall back to IP address

    allowed = allow_sliding_log(client_id, LIMIT, WINDOW_MS)
    if not allowed:
        return JSONResponse(
            status_code=429,
            content={"error": "rate limit exceeded"},
            headers={"Retry-After": "60"},
        )

    response = await call_next(request)
    return response
  • No background cleanup job. Each call trims its own old entries, and TTLs delete keys for idle clients.
  • Rejected requests are not recorded in the sliding window log. The script returns before ZADD, so hammering while blocked does not extend the lockout. To make blocked attempts count against abusive clients, move the ZADD above the limit check.
  • Check before expensive work. The point is to avoid spending database queries or compute on requests you will reject.
  • Precise Retry-After. The example sends the full window. For an exact value, read the oldest entry and compute oldest score + window − now, as in Card 3.
  • Different limits per route means different keys, such as rl:log:user42:search and rl:log:user42:upload, each checked in its own handler.

Production details

Atomicity
Never read, check, and write as separate round trips from the app. Use INCR, MULTI/EXEC transactions, or a Lua script.
Redis Cluster hash tags
In Redis Cluster, every key a script touches must live in the same hash slot. Scripts with one key are always fine. For two keys, wrap the shared part in braces, such as rl:sw:{user42}:29310840 and rl:sw:{user42}:29310839; Redis hashes only the text inside the braces, so both land in the same slot.
Failure mode
Decide what happens when Redis is unreachable: fail open (allow requests, favoring availability) or fail closed (reject, favoring protection). Put a short timeout on the Redis call either way.
Response headers
Return Retry-After and X-RateLimit-Remaining so clients can back off correctly. The token bucket script already returns the remaining tokens.
Script loading
SCRIPT LOAD caches a script and returns its Secure Hash Algorithm 1 (SHA-1) digest; EVALSHA then runs it by digest instead of resending the body. The register_script helper in redis-py does this automatically and reloads the script if Redis replies NOSCRIPT.
Hot keys
One very high-traffic client concentrates load on one Redis shard. For global limits (not per client), consider a local in-process limiter in front of Redis that syncs in batches.

Command reference

CommandDoesOn a missing keyCost
INCR keyAdds 1, returns the new valueTreats it as 0, returns 1O(1)
GET keyReads a string valueReturns nilO(1)
EXPIRE key sec [NX]Sets a relative TTL in secondsReturns 0O(1)
PEXPIRE key msSets a relative TTL in millisecondsReturns 0O(1)
PEXPIREAT key unix-msSets an absolute deadlineReturns 0O(1)
PTTL keyRemaining TTL in millisecondsReturns −2 (−1 means no TTL)O(1)
ZADD key score memberAdds a member or updates its scoreCreates the setO(log N)
ZCARD keyNumber of membersReturns 0O(1)
ZREMRANGEBYSCORE key min maxDeletes members with score in [min, max]Returns 0O(log N + M removed)
ZRANGE key start stop WITHSCORESReads members by position, lowest score firstReturns an empty listO(log N + M returned)
HSET key field value ...Sets hash fieldsCreates the hashO(1) per field
HMGET key field ...Reads hash fieldsReturns nilsO(1) per field
TIMEServer time as [seconds, microseconds]Not applicableO(1)
EVALSHA sha numkeys ...Runs a cached Lua scriptNOSCRIPT error if not loadedScript's own cost