# Rate limiting

> Choose what to limit and where, compare fixed window, sliding log, sliding counter and token bucket on the same traffic, and build a correct distributed limiter on Redis.

System Design roadmap · Communication & reliability · 19 min read · https://levelcode.org/roadmaps/system-design/rate-limiting

A rate limiter caps how much work a client can ask for in a period of time. It protects capacity from runaway scripts and abusive clients, keeps one tenant from starving the rest, puts a ceiling on spend for expensive operations, and slows down attacks such as credential stuffing. The idea is simple; the details — which algorithm, which key, where the counters live, and what happens when the limiter itself fails — decide whether it protects you or becomes a new outage. (The DevSecOps API-gateway lesson configures limits at the edge; this lesson is about designing the limiter itself.)

## Decide what you're limiting

Before choosing an algorithm, answer four questions:

- **Who is the client?** An API key, a user ID or a tenant if you know who's calling; the IP address for anonymous traffic and login endpoints (accepting that many users can share one IP behind a NAT).
- **What does a request cost?** A search may cost 100 times a profile read. Charging requests a *weight* rather than counting them equally makes limits track real load.
- **What are the limits for?** A burst limit protects servers (20 per second); a quota protects the business (10,000 per day on the free plan). They're often separate rules on the same request.
- **Where is it enforced?** At the edge (CDN, load balancer or gateway) to stop floods cheaply; in the service for limits that need application knowledge, such as per-tenant plans; and in **clients** that call your dependencies, so you never exceed a partner API's limits yourself.

## Four algorithms on the same traffic

All four below allow *limit* requests per *window* in the long run. They differ in what they allow in the short run. See [rate-limiting algorithms](https://levelcode.org/concepts/rate-limiting-algorithms) for a one-page comparison.

**Fixed window.** Count requests per aligned window: 12:00:00–12:00:59, 12:01:00–12:01:59, and so on. One counter per key, trivially cheap. The flaw is at the boundary: a client can send a full window's worth at 12:00:59 and another at 12:01:00, **twice the limit within two seconds**.

**Sliding log.** Store a timestamp for each accepted request and count those in the last *window* seconds. Exact — it never lets more than *limit* requests through in any span of length *window* — but it stores one entry per request, which is memory-hungry at high limits.

**Sliding window counter.** Keep fixed-window counters but estimate the sliding count by weighting the previous window by how much of it still overlaps:

```text
estimate = previous_count × (1 − elapsed_in_current / window) + current_count
```

It needs just two counters per key and is very close to exact. Cloudflare reported it within a fraction of a percent of a true sliding window on real traffic. It slightly over-admits right after a boundary, as you'll see below.

**Token bucket.** Each key has a bucket holding up to *capacity* tokens, refilled continuously at *rate* tokens per second. A request takes a token or is rejected. Capacity sets the burst you tolerate, rate sets the sustained average, and the state is two numbers. It's the most common choice for APIs because "bursts are fine, sustained floods aren't" matches how real clients behave. (A **leaky bucket** is the mirror image: requests queue and drain at a fixed rate, smoothing output rather than rejecting bursts.)

Run the same traffic through all four. Start with the window-edge traffic and compare the last column of the table; then try the burst.

> **Interactive: One request stream, four limiters.** On window-edge traffic the fixed window admits 10 requests within about two seconds against a limit of 5, while the sliding log never exceeds 5 in any 10-second span. On the burst, the token bucket admits a full bucket at once and then throttles to its refill rate. Try it: https://levelcode.org/labs/rate-limiter

| | Memory per key | Boundary bursts | Allows a short burst | Typical use |
|---|---|---|---|---|
| Fixed window | 1 counter | Up to 2× limit | Yes, up to the whole window | Daily or monthly quotas |
| Sliding log | 1 entry per request | Never over the limit | Up to the limit | Low limits that must be exact (logins) |
| Sliding counter | 2 counters | Slightly over, rarely | Up to the limit | High-volume API limits |
| Token bucket | 2 numbers | Up to capacity + rate × window | Yes, up to capacity | API rate limits, client-side throttling |

## Distributed rate limiting

With one server, an in-memory map of counters works. With twenty servers behind a load balancer, each would see only a twentieth of a client's traffic, so per-server counters let the client through at 20 times the intended rate. Three designs, in order of how often you'll see them.

**A shared store.** Keep the counters in Redis, which every server consults. A fixed window is two commands:

```text
INCR   rl:{api_key}:202610271205      → returns the count for this minute
EXPIRE rl:{api_key}:202610271205 120  (set on the first increment)
```

Anything more complex must be **atomic**: if a server reads the token count, decides, and writes the new count in separate commands, two servers can both read "1 token left" and both admit a request. Run the whole decision as a Lua script, which Redis executes without interleaving other commands:

```lua
-- KEYS[1] = bucket key; ARGV = capacity, refill per second, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

local t   = redis.call('TIME')                       -- Redis's clock, not each app server's
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)

local retry_ms = 0
if not allowed then retry_ms = math.ceil((cost - tokens) / rate * 1000) end
return { allowed and 1 or 0, math.floor(tokens), retry_ms }
```

```go
var tokenBucket = redis.NewScript(tokenBucketLua) // the script above; EVALSHA with EVAL fallback

type Decision struct {
	Allowed    bool
	Remaining  int64
	RetryAfter time.Duration
}

func (l *Limiter) Allow(ctx context.Context, key string, cost int) (Decision, error) {
	res, err := tokenBucket.Run(ctx, l.rdb, []string{"rl:" + key}, l.capacity, l.ratePerSec, cost).Int64Slice()
	if err != nil {
		return Decision{}, err
	}
	return Decision{Allowed: res[0] == 1, Remaining: res[1], RetryAfter: time.Duration(res[2]) * time.Millisecond}, nil
}
```

Using Redis's own `TIME` avoids clock skew between app servers, which would otherwise let a server with a fast clock mint extra tokens. The key expires once a full bucket's refill time has passed, so idle clients cost no memory. In Redis Cluster, every key a script touches must live in one hash slot; a single key per bucket satisfies that.

**Local limits with a global budget.** Each server enforces *limit / N* locally and periodically syncs with the others. No network call per request, at the cost of accuracy when traffic is uneven across servers. Envoy and many gateways combine a local token bucket (cheap, approximate) with a global service for the limits that must be exact.

**A dedicated rate-limit service.** A small service (Envoy's ratelimit, or your own) owns the counters and answers "allowed?" over gRPC. It centralises rules and metrics, and it's one more dependency on the request path.

### When the limiter fails

If Redis is unreachable, the limiter must choose:

- **Fail open** (allow everything): the service stays up, but unprotected. Right for most limits that guard against overload, as long as other protections such as [load shedding](https://levelcode.org/concepts/load-shedding) exist.
- **Fail closed** (reject everything): safe for limits that guard money or security — SMS sends, password attempts, expensive AI calls — where unlimited traffic does real damage.

Either way, give the Redis call a tight timeout (a few milliseconds) so a slow limiter can't slow every request.

## Telling clients what happened

A rejected request should return **429 Too Many Requests** with enough information to back off correctly:

```http
HTTP/1.1 429 Too Many Requests
Retry-After: 3
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1793098503
Content-Type: application/problem+json

{"type": "https://api.example.com/errors/rate-limited", "title": "Too many requests", "detail": "Limit of 100 requests per minute exceeded."}
```

`Retry-After` is standard HTTP and tells the client how long to wait. The `X-RateLimit-*` headers are a widespread convention (an IETF draft standardises them as `RateLimit` and `RateLimit-Policy`); sending remaining capacity on *successful* responses too lets well-behaved clients slow down before they hit the wall.

On the client side, the rules are: honour `Retry-After`; retry 429s and 503s with exponential backoff and jitter, never in a tight loop ([retries, backoff and jitter](https://levelcode.org/concepts/retries-with-backoff)); and run your own token bucket in front of any partner API with a published limit.

> [!WARNING]
> A rate limit is not an authentication or abuse system on its own. Attackers rotate IPs and keys. Use limits to bound damage, alongside authentication, bot detection and per-account controls.

## Practice

Design rate limiting for a public REST API with three plans — Free (60 requests per minute, 5,000 per day), Pro (600 per minute, 200,000 per day) and Enterprise (custom). Search requests cost 5 units; everything else costs 1. The API runs on 30 instances behind a gateway. Also protect `POST /login` against credential stuffing.

Specify the algorithms, keys, where the state lives, the failure behaviour, and the responses.

**Solution**

**Per-minute limits: token bucket per API key**, capacity equal to the per-minute limit (60 or 600) and refill of limit/60 tokens per second, so a client can burst a full minute's allowance but not sustain more. Search costs 5 tokens, other endpoints 1. State lives in Redis, updated by the atomic Lua script so all 30 instances share one bucket per key. Enterprise limits come from a per-customer configuration lookup, cached in each instance for a minute.

**Daily quotas: fixed window per API key per UTC day**, using `INCRBY` with the request cost on a key like `quota:{key}:2026-10-27`, set to expire after 48 hours. Boundary bursts don't matter for a daily business quota, and one counter is cheapest. Check the minute limit first, then the quota.

**Where:** the gateway does a coarse per-IP limit for unauthenticated traffic (to stop floods before they reach the instances); the service enforces plan limits, since it knows the plan and the per-endpoint costs.

**Failure behaviour:** for plan limits, fail open with a 5 ms Redis timeout and an alert, relying on load shedding to protect capacity. For login, fail closed.

**Login:** a sliding log (exact at low limits) keyed by account identifier — 5 failed attempts per 15 minutes — plus a token bucket keyed by IP for total attempts, for example 30 per minute. After the account limit trips, require a CAPTCHA or delay the response rather than revealing whether the account exists.

**Responses:** 429 with `Retry-After` (from the script's retry time, rounded up to whole seconds), `X-RateLimit-Limit/Remaining/Reset` on every response, and a problem+json body naming the limit that was hit (per-minute or daily). Quota exhaustion says when the quota resets and links to the upgrade page.

## Key takeaways

- Decide the client key, the cost of each request, burst limits versus quotas, and where each limit is enforced before choosing an algorithm.
- Fixed windows are cheap but admit up to twice the limit at boundaries; sliding logs are exact but memory-hungry; sliding counters approximate them in two counters.
- Token buckets allow bursts up to capacity and a sustained rate equal to the refill — the usual choice for APIs.
- Distributed limiters need shared state with atomic updates (Redis plus Lua using Redis's clock), or local limits with a global budget.
- Decide deliberately whether to fail open or closed, and keep the limiter's timeout tight.
- Return 429 with `Retry-After` and remaining-capacity headers; clients should back off with jitter.

## Quiz

1. A fixed-window limiter allows 100 requests per minute. What's the most a client can get through in about two seconds?

   A. 100
   B. About 3
   C. 200
   D. Unlimited

   **Answer: C.** 100 at the very end of one window and 100 at the very start of the next. Sliding windows and token buckets with matching parameters prevent most of this boundary burst.

2. Why must a Redis-backed token bucket run its read-decide-write as a Lua script (or another atomic operation)?

   A. Lua is faster than Redis commands
   B. Otherwise two servers can read the same token count, both admit a request, and overspend the bucket
   C. Redis can't store numbers outside Lua
   D. It lets the script use each app server's local clock

   **Answer: B.** Separate read and write commands from different servers interleave. A script runs atomically, so each decision sees the result of the previous one. Using Redis's TIME also avoids skew between app servers' clocks.

3. A token bucket has capacity 20 and refills 2 tokens per second. A client that has been idle for a minute sends 30 requests at once. How many succeed immediately?

   A. 2
   B. 20
   C. 30
   D. 120

   **Answer: B.** The bucket refills only up to its capacity, so after a long idle period it holds 20 tokens. Twenty requests pass; the rest are rejected until tokens refill at 2 per second.

4. Redis, which backs your rate limiter, becomes unreachable. For which limit is failing closed the right choice?

   A. General per-key API limits that protect against overload
   B. Limits on sending SMS verification codes, which cost money per message
   C. Per-IP limits on loading the public homepage
   D. Any limit; failing closed is always safer

   **Answer: B.** Unlimited SMS sends cause direct financial damage and enable abuse, so rejecting is safer. For general overload limits, failing open keeps the service up while other defences such as load shedding protect capacity.