Rate Limiter

Metadata

1. Overview

What problem does it solve?

No system has infinite resources. If a single user (or a malicious botnet) sends 10,000 requests per second to your API, your servers will crash, database connections will exhaust, and legitimate users will be locked out.

A Rate Limiter controls the rate of traffic sent by a client or a service. If the API allows 10 requests per minute, the 11th request is blocked and returned with an HTTP 429 Too Many Requests status code.

What breaks without it?

• DDoS Attacks: Attackers easily overwhelm your servers.
• Resource Starvation: One poorly coded script by a customer can consume 99% of your server capacity (the "Noisy Neighbor" problem).
• Runaway Costs: If your backend autoscales or calls paid 3rd-party APIs (like OpenAI), an infinite loop could cost you thousands of dollars.

2. Motivation

Rate limiting is usually implemented inside the API Gateway (Block 008) or a Load Balancer (Block 007).

But in a distributed system, rate limiting is hard. If a user is allowed 10 requests per minute, and you have 5 API Gateway servers, how do they coordinate? If Gateway A allows 5 requests and Gateway B allows 5 requests, they need a fast, centralized way to share state. This is why distributed rate limiters almost exclusively rely on fast in-memory stores like Redis.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The 4 Core Algorithms

graph TD
    subgraph "1. Token Bucket (Amazon, Stripe)"
        TB["Bucket capacity: 10 tokens<br/>Refill rate: 2 tokens/sec"]
        TB --> |Has token?| Allow1["Allow (Remove 1 token)"]
        TB --> |Empty?| Block1["Block (429)"]
    end

    subgraph "2. Leaky Bucket (Shopify)"
        LB["Queue capacity: 10 reqs<br/>Process rate: 2 reqs/sec"]
        LB --> |Queue full?| Block2["Block (Drop req)"]
    end

Fixed Window vs Sliding Window:

• Fixed Window: 100 reqs / min. Resets at exactly 12:01:00. (Flaw: A user can send 100 reqs at 12:00:59 and 100 reqs at 12:01:01 -> 200 reqs in 2 seconds).
• Sliding Window: Looks at the exact trailing 60 seconds from now. Perfectly smooth, but uses more memory.

6. Internal Working

6.1 Token Bucket (The Industry Standard)

Imagine a physical bucket that holds exactly C tokens.

• Every second, we drop R new tokens into the bucket.
• If the bucket is full, extra tokens overflow and are lost.
• When a request arrives, we take 1 token out. If the bucket is empty, we drop the request.

Pros: Allows for bursts of traffic. If you haven't used the API for a while, you can send C requests instantly. Memory efficient.

6.2 Leaky Bucket

Requests pour into the top of the bucket at any rate. They leak out the bottom at a constant rate.

• It's essentially a FIFO queue.
• If the queue is full, new requests are dropped.

Pros: Smooths out traffic bursts. Your backend servers see a perfectly consistent rate of requests. (Shopify uses this for their API).

6.3 Fixed Window Counter

Store a counter in Redis with the key user_42:minute_12:01. Increment it. If it > 100, reject. At 12:02, a new key is used. Pros: Extremely memory efficient. Cons: The "Edge of Window" spike problem (2x traffic allowed at the minute boundary).

6.4 Sliding Window Log

Keep a Redis Sorted Set (ZSET) of timestamps for every request a user makes. When a new request arrives:

1. Remove all timestamps older than 1 minute.
2. Count the remaining elements.
3. If count < limit, add the new timestamp and accept.

Pros: 100% perfectly accurate rate limiting. Cons: High memory usage (must store the timestamp of every single request).

7. Implementation

Why Python + Redis? Redis is the defacto standard for distributed rate limiting. We'll implement the Fixed Window Counter and the Sliding Window Log algorithms using Python.

"""
009 - Distributed Rate Limiter
Demonstrates Fixed Window and Sliding Window algorithms using Redis.
Prerequisites: `pip install redis` and a running Redis server on localhost:6379
"""
import time
import redis

# Connect to Redis
r = redis.Redis(host='localhost', port=6379, db=0, decode_responses=True)

# ── 1. Fixed Window Counter ──

def is_allowed_fixed_window(user_id: str, limit: int, window_sec: int) -> bool:
    """
    Allows 'limit' requests per 'window_sec' chunk of time.
    Vulnerable to the edge-of-window burst problem.
    """
    # Calculate current time window (e.g., integer division by 60)
    current_window = int(time.time() // window_sec)
    
    redis_key = f"rate:fixed:{user_id}:{current_window}"
    
    # INCR is atomic in Redis
    current_count = r.incr(redis_key)
    
    # Set expiration on the key so Redis doesn't fill up with old windows
    if current_count == 1:
        r.expire(redis_key, window_sec * 2)
        
    return current_count <= limit


# ── 2. Sliding Window Log ──

def is_allowed_sliding_window(user_id: str, limit: int, window_sec: int) -> bool:
    """
    Allows 'limit' requests in the exact trailing 'window_sec'.
    Perfectly smooth, but uses more memory (stores every request timestamp).
    """
    redis_key = f"rate:sliding:{user_id}"
    now_ms = int(time.time() * 1000)
    window_start_ms = now_ms - (window_sec * 1000)
    
    pipeline = r.pipeline()
    
    # 1. Remove all requests older than the window
    pipeline.zremrangebyscore(redis_key, 0, window_start_ms)
    
    # 2. Add the current request timestamp
    # Using timestamp as both score and value
    pipeline.zadd(redis_key, {str(now_ms): now_ms})
    
    # 3. Count total requests in the current window
    pipeline.zcard(redis_key)
    
    # 4. Set expiration to keep memory clean
    pipeline.expire(redis_key, window_sec * 2)
    
    # Execute transaction atomically
    results = pipeline.execute()
    
    # The result of zcard is at index 2
    request_count = results[2]
    
    return request_count <= limit


# ── Simulation ──

if __name__ == "__main__":
    USER = "user_42"
    LIMIT = 3
    WINDOW = 5 # seconds
    
    r.flushdb() # Clear redis for testing
    
    print(f"--- Testing Sliding Window ({LIMIT} reqs per {WINDOW}s) ---")
    
    for i in range(1, 8):
        allowed = is_allowed_sliding_window(USER, LIMIT, WINDOW)
        status = "✅ ALLOWED" if allowed else "❌ BLOCKED (429)"
        print(f"Req {i} at {time.strftime('%X')}: {status}")
        time.sleep(1) # Send 1 request per second
        
    print("\nWaiting 3 seconds for window to slide...")
    time.sleep(3)
    
    allowed = is_allowed_sliding_window(USER, LIMIT, WINDOW)
    status = "✅ ALLOWED" if allowed else "❌ BLOCKED (429)"
    print(f"Req 8 at {time.strftime('%X')}: {status}")

Sample Output

--- Testing Sliding Window (3 reqs per 5s) ---
Req 1 at 14:00:00: ✅ ALLOWED
Req 2 at 14:00:01: ✅ ALLOWED
Req 3 at 14:00:02: ✅ ALLOWED
Req 4 at 14:00:03: ❌ BLOCKED (429)
Req 5 at 14:00:04: ❌ BLOCKED (429)
Req 6 at 14:00:05: ❌ BLOCKED (429)
Req 7 at 14:00:06: ❌ BLOCKED (429)

Waiting 3 seconds for window to slide...
Req 8 at 14:00:09: ✅ ALLOWED

8. Complexity

Scalability Characteristics

• Because rate limiting happens on every single request, hitting Redis across the network adds 1-2ms of latency.
• At extreme scale (Millions of RPS), a central Redis cluster becomes a bottleneck. To solve this, companies use Local Cache + Async Sync. The API Gateway caches limits locally in RAM, and syncs to Redis asynchronously (sacrificing strict accuracy for massive performance).

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Explain the Token Bucket algorithm. Why is it so popular? Hint: It uses very little memory (just two integers: tokens left, last refill time) and it allows for brief bursts of traffic while enforcing an overall average rate.

2. How does a Sliding Window Log differ from a Fixed Window Counter? Hint: Fixed Window stores one counter per time block (e.g., minute). Sliding window stores the exact timestamp of every request. Fixed window allows 2x traffic at window edges; Sliding window is perfectly accurate but uses more memory.

3. Your distributed rate limiter relies on Redis. What happens if the Redis cluster crashes? Hint: The system should "Fail Open". It's better to temporarily lose rate limiting than to block 100% of legitimate traffic because the limiter is down.

4. How do you prevent Race Conditions in a distributed rate limiter? Hint: Do not use a "Read-Modify-Write" pattern in app code. Send a Lua script to Redis to execute the check and decrement atomically.

13. Used By (Downstream Blocks)

• 008 API Gateway — The component that usually executes the rate limiting logic.
• 028 Circuit Breaker — Rate limits protect your servers; circuit breakers protect downstream dependencies.
• 010 Caching — Relies on Redis, just like distributed rate limiters.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Sliding Window Approximation (Sliding Window Counter)

Combine Fixed Window and Sliding Window. Keep two counters: the previous minute and the current minute. Calculate the limit dynamically based on the overlap percentage of the current time into the current minute. This yields 99% accuracy with O(1) memory!

Exercise 2: Add Headers

Modify the Python script to return a dictionary containing allowed: bool and retry_after: int. Calculate the retry_after seconds so the caller knows exactly when they are allowed to make the next request.

Website Metadata