You need to enforce 100 requests per minute per API key across a fleet of forty servers. Which limiting algorithm, and where does the counter live?

Start with what the limit is protecting

Before choosing an algorithm, say what failure you are preventing, because the answer changes the design. A limit that exists to stop one tenant exhausting a shared database wants to be enforced close to that database and to count something correlated with load. A limit that exists to price an API wants to be exact and auditable. A limit that exists to blunt credential stuffing wants to be keyed on something the attacker cannot rotate cheaply, which is rarely the API key. Most candidates jump straight to token bucket; the ones who get graded well spend a sentence on the objective first, because it is what determines whether an approximation is acceptable.

What each algorithm permits at the boundary

The four algorithms are usually presented as interchangeable, and the only way to tell them apart is to ask what each one allows a caller to do at the worst possible moment.

Fixed window buckets requests by wall-clock period: a counter keyed on the API key plus the current minute, incremented per request, rejected past 100. It is one integer and one expiry per key, which is why everyone reaches for it. It also permits 200 requests in a 200-millisecond span, because a caller who sends 100 at 12:00:59.9 and 100 more at 12:01:00.1 has broken no rule as written. Your database sees a burst of double the limit, which is precisely the thing the limit was supposed to prevent.

Sliding window log stores a timestamp per request, discards everything older than the window on each check, and counts what remains. It is exact — no boundary artefact, no burst — and it costs memory proportional to the limit for every active key, plus a write and a trim per request. For 100 per minute that is cheap. For 100,000 per minute per key it is a memory budget you did not intend to spend.

Sliding window counter keeps the current and previous fixed-window counts and weights the previous one by how much of it still overlaps the trailing window. Thirty seconds into the current minute, the previous minute contributes half its count. It costs two integers and removes the double burst, at the price of assuming arrivals were spread evenly across the previous window. When they were not — 100 requests in the last second of the previous minute — it under-counts and lets a smaller burst through. That trade is usually the right one, and being able to state the assumption it makes is the point.

Token bucket holds a bucket of capacity C refilled at rate r; each request removes a token and is rejected when the bucket is empty. The long-run rate is r and the permitted burst is C, which is a feature rather than a defect: it lets a caller who has been idle spend accumulated allowance immediately. Set C equal to the per-minute limit and you have deliberately allowed 100 requests in one instant. Set C to 10 with the same refill rate and you have a much smoother caller and an API that feels stricter than advertised. Capacity and rate are independent knobs, and treating them as one number is where token-bucket answers go wrong.

Leaky bucket is two different things under one name, which is why it causes confusion. As a meter it is the mirror image of token bucket and admits exactly the same traffic; the generic cell rate algorithm implements it with a single stored timestamp per key rather than a token count, which is a genuine efficiency win. As a queue it is different in kind: requests enter a bounded FIFO drained at a constant rate, so output is perfectly smooth and excess is dropped only when the queue is full. That variant does not reject the burst, it delays it, which is right for an outbound integration with a fragile partner and wrong for a synchronous API where the caller is holding a socket open and will time out anyway.

The counter cannot live in the process

With forty servers each holding a local counter, a limit of 100 per minute is a limit of 4,000 per minute for a caller whose requests spread across the fleet, and a limit of 100 for an unlucky caller that a sticky load balancer pins to one node. This is the part of the question being tested, and stating the multiplication out loud is worth more than any algorithm choice.

Putting the counter in one shared store — Redis being the usual choice — fixes the arithmetic and introduces two new problems. The first is atomicity. A naive INCR followed by EXPIRE is two commands, and a process that dies between them leaves a key with no expiry, which silently bans that caller forever. Do the read-modify-write in a single server-side operation instead, which for anything more involved than a counter means a Lua script or a compare-and-set loop.

-- Atomic fixed-window check. KEYS[1] is "rl:{key}:{minute}",
-- ARGV[1] the limit, ARGV[2] the window in seconds.
local n = redis.call('INCR', KEYS[1])
if n == 1 then
  -- Set the TTL only on creation, in the same atomic script,
  -- so a crash between INCR and EXPIRE cannot leave a key immortal.
  redis.call('EXPIRE', KEYS[1], ARGV[2])
end
if n > tonumber(ARGV[1]) then return 0 end
return 1

The second problem is that every request now depends on a network hop to a component that is not your service. Three mitigations are worth knowing. Lease blocks of allowance to each node rather than checking per request, which trades precision for round trips and is how high-throughput limiters are built. Route a given key consistently to one node so its counter is in-process, accepting that a rebalance loses counters and that a hot key has nowhere to hide. Or keep an approximate local counter and reconcile asynchronously, which converges but overshoots during the reconciliation lag.

Deciding what a dead limiter means

You will be asked what happens when Redis is unavailable, and there is no universally correct answer, only a justified one. Failing open keeps your API up and removes the protection at the moment infrastructure is already unhealthy, which is when you need it most. Failing closed turns a limiter outage into a full outage, which is a poor trade for a component that exists to protect against a minority of callers. The defensible design is to fail open on the shared counter but keep a conservative local token bucket as a floor, so a Redis outage degrades you from a precise fleet-wide limit to a coarse per-node one rather than to nothing.

On the response, reject with 429 and a Retry-After telling the caller when to come back, and keep it distinguishable from the 503 you return when you are shedding load, because they mean different things to a well-written client. Publishing the remaining allowance in response headers is cheap and stops callers discovering their limit by hitting it.

Rate is a proxy for cost, and often a bad one

The strongest answers close by questioning the premise. A request-per-minute limit assumes requests are interchangeable, and in most real APIs one endpoint costs a thousand times another. A caller inside its rate limit can still saturate you with expensive queries, and a caller sending cheap reads gets throttled for no reason. Two things fix this. Charge weighted cost rather than count, deducting more tokens from the bucket for expensive operations. And put a concurrency limit alongside the rate limit, bounding in-flight requests rather than arrivals, because in-flight count responds to how slow the system has actually become while a fixed rate does not.

Every one of these algorithms is a statement about what burst you are willing to accept, so name the burst rather than the algorithm: fixed window permits double the limit across a boundary, token bucket permits its capacity in an instant, and a leaky-bucket queue permits none but makes the caller wait.