Code10x
ReliabilityIntermediate

A rate limiter that is fair when it is distributed

Every algorithm here is a few lines on one machine. The design question is what happens when there are twenty machines and they disagree.

The brief

Limit each API client to a fixed number of requests per window.

The service runs as many replicas behind a load balancer, and a client's requests land on whichever replica the balancer picks.

Requirements

Functional

  • Reject requests over a client's limit with 429 and a Retry-After
  • Different limits for different clients or tiers
  • Tell a caller how much budget is left before they run out

Non-functional

  • The limiter is on every request, so its own latency is added to every request
  • Failing open and failing closed are both defensible — but only one of them is the decision you made on purpose
  • A limit of 100/min must mean roughly 100/min across the fleet, not 100/min per replica

Back-of-envelope

Assume

  • 20 replicas behind the balancer
  • 10,000 active clients in any given minute
  • A limit expressed per minute

Therefore

  • In-memory per replica: each client sees 1/20th of its traffic per replica, so a 100/min limit becomes an effective 2,000/min across the fleet. The limiter is off by 20×, and it is off by exactly the replica count — which changes every time you scale.
  • Shared counter state: 10,000 clients × a counter and a timestamp is kilobytes. State size is not the problem.
  • Round trips: one shared-store call per request. That call's latency lands on every request, which is the real cost and the reason people reach for local counters in the first place.

The 20× error is the whole reason this is a design question. It is not a bug you would find in testing — with one replica running locally the limiter is perfectly correct.

The interface

429 Too Many Requests · Retry-After: 30For a limiter the API is what you say on the way out, not a route you expose. Retry-After is the difference between a client that backs off and a client that becomes the attack.
X-RateLimit-Limit / -Remaining / -Reset on every responseOn successful responses too, not only on rejections. A client that can see its budget shrinking can slow down; one that only learns at zero can only fail.
PUT /admin/limits/{clientKey} { limit, window, tier }Changing a limit must not need a deploy. The moment you need to raise one customer's limit is an incident, and a deploy is twenty minutes you do not have.

What is stored

counters (shared, in the fast store)key `rl:{clientKey}:{windowStart}` → integer, with a TTL of one window
The window is in the key, so expiry is the store's job and there is no cleanup job to write, monitor or forget. A counter keyed without the window needs someone to reset it, and that someone is a cron nobody notices has stopped.
limitsclientKey → limit · window · tier
Read on every request and changed a few times a month, which is the exact shape that should be cached in the replica for seconds at a time rather than fetched.
sliding window log (only if exactness is required)sorted set per client, member = request id, score = timestamp
Exact, and priced accordingly: one entry per request rather than one integer per client. The decision above chooses the approximation, and this is what it is approximating.

The design

The counter storeOne shared store the replicas agree through, holding a count and a window per client key. Atomic increment-and-read is the operation the whole design rests on.
The algorithmFixed window is one counter. Sliding window log is exact and stores a timestamp per request. Token bucket allows a burst on purpose. Pick for the traffic shape, not for elegance.
The decision pointA filter ahead of the application, so a rejected request never touches business code. In Spring, that is a filter or a gateway route, not a controller.
The response contract429 with Retry-After, and the remaining budget in headers. A limiter that rejects without saying when to come back turns every client into a retry storm.

The decisions

Each of these could go the other way. The choice, the reason, and what it costs — a design that lists only what it chose teaches the choice; one that lists what it gave up teaches the judgement.

Fixed window or sliding window?Chose — Sliding, if the burst at the boundary mattersBecause — A fixed window lets a client send its whole allowance in the last second of one window and again in the first second of the next — 2× the limit in a moment, forever, by design.A sliding log stores a timestamp per request rather than one integer per client. A sliding counter approximates it with two windows and much less memory, and approximate is usually the right answer here.
Fail open or fail closed when the counter store is down?Chose — Fail open, and alarm loudlyBecause — The limiter exists to protect the service from abuse, not to be the reason the service is down. If the store is unreachable, refusing all traffic converts a limiter outage into a total outage.During that window you have no limiter at all, which is precisely when an attacker would like the store to be down. If the limiter is a security control rather than a capacity control, this answer inverts — and knowing which one you are building is the actual question.
One round trip per request, or a local budget?Chose — Start with the round tripBecause — It is correct, and correctness at 20 replicas is the thing the naive design got wrong. Optimise after you can measure the added latency.Every request pays it. When that matters, replicas can lease a slice of the budget locally and reconcile — which reintroduces a bounded amount of the original error, on purpose and with a number attached to it.

What breaks first

In order. Each names what you would actually observe, and each fix carries its cost.

The round trip itself, immediatelySymptom — Every endpoint's p99 rises by the counter store's p99 — not by its mean. The limiter adds latency to requests it allows, which is all of them.Fix — Co-locate the store with the replicas, pipeline the increment and the read into one call, and set a timeout in single-digit milliseconds.Co-location makes the store a per-zone thing, and a per-zone counter is per-zone accuracy — a smaller version of the 20× error the design exists to fix.
One client that is most of the trafficSymptom — That client is one key, one key is one shard, and one shard is one node at capacity while the rest of the cluster idles.Fix — Split the key into a fixed number of sub-counters and sum them, or give the largest clients their own shard.Summing N sub-counters is N reads, and the limit becomes approximate in a new way. You have traded a hot key for a looser guarantee, deliberately.
Connection count, once the fleet growsSymptom — Twenty replicas with a pool each is fine; two hundred is thousands of connections and the store spends its time on connection handling rather than on increments.Fix — A pooling proxy in front of the store.Another hop on the path you were just trying to shorten, and another thing that can be the outage.

When something fails

The counter store is unreachableRequests are allowed and an alarm fires — the decision above, made on purpose. What matters in the code is that 'unreachable' is a short timeout, not a hung socket.
The counter store is slow but upThis is worse than down, and it is the case people forget. Without a hard timeout, a two-second store makes every request two seconds and the limiter takes the service down by itself. Treat slow as down, at a number you chose.
Replica clocks disagreeWindow boundaries land at different instants, so a client at the boundary gets a little more than its limit. Fixed windows make this worse than sliding ones, and it is an argument for deriving the window from the store's clock rather than each replica's.

Scaling it

Each step is triggered by a number, not a feeling — and carries what it costs.

10× clients — 100,000 a minuteMove — Nothing. The estimation already showed state is kilobytes.None, and that is worth saying rather than skipping. Half of scaling is being able to show which numbers do not move.
The added latency becomes unacceptableMove — Replicas lease a slice of each client's budget locally and reconcile periodically.A bounded amount of the original 20× error comes back — bounded, chosen, and written down, rather than emergent from the replica count.
The limit has to be exact, because it is billedMove — Stop counting and start reserving: take the budget before the work, return it if the work did not happen.Two round trips instead of one, and the returns have to survive a crash or the budget leaks. At this point it is a quota system, not a rate limiter, and calling it the right name changes who owns it.

What gets probed

The design is the easy half. These are where the conversation goes, and each has a defensible answer above.

  • You add ten replicas at peak. What happens to every client's effective limit?
  • What is the client key — an API key, an IP, a user? What does each one do to a shared corporate NAT?
  • A client is rejected and retries immediately, forever. What in your design stops that?
  • How would you let one customer burst to 5× for thirty seconds without changing anyone else's limit?