Designing a rate limiter that won’t lie to you

Almost every public system needs a rate limiter, and almost every rate limiter ships with a quiet lie baked in: it claims to enforce “100 requests per minute” while actually enforcing something fuzzier. That’s usually fine — but only if you chose the fuzziness on purpose. Here’s how I’d reason about it.

The problem, stated plainly

We want to cap how often a given client (an API key, a user, an IP) can hit an endpoint, to protect the system from abuse and from accidental stampedes. The cap has to hold under real traffic: bursty, concurrent, and spread across many servers. And the enforcement itself can’t become the bottleneck it’s meant to prevent.

The solution

Use a token bucket per client, with the counters held in a shared, in-memory store (Redis or equivalent) and enforced at the edge — the API gateway — before requests reach application servers.

Each client gets a bucket that refills at a steady rate (say, 100 tokens/minute) up to a maximum capacity (say, 100). Every request spends one token. Empty bucket, request rejected with 429 and a Retry-After header. The whole check is a single atomic operation:

-- Atomic token-bucket check (Lua, runs inside Redis)
-- KEYS[1] = bucket key   ARGV = now, rate, capacity, cost
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or capacity
local ts     = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * rate)
if tokens < cost then return 0 end          -- reject
redis.call('HMSET', KEYS[1], 'tokens', tokens - cost, 'ts', now)
return 1                                       -- allow

The rationale

Why token bucket, not a fixed window

A fixed-window counter (“reset the count every minute”) is the simplest thing that works, and it’s what I’d reach for if traffic were smooth. But it has a notorious edge: a client can fire 100 requests at 00:59 and another 100 at 01:00 — 200 requests in two seconds while never “breaking” the limit. Token bucket smooths that out because it thinks in terms of a continuous refill rate, not a wall-clock boundary. It also naturally allows a controlled burst up to the bucket capacity, which is usually what you actually want: tolerate a short spike, punish sustained abuse.

Why the counters live in a shared store

The moment you have more than one server enforcing the limit, per-server counters stop meaning anything — ten servers each allowing 100/min is a 1,000/min limit by accident. A shared store gives every node one source of truth. The cost is a network hop per request, which is why the check has to be cheap and atomic (hence the Lua script: read-modify-write in one round trip, no race between concurrent requests).

Why enforce at the edge

Rejecting at the gateway means abusive traffic dies before it consumes an app server, a database connection, or a thread pool. The limiter protects the expensive part of the system by living in the cheap part. As a TPM, this is the line I’d underline in the design review: the further out you reject, the more the limit is worth.

A rate limiter you can’t reason about under failure is just a second outage waiting for the first one.

The risks — what I’d flag before shipping

This is the part that gets skipped in interviews and remembered in incidents. None of these are reasons not to ship; they’re things I’d want a decision on, in writing.

• The store is now a dependency on the hot path. If Redis is slow or down, what happens? “Fail open” (allow everything) protects availability but removes the limit exactly when load is high. “Fail closed” (reject everything) protects the backend but turns a cache blip into a full outage. I’d default to fail-open with a tight timeout and an alert — but that’s a business call, not a technical one.
• Hot keys. One enormous client (or one IP behind a corporate NAT) can concentrate all its traffic on a single bucket key, and that key’s shard becomes a hotspot. Mitigations: shard the key, or accept approximate limiting with local pre-checks.
• “Approximately correct” is a feature, not a bug — if you say so. To avoid a network hop on every request, many systems do local token buckets per node and reconcile periodically. That means the global limit is enforced loosely. Totally fine for abuse prevention; not fine if the limit is a billing or quota boundary. The risk is shipping the loose version against a requirement that needed the strict one.
• Clock and refill drift. The math leans on now. Skew between nodes, or pushing time logic into application code instead of the store, reintroduces the races we just removed. Keep the time source and the arithmetic in one place.
• The client experience of a 429. A limit with no Retry-After, or with retries that all wake up at the same instant, creates a thundering herd that re-limits everyone. Honest headers plus jittered backoff on the client side are part of the design, not an afterthought.

What I’d actually recommend

For most systems: token bucket, shared store, edge enforcement, fail-open with alerting, and an explicit written note that the limit is “approximately correct” and must not be used as a billing boundary without revisiting the design. That last sentence is the whole job — not picking the algorithm, but making sure the limit we built matches the limit we promised.

Filed under: rate limiting, edge, trade-offs. Got a sharper take or a war story? Tell me.