A rate limiter caps how many requests a client can make in a given time. In a system design interview, most candidates answer with one word: Redis. Then the interviewer asks which algorithm, what happens when Redis is down, and how it works across ten servers, and the answer falls apart.
This article gives you one structure that holds up: the questions to ask first, the five common algorithms and how to choose between them, how to share state across servers without race conditions, and what to say when the interviewer asks how it fails. It is written for backend and Java developers preparing for system design rounds, and for anyone who has to protect an API in production.
Prefer to watch? The full walkthrough is here:
Why rate limiters exist
There are four reasons you need one.
- Abuse. A scraper or a buggy client stuck in a loop can take your service down.
- Fairness. One noisy customer should not starve everyone else.
- Cost. Every request that reaches your database or a paid third-party API costs money.
- Stability. When a downstream service slows down, retries pile up and a small problem becomes an outage. A limiter stops that from spreading.
Everyone knows why. The interview is about how you build it.
Five questions to ask before choosing an algorithm
Never start with an algorithm. Start with five questions.
- Who are we limiting? A user ID, an API key or an IP address? IP alone is a weak key, because a whole office can sit behind one address.
- Where does the limiter sit? In an API gateway or middleware in front of every service, or inside each service? A gateway gives you one place to enforce rules. Inside the service you get finer control per endpoint.
- Hard or soft limit? Do we reject at exactly the limit, or allow a small overshoot to keep the check cheap?
- What are the rules? Different limits per endpoint, per plan, per client? Can they change without a deploy?
- One server or many? If many, the counters must be shared, and that is where most of the difficulty lives.
Then say the non-functional requirements out loud. The check runs on every request, so it must add almost no latency, and the limiter itself must not become a single point of failure.
The five algorithms
Fixed window counter. Split time into windows, say one minute, and keep one counter per client per window. Count up on each request and reject past the limit. It is very cheap: one number per client. The flaw is the boundary. A client can send the full limit at the end of one window and the full limit again at the start of the next, so for a moment they send double.
Sliding window log. Store a timestamp for every request. On a new request, drop the timestamps older than the window and count what is left. It is exact, with no boundary problem. The cost is memory, because you store one entry per request, and a busy client with a high limit gets expensive fast.
Sliding window counter. A hybrid. Keep counters for the current and the previous window, and weight the previous one by how much of it still overlaps. If you are thirty percent into the current minute, count seventy percent of last minute's requests plus all of this minute's. It is an approximation, but a close one, with the memory cost of a fixed window.
Token bucket. A bucket holds tokens up to a fixed capacity, and tokens refill at a steady rate. Each request takes one token; with no token, the request is rejected. Because the bucket can be full, a client can burst up to the capacity and then settle to the refill rate, which is why it suits public APIs. Stripe documents that it uses a token bucket for its rate limiters, and the Spring Cloud Gateway Redis rate limiter uses one too.
Leaky bucket. Requests enter a queue and leave at a fixed rate. The output is smooth, which protects a downstream system that cannot take bursts. The downside is that a burst fills the queue, and newer requests either wait or get dropped.
So which one do you pick? Token bucket for a public API where short bursts are fine. Sliding window counter when you want a smooth, close-to-exact limit at scale. Leaky bucket when you protect something with a fixed throughput. Fixed window only when simple is good enough.
| Algorithm | Bursts | Memory per client | Accuracy | Pick it when |
|---|---|---|---|---|
| Fixed window | Up to 2x at the boundary | One counter | Low at window edges | Simple internal limits |
| Sliding window log | None | One entry per request | Exact | Low limits that must be exact |
| Sliding window counter | Small | Two counters | Close approximation | Smooth limits at scale |
| Token bucket | Yes, up to capacity | Token count plus last refill time | Good | Public APIs that allow bursts |
| Leaky bucket | Queued, not passed on | A queue | Smooth output | Protecting a fixed-throughput downstream |
Two answers that sound right and are wrong
Wrong answer one: keep the counter in the app's memory. That works with one server. With ten servers behind a load balancer, each one keeps its own count, so a client can get up to ten times the limit depending on where the requests land. The state has to be shared.
Wrong answer two: Redis INCR plus EXPIRE is enough. INCR bumps the counter and EXPIRE sets its time to live. If you send them as two separate commands, the app can crash between them, and you have a counter that never expires, so that client is blocked forever. The same problem shows up in a token bucket: if two requests read the token count at the same moment, both see one token left and both pass.
The fix is to make the whole check one atomic step. In Redis that means a Lua script, because Redis runs the script from start to finish without other commands slipping in between.
The distributed design with Redis
Here is the design for a token bucket shared by every server, in one round trip to Redis.
- A request reaches your gateway or filter. Build a key from the client ID and the endpoint, for example
rl:client:endpoint. - Call a Lua script in Redis with that key, the bucket capacity, the refill rate and the current time. Read the time inside the script with the Redis TIME command, so servers with different clocks cannot disagree. I tested this on Redis 7.0.15.
- The script reads the stored token count and the last refill time. It adds the tokens earned since then, up to the capacity. If there is at least one token, it takes one. Then it writes the new values back and sets an expiry so idle clients clean themselves up.
- The script returns allowed or not, plus the tokens remaining.
- If allowed, pass the request on. If not, return HTTP 429, Too Many Requests, with a Retry-After header and rate limit headers showing the limit and what is left. Well-behaved clients use those to back off.
In Java and Spring Boot you can write this as a servlet filter or an interceptor, or enforce it at the gateway. Spring Cloud Gateway ships a Redis rate limiter, where you set replenishRate for the refill rate and burstCapacity for the bucket size. Bucket4j has a Redis integration through Jedis, Lettuce and Redisson.
Redis scales here because every client key is independent. Shard by client ID, and the limiter scales out with the cluster.
The Lua script:
-- KEYS[1] = bucket key -- ARGV[1] = capacity, ARGV[2] = refill rate (tokens per second), ARGV[3] = tokens requested local capacity = tonumber(ARGV[1]) local rate = tonumber(ARGV[2]) local requested = tonumber(ARGV[3]) -- Use the Redis server clock so app servers with skewed clocks cannot disagree local t = redis.call('TIME') local now = tonumber(t[1]) + tonumber(t[2]) / 1000000 local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts') local tokens = tonumber(state[1]) local ts = tonumber(state[2]) if tokens == nil then tokens = capacity ts = now end -- Refill for the time elapsed, never above capacity tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate) local allowed = 0 local retry_after = 0 if tokens >= requested then tokens = tokens - requested allowed = 1 else retry_after = (requested - tokens) / rate end redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now) -- Idle buckets clean themselves up once they would be full again redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1) return {allowed, tostring(tokens), tostring(retry_after)} Test results with a capacity of 5 and a refill of 1 token per second:
1) Burst: 7 rapid requests -> allowed flags [1, 1, 1, 1, 1, 0, 0] 2) Retry-After on the first rejected request -> about 1.0s 3) After waiting 2s, 3 requests -> allowed flags [1, 1, 0] 4) Race test: 50 threads, one new key, capacity 10 -> total allowed: 10 of 50 5) TTL on an idle key -> 11 seconds The race test is the point: 50 simultaneous requests let exactly 10 through, because the read, refill and write happen in one step inside Redis.
What breaks in production
Interviewers love this part, so have these ready.
- Redis goes down. Do you fail open or fail closed? Fail open keeps the API up but unprotected. Fail closed protects you but takes you down with Redis. A sensible answer is to fail open on ordinary endpoints and fail closed on the expensive or sensitive ones, like login and payments.
- Hot keys. One very busy client hammers one Redis shard. You can pre-check locally and send fewer calls, or split that client's key across several keys.
- Multiple regions. A single global limit needs cross-region sync, which adds latency. A common answer is to give each region a share of the quota and accept an approximate global limit.
- Rules that change. Keep limits in a config service, cache them locally, and change them without a deploy.
- Monitoring. Count rejections per client and alert on spikes, because a sudden jump means either an attack or a limit that is set too low.
Bonus: rate limiting LLM APIs
If you build with LLM APIs, you are on the other side of this problem. Providers limit requests per minute and tokens per minute. OpenAI documents both limits in its rate limits guide, and the same idea applies to other providers.
Treat it like a token bucket. Estimate the tokens before you send. Queue the work when you are close to the limit. On a 429, back off with exponential delay and a little random jitter, so a hundred workers do not retry at the same instant. And if you expose your own AI feature, limit by tokens, not by requests, because one long prompt can cost more than ten short ones.
Your answer template for the interview
When this question comes up, answer in five steps:
- Requirements first.
- The algorithm, and why you chose it.
- Where the limiter sits and what the key is.
- The atomic Redis check and the 429 response.
- Failure modes.
Do it in that order and you will sound like someone who has built one.
Conclusion
Ask the clarifying questions. Pick the algorithm that matches the traffic, and default to a token bucket for a public API that tolerates bursts. Keep the state in Redis and make the check atomic with a Lua script. Return a 429 with Retry-After, and decide the failure policy per endpoint.
Watch the full walkthrough here: https://www.youtube.com/watch?v=STtovk5N6PA
Sources
- Stripe: Scaling your API with rate limiters, which uses the token bucket algorithm
- Spring Cloud Gateway: RequestRateLimiter, a Redis limiter with
replenishRateandburstCapacity - Bucket4j on GitHub, a token bucket library with Redis back-ends
- Redis: token bucket rate limiter with Lua, the atomic check in one script
- OpenAI: rate limits, requests per minute and tokens per minute
