Rate Limiting¶

Prerequisites: Reliability Overview

Why This Exists¶

Without rate limiting: - One misbehaving client can exhaust server resources, degrading service for everyone - A DDoS attack can bring down your entire system - Runaway scripts can generate millions of API calls

Rate limiting ensures fairness (everyone gets their share), stability (the system doesn't overload), and economics (you don't serve unlimited free requests).

Mental Model¶

Think of a rate limiter as a token bucket at the entrance of a nightclub. The club issues 10 tokens per second. Each person needs 1 token to enter. When tokens run out, people wait or leave.

Architecture¶

graph LR
    C[Client] -->|Request| RL{Rate Limiter}
    RL -->|Tokens available| S[Service]
    RL -->|No tokens: 429| C
    RL -->|Check/Update| R[(Redis\nCounters)]
    style RL fill:#1565c0,color:#fff
    style R fill:#b71c1c,color:#fff

Interactive Simulation¶

Try: Inject a burst of 200 requests. Observe how token bucket handles it vs fixed window.

Algorithms¶

1. Token Bucket¶

Bucket capacity: 20 tokens
Refill rate: 10 tokens/second

Every second: add 10 tokens (up to max 20)
Each request: consume 1 token
If no tokens: reject with 429

import time
import threading

class TokenBucket:
    def __init__(self, rate: float, capacity: int):
        self.rate = rate          # tokens per second
        self.capacity = capacity  # max tokens
        self.tokens = capacity    # start full
        self.last_refill = time.time()
        self.lock = threading.Lock()

    def allow(self) -> bool:
        with self.lock:
            now = time.time()
            elapsed = now - self.last_refill
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.rate
            )
            self.last_refill = now

            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

# Usage
limiter = TokenBucket(rate=10, capacity=20)
if limiter.allow():
    process_request()
else:
    return Response(status=429, headers={"Retry-After": "0.1"})

Best for: Smoothing bursty traffic while allowing controlled bursts.

2. Leaky Bucket¶

A leaky bucket drains at a constant rate. Requests enter the bucket; they leave at the drain rate. Burst capacity = bucket depth. If the bucket is full, new requests are dropped (or queued until they would overflow).

Bucket depth: 20
Drain rate: 10 req/s (constant)

Burst of 50:
  20 fill the bucket
  30 rejected
  Output never exceeds 10/s — the leak is the rate

Token bucket vs leaky bucket: token bucket allows a burst up to capacity, then limits to the refill rate. Leaky bucket smooths to a constant output; the burst is only how much you can queue before drop.

3. Fixed Window Counter¶

Window: 1 second
Limit: 10 requests per window

[00:00.000 - 00:01.000]: 10 requests allowed
[00:01.000 - 00:02.000]: counter resets → 10 more allowed

Problem: A client can send 10 requests at 00:00.999 and 10 more at 00:01.001 — 20 requests in 2ms, 2× the rate limit.

import redis
import time

def allow_fixed_window(user_id: str, limit: int = 10) -> bool:
    r = redis.Redis()
    window = int(time.time())  # current second
    key = f"rate:{user_id}:{window}"

    count = r.incr(key)
    if count == 1:
        r.expire(key, 2)  # expire after 2 windows
    return count <= limit

4. Sliding Window Log¶

Track exact timestamps of recent requests:

def allow_sliding_window(user_id: str, limit: int = 10, window_sec: int = 1) -> bool:
    r = redis.Redis()
    now = time.time()
    key = f"rate_log:{user_id}"

    pipe = r.pipeline()
    pipe.zremrangebyscore(key, 0, now - window_sec)
    pipe.zcard(key)
    count = pipe.execute()[1]
    if count >= limit:
        return False  # rejected traffic is not ZADD'd
    pipe = r.pipeline()
    pipe.zadd(key, {str(now): now})
    pipe.expire(key, window_sec + 1)
    pipe.execute()
    return True

Pros: Accurate, no boundary spike issue Cons: Memory-intensive (stores every request timestamp)

5. Sliding Window Counter (Approximate)¶

Combines accuracy with efficiency using two fixed windows:

Current window count + Previous window count × (remaining fraction of previous window)

Example:
- Limit: 100/minute
- Previous window (last minute): 80 requests
- Current window (this minute): 30 requests, 25 seconds elapsed
- Fraction of current window elapsed: 25/60 = 0.42

Estimated rate = 30 + 80 × (1 - 0.42) = 30 + 46.4 = 76.4 → under limit ✓

Distributed Rate Limiting¶

For a service running across multiple pods/servers, each pod maintaining its own counter doesn't work — 10 pods with a limit of 100/pod = 1000 effective requests.

Redis-Based Distributed Rate Limiting¶

import redis
import time

r = redis.Redis(host='redis-cluster')

def allow_distributed(user_id: str, limit: int = 100) -> bool:
    key = f"rate:{user_id}:{int(time.time())}"

    # Atomic increment + expire using Lua script
    script = """
    local current = redis.call('INCR', KEYS[1])
    if current == 1 then
        redis.call('EXPIRE', KEYS[1], 2)
    end
    return current
    """
    count = r.eval(script, 1, key)
    return count <= limit

Why Lua? INCR is already atomic — two requests cannot both "see count=0." The real race is INCR without EXPIRE: if the process dies after INCR and before EXPIRE, the key never expires and the counter is stuck forever. The Lua script makes INCR+EXPIRE one server-side step.

Architecture: Rate Limiter in API Gateway¶

graph TD
    C1[Client] --> AG[API Gateway\nRate Limiter]
    C2[Client] --> AG
    C3[Client] --> AG
    AG -->|Check limit| R[(Redis Cluster\nCounters)]
    AG -->|Pass| S1[Service A]
    AG -->|Pass| S2[Service B]
    AG -->|429 Too Many Requests| C1

Levels of rate limiting: 1. IP-based: prevent DDoS (coarse, can affect NAT users) 2. User/API key: per-customer limits 3. Endpoint: different limits for different APIs (/search vs /checkout) 4. Tenant: large tenant limits separate from small tenant limits

Failure Modes¶

Rate Limiter Redis Failure¶

• Behavior depends on policy: fail-open (allow all traffic) vs fail-closed (deny all traffic)
• Production choice: Fail-open — a brief period of unthrottled traffic is better than complete service outage
• Detection: Redis connectivity metric; alert when rate limiter is in fail-open mode

Retry Storms Amplified by Rate Limiting¶

• Client gets 429 → retries immediately → 429 → retries → ... → amplifies load
• Fix: Clients must implement exponential backoff with jitter; include Retry-After header in 429 response

Thundering Herd at Window Reset¶

• Fixed window: all throttled clients retry exactly when the window resets → burst at window boundary
• Fix: Sliding window, or add jitter to Retry-After

Production Debugging¶

Symptom: High 429 rate for a specific customer

1. Check customer's actual request rate
   → rate_limiter_requests metric, filter by customer_id
2. Check what limit is configured
   → Rate limit config service / Redis key
3. Check if limit is appropriate
   → Is customer on right tier? Did usage legitimately grow?
4. Check for retry amplification
   → Is the customer's client retrying aggressively on 429?
5. Check for misconfiguration
   → Is rate limit applied per-instance instead of globally?

Headers to include in 429 response:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 0
  X-RateLimit-Reset: 1704067200
  Retry-After: 45

Trade-offs¶

Interview Questions¶

Key Takeaways¶