Every public API eventually gets a rate limiter, and almost every first version is a counter in a hash map with a threshold check. That version works on one machine, in one process, in a demo. It stops working the moment you run more than one server, and it stops being correct long before anybody notices, because a rate limiter fails quietly. It lets through twice what you allowed, or it rejects a customer who was inside their budget, and unless you are measuring the decision itself you will not see either one.
The interesting part is not the counting. It is that a rate limit is a global assertion about a distributed system, evaluated on the hot path of every request, under a latency budget measured in fractions of a millisecond, against shared state on another machine. You have to choose an algorithm whose error you can characterize, a place to keep the state, an atomicity strategy, a memory model, and a behavior for when the state store is unreachable. Get those five right and the limiter is invisible. Get them wrong and the limiter is what takes your API down.
We start with requirements and arithmetic, walk the four candidate algorithms and characterize exactly how each one is wrong, pick between token bucket and sliding window on the evidence, and then spend the second half on the part interviews skip: making it correct across a fleet, sizing the store, handling hot keys, and deciding what happens when the shared state is gone. Every latency, throughput, and memory number here is an industry-typical estimate used to drive sizing, not a measured metric from a particular production service.
What we are actually building
Strip the problem down and the functional surface is one call. Given an identity and a request, return allow or deny, and if deny, say how long to wait. Everything else is packaging.
The constraints are where the design lives, and they are tight because of where this component sits. The limiter runs before the work, on every request, so its cost is pure overhead added to the fastest and the slowest endpoint alike. If the median API call is 40 milliseconds, a limiter that adds 2 milliseconds has taxed you 5 percent for nothing a user can see. The budget I would defend is under 1 millisecond added at p99, which in practice means at most one network round trip to a store in the same availability zone, and no round trip at all on the common path if you can avoid it.
The constraint ladder for a rate limiter, from the numbers that set the memory budget up to the latency and blast-radius rules that decide the architecture.
Now the arithmetic, because it decides the storage choice before any component does. Take a gateway fronting a public API at 200,000 requests per second at peak, 50 million registered API keys, of which roughly 2 million are active in any given minute, and a default limit of 1,000 requests per minute per key. Two numbers fall out. First, the limiter performs 200,000 decisions per second, more than a single Redis instance comfortably serves, so the state gets sharded no matter which algorithm wins. Second, 2 million active keys is the multiplier on per-key memory, and that multiplier alone eliminates one of the four algorithms outright. A design costing 100 bytes per active key needs 200 megabytes. A design costing 70 kilobytes per active key needs 140 gigabytes. Those are not the same system.
The last constraint is blast radius. The limiter is a dependency of everything, so it must degrade rather than fail, and its failure behavior has to be a deliberate choice rather than whatever the client library does by default.
Where the limiter lives
Before choosing an algorithm, decide where the decision happens, because that placement determines what state is available and how much traffic the limiter can actually shed.
Four places a limit can be enforced, and what each one can and cannot protect.
There are four realistic positions. At the edge, in a CDN or scrubbing layer, you drop volumetric floods by IP before they cost you bandwidth, but you know almost nothing about the caller, so the limits are coarse. At the API gateway you have the authenticated identity, the route, and the tenant, and you can reject before the request touches business logic. This is where the primary limiter belongs. Inside individual services you enforce fine-grained limits only that service understands, such as a per-tenant cap on an expensive report path. At the resource itself, connection pools and queue depths act as a last-resort limit no application bug can bypass.
These compose rather than compete. The edge sheds junk cheaply, the gateway enforces the contract you sell, the service protects its own expensive paths, and the pool protects the database. Put everything in one layer and you either reject too coarsely to be fair or let too much through to be safe. The rest of this piece is about the gateway limiter, because that is the one that has to be both precise and fast.
Fixed window counters, and the burst they cannot see
The simplest correct-looking algorithm is a fixed window counter. Divide time into aligned windows of length W, keep one integer per identity per window, increment on each request, and reject when the integer exceeds the limit. The counter expires when the window does.
It is genuinely appealing. One integer per key, one atomic increment per request, and the memory is as small as it can possibly be. It is also wrong in a way that matters.
A fixed window resets on a wall-clock boundary, so a client can spend a full window at the end of one and a full window at the start of the next.
The flaw is at the boundary. With a limit of 100 requests per minute, a client can send 100 requests at 11:00:59 and another 100 at 11:01:00. Both windows are individually within limit. The server just absorbed 200 requests inside a two-second span, which is twice the rate you advertised and twice the rate your capacity planning assumed. Over any sliding minute that straddles a boundary, a fixed window permits up to 2x the nominal limit, and that is not a rare edge case. Clients that retry on a schedule, cron jobs aligned to the minute, and any library that resets its backoff at the top of the minute find this boundary reliably.
There is a second, operational problem. Aligned windows synchronize clients. Every caller that got a 429 learns the window resets at the top of the minute, and they all come back at the same instant, producing a sawtooth with a spike at every boundary. You have taken smooth traffic and made it bursty. Both problems trace to one root cause: the window is a property of the clock rather than of the request.
The sliding window log: correct and unaffordable
The exact fix is obvious. Instead of counting requests in a clock-aligned bucket, keep the timestamp of every request and, on each new request, count how many fall inside the trailing window ending now. This is the sliding window log, and it is the only algorithm here with no approximation error at all.
The log stores one timestamp per request, trims everything older than the window, and counts what is left. Exact, and priced accordingly.
In Redis it is a sorted set per identity, scored by request timestamp. The member has to be unique rather than the timestamp itself, since two requests in the same millisecond would otherwise collapse into one entry and undercount, so it is usually the timestamp plus a random suffix or a request id. Each decision is a ZREMRANGEBYSCORE to discard entries older than now minus W, a ZCARD to count the survivors, and a ZADD to record the new request, wrapped in a script so the three run atomically. The count is exact for every possible instant, and the boundary burst is impossible by construction.
The problem is the bill. You store one entry per request for the duration of the window. At a limit of 1,000 requests per minute, a fully active key holds 1,000 sorted set entries, and a Redis sorted set entry at that size carries roughly 60 to 80 bytes of member, score, skiplist, and hash table overhead. Call it 70 kilobytes per active key. Multiply by 2 million active keys and you need on the order of 140 gigabytes of memory to rate limit an API, before replication. The CPU cost scales the same way, because the trim has to locate and delete every entry that fell out of the window, and the set it works on grows with the limit rather than staying a fixed size. And the cost is highest exactly when you least want it, since the clients generating the most entries are the ones you are trying to throttle.
The sliding window log is the right answer when limits are small and correctness is absolute. Five login attempts per fifteen minutes is a perfect fit, because the log is at most five entries and the security team wants exactness. One thousand requests per minute across millions of keys is not. This is a case where the exact algorithm is the wrong engineering choice, and being able to say why is more valuable than knowing it exists.
The sliding window counter: buying back the memory
The sliding window counter is the approximation that makes sliding windows affordable. Keep the fixed window counters, two of them, the current window and the previous one, and estimate the count over the trailing window by weighting the previous window by how much of it still overlaps.
Two counters and one multiplication approximate an exact sliding window, with error bounded by how uneven the previous window’s traffic actually was.
Concretely, with a limit of 100 per minute, suppose at 11:01:15 the 11:00 window recorded 80 requests and the 11:01 window has recorded 30 so far. Fifteen seconds of the current minute have elapsed, so 45 of the previous 60 seconds still lie inside the trailing minute, a weight of 0.75. The estimate is 80 times 0.75 plus 30, which is 90. That is under 100, so the request is allowed. Compare that to a fixed window, which would have seen only the 30 and cheerfully allowed 70 more.
The estimate assumes the previous window’s requests were spread evenly across it, and when they were not it is wrong in both directions. If all 80 landed in the first ten seconds of the previous minute, none are really inside the trailing window, the estimate over-counts, and you reject a client who was within budget. If they all landed in the last five seconds, the estimate under-counts and you let through more than the limit. The error is bounded by the limit itself and only appears when traffic within a window is heavily skewed. Cloudflare published an analysis of this approximation in production and reported that on the order of 0.003 percent of requests were classified differently than an exact sliding window would have classified them, which is a rounding error for quota enforcement.
The cost is two integers per key, roughly the same as a fixed window and around one seven-hundredth of the log. That is the trade: you give up exactness you cannot measure in exchange for memory you can.
The token bucket: rate and burst as separate dials
Token bucket approaches the problem from a different direction. Instead of counting requests in a window, model a bucket that holds up to B tokens and refills at r tokens per second. Each request removes one token. If the bucket is empty, the request is denied.
A token bucket refills continuously at the sustained rate and holds a reservoir up to its capacity, so burst size and steady rate are configured independently.
Two properties make this the default for most production API limiters. First, it separates the sustained rate from the burst allowance into two independent parameters. A bucket with capacity 100 and a refill of 10 tokens per second lets a client sit idle, accumulate a full reservoir, fire 100 requests instantly, and then settle into a steady 10 per second. Window algorithms cannot express that shape; they have one number and it conflates the two. Real clients are bursty on purpose, since a page load fires a dozen calls at once and a batch job wakes up and works, so a limiter that permits a controlled burst while capping the long-run rate fits how software behaves.
Second, the state is tiny and the refill is lazy. You do not run a timer that adds tokens. You store two values, the token count and the timestamp of the last update, and on each request compute the tokens that should have accrued: new tokens equals old count plus elapsed seconds times r, clamped at B. Two fields per key, one arithmetic update per request, no background job. That is roughly 100 bytes per key including Redis key and hash overhead, so 2 million active keys costs about 200 megabytes.
Token bucket also handles weighted requests naturally, which window algorithms do not. If a search query costs your backend twenty times what a key lookup costs, charge it twenty tokens. The limiter then budgets work rather than calls, which is almost always what you meant.
One variant is worth knowing because it compresses the state further. The generic cell rate algorithm, or GCRA, stores a single timestamp, the theoretical arrival time at which the next request would be perfectly conforming, and decides by comparing that time against now plus a fixed burst tolerance. The sustained rate is the emission interval baked into how the timestamp advances, and the burst allowance is that tolerance. One value per key instead of two, no clamping logic, behavior equivalent to a token bucket.
Leaky bucket, and why it is a different tool
Leaky bucket is often listed as a fourth algorithm, and it is worth separating because the name covers two different things.
A token bucket admits a burst and then throttles; a leaky bucket queue admits nothing faster than its drain rate and smooths everything into a constant stream.
As a queue, the leaky bucket holds requests in a fixed-size FIFO and releases them downstream at a constant rate, dropping overflow. That gives a perfectly smooth output stream regardless of how bursty the input was, which is what you want in front of a fragile dependency such as a legacy system or a third-party API with its own hard limit. The cost is latency and memory, since requests wait rather than being answered.
As a meter, the leaky bucket is mathematically equivalent to GCRA and therefore to a token bucket with burst tolerance. What matters is not the shape of the bucket but whether you are shaping traffic or rejecting it. A gateway limiter rejects, because holding a client’s request for two seconds to smooth your own load is worse for them than telling them to retry. An internal fan-out to a rate-limited downstream shapes, because there is no user waiting. Use the queue where you control both ends and latency is not the product.
Choosing between them
Put the four side by side and the choice is not close for a general-purpose API gateway.
The four algorithms compared on the dimensions that decide the choice: memory per key, burst behavior, precision, and what each one gets wrong.
Fixed window is out because the 2x boundary burst is a real capacity risk and the synchronized retries make traffic worse. Sliding window log is out on memory at this scale, though keep it for small, security-sensitive limits where exactness is the requirement. That leaves sliding window counter and token bucket, both of which cost a couple of values per key and both of which are correct enough.
Between those two, choose sliding window counter when the limit you sell is literally phrased as a count per interval, such as 10,000 requests per hour, because the algorithm matches the contract and the number in the customer’s dashboard matches what the limiter computes. Choose token bucket when you want to permit bursts deliberately, when requests have different costs, or when you want the client-facing behavior to be a drip rather than a cliff. Token bucket is the better default for a public API; sliding window counter is the better fit for billing-adjacent quotas where the count has to be defensible. Nothing stops you running both, since they cost almost nothing to evaluate together.
The distributed problem starts here
Everything so far assumed one process holding the state. Now run the gateway on 100 nodes behind a load balancer, and the algorithm you picked stops being the hard part.
Splitting a global limit evenly across nodes is only correct if traffic splits evenly across nodes, which it does not.
The tempting move is to divide. Global limit of 1,000 per minute, 100 nodes, so give each node a local limit of 10 per minute and keep all state in process. It is fast, it has no shared dependency, and it is wrong in both directions. A client with a handful of long-lived HTTP/2 connections lands on maybe three nodes, so their effective ceiling is 30 requests per minute rather than 1,000, and you have throttled a paying customer to 3 percent of what you sold them. A client that opens fresh connections and spreads across all 100 nodes gets the full 1,000. Enforcement now depends on client connection behavior rather than on policy. Autoscaling makes it worse, because the node count changes underneath you and the per-node share silently drifts. Any load balancing that is not perfectly uniform, which is all of it, breaks this scheme.
A rate limiter is not a counter with a threshold. It is a distributed consensus problem that you are allowed to get slightly wrong, and the whole design is a negotiation over how wrong.
The correct approach is shared state. Every node reads and updates one authoritative counter per identity, so the limit is enforced globally regardless of how requests were routed. That introduces a network round trip on every request and a hard dependency on a store, which are exactly the two things the rest of this design has to manage.
Centralizing the state
The store for this workload has a specific shape. Keys are short strings, values are one or two small numbers, every operation is a read-modify-write, entries expire on their own, and the working set has to be in memory because you pay for it on every request. That is Redis, for reasons rather than by habit.
Stateless gateway nodes share one authoritative limiter state in a Redis cluster, keyed so that each identity’s counters live in one slot.
The properties that matter: single-threaded command execution gives atomicity for free without locks, in-memory access keeps a decision at tens of microseconds of server time, native TTLs mean expired windows clean themselves up with no sweeper, and server-side scripting runs the whole read-modify-write as one indivisible unit. Round-trip latency inside an availability zone is a few hundred microseconds, which fits the budget. Cross-zone does not, so the limiter’s Redis needs to be zone-local with a replica elsewhere rather than a single shared cluster three hops away.
Throughput forces sharding. A single Redis instance handles somewhere around 100,000 simple operations per second, and a small Lua script doing several commands lands closer to 50,000 to 80,000. At 200,000 decisions per second that is three to four primaries running flat out, so six to eight once you leave room for peaks and for losing one, which means Redis Cluster with limiter keys spread across hash slots. That works because the natural key is the identity and identities spread evenly. Mostly. The exception is a later section.
Atomicity is the whole game
Here is the bug that ships more often than any other in this design. A node reads the current count, compares it to the limit, decides to allow, and writes the incremented value back. Two nodes do that concurrently for the same key, both read 999 against a limit of 1,000, both allow, and both write 1,000. You permitted 1,001 requests and your counter says 1,000, so the overage is not even visible in metrics. At 200,000 requests per second this does not happen occasionally, it happens constantly.
The token bucket as a single server-side script: refill, test, deduct, and set expiry as one indivisible operation, with the store’s own clock as the time source.
The fix is to move the entire decision into the store as one atomic operation. For a plain fixed window, INCR is already atomic and returns the new value, so the check becomes increment first and reject if the result exceeds the limit, with the caveat that the TTL must be set in the same breath or a key survives forever. Token bucket needs real logic, so it goes in a Lua script executed with EVALSHA. The script reads the stored token count and last-refill timestamp, computes the tokens accrued since the last update and clamps at capacity, compares against the requested cost, then either deducts and returns allow or leaves the state alone and returns deny with a wait time, finally setting a TTL slightly longer than a full refill. Redis runs that script to completion without interleaving anything else, so the race cannot occur.
One detail decides whether this is correct across a fleet. Do not let each node pass its own wall clock into the script. Node clocks drift, and a node running two seconds fast grants itself tokens that do not exist while a slow node under-grants. Take the time from the store instead, using the server’s TIME command inside the script, so every node’s arithmetic uses one clock. This was historically forbidden because scripts replicated verbatim and a non-deterministic command would diverge on replicas, but modern Redis replicates scripts by their effects, so reading the server clock inside a script is both safe and correct.
Keys, memory, and expiry
The key schema is not an afterthought. It defines the granularity of every limit you can express, and once clients depend on a limit you cannot easily change it.
The limiter key space: what identifies a bucket, what each entry stores, how long it lives, and what the whole thing costs in memory.
A workable scheme is a namespaced composite: limiter version, scope, identity, resource. Something like rl:v1:user:8831:search for a per-user per-endpoint limit and rl:v1:ip:203.0.113.9:global for the coarse IP limit. The version prefix lets you roll out a new algorithm or window size by writing under a new prefix and cutting over, rather than migrating live counters. The scope lets one Redis hold all limit tiers without collision. Keep keys short, because at 2 million active keys the key strings are a meaningful fraction of the memory.
Store the token bucket as a small hash with two fields, tokens and last refill timestamp, or as a packed string to shave allocation overhead. Either way the entry is roughly 100 bytes all in, so 2 million active keys is about 200 megabytes per replica set. Set the TTL to a full refill plus a small margin, because past that point a missing key and a full bucket are indistinguishable, so expiry is free and correct. That is what keeps memory proportional to active keys rather than registered ones. Fifty million accounts cost you nothing until they send traffic.
One thing to resist: do not store analytics in the limiter. Recording every rejection with its timestamp and endpoint in the same structure is how a 200 megabyte working set becomes a 40 gigabyte one. Emit an event and aggregate it elsewhere.
Hot keys and the token lease
Sharding by identity distributes load evenly right up until one identity is enormous. A single enterprise tenant sending 30,000 requests per second maps to one key, one hash slot, one primary. That primary now takes 30,000 writes per second to a single key while its peers idle, and adding shards does not help, because the cluster cannot split a key.
Two ways to relieve a hot limiter key: split one logical bucket into shards that clients pick from at random, or have each node lease a batch of tokens and spend them locally.
There are two standard remedies and they compose. The first is to shard the bucket itself. Split one logical limit of R into K sub-buckets each holding R divided by K, with keys suffixed by a shard number the calling node picks at random. Load spreads across K slots. The cost is precision at the tail, because a client whose requests land unevenly across sub-buckets can be rejected while another sub-bucket still has tokens. With K small, say 8 or 16, and traffic large enough to be statistically smooth, the error is minor, and it only applies to the largest tenants, who are exactly the ones with enough volume for randomness to average out.
The second remedy is token leasing, which also fixes the round-trip cost. Instead of asking the store for one token per request, a node atomically reserves a batch, say 50 tokens, then serves the next 50 requests from local memory with no network call. Redis traffic drops by the batch factor and limiter latency drops to nearly zero for most requests. The cost is precision again, in a bounded way: at any instant up to node count times batch size can sit in unspent leases, which is capacity allocated but not delivered. Keep the batch small relative to the limit, give leases a short expiry so unspent tokens return to the pool when a node goes idle or dies, and size the batch from measured per-node traffic rather than a constant. This is the same idea as pre-allocating identifier ranges, applied to permission instead of identity.
When the limiter cannot reach its state
Now the failure mode that decides whether this component is an asset or a liability. Redis becomes unreachable, or slow, which is worse. Every request hits a limiter that cannot decide. What should happen?
The fail-open versus fail-closed decision, with the local degraded bucket that makes fail-open survivable.
Fail open means allow the request when the limiter cannot decide. Your API stays up, and for the duration of the incident you have no rate limiting, so a client in a retry storm or an abusive caller can push straight through to your backends. Fail closed means deny, which preserves the protection and turns a limiter outage into a full API outage, converting a dependency failure into a customer-visible one.
Neither is universally right, and the correct move is to decide per limit class rather than globally. General quota enforcement should fail open, because the limit exists to allocate capacity fairly and a brief lapse in fairness costs far less than refusing all traffic. Security-critical limits should fail closed: login attempts, password resets, payment submissions, anything where the limit is the control preventing abuse rather than a fairness mechanism. If you cannot verify that this is the sixth failed login in a minute, denying is the safe answer.
Fail open on its own is too blunt, and the mitigation is a degraded local mode. Each node keeps a small in-process token bucket sized to a conservative per-node share of the global limit, normally unused. When the shared store is unavailable, nodes fall back to it, so enforcement becomes approximate and generally stricter than intended but never disappears. That is the availability of fail open with a floor under the damage.
Two operational details separate a limiter that degrades from one that cascades. Set a hard, short timeout on the store call, on the order of 5 milliseconds, and treat a timeout as unavailable rather than waiting. A limiter that blocks for 200 milliseconds on a slow Redis has taken your API down more effectively than the traffic it was meant to control. And put a circuit breaker in front of the store, so after a run of failures the nodes stop calling it and go straight to local mode, which preserves latency and gives the store room to recover instead of being hammered by retries from every node at once.
Telling the client what happened
The response is the part clients integrate against, so getting it right materially reduces the load you receive.
Reject with 429 Too Many Requests and always include a Retry-After. A client told to wait 8 seconds waits 8 seconds; a client that gets a bare 429 retries immediately, which is why an under-specified limiter tends to increase the traffic it was deployed to reduce. Publish the state on successful responses too, with the limit, remaining allowance, and reset time, so a well-behaved client paces itself and never hits the wall. The IETF has been standardizing this as the RateLimit family of headers, and the older X-RateLimit spelling is what most clients already parse. Add jitter to Retry-After: if every rejected client is told to come back in exactly 8 seconds, they all do, and you have rebuilt the synchronized herd that the fixed window boundary produced.
One subtlety appears once you enforce several limits at once, which you will, since a real gateway checks global, per-IP, per-user, and per-endpoint limits on the same request. If you deduct from each in sequence and the fourth rejects, you have consumed budget from the first three for a request that never ran, and a client sitting near several limits bleeds allowance for requests it was never served. The clean fix is to evaluate all limits first and commit the deductions only once every one passes, which for a Redis-backed limiter means a single script taking all the relevant keys. If that is impractical, order the checks cheapest and most likely to reject first and accept a small over-deduction. Either way, make it a decision rather than an accident.
The patterns that transfer
The reason this problem is worth the depth is that almost none of its lessons are about rate limiting.
Four decisions from this design that reappear in any system enforcing a shared global constraint at high request volume.
First, shared state plus concurrency means the decision has to be atomic where the state lives, not where the code runs. Read, decide, write is a race in every system with more than one writer, and moving the whole operation into the store, by an atomic primitive, a server-side script, or a conditional write, is the general fix. Anywhere you check a value and then act on it, that is the same bug.
Second, exact algorithms are sometimes the wrong engineering choice. The sliding window log is perfectly correct and costs about 700 times the memory of an approximation whose error is a few thousandths of a percent. Knowing which inaccuracies are cheap and which are dangerous is most of applied system design, and the discipline is to characterize the error rather than avoid it.
Third, batching converts a per-request cost into a per-batch cost at a bounded, quantifiable loss of precision. Token leasing is the same shape as pre-allocating ID ranges, buffering writes, and prefetching. Each trades a small, computable amount of correctness for a large reduction in coordination.
Fourth, a component on every request path must have an explicit, per-class failure behavior. Fail open and fail closed are both correct answers to different questions, and the failure that hurts is the one nobody chose. Any hot-path dependency deserves the same treatment: a hard timeout, a circuit breaker, a degraded local mode, and a written decision about what happens when it is gone.
Learn to see which of those four your bottleneck sits on and the design stops being a memorized algorithm list and becomes a method.
I teach system design this way, from first principles with real diagrams and the trade-offs that only surface in production, as an interactive course at systemdesign.academy. The foundation lessons are free and need no signup.
Read the free lessons: https://systemdesign.academy
답글 남기기