Rate Limiting: Every Algorithm, and the Race Condition in the Obvious One

Most system design content optimizes for the interview: a checklist of components — load balancer, cache, message queue, sharded database — assembled into a diagram that would never survive a design review, because it never has to. Nobody asks the follow-up questions a real system forces on you: what happens when the cache and the database disagree, what your on-call engineer does at 3 a.m. when the queue backs up, what breaks first when traffic is ten times what you planned for.

This series is the other version — one real system per part, built up from its actual constraints, each part standing on its own. We start with a rate limiter, because it is the smallest system in the set that still contains a genuine distributed-systems bug that almost everyone ships.

What are you actually limiting?

Before the algorithm, the awkward question: what counts as “one caller”?

By API key is the easy case and the only one that is really correct, because the key identifies an account you have a relationship with.

By IP is what you fall back to for unauthenticated traffic, and it is wrong in both directions. A corporate NAT or a university puts thousands of people behind one address, so a limit low enough to stop an attacker locks out a customer’s whole office. Meanwhile an attacker with a residential proxy pool has more addresses than you have limits. IPv6 makes this worse, not better: an attacker may control a /64 with 18 quintillion addresses, so if you limit IPv6 by full address you have no limit at all. Key on the /64 prefix.

By user, and by endpoint. One global limit per account means an expensive report query and a cheap health check draw from the same budget. Separate buckets, or weight requests by cost.

And the header contract matters more than people expect: return RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset and, on a 429, a Retry-After. A well-behaved client will back off if you tell it how long. A client with no information retries immediately, and you have converted a rate limit into a hot loop.

The four algorithms

Run the burst preset and watch the second row. That is fixed window, and its failure is the one you should be able to recite: a limit of 100 per minute lets through 200 requests in a two-second span straddling a window boundary — 100 at 11:59:59, 100 more at 12:00:01 — because each half is legal in its own window. Every naive INCR key:$minute implementation has this bug. It is not subtle at scale; it is the reason your “100/min” limit sometimes admits 200.

The other three each fix it differently:

Sliding window log stores a timestamp per request and counts the ones inside the last 60 seconds. Exactly correct, and it costs memory proportional to your limit times your caller count — a 1,000/min limit across 100,000 callers is 100 million timestamps. Correct and unaffordable, which is a useful thing for a design to be, because it tells you the other options are approximations of this.

Sliding window counter keeps two numbers — the current window’s count and the previous window’s — and interpolates: 30% into the current minute, charge 70% of the previous window’s count plus everything so far this one. It is an approximation that assumes requests were spread evenly through the previous window, it is wrong by a few percent under adversarial bursts, and it costs two integers per caller. This is what most production limiters actually run, and it is the right default.

Token bucket is the odd one out because it is not trying to answer “how many in the last minute?” at all. A bucket holds up to burst tokens and refills at rate tokens per second; a request takes one or is rejected. It permits a burst up to the bucket size and then enforces a smooth long-run rate — which is usually what you actually wanted, since a client that has been quiet for an hour is not the client you are trying to stop. Two numbers per caller (token count, last refill time), and refill is computed lazily on read rather than by a background job.

Pick token bucket when you want to allow bursts and shape the average. Pick sliding window counter when the limit is a promise in your API docs that must not be visibly exceeded.

The bug

Here is the implementation nearly everyone writes first, and it is wrong:

# Broken under concurrency. Do not ship this.
count = redis.get(key)
if int(count or 0) >= LIMIT:
    return TOO_MANY_REQUESTS
redis.incr(key)
redis.expire(key, WINDOW)
return OK

Read, decide, write. Between the get and the incr there is a window — a network round trip wide, which on a busy service is an eternity — in which any number of other workers run the same get, see the same value, and all decide they are allowed. Every one of them then increments.

This is a check-then-act race, and it has three properties that make it particularly nasty to find. It is invisible under light load, because concurrent requests for the same key are rare. It gets worse exactly as you scale, because more workers means more overlap. And it never produces an error — the limiter simply lets through more than it promised, which nothing alerts on.

The fix is not a lock, and it is not “use a faster Redis”. It is to make the whole read-decide-write one atomic operation:

-- Atomic. Redis runs the whole script without interleaving another command.
local current = tonumber(redis.call('GET', KEYS[1]) or '0')
if current >= tonumber(ARGV[1]) then
  return 0
end
redis.call('INCR', KEYS[1])
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]))
return 1

Redis executes a Lua script atomically — no other command runs partway through it — so the gap the race lived in no longer exists. Token bucket has the same shape and the same fix: read tokens and last-refill, compute the refill, decide, write both, all inside one script.

Two things to get right around it. EXPIRE must be set in the same atomic step, or a crash between INCR and EXPIRE leaves a key that never expires and permanently blocks that caller. And prefer redis.call('TIME') inside the script over a timestamp passed in by the caller — application clocks drift, and a client with a fast clock can otherwise refill its own bucket early.

The parts nobody mentions

The limiter is now a hard dependency. Redis being down must not take your API down. Decide in advance whether you fail open (serve traffic, drop the limit) or fail closed (reject everything), and know that fail-open during a Redis outage is exactly when an attacker would like you to fail open. For most products fail-open is right for customer-facing limits and fail-closed is right for auth endpoints — which is to say it is a per-endpoint decision, not a global one.

One shared counter is a hot key. Every request for a popular caller hits the same Redis slot, and at some point that slot is your bottleneck. The usual fix is local token buckets per instance, each holding limit / instances tokens, reconciled with the central store periodically. That trades exactness for throughput and is almost always the right trade — but be honest that a caller can now exceed the limit briefly while the instances are out of sync.

Rejections must be cheap. If producing a 429 costs a database lookup to resolve the API key, an attacker sending 50,000 requests a second is still doing 50,000 database lookups a second, and your rate limiter has become the amplifier. Cache the key lookup, and put the cheapest checks first.

Retry-After needs jitter. Tell 10,000 clients to retry in exactly 60 seconds and they will all retry in exactly 60 seconds. Randomise within a range, or you have built a synchronised stampede on a timer.

The short version

Choose the identity you are limiting before the algorithm, and remember that IP is a lossy proxy for a person in both directions — key IPv6 on the /64.

Fixed window is broken at the boundary by a factor of two. Sliding window log is exact and too expensive. Sliding window counter approximates it for two integers per caller and is the right default when the number in your docs must hold. Token bucket shapes the average while permitting a burst, which is usually what “rate limit” actually means.

Then the part that matters more than any of it: get-then-incr is a check-then-act race that lets through roughly double the limit under concurrency, is invisible in testing, worsens as you scale and raises no error. Do the whole decision in one atomic script, set the expiry inside it, take the clock from the store rather than the caller — and decide, before the outage, whether the limiter failing means everything is allowed or nothing is.