How API Gateways Rate Limit and Throttle Traffic

Introduction

Rate limiting protects backend services from being overwhelmed by too many requests — whether from misbehaving clients, DDoS attacks, or runaway automation scripts. API gateways like Kong, AWS API Gateway, and Nginx implement rate limiting as a middleware layer, rejecting excess requests with 429 Too Many Requests before they reach application servers. The algorithm choice significantly affects user experience: some algorithms cause thundering-herd problems at epoch boundaries, while others smooth traffic more gracefully.

Step-by-Step: Rate Limiting Algorithms

flowchart TD
    A["1. Fixed Window Counter (Simple but Flawed)"]
    B["2. Sliding Window Log"]
    C["3. Token Bucket (Most Common)"]
    D["4. Sliding Window Counter (Best of Both)"]
    E["5. Client Response and Retry Handling"]
    A --> B
    B --> C
    C --> D
    D --> E

Step 1: Fixed Window Counter (Simple but Flawed)

The simplest approach: count requests per client per time window (e.g., 100 requests per 60-second window). Reset the counter at the window boundary.

Problem: A client can send 100 requests at 23:59:59 and 100 more at 00:00:01 — effectively 200 requests in 2 seconds.

# Redis implementation
INCR rate:user123:window:1704067200  # Unix epoch of window start
EXPIRE rate:user123:window:1704067200 60

Step 2: Sliding Window Log

Record the timestamp of every request. On each new request, count timestamps within the last N seconds and reject if over limit.

Problem: Stores every request timestamp — O(requests) memory per user.

Step 3: Token Bucket (Most Common)

A bucket holds up to capacity tokens. Tokens refill at a fixed rate (e.g., 10/second). Each request consumes one token. If empty, the request is rejected.

Advantage: Allows controlled bursting up to bucket capacity, then enforces the average rate.

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.last_refill = time.time()

    def consume(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  # allowed
        return False  # rate limited

Step 4: Sliding Window Counter (Best of Both)

Combines fixed window simplicity with sliding accuracy. Uses two windows and weights the previous window by the overlap:

rate = prev_window_count × (1 - elapsed/window) + curr_window_count

# Redis atomic Lua script for sliding window
local key_curr = KEYS[1]
local key_prev = KEYS[2]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local elapsed = now % window
local weight = (window - elapsed) / window
local count = tonumber(redis.call('GET', key_curr) or 0)
           + math.floor(tonumber(redis.call('GET', key_prev) or 0) * weight)
if count >= limit then return 0 end
redis.call('INCR', key_curr)
redis.call('EXPIRE', key_curr, window * 2)
return 1

Step 5: Client Response and Retry Handling

Rate-limited responses must include headers to guide clients:

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

Clients should implement exponential backoff with jitter:

import random, time
def retry_with_backoff(fn, max_retries=5):
    for attempt in range(max_retries):
        try:
            return fn()
        except RateLimitError:
            wait = (2 ** attempt) + random.uniform(0, 1)  # jitter prevents thundering herd
            time.sleep(wait)
    raise Exception("Max retries exceeded")

Key Takeaways

• Fixed window is simple but creates boundary burst vulnerability; never use it for security-critical rate limits.
• Token bucket is the industry standard — it allows short bursts while enforcing the average rate.
• Sliding window counter provides the best accuracy-to-memory tradeoff for high-throughput APIs.
• Use Redis atomic Lua scripts for distributed rate limiting across multiple gateway instances.
• Always return Retry-After headers; clients using exponential backoff with jitter prevent thundering-herd retry storms.