Track 1 · Foundations
mediumRate Limiter
Decide, in under a millisecond and across a whole fleet, whether this request is allowed through. The algorithm choice and the counter-sharing problem are the two real questions.
Suggested architecture
Scenario
A limiter's own cost is one atomic increment per request, so the counter store sees everything. What it rejects never reaches the upstream — which is the point, and the number to watch.
Everything arriving at the gateway, allowed or not.
Share of requests over their limit. The limiter still pays for each one; the upstream does not.
Stateless apart from a local rules cache.
Redis nodes holding the windows. Shard by client key so a hot tenant lands on one node — and watch that node.
Click a component for its role, common technology choices and tradeoffs, and what it is carrying at this scale. Hover a connection to see what flows along it. Drag to rearrange — layout changes are local and reset on reload.
Every figure here is a rough estimate from simple capacity arithmetic, not a benchmark. Each part carries its own assumption about what one copy can do — real numbers depend on your hardware, payloads and access pattern. The point is which component moves first as you turn the dials, not the digits themselves.
In plain words
A rate limiter decides, for every request, whether this caller has done too much recently — and says no if so. It protects a system from abuse, from a buggy client in a loop, and from itself. The two questions are how to count (the algorithm) and where the count lives when there are many servers doing the counting.
The shape of the problem
A rate limiter has an unusual constraint: it runs on every single request, including the ones it is about to reject. Any design that costs 5 ms per check has made the system slower for everyone in order to protect it. So the real question is not "which algorithm is most accurate" but "which algorithm is accurate enough at one cheap atomic operation per request" — atomic meaning done in one indivisible step, so two requests cannot interleave and both slip through.
There are two hard parts, and they are independent:
- Which algorithm — how bursts are treated, and how much memory each key costs.
- Where the counter lives — because a fleet of N gateways each enforcing the limit locally enforces N times the limit.
The algorithms
| Algorithm | Memory per key | Burst behaviour | The catch |
|---|---|---|---|
| Fixed window | 1 counter | Allows 2× at a window boundary | Simple, cheap, and visibly wrong at edges |
| Sliding window log | 1 timestamp per request | Exact | Memory grows with traffic — unusable at high volume |
| Sliding window counter | 2 counters | Approximates the log well | Slight inaccuracy, assumes even distribution in the previous window |
| Token bucket | 2 numbers (tokens, last refill) | Allows a controlled burst, then steady rate | Burst size is a second parameter to reason about |
| Leaky bucket | 1 queue | Perfectly smooth output | Queues requests, adding latency; no burst allowance at all |
Fixed window is the one to understand as a failure case. With a limit of 100/minute, a client sends 100 requests at 11:59:59 and 100 more at 12:00:00 — 200 requests in one second, both windows technically respected.
Token bucket is the usual answer. It stores two numbers, refills lazily (compute tokens from elapsed time on read rather than running a timer), and its burst allowance matches how real clients behave — bursty, then idle. Sliding window counter is the other good answer when you want to forbid bursts outright.
Making it correct across a fleet
Ten gateway instances, a limit of 100/min, and per-instance counters means a real limit of 1 000/min. Three ways out:
- Shared atomic counter. All instances
INCRthe same key in Redis. Correct, but adds a network round trip to every request and creates a hard dependency. - Local counters, periodic sync. Each instance limits to its share and swaps totals with the others every few hundred milliseconds. Fast and failure-tolerant, but briefly over-permissive — fine for abuse prevention, not for billing quotas.
- Sticky routing by key. Hash the rate-limit key at the load balancer so one key always lands on one instance. Now local counters are correct, at the cost of an uneven load distribution and a rebalancing problem when instances change.
The atomicity detail matters: GET, decide, SET is a race. Use INCR (atomic by
itself) or a small Lua script, which Redis runs as one unit, so the
read-decide-write happens as one operation.
Failing open
The counter store will be unavailable at some point. If the limiter treats that as "reject everything", a Redis blip becomes a full outage of a service that was otherwise healthy. Almost always the right choice is fail open: let traffic through, emit a loud metric, and accept that you were briefly un-protected. The exception is when the limit exists for correctness or cost control rather than abuse prevention — a metered paid API, for example.
What to return
A 429 ("Too Many Requests") with a Retry-After header is the baseline. Returning X-RateLimit-Limit,
X-RateLimit-Remaining, and X-RateLimit-Reset on every response — not just
rejections — is what actually makes a client well-behaved, because it can slow
itself down before it gets rejected at all.
Where this design breaks
- Keying on IP. Everyone behind one NAT (one public address shared by a whole office or household) shares a bucket; a distributed attacker gets a fresh bucket per address. IP is a last resort for unauthenticated traffic.
- Hot keys. One extremely active token concentrates all its counter writes on a single Redis key, and therefore a single shard.
- Many rules per key. Checking 100/min, 5 000/hour and 50 000/day means three counter operations, not one. Send them as one batch (a pipeline) so it is a single round trip.
- Retry storms. Every rejected client retrying at exactly
Retry-Afterproduces a synchronised wave. Jitter the value you hand back — see retries, backoff and jitter.
Take this with you
- The one idea: the check runs on every request, so it must cost one cheap atomic operation — and the count must be shared, or N servers enforce N× the limit.
- In an interview, name token bucket, explain the fixed-window edge case, and say where the counter lives and what happens when that store is down.
- At work, return the
X-RateLimit-*headers on every response, and decide on purpose whether your limiter fails open or closed.