Design a Rate Limiter
Asked both as an algorithm question and as a distributed system question; be ready for either.
- 10K req/speak traffic, one script call each
- ~200 MBmemory for 1M active keys
- < 5 msadded p99 latency target
Show what to say
“I'd use a token bucket per user, API key or IP, stored in Redis and updated by one Lua script on Redis's own clock, so the check is atomic across every app server. The gateway answers 429 with Retry-After. If Redis dies, most endpoints fail open to a local bucket, but login and OTP fail closed.”
Trade-offs
- Central Redis vs local only: accurate global limits, but you add a network hop and a dependency.
- Token bucket vs sliding window: bursts and tiny state, but a looser 'per minute' limit.
- Fail open vs closed: open keeps the API available, but allows abuse during outages.
Bring it up before they ask
If Redis is down or slow, fail fast with a 50 ms timeout, then fall back per rule: a local bucket for normal endpoints, a 503 for login and payments.
New to the words? Read the one-minute primer
Give each user a in , updated by one Lua script so the check is atomic. Over the limit, the gateway answers 429. If Redis dies, most endpoints keep working and login does not.
Functional
- Limit per user, API key or IP, e.g. 100 requests per minute
- Different rules per endpoint and plan
- 429 with Retry-After and the remaining quota
Non-functional
- Under 5 ms added p99
- Consistent across N app servers
- A limiter outage must not take the API down
- Memory-bounded for millions of keys
Out of scope
- Billing for overages
- Volumetric DDoS (the CDN/WAF does that)
Two questions in one: which algorithm, and how to make it hold across 50 servers.
Scope and scale
Read more · 86 words
- Limit the user, the key or the IP?
- Bursts allowed, or smooth traffic?
- Reject, or just warn?
- One region or global?
- If the limiter fails, serve or block?
Size it:
One handles this. Split by key with Redis Cluster when it can't.
Choosing an algorithm
Five algorithms, one real question: how much burst do you allow?
Read more · 150 words
| Algorithm | State per key | Behaviour |
|---|---|---|
| Fixed window | 1 counter | Simplest; 2× bursts at the edges |
| Sliding log | Every timestamp | Exact; memory grows |
| Sliding window counter | 2 counters | Nearly exact; good for quotas |
| Token bucket | Tokens + time | Allows bursts; the API default |
| Leaky bucket | Queue | Smooth; adds delay |
Match the traffic to the algorithm:
| Traffic | Pick | Why |
|---|---|---|
| A page fires 20 calls at once | Token bucket | The burst passes, the average stays 5 a second |
| Paid quota of 100 a minute | Sliding window counter | No edge doubling |
| Calls to a fragile partner | Leaky bucket | Steady rate out |
A bucket refills at a steady rate. Each request spends a token. Bursts pass, the average holds. Fire a burst at it.
A fixed window resets on the minute. At 100 a minute, a client sends 100 at 11:59:59 and 100 at 12:00:00: 200 in two seconds. Try it here.
API and data model
The contract is mostly headers. Here is a 429.
Read more · 115 words
| Header | When | Meaning |
|---|---|---|
RateLimit-Limit | Every response | Bucket capacity (the burst size) |
RateLimit-Remaining | Every response | Whole tokens left right now |
RateLimit-Reset | Optional | Seconds until the bucket is full again |
Retry-After | On 429 (and 503) | Seconds to wait, from the token deficit |
The gateway calls check(key, rate, capacity) and gets { ok, remaining, retryAfterMs }.
Keys in :
| Key | Holds | Expiry |
|---|---|---|
rl:<rule>:<id> | Hash: tokens (float), ts (ms, Redis time) | Time to refill completely |
sw:<key>:<window> | String: request count in that window | Two windows |
Rules are cached config. plans scales them per tier.
HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 20
RateLimit-Remaining: 0
Retry-After: 1
Content-Type: application/json
{"error":"Too many requests"}{
"api": { "ratePerSec": 5, "capacity": 20, "key": "user", "failClosed": false },
"login": { "ratePerSec": 0.1, "capacity": 5, "key": "ip", "failClosed": true },
"plans": { "free": 1, "pro": 10 }
}Architecture
One server can count in memory.
Read more · 55 words
Behind 50, each counting alone, a user capped at 100 a minute could send 5,000. Shared state fixes that.
Play Allowed, Burst exhausted (a 429) and down (the local fallback).
Tap any box to see what it is and what it talks to.
- Client
- API gateway
- Cache
- Service
Text description
- GET /api/orders arrives with API key k_42. The rule for this plan is 5 tokens per second, bursts up to 20.
- The gateway runs the token-bucket script on rl:api:k_42. Read, refill, take and write happen in one atomic step.
- Redis replies [1, 19, 0]: allowed, 19 tokens left, no wait. The whole check took under a millisecond.
- The request is forwarded to the service.
- The service answers.
- 200 OK, with RateLimit-Limit: 20 and RateLimit-Remaining: 19 so the client can pace itself.
Step-by-step answer
In one line each:
Read more · 258 words
Clarify
Who, how hard.
Pick an algorithm
Bursts or strictness.
Place the state
Shared .
Make it atomic
One Lua script.
Failure and UX
Open or closed.
In full:
Identity
The user or key first. The IP only for anonymous traffic.
Algorithm
A by default. A sliding window counter for strict "100 per minute" quotas.
Where to enforce
Global limits at the gateway, where rejecting is cheap.
State
One hash per key, expiring once it is full.
Atomicity
One Lua script reads, refills, takes and writes. A separate
GETandSETwould race: two servers read "1 token left" and both spend it.tokens = math.min(cap, tokens + math.max(0, now - ts) * rate / 1000) if tokens >= 1 then tokens = tokens - 1; allowed = 1 end redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)Clock
Use Redis's own
TIME, so a fast server clock can't mint tokens.Response
429withRetry-After, plus quota headers on every response.Failure policy
- Normal endpoints fail open, to a local bucket.
- Login, OTP and payments fail closed (
503). - Fail fast: a 50 ms timeout, no retries, or the limiter becomes the outage.
Rules and regions
Rules per plan come from cached config.
Observability
Count allowed and limited calls. Alert on 429 spikes.
Implementation
Read more · 59 words
- The in-memory
TokenBucketis the single-server answer and the fallback. - The Lua script uses 's clock and works out the retry delay.
middleware.jskeeps fallback buckets in the boundedLRUfrom the caching lesson.
// In-memory token bucket: a single instance, and the fallback when Redis is down
export class TokenBucket {
constructor({ ratePerSec, capacity, now = () => Date.now() }) {
Object.assign(this, { ratePerSec, capacity, now, tokens: capacity, last: now() });
}
take(n = 1) {
const t = this.now();
this.tokens = Math.min(this.capacity, this.tokens + ((t - this.last) / 1000) * this.ratePerSec);
this.last = t;
if (this.tokens >= n) {
this.tokens -= n;
return { ok: true, remaining: Math.floor(this.tokens), retryAfterMs: 0 };
}
return { ok: false, remaining: 0, retryAfterMs: Math.ceil(((n - this.tokens) / this.ratePerSec) * 1000) };
}
}Failure modes
Read more · 56 words
| What breaks | Effect | Mitigation |
|---|---|---|
| Redis down | No shared state | Fail fast; local bucket (open) or 503 (closed) |
| Redis slow | Every request slows | 50 ms timeout, then treat as down |
| One key floods | A hot Redis shard | A local pre-limiter |
| Skewed clocks | Wrong refills | Redis TIME in the script |
| Millions of idle keys | Memory growth | Expire them |
Trade-offs
Read more · 111 words
| Choice | Pros | Cons |
|---|---|---|
| Central Redis vs local | Accurate global limits | A hop and a dependency |
| Token bucket vs sliding window | Bursts, tiny state | Looser "per minute" |
| Fail open vs closed | Stays up | Abuse during outages |
| Gateway vs in-service | Rejects early | Blind to cost |
Follow-up questions
Per-IP or per-user limits, and what about shared NATs?
By user or key. Per-IP only for anonymous traffic, and generous. For login, use both.
How do you handle 1M distinct keys?
Expiry drops idle buckets. Cluster scales it, since each script touches one key.
How do you avoid clock skew between servers?
Read the time from Redis inside the script.
How do you rate-limit globally across regions?
Give each region a share, or sync counters later and accept a brief overshoot.
Rate limiting or load shedding?
Both. is fair per client. drops low-priority work when overloaded.
Check yourself
Question 1 of 3Score 2 out of 3 or better to mark this page complete.
Patterns behind this
The coding patterns this design is built on. Practise them and the design questions get easier.
- Sliding WindowA sliding-window limiter keeps a window over recent request timestamps: evict the old ones, count the rest.
- Design Data Structures: LRU, LFU and FriendsA limiter keeps one small record per user, such as a token bucket, and updates it in O(1) per request: a class whose every method has a time budget.