How to design a distributed rate limiter in a system design interview: token bucket, leaky bucket, fixed and sliding windows, Redis with atomic Lua scripts, fail-open vs fail-closed, and the follow-ups interviewers ask.
Updated 17 October 2026
A rate limiter caps how many requests a client can make in a period - for example 100 requests per minute per user - and rejects the excess. It protects services from overload and abuse, keeps usage fair between customers, and controls the cost of expensive operations.
Example assumptions: 10 million active clients, an API peak of 1 million requests per second across the fleet, and one limiter check per request.
| Quantity | Calculation | Result |
|---|---|---|
| Limiter checks | One per request | ≈ 1M operations/s at peak |
| State per client (token bucket) | Key + token count + last refill time, with store overhead | ≈ 100 bytes |
| Total state | 10M clients × 100 bytes | ≈ 1 GB - fits in memory easily |
| Store throughput | A single Redis node handles on the order of 100k simple ops/s | Shard across ~10-20 nodes for 1M/s |
| Placement | Pros | Cons |
|---|---|---|
| Client side | No server cost. | Cannot be trusted - clients can be modified or ignore it. |
| API gateway | One place for every service; rules are central; rejects traffic before it reaches services. | The gateway becomes critical infrastructure and must scale with all traffic. |
| Middleware in each service | Limits can use business context, such as the cost of a specific operation. | Every service must implement it consistently. |
| Sidecar (service mesh) | Language-agnostic and consistent across services. | Extra moving part per instance. |
Most designs put coarse limits (per IP, per API key) at the gateway and finer, business-aware limits (per account, per expensive operation) in the service. Say which limits live where.
Interviewers expect you to compare at least three algorithms and choose one for a reason. These are the five that come up.
| Algorithm | How it works | Strengths | Weaknesses |
|---|---|---|---|
| Token bucket | A bucket holds up to N tokens and refills at a fixed rate; each request takes one token or is rejected. | Allows short bursts up to N; only two values per key; widely used. | Burst size and refill rate both need tuning. |
| Leaky bucket | Requests enter a queue that drains at a fixed rate; overflow is dropped. | Smooth, constant output rate - good for protecting a fragile downstream. | Bursts are delayed or dropped; queued requests add latency. |
| Fixed window counter | Count requests per key in fixed windows (e.g. each minute); reject past the limit. | Simplest to build: INCR plus an expiry. | Bursts at window boundaries: up to 2× the limit across two adjacent windows. |
| Sliding window log | Store a timestamp per request; count timestamps in the last window. | Exact. | Memory grows with the request rate - one entry per request. |
| Sliding window counter | Weight the previous window’s count by how much of it overlaps the current window, plus the current count. | Smooths boundary bursts with two counters per key. | An approximation that assumes requests were evenly spread in the previous window. |
estimated = current_window_count
+ previous_window_count × (1 − elapsed_in_current_window / window_length)
e.g. limit 100/min, 30 s into the minute, previous = 80, current = 50:
estimated = 50 + 80 × 0.5 = 90 → allowedclient ──► API gateway / middleware ──► rate limiter check ──► service
│ │
│ ┌──────▼───────┐
│ │ Redis cluster│ (sharded by client key)
│ └──────────────┘
▼
rules cache ◄──── rules config service (per endpoint, per tier)
over limit → 429 Too Many Requests + Retry-AfterEvery API server must see the same counter for a client, which is why state lives in a shared store rather than in each server’s memory. Sharding the store by client key keeps each client’s state on one node, so a check is a single round trip.
The classic bug is read-then-write: two servers read "99 requests", both allow the request, and both write 100 - the client got 101. Under load this happens constantly.
-- KEYS[1] = bucket key; ARGV = capacity, refill_per_sec, now_ms
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or tonumber(ARGV[1])
local ts = tonumber(b[2]) or tonumber(ARGV[3])
local elapsed = (tonumber(ARGV[3]) - ts) / 1000
tokens = math.min(tonumber(ARGV[1]), tokens + elapsed * tonumber(ARGV[2]))
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return allowed and 1 or 0Partition Redis by a hash of the client key. Each check touches one shard, and adding shards scales throughput roughly linearly.
For very hot paths, keep an approximate local counter on each server and sync with Redis periodically. It removes a network hop at the cost of small overshoots - acceptable for most limits.
A single global counter means cross-region latency on every request. Usually each region enforces its own share of the limit, or regions sync asynchronously and accept brief overshoot.
Store rules in a config service, cache them in every gateway, and refresh on change. Rules are matched by descriptors such as endpoint, tier and client type.
Return Retry-After on 429s, and commonly the limit, remaining requests and reset time on every response, so clients can pace themselves.
A single abusive client concentrates load on one shard. Block it earlier - at the edge or WAF - once it crosses a much higher threshold.
| What fails | Impact | Mitigation |
|---|---|---|
| Redis shard down | Checks for the clients on that shard fail. | Replica failover; meanwhile fail open with a conservative local limit per server. |
| Limiter is slow | Latency is added to every request. | Tight timeouts on the check; treat a timeout like a store failure. |
| Rules service down | New rules cannot be loaded. | Gateways keep the last good rules in memory. |
| Misconfigured rule | Legitimate traffic is rejected. | Shadow mode - log what would be rejected - before enforcing new rules. |
Fail open means allowing traffic when the limiter cannot decide; fail closed means rejecting it. User-facing APIs usually fail open, because rejecting every request is worse than briefly not limiting. Security-sensitive limits, such as login attempts, often fail closed.
What is limited, by which key, exact or approximate, single region or global.
Checks per second and state size - then note that throughput and latency, not memory, are the constraint.
Gateway vs middleware, the 429 response and its headers.
Compare token bucket, fixed window and sliding windows; choose one with a reason.
Shared store, sharding, atomic Lua updates, rules cache and multi-region trade-offs.
Fail-open vs fail-closed, monitoring, and shadow-mode rollout of rules.
Requests from one client spread across many servers, so each server would see only part of the traffic and the client could exceed the limit many times over. Local counters only work as an approximate first check in front of a shared store.
IP limits punish everyone behind a NAT or corporate proxy. Prefer API keys or user IDs for authenticated traffic and keep IP limits generous, reserving them for unauthenticated endpoints.
Give each operation a weight and take that many tokens from the bucket. An expensive export might cost 50 tokens while a read costs 1.
HTTP 429 Too Many Requests with a Retry-After header. Clients should retry with exponential backoff and jitter so they do not all return at the same moment.
Run it in shadow mode first: evaluate the rule and log what it would reject without rejecting anything. Enforce it once the numbers look right.
Split the global limit between regions, or sync counters asynchronously and accept a brief overshoot. A strongly consistent global counter adds cross-region latency to every request, which is rarely worth it.
There is no single best one. Token bucket is the common default for APIs because it allows short bursts with little state. Sliding window counter reduces boundary bursts, leaky bucket smooths output, and sliding window log is exact but memory-heavy.
Token bucket allows bursts up to its capacity and then limits to the refill rate. Leaky bucket queues requests and releases them at a constant rate, so output is smooth but bursts are delayed or dropped.
A client can send the full limit at the end of one window and again at the start of the next, briefly getting up to twice the intended rate. Sliding windows fix this.
It is in-memory and fast, supports atomic operations like INCR and Lua scripts, sets expiries on keys, and shards across a cluster - which covers what a shared limiter needs.
429 Too Many Requests, usually with a Retry-After header telling the client how long to wait.
Most user-facing APIs fail open so a limiter outage does not take down the service, often with a local fallback limit. Security-sensitive limits such as login attempts usually fail closed.
You can practise it free on InstaMock with an AI interviewer that asks for your requirements, pushes on your algorithm and concurrency choices, and gives scored feedback.
Reading a design is not the same as defending one. Book a live 1:1 round with an engineer who has taken hiring decisions: they ask the follow-ups, push on the weak parts, and send written feedback.
Book a 1:1 Mock Interview - ₹499Not ready yet? Practise this question free with the AI interviewer