Skip to content

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
Practice this question

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

AskWhy it mattersA 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.

The requirements menu

RequirementScopeWhy

Identify clients by user id, IP address or API key

Core

The counter key starts with the client identity, so this decides what the gateway must extract from each request before it can count anything.

Limit requests by configurable rules, such as 100 requests a minute per user

Core

The product itself. A rule names a scope, a limit and a window; the algorithm you pick turns those into fields per client.

Answer over-limit requests with 429 and headers for the limit, what remains and when it resets

Core

A well-behaved client backs off when told how long to wait. Without the headers it retries blindly and adds load at the worst moment.

Change rules without a deploy

Core

Limits get tightened during incidents. This forces the rules to live in a store the gateways read from, not in code.

Apply the strictest of several matching rules (per user, per IP, per endpoint)

Optional

Worth taking: real limiters layer rules, and it costs one extra bucket check per matching rule. Leave it if time is short, since the single-rule design extends to it without changing shape.

Per-client overrides so a large customer gets a higher limit

Optional

Cheap to add as a rule whose scope is one client id, and it is the honest answer to a big customer who keeps tripping the default. Mention it; build it if asked.

A dark-launch mode that logs what a rule would have rejected without rejecting

Optional

Stripe's engineering blog recommends launching each limiter this way to tune thresholds before they bite. It is a flag on the rule, not a new component, so it is a good thing to name late in the round.

A concurrency limit on in-flight requests, not just request rate

Optional

Protects slow endpoints that a request-rate limit misses. It needs a decrement when the request finishes, which is a different mechanism; take it as a variant if the interviewer steers there.

Queue over-limit requests and replay them later

Out of scope

Tempting for orders that must not be lost, but it turns a limiter into a queue with its own backlog and ordering problems. Fail fast with 429 and let the client retry.

Analytics over rate limit data

Out of scope

Useful for tuning rules, but it is a separate pipeline fed by log events from the gateway. Name the event and move on.

Keeping counters long term

Out of scope

Counters are live state that expires when a client goes idle. Keeping them would add a durable store to a path that must stay fast.

Strong consistency across every node

Out of scope

Making regions or shards agree on each count before answering would put a cross-node round trip inside the latency budget. Counts may drift a little; the limit is a protection, not a ledger.

Non-functional requirements

RequirementWhat 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

QuantityWorkingResultWhat 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

EntityWhat 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

EndpointNotes

isRequestAllowed(client_id, rule_id) → { passes, remaining, reset_time }

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. remaining is the floor of the tokens left; reset_time is when the bucket next holds a token, from the refill rate. With several matching rules, the gateway calls it for each and the first refusal wins.

HTTP 429 with X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset and Retry-After

Sent by the gateway without touching a service. Retry-After is the standard header a client should honor before trying again; the X-RateLimit-* set is the common convention for the ceiling, what is left and when it resets. Send the X-RateLimit-* headers on allowed responses too, so clients can pace themselves before hitting the wall.

PUT /rules/{id} { limit, window, scope } (admin)

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 limit and window are positive and that scope is one of the three client kinds, and reject anything else with 400.

The high-level design

allowedClientAPI gatewayAllow or 429API servers

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.

pollallowedLua scriptasyncClientAPI gatewayAdminRules storeAllow or 429API serversRedis countersReplicas
The whole design

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?

A concept that helps here: Rate limiting algorithmsA concept that helps here: Approximate countingA concept that helps here: API gateways

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: Sharding and partition keysA concept that helps here: Consistent hashing

When 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: Failing open or failing closedA concept that helps here: Leader election and failover

Concepts this guide uses

Sources

  1. Hello Interview: Design a Rate Limiter (Substack edition of the breakdown)
  2. Alex Xu, System Design Interview, chapter 5: Design a Rate Limiter (reading notes)
  3. Redis documentation: Scripting with Lua
  4. Redis documentation: Scale with Redis Cluster
  5. Redis documentation: High availability with Redis Sentinel
  6. Stripe engineering blog: Scaling your API with rate limiters
  7. MDN: 429 Too Many Requests
Sign in to report a mistake