Distributed Rate Limiting: Protecting Services and Managing Capacity at Cloud Scale

In internet-scale cloud applications and multi-tenant architectures, unconstrained incoming traffic poses severe risks: malicious Denial-of-Service (DoS) attacks, cascading failures triggered by buggy client retry storms, resource starvation by noisy neighbors, and unexpected cloud infrastructure billing spikes.

Rate limiting governs the frequency with which a client (identified by IP address, user ID, or API key) can invoke system endpoints within a sliding time duration. In a distributed deployment with hundreds of stateless API servers or edge proxies, rate limiting must transition from simple in-memory process counters to horizontally scalable, low-latency distributed coordination architectures capable of making millisecond throttling decisions.

Algorithmic Primitives: Mechanisms and Trade-offs

Rate limiters rely on distinct mathematical models depending on whether burstiness or smooth steady-state pacing is required:

1. Token Bucket

• Mechanism: A bucket holds up to a maximum burst capacity of $B$ tokens. Tokens refill continuously at a fixed sustained rate of $r$ tokens per second. Every incoming request attempts to consume 1 (or $k$) tokens; if enough tokens exist, the request passes; otherwise, it is dropped or delayed.
• Strengths: Allows controlled traffic bursts up to $B$ while enforcing a rigid average rate limit $r$. Extremely memory-efficient since it only tracks two numerical variables: `last_refill_timestamp` and `current_token_count`.

2. Leaky Bucket

• Mechanism: Requests enter a FIFO queue (the bucket) of capacity $B$ and are dequeued and processed at a strictly constant rate $r$, regardless of incoming burst volume. If the queue overflows, new requests leak over the edge and are immediately rejected.
• Strengths: Produces a smooth, predictable egress traffic profile, ideal for rate-limiting calls to sensitive downstream third-party APIs or physical disk write queues.

3. Fixed Window Counter vs. Sliding Window Log

• Fixed Window: Divides the timeline into static buckets (e.g., 12:00:00 to 12:01:00). Suffers from the boundary burst problem: a client sending $N$ requests at 12:00:59 and $N$ requests at 12:01:01 bypasses the limiter and drives $2N$ requests across a 2-second window.
• Sliding Window Log: Stores timestamps of all requests in a sorted set and removes timestamps older than `now - window_size`. Completely accurate, but memory-prohibitive for high-throughput endpoints ($O(N)$ storage per client).

4. Sliding Window Counter (Hybrid Memory-Optimal)

Approximates sliding window counts by blending the counts of the current and previous fixed windows without storing individual request timestamps:

Provides 99.9% accuracy while requiring only two integer counters per key.

Distributed Coordination: Centralized Stores vs. Local Batching

Enforcing rate limits across fleets of distributed API instances requires coordinating state across physical machines:

1. Centralized Shared State (Redis + Atomic Lua)

API gateways check and decrement counters stored in a shared Redis cluster. To prevent race conditions (time-of-check to time-of-use bugs where concurrent requests bypass limits), all token refill and decrement steps run atomically inside a single **Redis Lua Script** via `EVALSHA`, completing in a single round-trip without distributed locks.

2. Batch Token Reservation (Mitigating Redis Bottlenecks)

When aggregate cluster throughput reaches millions of requests per second, querying a centralized Redis instance on every single HTTP request saturates network interfaces and adds 1-2 ms of network latency. High-performance gateways employ **Token Batching**:

1. Local API nodes request a batch of tokens (e.g., 50 tokens) from the central Redis cluster in a single RPC.
2. The API node satisfies subsequent client requests entirely from its local in-memory pool with zero network latency.
3. The node asynchronously refills its local batch before exhaustion. If a node crashes, only its unused batch slice is lost.

C++ Conceptual Simulation Blueprint (Sliding Window Counter Engine)

#include <iostream>
#include <string>
#include <unordered_map>
#include <chrono>
#include <algorithm>

struct ClientWindowState {
    uint64_t currentWindowId = 0;
    uint32_t currentCount = 0;
    uint32_t previousCount = 0;
};

class DistributedSlidingWindowLimiter {
private:
    uint64_t windowDurationSec;
    uint32_t maxAllowedPerWindow;
    std::unordered_map<std::string, ClientWindowState> store;

public:
    DistributedSlidingWindowLimiter(uint64_t duration, uint32_t maxRequests)
        : windowDurationSec(duration), maxAllowedPerWindow(maxRequests) {}

    bool allowRequest(const std::string& clientId, uint64_t currentEpochSec) {
        uint64_t activeWindowId = currentEpochSec / windowDurationSec;
        auto& state = store[clientId];

        // 1. Advance window state based on time progression
        if (state.currentWindowId == activeWindowId) {
            // Same window: no rotation required
        } else if (state.currentWindowId + 1 == activeWindowId) {
            // Advanced by exactly 1 window: slide current into previous
            state.previousCount = state.currentCount;
            state.currentCount = 0;
            state.currentWindowId = activeWindowId;
        } else {
            // Advanced by >= 2 windows: previous counts have fully expired
            state.previousCount = 0;
            state.currentCount = 0;
            state.currentWindowId = activeWindowId;
        }

        // 2. Compute sliding window weighted overlap
        double timeInCurrentWindow = static_cast<double>(currentEpochSec % windowDurationSec);
        double previousWindowWeight = 1.0 - (timeInCurrentWindow / static_cast<double>(windowDurationSec));
        
        double estimatedTotal = state.currentCount + (state.previousCount * previousWindowWeight);

        // 3. Admission decision
        if (estimatedTotal < maxAllowedPerWindow) {
            state.currentCount++;
            return true; // Request Allowed
        }
        return false; // Throttled (HTTP 429 Too Many Requests)
    }
};

Real-World Cloud & Edge Implementations

1. Envoy Proxy Global Rate Limiting Service (RLS): Uses an out-of-process gRPC service backed by Redis to enforce global rate limits across entire Kubernetes ingress fleets.
2. Cloudflare & Fastly Edge Rate Limiting: Deploys sliding-window counter estimators across globally distributed Anycast edge PoPs, synchronizing cross-datacenter aggregates via asynchronous delta streaming.
3. Stripe & GitHub API Gateways: Implements tiered token bucket algorithms paired with localized Redis Lua scripts to return standard RFC 6585 rate-limiting response headers (`X-RateLimit-Remaining`, `Retry-After`).
4. AWS API Gateway & Amazon WAF: Managed token bucket controls allowing clients to configure steady-state limits (RPS) alongside burst bucket sizes per API key or usage plan.