Distributed Rate Limiting

1. What It Is & Why It Exists

The Core Problem

In modern distributed and multi-tenant architectures, uncontrolled incoming traffic poses existential threats to service stability, operational budgets, and security posture:

• DDoS & Malicious Floods: Attackers saturate layer-7 application compute, exhaust HTTP connection pools, and overwhelm memory buffers.
• Resource Starvation ("The Noisy Neighbor Problem"): In multi-tenant environments, an individual rogue or misconfigured tenant consuming thousands of concurrent requests can monopolize database thread pools, degrading availability for all other tenants.
• Downstream Cascading Service Failures: Surges in client requests propagate to backend datastores, third-party payment gateways (e.g., Stripe, Adyen), messaging brokers, or LLM inference endpoints (e.g., OpenAI, Anthropic), resulting in quota bans, cascading brownouts, and massive billing overruns.

The Breakdown: The Naive Counter Breakdown & Boundary Cliff

1. The Distributed Drift Cliff (Uncoordinated Local State)

When microservices scale horizontally across $N$ stateless nodes, maintaining rate limits locally in application server memory (e.g., standard in-process memory maps or Guava caches) creates catastrophic quota amplification. Without centralized synchronization, an authorized threshold of $R\text{ req/min}$ allows up to $N \times R\text{ req/min}$ before any single node triggers throttling.

2. The Fixed-Window Boundary Spike (The 2× Burst Cliff)

Naive rate limiters track requests using discrete time buckets (e.g., 1-minute blocks from 12:00:00 to 12:01:00). If a client concentrates all requests at the tail of the first window and the head of the second window, twice the maximum allowed quota enters the system within a micro-interval, overwhelming downstream infrastructure while technically obeying window quotas.

Concrete Proof: Naive Modulo vs. Fixed-Window vs. Distributed Control

Consider an API with an intended quota of $100\text{ requests/minute}$ distributed across $4$ stateless application nodes:

---

The First-Principles Solution: Distributed Admission Control

A Distributed Rate Limiter is a high-throughput, sub-millisecond admission-control primitive placed at ingress networks (API Gateways, reverse proxies, edge CDNs). It coordinates consumption state against global policies, returning standard HTTP 429 (Too Many Requests) with precise backoff telemetry (Retry-After) when quotas are exhausted.

Synthesizing vector architecture diagram...

Both panels start with the same abusive tenant sending 300 RPS against a 100 RPS limit. In the "Broken Baseline" panel, the load balancer spreads that flood across three nodes, each node sees only 100 RPS, which is exactly its local limit, so all three let everything through and the database receives the full 300 RPS. In the "Production Standard" panel, the gateway checks one shared counter in Redis with an atomic Lua script on every request, so it sees the tenant's true total, lets 100 RPS through to the app, and answers the other 200 with HTTP 429 plus Retry-After. The lesson: a limit is only as good as the counter behind it; local counters give each tenant N times its quota once you run N nodes.

---

2. Core Mechanics & Algorithmic Architecture

Mathematical Formulations of Core Rate Limiting Algorithms

1. Token Bucket Algorithm

A bucket with capacity $C$ continuously replenishes with tokens at a rate of $r$ tokens per second. An incoming request requiring cost $k$ (typically $k=1$) is granted entry if $T \ge k$; otherwise, it is throttled.

Instead of running background daemon ticks to add tokens, token replenishment is calculated deterministically on-demand upon request arrival using time deltas:

$$T_{\text{now}} = \min\left(C, \; T_{\text{last}} + (t_{\text{now}} - t_{\text{last}}) \times r\right)$$ $$\text{Decision} = \begin{cases} \text{ALLOW}, & \text{if } T_{\text{now}} \ge k \implies T_{\text{new}} = T_{\text{now}} - k, \; t_{\text{last}} = t_{\text{now}} \\ \text{THROTTLE}, & \text{if } T_{\text{now}} < k \implies T_{\text{new}} = T_{\text{now}}, \; t_{\text{last}} = t_{\text{now}} \end{cases}$$

2. Leaky Bucket Algorithm

Requests enter a FIFO queue with maximum buffer size $B$ and drain (leak) to backend processing pipelines at a strictly constant rate $L$. If the queue is full ($Q = B$), subsequent incoming requests are dropped or rejected immediately.

$$Q_{\text{now}} = \max\left(0, \; Q_{\text{last}} - (t_{\text{now}} - t_{\text{last}}) \times L\right)$$ $$\text{Decision} = \begin{cases} \text{ALLOW (Enqueued)}, & \text{if } Q_{\text{now}} + 1 \le B \implies Q_{\text{new}} = Q_{\text{now}} + 1 \\ \text{THROTTLE}, & \text{if } Q_{\text{now}} + 1 > B \end{cases}$$

3. Sliding Window Counter Algorithm (Weighted Moving Average)

Combines the ultra-low memory footprint of Fixed Window counters with most of the boundary smoothing of Sliding Window logs, as an estimate: it assumes the previous window's requests were spread evenly, so a client that fills the very end of one window can still get close to 2× the limit into one trailing window. The current rolling count is approximated by weighting the previous window's count proportionally to the overlapping time remaining:

$$\text{Estimated Count} = C_{\text{current}} + C_{\text{previous}} \times \left(1 - \frac{t - t_{\text{window\_start}}}{W}\right)$$

Where:

• $W$ is the total duration of the window (e.g., 60 seconds).
• $t - t_{\text{window\_start}}$ is the time elapsed in the current window.
• Cloudflare's analysis of 400 million requests from 270,000 sources found that assuming an even distribution over the prior window wrongly allowed or rate limited only $0.003\%$ of requests (the estimated rate differed from the real rate by 6% on average).

---

Step-by-Step Deterministic Token Generation & Routing Pipeline

Synthesizing vector architecture diagram...

---

In-Memory State Representation in Redis

To minimize network serialization and memory overhead, rate limit state is stored either as a Redis Hash (for Token Bucket) or dual 64-bit integer counters (for Sliding Window Counter):

---

State-Transition Trace: Token Bucket Under Burst & Depletion

Under configuration capacity $C = 10$, refill rate $r = 2\text{ tokens/s}$, and initial state $(T = 4.0\text{ tokens}, t = 100.0\text{s})$:

Note: On throttled requests the stored state is left unchanged (the §8.3 script writes nothing), so the 0.4 tokens accrued since $t_{\text{last}}$ are recomputed on the next request; storing $(0.4, 102.2\text{s})$ instead gives the same result. Storing $(0.4, 102.0\text{s})$ would count the same 0.2 s of refill twice. $\text{Retry-After} = \lceil (k - T) / r \rceil = \lceil 0.6 / 2 \rceil = 1$.

---

Heterogeneous Tenant Fleet Sizing & Tiered Rules

Modern systems serve users with vastly different contractual entitlements (e.g., Free vs. Pro vs. Enterprise). Distributed rate limiters organize rules into hierarchical descriptor trees:

Synthesizing vector architecture diagram...

Heterogeneous allocation is achieved by adjusting bucket parameters dynamically in policy configurations without recompiling routing gateways.

---

3. Data Migration, Anti-Entropy & Consistency Protocols

Rate-limiting counters are transient, ultra-high-velocity state. Synchronizing this state across multi-zone or multi-region deployments requires balancing accuracy against network latency:

1. Multi-Tier L1/L2 Rate Limiting (Batch Reconciliation)

To eliminate a remote network round-trip on every single API request, high-scale architectures can deploy a two-tiered caching hierarchy (the rate limiter loop, step 2.3, applies it to hot keys only):

• L1 In-Process Local Memory: Each edge gateway node maintains a local, lock-free token bucket. Requests consume local tokens instantly ($< 1\mu\text{s}$).
• L2 Centralized Redis: Gateways batch-deduct tokens asynchronously from central Redis clusters every $\Delta \tau = 50\text{--}100\text{ ms}$, using token leases.
• Max Quota Drift: The maximum quota overage possible across $N$ gateway instances during a sudden synchronized spike is bounded by: $\text{Max Overage} \le N \times (\text{Local Batch Limit})$ (where the batch limit is the most tokens one gateway can hold at once: 1.2 blocks with the loop's refill-at-20% rule, step 2.3).

2. Multi-Region Active-Active Anti-Entropy

When deploying multi-region architectures (e.g., us-east-1 and eu-west-1), cross-region WAN latency ($70\text{--}100\text{ ms}$) prohibits synchronous cross-region coordination for rate limits.

Synthesizing vector architecture diagram...

Start in either region: US clients hit the US gateway, EU clients the EU gateway, and each gateway checks a local Redis in under a millisecond. The global quota is pre-split (60% for us-east-1, 40% for eu-west-1, based on where traffic comes from), so neither region has to ask the other before answering. In the "Asynchronous Anti-Entropy Plane" panel, a small sync service in each Region publishes that Region's usage every second and moves quota toward the busier Region; each Region writes only its own record, so nothing conflicts (Redis OSS, Valkey and ElastiCache have no multi-writer CRDT replication; a CRDT counter would be something you build). You trade a small, temporary overshoot of the global limit for never paying 70-100 ms of cross-region latency on each request.

Multi-Region Strategies:

1. Dynamic Quota Partitioning: A global quota of $10,000\text{ RPS}$ is statically or dynamically split between regions based on historical traffic (e.g., 6,000 RPS to US, 4,000 RPS to EU). Each region enforces its partition locally with zero cross-region latency.
2. Conflict-Free Replicated Data Types (CRDT PN-Counters): Each region tracks its own increments (and, in a PN-counter, its decrements, such as returned tokens) and communicates counter differentials via asynchronous background gossip.

3. Graceful Draining, Token Lease Protocol & Cluster Resharding

• Token Lease Protocol & Draining: Under L1/L2 hierarchical rate limiting, gateways acquire a batch lease of $B$ tokens valid for duration $\tau_{\text{lease}}$ (e.g., $100\text{ ms}$). When an API gateway pod receives SIGTERM during autoscaling or deployments, it invokes a graceful drain hook: unconsumed local tokens are returned to the central bucket by a small script that adds them capped at the bucket's capacity (a bare HINCRBYFLOAT can overfill it), preventing artificial tenant quota exhaustion.
• Cluster Resharding & Redirection Protocols: During Redis slot migration (MIGRATE), commands return ASK <slot> <ip:port> (transient during key move) or MOVED <slot> <ip:port> (permanent migration). Gateway drivers must execute ASKING prior to retrying the target node without invalidating local slot caches, reserving full CLUSTER SLOTS re-polling strictly for MOVED. If redirection latency exceeds the circuit-breaker threshold ($2\text{ ms}$), the client trips to Fail-Open to protect ingress throughput.

---

4. Client-Side vs. Proxy-Mediated Routing Topologies

Synthesizing vector architecture diagram...

The two panels limit traffic in opposite directions. In the "Smart Client Routing" panel, your service is the caller: before each call to an external API it takes a token from an in-memory bucket, and when the provider still replies 429 it waits with exponential backoff and jitter, which protects the partner and your API key. In the "Proxy-Mediated Ingress Limiting" panel, you are the one being called: public traffic enters through the NLB, the Envoy or gateway tier checks a shared Redis counter atomically, clean traffic goes to the backends and excess gets HTTP 429. Real systems need both: egress limits so you are a good client, and ingress limits so no client can overload you.

Trade-Off Matrix

---