Design a rate limiter

In 2 minutes

I would put the rate limiter at the front of the API, as gateway middleware, so rejected requests never reach the backend. For each request it identifies the caller by API key, reads that plan's limit from a rules config that it caches for a few seconds, and updates a counter in a shared in-memory store with one atomic operation. I would use a token bucket, because it allows a short burst but holds the long-run rate, and it needs just two numbers per client. At 10,000 checks a second and 5 million active clients, the state is about 500 MB, which fits on one node, and I would shard it by client key as it grows. The refill and spend happen in a single server-side script using the store's own clock, so there are no race conditions. Over the limit, the client gets a 429 with a Retry-After header and the remaining quota in headers. If the counter store is down, public reads fail open and are logged, while login and anything that sends messages fail closed. The main trade-off is accuracy against latency: a shared counter is exact but adds one hop to every request.

The question

Clarifying questions

• What do we limit by: API key, user, IP address, or all of them? The key you count against decides what the counter is keyed on, and an IP address is a weak identity when many users share one.
• Is the limit a hard cap, or can a client burst briefly above its average rate? Allowing bursts points to a token bucket. A strict cap per window points to a window counter.
• Do different endpoints or plans have different limits? Per-plan and per-endpoint rules mean the limiter needs a rules store, not one constant.
• Is this one data centre, or many regions that share a limit? A limit shared across regions needs either cross-region counters or a split budget per region.
• If the limiter itself breaks, should requests go through or be blocked? This is the fail-open or fail-closed decision, and it differs between a public read API and a login endpoint.

Requirements

Functional

• Count requests per client and reject those over the configured limit.
• Support different limits per plan and per endpoint, changeable without a deploy.
• Reply with a clear error that says when the client can retry.
• Expose the client's limit and remaining quota in response headers.

Non-functional

• Added latency: p99 under 5 ms per request.
• Accuracy: a client never gets more than about 1.1 times its limit in any window.
• Availability: the limiter is never the reason the API is down.
• Scales to 10,000 checks a second without a single hot spot.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real service.
• 10,000 API requests a second at peak, and 5 million distinct clients active in an hour.
• Each client's limiter state takes about 100 bytes with its key.
• The limit is 100 requests a minute per client, and one in-memory node handles about 100,000 simple operations a second.

The arithmetic:

• Checks per second: Every request is checked once → 10,000/s, so one counter node has 10x headroom
• Memory for counters: 5M clients × 100 bytes → 500 MB, which fits on one node
• Memory for a request log: 100 timestamps × 8 bytes = 800 bytes per client; × 5M clients → 4 GB, eight times the counter design
• Added latency: One round trip inside the same zone, assumed at about 1 ms → ≈ 1 to 2 ms, inside the 5 ms budget

High-level design

Every request passes through the Rate limiter, which sits at the front of the API so rejected traffic never reaches the backend. It identifies the caller from the API key, then asks two things.

First, what is this caller's limit? The limiter reads that from the Rules config, which it caches locally and refreshes every few seconds. Second, has the caller used it up? That lives in the Counter store, a fast in-memory store shared by all limiter instances, so the count is global rather than per instance.

If the caller is under the limit, the request goes on to the Backend API and its Database. If not, the limiter answers right away with HTTP 429 and a Retry-After header, and the backend never sees the request. If the counter store is down, the limiter applies the fail-open or fail-closed rule for that endpoint.

How a request flows

A request under the limit

1. A request arrives carrying the client's API key.
2. The limiter finds the limit for this key's plan, usually from its local copy of the rules.
3. It runs one atomic update on the shared counter and learns the client is under the limit.
4. The request is forwarded to the backend, with the remaining quota attached for the response headers.
5. The backend does its normal work, including its database call.
6. The response returns to the limiter, which adds the rate limit headers.
7. The client receives the response and can see how much quota it has left.

A request over the limit

1. A request arrives from a client that has already used its quota.
2. The atomic update shows the counter is at the limit, so this request is not counted as allowed.
3. The limiter replies at once with 429 Too Many Requests and a Retry-After header. The backend is never touched.

The counter store is down

1. A request arrives at the limiter as usual.
2. The call to the counter store times out after a few milliseconds, so the limiter cannot count.
3. A public read endpoint fails open: the request goes through and the miss is logged. A login endpoint would fail closed instead.

Deep dive: choosing the algorithm

All four of these answer the same question: has this client sent too much recently?

• Fixed window counter. Count requests in each clock minute, reset at the boundary. It is trivial and cheap, but it has an edge problem. With a limit of 100 a minute, a client can send 100 requests at 12:00:59 and 100 more at 12:01:00. That is 200 requests in two seconds, double the limit.
• Sliding window log. Store a timestamp for every request and count those in the last 60 seconds. It is exact, but memory grows with the limit: our estimate shows eight times the memory of a counter design.
• Sliding window counter. Keep the count for the current window and for the previous one, then weight the previous window by how much of it still overlaps the last 60 seconds. If the previous window had 84 requests, the current one has 36, and we are 25% into the current window, the estimate is 84 × 0.75 + 36 = 99. It uses two numbers per client and is close to exact if traffic is fairly even.
• Token bucket. Each client has a bucket that holds up to b tokens and refills at r tokens a second. A request takes one token and is rejected if the bucket is empty. This allows a short burst up to b while holding the long-run rate to r.

A token bucket needs only two stored values: the token count and the time of the last refill. You do not need a timer. On each request, compute the refill lazily: add elapsed seconds × r, cap at b, then subtract one.

My pick is the token bucket for most API limits, because real clients are bursty and a burst of ten requests in a second is usually fine. If the product promise is a strict count per minute, I would use the sliding window counter. I would avoid the fixed window unless the edge burst truly does not matter.

Deep dive: shared counters and atomic updates

If each limiter instance keeps its own counter, a client spread across ten instances can send up to ten times its limit. So the state must be shared. A fast in-memory store, such as Redis, works well: it supports atomic increments, key expiry (TTL) and scripts that run as one step.

The simplest version is a fixed-window counter. Increment a key such as the client id plus the window number, and set it to expire shortly after the window ends. The trap is doing this in two calls. If the process dies between the increment and the expiry, the key lives forever. The fix is to send both in one script, or to set the expiry only when the increment returns 1, inside the same atomic step.

A token bucket needs a read, a calculation and a write. Done from the limiter, two instances can both read the same token count and both spend it. Put the whole refill-and-spend step in one server-side script so the store runs it atomically. Use the store's own clock inside the script, not the clocks of the limiter servers, so clock skew between them cannot grant or steal tokens.

Shard the counter store by client key so no node is hot, and replicate for failover. A replica can lag, so a failover may forget a few seconds of counts. For a rate limiter that is acceptable, because the cost is a briefly generous limit, not lost data.

To cut round trips, an instance can lease a small batch of tokens, say 10, from the shared store and spend them locally. The cost is accuracy: a client can briefly exceed its limit by up to the leased amount across instances. State this trade-off out loud.

Deep dive: placement, failure and the response

Run it in the API gateway or as middleware at the front of the service, before any real work. Rejecting early protects the backend and the database, which is the point of the whole exercise. A separate network hop to a standalone limiter service adds latency; middleware that talks to the shared counter store adds only that one hop.

When the limiter fails, choose per endpoint. Fail open means let the request through. It protects availability, and it is right for most read endpoints. Fail closed means reject. It protects the backend and money, and it is right for login, password reset and anything that sends SMS or email, where unlimited traffic is itself the attack. A good middle path is a coarse local limiter that takes over when the shared store is unreachable.

The rejection. Reply with HTTP status 429 Too Many Requests and a Retry-After header giving the seconds to wait. Add headers that show the limit, the remaining quota and the reset time. Common names are X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset. There is no single settled spelling, so match what your clients already expect. A short JSON body that names the limit and the rule helps developers debug.

Tell clients what to do: wait for the Retry-After time, then retry with exponential backoff and a little random jitter, so a crowd of rejected clients does not come back in the same second.

Make the rules data, not code. Keep limits per plan and per endpoint in a config store, cache them in each limiter instance for a few seconds, and let support staff change a limit without a deploy.

Trade-offs

• Algorithm: Token bucket over Fixed window counter. It allows a bounded burst and has no spike at the window edge, with just two numbers per client. The cost is an atomic read-modify-write script.
• Where counts live: A shared in-memory counter store over A counter in each limiter instance. The limit is global and accurate. The cost is one network hop per request and a dependency that must be kept healthy.
• Failure mode: Fail open for most endpoints over Fail closed everywhere. A counter outage should not take the API down. The cost is no protection during the outage, so sensitive endpoints fail closed.
• Where it runs: Middleware at the API gateway over A check inside every backend service. One place enforces every rule and rejected traffic never reaches the backend. The cost is that the gateway is on the critical path of every request.

Common follow-up questions

How do you limit by IP address when many users share one address?
Prefer the API key or the signed-in user, and use IP limits only for requests that have no identity yet, such as sign-up. Set IP limits loosely, because an office or a mobile carrier can put thousands of people behind one address. Combine both: a loose limit per IP and a strict one per account.

How would you stop an attack spread across thousands of keys?
Per-key limits alone do not help, because each key stays under its limit. Add a global limit per endpoint, limits per IP range and per account age, and signals such as new accounts all sending the same call. At that point the limiter works with other defences, such as a web firewall and bot detection.

How do you change a limit without a deploy?
Store rules in a config store keyed by plan and endpoint. Each limiter instance caches them and refreshes every few seconds, or receives a push on change. A new limit then applies everywhere within seconds.

How would limits work across several regions?
The simplest design gives each region its own share of the budget, for example half of the limit each, with local counters. It is fast and never crosses regions, but it can be unfair if a client's traffic is lopsided. Syncing counters between regions gives a fairer count at the price of latency and of failures when the link breaks.