Distributed Rate Limiting Architecture

The variable that separates designs is not the algorithm but where the counter lives and how much drift the service can absorb.

Why a global count is expensive

Counting requests on a single node is not hard. Increment a counter, compare it against a threshold, and bind the two operations atomically. The cost of that same work changes the moment it spans several nodes and regions.

Checking a global count in a shared store on every request adds a network round trip to the request path. Preallocated quotas can allow local decisions, but add quota redistribution and idle-capacity costs.

The Redis Cluster specification documents asynchronous replication and possible loss of acknowledged writes. A minority partition cannot keep accepting writes indefinitely, so describing it simply as an AP system is inaccurate.

So the first question in practice is not how to count exactly. It is how much drift the service can tolerate, and what shape that drift takes when it reaches users. A payment limit and abuse prevention on a public API cannot share the same error budget.

What the algorithm decides about accuracy and memory

Choosing an algorithm trades accuracy against memory per key and against how much burst gets through. The error budget set earlier narrows the candidates.

The boundary problem in Fixed Window is structural. Under a limit of 100 per minute, sending 100 requests at second 59 and another 100 at second 61 pushes 200 requests through in two seconds. The flaw comes from counting only relative to the reset point.

Sliding Window Log records a timestamp per request, so memory per key grows with request volume. A single ZADD insertion takes O(log N). ZREMRANGEBYSCORE also processes M removed entries, giving O(log N + M).

What matters here is atomicity rather than the data structure. Separate commands for expired-entry cleanup, remaining-entry counting, and new-entry insertion allow another node's operations to interleave. Binding the three operations into one server-side Lua script is what removes the race condition.

Rule changes are handled in the same place. Hashing the limit parameters into the key allows the threshold or the window length to change without touching the cached script.

GCRA (Generic Cell Rate Algorithm) expresses the same behavior as Token Bucket with a single timestamp. The smaller state is why it appears mostly in gateway and proxy layers.

sequenceDiagram
    participant A as Request A
    participant R as Redis primary
    participant B as Request B
    A->>R: Lua decision request
    Note over R: Remove expired entries, count, insert if allowed
    B->>R: Decision request for the same key
    R-->>A: Allow or reject
    Note over R: Decide B against the state left by A
    R-->>B: Allow or reject

A competing request must not interleave between checking a counter and inserting the new entry. Atomicity resolves competition on one primary; it does not replace durability across replication failures.

Where the counter lives

Choosing the algorithm settles only half the design. Counter placement changes an algorithm's accuracy and latency. The counter can reside in a central store, across regions, or on the client.

flowchart TD
    subgraph central["Central store"]
        A1["App node<br/>receives request"] --> A2["Redis cluster<br/>atomic Lua decision"]
        A2 --> A3["Global accuracy<br/>one extra round trip per request"]
    end
    subgraph regional["Regional approximation"]
        B1["PoP local memory<br/>immediate decision"] --> B2["Memcache counter<br/>async background increment"]
        B2 --> B3["Above threshold<br/>mitigation signal inside the PoP"]
    end
    subgraph clientside["Client cooperation"]
        C1["Client<br/>infers congestion"] --> C2["Reschedules retries<br/>avoids 429 responses"]
    end

• A central store counts atomically on one primary, but round-trip cost and record loss during failures still need consideration.
• Regional approximation ends the decision locally and drops the round trip, at the cost of an effective limit that multiplies with the number of regions.
• Client cooperation uses no server state at all and costs the least, but it assumes clients follow the rules.
• The three placements are not exclusive. Stripe, discussed below, stacks several layers on a central Redis, and Cloudflare combines local memory with a PoP-shared counter.

Cloudflare's published case uses approximate counters. It multiplies the previous window's request count by the fraction still overlapping the sliding window. It then adds the current window's count. Consider a limit of 50 per minute, with 42 requests in the previous window and 18 requests 15 seconds into the current one. The remaining 45 seconds of the previous window still overlap, so the estimate is 42 × (45/60) + 18 = 49.5.

The measured error was small. Across a sample of roughly 4 million requests, the share incorrectly allowed or incorrectly limited was 0.003%. The mean error of the estimated rate was about 6% against the actual value. Three false negatives exceeded the threshold by as much as 15% and still passed, and there were zero false positives against legitimate traffic.

Routing is what makes the approximation hold. Anycast sends traffic from the same IP to the nearest PoP (Point of Presence, a data center). This routing makes independent per-PoP counting meaningful without central aggregation. Inside a PoP, Twemproxy spreads load across several Memcache servers with consistent hashing, which keeps key redistribution minimal when the cluster size changes.

The decision path has two stages. An incoming request consults the local memory cache first, and the Memcache counter is incremented asynchronously in the background. Once the threshold is crossed, a mitigation signal propagates to every server in the PoP, and later requests no longer consult Memcache. Cloudflare reports mitigating attacks of 400,000 requests per second on this structure without degrading service for legitimate users.

The third placement is the client. Farkiani et al. (2025, arXiv:2510.04516, accepted at IEEE CCNC 2026) address the shared-quota case. Several independent clients draw on one quota, and their retries fail repeatedly because none of them sees the others' load. The proposed ATB runs offline and can be deployed through a service worker, while AATB uses aggregated telemetry.

Both algorithms infer system congestion and schedule retries accordingly, cutting HTTP 429 (Too Many Requests) responses by up to 97.3% against exponential backoff. Completion time rises slightly, and the authors state that the reduction in errors offsets it. They point out that server-side control is more secure but inefficient. The client side works with minimal feedback and no central coordination, yet it depends on clients being willing to cooperate. This placement cannot be used where malicious clients have to be assumed.

Failure modes one layer cannot cover

Stripe's published case describes four limiters serving different purposes. Request floods, slow requests piling up, infrastructure saturation, and worker exhaustion each bring a service down in a different way.

A Redis cluster carries the shared state and counts requests per type centrally. The decision that splits designs here is behavior when the store fails. Stripe integrated the limiters into middleware as fail-open so the API keeps serving even when Redis is down.

Choosing between fail-open and fail-closed is a comparison of risks, not a matter of taste. Fail-open lifts the limit while the store is down and lets the systems behind it take the full load. Fail-closed blocks legitimate traffic when a single limiting layer dies, which widens the incident instead of containing it.

The criterion is what the rate limiter is actually protecting. Even abuse prevention requires comparing the cost of lifting limits with the cost of an outage. If exceeding a limit breaks consistency or billing, use fail-closed behavior and a durable final decision. Redundancy alone does not guarantee preservation of acknowledged counts.

Operational tooling deserves the same attention. Each Stripe limiter can be turned off immediately through a feature flag. Before gradual rollout, each ran against real traffic in decision-only mode, called dark launching. A misconfigured limit rule is itself an incident, so a path back matters as much as the choice of algorithm.

flowchart TD
    A["Shared store does not respond"] --> P{"Configured failure policy"}
    P -->|fail-open| O["Continue requests<br/>Higher downstream load and cost"]
    P -->|fail-closed| C["Reject requests<br/>Legitimate users affected too"]
    O --> M["Failure metrics and decision records"]
    C --> M

Record store failures separately from actual quota exhaustion. Treating both as the same outcome makes it difficult to distinguish expected limiting from an outage.

Adaptive policy and limits pointing outward

Fixed parameters drift out of alignment as soon as traffic patterns change. Starting from that observation, Lyu et al. (2025, arXiv:2511.03279) model microservice state as a Markov Decision Process (MDP). They then learn the limiting policy itself through a hybrid of DQN (Deep Q-Network) and A3C (Asynchronous Advantage Actor-Critic).

They report a 90-day production deployment on a Kubernetes cluster. It handled 500 million requests per day. Throughput rose 23.7%, P99 latency fell 31.4%, service degradation incidents fell 82%, and manual intervention fell 68%. What separates this from the earlier patterns is that the policy comes from data instead of human tuning.

Everything so far concerned the inbound direction, blocking requests arriving from outside. The outbound direction, where a system throttles the load it places on external or downstream dependencies, has the same problem structure.

Toss Securities faced more than one million reserved orders reaching an external broker at once at market open, overloading it. The fix was the RateLimiter from resilience4j. A transactions-per-second (TPS) value passed as a batch parameter creates the RateLimiter object dynamically, and requests go to the broker only within that limit.

During the market open window, TPS climbs more than 20 times above normal, and this control eased broker response latency there. It also gave the automatic failover system a working foundation for the broker issues that followed.

Woowa Brothers addressed a case where scaling Kafka consumers horizontally still left throughput bounded by a dependency. Once the master database's CPU utilization spikes above 80%, adding consumers achieves nothing. Their record comparing three throttling approaches makes the reasoning behind the final choice readable.

Thread.sleep() keeps the heartbeat alive but stops poll(), which risks a rebalance. pause()/resume() keeps calling poll and returns empty records, which avoids the rebalance. ConsumerInterceptor applies the delay at commit time. The final choice monitors CPU utilization and computes a quadratic delay that is applied dynamically to per-partition containers.

Choosing the combination

One algorithm or one pattern rarely finishes the job. Start from the requirement and decide the algorithm, the counter placement, and the failure behavior as a single bundle.

The numbers in the table come from each organization's traffic distribution and do not transfer as they are. Cloudflare's 0.003% came from a sample of roughly 4 million requests, and a different request distribution yields a different error rate. Setting an error budget from someone else's benchmark means discovering the gap during the first incident.

The adaptive numbers carry a heavier premise. They require 90 days of learning data at 500 million requests per day and an operation of matching size. Learning is difficult on a low-traffic service. Explaining after the fact why the policy decided as it did also remains difficult.

The limits of approximation itself are equally clear. If one user's traffic spans several regions, each region counts it independently. Regional approximation therefore multiplies the effective limit by the number of regions. The error stays within a controllable range only when the premise holds that Anycast concentrates the same IP on one PoP.

Summary

Distributed rate limiting requires choosing algorithm accuracy, counter placement, and failure policy together. Atomic operations on one primary prevent competing requests from interleaving, but do not guarantee record durability during replication failures. Regional approximation reduces latency while allowing drift in the global limit. Compare the costs of lifting limits and refusing service, and enforce final money or inventory limits at a durable processing boundary.