Build Redis-backed token-bucket rate limiter

Introduction

When your GenAI gateway gets hammered by a single client looping prompts in a tight retry loop, you can burn through your LLM inference budget in minutes and starve every other tenant of capacity. A Redis-backed token bucket gives you precise, distributed control over how many requests each user, API key, and IP can fire per second, with atomic check-and-decrement so two workers can never both let a request through on the same last token. By the end of this lesson you'll be able to configure per-tier token buckets, run an atomic Redis Lua script for race-free token consumption, and wire the limiter into FastAPI middleware that gates every request across multiple identity dimensions.

Key Terminology

• Token bucket — algorithm storing up to max_tokens tokens that refill at a constant rate; each request consumes one and an empty bucket triggers rejection. Defines the sustained rate and burst budget the limiter enforces.
• Refill rate — tokens added per second up to the bucket's capacity, expressed in this lesson as refill_rate. Sets the steady-state allowance for each client identity.
• Atomic Lua script — Lua executed by Redis without interleave across commands or clients. Required so the check-and-decrement of a single bucket is race-free across multiple FastAPI workers hitting the same Redis instance.
• Rate-limit dimension — the identity axis (per-user, per-key, per-IP) along which a bucket is keyed. Lets the middleware enforce different ceilings on different identity classes for the same request simultaneously.
• Retry-After — HTTP 429 response header value in seconds, derived from the bucket deficit divided by the refill rate. Tells clients when they may retry instead of hammering blindly.

Concepts

Operational Considerations for Production

When deploying this rate limiter alongside the rest of your gateway stack—request validation, response caching, guardrails, and health probes—keep these patterns in mind:

• Redis Sentinel or Cluster: A single Redis instance is a single point of failure. Use Redis Sentinel for automatic failover or Redis Cluster for horizontal sharding. The Lua script works identically on both topologies because it operates on a single key.
• Graceful degradation: If Redis becomes unreachable, the middleware should allow requests through (open-circuit) rather than rejecting all traffic. Set a configurable fallback policy—most production gateways prefer temporary over-admission to total denial of service.
• Key expiry hygiene: The TTL calculation in the Lua script (max_tokens / refill_rate * 2) ensures keys expire after a period proportional to the bucket size. Without TTL, abandoned client keys accumulate indefinitely, eventually consuming significant Redis memory.
• Monitoring integration: Emit rate-limit events to your audit trail (the same system used by gateway guardrails for PII detection logging). Track rejection rates per tier and per dimension to detect abuse patterns and calibrate limits.
• Kubernetes readiness coupling: Your readiness probe should verify Redis connectivity. If the rate limiter's Redis backend is down, the pod should be marked unready so the Kubernetes service stops routing traffic to it, preventing requests from bypassing rate limiting entirely.

Code Walkthrough

Why Token Bucket Over Alternatives

Before writing code, understand why the token-bucket algorithm dominates gateway rate limiting at scale. Three algorithms compete in practice:

• Fixed Window: Counts requests in discrete time windows. Simple but suffers from boundary bursting—a client can double the intended rate across a window boundary.
• Sliding Window Log: Tracks every request timestamp in a rolling window. Accurate but requires O(n) storage per client.
• Token Bucket: Maintains a bucket that refills at a constant rate up to a maximum capacity. Each request consumes tokens; empty bucket means rejection. Storage is O(1) per client.

The token bucket maps cleanly to GenAI usage: a developer submits prompts in bursts, then pauses to review outputs.

This flowchart maps the request lifecycle through a token-bucket rate limiter that resolves client identity three ways—User ID, API Key, or Client IP—each routing to its own bucket via Lookup User Bucket, Lookup Key Bucket, or Lookup IP Bucket. A single Execute Lua Script node atomically checks and decrements tokens, branching to either Forward to Guardrails Layer on success or Return 429 + Retry-After when the bucket drains, ensuring upstream guardrails and response caching only process authenticated, rate-compliant traffic.

Loading diagram...

The diagram above illustrates how every request passes through identity resolution before hitting the atomic Lua script in Redis. Notice that the rate limiter sits between request validation (which has already sanitized the input) and the guardrails layer (which scans content for safety).

Configuring, Consuming, and Wiring the Limiter

A well-designed rate limiter separates configuration from enforcement. A TokenBucket Pydantic model defines per-client bucket parameters — max_tokens (capacity, validated gt=0), refill_rate (tokens per second, also gt=0), current_tokens, and last_refill_ts — while a RateLimitConfig model maps each tier and identity dimension to its own bucket. This separation lets you adjust limits per tier without modifying the core algorithm: free-tier users get max_tokens=10 at refill_rate=0.17 (≈10 req/min), standard users max_tokens=60 at refill_rate=1.0, and enterprise keys max_tokens=1500 at refill_rate=25.0 for per-key traffic. A key_prefix of "rl:" keeps rate-limit keys in Redis from colliding with cache keys used by the content-addressable response caching layer.

The critical correctness requirement for distributed rate limiting is atomicity. If two requests arrive simultaneously for the same client, both might read the bucket as having one remaining token, both decrement it, and both proceed—exceeding the limit. Redis Lua scripts solve this because Redis executes them atomically: no other command can interleave during script execution. The RateLimiter class below encapsulates the Redis connection, registers the Lua script on initialization, and exposes a consume_token method that performs the refill calculation and consumption check in a single round trip. The RateLimitMiddleware then wires this limiter into FastAPI's middleware stack, positioned after request validation and before the guardrails layer. It resolves the client's tier, checks all three dimensions—user, key, and IP—in parallel, and rejects with the longest Retry-After across all dimensions if any bucket is exhausted. This prevents a scenario where a single API key shared across many users bypasses the per-user limit.

Code snippetpython
1import asyncio
2import time
3from enum import Enum
4from typing import Optional
5import redis.asyncio as redis
6from pydantic import BaseModel, Field
7from fastapi import Request, Response
8from starlette.middleware.base import BaseHTTPMiddleware
9from starlette.responses import JSONResponse
10
11class RateLimitTier(str, Enum):
12    FREE = "free"
13    STANDARD = "standard"
14    ENTERPRISE = "enterprise"
15
16class TokenBucket(BaseModel):
17    max_tokens: float = Field(gt=0)
18    refill_rate: float = Field(gt=0)
19    current_tokens: float = 0.0
20    last_refill_ts: float = 0.0
21
22class TierLimits(BaseModel):
23    per_user: TokenBucket
24    per_key: TokenBucket
25    per_ip: TokenBucket
26
27class RateLimitConfig(BaseModel):
28    key_prefix: str = "rl:"
29    tiers: dict[RateLimitTier, TierLimits]
30
31LUA_TOKEN_BUCKET = """
32local key = KEYS[1]
33local max_tokens = tonumber(ARGV[1])
34local refill_rate = tonumber(ARGV[2])
35local now = tonumber(ARGV[3])
36local requested = tonumber(ARGV[4])
37local ttl_seconds = tonumber(ARGV[5])
38
39local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
40local tokens = tonumber(bucket[1])
41local last_refill = tonumber(bucket[2])
42
43if tokens == nil then
44    tokens = max_tokens
45    last_refill = now
46end
47
48local elapsed = now - last_refill
49local new_tokens = math.min(max_tokens, tokens + (elapsed * refill_rate))
50
51if new_tokens >= requested then
52    new_tokens = new_tokens - requested
53    redis.call('HSET', key, 'tokens', new_tokens, 'last_refill', now)
54    redis.call('EXPIRE', key, ttl_seconds)
55    return {1, math.floor(new_tokens * 1000)}
56else
57    local deficit = requested - new_tokens
58    local retry_after = math.ceil(deficit / refill_rate)
59    return {0, retry_after}
60end
61"""
62
63class RateLimiter:
64    def __init__(self, redis_client: redis.Redis, config: "RateLimitConfig"):
65        self._redis = redis_client
66        self._config = config
67        self._script: Optional[str] = None
68
69    async def initialize(self) -> None:
70        self._script = self._redis.register_script(LUA_TOKEN_BUCKET)
71
72    async def consume_token(
73        self, identity: str, dimension: str,
74        bucket_cfg: "TokenBucket", tokens: int = 1
75    ) -> tuple[bool, float]:
76        key = f"{self._config.key_prefix}{dimension}:{identity}"
77        ttl = int(bucket_cfg.max_tokens / bucket_cfg.refill_rate) * 2
78        now = time.time()
79
80        result = await self._script(
81            keys=[key],
82            args=[
83                bucket_cfg.max_tokens,
84                bucket_cfg.refill_rate,
85                now,
86                tokens,
87                ttl,
88            ],
89        )
90
91        allowed = result[0] == 1
92        remaining_or_retry = result[1] / 1000.0 if allowed else float(result[1])
93        return allowed, remaining_or_retry
94
95class RateLimitMiddleware(BaseHTTPMiddleware):
96    def __init__(self, app, limiter: RateLimiter, config: RateLimitConfig):
97        super().__init__(app)
98        self.limiter = limiter
99        self.config = config
100
101    async def dispatch(self, request: Request, call_next) -> Response:
102        tier = self._resolve_tier(request)
103        tier_cfg = self.config.tiers[tier]
104        identities = {}
105
106        user_id = request.state.__dict__.get("user_id")
107        api_key = request.headers.get("X-API-Key", "")
108        client_ip = request.client.host if request.client else "unknown"
109
110        if user_id:
111            identities["per_user"] = (user_id, tier_cfg.per_user)
112        if api_key:
113            identities["per_key"] = (api_key, tier_cfg.per_key)
114        identities["per_ip"] = (client_ip, tier_cfg.per_ip)
115
116        results = await asyncio.gather(*[
117            self.limiter.consume_token(identity, dim, bucket_cfg)
118            for dim, (identity, bucket_cfg) in identities.items()
119        ])
120
121        max_retry = 0.0
122        for (allowed, value), dim in zip(results, identities.keys()):
123            if not allowed:
124                max_retry = max(max_retry, value)
125
126        if max_retry > 0:
127            return JSONResponse(
128                status_code=429,
129                content={"error": "rate_limit_exceeded", "retry_after": max_retry},
130                headers={"Retry-After": str(int(max_retry))},
131            )
132
133        response = await call_next(request)
134        first_dim = next(iter(identities.keys()))
135        first_allowed, first_remaining = results[0]
136        response.headers["X-RateLimit-Remaining"] = str(int(first_remaining))
137        response.headers["X-RateLimit-Limit"] = str(
138            getattr(tier_cfg, first_dim).max_tokens
139        )
140        return response
141
142    def _resolve_tier(self, request: Request) -> RateLimitTier:
143        tier_claim = request.state.__dict__.get("tier")
144        if tier_claim and tier_claim in RateLimitTier.__members__:
145            return RateLimitTier(tier_claim.lower())
146        return RateLimitTier.FREE

• Config models (RateLimitTier, TokenBucket, TierLimits, RateLimitConfig): The gt=0 validators prevent misconfiguration where a zero-rate bucket would permanently block a client. Tier limits are looked up via self.config.tiers[tier] in the middleware.
• Lua script (ARGV[1-5]): Accepts the bucket's maximum capacity, refill rate, current Unix timestamp, number of tokens to consume, and a TTL for automatic key expiry. Passing the timestamp from the application (rather than using Redis's TIME command) ensures consistency when the application and Redis server clocks diverge slightly. HMGET retrieves the token count and last refill timestamp in a single command; Redis hashes store bucket state compactly with two fields per client identity.
• RateLimiter.consume_token: Constructs a namespaced Redis key (e.g., rl:per_user:user_42), calculates a safe TTL, and invokes the Lua script. The return tuple (allowed, value) encodes either the remaining token count (on success) or the retry-after seconds (on rejection). Using redis.asyncio is essential for non-blocking operation within FastAPI's event loop—synchronous Redis calls would block the entire worker process.
• RateLimitMiddleware.dispatch: Called for every inbound request. It first resolves the client's tier using JWT claims or API key metadata, then builds a dictionary of identity dimensions and checks them concurrently via asyncio.gather.
• _resolve_tier: Checks the request state (populated by authentication middleware during request validation) for a tier claim. If the claim is missing or invalid, it defaults to RateLimitTier.FREE—the most restrictive tier. This fail-closed behavior is critical for security: a misconfigured authentication layer should never grant elevated rate limits.

Do's and Don'ts

Do's

1. ✓Do execute the refill calculation, token comparison, and HSET of updated bucket state together inside LUA_TOKEN_BUCKET — Redis runs Lua scripts atomically, so no FastAPI worker can interleave a read between another worker's read and write; any split into separate Python GET/SET calls breaks this guarantee and lets two concurrent workers both see the last available token and both proceed.
2. ✓Do check all three identity dimensions — per-user, per-key, and per-IP — on every request and return the largest Retry-After across any exhausted bucket — a shared API key checked in isolation can still exhaust the per-user ceiling while appearing compliant at the key level, so only the cross-dimension maximum enforces the true limit.
3. ✓Do namespace every rate-limit key under RateLimitConfig.key_prefix ("rl:") and keep that prefix distinct from the response-cache namespace — when the token bucket's HSET and the content-addressable cache layer write to the same key space, one clobbers the other's data structure, producing corrupted bucket state or stale cache reads.

Don'ts

1. ✗Don't implement the refill-and-consume logic as separate Python GET/SET calls around Redis — two concurrent workers will both read current_tokens = 1, both decide the bucket is non-empty, and both decrement to 0, allowing two requests through on a single remaining token and defeating the distributed limiter entirely.
2. ✗Don't create one bucket key per tier without scoping it to the client identity — rate-limit keys must be formed as rl:user:<id>, rl:key:<hash>, and rl:ip:<addr> so a single free-tier user's burst drains only their own bucket and not the token supply for every other client sharing the same RateLimitTier.FREE configuration.
3. ✗Don't omit the gt=0 constraint on max_tokens and refill_rate in the TokenBucket Pydantic model — a zero refill_rate produces a divide-by-zero when computing ceil(deficit / refill_rate) for the Retry-After header, and a zero max_tokens makes every bucket permanently exhausted from the very first request.