How to design a rate limiter
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- Choosing the algorithm
- Two servers, one counter
- When the counter store fails
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
A rate limiter sits in the API gateway, decides for each request whether its client has gone over a configured limit, and answers 429 with headers when it has. The answer turns on two things: picking a counting algorithm whose state per client stays tiny (a token bucket holds two fields), and keeping those counts in one shared store that many gateways update atomically, sharded so that the store, not the gateway, is what you scale. The rest is deciding what happens to callers when that store is down.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
Is this a server-side limiter for our own API, and does it sit in the gateway or inside each service? | A client-side limiter can be bypassed by anyone who forges requests, and a limiter inside each service means the count is split across services. The gateway is the one place each request passes through. | Server-side, in the gateway your team owns. Over-limit traffic should stop there, before it reaches a service. |
What identifies a client: a user id, an API key, an IP address, or all three? | It decides what the counter key looks like and how many buckets a request touches. An IP rule on top of a user rule means two checks per request. | All three can appear in rules. A request may match more than one rule, and the strictest one decides. |
How many requests a second do we check, and how much latency may the check add? | The check is on the hot path of each request, so its budget caps what the counter store may cost and tells you how many store nodes you need. | About 100 million daily users and 1 million checked requests a second, each check adding under 10 ms. |
How exact must the limit be? Is a short burst past it acceptable? | An exact rolling-window limit needs a record of recent requests; a limit that tolerates a small overshoot fits in two counters. The answer picks the algorithm. | Limits are a protection, not a billing meter. Counts may lag slightly between nodes, and a small overshoot is fine; a burst allowance is a feature if you can name it. |
When the counter store is unreachable, should the API keep serving or refuse? | There is no default here. Letting traffic through protects availability; refusing protects the services behind the gateway. The right call depends on what the API does. | Pick one and defend it. We'll push on it in the failure discussion. |
How fast must a rule change take effect, and who changes rules? | If an operator must be able to tighten a limit during an incident, rules can't live in a deploy, and you need a path from an admin call to each gateway. | Operators change rules through an admin endpoint without a deploy. Taking effect within tens of seconds is acceptable. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
Under 10 ms added to each request | One round trip to a nearby in-memory store per check, over a connection that is already open, with the rule lookup done from the gateway's own memory. No database, no second hop. |
1 million requests a second across 100 million daily users | Each check reads and writes a counter, so the store takes two operations per check at a rate one node is unlikely to carry. The counters are partitioned on the client key across a group of nodes, and the group's size follows from what a single node can serve. |
Works across many servers; counts may be eventually consistent between nodes | The count lives in a shared store, not in each gateway's memory, so adding a gateway does not raise the effective limit. Replicas and far regions may lag, and the design accepts a small overshoot rather than coordinating on each check. |
Keeps behaving safely when the counter store fails | The gateway needs a timeout on the store call and a chosen behavior when it fires: let the request through or refuse it. Each shard gets a replica that is promoted automatically. |
Low memory per client | Rules out storing a timestamp per request. Each client gets a fixed handful of fields (a token count and a refill time) under one key with an expiry, so idle clients cost nothing after a while. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Requests a fixed window lets through at a window edge | Limit of 100 a minute: 100 in the last second of one minute plus 100 in the first second of the next = 200 in two seconds | Up to 200 requests in about two seconds, twice the limit | Why a plain per-minute counter is the weak answer: the limit is met per window but a burst across the boundary doubles it. |
Memory per client with token buckets | Assume a key of about 40 bytes (client id plus rule id), two numeric fields of 8 bytes each, and Redis overhead of about 50 bytes: roughly 100 bytes a bucket. 100 million clients × 100 bytes = 10 GB; with three rules per client, 30 GB | About 10 GB for one rule per client, about 30 GB for three rules | The memory of the counter store as a whole; spread over 10 to 20 shards, each shard holds a few gigabytes at most, which fits comfortably in memory. |
Memory for a sliding window log per client | Limit of 100 a minute means up to 100 timestamps kept per client; assume 16 bytes per entry in a sorted set: 100 × 16 = 1,600 bytes. 100 million clients × 1,600 bytes = 160 GB | About 1,600 bytes a client, about 160 GB in total, about sixteen times the token bucket | The memory cost of exact counting, and it grows with the limit: a client allowed more requests a minute needs a longer log. |
Counter store shards | If one Redis node handles between 100,000 and 200,000 operations each second, and a check costs one read plus one write, a node serves between 50,000 and 100,000 checks each second. 1 million checks × 2 operations = 2 million operations a second; 1 million ÷ 100,000 = 10; 1 million ÷ 50,000 = 20 | 10 to 20 shards for 1 million checks a second | How many counter nodes the design needs, and why a single node is the first thing that breaks. |
A fresh connection against the latency budget | If opening a new connection to the store costs 20 to 50 ms and the whole check may add under 10 ms: 20 ÷ 10 = 2, 50 ÷ 10 = 5 | A connection setup costs two to five times the entire budget | Why gateways keep a pool of open connections to each shard instead of connecting per check. |
Requests judged by a stale rule when rules are polled | Polling each 30 seconds at 1 million requests a second: 30 × 1 million = 30 million | Up to 30 million requests under the old rule after a change, in the worst case | What polling costs against push: acceptable for routine tuning, painful when an operator is tightening a limit during an incident. |
Requests a sliding window counter misjudges | 0.003% of 1 million requests a second = 0.00003 × 1,000,000 = 30 | About 30 requests a second wrongly allowed or refused | The accuracy you give up with the two-counter approximation, which is small against a protective limit. |
Core entities
| Entity | What it holds |
|---|---|
Rule | What a limit is: who it applies to, which endpoint, how many requests and over what time. |
Client | Whoever is being limited. Not a stored row, but an identity the gateway derives from the request. |
Bucket | The live count for one client under one rule, kept in the counter store and gone when the client goes idle. |
The API
| Endpoint | Notes |
|---|---|
| The gateway's internal call, one per matching rule. It runs the bucket update as one atomic script on the shard that owns the key. |
| Sent by the gateway without touching a service. |
| Writes the rule to the rules store and bumps its version. Gateways pick the change up by polling or a push; until they do, the old rule keeps applying. Validate that |
The high-level design
Step 1 of 4
A gateway that counts in its own memory
Start where the requests already pass: the API gateway. For each request it works out the client (user id from the auth token, address from the forwarded-for header, or API key), finds the matching rule, and checks a counter it keeps in its own memory. If the client is under the limit the request goes on to the API servers; if not, the gateway answers 429 with the limit headers and the request stops at the edge. This is the shape Hello Interview's breakdown recommends over limiting inside each service, since a gateway check adds no extra hop. The weakness is the counter's home: a load balancer spreads one client across many gateways, so each gateway sees a slice of that client's traffic and the real limit becomes the configured limit times the number of gateways.
What breaks first
The deep dives
Choosing the algorithm. A client uses its full allowance in the last second of a minute and does it again in the first second of the next one. Which algorithm do you run on each request, what does it store per client, and what does it let through in that scenario?
Two servers, one counter. Two gateways receive the same client's final allowed request in the same millisecond. How do you make sure one of them is refused, where does the count live, and how many counter nodes does 1 million checks a second need?
A concept that helps here: Atomic read-modify-write
A concept that helps here: Sharding and partition keysA concept that helps here: Consistent hashingWhen the counter store fails. During a traffic spike, the shard holding one slice of the clients' counts stops answering. What does the gateway do with those clients' requests, how does the shard recover, and how does a rule change reach all the gateways?
A concept that helps here: Dynamic configuration
Concepts this guide uses
- Rate limiting algorithms
- Approximate counting
- API gateways
- Atomic read-modify-write
- Sharding and partition keys
- Consistent hashing
- Failing open or failing closed
- Leader election and failover
- Dynamic configuration
Sources
- Hello Interview: Design a Rate Limiter (Substack edition of the breakdown)
- Alex Xu, System Design Interview, chapter 5: Design a Rate Limiter (reading notes)
- Redis documentation: Scripting with Lua
- Redis documentation: Scale with Redis Cluster
- Redis documentation: High availability with Redis Sentinel
- Stripe engineering blog: Scaling your API with rate limiters
- MDN: 429 Too Many Requests