Track 7 · Module 7.1 · Distributed Reliability, Rate Limiting & DevOps

Design a Distributed Rate Limiter

How Stripe, Cloudflare, and Amazon protect their infrastructure from DDoS, brute-force bots, and noisy neighbors. Master Token Bucket, Leaky Bucket, Sliding Window Counter, Redis Lua Script atomicity, and HTTP 429 headers.

⏱️ Reading Time: ~28 min

🎯 Architecture: Token Bucket, Redis Lua Scripts, HTTP 429

🎬 Format: Nightclub Bouncer Analogy + Live Token Bucket Lab

🎟️ 1. The Core Intuition: The Nightclub Bouncer with Tokens

🚪 The Analogy: The Bouncer's Bucket & The Refill Conveyor Belt

Imagine a popular nightclub with a strict capacity limit:
1. The bouncer holds a bucket that can hold a maximum of 10 VIP Tokens (Bucket Capacity $B = 10$).
2. A mechanical conveyor belt drops 2 new tokens into the bucket every second (Refill Rate R = 2/sec).
3. When a party of 8 people arrives at once, the bouncer takes 8 tokens and lets them all in immediately! (Burst Traffic Handled).
4. When the bucket reaches 0 tokens, any new arrival is told: "Bucket is empty, please wait 0.5s for the next token" (HTTP 429 Too Many Requests).

💡 Why Do We Need Rate Limiting in System Design?1. DoS & DDoS Protection: Prevent malicious bots from crashing your servers.
2. Cost Control: Prevent runaway third-party API spend (OpenAI GPT-4 tokens, Twilio SMS, Stripe charges).
3. Preventing Cascading Failure: Prevent noisy neighbors from hogging database connection pools.

⚙️ 2. Deep Dive into the 5 Rate Limiting Algorithms

Every system design interview requires comparing these 5 algorithms:

1Token Bucket (Amazon & Stripe Standard)

Tokens added at a constant rate $R$ up to capacity $B$. Each request consumes 1 token. Allows sudden bursts of traffic while maintaining a strict long-term average rate. Requires only 2 numbers in memory per user: tokens and last_refill_timestamp ($O(1)$ RAM).

2Leaky Bucket (Shopify & Nginx Standard)

Requests enter a fixed-capacity FIFO queue and leak out at a strictly constant, smooth rate. Perfect for smoothing out bursty eCommerce flash-sales into a steady flow for databases.

3Fixed Window Counter (The 2x Boundary Burst Trap ⚠️)

Divides time into fixed 1-minute windows (12:00, 12:01) with a counter.

🚨 The Vulnerability: A client sends 100 requests at 12:00:59 and 100 requests at 12:01:01. Both are allowed because they are in separate windows, resulting in 200 requests in 2 seconds (2x traffic burst!).

4Sliding Window Log (Exact Precision)

Keeps timestamps in a Redis Sorted Set. Removes timestamps older than 1 minute and counts remaining. 100% mathematically accurate, but memory-heavy ($O(M)$ RAM) because it stores a timestamp for every single request.

5Sliding Window Counter (Cloudflare Hybrid Standard)

Combines fixed windows with a weighted rolling average formula:Requests = (Current Window Count) + (Previous Window Count × (1 - Time Elapsed Fraction))Provides 99.95% accuracy with $O(1)$ memory!

⚡ 3. Eliminating Distributed Race Conditions with Redis Lua Scripts

When 50 API servers connect to a centralized Redis cache, naive code has a severe race condition:

❌ Naive Code (Race Condition)

tokens = redis.get(user_id)
if tokens > 0:
    redis.set(user_id, tokens - 1)
    return ALLOW

Under high concurrency, 10 parallel threads all read tokens = 1 at the same time and all 10 succeed, exceeding the rate limit!

✅ Atomic Redis Lua Script (EVAL)

-- Executed atomically in Redis single-thread!
local current = redis.call('get', KEYS[1])
if tonumber(current) > 0 then
    redis.call('decr', KEYS[1])
    return 1
end
return 0

⚡ Zero Race Conditions: Redis executes the entire Lua script atomically without locks or context switches.

🌐 4. Standard HTTP 429 Headers Protocol

When a rate limit is exceeded, return HTTP 429 Too Many Requests with standard RFC headers:

HTTP/1.1 429 Too Many Requests

X-RateLimit-Limit: 100 # Allowed requests per window

X-RateLimit-Remaining: 0 # Remaining requests in current window

X-RateLimit-Reset: 1672531200 # UTC Unix timestamp when window resets

Retry-After: 30 # Number of seconds the client must wait before retrying

💻 5. Production Token Bucket Rate Limiter (Multi-Language)

Production Token Bucket rate limiter with automated time refill across 5 languages:

Select Language:

Token Bucket Engine

# Python In-Memory Token Bucket with Timestamp Refill
import time

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate
        self.last_refill = time.time()

    def allow_request(self, tokens_needed: int = 1) -> bool:
        now = time.time()
        elapsed = now - self.last_refill
        # Refill tokens lazily without background cron!
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

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

// C++20 Thread-Safe Token Bucket
#include <chrono>
#include <mutex>

class TokenBucket {
    double capacity, tokens, refillRate;
    std::chrono::steady_clock::time_point lastRefill;
    std::mutex mtx;
public:
    TokenBucket(double cap, double rate) : capacity(cap), tokens(cap), refillRate(rate), lastRefill(std::chrono::steady_clock::now()) {}

    bool allowRequest() {
        std::lock_guard<std::mutex> lock(mtx);
        auto now = std::chrono::steady_clock::now();
        double elapsed = std::chrono::duration<double>(now - lastRefill).count();
        tokens = std::min(capacity, tokens + elapsed * refillRate);
        lastRefill = now;

        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }
};

// Java Token Bucket Rate Limiter
public class TokenBucket {
    private final long capacity;
    private final double refillRate;
    private double tokens;
    private long lastRefillNanos;

    public TokenBucket(long capacity, double refillRate) {
        this.capacity = capacity;
        this.tokens = capacity;
        this.refillRate = refillRate;
        this.lastRefillNanos = System.nanoTime();
    }

    public synchronized boolean tryConsume() {
        long now = System.nanoTime();
        double elapsedSec = (now - lastRefillNanos) / 1e9;
        tokens = Math.min(capacity, tokens + elapsedSec * refillRate);
        lastRefillNanos = now;

        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }
}

// Go Token Bucket with Mutex
package main

import (
    "sync"
    "time"
)

type TokenBucket struct {
    capacity   float64
    tokens     float64
    refillRate float64
    lastRefill time.Time
    mu         sync.Mutex
}

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens = math.Min(tb.capacity, tb.tokens+elapsed*tb.refillRate)
    tb.lastRefill = now

    if tb.tokens >= 1.0 {
        tb.tokens -= 1.0
        return true
    }
    return false
}

// TypeScript Token Bucket Class
export class TokenBucket {
  private tokens: number;
  private lastRefill: number;

  constructor(private capacity: number, private refillRate: number) {
    this.tokens = capacity;
    this.lastRefill = Date.now();
  }

  allowRequest(cost = 1): boolean {
    const now = Date.now();
    const elapsedSec = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSec * this.refillRate);
    this.lastRefill = now;

    if (this.tokens >= cost) {
      this.tokens -= cost;
      return true;
    }
    return false;
  }
}

🧪 6. Interactive Lab: Live Rate Limiter Simulator

⚡ Real-Time In-Flight Throttle

Distributed Rate Limiting Simulator

Fire requests and observe token consumption, refills, and HTTP 429 errors!

1. Algorithm:

2. Single Request:

3. Traffic Surge:

🎟️ Bucket Capacity10 / 10 Tokens

Refilling +2 tokens every second

🌐 Last Response Status

HTTP 200 OK

X-RateLimit-Remaining: 9

📊 Traffic Telemetry

Allowed: 0

Blocked (429): 0

🚀 Rate Limiter Active: Click "Send 1 Request" or "Fire 15-Request Burst" to test throttling!

🎯 7. Test Your Understanding

Scenario 1: The 2x Traffic Boundary Burst

Your API is configured for a limit of 1,000 requests/minute using a Fixed Window Counter. A bot sends 1,000 requests at 00:00:59 and another 1,000 requests at 00:01:01. What happens?

Scenario 2: Distributed Race Condition Prevention

Under high load, 100 API gateway instances concurrently check a user's rate limit in Redis. Why is a Redis Lua Script strictly required over individual GET and DECR commands?

← Module 6.2: Distributed Sagas Curriculum Hub →

Full Deep-Dive Locked