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.

Keeping an exact global count forces every node to consult a shared store on every request. One network round trip attaches to each request, and that store becomes the ceiling on total throughput. Latency and a bottleneck are the price of accuracy.

Guan (2026, arXiv:2602.11741) frames the problem through the CAP theorem. The paper explains that Redis Cluster deployments commonly choose availability and partition tolerance (AP) through data sharding and replication. The choice gives up perfect global consistency and accepts an approximation, and gets scalability and availability in return.

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 removes that flaw by keeping a timestamp for every request, but memory per key grows with request volume. Guan (2026) documents that a Rolling Window built on Redis Sorted Sets runs in O(log N) time through ZADD and ZREMRANGEBYSCORE. The same paper quantifies the accuracy-versus-memory trade against Token Bucket and Fixed Window.

What matters here is atomicity rather than the data structure. Sending the cleanup of expired entries, the count of what remains, and the insertion of a new entry as separate commands leaves gaps where another node interleaves. 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.

Where the counter lives

Choosing the algorithm settles only half the design. Accuracy and latency of the same algorithm change depending on whether the counter sits in a central store, spreads across regions, or lives on the client.

• A central store holds one count and is therefore exact, but the per-request round trip and the store's own throughput set the ceiling.
• 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 chose the approximate side. It multiplies the previous window's request count by the fraction of that window still overlapping the sliding window, 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), so an independent per-PoP count carries meaning 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

Rather than picking one algorithm, Stripe places four limiters in sequence. 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. Fail-open is right when the goal is abuse prevention and cost control. Where a request past the limit breaks consistency or billing on its own, go fail-closed and lower the failure probability by running a redundant store.

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

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 results from a production deployment on a Kubernetes cluster over 90 days at a scale of 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, and learning barely holds 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. A regional approximation multiplies the effective limit by the number of regions, because each region counts independently when one user's traffic spans several of them. The error stays within a controllable range only when the premise holds that Anycast concentrates the same IP on one PoP.

Summary

An exact global count and low latency are hard to obtain together in distributed rate limiting, and as Guan (2026) documents, practice generally leans toward availability. The algorithm choice trades accuracy against memory per key and burst width. The O(N) memory of Sliding Window Log and the 0.003% error of Sliding Window Counter mark the two ends.

The next decision is counter placement. A central Redis is exact but carries round-trip latency and a single bottleneck. Cloudflare-style regional approximation absorbs attacks of 400,000 requests per second on the premise of independent per-PoP counting.

Stripe's four layers and its fail-open choice show that failure modes come in several layers no single algorithm covers. What gets lost when the store dies has to be decided first. Where accuracy equals money or consistency, take a central store and fail-closed. Where the goal is abuse prevention, take approximation and fail-open.