Build rate limiting with Redis sorted sets

Introduction

Engineers often learn the hard way that GenAI endpoints are fundamentally different from ordinary REST surfaces — each request burns upstream tokens that cost real money, and a single misbehaving client can exhaust a monthly quota in minutes or push the upstream provider into returning 429 for every tenant, not just the offender. Without a rate limiter there is no fair-use story, no tier differentiation, and no protection against the runaway loop that always appears. This lesson teaches you to implement a sliding-window rate limiter using Redis sorted sets — including the atomic Lua script that prevents race conditions, the HTTP 429 response contract with Retry-After and X-RateLimit-Remaining headers, and the tier-based scaling primitive that lets free, pro, and enterprise budgets share the same algorithm.

Key Terminology

• Sliding-window log — exact-count rate-limit algorithm that records each request's timestamp and trims+counts the trailing window on every check; matters here because it eliminates the boundary-cheating that lets a fixed-window counter pass 2 × limit in a two-second straddle.
• Redis sorted set (ZSET) — keyed collection of (score, member) pairs ordered by score; the limiter uses millisecond timestamps as scores and UUID4s as members so the four-op trim+add+count sequence runs in O(log N) per request.
• Atomic Lua script — multi-command Redis snippet that executes under a single server-side lock; matters because pipelines and MULTI/EXEC still let concurrent connections interleave, so only Lua prevents two requests from both passing ZCARD and letting limit + 1 through.
• Tier — named budget bucket (free, pro, enterprise) mapping a user to per-minute and per-day request limits; matters because switching tiers must change only the budget consulted, never the limiter primitive, key shape, or Lua script.

Concepts

Why rate limit GenAI endpoints

A typical REST API rate-limit budget is shaped by CPU and database load. GenAI endpoints have three additional pressures that make rate limiting non-optional:

1. Token-based costs. Each completion translates to a billable token count. A pathological client looping at 50 RPS against a gpt-4o endpoint can burn hundreds of dollars per hour. Rate limiting is the first cost-control gate.
2. Fair-use across tiers. Free-tier users sharing the same provider key as paying customers will starve the paying customers if they are not throttled. The limiter is what prevents one tenant from consuming the headroom another tenant has paid for.
3. Upstream provider protection. Every LLM provider has its own rate limits — OpenAI's TPM/RPM, Anthropic's token-per-minute caps, Gemini's quota system. If you forward bursts faster than your upstream allows, the provider returns 429 and your error rate spikes for every user, not just the offender. Your limiter must keep traffic below the smallest upstream cap.

The right algorithm depends on which of those pressures dominates and how much accuracy you need at the window boundary.

The sorted-set sliding window: data shape

Each tenant gets its own sorted set keyed by user (and optionally route, when you want per-endpoint limits):

• Key: ratelimit:{user_id}:{window_seconds} — for example ratelimit:user_8421:60 for the 60-second sliding window for user 8421.
• Score: the unix timestamp in milliseconds of the request. Millisecond resolution matters because at high RPS multiple requests per second are routine.
• Member: a unique request id (UUID4). The member must be unique even at the same millisecond, otherwise ZADD would silently overwrite and undercount.

On every request the limiter performs four operations against that key:

1. ZREMRANGEBYSCORE key 0 (now - window_ms) — drop entries that fell out of the trailing window.
2. ZADD key {now_ms} {request_uuid} — record this request.
3. ZCARD key — count remaining entries (including the one we just added).
4. EXPIRE key {window_seconds + 1} — let Redis garbage-collect the key when the user goes idle, so we do not leak keys for one-off visitors.

If ZCARD exceeds the tenant's quota, the request is rejected with HTTP 429. The four operations must be atomic — two concurrent requests that both pass ZCARD but should not have is the classic concurrency bug here.

The diagram below traces the decision path inside the Lua script for a single request, showing where the allow and reject branches diverge:

Operating discipline

• Always use a Lua script (or MULTI/EXEC) for the four-op sequence. Doing them as separate commands races under load — two requests can both pass ZCARD and both ZADD, and you have just let through limit + 1.
• Score in milliseconds, not seconds. At any non-trivial RPS the second-resolution tie causes member collisions and undercounts. UUID members plus millisecond scores are the safe combination.
• Set EXPIRE on every allow path. Without it, sorted sets for one-time visitors accumulate forever. With it, idle keys evict themselves and your memory footprint stays proportional to active tenants, not lifetime tenants.
• Order windows shortest-first when checking. Rejecting on the per-minute limit before the per-day limit minimizes Redis round-trips on the hot rejection path and surfaces the correct Retry-After.
• Return Retry-After honestly — based on the oldest entry in the window. A flat Retry-After: 60 after every rejection trains clients to either over-wait or to ignore the header entirely. The Lua script computes the exact moment the oldest entry expires; surface that.
• Surface X-RateLimit-Remaining on success responses too. Clients that see the remaining count drop will self-throttle. Only exposing the limit on rejection means clients only learn about it by tripping it.
• Keep tier definitions in code or config, not per-user database rows. Looking up the tier costs one cheap field; recomputing per-user limits per request adds no value over a tier table and bloats the schema.
• Have a kill switch. A RATE_LIMIT_DISABLED=true env var or a feature flag that makes check always return (True, limit, 0) is essential when Redis is unhealthy and you would rather serve un-throttled traffic than 500 every request. Pair it with an alert so it cannot be left on by accident.

Exit criteria

You have satisfied this goal when you can demonstrate all of the following against a running Redis:

1. Atomic check-and-increment. A single RateLimiter.check(user_id, limit, window_seconds) call performs ZREMRANGEBYSCORE + ZCARD + (on allow) ZADD + EXPIRE in one server-side Lua execution and returns (allowed, remaining, retry_after_s).
2. Sliding-window correctness under load. With limit=10, window_seconds=60, firing 20 concurrent requests for the same user_id produces exactly 10 allows and 10 rejects — never 11 allows and never limit + 1 letting through. Re-running 61 seconds later allows another 10.
3. Honest Retry-After. On a rejection, the returned retry_after_s equals the number of seconds (rounded up, minimum 1) until the oldest entry in the sorted set falls out of the window — not a flat constant.
4. HTTP 429 contract. The FastAPI dependency rejects with status 429 and headers Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining: 0, and X-RateLimit-Window indicating which window tripped (minute or day).
5. Tiered scaling without algorithm changes. Switching user.tier from free to pro to enterprise changes only the budget consulted in TIER_LIMITS; the limiter primitive, key shape, and Lua script are unchanged.
6. Shortest-window-first evaluation. When both per-minute and per-day windows would reject, the response surfaces the per-minute window's Retry-After (the soonest retry), and the per-day Redis call is skipped on the rejection path.
7. Idle-key reclamation. After a user stops issuing requests, their ratelimit:{user_id}:{window_seconds} key disappears from Redis within window_seconds + 1 seconds (verifiable via TTL then EXISTS).
8. Kill-switch behavior. With RATE_LIMIT_DISABLED=true, check returns (True, limit, 0) for every call and performs no Redis writes.

Code Walkthrough

Building on the sorted-set data shape from the Concepts section, we can now implement the atomic check-and-increment pattern that makes the sliding window correct under concurrent load.

The Lua script below runs atomically on the Redis server, executing the trim → count → conditional-add sequence without letting a concurrent request slip between steps. The RateLimiter class registers the script once and calls it via EVALSHA on every subsequent request, keeping each check to a single network round-trip:

Code snippetpython
1import time
2import uuid
3from typing import Tuple
4import redis
5
6# KEYS[1] = ratelimit key  (e.g. ratelimit:user123:60)
7# ARGV[1] = now_ms  ARGV[2] = window_ms  ARGV[3] = limit
8# ARGV[4] = request_uuid  ARGV[5] = expire_seconds
9RATE_LIMIT_LUA = """
10local key    = KEYS[1]
11local now    = tonumber(ARGV[1])
12local window = tonumber(ARGV[2])
13local limit  = tonumber(ARGV[3])
14local member = ARGV[4]
15local ttl    = tonumber(ARGV[5])
16
17redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
18local count = redis.call('ZCARD', key)
19if count >= limit then
20    local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
21    local retry_after_ms = (tonumber(oldest[2]) + window) - now
22    return {0, count, retry_after_ms}
23end
24redis.call('ZADD', key, now, member)
25redis.call('EXPIRE', key, ttl)
26return {1, count + 1, 0}
27"""
28
29class RateLimiter:
30    """Sliding-window rate limiter backed by Redis sorted sets."""
31
32    def __init__(self, redis_url: str = "redis://localhost:6379/0"):
33        self.client = redis.Redis.from_url(redis_url, decode_responses=True)
34        self._script = self.client.register_script(RATE_LIMIT_LUA)
35
36    def check(
37        self, user_id: str, limit: int, window_seconds: int
38    ) -> Tuple[bool, int, int]:
39        key = f"ratelimit:{user_id}:{window_seconds}"
40        now_ms = int(time.time() * 1000)
41        window_ms = window_seconds * 1000
42        ttl = window_seconds + 1
43
44        allowed, count, retry_after_ms = self._script(
45            keys=[key],
46            args=[now_ms, window_ms, limit, str(uuid.uuid4()), ttl],
47        )
48        remaining = max(0, limit - count)
49        retry_after_s = max(1, (retry_after_ms + 999) // 1000) if not allowed else 0
50        return bool(allowed), remaining, retry_after_s

ZREMRANGEBYSCORE trims every timestamp older than now - window, keeping the set to the trailing window only. ZCARD reads the current occupancy — the exact request count with no boundary-cheating error. When the count is already at the limit, ZRANGE WITHSCORES fetches the oldest timestamp and computes when it will slide out of the window; that becomes the Retry-After value. Only on the allow path does the script call ZADD and EXPIRE, so a rejected request never extends the key's TTL and accidentally penalises the user further.

With RateLimiter defined, a FastAPI dependency wires in the tier limits and emits the standard headers clients depend on:

Code snippetpython
1from fastapi import HTTPException, Request
2
3TIER_LIMITS = {
4    "free":       {"per_minute": 5,   "per_day": 100},
5    "pro":        {"per_minute": 60,  "per_day": 5_000},
6    "enterprise": {"per_minute": 600, "per_day": 100_000},
7}
8
9_limiter = RateLimiter()
10
11def rate_limit(request: Request, tier: str = "free") -> None:
12    limits = TIER_LIMITS.get(tier, TIER_LIMITS["free"])
13    user_id = request.state.user_id  # set by auth middleware
14
15    for window_seconds, budget_key in [(60, "per_minute"), (86400, "per_day")]:
16        allowed, remaining, retry_after = _limiter.check(
17            user_id=user_id,
18            limit=limits[budget_key],
19            window_seconds=window_seconds,
20        )
21        if not allowed:
22            raise HTTPException(
23                status_code=429,
24                detail="Rate limit exceeded",
25                headers={
26                    "Retry-After": str(retry_after),
27                    "X-RateLimit-Limit": str(limits[budget_key]),
28                    "X-RateLimit-Remaining": "0",
29                    "X-RateLimit-Window": (
30                        "minute" if budget_key == "per_minute" else "day"
31                    ),
32                },
33            )

Switching a user from free to pro changes only which budget map entry is looked up — the Lua script, the key shape, and the Redis sorted-set structure stay identical across all tiers.

Confirm that firing requests beyond the per-minute budget returns HTTP 429 with a non-zero Retry-After header, and that the limiter allows traffic again once enough time has elapsed for the oldest sorted-set members to slide out of the window.

Do's and Don'ts

Now that you have worked through the implementation, the practices below separate a durable approach from a fragile one.

Do's

1. ✓Do run the trim → count → conditional-add sequence inside a single Lua script loaded via register_script/EVALSHA — executing these three Redis calls atomically prevents concurrent requests from reading a stale count between the ZREMRANGEBYSCORE and ZCARD steps, which would allow bursts to exceed the limit under load.
2. ✓Do compute Retry-After from ZRANGE ... WITHSCORES on the oldest sorted-set member — calculating (oldest_timestamp + window_ms) - now_ms gives clients the exact milliseconds until the window opens again, rather than forcing them to guess or poll.
3. ✓Do separate the per-minute and per-day budgets into two independent RateLimiter.check calls using distinct key shapes (ratelimit:{user_id}:60 vs ratelimit:{user_id}:86400) — this lets free, pro, and enterprise tiers share the same Lua script and sorted-set algorithm while enforcing different budget maps from TIER_LIMITS without any branching inside Redis.

Don'ts

1. ✗Don't call ZADD on a rejected request — the Lua script intentionally skips ZADD and EXPIRE when count >= limit, so adding those calls for logging or debugging would reset the key's TTL and silently extend the penalty window for a user who is already being throttled.
2. ✗Don't perform the ZREMRANGEBYSCORE/ZCARD/ZADD sequence as separate round-trip Python calls — splitting the Lua script into discrete client.zremrangebyscore() + client.zcard() + client.zadd() calls reintroduces the race condition the atomic script exists to close, making the limiter unsound under any concurrency.
3. ✗Don't use a fixed-window counter (e.g., a Redis INCR on a key that expires at the top of the minute) as a drop-in replacement for this sorted-set design — fixed windows allow up to 2×limit requests at window boundaries (burst at the end of one window plus burst at the start of the next), exactly the problem the sliding-window ZREMRANGEBYSCORE trim is designed to eliminate.