Skip to main content
Cloud & AI Hub
Browse
Glossary AI Directory Playgrounds Models Prompts Explainers Strategy Matrix Benchmark Decoder
intermediate 8 mins Read

How API Gateways Rate Limit Traffic

A technical breakdown of token bucket, fixed window, and sliding window rate limiting algorithms, Redis-backed implementation, 429 responses, and client-side exponential backoff with jitter.

Introduction

Rate limiting is the mechanism by which API gateways enforce consumption quotas on clients, protecting backend services from traffic spikes, DoS attacks, and resource exhaustion. Without rate limiting, a single misbehaving or compromised client can saturate a shared API, degrading quality of service for all users. API gateways like Kong, AWS API Gateway, Nginx, and Envoy implement rate limiting as a first-class concern at the network edge, making throttling decisions before requests reach application servers — at latencies of <1ms per decision.

The challenge of rate limiting is algorithmically non-trivial: naive implementations suffer from race conditions in distributed environments (multiple gateway replicas counting independently), boundary effects at window resets (a burst of 2× the limit is possible in the span of 1 second straddling a window boundary), and fairness issues (blocking legitimate bursts while allowing sustained at-limit traffic). The token bucket algorithm, sliding window log, and sliding window counter each make different trade-offs among accuracy, memory consumption, and distributed coordination overhead.

Step-by-Step: Rate Limiting Algorithms

flowchart TD
    A["1. Token Bucket Algorithm (Burst-Tolerant)"]
    B["2. Fixed Window Counter (Simple but Flawed)"]
    C["3. Sliding Window Log"]
    D["4. Redis INCR + EXPIRE"]
    E["5. 429 Too Many Requests + Retry-After Header"]
    F["6. Client-Side Exponential Backoff with Jitter"]
    A --> B
    B --> C
    C --> D
    D --> E
    E --> F

Step 1: Token Bucket Algorithm (Burst-Tolerant)

The token bucket is the most widely used rate limiting algorithm because it allows controlled bursting — short spikes above the sustained rate are permitted, up to the bucket capacity.

Mechanics:

  • A bucket has a maximum capacity B tokens (the burst allowance)
  • Tokens are added at rate r tokens/second (the sustained rate)
  • Each request consumes 1 token; if the bucket is empty, the request is rejected
  • The bucket starts full (or can start empty for stricter limits)
State: (token_count, last_refill_timestamp)

On each request:
  elapsed = current_time - last_refill_timestamp
  token_count = min(B, token_count + elapsed * r)
  last_refill_timestamp = current_time
  
  if token_count >= 1:
    token_count -= 1
    ALLOW request
  else:
    REJECT with 429

Example: A rate limit of 100 req/s with burst capacity 200 means:

  • Sustained: 100 requests per second indefinitely
  • Burst: Up to 200 requests can be made instantly if the bucket was full
  • A client that is idle for 2 seconds can then make 200 requests immediately
import time
import threading

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity        # Maximum tokens (burst size)
        self.refill_rate = refill_rate  # Tokens per second
        self.tokens = capacity          # Start full
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()
    
    def consume(self, tokens: float = 1.0) -> bool:
        with self.lock:
            now = time.monotonic()
            # Refill based on elapsed time
            elapsed = now - self.last_refill
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.refill_rate
            )
            self.last_refill = now
            
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True  # Allow
            return False     # Reject

# 100 req/s sustained, 200 burst
limiter = TokenBucket(capacity=200, refill_rate=100)

Step 2: Fixed Window Counter (Simple but Flawed)

The fixed window counter divides time into fixed intervals (e.g., 1-minute windows) and counts requests per window:

window_key = f"rate:{client_id}:{floor(current_time / window_size)}"
count = INCR window_key
if count == 1:
    EXPIRE window_key window_size  # Set TTL on first request

if count > limit:
    REJECT with 429

The epoch reset problem: A client can send limit requests at 11:59:59 and another limit requests at 12:00:01 — consuming 2 × limit requests in 2 seconds. This “boundary burst” is a fundamental flaw of fixed windows that sliding window algorithms fix.

# Redis fixed window implementation
redis-cli <<'EOF'
SET rate:client123:1700000 0 EX 60 NX  # Only set if not exists
INCR rate:client123:1700000              # Increment counter
GET rate:client123:1700000               # Check count
TTL rate:client123:1700000              # Check remaining window
EOF

Step 3: Sliding Window Log (Accurate but Memory-Intensive)

The sliding window log stores a timestamp for every request in the window:

On each request:
  window_start = current_time - window_size
  
  ZREMRANGEBYSCORE client_log -inf window_start   # Remove old entries
  count = ZCARD client_log                         # Count requests in window
  
  if count < limit:
    ZADD client_log current_time current_time     # Add this request
    ALLOW
  else:
    REJECT with 429

This is perfectly accurate (no boundary effects) but stores one entry per request, which is memory-intensive for high-traffic APIs. For 10,000 clients each making 1,000 requests per window, you need storage for 10M timestamps.

# Redis sliding window log
CLIENT_ID="user_abc"
WINDOW=60   # 60-second window
LIMIT=100
NOW=$(date +%s%3N)  # Milliseconds since epoch
WINDOW_START=$((NOW - WINDOW * 1000))

redis-cli ZREMRANGEBYSCORE "log:$CLIENT_ID" -inf $WINDOW_START
COUNT=$(redis-cli ZCARD "log:$CLIENT_ID")

if [ "$COUNT" -lt "$LIMIT" ]; then
  redis-cli ZADD "log:$CLIENT_ID" $NOW $NOW
  redis-cli EXPIRE "log:$CLIENT_ID" $WINDOW
  echo "ALLOWED"
else
  echo "RATE LIMITED"
fi

Step 4: Redis INCR + EXPIRE — Distributed Fixed Window

For distributed rate limiting across multiple gateway replicas, Redis is the canonical shared state store. The INCR command is atomic in Redis (single-threaded command execution), making it safe for concurrent increments from multiple gateway nodes:

# Atomic rate limit check using Redis Lua script (prevents TOCTOU race)
redis-cli EVAL "
  local key = KEYS[1]
  local limit = tonumber(ARGV[1])
  local window = tonumber(ARGV[2])
  local current = redis.call('INCR', key)
  if current == 1 then
    redis.call('EXPIRE', key, window)
  end
  if current > limit then
    return 0  -- Rejected
  end
  return 1    -- Allowed
" 1 "rate:user123:$(date +%s | awk '{print int($1/60)}')" 100 60

Using a Lua script ensures the INCR and EXPIRE operations execute atomically — no other Redis command can interleave between them, preventing the race condition where two concurrent requests both see count=0 and neither sets the expiry.

Step 5: 429 Too Many Requests + Retry-After Header

When a request is rate limited, the API gateway returns HTTP 429 Too Many Requests with a Retry-After header indicating when the client may retry:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 23
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1700000060

{
  "error": {
    "code": "RATE_LIMIT_EXCEEDED",
    "message": "API rate limit exceeded. Retry after 23 seconds.",
    "retryAfter": 23
  }
}

The Retry-After value can be an integer (seconds to wait) or an HTTP-date. The X-RateLimit-Reset is a Unix timestamp of when the window resets. Well-designed clients must parse these headers rather than blindly retrying immediately.

Step 6: Client-Side Exponential Backoff with Jitter

A naive client that retries immediately upon receiving 429 will storm the API at the window reset boundary — thousands of clients all retrying at the same moment. Exponential backoff with jitter breaks up this thundering herd:

import time
import random
import httpx

def api_request_with_backoff(
    client: httpx.Client,
    url: str,
    max_retries: int = 5,
    base_delay: float = 1.0,
    max_delay: float = 60.0,
) -> httpx.Response:
    for attempt in range(max_retries):
        response = client.get(url)
        
        if response.status_code != 429:
            return response
        
        # Check Retry-After header first
        retry_after = response.headers.get("Retry-After")
        if retry_after:
            wait_time = float(retry_after)
        else:
            # Exponential backoff: base_delay * 2^attempt
            exponential_delay = base_delay * (2 ** attempt)
            capped_delay = min(exponential_delay, max_delay)
            # Full jitter: random value in [0, capped_delay]
            # This prevents synchronized retries across clients
            wait_time = random.uniform(0, capped_delay)
        
        if attempt < max_retries - 1:
            print(f"Rate limited. Waiting {wait_time:.2f}s (attempt {attempt+1}/{max_retries})")
            time.sleep(wait_time)
    
    raise RuntimeError(f"Max retries ({max_retries}) exceeded")

# Usage
with httpx.Client() as client:
    response = api_request_with_backoff(client, "https://api.example.com/data")

Full jitter (random.uniform(0, cap)) is preferred over “equal jitter” because it maximally spreads retry times. The AWS Architecture Blog demonstrated that full jitter reduces mean completion time by 30-50% in high-contention scenarios compared to simple exponential backoff without jitter.

Key Takeaways

  • Token bucket allows bursting above the sustained rate: The capacity parameter is independent of the rate — a client can consume capacity tokens instantly if the bucket is full, then must wait for tokens to refill at rate tokens/second.
  • Fixed window counters have a 2× burst vulnerability at window boundaries: A client can send limit requests just before a window resets and limit requests just after, consuming 2 × limit requests in 2 seconds — sliding window algorithms eliminate this.
  • Redis Lua scripts provide atomic distributed rate limiting: Using EVAL to run INCR + EXPIRE atomically prevents TOCTOU race conditions in multi-replica gateway deployments where multiple processes increment the same counter concurrently.
  • HTTP 429 must include a Retry-After header: Clients cannot implement correct backoff without knowing when the rate limit window resets; including X-RateLimit-Remaining and X-RateLimit-Reset additionally enables proactive client-side throttling before hitting the limit.
  • Full jitter prevents the thundering herd at window reset: By randomizing retry delays uniformly in [0, exponential_cap] rather than using deterministic delays, clients spread their retry attempts across time, preventing the synchronized burst that would occur if all clients backed off to the exact same retry timestamp.

Historical figures, architectures, and capabilities are for informational purposes only. Not technical, professional, legal, or financial advice. Sources: Research papers, developer documentation.