Distributed Rate Limiting at 10 Million RPS: Sliding Windows, Token Buckets, and Redis Cells

Introduction / Executive Summary

At scale—defined here as 10 million requests per second (RPS)—rate limiting shifts from a simple API gateway middleware concern into a distributed systems consistency, memory bandwidth, and network topology problem. When a tier-1 internet service experiences a thundering herd, a cascading failure, or a malicious credential stuffing attack, the rate-limiting subsystem is the first and often only line of defense protecting core transactional storage engines and downstream microservices from catastrophic collapse.

Consider the operational envelope: processing $10^7$ requests per second means handling $10$ million state lookups, updates, and evaluations every single second. If each rate-limit evaluation incurs a conservative round-trip time (RTT) of $1.0\text{ ms}$ to a centralized data store, the system requires $10,000$ concurrent network connections and an unsustainable CPU overhead just to manage socket state, completely independent of the actual application business logic. Furthermore, modern microservice meshes span multiple availability zones (AZs) and geographical regions, introducing network partition risks, clock drift, and cache synchronization challenges that violate the assumptions of single-node token bucket algorithms.

This dispatch deconstructs the engineering mechanics of massive-scale distributed rate limiting. We examine the physical and protocol boundaries of network I/O, evaluate fundamental algorithmic trade-offs (Fixed Window, Sliding Window Log, Sliding Window Counter, Token Bucket, and Leaky Bucket), dive into production-grade implementations using Go and Redis/Lua, and analyze the failure modes, memory layouts, and hardware acceleration techniques required to sustain ultra-low tail latencies at extreme scales.

Part 1: First Principles and Hardware / Physical / Protocol Foundation

To understand why naïve rate-limiting architectures fail at 10 million RPS, we must first analyze the physical constraints of modern server hardware, network interface cards (NICs), and memory buses.

The Memory Bandwidth Bottleneck

At $10^7$ RPS, if every request requires an atomic counter increment in RAM, we must examine the physical memory bandwidth of a standard dual-socket server. Assuming a cache-line size of $64$ bytes, and a hypothetical distributed in-memory data store where each client's rate-limiting state occupies a minimal $32$ -byte payload, the raw memory read/write throughput required is:

$\text{Throughput} = 10^6 \text{ or } 10^7 \text{ ops/sec} \times 32 \text{ bytes} \approx 320 \text{ MB/sec} \text{ to } 3.2 \text{ GB/sec}$

While $3.2\text{ GB/sec}$ appears modest compared to modern DDR5 multichannel memory bandwidths (which exceed $60\text{ GB/sec}$ per channel), cache coherence protocols (MESI/MOESI), multi-core bus contention (UPI/Infinity Fabric), and lock contention on atomic instructions ( $_InterlockedIncrement$ or LOCK XADD on x86) create severe serialization bottlenecks. A centralized locking structure will instantly saturate core interconnects, spiking tail latency ( $ext{p999}$ ) into hundreds of milliseconds.

Network Latency and Serialization Bounds

Network round-trip times within a localized datacenter are bounded by the speed of light in fiber optic cables ( $\approx 200,000\text{ km/s}$ ) and switch serialization delays. The minimum physical latency between two nodes in the same rack is approximately $200\mu\text{s}$ to $500\mu\text{s}$ . If a gateway process must make a synchronous network hop to a centralized Redis cluster for every incoming HTTP request, the latency equation becomes:

$T_{\text{total}} = T_{\text{tcp\_stack}} + T_{\text{serialization}} + T_{\text{network\_rtt}} + T_{\text{store\_execution}} + T_{\text{deserialization}}$

At 10 million RPS, centralized coordination is a physical impossibility without sharding, local caching, and asynchronous batching. We must transition from synchronous remote procedure calls (RPCs) to decentralized, eventually-consistent, or tightly sharded architectures that push state evaluation to the network edge.

Part 2: Algorithmic Mechanics and Detailed State Machine / Protocol Flow

Selecting the correct rate-limiting algorithm dictates both memory consumption and fairness guarantees under bursty workloads.

1. Fixed Window Counter

The simplest algorithm divides time into discrete, static windows (e.g., every minute: 00:00, 01:00). A counter is maintained for each client key.

Pros: Minimal memory footprint ( $\mathcal{O}(1)$ per key) and trivial implementation.
Cons: Boundary burst vulnerability. A client can consume their entire quota at 00:59 and consume another full quota at 01:00, effectively executing $2 \times N$ requests within a single $1$ -minute sliding duration.

2. Sliding Window Log

Stores a sorted set (ZSET in Redis) of timestamps for every request made by a client. When a new request arrives, timestamps older than the current window minus the window size are pruned, and the cardinality of the set is checked.

Pros: Perfectly accurate, eliminates boundary bursts.
Cons: Unbounded memory consumption ( $\mathcal{O}(N)$ where $N$ is the number of requests per window). At 10 million RPS, storing millions of individual timestamps per active user destroys memory caches.

3. Sliding Window Counter (Hybrid Approach)

Combines the fixed window approach with a weighted calculation of the previous window's request volume.

$\text{Current Count} = \text{Previous Window Count} \times \left(1 - \frac{\text{Current Timestamp Offset}}{\text{Window Size}}\right) + \text{Current Window Count}$

Pros: Constant memory ( $\mathcal{O}(1)$ ), highly accurate approximation without storing raw logs.
Cons: Assumes uniform request distribution across the previous window, which can introduce minor error margins during sudden traffic cliffs.

4. Token Bucket & Leaky Bucket

The Token Bucket algorithm maintains a bucket of capacity $b$ that fills with tokens at a constant rate $r$ . Each request consumes 1 token. If the bucket is empty, the request is dropped.

$\text{Tokens}(t) = \min\left(b, \text{Tokens}(t_0) + (t - t_0) \times r\right)$

[Client Request] ---> ( Rate Limiter Gateway )
                           |-- Token Bucket Check (Local Memory / Sharded Redis)
                           |----> [Allowed]   ---> Forward to Microservice
                           |----> [Exhausted] ---> Return HTTP 429 Too Many Requests

Part 3: Concrete Implementation and Code Analysis

To achieve ultra-low latency at scale, we implement a highly optimized, thread-safe Token Bucket rate limiter in Go, coupled with an atomic Lua script for distributed Redis coordination.

Go In-Memory Local Rate Limiter (Token Bucket)

package ratelimiter

import (
	"sync/atomic"
	"time"
)

type TokenBucket struct {
	capacity       int64
	tokens         int64
	refillRatePerNs int64
	lastRefill     int64
}

func NewTokenBucket(capacity int64, refillRatePerSec int64) *TokenBucket {
	return &TokenBucket{
		capacity:        capacity,
		tokens:          capacity,
		refillRatePerNs: refillRatePerSec,
		lastRefill:      time.Now().UnixNano(),
	}
}

func (tb *TokenBucket) Allow(tokensRequested int64) bool {
	now := time.Now().UnixNano()
	last := atomic.LoadInt64(&tb.lastRefill)
	
	// Calculate elapsed time and generated tokens
	elapsed := now - last
	if elapsed <= 0 {
		return tb.consume(tokensRequested)
	}
	
	// Atomic refill calculation
	generated := (elapsed * tb.refillRatePerNs) / int64(time.Second)
	if generated > 0 {
		if atomic.CompareAndSwapInt64(&tb.lastRefill, last, now) {
			// Safely add tokens up to capacity
			for {
				currentTokens := atomic.LoadInt64(&tb.tokens)
				newTokens := currentTokens + generated
				if newTokens > tb.capacity {
					newTokens = tb.capacity
				}
				if atomic.CompareAndSwapInt64(&tb.tokens, currentTokens, newTokens) {
					break
				}
			}
		}
	}
	
	return tb.consume(tokensRequested)
}

func (tb *TokenBucket) consume(n int64) bool {
	for {
		current := atomic.LoadInt64(&tb.tokens)
		if current < n {
			return false
		}
		if atomic.CompareAndSwapInt64(&tb.tokens, current, current-n) {
			return true
		}
	}
}

Distributed Redis Lua Script (Redis Cells / Token Bucket)

To synchronize state across multiple API gateway nodes without race conditions, we execute an atomic Redis Lua script.

-- KEYS[1]: Rate limiter key
-- ARGV[1]: Capacity
-- ARGV[2]: Refill rate per second
-- ARGV[3]: Current timestamp (microseconds)
-- ARGV[4]: Requested tokens

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'last_updated')
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_updated = now
else
    local delta = math.max(0, now - last_updated)
    local tokens_to_add = (delta / 1000000) * refill_rate
    tokens = math.min(capacity, tokens + tokens_to_add)
    last_updated = now
end

if tokens < requested then
    return {0, math.floor(tokens)}
else
    tokens = tokens - requested
    redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)
    redis.call('EXPIRE', key, math.ceil(capacity / refill_rate))
    return {1, math.floor(tokens)}
end

Part 4: Production Trade-offs, Failure Modes, Benchmarks, and Edge Cases

Deploying rate limiters at 10 million RPS introduces complex failure modes that test the resilience of the entire architecture.

1. Network Partitions and Split-Brain Scenarios

When deploying a distributed Redis cluster, a network partition can split nodes across availability zones. If the rate limiter relies on strict linearizability (CP in the CAP theorem), availability drops during partitions. For rate limiting, Availability and Low Latency (AP) are prioritized over strict linearizability. If Redis becomes unreachable, gateways fail-open (allowing traffic through while logging telemetry) or fall back to local in-memory approximations, preventing the rate limiter from becoming a single point of failure (SPOF) that takes down the entire application.

2. The Thundering Herd and Hot Key Problem

Global resources (e.g., rate limiting the root login endpoint or a viral API route) create extreme hot keys in Redis clusters. Sharding keys by hashing ClientID + IP + Route + Salt distributes the load across hash slots. Furthermore, implementing Local Token Bucket Leaching at the API gateway layer reduces centralized Redis calls by 95%: gateways pull tokens in bulk batches (e.g., blocks of 1,000 tokens) via a single atomic Redis operation, locally draining them before requesting a refill.

3. Observability and Telemetry Overhead

At 10 million RPS, emitting structured logs (stdout/stderr) for every rate-limit check will exhaust disk I/O and CPU. Telemetry must be aggregated in-memory using ring buffers and emitted asynchronously via metrics sliding windows (Prometheus histograms, OpenTelemetry counters) with probabilistic sampling.

Conclusion & Future Outlook

Designing a distributed rate-limiting infrastructure for 10 million RPS requires abandoning monolithic, synchronous state coordination in favor of layered, decentralized architectures. By combining local, lock-free in-memory token buckets with bulk-refilled, sharded Redis backends via atomic Lua scripts, systems engineers can achieve sub-millisecond tail latencies while maintaining strict traffic governance.

As systems evolve toward eBPF (Extended Berkeley Packet Filter) and kernel-bypass networking (DPDK, Solarflare OpenOnload), rate-limiting logic is increasingly shifting downward from user-space application runtimes directly into the network interface controller and Linux kernel transport layers. Mastering these trade-offs ensures resilience, predictability, and uncompromising performance under the most extreme traffic loads.