Rate Limiting

Without rate limiting:
  Client sends 10,000 req/sec → Server crashes → All users affected

With rate limiting:
  Client sends 10,000 req/sec → Rate limiter → 429 Too Many Requests
  Server stays healthy → Other users unaffected

Bucket: capacity C tokens, refills at rate R tokens/sec

  ┌─────────────────────┐
  │  ● ● ● ● ● ● ● ●  │  ← Bucket with tokens
  │  ● ● ● ● ●         │
  └─────────────────────┘
       ↑ Each request consumes 1 token
       If empty → reject (HTTP 429)

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate
        self.last_refill = time.time()
    
    def allow(self):
        now = time.time()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now
        
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Requests enter a FIFO queue → drained at fixed rate R

  ┌─────────────────────┐
  │  → → → → → → → →   │  Queue
  └────────┬────────────┘
           │ Fixed rate drain
           ▼
     Smooth output

Window: 12:00-12:01    Window: 12:01-12:02
┌──────────────────┐   ┌──────────────────┐
│ Count: 99        │   │ Count: 100       │
│ Limit: 100       │   │ Limit: 100       │
└──────────────────┘   └──────────────────┘

Problem: 99 requests at 11:59:59 + 100 at 12:00:01
         = 199 requests in 2 seconds (2x burst!)

Redis sorted set:
ZADD rate_limit:user123 <timestamp> <request_id>
ZREMRANGEBYSCORE rate_limit:user123 0 <now - window>
ZCARD rate_limit:user123  →  count

effective_count = current_window_count + 
                  previous_window_count × overlap_percentage

Example: limit=100/min, current=30, previous=70, 40% elapsed
  effective = 30 + 70 × (1 - 0.4) = 30 + 42 = 72 → Allow

TAT = max(TAT, now) + increment
If TAT - now <= tolerance: allow
Else: reject

10 servers, each with local counter (limit: 100/min)
  Server 1: allows 100 requests from user
  Server 2: allows 100 requests from user
  ...
  Server 10: allows 100 requests from user
  
  Total: 1000 requests/min (10x intended limit!)

-- Token bucket in Redis (atomic Lua script)
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
 
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
 
-- Refill tokens
local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * rate)
 
if tokens >= requested then
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / rate) * 2)
    return 1  -- allow
else
    return 0  -- reject
end

Tier 1: Local token bucket (in-memory)
  - Each gateway borrows a chunk of tokens from Redis (e.g., 10 at a time)
  - Consumes locally until chunk exhausted
  - Borrows again from Redis

Tier 2: Global Redis token bucket
  - Authoritative token count
  - Issues chunks to gateways on demand

Result: Reduces Redis traffic by 10x, accuracy within 6%

Gateway 1: borrows 10 tokens → serves 10 requests locally → borrows again
Gateway 2: borrows 10 tokens → serves 10 requests locally → borrows again
Gateway 3: borrows 10 tokens → serves 8 requests → returns 2 unused

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

{
  "error": {
    "code": "RATE_LIMITED",
    "message": "Too many requests. Try again in 30 seconds."
  }
}