Part 4: Rate Limiting - Complete Guide to Algorithms and Implementation

Part 4: Rate Limiting

Complete Guide to Rate Limiting Algorithms and Implementation

📌 Quick Summary:
Rate limiting controls how many requests a client can make within a specific time window. It protects your services from abuse, ensures fair usage, and prevents system overload. When exceeded, return HTTP 429 "Too Many Requests". The most common algorithm is Token Bucket.

What is Rate Limiting?

📖 Real-World Example: A nightclub allows only 50 people to enter per hour. Once 50 people are inside, new arrivals must wait outside until someone leaves. This protects the club from overcrowding.

Why Do We Need Rate Limiting?

Prevent DDoS attacks - Stop malicious actors from overwhelming your system
Ensure fair usage - One client shouldn't consume all resources
Protect downstream services - Prevent cascading failures
Control costs - Reduce unnecessary API calls (especially for paid APIs)
Maintain service quality - Keep response times predictable for all users

1. Token Bucket Algorithm

What is Token Bucket?

Tokens are added to a bucket at a fixed rate. Each request consumes one token. If no tokens are available, the request is rejected.

📖 Real-World Example: A vending machine is restocked with 10 candies per hour. Each purchase removes one candy. If someone buys 50 candies at once, they can't because only 10 are available. They must wait for restocking.

How It Works

┌─────────────────────────────────────────────────────────────┐
│                                                             │
│   Tokens added at           ┌─────────────┐                │
│   steady rate (10/sec) ───► │             │                │
│                             │   Bucket    │                │
│   Each request consumes ───► │  (50 max)  │                │
│   1 token                    │             │                │
│                             └─────────────┘                │
│                                    │                        │
│                                    ▼                        │
│                        Request allowed? YES → Process       │
│                        Request allowed? NO  → HTTP 429     │
│                                                             │
│   Burst capability: 50 requests can come instantly!       │
└─────────────────────────────────────────────────────────────┘

Parameters

Parameter	Meaning	Example
Refill Rate	Tokens added per second	10 tokens per second
Bucket Capacity	Maximum tokens that can be stored	100 tokens maximum
Cost per Request	Tokens consumed per request	1 token per API call

Code Implementation

// Token Bucket Implementation in Java
public class TokenBucket {
    private final long capacity;        // Max tokens
    private final long refillTokens;    // Tokens added per refill
    private final long refillIntervalMs; // Refill interval in milliseconds
    
    private long currentTokens;
    private long lastRefillTimestamp;
    
    public TokenBucket(long capacity, long refillTokens, long refillIntervalMs) {
        this.capacity = capacity;
        this.refillTokens = refillTokens;
        this.refillIntervalMs = refillIntervalMs;
        this.currentTokens = capacity;
        this.lastRefillTimestamp = System.currentTimeMillis();
    }
    
    public synchronized boolean allowRequest() {
        refill();
        
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }
    
    private void refill() {
        long now = System.currentTimeMillis();
        long timePassed = now - lastRefillTimestamp;
        
        if (timePassed >= refillIntervalMs) {
            long intervals = timePassed / refillIntervalMs;
            long tokensToAdd = intervals * refillTokens;
            currentTokens = Math.min(capacity, currentTokens + tokensToAdd);
            lastRefillTimestamp = now;
        }
    }
}

// Usage
TokenBucket limiter = new TokenBucket(100, 10, 1000); // 10 tokens/sec, max 100
if (limiter.allowRequest()) {
    processRequest();
} else {
    return ResponseEntity.status(429).body("Too Many Requests");
}

✅ Pros
• Allows bursts
• Simple to implement
• Memory efficient
• Predictable behavior

❌ Cons
• Two parameters to tune
• Burst can overwhelm if too large
• Clock synchronization issues in distributed setup

2. Fixed Window Counter

What is Fixed Window Counter?

Time is divided into fixed windows (e.g., 1 minute). Each window has a counter that resets at the end of the window.

📖 Real-World Example: A gym allows only 30 people to enter per hour. At the start of each hour, the counter resets to zero. No matter how many people came in the last hour, a new hour starts fresh.

How It Works

Window 1 (10:00:00 - 10:00:59)    Window 2 (10:01:00 - 10:01:59)
┌─────────────────────────┐      ┌─────────────────────────┐
│ Counter: 25 requests    │      │ Counter: 30 requests    │
│ (5 remaining)           │      │ (0 remaining)           │
└─────────────────────────┘      └─────────────────────────┘
                    ↓                              ↓
            At 10:00:60, counter resets    At 10:02:00, counter resets

PROBLEM: A burst at 10:00:59 and 10:01:00 (50 requests in 2 seconds) will pass!
Both windows allow requests, but requests were actually 1 second apart.

Code Implementation

// Fixed Window Counter Implementation
public class FixedWindowCounter {
    private final long windowSizeMs;    // Window size (e.g., 60000 for 1 minute)
    private final long maxRequests;      // Max requests per window
    
    private long windowStart;
    private long counter;
    
    public FixedWindowCounter(long windowSizeMs, long maxRequests) {
        this.windowSizeMs = windowSizeMs;
        this.maxRequests = maxRequests;
        this.windowStart = System.currentTimeMillis();
        this.counter = 0;
    }
    
    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        
        // Check if we're in a new window
        if (now - windowStart >= windowSizeMs) {
            windowStart = now;
            counter = 0;
        }
        
        if (counter < maxRequests) {
            counter++;
            return true;
        }
        return false;
    }
}

✅ Pros
• Very simple to implement
• Memory efficient
• Works well for most use cases

❌ Cons
• Window boundary problem (bursts at edges)
• Less accurate than sliding window
• Can allow 2x traffic at boundaries

⚠️ The Boundary Problem:
If a client sends 100 requests at 10:00:59.999 and another 100 at 10:01:00.000, both windows allow them even though 200 requests happened in 1 millisecond! Use Sliding Window to fix this.

3. Sliding Window Log

What is Sliding Window Log?

Stores timestamps of all requests and slides the window continuously rather than resetting at fixed boundaries.

📖 Real-World Example: Instead of counting "per hour", you look at "last 60 minutes from now" continuously. The window moves with time, not in fixed jumps.

How It Works

Time: 10:00:00 ─────────────────────────────► 10:01:00
                        Sliding Window (60 seconds)
                              ↓
        [timestamp1][timestamp2][timestamp3][timestamp4][timestamp5]
        
At 10:00:30, window = 09:59:30 to 10:00:30
At 10:00:31, window = 09:59:31 to 10:00:31  (slides continuously)

When new request arrives:
1. Remove timestamps older than window size
2. Count remaining timestamps
3. If count < limit, allow request and add timestamp

Code Implementation

// Sliding Window Log Implementation
public class SlidingWindowLog {
    private final long windowSizeMs;
    private final long maxRequests;
    private final Queue<Long> timestamps;
    
    public SlidingWindowLog(long windowSizeMs, long maxRequests) {
        this.windowSizeMs = windowSizeMs;
        this.maxRequests = maxRequests;
        this.timestamps = new LinkedList<>();
    }
    
    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        long windowStart = now - windowSizeMs;
        
        // Remove old timestamps
        while (!timestamps.isEmpty() && timestamps.peek() < windowStart) {
            timestamps.poll();
        }
        
        if (timestamps.size() < maxRequests) {
            timestamps.add(now);
            return true;
        }
        return false;
    }
}

✅ Pros
• Very accurate
• No boundary problems
• Works for any window size

❌ Cons
• Memory intensive (stores all timestamps)
• Slower (requires sorting/cleaning)
• Not suitable for high throughput

4. Sliding Window Counter (Best of Both)

What is Sliding Window Counter?

Hybrid approach combining Fixed Window and Sliding Window. Uses weighted count based on overlapping windows.

📖 Real-World Example: Instead of exact timestamps, you use smaller buckets (e.g., 1-second buckets) and calculate weighted average.

How It Works

Current window: 10:00:00 - 10:01:00 (60 seconds)
Previous window: 09:59:00 - 10:00:00 (60 seconds)

Request at 10:00:45:

Previous window weight = 15/60 = 0.25  (last 15 seconds of previous window)
Current window weight = 45/60 = 0.75   (first 45 seconds of current window)

Estimated count = (previous_count * 0.25) + (current_count * 0.75)

✅ Pros
• Much more accurate than Fixed Window
• Memory efficient
• Fast computation

❌ Cons
• More complex implementation
• Still not 100% accurate (but good enough)

5. Leaky Bucket Algorithm

What is Leaky Bucket?

Requests enter the bucket and are processed at a constant rate. If bucket is full, requests are discarded.

📖 Real-World Example: A water tank with a small hole at the bottom. Water enters at any rate, but leaves at constant rate. If too much water enters, the tank overflows.

How It Works

    Requests (uneven rate)          Processed (constant rate)
    ═══════════════════►              ═══════════════════►
            ↓                                   ↑
    ┌─────────────────┐                         │
    │                 │                         │
    │   Leaky Bucket  │ ───► at steady rate ────┘
    │   (Queue)       │
    │                 │
    └─────────────────┘
            ↑
    Overflow → Requests discarded

Good for: Smoothing output traffic, preventing bursts

Code Implementation

// Leaky Bucket Implementation
public class LeakyBucket {
    private final long capacity;
    private final long leakRateMs;     // Time between leaks
    private final int leakAmount;       // How many to leak each time
    
    private long currentWater;
    private long lastLeakTimestamp;
    
    public LeakyBucket(long capacity, long leakRateMs, int leakAmount) {
        this.capacity = capacity;
        this.leakRateMs = leakRateMs;
        this.leakAmount = leakAmount;
        this.currentWater = 0;
        this.lastLeakTimestamp = System.currentTimeMillis();
    }
    
    private void leak() {
        long now = System.currentTimeMillis();
        long timePassed = now - lastLeakTimestamp;
        
        if (timePassed >= leakRateMs) {
            long leaks = timePassed / leakRateMs;
            long waterToLeak = leaks * leakAmount;
            currentWater = Math.max(0, currentWater - waterToLeak);
            lastLeakTimestamp = now;
        }
    }
    
    public synchronized boolean allowRequest() {
        leak();
        
        if (currentWater < capacity) {
            currentWater++;
            return true;
        }
        return false;
    }
}

✅ Pros
• Smooths out bursts
• Predictable output rate
• Good for network traffic shaping

❌ Cons
• No burst capability
• Can waste capacity if not fully used
• Less flexible

Complete Algorithm Comparison

Algorithm	Burst Allowed?	Memory Usage	Accuracy	Complexity	Best For
Token Bucket	✅ Yes	Low	Good	Medium	Most production systems
Fixed Window	❌ No (but boundary gap)	Very Low	Poor at boundaries	Very Simple	Basic throttling, non-critical
Sliding Window Log	❌ No	High	Excellent	High	Accurate rate limiting, low scale
Sliding Window Counter	❌ No	Low	Very Good	Medium	Production systems needing accuracy
Leaky Bucket	❌ No	Low	Good	Medium	Smooth output traffic

Real-World Use Cases

Use Case	Recommended Algorithm	Typical Limits	Why
Public API (GitHub, Twitter, Stripe)	Token Bucket	5000 req/hour	Allows bursts, simple to explain to developers
Login Attempts	Fixed Window	5 attempts/15 minutes	Simple, boundary burst is acceptable
Service Mesh / API Gateway	Sliding Window Counter	1000 req/sec	Memory efficient, accurate enough
Network Traffic Shaping	Leaky Bucket	10 Mbps	Smooths out network bursts
Microservices Circuit Breaker	Sliding Window	50% failure rate	Accurate failure detection

Distributed Rate Limiting

Rate Limiting Across Multiple Servers

When you have multiple instances of your service, rate limiting must be centralized to be effective.

Solutions for Distributed Rate Limiting

A. Centralized Redis

// Redis-based Token Bucket (using Lua script for atomicity)
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 lastRefill = redis.call('GET', key .. ':last')
if lastRefill == false then
    lastRefill = now
    redis.call('SET', key .. ':tokens', capacity - requested)
    redis.call('SET', key .. ':last', now)
    return {1, capacity - requested}
end

-- Calculate tokens to refill
local timePassed = now - lastRefill
local tokensToAdd = math.floor(timePassed * rate / 1000)
local currentTokens = math.min(capacity, 
    tonumber(redis.call('GET', key .. ':tokens') or 0) + tokensToAdd)

if currentTokens >= requested then
    redis.call('SET', key .. ':tokens', currentTokens - requested)
    redis.call('SET', key .. ':last', now)
    return {1, currentTokens - requested}
else
    return {0, currentTokens}
end

B. API Gateway Native Limiting

# Kong API Gateway Rate Limiting Configuration
curl -X POST http://localhost:8001/services/example-service/plugins \
    -d "name=rate-limiting" \
    -d "config.minute=100" \
    -d "config.hour=5000" \
    -d "config.policy=redis" \
    -d "config.redis_host=redis.example.com"

# NGINX Rate Limiting
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=10r/s;
limit_req zone=mylimit burst=20 nodelay;

C. Kubernetes Rate Limiting (Istio)

# Istio Rate Limiting with Envoy
apiVersion: networking.istio.io/v1beta1
kind: EnvoyFilter
metadata:
  name: rate-limit-filter
spec:
  configPatches:
  - applyTo: HTTP_FILTER
    match:
      context: SIDECAR_INBOUND
    patch:
      operation: INSERT_BEFORE
      value:
        name: envoy.filters.http.ratelimit
        typed_config:
          "@type": type.googleapis.com/envoy.extensions.filters.http.ratelimit.v3.RateLimit
          domain: service-rate-limit

Standard HTTP Headers for Rate Limiting

Header	Purpose	Example
X-RateLimit-Limit	Maximum requests allowed in window	X-RateLimit-Limit: 100
X-RateLimit-Remaining	Requests remaining in current window	X-RateLimit-Remaining: 42
X-RateLimit-Reset	Time when window resets (UTC epoch seconds)	X-RateLimit-Reset: 1700000000
Retry-After	Seconds to wait before retrying	Retry-After: 3600

// Example Response Headers when rate limited
HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1700000000
Retry-After: 3600
Content-Type: application/json

{
    "error": {
        "code": "RATE_LIMIT_EXCEEDED",
        "message": "You have exceeded your rate limit. Please wait 1 hour.",
        "limit": 100,
        "reset": 1700000000
    }
}

💡 Interview Power Phrases

"We use token bucket rate limiting to protect downstream services from traffic spikes while allowing reasonable bursts for legitimate users."

"For distributed rate limiting, we use Redis with Lua scripts to ensure atomic operations across multiple service instances."

"Fixed window has a boundary problem where 2x traffic can pass at window edges. Sliding window counter solves this with weighted counts."

"Always return standard rate limit headers (X-RateLimit-*) so clients can implement intelligent backoff."

📌 Key Takeaways

Token Bucket is the most popular for production APIs - allows bursts, simple to tune
Fixed Window has boundary issues but is simplest to implement
Sliding Window is most accurate but memory intensive
Leaky Bucket is best for smoothing output traffic
Distributed rate limiting needs centralized store (Redis, API Gateway)
Always return HTTP 429 with rate limit headers
Consider different limits for different clients (free vs premium tier)

🧠 Mental Model:
Rate limiter = Traffic police at intersection.
Token Bucket = VIP lane with passes.
Leaky Bucket = Merge lane (one car at a time).
Fixed Window = "Only 30 cars per green light" (resets each time).