Chapter 28: Rate Limiting & Throttling

Why Rate Limit

Rate limiting controls the frequency of requests to prevent system overload and ensure fair resource allocation.

Where Rate Limiting Applies

• API Gateway: Public-facing APIs (REST, GraphQL)
• Authentication: Login, password reset, 2FA attempts
• Database: Query rate per tenant to prevent noisy neighbors
• Microservices: Inter-service communication limits
• Third-Party Integrations: Respect downstream rate limits
• User Actions: Post creation, file uploads, message sends

Token Bucket

The most widely used rate limiting algorithm. Tokens are added to a bucket at a fixed rate, and each request consumes a token.

Algorithm Parameters

How Bursts Work

Token bucket allows short bursts up to bucket capacity, then enforces sustained rate equal to refill rate.

Implementation Pseudocode

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

    def allow_request(self, tokens_required=1):
        self.refill()

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

    def refill(self):
        current_time = now()
        elapsed = current_time - self.last_refill
        tokens_to_add = elapsed * self.refill_rate

        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill = current_time

Advantages & Disadvantages

Real-World Usage

• AWS API Gateway: Token bucket with burst and sustained rate
• Stripe API: 100 req/sec sustained, 1000 req/sec burst
• Kubernetes: Client-side rate limiting for API server
• Network Traffic Shaping: QoS in routers (tc command in Linux)

Leaky Bucket

Requests are added to a fixed-size queue and processed at a constant rate, like water dripping from a bucket with a hole.

Key Characteristics

Implementation Pseudocode

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity  # max queue size
        self.leak_rate = leak_rate  # requests per second
        self.queue = []
        self.last_leak = now()

    def allow_request(self, request):
        self.leak()

        if len(self.queue) < self.capacity:
            self.queue.append(request)
            return True
        return False

    def leak(self):
        current_time = now()
        elapsed = current_time - self.last_leak
        requests_to_process = int(elapsed * self.leak_rate)

        # Process (remove) requests from queue
        for i in range(min(requests_to_process, len(self.queue))):
            process(self.queue.pop(0))

        self.last_leak = current_time

When to Use Leaky Bucket

Fixed Window Counter

Count requests in fixed time windows (e.g., 1-minute intervals). Simple but has edge-case issues.

How It Works

The Edge-Case Problem

Limit: 100 req/min. User sends 100 requests at 12:00:59 and 100 at 12:01:00 = 200 requests in 1 second, violating the intent of the limit.

Implementation Pseudocode

class FixedWindowCounter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size  # seconds
        self.counter = 0
        self.window_start = current_window_start()

    def allow_request(self):
        current_window = current_window_start()

        # Reset counter if new window
        if current_window > self.window_start:
            self.counter = 0
            self.window_start = current_window

        if self.counter < self.limit:
            self.counter += 1
            return True
        return False

    def current_window_start(self):
        return (now() // self.window_size) * self.window_size

Advantages & Disadvantages

Sliding Window Log

Track the timestamp of every request in a log. Most accurate but memory-intensive.

How It Works

1. Store timestamp of every request in a sorted log (array or sorted set)
2. On new request, remove timestamps older than window size
3. Count remaining timestamps
4. If count < limit, allow request and add new timestamp
5. Otherwise reject

Example: 5 requests per minute

Implementation Pseudocode

class SlidingWindowLog:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size  # seconds
        self.log = []  # sorted list of timestamps

    def allow_request(self):
        current_time = now()
        cutoff_time = current_time - self.window_size

        # Remove expired timestamps
        self.log = [ts for ts in self.log if ts > cutoff_time]

        if len(self.log) < self.limit:
            self.log.append(current_time)
            return True
        return False

Redis Implementation

-- Use sorted set with timestamps as scores
ZADD rate_limit:user123 {timestamp} {request_id}
ZREMRANGEBYSCORE rate_limit:user123 0 {cutoff_timestamp}
ZCARD rate_limit:user123  -- count requests in window
EXPIRE rate_limit:user123 {window_size + buffer}

Advantages & Disadvantages

Sliding Window Counter

Hybrid approach combining fixed window simplicity with sliding window accuracy. Best balance for production systems.

Algorithm

Estimate current window count using weighted sum of previous + current fixed windows.

Formula

Current Time: 12:01:30 (50% through current window)
Window Size: 60 seconds
Limit: 100 requests

previous_window_count = 80
current_window_count = 40
overlap_percentage = (60 - 30) / 60 = 0.5

estimated_count = previous_window_count × overlap_percentage + current_window_count
                = 80 × 0.5 + 40
                = 40 + 40
                = 80

80 < 100 → Allow request

Step-by-Step Example

Implementation Pseudocode

class SlidingWindowCounter:
    def __init__(self, limit, window_size):
        self.limit = limit
        self.window_size = window_size
        self.windows = {}  # {window_id: count}

    def allow_request(self):
        current_time = now()
        current_window = current_time // self.window_size
        previous_window = current_window - 1

        current_count = self.windows.get(current_window, 0)
        previous_count = self.windows.get(previous_window, 0)

        # Calculate position in current window (0.0 to 1.0)
        elapsed_in_current = (current_time % self.window_size) / self.window_size
        previous_weight = 1.0 - elapsed_in_current

        estimated_count = previous_count * previous_weight + current_count

        if estimated_count < self.limit:
            self.windows[current_window] = current_count + 1
            return True
        return False

Redis Implementation

-- Store two counters: previous and current window
current_window = floor(timestamp / window_size)
previous_window = current_window - 1

current_key = "rate_limit:user123:" .. current_window
previous_key = "rate_limit:user123:" .. previous_window

current_count = GET current_key OR 0
previous_count = GET previous_key OR 0

elapsed_in_current = (timestamp % window_size) / window_size
estimated = previous_count * (1 - elapsed_in_current) + current_count

if estimated < limit then
    INCR current_key
    EXPIRE current_key (window_size * 2)
    return true
end
return false

Advantages & Disadvantages

Algorithm Comparison

Performance Comparison (1M requests/sec)

Decision Tree

Distributed Rate Limiting

In multi-server deployments, rate limiting must be coordinated to prevent over-provisioning.

Challenges

Redis-Based Solutions

Option 1: INCR + EXPIRE (Fixed Window)

-- Simple but has race condition between INCR and EXPIRE
key = "rate_limit:user123:" .. current_window
count = INCR key
if count == 1 then
    EXPIRE key window_size
end

if count <= limit then
    return true
else
    return false
end

Problem: If server crashes after INCR but before EXPIRE, key never expires.

Option 2: Lua Script (Atomic)

-- Atomic execution, no race conditions
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local current = redis.call('GET', key)
if current == false then
    redis.call('SET', key, 1, 'EX', window)
    return 1
end

current = tonumber(current)
if current < limit then
    redis.call('INCR', key)
    return 1
else
    return 0
end

Option 3: Token Bucket with Redis

-- Store tokens and last_refill_time
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- Refill tokens
local elapsed = now - last_refill
local tokens_to_add = elapsed * refill_rate
tokens = math.min(capacity, tokens + tokens_to_add)

if tokens >= 1 then
    tokens = tokens - 1
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, 3600)
    return 1
else
    return 0
end

Option 4: Sliding Window Counter with Redis

-- Most accurate distributed algorithm
local key_prefix = KEYS[1]
local limit = tonumber(ARGV[1])
local window_size = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local current_window = math.floor(now / window_size)
local previous_window = current_window - 1

local current_key = key_prefix .. ":" .. current_window
local previous_key = key_prefix .. ":" .. previous_window

local current_count = tonumber(redis.call('GET', current_key) or "0")
local previous_count = tonumber(redis.call('GET', previous_key) or "0")

local elapsed = (now % window_size) / window_size
local previous_weight = 1 - elapsed
local estimated = previous_count * previous_weight + current_count

if estimated < limit then
    redis.call('INCR', current_key)
    redis.call('EXPIRE', current_key, window_size * 2)
    return 1
else
    return 0
end

Strategies for Reducing Redis Load

Handling Redis Failures

Rate Limiting Architecture

Rate limiting can be enforced at multiple layers for defense in depth.

Layer-by-Layer Breakdown

Multi-Tenant SaaS Architecture

Hierarchical Rate Limiting

Apply multiple limits in order from broadest to most specific.

HTTP Headers & Responses

Standard headers communicate rate limit status to clients.

Common Rate Limit Headers

Example Response Headers

HTTP/1.1 200 OK
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 457
X-RateLimit-Reset: 1672531200
Content-Type: application/json

{
  "data": "..."
}

429 Too Many Requests Response

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1672531200
Retry-After: 42
Content-Type: application/json

{
  "error": {
    "code": "rate_limit_exceeded",
    "message": "You have exceeded the rate limit of 1000 requests per hour.",
    "retry_after": 42,
    "limit": 1000,
    "window": "1 hour",
    "documentation_url": "https://api.example.com/docs/rate-limits"
  }
}

Client-Side Handling

Standard: IETF Draft

The IETF RateLimit Header Fields draft standardizes these headers:

• RateLimit-Limit: Requests allowed in window
• RateLimit-Remaining: Requests left
• RateLimit-Reset: Seconds until reset (not Unix timestamp)

HTTP/1.1 200 OK
RateLimit-Limit: 100
RateLimit-Remaining: 45
RateLimit-Reset: 42
RateLimit-Policy: 100;w=60

Design a Rate Limiter

End-to-end design for a multi-tenant SaaS with per-user, per-API, and global limits.

Requirements

High-Level Architecture

Data Model

Algorithm Choice

Sliding Window Counter for all limits (best balance of accuracy and performance).

Implementation Flow

function handle_request(user_id, api_endpoint):
    # 1. Check global limit (fastest path)
    if not check_global_limit():
        return 429_response("System overload")

    # 2. Check local cache (no network call)
    local_count = local_cache.get(user_id)
    if local_count and local_count > limit * 0.9:
        # Approaching limit, check Redis
        pass
    elif local_count and local_count < limit * 0.5:
        # Safely under limit, allow without Redis check
        local_cache.incr(user_id)
        return process_request()

    # 3. Check Redis (accurate distributed count)
    redis_result = redis_sliding_window_check(user_id, limit, window)
    if not redis_result.allowed:
        return 429_response(redis_result)

    # 4. Check endpoint-specific limit
    endpoint_result = check_endpoint_limit(api_endpoint)
    if not endpoint_result.allowed:
        return 429_response(endpoint_result)

    # 5. Update local cache
    local_cache.set(user_id, redis_result.count, ttl=60)

    # 6. Process request
    return process_request()

Optimizations

Failure Modes

Throttling vs Rate Limiting vs Load Shedding

Related but distinct concepts for controlling system load.

When to Use Each

Comparison: Rate Limiting vs Throttling

Load Shedding Strategies