Designing a Rate Limiter

Like explaining to a 5-year-old: Imagine a water fountain at school. If everyone rushes at once, there’s no water left for anyone. So the teacher says: “Each student gets 5 sips per hour.” That’s a rate limiter — it makes sure one person can’t use everything, so everyone gets a fair share.

Rate limiters are the bouncers of your API — they decide who gets in, at what speed, and when to say “come back later.” Building one correctly in a distributed environment is trickier than it looks.

Requirements

Functional

• Reject requests that exceed a threshold (e.g. 100 req/min per user)
• Return 429 Too Many Requests with a Retry-After header
• Support multiple limit tiers: per IP, per user, per API key, per endpoint

Non-Functional

• Low latency: limit checks must add < 5ms to every request
• Accuracy: shouldn’t allow bursts that violate limits by more than ~1%
• Distributed: must work across many app server instances
• Fault-tolerant: if the limiter fails, fail open (let traffic through) rather than blocking everyone

Algorithms

1. Fixed Window Counter

Count requests in a fixed time bucket (e.g. “minute 12:03”).

window_key = f"rl:{user_id}:{floor(now / 60)}"
count = INCR window_key
EXPIRE window_key 60
if count > limit: reject

Problem: A user can send 100 requests in the last second of minute 1, then 100 more in the first second of minute 2 — 200 requests in 2 seconds, double the limit.

2. Sliding Window Log

Store a sorted set of timestamps for each user.

ZADD rl:{user_id} now now
ZREMRANGEBYSCORE rl:{user_id} 0 (now - 60)
count = ZCARD rl:{user_id}
if count > limit: reject

Pros: perfectly accurate.
Cons: memory scales with request count, not user count. 100 req/min × 10M users = 1B entries.

3. Token Bucket (Recommended for most APIs)

The cookie jar analogy: You have a jar that holds 10 cookies. Every minute, someone adds 2 new cookies (up to the max of 10). Every time you take a cookie (make a request), one is removed. If the jar is empty, you wait. This lets you burst up to 10, but sustains at 2 per minute.

Each user has a token bucket. Tokens refill at a constant rate; each request consumes one.

def is_allowed(user_id: str, capacity: int, refill_rate: float) -> bool:
    key = f"tb:{user_id}"
    now = time.time()

    # Lua script for atomicity
    script = """
    local tokens = tonumber(redis.call('HGET', KEYS[1], 'tokens')) or tonumber(ARGV[1])
    local last   = tonumber(redis.call('HGET', KEYS[1], 'ts'))    or tonumber(ARGV[3])
    local rate   = tonumber(ARGV[2])
    local cap    = tonumber(ARGV[1])
    local now    = tonumber(ARGV[3])

    local elapsed = now - last
    tokens = math.min(cap, tokens + elapsed * rate)

    if tokens >= 1 then
        tokens = tokens - 1
        redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
        return 1
    end
    redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
    return 0
    """
    return bool(redis.eval(script, 1, key, capacity, refill_rate, now))

Pros: allows controlled bursting, smooth average rate.
Cons: two fields per user in Redis; slightly complex Lua script.

4. Sliding Window Counter (Best balance)

Hybrid of fixed window + sliding: estimate the sliding count using two adjacent windows.

current_window  = floor(now / 60)
previous_window = current_window - 1

curr_count = GET rl:{user}:{current_window}   or 0
prev_count = GET rl:{user}:{previous_window}  or 0

# Weight previous window by how far we are into the current one
elapsed_fraction = (now % 60) / 60.0
estimated = prev_count * (1 - elapsed_fraction) + curr_count

if estimated + 1 > limit: reject

Only 2 Redis keys per user. Accurate to within ~0.003% in practice (proven by Cloudflare).

Architecture: Where to Enforce

                ┌─────────────────────────────┐
Client ────────▶│  API Gateway / Edge Node    │  ← Layer 1: coarse IP-level limits
                └─────────────┬───────────────┘
                              │
                ┌─────────────▼───────────────┐
                │     Rate Limit Service      │  ← Layer 2: per-user/key limits
                │  (stateless, reads Redis)   │
                └─────────────┬───────────────┘
                              │
                ┌─────────────▼───────────────┐
                │      App Servers            │
                └─────────────────────────────┘
                              │
                        Redis Cluster
                    (rate limit counters)

Enforcing at the edge (API Gateway/CDN) handles floods before they hit your app servers. Enforcing at the service layer handles authenticated per-user limits.

Response Headers

Always return informative headers so clients can self-throttle:

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 73
X-RateLimit-Reset: 1718200800

HTTP/1.1 429 Too Many Requests
Retry-After: 27
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0

Distributed Coordination Problem

With 10 app servers, each checking Redis independently, you get a race condition: two servers can both read count = 99 and both allow the 100th request before either increments.

Solution: use Redis atomic operations. The Lua script above runs atomically on the Redis server — no race condition possible. Alternatively, use INCR which is inherently atomic.

For multi-region setups, accept eventual consistency: use local Redis per region with a small overage allowance (e.g. allow 110 req/min where 100 is the nominal limit).

Trade-offs & Decisions

Decision	Choice	Reason
Algorithm	Token bucket or sliding window counter	Balance between burst tolerance and accuracy
Storage	Redis (in-memory)	Sub-millisecond reads; TTL support built-in
Atomicity	Lua scripts	Single round-trip, no TOCTOU race
Failure mode	Fail open	Availability > strict enforcement; log & alert
Enforcement point	Both edge and service layer	Defense in depth

---

Rate limiting is one of those problems that looks trivial until you need it to work perfectly across 50 servers in 3 regions. The token bucket + Redis Lua atomic script is the sweet spot for most production APIs.