Rate limiter system design: token bucket vs sliding window, at scale

Rate limiter system design comes down to three choices: how you count, where the count lives, and what happens when that storage goes down. For a public API the usual answer is a token bucket per API key, kept in Redis and checked with one atomic script. When Redis stops answering, the check is skipped and an alert fires.

The walkthrough below designs that limiter for the numbers the app's rate limiter problem uses. Two million API keys. A default plan of 1,000 requests a minute. 120,000 requests a second at peak, spread across 40 gateway servers.

0.5×1×2×ResetBurst ×12

Scroll →

Incoming traffic6req/sRefill rate4tok/sCapacity (burst)10tok

Traffic (6/s) is above the refill rate (4/s). The bucket drains, then about 33% of requests get 429. A bigger capacity only delays this. The refill rate is what you sustain.

The figure is one token bucket. Each request takes a token at the gate. With no token left, it gets a 429, the status that tells one client it has sent too many requests. Move Incoming traffic above Refill rate and watch the bucket drain. Then press Burst ×12 with a full bucket, and again with Capacity set to 3.

Ask three questions before you draw anything#

The first minutes of the interview are for questions that change the design. Three of them do here.

What is the limit keyed on? A limit per API key means the limiter has to know the key, so it sits after authentication. A limit per IP address can sit in front of everything.

Do limits differ by plan? If they do, every check needs the key's plan limit. That's a lookup on every request, so it has to be cheap.

How exact must the limit be? If a few percent over is fine, each server could count on its own. If the limit has to hold across the whole fleet, the servers need to share their counts.

The brief answers all three. Limits are per API key, they come from the key's plan, and they must hold within 5% of exact across all 40 gateways. Two more numbers shape everything after that.

The check must add under 2 ms at p99, the time the slowest one in a hundred requests takes. And when the limiter's own storage is down, the API must keep answering. Billing for overage and stopping network floods belong to other systems. Say so, and move on.

Refuse over-quota calls with 429 and say when to retry#

Decide what each caller hears back before you pick an algorithm. A call within quota gets 200, with a header saying how much of the quota is left. A call over quota gets 429 with a Retry-After header, the number of seconds until the next token arrives. An unknown key gets 401 before the limiter is consulted, because there is no quota to check.

You could hold an over-quota call until a token arrives. Callers would see slower responses and change nothing in their code. But every held call keeps a gateway connection open while it waits. A burst of held calls fills the gateway, and the caller never learns to slow down.

A 429 only reduces load when clients back off. A client that retries at once sends the same traffic, and every attempt still costs a connection and a limiter check. So the 429 carries Retry-After, and well-behaved clients add jitter, a small random amount added so things don't all happen at the same moment.

Token bucket vs sliding window: what each one counts#

There are five standard algorithms. Each one keeps something different per key, and each fails in its own way.

A fixed window counter keeps one number per key per minute. It resets to zero at the top of each minute. It's the cheapest, and it has a hole at the boundary. A client can send 100 requests at 11:59:59 and 100 more at 12:00:00. That's 200 in two seconds on a limit of 100 a minute.

A sliding window log stores a timestamp for every request and counts the ones from the last 60 seconds. It's exact. It also stores up to 1,000 timestamps per key at 8 bytes each. Across two million keys that's about 16 GB, and it grows with traffic.

A sliding window counter keeps two numbers per key, this minute's count and last minute's. It estimates the rolling count from the share of last minute still inside the window. At 12:00:15, with 800 requests last minute and 300 so far this one, the estimate is 300 + 800 × 45/60 = 900. It's close to exact for two integers per key.

A token bucket is a counter that refills at a steady rate, and each request spends one token. It keeps two fields per key: the token count and when it last refilled. The refill rate is the limit a client can sustain. The capacity is the biggest burst you'll ever let through, and you choose it.

A leaky bucket puts requests in a queue and lets them out at a constant rate. Nothing over the limit is refused. It waits in the queue instead, and a client may give up on a request that will still run later. It fits smoothing writes to a slow downstream. For a public API that has to answer at once, it's the wrong shape.

Pick the token bucket and say why. It costs two fields per key, and it lets you size the burst separately from the sustained rate. For the 1,000-a-minute plan, the bucket refills at about 17 tokens a second. A capacity of 1,000 lets a quiet client send a whole minute's allowance in one second. If the backend can't take that, a capacity of 100 holds the burst to 100.

One Redis hash per key, changed by one atomic script#

Each bucket is a Redis hash with two fields: tokens and last_refill. The check reads both, adds the tokens earned since the last refill, takes one if there is one, and writes both back.

-- KEYS[1] = bucket, ARGV = capacity, refill per second
local cap, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local t = redis.call("TIME") -- Redis's clock, the same for every gateway
local now = t[1] * 1000 + math.floor(t[2] / 1000)
local b = redis.call("HMGET", KEYS[1], "tokens", "last_refill")
local tokens = tonumber(b[1]) or cap
local last = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - last) / 1000 * rate)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call("HSET", KEYS[1], "tokens", tokens, "last_refill", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(cap / rate * 1000))
return allowed and 1 or 0

It has to be one script. With a separate read and write, two requests that arrive together both read the last token, and both pass. Redis runs a script start to finish with nothing in between, so the read and the write can't be split.

The expiry on the last line handles idle keys. A bucket that has refilled to full is the same as no bucket. So its TTL, how long the entry is allowed to live, is the time it takes to refill, reset on every request.

Plan limits live somewhere else. The plan-to-limit table is small and rarely changes, so every gateway keeps a copy in memory. Refusal counts for the ops dashboard go to a queue and on to a time-series store. Nothing in the 429 depends on them, so they stay off the request path.

Size it: 100 MB of buckets, 120,000 operations a second#

Memory is the easy part. Two million keys at about 50 bytes of bucket state each is 100 MB. One Redis node holds that many times over. A sliding window log for the same keys would need about 16 GB, which is the other reason to drop it.

Operations decide the cluster size. Every request runs the script once, so the store sees 120,000 operations a second at peak. Spread across six Redis nodes by key, that's about 20,000 a second per node, which a node handles comfortably.

One round trip to Redis in the same region takes about half a millisecond. The check fits inside the 2 ms budget with room to spare, as long as nothing else waits on the path.

The distributed part: where the counters live#

The hard part of this design is that 40 gateways enforce one limit. Step through the figure.

0.5×1×2×▶ Play all

Scroll →

Key A allowed/min

5,000

Busiest Redis node ops/s

0

Unchecked req/s

0

01 Local02 Shared03 Hot key04 Outage

01

Each gateway counts alone. Key A's 5,000 a minute arrive as about 125 per gateway, so every one is allowed. Its real limit is 40,000.

You have three places to keep the counts.

Counters on each gateway need no network call. They also enforce 40 separate limits. A client spread across the fleet gets 40 times its plan, and that multiple changes every time the fleet scales up or down.

A shared store, one Redis cluster every gateway talks to, holds the true count. It costs one round trip per request, about half a millisecond, which the 2 ms budget allows. It's the only option that's exact by construction.

Local slices give each gateway a share of every key's budget, 25 a minute each here, and a central process moves the shares as traffic shifts. It keeps Redis off the request path, and you run that rebalancing loop forever. Every resize of the fleet moves every key's shares.

With 5% of exact as the requirement and an autoscaling fleet, pick the shared store. Then watch for the hot key, one key that gets far more traffic than the rest. Per-key buckets spread evenly across the cluster, and a single platform-wide cap doesn't. Split that cap into ten sub-keys, each holding a tenth of the budget, and pick one at random per request. The cap becomes a few percent less exact, and the load spreads over ten nodes.

When Redis is down, fail open and alert#

The brief says the API keeps answering when the limiter's store is down. That's failing open: let requests through unchecked while the store is gone. Failing closed would refuse every caller, which turns a Redis outage into an API outage.

Give the Redis call a short timeout, about 1 ms. When it expires, allow the request and add one to an "unchecked" counter. Don't retry Redis inside the request, because the retry spends the rest of the 2 ms waiting on the part you already know is slow. The counter turns a quiet minute of unlimited traffic into an alert someone sees.

A payments API or a login endpoint might choose differently. There, letting through a minute of unchecked attempts can cost more than a minute of errors. Say which way you'd go for each, and why.

What to say in an interview#

The design fits in five sentences, and each one carries a number.

1. Token bucket per API key, refilling at the plan rate, with a capacity sized to what the backend can absorb at once.
2. Buckets are Redis hashes, about 100 MB for two million keys, changed by one atomic script.
3. Counters are shared because the limit must hold within 5% across 40 autoscaling gateways, and one round trip fits in 2 ms.
4. Over-quota calls get 429 with Retry-After, and refusal counts leave the request path through a queue.
5. When Redis is down, the gateway fails open after 1 ms and alerts.

If the interviewer asks what breaks at ten times the traffic, name the stage first. A single cap key gives way before anything else. Then say the fix, sub-keys, and what it costs: a few percent of exactness on that cap.